当前位置：文档之家 › 第四章 高斯消元法与选主元

第四章 高斯消元法与选主元

  • 格式：pdf
  • 大小：420.44 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

高斯消元法(完整)

高斯消元法(完整)

高斯消元法解线性方程组在工程技术和工程管理中有许多问题经常可以归结为线性方程组类型的数学模型，这些模型中方程和未知量个数常常有多个，而且方程个数与未知量个数也不一定相同。

那么这样的线性方程组是否有解呢？如果有解，解是否唯一？若解不唯一，解的结构如何呢？这就是下面要讨论的问题。

一、线性方程组设含有n 个未知量、有m 个方程式组成的方程组a x a x a xb a x a x a x b a x a x a x b n n n n m m mn n m11112211211222221122+++=+++=+++=⎧⎨⎪⎪⎩⎪⎪ （3.1） 其中系数a ij ，常数b j 都是已知数，x i 是未知量（也称为未知数）。

当右端常数项b 1,b 2, …, b m 不全为0时，称方程组（3.1）为非齐次线性方程组；当b 1=b 2= … =b m = 0时，即a x a x a x a x a x a x a x a x a x n n n n m m mn n 111122121122221122000+++=+++=+++=⎧⎨⎪⎪⎩⎪⎪ （3.2） 称为齐次线性方程组。

由n 个数k 1, k 2, …, k n 组成的一个有序数组（k 1, k 2, …, k n ），如果将它们依次代入方程组（3.1）中的x 1, x 2, …, x n 后，（3.1）中的每个方程都变成恒等式，则称这个有序数组（k 1, k 2, …, k n ）为方程组（3.1）的一个解。

显然由x 1=0, x 2=0, …, x n =0组成的有序数组（0, 0, …, 0）是齐次线性方程组（3.2）的一个解，称之为齐次线性方程组（3.2）的零解，而当齐次线性方程组的未知量取值不全为零时，称之为非零解。

（利用矩阵来讨论线性方程组的解的情况或求线性方程组的解是很方便的。

因此，我们先给出线性方程组的矩阵表示形式。

）非齐次线性方程组（3.1）的矩阵表示形式为：AX = B其中A = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡mn m m n n a a a a a a a a a 212222111211，X = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡n x x x 21，B = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡n b b b 21 称A 为方程组（3.1）的系数矩阵，X 为未知矩阵，B 为常数矩阵。

04线性方程组(工程数学)

04线性方程组(工程数学)
9
2. 列主元消元法
列主元消元法的计算步骤： 在进行第 k ( k = 1, 2,
, n - 1) 步消元时， 首先在第 k 列下
面 的 n - k +1 个 元 素 中 选 取 绝 对 值 最 大 的 元 素
k k ( 然后将列主元所 a (pk−1) , 即 a (pk−1) = max aikk −1) 作为列主元素， k≤i
⎡ a11 ⎢a A = ⎢ 21 ⎢ ⎢ an1 ⎣
a12 a22 an 2
a1n ⎤ ⎡1 ⎢l a2 n ⎥ 1 21 ⎥，L= ⎢ ⎢ ⎥ ann ⎥ ⎢ln1 ln 2 ⎣ ⎦
⎤ ⎡u11 u12 ⎥ ⎢ u22 ⎥ ，U = ⎢ ⎥ ⎢ 1⎥ ⎢ ⎦ ⎣
u1n ⎤ u2 n ⎥ ⎥. ⎥ unn ⎥ ⎦
【思路】可以利用消去法对矩阵 A 进行三角分解；也可以利用紧凑格 直接完成 式的计算公式按顺序计算出单位下三角阵 L 和上三角阵 U ， 求 A = LU 的三角分解.再分别代入两个三角方程 Ly = b 和 Ux = y 中， 出方程的解 x ．
有两个乘数2和-4，每个乘数正好可以产生一个零，用来记-乘数，
⎡ 1 −1 2 −2 ⎤ ⎡ 1 −1 2 −2 ⎤ ⎡ 1 −1 2 −2 ⎤ [ A b] = ⎢−2 1 −1 2 ⎥ → ⎢ −2 −1 3 −2⎥ → ⎢ −2 −1 3 −2⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 4 −1 2 1 ⎦ ⎣ 4 3 −6 7 ⎦ ⎣ 4 −3 3 1 ⎦ ⎣
17
定理 1 矩阵 A 可以三角分解的条件如下：
1. 若矩阵 A 的所有顺序主子式不等于零; 2. 若矩阵 A 对称正定; 3. 若矩阵 A 严格对角占优，即：
akk > ∑ akj , k = 1, 2,

高斯消元法

高斯消元法

选取主元 在消元过程进行到第k步时，即正要用第k行去消后面 的行时。我们需要把第k行除以akk 然后乘上aik 加到第i行 (1) 上(i k)。显然如果akk 特别小的话，不仅有可能损失精度， 还有可能造成溢出。为了避免这种情况，我们需要选取主 元: 在系数矩阵右下角选取n-k+1阶子矩阵中绝对值最大 的元素aij ，交换第k行与第i行，交换第k列与第j列。注意到 列的交换会使得解的顺序混乱，因此我们需要记录列的交 换过程，以便最后还原。当然由于交换后akk 的绝对值是最 大的，所以如果akk =0我们就可以直接终止计算了，因为这 时无法找到唯一的一组解。 （选取主元的过程并不影响时间 复杂度， 整个过程的时间复杂度仍然是O（n3 )）
nn n n
高斯约当消元法
高斯约当消元法是一种不需要回代的消元法，可以算 是高斯消元法的一种改进，它与高斯消元法唯一的不同是： 高斯约当消元法每次不仅要把主对角线以下的元素消为0 ,还要把主对角线以上的元素消为0。 自然消完后系数矩阵只 有主对角线上有非0元素， 所以就不需要回代外，我们还可以使 用迭代法或者共轭梯度法来解线性方程组，限于篇幅这里 不作介绍， 有兴趣的同学可阅读相关资料。
-3-
-4-
我们的感言
by Mr Joke
冬去春来，转眼鼠年已经过去。在此新春佳节之际，我 谨代表OIBH管理团队恭祝各位牛年快乐！ 在过去的一年里，我们OIBH管理团队在坚持做好日常 而这并不意味着，我们会改变论坛定位。OIBH始终要秉承 信息学初学者之家的定位。家是最根本的定义。我们力求提 供人性化的管理，使每一位oier体会到家的感觉。其次是初
论坛管理的同时，积极探索。尝试了建立同城区、交流区、 学者。我们论坛的主要群体应该是针对信息学初学者， 是给 宠物中心、打造OOJ等一些列管理措施。在过去的一年里， 大家一个入门的平台， 打造一个交流的平台。我们不能因为 我们有失败也有成功。然而我们胜不骄败不馁， 在成功中总 结经验，在失败里总结教训。在新的一年里，我们将立足于 现在， 以求真务实的态度审视未来。将团队管理理念转变为 少而精。我们力求每年认真的做好一两件事实。 同时我们将舍弃无用而庞大的部分， 打造精品论坛。然 论坛大牛的人数增多而放弃基础区的建设。基础区的建设， 永远是我们工作的重中之重。与此同时， 我们立志为给大家 进一步学习提供一个良好的平台。如果您对我们的管理有 任何意见或建议， 请与我们联系。

数值计算方法 高斯消元法、主元素法 - 高斯消元法、主元素法-1

数值计算方法 高斯消元法、主元素法 - 高斯消元法、主元素法-1

求 f (4) .
c b a 1
高 斯
设所求二次函数为 f ( x) ax2 bx c ，其待定系数满足c 2b 4a 2 解此方程组得 f ( x) 3 x2 11 x 3 ，则 f (4)= 5 c 3b 9a 0
消
22
元
思 考 在一次智力测验中，老师写出某个数列的前两项为1，2，让学生按照前两
9
预备知识——Cramer法则
b1 a12
a1n
b2 a22
a2 n
高
x1
D1 D
bn
an2 A
ann ,
斯
消
元
a11 a12
b1
法
a21 a22
b2
xn
Dn D
an1
an 2 A
bn ,
D0
a11
b1
a1n
a21
b2
a2n
,
xk
Dk D
an1
bn A
ann ,
,
优点：收敛、稳定、结论可靠 缺点：计算量过大 计算量： M＝(n2 1)n!n 当 n 10 时，M 0.359251210109 当n 40时，M 0.13046485371042
a
(2) 2j
ai(22)
a
(2) 22
方程右边
bi(3)
bi(2) b2(2)
ai(22)
a
(2) 22
方程左边
ai(jk 1)
ai(jk)
ak(kj)
ai(kk) ak(kk)
方程右边
bi(k 1)
bi(k)
bk(k)
ai(2k) ak(kk)
25

第四章 第一节 Gauss消元法

第四章 第一节 Gauss消元法

选主元的一种简单办法是，第 k 步消元时，在 A( k ) 的第 k列 (k ) 元素 aik (i k ) 中选取绝对值最大者作为主元，并将其对换到 k , k 位置上，然后再进行消元计算，这样选取的主元叫列主元。
另一种选主元的办法是选所谓全主元，也就是在第 k 步消 ( 元时，从 A( k ) 的右下方 n k 1 阶矩阵的所有元素 aijk ) (i, j k ) 中， 选取绝对值最大者作为主元，并将其对换到 (k , k ) 位置上，再做 消元计算。
主对角元以下的元素全化为0，得
1 1 a11 a12 a11 b11 n 2 2 2 a22 a2 n bn a 2 a 2 b 2 n2 nm n

A , b
左乘 ( A(2) , b(2) ), 即
M (2) ( A(2) , b(2) ) A(3) , b(3)
就是说，每消元一步相当于对方程组的增广矩阵左 乘以相应的矩阵 M ( k ) , 此处
1 0 0 0 0 0 1 0 0 0 0 1 mn , k 0 0 0 0 0 0 1 0 0 1
第一节 Gauss 消元法
一、引言 二、Gauss 消元法的基本思想
三、
主元消元法
四、 Gauss 消元法的矩阵形式 五、小结
一、引言
在自然科学和工程技术问题中，涉及到许多数值计算 问题，最终都要归结为解线性代数方程组 AX b 。其中 A Rnn , b Rn , A 是可逆的。本章和下一章分别讨论解方程 组的直接方法和迭代方法。所谓直接方法就是通过有限次 的精确运算能得到真解的一类数值方法。从本质上讲，直 接方法的原理是找到一个可逆矩阵 M ，使得 MA 是一个上 三角阵，这个过程称为“消元”过程。消元之后再进行 MAX “回代”，即求解 Mb 。实际计算过程中，不必明显 M MA 地计算出矩阵 ,而只须把 Mb和 计算出来。这类直接 Gauss Gauss 方法中最基本和最简单的就是 消元法，本章首先讨论 消元法和矩阵分解法，以及 Gauss 消元法在各种情况下的 变形，并分析其误差。

全选主元高斯消去法求解实系数线性方程组

全选主元高斯消去法求解实系数线性方程组

全选主元高斯消去法求解实系数线性方程组实验3 全选主元高斯消去法求解实系数线性方程组全选主元的基本思想和基本原理在教材的第40页，全选主元高斯消去法求解线性代数方程组的步骤在教材的第41页。

一、算法描述参数说明：n整型变量。

方程组的阶数。

a双精度实型二维数组，体积为n*n。

存放方程组的系数矩阵，返回时将被破坏。

b双精度实型一维数组，长度为n。

存放方程组右端的常数向量；返回方程组的解向量。

本函数返回整型标志值。

若返回的标志值为0，则表示原方程组的系数矩阵奇异，输出信息“fail”；若返回的标志值不为0，则表示正常返回。

#include”stdlib.h”#include “math.h”#include “stdio.h”int rgauss(n,a,b)int n;double a[],b[];{ int *js,l,k,I,j,is,p,q;double d,t;js=malloc(n*sizeof(int)); /*开辟用于记忆列交换信息的动态空间*/l=1; /*置非奇异标志*/for (k=0;k<=n-2;k++){d=0.0;for (i=k;i<=n-1;i++) /*全选主元*/for (j=k;j<=n-1;j++){t=fabs(a[i*n+j]);if (t>0) {d=t;js[k]=j;is=i;} /*记忆行、列交换信息*/ }if (d+1.0==1.0)l=0; /*置奇异标志*/else{if (js[k]!=k)for (i=0;i<=n-1;i++) /*列交换*/{p=i*n+k;q=i*n+js[k];t=a[p];a[p]=a[q];a[q]=t;}if (is!=k){ for (j=k;j<=n-1;j++) /*行交换*/{ p=k*n+j;q=is*n+j;t=a[p];a[p]=a[q];a[q]=t;}t=b[k];b[k]=b[is];b[is]=t;}}if (l==0) /*奇异返回*/, free(js); printf(…fail\n);return(0);}d=a[k*n+k];for (j=k+1;j<=n-1;j++) /*归一化*/{ p=k*n+j; a[p]=a[p]/d;}b[k]=b[k]/d;for (i=k+1;i<=n-1;i++) /*消元*/{ for (j=k+1;j<=n-1;j++){ p=i*n+j;a[p]=a[p]-a[i*n+k]*a[k*n+j];}b[i]=b[i]-a[i*n+k]*b[k];}}d=a[(n-1)*n+n-1];if (fabs(d)+1.0==1.0) /*奇异返回*/, free(js); prin tf(“fail\n”);return(0);}b[n-1]=b[n-1]/d; /*计算解向量的最后一个分量*/ for (i=n-2;i>=0; i--) /*回代*/{ t=0.0;for (j=i+1; j<=n-1; j++)t=t+a[i*n+j]*b[j];b[i]=b[i]-t;}js[n-1]=n-1;for (k=n-1;k>=0; k--) /*恢复解向量*/if (js[k]!=k){ t=b[k]; b[k]=b[js][k]}; b[js[k]]=t;} /*解向量行交换*/ free(js); /*释放动态空间*/return(l); /*返回正常标志*/}二、用高斯消去法求解下列方程组：0.2388x0+0.2471x1+0.2568x2+1.2671x3=1.84710.1968x0+0.2071x1+1.2168x2+0.2271x3=1.74710.1581x0+1.1675x1+0.1768x2+0.1871x3=1.64711.1161x0+0.1254x1+0.1397x2+0.1490x3=1.5471主函数程序如下：/*rgaus0.c*/#include “stdio.h”#include “rgauss.c”main(){ int I;static double a[4][4]={{0.2388,0.2471,0.2568,1.2671},{0.1968,0.2071,1.2168,0.2271},{0.1581,1.1675,0.1768,0.1871},{1.1161,0.1254,0.1397,0.1490}};static double b[4]={1.8471,1.7471,1.6471,1.5471}; if (rgauss(4,a,b)!=0)for (i=0; i<=3; i++)printf(“x(%d)=%e\n”,i,b*i+);}程序运行结果为x(0)=1.04058e+00x(1)=9.87051e-01x(2)=9.35040e-01x(3)=8.81282e-01。

高斯消元法（完整）

高斯消元法解线性方程组 在工程技术和工程管理中有许多问题经常可以归结为线性方程组类型的数学模型，这些模型中方程和未知量个数常常有多个，而且方程个数与未知量个数也不一定相同。

那么这样的线性方程组是否有解呢？如果有解，解是否唯一？若解不唯一，解的结构如何呢？这就是下面要讨论的问题。

一、线性方程组 设含有n 个未知量、有m 个方程式组成的方程组（3.1）a x a x a x b a x a x a x b a x a x a x b n n n n m m mn n m11112211211222221122+++=+++=+++=⎧⎨⎪⎪⎩⎪⎪ 其中系数，常数都是已知数，是未知量（也称为未知数）。

当右端常数项a ij b j x i , , …, 不全为0时，称方程组（3.1）为非齐次线性方程组；当== … =b 1b 2b m b 1b 2= 0时，即b m （3.2）a x a x a x a x a x a x a x a x a x n n n n m m mn n 111122121122221122000+++=+++=+++=⎧⎨⎪⎪⎩⎪⎪ 称为齐次线性方程组。

由n 个数, , …, 组成的一个有序数组（, , …, ），如果将它们k 1k 2k n k 1k 2k n 依次代入方程组（3.1）中的, , …, 后，（3.1）中的每个方程都变成恒等式，x 1x 2x n 则称这个有序数组（, , …, ）为方程组（3.1）的一个解。

显然由=0, k 1k 2k n x 1=0, …, =0组成的有序数组（0, 0, …, 0）是齐次线性方程组（3.2）的一个解，x 2x n 称之为齐次线性方程组（3.2）的零解，而当齐次线性方程组的未知量取值不全为零时，称之为非零解。

（利用矩阵来讨论线性方程组的解的情况或求线性方程组的解是很方便的。

因此，我们先给出线性方程组的矩阵表示形式。

）非齐次线性方程组（3.1）的矩阵表示形式为：AX = B其中A = ，X = ，B = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡mn m m n n a a a a a a a a a 212222111211⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡n x x x 21⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡n b b b 21称A 为方程组（3.1）的系数矩阵，X 为未知矩阵，B 为常数矩阵。

高斯选主元消去法.ppt

1 0 1/ 2 0 5/ 2
1 0 r3 2 r20
2/3 0
1 1/2
0 1
1 1/2
2 / 3 3 0 2 r2
0 1 0 0
3/2 1/2
0 3/2 1 1/2
2 1 0
5
r1 3 r2
1 5/ 3 2 0 0 1/ 3
1 0 1/ 2 0 5/ 2 2
1 0 2/ 3 1 0 1 2/ 3 3 0 1 3/ 2 0 3/ 2 1
0 1
r1
r3
2 1
4 2
5 3
0 1
1 1 5/ 3 2 0
1 0 0
0 0
1/3
m31
1 3
1
m32 2
2 r2 3 r1
1 r3 3 r1
0 0
1
2/3 1/3 5/3
101 110
2/3
2 / 3 1 0 1 2/ 3 1/ 3 1 1 0 1/ 3
yn yi
bn (bi
/ ann
n
aij y j ) / aii
j i 1
(i n 1,,2,1)
优点 该方法数值稳定( mi k 1). 缺点 工作量大. 改进方法 列主元消去法，且此时mi k 1.
4.2 列主元素消去法
设已完成第1步~第k-1步计算，得到与原方程组等价的方程组
)第k列与第jk列元素;
1,, n)
bi bi mik bk (i k 1,, n)
二、 回代求解
a11 a12 a1n y1 b1
经过上述过程，方程组约化为
a22
a2n
y2
b2
ann
yn

高斯消元法完整

高斯消元法(完整)高斯消元法解线性方程组在工程技术和工程管理中有许多问题经常可以归结为线性方程组类型的数学模型，这些模型中方程和未知量个数常常有多个，而且方程个数与未知量个数也不一定相同。

那么这样的线性方程组是否有解呢？如果有解，解是否唯一？若解不唯一，解的结构如何呢？这就是下面要讨论的问题。

一、线性方程组设含有n 个未知量、有m 个方程式组成的方程组a x a x a xb a x a x a x b a x a x a x b n n n n m m mn n m11112211211222221122+++=+++=+++=⎧⎨⎪⎪⎩⎪⎪ （3.1） 其中系数a ij ，常数b j 都是已知数，x i 是未知量（也称为未知数）。

当右端常数项b 1,b 2, …, b m 不全为0时，称方程组（3.1）为非齐次线性方程组；当b 1=b 2= … =b m = 0时，即a x a x a x a x a x a x a x a x a x n n n n m m mn n 111122121122221122000+++=+++=+++=⎧⎨⎪⎪⎩⎪⎪ （3.2） 称为齐次线性方程组。

由n 个数k 1, k 2, …, k n 组成的一个有序数组（k 1, k 2, …, k n ），如果将它们依次代入方程组（3.1）中的x 1, x 2, …, x n 后，（3.1）中的每个方程都变成恒等式，则称这个有序数组（k 1, k 2, …, k n ）为方程组（3.1）的一个解。

显然由x 1=0,x 2=0, …, x n =0组成的有序数组（0, 0, …, 0）是齐次线性方程组（3.2）的一个解，称之为齐次线性方程组（3.2）的零解，而当齐次线性方程组的未知量取值不全为零时，称之为非零解。

（利用矩阵来讨论线性方程组的解的情况或求线性方程组的解是很方便的。

因此，我们先给出线性方程组的矩阵表示形式。

数值分析-高斯消元法

数值分析-牛顿迭代法实验报告一、实验内容和要求用列主元高斯消去法解线性方程组Ax=b方程1：=;方程2：=;二、算法说明设Ax=b。

本算法用A的具有行交换的列祖元素消去法，校园结果冲掉A，乘数冲掉，计算解x冲掉常数项b，行列式存放在det中。

1.det←12.对于k=1,2,…,n-1(1)按列选主元=，(2)如果，=0，则计算停止(det(A)=0)(3)如果，=k，则转(4)(j=k,k+1,……,n)换行：，←-det(4)消元计算对于i=k+1,……,ni.←/ii.对于i=k+1,……,n←*iii.←-(5)det←*det3.如果，则计算停止(det(A)=0)4.回带求解(1)/(2)对于i=n-1,…,2,1←()/5.det←*det三、源程序#include <stdio.h>#include<conio.h>#include <math.h>#define max_dimension 20 //定义最大阶数为20 int n;static float a[max_dimension][max_dimension]; static float b[max_dimension];static float x[max_dimension];void main() {int I,j,d,row;float temp;float known_items;float l[max_dimension][max_dimension];printf("请输入方程的阶数:"); //输入矩阵阶数scanf("%d",&n);printf("\n");for (i=0; i<n; i++){printf("请输入第%d 的系数:",i+1); //矩阵输入for (j=0; j<n; j++){scanf("%f",&a[i][j]);}printf("\n");}printf("请输入常数项: "); //常数输入for (i=0; i<n; i++)scanf("%f",&b[i]);for (i=0; i<n; i++) //计算增广矩阵{for (j=0; j<n; j++);} for (d=0; d<n-1; d++){ row=d;for (i=d+1; i<n; i++) //查找最大元素所在行{if (fabs(a[i][d])>fabs(a[row][d]))row=i;}if (row!=d){for (j=d; j<n; j++){temp=a[row][j];a[row][j]=a[d][j];a[d][j]=temp;}temp=b[row];b[row]=b[d];b[d]=temp;}for (i=d+1; i<n; i++){l[i][d]=-a[i][d]/a[d][d];for (j=d; j<n; j++){a[i][j]=a[i][j]+a[d][j]*l[i][d];}b[i]=b[i]+b[d]*l[i][d];}}for (i=0; i<n; i++) //计算上三角矩阵{for (j=0; j<n; j++);}printf("\n");for (i=n-1; i>-1; i--){known_items=0;for (j=1; j<n-i; j++){known_items=known_items+a[i][i+j]*x[i+j]; }x[i]=(b[i]-known_items)/a[i][i];} printf("X的值分别为:\n");for (i=0; i<n; i++)printf("%.5f ",x[i]);//输出x的值printf("\n");getch();}四、实验结果方程1：=1592.22119=-631.76123=-493.50037方程2：=119.52600=-47.14207=-36.83984五、说明与分析在高斯消去法运算的过程中，如果出现(A(i,i))的绝对值等于零或过小的情况，则会导致矩阵元素数量级严重增长和舍入误差的扩散，使得最后的计算结果不可靠，所以需先对矩阵进行变换在计算。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例 1、 用回代法求解线性方程 =2 ⎧ 2 x1 ⎪ =2 ⎨ x1 + x 2 ⎪3x + 2 x + 4 x = 9 2 3 ⎩ 1
解: x1 = 2 / 2 = 1 x2 = ( 2 − 1) / 1 = 1 x3 = (9 − 3 × 1 − 2 × 1) / 4 = 1 所以，解为 （x1 , x2 , x3 ) = (1 ,1 ,1)
组
求解一个三角形方程组 需n个除法与∑ i − n( n − 1) ≈ n 2 2 2
次加法与乘法。
2.Gauss消元法
(一) 高斯消去法的求解过程,可大致分为两个阶段:首先,把 原方程组化为上三角形方程组,称之为“消去(消元)”过程;然后, 用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并 称之为“回代”过程.,下面分别写出“消去(消元)”和“回代” 两个过 程的计算步骤.
做(消去第i
mik×第k个方程 + 第i个方程
类似可得第k步消元后的方程组为
i= k+1,k+2,…n
(0 ( 0 ⎧ a 11 ) x 1 + a 120 ) x 2 + L L L L L L L L + a 1(n ) x n = b1( 0 ) (1 ) (1 ) (1 ) ⎪ a 22 x 2 + L L L L L L L L + a 2 n x n = b 2 ⎪ LLLLLLLLLL ⎪ ⎨ ( ) ( ) ) a k k 1 k +1 x k +1 + L + a k k 1 n x n = b k( k 1 + + + ⎪ ⎪ LLLLLLLLLLM ( (k ( ⎪ a n kk)+1 x k +1 + L + a nn ) x n = b n k ) ⎩ (k ) (k−1) (k−1) (k ) (k−1) (k−1) aij = aij + mikakj , bi = bi + mikbk
及问题的引出暂介绍如下:
如果未知量的个数为 n ,而且关于这些未知量 x1,x2, … ,xn 的幂次都是一次的(线性的),那末, n 个方程
a11x1+a12x2+ … +a1nxn=b1 ┆ ┆ ┆ (1) an1x1+an2x2+ … +annxn=bn 构成一个含 n 个未知量的线性方程组,称为 n 阶线性方程 组 其中,系数a11,…,a1n,a21, …,a2n, …,an1, …,ann 是给定的 常数;b1, …,bn 也是给定的常数,通常称为常数项,或称为 方程组的右端. 方程组(1)也常用矩阵的形式表示,写为 Ax=b
i, j = k +1, k + 2,...,n
继续下去到第n-1步消元,可将线性方程组化为如下上三角方 程组: ⎫
a11 x1 + a12 x 2 + L + a1n x n = b1 ⎪ (1) (1) (1) a 22 x 2 + L + a 2 n x n = b2 ⎪ ⎬ L ⎪ ( n −1) ( n −1) ⎪ a nn x n = bn ⎭
1 . 2 For i = k + 1, k + 2 , L , n 1 . 2 . 1 − a ik / a kk ⇒ a ik 1 .2 .2 1 .2 .3 2 3 For 3 .1 4 End a ij + a ik a kj ⇒ a ij ( j = k + 1, k + 2 , L , n ) b i + a ik b k ⇒ b i k = n − 1, n − 2 , L ,1 (bk −
消去(消元)过程:
第一步: 设a11≠0,取 m
i1
a i1 = − a 11
做(消去第i个方程组的x1) i=2,3,…n
mi1×第一个方程+第i个方程
则第i个方程变为
( a i(11 ) x 1 + a i(21 ) x 2 + L + a in1 ) x n = b i( 1 )
aij = aij
N=(n2-1)n!+n
次乘除法运算,这个计算量是大得惊人的.例如,当n=10(即求解一 个含10个未知量的方程组),乘除法的运算次数共为32659210次;
当n=40,乘除法运算次数可达3.18 ×1049次.对于上百个未知量的 方程组,次数运算量就更大了.因此克莱姆规则在理论上尽管是完 善的,但在实际计算中却没有什么实用价值.本文我们将重点讨论 求解线性方程组的一种有效的数值方法.
(二)求解线性方程组的消元法
消(元)去法是求解线性方程组
Ax=b
(3)
和满秩矩阵的逆阵A-1的一种直接方法.尽管它比较古老,但它具 有演算步骤,推算公式都系统化的特点(对其中选主元消去法,还 可以证明是稳定的).因此,它至今仍然是求解方程组的一种有效 的方法.
消去法可以引出几种计算方法,下面按三角形方程 组和一般线性方程组的顺序来讨论.
为求解上面的上三角方 程组，从最后一 个方程开始，先解出 xn = bn / a nn , 然后按方程 从后向前的顺序，用已 求出的 xk 值，从方程 中依次解出 x n −1 , x n − 2 ,...., x1。这样就完成了上三 角方程组的求解过程这 个过程的计算公式为： x n = bn / a nn xi = (bi −
其中,A是由系数按次序排列构成的一个n阶矩阵, 称为方程组的系数矩阵,x和b都是n维向量,称为方程 组的解向量和右端向量，即
⎡a11 a12 ⎢a a22 21 A = ⎢ L ⎢ ⎢ ⎣an1 an 2
L a1n ⎤ L a2 n ⎥ ⎥ L ⎥ ⎥ L ann ⎦
⎡ b1 ⎤ ⎢b ⎥ b = ⎢ 2⎥ ⎢M⎥ ⎢ ⎥ ⎣bn ⎦
⎡ x1 ⎤ ⎢x ⎥ x = ⎢ 2⎥ ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦
使方程组(1)中每一个方程都成立的一组数x1*,x2*,…,xn* 称 为式(1)的解,把它记为向量的形式,称为解向量.
我们总是希望方程组有解,且有唯一解.由线性代数的克莱姆 (cramer)规则可知,如果方程组(1)的系数矩阵A的行列式(一般记 为D=|A|)不等于零,那末,这个方程组有唯一解,而且它们可以表 示为 xi=Di/D (i=1,2,…,n)
(k )
其中 a ij 和 bi 的上标 k 表示第 k 次消元后的系数， 计算公式为 : 对 k = 1，,3, L , n − 1 2 ⎧ m ik = − a ik ( k −1) / a kk ( k −1) ⎪ (k ) ( k −1) ( k −1) + m ik a kj ⎨ a ij = a ij ⎪b ( k ) = b ( k −1) + m b ( k −1) i ik k ⎩ i i , j = k + 1, k + 2 ,..., n
高斯消元法与选主元
高斯消元法是一种古老的直接 法,由它改进得到的选主元消元法,是 目前计算机上常用于求解低阶稠密 矩阵方程组的有效方法,其特点就是 通过消元将一般线性方程组的求解 问题转化为三角方程组的求解问题
关键词：
高斯消去法， 主元消去法
一 问题的描述
(一)引言 为便于以下讨论,把涉及到的有关名词
(1)
(0)
+ mi1a1 j , bi = bi
(0) (1)
(0)
+ mi1b1(0) , aij
( 0)
= aij , bi
( 0)
= bi
i,j=2,3,…,n 因为
a i1
(1)
ai1 = ai1 + mi1a11 = ai1 − • a11 = 0 a11
可得第一步消元后的方程组为
( ( 0 ⎧ a 110 ) x 1 + a 120 ) x 2 + L + a 1(n ) x n = b1( 0 ) ⎪ (1 ( ( a 22) x 2 + L + a 21n) x n = b 21 ) ⎪ ⎨ LLLLLLLLLM ⎪ ( (1 ( ⎪ a n12) x 2 + L + a nn) x n = b n1 ) ⎩
b n / a nn ⇒ x n
∑
n
j =1
a kj x j ) / a kk ⇒ x k
为具体认识这种方法， 例2
下面给出例题。
用 Gauss 消元发求解方程组 ⎧ x1 + 2 x 2 + 3 x 3 = 6 ⎪ ⎨ 2 x1 + 3 x 2 + 4 x 3 = 9 ⎪ x + 3x + 2 x = 6 2 3 ⎩ 1
i=3,4,…n
0 + LL + a 1(n ) x n = b1( 0 ) ( ( + L L L + a 21n) x n = b 21 ) (2) (2) (2) a 33 x 3 + L + a 3 n x n = b3
LLLLLLLLLM ( (2 ( a n 2 ) x 3 + L + a nn ) x n = b n 2 ) 3
步骤： 1. bn / a 2 . For
nn
k = i +1
∑a
n
ik
x k ) / aii
xn
⇒
i = n − 1 , n − 2 , L ,1 (bi −
k = i+1
∑
n
a
ik
xk ) / a
ii
⇒
xi
下三角方程组的一般形 式为： a11 x1 = b1 a 21 x1 + a 22 x 2 = b2 LLLLLLL a n1 x1 + a n 2 x 2 + L + a nn x n = bn 其中 aii ≠ 0, i = 1, 2, L , n 下三角形方程组可以参 照上三角形方程组的解 法来求解， 下三角形方程组的求解 顺序是从第一个方程开 始，按从上到下 的顺序，依次解出： x1 , x 2 , L , x n , 其计算公式为： ⎧ x1 = b1 / a11 ⎪ i −1 ⎨ x = (b − ∑1 aik xk ) / aii (i = 2,3, L , n ) i ⎪ i k= ⎩ 如上解三角形方程组的 方法称为 回代法 .