第三章 线性方程组的数值方法
在自然科学和工程技术中很多问题的解决常常归结为求解线性代数方程组.
?a11x1?a12x2??a1nxn??a21x1?a22x2??a2nxn???ax?ax??ax?n11n22nnn?b1?b2??bn
当它的系数行列式不为零时，由克莱姆法则可以给出方程组的唯一解，但是这一理论上完 善
的结果，在实际计算中可以说没有什么用处。因此如何建立在计算机上可以实现的有效而实用的解法，具有极其重要的意义。这些方法大致可分为两类：一类是直接法，就是经过有限步算术运算,可求得方程组精确解的方法(如果每步计算都是精确进行的话)；另一类是迭代法，就是用某种极限过程去逐步逼近其精确解的方法.
本章将阐述这两类算法中最基本的高斯消元法及其变形、矩阵分解法、雅可比迭代法、高斯 -塞德尔迭代法等.
第一节 高斯消元法
一 回代过程
? 设系数矩阵为n阶上三角矩阵的线性方程组
?a11x1?a12x2??a1nxn?a22x2??a2nxn????annxn?如果a11,a22,...ann都
?b1?b2??bn (1)
(1)自下而上可以逐次求出xn,xn?1,...x1为
?bnxn??ann?n?bk??akjxj?j?k?1?,k?n?1,n?2,...1xk?akk?按上述公式求方程组(1) 解的过程称为回代过程.
?2?
11n?n?1?n?n?1?不难看出，解方程组(1)共需2次加法和2次乘法.这恰好是用一个n阶三
2角方阵乘n维向量所需的运算次数。当n较大时,n??n，同时加法运算速度远快于乘法的运
12n2算速度，所以，可用次乘法来近似表示回代过程的运算量.
?二 消元过程?
设有线性方程组
?a11x1?a12x2??a1nxn?b1??a21x1?a22x2??a2nxn?b2?3?????ax?ax??ax?b?n11n22nnnn ?0??0??aij,ain?1?bi?i?1,2,...n;j?1,2...n?, 则原方程组改写成
为了符号统一，记aij?0??0?0?x1?a12x2??a1?nxn?a11??0??0??0?)?a21x1?a22x2??a2nxn???a?0?x?a?0?x??a?0?x?111n22nnn0??a1?n?1?0??a2n?1??0??ann?1?3?'如果a11量.令
?0?
?0，那么就可以保留其中第一个方程并利用它分别与其余方程消去第一个未知
ai1?,li1?0?a11则以
?0?i?2,3,..,n
?4?
?li1乘第一个方程加到第
i个方程中，就把方程组
?0??a1n?1?3?'化为
?0??0?0?x1?a12x2??a1?nxn?a11??1??1?a22x2??a2x?nn???1??1??ax??ax?n22nnn?a?21n??1?1??a?nn?1?5?
其中
i?2,3,...n,j?2,3,...n?1 ?6?
?0??0?aa1111由方程组(3′)化为(5)的过程中，元素起着特殊的作用，特把元素称为主元素.
?1??1?如果方程组(5)中a22?0, 则以a22为主元素，并利用类似的方法消去第3,4,...n个方程
?1??0??0?aij?aij?li1a1j,中的第二个未知量，即令
ai2i?3,4,..,nli2??1?,a22 ?7?
则以?li2乘以第二个方程加到第i个方程中,于是得到新的方程组
?0??0??0??0??0?x1?a12x2?a13?a11x3???a1nxn?a1n?1??1??1??1??1??ax???ax?axa2222n?12332nn???2??2??2?a33x3?....?a3nxn?a3n?1?????2??2??2??ax??ax?ann?1n33nnn??1??8?
其中
?2??1??1?aij?aij?li2a2j,i?3,...n,j?3,...n?1 ?9?
重复上述过程
n?1步后，我们得到原方程组等价的系数矩阵为三角形方阵的方程组
?0??0??0??0??0?x1?a12x2?a13?a11x3???a1nxn?a1n?1??1??1??1??1??ax???ax?axa2222n?12332nn???2??2??2?a33x3?....?a3nxn?a3n?1?????n?1??n?1??ax?ann?1nnn??10?
其中
把方程组(3)逐步化为方程组(10)的过程称为消元过程.最后，由回代过程可求得原方程组的
解为
?n?1??ann?1?xn??n?1?ann?n??k?1??k?1?axjkn?1??akj?j?k?1,?xk??k?1?akk?aiklik??k?1?akk ?11?
?k??k?1??aij?lika?kjk?1??aij??k?1,2,...n?1?i?k?1,k?2,...n;j?k?1,k?2,...n?1? ?12?
?k?1?k?n?1.n?2,...2,1这种通过消元、再回代的求解方法称为高斯(Gauss)消元法(其特点是始终消去主对角线下方
的元素).
注意到，上标k仅仅用来识别一次消元前后系数矩阵的变化，而aij再使用，所以在计算机存贮中只要用aij?k?1? ?13?
?k?1??k?变为aij后,aij?k?不
即可；另一方面，主元素所在列中主元素下
面的各元素在消元过程中必然是零，而且在后面将要列出的回代过程中也不用它们，所以没有必要通过计算得到它们，从而在消元过程中
例1 用高斯消元法求解方程组
冲掉aij?k?j就可从k?1开始，这样做还可以节约计算时间.
?2x1?8x2?2x3?14??x1?6x2?x3?13?2x?x?2x?53?12
解 用第一个方程消去后两个方程中的x1，得 ?2x1?8x2?2x3?14?2x2?2x3?6???9x2??9 ?再用第二个方程消去第三个方程中的x2，得
?2x1?8x2?2x3?14?2x2?2x3?6???9x3?18 ?最后，经过回代求得方程组的解为
三 高斯消元法的条件与运算量
18??2?96?2x3x2??1214?8x2?2x3x1??52 x3??k?1?从消元过程可以看出，对于n阶线性方程组，只要各步主元素不为零，即akk求得原方程组的解.因此,有下面结论.
?0，经过
n?1步消元，就可以得到一个等价的系数矩阵为上三角形阵的方程组，然后再利用回代过程可
?k?1?a定理1 如果在消元过程中A的主元素不为零，即kk?0(k=1,2,…,n),则可通过高斯
消元法求出Ax?b的解.
?k?1?aA矩阵在什么条件下才能保证kk?0,下面的定理给出了这一条件.
?k?1?aA引理 在高斯消元过程中系数矩阵的主元素不为零，即kk?0(k=1,2,…，n)的充要
条件是矩阵A的各阶顺序主子式不为零，即
D1?a11?0a11...a1kDk?.........?0,k?2,3...nak1...akk证明 首先利用归纳法证明引理的充分性，显然 ，当n?1时，引理的充分性是成立的，现假设引理对n?1时也成立，求证引理对n也成立，由归纳法假设有
?k?1?akk?0, k?1,2...n?1
于是可用高斯消元法将
A化为
(0)a12?(1)a22?且
(0)?a11??A??????a1(n0?)1(1)a2n?1??(n?2)an?1n?1a1(n0)??(1)a2n????(n?2)an?1,n?(n?1)?ann?
?0??0?D1?a11?a11
a11?D20?0?a12?0??1??0??1??a11a22a22
(0)(0)a12?a1(n0?)1a1(n0)??a11??(1)(1)(1)a22?a2n?1a2n???0??1??n?1??...?????a11aaDn??22nn????(n?1)?a?nn?
?n?1?由假设Dk?0,k?1,2,...n,所以有ann?0.
反过来,由上式可知必要性是显然的.
定理2 如果n阶矩阵A的所有顺序主子式均不为零，即Dk高斯消元法求出的解.
下面考虑求解(3)的高斯消元法的运算量.消元过程需要除法
?0,k?1,2,...n,则可通过
?n?1???n?2??...?2?1?1n?n?1?2
次，而需要的乘法和加法的次数都是
1n??n?1???n?1???n?2??...?2?1?n?n2?1?3
加上回代过程的运算次数，共需乘、除法的次数为
1111n?n?1??n?n2?1??n?n?1??n?n2?3n?1?2323
加、减法的次数为
111n?n2?1??n?n?1??n?2n2?3n?5?326 32当n较大时,n??n,消元过程的运算量远大于回代过程，从而，高斯消元法中乘除法的次数
13n与加减法的次数近似为3.
第二节 第二节 高斯主元素消元法
一 问题的提出
由高斯消元法可知，在消元过程中如果出现akk舍入误差的扩散，最后也使得计算结果很不可靠.
?k?1??0的情况，这时消元法将无法进行；另
?k?1?a一方面，即使主元素kk?0，但很小时，用其作除数，会导致其它元素数量级的严重增长和
例1 例1 解方程组
?0.0003x1?3.0000x2?2.0001??1.0000x1?1.0000x2?1.0000
12x1?,x2?33) (它的精确解为