数值分析教学课件：ch03方程组迭代法

第六章线性方程组的数值解法-------迭代法1

直接法得到的解是理论上准确的，但是计算量都是

n3数量级，存储量为n2量级，这在n比较小的时候

还比较合适（n<400）

实际问题中，往往方程组的阶数很高，而且这些矩

阵(系数矩阵)往往是含有大量的0元素（稀疏矩阵方程组）。直接法运算量将会很大并且大量占用计算机资源。

因此有必要引入一类新的方法：迭代法。

引言2

迭代法的基本思想

迭代法是解线性方程组的一种重要的实用方

法，特别适用于求解在实际中大量出现的，系

数矩阵为稀疏阵的大型线性方程组。

迭代法的基本思想是去构成一个向量序列{x(k)}，

使其收敛至某个极限向量x*，并且x*就是要求解

的方程组：Ax=b的准确解。3迭代法的主要步骤

Theprocessofiterativemethod

解线性方程组迭代法的主要步骤是:

把线性方程组Ax=b化成如下形式的同解方程组

x=Bx+f

给出初始向量,按迭

代公式

x(k+1)=Bx(k)+f(k=0,1,2,…)

进行计算,其中k表迭代次数。

4

如果按上述迭代公式所得到的向量序列{x(k)}收敛于某个向量x*,则x*就是方程组Ax=b的解，并称此迭代法收敛。否则，就叫不收敛或发散。

迭代公式中的矩阵B，称为迭代矩阵。

问题

迭代公式的建立迭代公式的收敛性收敛速度误差估计5基本迭代公式把矩阵A分裂为则记

B=M-1N，f=M-1b，

则注：选取M阵，就得到解Ax=b的各种迭代法.6

本章重点介绍三个迭代法，即：

Jacobi迭代法

Gauss-Seidel迭代法

超松弛迭代法（SOR法）7Jacobi迭代法由方程组AX=b的第i个方程解出得到一个同解方程组

8获得相应的迭代公式Jacobi迭代法取初始向量称上式为雅可比迭Jacobi迭代公式。9Jacobi迭代法的矩阵形式若记

则有A=D-L-U成立，矩阵形式为

Dx=（L+U)x+b

等式两边乘以D-1，得

x=D-1（L+U）x+D-1b

由此得到迭代公式(Theiterativeschemeis:)

x（k+1）=D-1（L+U）x（k）+D-1b

10

迭代矩阵

Jacobi迭代法的特点

每迭代一次主要是计算一次矩阵乘向量所以计算量为n平方数量级。

计算过程中涉及到的中间变量及,需要

两组工作单元x(n),y(n)来存储.

计算过程中,初始数据A始终不变;

11问题：如何判断迭代终止？

定理若迭代矩阵B满足||B||〈1则

此定理给出了一个停止迭代的判别准则。12

输入最大迭代次数N，控制误差ε以及迭代初值

x=（x1，x2…，xn）输出近似值y=（y1，y2，…，yn）Jacobi迭代法的计算步骤

k=1；

如果||y-x||<ε，则输出y=（y1，y2，…，yn）。

否则k=k+1，如果k>N，算法失败。如果k<=N,

置x=y，即xi=yi

(i=1,2,…,n)，goto②

；

13例子解：相应的雅可比迭代公式为14例子0123400.30000.80000.91800.971601.50001.76001.92601.970002.00002.66002.86402.9540567890.98940.99630.99860.99950.99981.98971.99611.99861.99951.99982.98232.99382.99772.99922.9998原方程组的准确解为取初值得计算结果，按迭代公式进行迭代，15MatlabforJacobiMethodfunction

y=jacobi(a,b,x0)D=diag(diag(a));U=-triu(a,1);L=-tril(a,-1);B=D\(L+U);f=D\b;y=B*x0+f;n=1;whilenorm(y–x0)>=1.0e–6x0=y;y=B*x0+f;n=n+1;end16高斯—塞德尔(Gauss-Seidel)迭代法

Jacobi迭代法的优点是公式简单，迭代矩阵容易得到，

称为同时替换法：在每一步迭代计算过程中，计算

x(k+1)时是用x(k)的全部分量代入求x(k+1)的全部分量。

研究雅可比迭代法，我们发现在逐个求

的分量时，当计算到的分量时，当计算到都已经求得.设想一旦新分量代替旧分量，可能会加速收敛。

例如

17…………Gauss-Seidel迭代法分量形式

18Gauss-Seidel迭代的矩阵形式作

A的另一个分裂：

迭代矩阵

19例子解：相应的高斯-赛德尔迭代公式为20取迭代初值按此迭代公式进行迭代，计算结果为01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999921迭代法的收敛性

迭代法的收敛性，是指方程组

从任意初始向量X(0)出发，由迭代算法算出向量序列随着k的增加而趋向于解向量X*。

记各次误差向量22迭代法的收敛性

迭代法的收敛性等价于误差向量序列随着k的增加而趋向于零。

由

x(k+1)=Bx(k)+f及x*=Bx*+fεk+1=X(k+1)-X*=B（X(k)-X*）=·············=B

k+1（X(0)-X)=B

k+1

ε0

可推知

{x(k)}的收敛性

Bk

0

(k∞)

23迭代法的收敛性定理

定理(充要条件判别法)给定方程组X=BX+f则迭代公式对任意初始向量，都收敛的充要条件为

24

迭代法的收敛性定理

定理

(充分条件判别法)给定方程组X=BX+f如果，则迭代公式1.对任意初始向量收敛。2.有如下估计25证明

26注

由于此估计式，在实际计算中，用

||X(k+1)-X(k)||≤ε

作为迭代终止条件是合理的。

进一步可以推知：由于ρ(B)≤‖B‖<1，‖B‖越小，说明ρ(B)越小，序列{X(k)}收敛越快。27收敛速度下面我们给出收敛速度的概念：定义

R(B)=-lnρ(B)，称为迭代法的渐进

收敛速度。

由于Gauss-Seidel迭代法逐次用计算出来的新值代替旧值，所以在收敛的条件下，它要比Jacobi迭代法收敛速度快。。28Jacobi和Gauss-Seidel的收敛性29注

30对于前面的例子由迭代矩阵的特征方程因而雅可比迭代公式是收敛的。31注

32直接用矩阵A判定敛散性

收敛性定理虽然给出了判别迭代法收敛的充要条件，

但实际使用时很不方便，因为求逆矩阵和特征值的

难度并不亚于用直接法求解线性方程组。下面对一些特殊的方程组，从方程组本身出发给出几个常用的判别条件，而不必求迭代阵的特征值或范数。

定义如果矩阵A满足条件则称A是严格对角占优阵(strictlydiagonallydominantmatrix)；33A为按行按列严格对角占优阵；B为按行对角占优阵。实例(Example)34定理1若A为严格对角占优阵，则Jacobi迭代法和

G-S迭代法收敛。

定理2

若A为对称正定阵，则G-S迭代法收敛。

相关定理

可以总结，讨论迭代法的收敛性，应首先从A出发讨论其是否具有主对角占优或对称正定性；其次对迭代法的迭代阵讨论其是否有范数小于1；最后利用迭代阵的谱半径讨论（这是充分必要条件）。35定理1的证明证

首先证明Jacobi迭代的收敛性。由易求

由严格对角占优定义，得BJ∞<1,所以,Jacobi迭代法收敛。36

下面证明G-S迭代法的收敛性。对于严格对角占优阵A，其对角元素aii≠0，

i=1,2,,n，故

考虑BG的特征值λ，其特征方程为

det(I-BG)=det(I-(D-L)-1U)=det(D-L)-1det((D-L)-U)=０=>det((D-L)-U)=037

我们通过A的严格对角占优性质去证明det((D-L)-U)=0的根有性质||<1。用反证法：假设||≥1，且由于A的严格对角占优性质，有

38是严格对角占优阵，所以它是非奇异的，即det((D-L)-U)0与特征值满足det((D-L)-U)=0矛盾。故||<1即ρ(BG)<1，G-S迭代法收敛。定理得证。

39注值得注意的是，改变方程组中方程的次序，即将系数矩阵进行行交换，会改变迭代法的收敛性。

无法直接判断Jacobi迭代法和G-S迭代法的收敛性，但如果将方程组的次序修改为

40注

对于对称正定矩阵A，Jacobi迭代法不一定收敛。

迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。

41

超松弛迭代法(SOR)

通过引入参数，在Gauss-Seidel法的基础上作适当修改，在不增加过多的计算量的条件下，可得到一种新的，收敛更快的迭代法。

：

首先用G-S法定义辅助量：选择参数ω，取42

超松弛迭代法(SOR)即得SOR法其中，参数ω叫做松弛因子；若ω=1，它就是Gauss-Seidel迭代法。

43

超松弛迭代法(SOR)另一种理解将Gauss-Seidel迭代格式改写为被称为增量形式。可以将看做加一个修正量得到的。44

超松弛迭代法(SOR)如果将修正量改为即为SOR.通常，当ω>1

时，称为超松弛算法，当ω<1

时，称为亚松弛算法。目前，还没有自动选择因子的一般方法，实际计算中，通常取（0，2）区间内几个不同的ω值进行试算，通过比较后，确定比较理想的松弛因子ω。

45例用SOR法求解线性方程组

①取ω=1，即Gauss-Seidel迭代：

②取ω=1.25，即SOR迭代法：

46例迭代结果见表3.3。

表3.3Gauss-Seidel迭代法与SOR迭代法比较

Gauss-Seidel迭代法SOR迭代法(ω=1.25)kx1x2x3x1x2x301.00000001.00000001.00000001.00000001.00000001.000000015.25000003.1825000-5.04687506.31250003.9195313-6.650146523.14062503.8828125-5.02929692.62231453.9585266-4.600423833.08789063.9267587-5.01831053.13330274.0402646-5.096686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.03433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.000348647

迭代法若要精确到七位小数，

Gauss-Seidel迭代法需要34次迭代；而用SOR迭代法(ω=1.25)，只需要14次迭代。可见，若选好参数ω，SOR迭代法收敛速度会很快。

48SOR迭代的矩阵形式：X(k+1)=(1-ω)X(k)+ωD-1(b+LX(k+1)+UX(k))DX(k+1)=(1-ω)DX(k)+ω(b+LX(k+1)+UX(k)）(D-ωL)X（k+1）=[(1-ω)D+ωU]X(k)+ωb解得

X(k+1)=(D-ωL)-1[(1-