《应用数值分析》课件数值分析5.5线性方程组的数值解法

第5章线性方程组的数值解法对线性方程组要求寻找更经济、适用的数值解法.其中A为非奇异矩阵,当A为低阶稠密矩阵时,选主元消去法(直接法)是有效的.但对于大型稀疏矩阵方程组(A的阶数n很大

104，但零元素较多),方程组的阶数很高,则运算量将会很大并且大量占用计算机资源.利用迭代法求解是合适的.§5.5

雅可比迭代法和高斯-赛德尔迭代法

将介绍迭代法的一些基本理论及雅可比迭代法，高斯-赛德尔迭代法，超松弛迭代法，而超松弛迭代法应用很广泛。

则(1)式和(2)式同解,称(1)与(2)等价.

例1求解方程组记为Ax=b，其中此方程组的精确解是x*=(3,2,1)T.现将(1.2)改写为迭代法的基本概念

下面举简例，以便了解迭代法的思想.或写为x=B0x+f，其中取x(0)=(0,0,0)T.将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解，但一般不满足)，得到新的值x(1)=(x1(1),x2(1),x3(1))T

=(3.5,3,3)T

，再将x(1)分量代入(1.3)式右边得到x(2)，反复利用这个计算程序，得到一向量序列简写为x(k+1)=B0x(k)+f，其中k表示迭代次数(k=0,1,2,

).

迭代到第10次有一般的计算公式(迭代公式)

从此例看出，由迭代法产生的向量序列x(k)逐步逼近方程组的精确解是x*=(3,2,1)T.即有

对于任何一个方程组x=Bx+f(由Ax=b变形得到的等价方程组)，由迭代法产生的向量序列x(k)是否一定逐步逼近方程组的解x*呢？回答是不一定.请考虑用迭代法解下述方程组但x(k)并不是所有的都收敛到解x*！x*=(-3,-4)T

这种方式就称为迭代法.以上过程称为迭代过程.迭代法产生一个序列则称迭代法收敛,否则称为发散.(3)

如果对于任意其极限存在,即

对线性方程组(2),采用以下迭代步骤:

迭代法的基本思想是通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解，因此，要解决的基本问题有：1.如何构造迭代格式

2.迭代序列是否收敛设线性方程组(1)的一般形式为Jacobi迭代G-S迭代SOR迭代法(4)5.5.1

Jacobi迭代法由(4)建立Jacobi迭代公式为(5)将(5)式转化为矩阵形式矩阵形式为称(5)、(6)式为解线性方程组(1)的Jacobi迭代法(J法)(6)(5)用Jacobi迭代法求解方程组,误差不超过1e-4解:例2依此类推,得方程组满足精度的解为x12迭代次数为12次x4=3.02411.94780.9205d=0.1573x5=3.00031.98401.0010d=0.0914x6=2.99382.00001.0038d=0.0175x7=2.99902.00261.0031d=0.0059x8=3.00022.00060.9998d=0.0040x9=3.00031.99990.9997d=7.3612e-004x10=3.00001.99990.9999d=2.8918e-004x11=3.00002.00001.0000d=1.7669e-004x12=3.00002.00001.0000d=3.0647e-0055.5.2Gauss-Seidel迭代法分析Jacobi迭代法(5)的迭代过程称(7)、(8)式为解线性方程组(1)的Gauss-Seidel迭代法(G-S法)

雅可比迭代法不使用变量的最新信息计算xi(k+1)，而由高斯-塞德尔迭代公式可知，计算x(k+1)的第i个分量xi(k+1)时，利用了已经计算出的最新分量xj(k+1)(j=1,2,

,i-1).

可看作雅可比迭代法的一种改进.高斯—塞德尔迭代公式每迭代一次只需计算一次矩阵与向量的乘法.G-S迭代法有一个明显的优点是：在计算时，只需一组工作单元，以便存放近似解.而J迭代法需要两组工作单元，分别存放

和

.例3解:用Gauss-Seidel迭代法求解方程组,误差不超过1e-4x1=2.50002.09091.2273d=3.4825x2=2.97732.02891.0041d=0.5305x3=3.00981.99680.9959d=0.0465x4=2.99981.99971.0002d=0.0112x5=2.99982.00011.0001d=3.9735e-004x6=3.00002.00001.0000d=1.9555e-004x7=3.00002.00001.0000d=1.1576e-005通过迭代,至第7步得到满足精度的解x7Jacobi迭代法和Gauss-Seidel迭代法均为简单迭代法后面我们会看到，甚至有这样的方程组，Jacobi迭代收敛，而Gauss-Seidel迭代却是发散的.不能说G-S法比J法更好.从例2和例3看出,Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要快（达到同样的精度所需迭代次数较少).但这个结论，在一定条件下才是对的.

练习

用Jacobi和Gauss-Seidel迭代法解方程组

Jacobi迭代

Gauss-Seidel迭代解：

kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T计算结果如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3

Jacobi迭代Gauss-Seidel迭代5.5.3迭代法的收敛性设解线性方程组的迭代格式(10)(11)将(10)与(11)相减,得因此迭代法收敛的充要条件可转变为则定理(迭代法收敛的充要条件)

迭代格式收敛的充要条件为(12)

设Ax=b，其中A=D+L+U为非奇异矩阵,且对角矩阵D也奇异，则

(1)解线性方程组的雅可比迭代法收敛的充要条件是

(J)<1，其中J=-D-1(L+U).

(2)解线性方程组的高斯-塞德尔迭代法收敛的充要条件是

(G)<1，其中G=-(D+L)-1U.

(3)雅可比迭代法收敛的充分条件是||J||<1.(4)高斯-塞德尔迭代法收敛的充分条件是||G||<1.

由定理5.5.1和定理5.5.2可知解：方程组的迭代格式为取，问雅可比迭代法是否收敛？若收敛，需要迭代多少次，才能保证各分量的误差绝对值小于10-6？例4：用雅可比方法解下列方程组迭代阵所以要保证各分量的误差绝对值小于10-6，需要迭代14次

求迭代矩阵的谱半径，需要求迭代矩阵的特征值，对高阶矩阵是比较麻烦的。利用定理5.5.1去判别比较方便一些。但在科学及工程计算中，要求解的线性方程组Ax=b,其矩阵A常常具有某些特性.例如，A具有对角占优性质或A是对称正定矩阵等，根据这些矩阵的性质，可以比较方便地判别这些迭代法的收敛性。两种特殊情况1.A为严格(按行)对角占优阵2.A是对称正定矩阵

定义5.5.3(对角占优阵)设A=(aij)n×n.如果A的元素满足称A为严格(按行)对角占优阵.矩阵A的每一行对角元素的绝对值都严格大于非对角元素绝对值之和

定理5.5.3(对角占优定理)

如果A=(aij)n×n为严格对角占优矩阵，则A为非奇异矩阵.

定理5.5.4设方程组Ax=b，如果A为严格对角占优阵，则解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收敛.证:(1)对于Jacobi迭代法,其迭代矩阵为根据定理5.5.1Jacobi迭代法收敛(2)对于G—S迭代法,其迭代矩阵为不能使用定理5.5.1,而用定理5.5.2.即从而因此由于可得矛盾由定理5.5.2知G—S迭代法收敛。定理5.5.5设矩阵A对称,且所有对角元素aii>0,则解线性方程组Ax=b的Jacobi迭代法收敛的充要条件是A及2D-A均为正定矩阵,其中D=(a11,…,ann).(2)解线性方程组Ax=b的Gauss-Seidel迭代法收敛的充分条件是A正定.

如果线性方程组系数矩阵A对称正定，则有以下的收敛定理.

例5已知方程组判断雅可比迭代法和高斯—塞德尔法的敛散性？

解

因为系数矩阵A的顺序主子式所以A是正定矩阵.也是正定矩阵，故Jacobi迭代法收敛.

再由A是对称正定矩阵，故

Gauss—Seidel迭代法也收敛.又由于

例6

在线性方程组Ax=b中，证明：当-1/2<a<1时高斯-塞德尔法收敛，而雅可比法只在-1/2<a<1/2时才收敛.即A正定，所以当-1/2<a<1时高斯-赛德尔法收敛.

证明

因为当-1/2<a<1时，得A的顺序主子式

对雅可比法迭代矩阵故只在

(J)=|2a|<1，即|a|<1/2时雅可比法收敛.当a=0.8时,G-S法收敛，

(J)=1.6>1，J法不收敛.Ax=b，例8判别下列方程组用J法和G-S法求解是否收敛因此不能用定理5.5.1，只能用定理5.5.2判断(1)Jacobi法的迭代矩阵解:即Jacobi迭代法收敛(2)Gauss-Seidel法的迭代矩阵同样用定理5.5.2判断即Gauss-Seidel迭代法发散该例说明G-S法发散时而J法却收敛！例9

讨论用Jacobi迭代法和Gauss-Seidel迭代法求解方程组