第4章 解线性方程组的迭代解法

1计算方法第四章解线性方程组的迭代解法医学技术学院医学信息工程教研室赖小波博士，副教授，硕士研究生导师

在第2章中我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。第4章解线性方程组的迭代法上一章我们介绍了解线性方程组AX=b的直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解。最基本的直接法是Gauss消去法，其余的的方法全都受到Gauss消去法的启发。计算代价高。本章介绍解线性方程组的另一种方法：迭代法。它基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题。

简单实用,诱人。第4章解线性方程组的迭代法问题引入用迭代法求解线性方程组

解构造方程组的等价方程组据此建立迭代公式取计算得

迭代解离精确解越来越远迭代不收敛

取计算得

迭代解离精确解越来越近，迭代收敛

构造方程组等价方程组据此建立迭代公式考虑解方程组准确解建立与上式等价的形式据此建立迭代格式迭代结果如下表迭代次数

x1

x2

x3000010.720.830.8420.9711.071.1531.05711.15711.248241.085351.185341.2828251.0950981.1950991.29413861.0983381.1983371.29803971.0994421.194421.29933581.0998111.1998111.29977791.0999361.1999361.299924101.0999761.1999791.199975111.0999931.1999931.299991121.0999981.1999981.299997131.0999991.1999991.2999999141.11.21.3151.11.21.3迭代次数 x1

x2

x34.2迭代法的基本思想迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。与解f(x)=0

的非线性方程相似，将方程组等价改写成形式，从而建立迭代格式，从出发，生成迭代序列设非奇异，，则线性方程组有惟一解，经过变换构造出一个等价同解方程组将上式改写成迭代式选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法迭代法是一种逐次逼近的方法,与直接法比较,具有:程序简单,存储量小的优点。特别适用于求解系数矩阵为大型稀疏矩阵的方程组。

如果存在极限则称迭代法是收敛的，否则就是发散的。对于给定的方程组可以构造各种迭代公式。并非全部收敛收敛时，在迭代公式中当时则故是方程组的解4.3雅可比（Jacobi）迭代法4.3.1雅可比迭代法算法构造例4.2用雅可比迭代法求解方程组解：从方程组的三个方程中分离出和建立迭代公式

取初始向量进行迭代,可以逐步得出一个近似解的序列：（k=1,2,…）直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。考察一般的方程组，将n元线性方程组

写成若,分离出变量据此建立迭代公式上式称为解方程组的Jacobi迭代公式。4.3.2雅可比迭代法的矩阵表示设方程组的系数矩阵A非奇异，且主对角元素，则可将A分裂成

记作A=L+D+U则等价于即因为

，则这样便得到一个迭代公式令则有（k=0,1,2…）称为雅可比迭代公式,B称为雅可比迭代矩阵其中在例4.2中,由迭代公式写出雅可比迭代矩阵为雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即

(k=0,1,2,…)4.4高斯-塞德尔（Gauss-Seidel）迭代法4.4.1高斯-塞德尔迭代法的基本思想

在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求时用新分量代替旧分量,就得到高斯-赛德尔迭代法。其迭代法格式为：

(i=1,2,…,n

k=0,1,2,…)例4.3用GaussSeidel迭代格式解方程组

精确要求为ε=0.005

解GaussSeidel迭代格式为取初始迭代向量,迭代结果为：x*≈例4.4用Jacobi和Gauss-Seidel迭代法求解方程组解：Jacobi迭代格式G-S迭代格式计算结果取初值Jacobi迭代法要求精度迭代次数

0.001

9(1.00025071.00006941.0002507)

0.0001

10(0.99995411.00012530.9999541)0.00001

14(0.99999811.00000200.9999981)方程组的近似解Gauss-Seidel迭代法

要求精度迭代次数

0.001

5(0.99979160.99984791.0000664)

0.0001

7(0.99999290.99999491.0000022)0.00001

8(1.00000131.00000090.9999996)方程组的近似解取初值计算结果4.4.2Gauss—Seidel迭代法的矩阵表示将A分裂成A=L+D+U，则等价于(L+D+U)x

=b于是,则高斯—塞德尔迭代过程因为,所以

则高斯-塞德尔迭代形式为：

故

令

4.4.3高斯—塞德尔迭代算法实现高斯-塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同，只是一旦求出变元的某个新值后,就改用新值替代老值进行这一步剩下的计算。

高斯-塞德尔迭代算法的程序实现(见附录AA-7用高斯—塞德尔迭代法求解线性方程组）4.6雅可比（Jacobi）算法构造设n阶方程组的系数矩阵A非奇异,主对角元素非零，从方程组的第i

个方程中解出，得到等价的方程组

由上式构造迭代公式

初始值任取。其算法实现步骤为：雅可比迭代算法实现步骤（1）输入方程组的阶数n，系数矩阵A，右端常数矩阵b，最大迭代次数MAX_N以及容许误差；（2）k=0；（3）对，计算：（4），成立转（6），否则继续；（5）成立，，转（3）；否则输出失败信息，转（7）（6）输出；（7）结束。雅可比迭代法的流程图描述

例4.5用雅可比迭代法求解线性方程组，式中#include<stdio.h>#include<math.h>#defineN3/*N为方程组系数矩阵的阶数*/#defineMAX_N100/*最大迭代次数*/#defineepsilon1e-6/*容许误差*/intyacobi(floata[N][N],floatb[N],floatx[N]){floatd,s,max,y[N];inti,j,k,flag;k=0;for(i=0;i<N;i++)x[i]=0.0;while(1){max=0.0;k++;for(i=0;i<N;i++){s=0.0; for(j=0;j<N;j++) if(j!=i)s=s+a[i][j]*x[j];y[i]=(b[i]-s)/a[i][i]; d=fabs(y[i]-x[i]);if(max<d)max=d;/*将循环过程中最大的d值赋值给max*/}for(i=0;i<N;i++)x[i]=y[i];if(max<eps)/*当max<eps时结束迭代*/{flag=1;break;}if(k>=MAX_N)/*当k>=MAX_N时反馈失败信息，结束迭代*/{flag=0;break;}}return(flag);}

voidzg_matric(floata[N][N],floatb[N])/*输出增广矩阵*/{inti,j;for(i=0;i<N;i++){for(j=0;j<N;j++) printf("%10f",a[i][j]);printf("%12f",b[i]);printf("\n");}printf("\n");}

main(){floata[N][N]={{10,1,-2},{-2,10,-1},{1,-2,5}};floatb[N]={9,7,4};floatx[N];inti,k;zg_matric(a,b);k=yacobi(a,b,x);if(k==1)for(i=0;i<N;i++)/*输出方程组的解*/printf("x%d=%11.7f\n",i+1,x[i]);elseprintf("TheMethodisdisconvergent!\n");/*输出失败信息*/}程序运行结果：

10.0000001.000000-2.0000009.000000-2.00000010.000000-1.0000007.0000001.000000-2.0000005.0000004.000000x1=1.0000002x2=0.9999999x3=0.9999996

4.7迭代法的收敛性我们知道,对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。在什么条件下迭代序列收敛？先引入如下定理

对于方程组

经过等价变换构造出的等价方程组定理4.1对给定方阵G,若,则为非奇异矩阵,且证:用反证法,若为奇异矩阵,则存在非零向量x,使,即有由相容性条件得又由于即有由于,两端消去,有,与已知条件矛盾,假设不成立,命题得证。将G分别取成G和-G，再取范数定理4.2迭代公式收敛的充分必要条件是迭代矩阵G的谱半径证:充分性设迭代公式收敛,当k→∞时,则在迭代公式两端同时取极限得记,则收敛于0(零向量),且有于是

由于可以是任意向量,故收敛于0当且仅当收敛于零矩阵，即当时于是

所以必有

由此定理可知，不论是雅可比迭代法、高斯—塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径。

事实上,在例4.1中,迭代矩阵G=其特征多项式为,特征值为-2，-3，,所以迭代发散

必要性:设,则必存在正数ε,使则存在某种范数,使,则所以则收敛于即故收敛于0定理4.3(迭代法收敛的充分条件)若迭代矩阵G的一种范数,则迭代公式收敛,且有误差估计式,且有误差估计式及证:矩阵的谱半径不超过矩阵的任一种范数,已知,因此,根据定理4.2可知迭代公式收敛又因为,则det(I-G)≠0,I-G为非奇异矩阵,故x＝Gx＋d有惟一解,即与迭代过程相比较,有∴

两边取范数由迭代格式，有

两边取范数,代入上式证毕

由定理知，当时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代（ε为给定的精度要求）作为控制迭代结束的条件即复习：1.雅可比（Jacobi）算法设n阶方程组的系数矩阵A非奇异,主对角元素非零，从方程组的第i

个方程中解出，得到等价的方程组

由上式构造迭代公式

初始值任取。2.高斯-塞德尔（Gauss-Seidel）迭代法在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求时用新分量代替旧分量,就得到高斯-赛德尔迭代法。其迭代法格式为：

(i=1,2,…,n

k=0,1,2,…)例4.8已知线性方程组考察用Jacobi迭代和G-S迭代求解时的收敛性故Jacobi迭代收敛

解:⑴雅可比迭代矩阵⑵

将系数矩阵分解

则高斯-塞德尔迭代矩阵

故高斯—塞德尔迭代收敛。

则高斯-塞德尔迭代矩阵

定理4.4设n阶方阵为对角占优阵,则非奇异证:因A为对角占优阵,其主对角元素的绝对值大于同行其它元素绝对值之和,且主对角元素全不为0,故对角阵为非奇异。作矩阵利用对角占优知

由定理4.1知非奇异,从而A非奇异,证毕系数矩阵为对角占优阵的线性方程组称作对角占优方程组。定理4.5对角占优线性方程组的雅可比迭代公式和高斯-赛德尔迭代公式均收敛证明:略例4.7设求解线性方程组的雅可比迭代

求证：当<1时,相应的高斯-塞德尔迭代收敛

又<1,故有则证:由于B是雅可比迭代的迭代矩阵,故有所以Ax=b的系数距阵为对角占优距阵,故G-S迭代收敛例4.8

设,证明,求解方程组的Jacobi迭代与G-S迭代同时收敛或发散

证:雅可比迭代矩阵其谱半径

例4.8

设,证明,求解方程组的Jacobi迭代与G-S迭代同时收敛或发散

证:G-S迭代矩阵

其谱半径

显然,和同时小于、等于或大于1,因而Jacobi迭代法与G-S迭代法具有相同的收敛性

例4.9

考察用雅可比迭代法和高斯-塞德尔迭代法解线性方程组Ax=b的收敛性，其中解：先计算迭代矩阵求特征值雅可比矩阵

(B)=0<1∴用雅可比迭代法求解时，迭代过程收敛1=0,2=2,3=2(G1)=2>1

∴用高斯-塞德尔迭代法求解时，迭代过程发散高斯-塞德尔迭代矩阵求特征值∴Ax=b的系数矩阵按行严格对角占优,故高斯-塞德尔迭代收敛例4.10设有迭代格式

X(k+1)=BX(k)+g(k=0,1,2……）其中B=I-A,如果A和B的特征值全为正数，试证：该迭代格式收敛。分析:根据A，B和单位矩阵I之间的特征值的关系导出()<1,从而说明迭代格式收敛。证:因为B=I-A,故(B)=(I)-(A)=1-(A)

(A)+(B)=1由于已知(A)和(B)全为正数，故0<(B)<1,从而(B)<1所以该迭代格式收敛。例4.11设方程组写出解方程组的Jacobi迭代公式和迭代矩阵并讨论迭代收敛的条件。写出解方程组的Gauss-Seidel迭代矩阵,并讨论迭代收敛的条件。解①Jacobi迭代公式和Jacobi矩阵分别为当时,对初值x(0)均收敛例4.12设方程组写出解方程组的Gauss-Seidel迭代矩阵，并讨论迭代收敛的条件。解②Gauss-Seidel矩阵为

时,对任意初值均收敛。当求解AX=b,当取何值时迭代收敛？

例4.13给定线性方程组AX=b

用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1,…）解:所给迭代公式可化为迭代公式的迭代矩阵为即

2-(2-5)+1-5+4

2=0

2-(2-5)+(1-)(1-4)=0

[-(1-)][-(1-4)]=0

1=1-2=1-4(B)=max{|1-|,|1-4|}<1取0<<1/2迭代收敛JacobiG-S判断收敛迭代求解判断收敛迭代求解总结本章小结

本章介绍了解线性方程组迭代法的一些基本理论和具体方法。迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法解方程组时，其迭代矩阵B和迭代向量f在计算过程中始终不变,迭代法具有循环的计算公式,方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性,适宜解大型稀疏系数矩阵的方程组。

迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与收敛速度，收敛性与迭代初值的选取无关，这是比一般非线性方程求根的优越之处。在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于1或对角占优来判断收敛性。有时也可边计算边观察其收敛性。如何加快迭代过程的收敛速度是一个很重要的问题，实用中更多的采用SOR法，选择适当的松驰因子ω有赖于实际经验。我们应针对不同的实际问题，采用适当的数值算法。例4.15设求解线性方程组Ax=b的简单迭代法