数值分析教教案20

对于阶数不太高的线性方程组，用直接法比较有效，但对于由工程技术产生的高阶方程组，若其系数矩阵是无规律稀疏阵（即矩阵的阶数较大，但零元素较多），直接法就很难解决存储问题，所以提出了用迭代思想求解线性方程组的方法。

迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法，它需要计算机的存储单元较少，因为它可不必存储系数矩阵的零元素。迭代法的基本思想是给定方程组AXb，构造一个序列

X，使其收敛到某个极限向量Xn**X，其中是方程组AXb的

精确解。

在讨论迭代法的过程中要用到向量范数、矩阵范数及序列极限等概念，为此，先介绍这方面的基本知识。

5.1.2向量范数

向量范数是用来度量向量长度的。 定义1：对XRn，若有实数X与之对应，且这种对应法

满足下面三个性质：

n1. XR，X0，而且X0，当且仅当X0（非负性）。

2. R，

XX（齐次性）。

nX,YR3. ，有XYXY（三角形不等式），则

称该实数X为向量X的范数。

nX,YR利用定义1中的性质3可以证明对，有

XYXY。事实上，由XXYYXYY所以，

XYXY。

XR其中

n，定义：Xpnpxi (5-1) i1p1pp1,。可以根据定义

p1验证X满足范数定义的条

件，所以X为

X的范数。由(5-1)式可知道，给定一个向量，它

的范数定义可以有无穷多种，经常采用的范数是

p1，p2，

p时的定义。

给定RnTX(x,x,,x)中的，常用的范数为： 12nX1x1x2xnxi （5-2）

i1n2222x1x2xnxi （5-3）

i112nX2X

maxx1,x2,,xnmaxxi （5-4）

1inTX(1,2,4)【例5-1】计算向量的各种范数。

解：

X1=1+2+4=7；X2=

12(2)24221；

Xmax{1,2,4}=4

1x3由向量范数的定义，可以讨论向量的收敛问题。 若R中的向量序列{XnnklimXX0，则}满足条件：knn{X}在范数称

意义下收敛于R中的向量

X。

n1. 向量范数的连续性定理：给定R中的任意向量

X(x1,x2,,xn)T，非负函数X为向量的任意一向量范数，则

X是X的各分量x1,x2,,xn的连续函数。

2. 向量范数的等价定理：给定XR，对于R上的任意两种

nn范数，总存在与

X无关的正常数

m，M，使关系式：

mXXMXnXR成立。 ，对一切

nnR3. 在中，若在某一种范数意义下向量序列{X}收敛，则在

任何范数意义下该向量序列仍收敛，即：

limXkX*limXkX0。这里是向量的任意一种kk范数。

4. 在R中，向量序列{Xnn}收敛于向量X*的充要条件为：

limxjkxj，其中xjk,xj分别表示Xk和X*的第kj个分量。

AX5.1.3矩阵范数

设ARnn，定义矩阵A的范数为：AmaxX0XnXRmaxAX，

X1XRn则由定义可知矩阵范数具有下列性质：

1. ARnn，

A0，而且A0当且仅当A0（非负性）。

2. R，有AA（齐次性）。

nnA,BR3. ，有ABAB（三角形不等式）。

4. XRn，ARnnnn，AXAX。

5. A,BR，ABAB

6. I1，其中I为单位阵。

nnAR设，如果存在R使得：AXX，则称为

矩阵A的一个特征值。

X就是特征值对应的特征向量。

式（5-2）～（5-4）定义的三种常用向量范数对应的矩阵范数定义为：

A1maxaij（列范数）

1jni1nA2max(ATA)（2-范数）

其中max(ATA)表示AA的最大特征值。

TAmaxaij（行范数）

1inj1n12【例5-2】给定A34求A1，A2，A。

解：由

a11a214，a12a226，得A16。

又由a11a123，a21a227，得

A7。

13121010AA1020 由：2434TAA的特征多项式为： 得

TP()101010230100

20T2301000AA的特征值11555，解，得

21555。从而：

A21555。

对应于向量范数的等价性，矩阵范数也有等价性结论： 给定

ARnn，对于Rnn上的任意两种范数，，总

存在与A无关的正常数m，M，使关系式：mA成立，即RnnAMA上的任意两种范数，是等价的。

{AknnnnR}为上的矩阵序列，若存在R上的矩阵A，使得：

limAkA0成立，则称矩阵序列{Ak}是收敛的，称

kk{A}的收敛极限。 序列

A为矩阵

由矩阵范数的等价性与矩阵收敛性的定义知，对矩阵序列

{A}收敛到矩阵A，若对Rnn上的一种范数成立，则其他范数

klimAA，也成立。所以通常记矩阵序列{A}是收敛于A为：kkk而不特别强调是在哪种范数意义下收敛。

Rknnk上的矩阵序列A是收敛于

A的充要条件为：

kkklimaijaij，aaA其中ij和ij分别表示和A的第i行第

j列的

元素。

5.1.4谱半径

对于Rnn的上的矩阵

A，设A的特征值为1,2,,n，称

(A)=max{1,2,,n}为矩阵A的谱半径。

39【例5-3】给定A61，求(A)。

解：特征多项式为：IA963289，则1的特征为147，247，从而(A)47。

nnR对于上的矩阵A，有(A)A。此定理给出矩阵范

数与谱半径的关系。

nnR如果对于上的矩阵A有A1，则IA为非奇异矩阵，

且有估计式：(IA)给定

k111A成立。

ARnnklimA0的充要条件是，则k(A)1，其中

A(k1,2,)表示

A的k次幂。

X0出发，利用迭代格式

5.1.5迭代法的收敛性

从任意选取的初始向量

Xk1MXkg构造迭代序列Xk，向量序列收敛到方程组的精

确解的条件是什么呢？下同面给出了4个定理。其中前两个定理适用

k1kXMXg的迭代法，后两个定理是针于所有具有迭代格式

对Jacobi迭代法、Gauss-Seidel迭代法和逐次超松弛迭代法提出的一些特殊的结论。

1. 对任意初始向量

X0和常数项

g，由迭代格式

Xk1MXkg（k1,2,,n）产生的向量序列{Xk}收敛的充

klimM0。其中M为所选迭代格式的迭代矩阵。 要条件为k02. 对任意初始向量X和常数项

g，由迭代格式

Xk1MXkg（k1,2,,n）产生的向量序列{Xk}收敛的

充要条件为：(M)1，其中M为所选迭代格式的迭代矩阵。

3. 若矩阵A(aij)nn满足：aiiaij (ij1jin1,2,,n)且至少

有一个i值，使上式中严格的不等号成立，则称矩阵

A具有对角优势。

若对所有值上式中的严格不等号都成立，则称矩阵占优矩阵。如果矩阵

iA是严格对角

A是严格对角占优矩阵，则矩阵

A非奇异。

4. 若系数矩阵

A严格对角占优，则Jacobi迭代法和

Gauss-Seidel迭代法必定收敛。逐次超松弛迭代法的必要条件是

02。

5.1.6迭代法的误差估计

klimM0或者上节得出的迭代法收敛的充要条件为k(M)1，其中M为迭代格式的迭代矩阵，在实际问题中，这两

种条件都很难验证的，对于

Rnn上的矩阵A，有(A)A得

(M)M，所以可以用M作为(M)的一种估计得到迭代收敛

的充要条件，即当M1时迭代必收敛。关于这个充要条件的误差计算，有以下定理。

k1kXMXg中，在方程组的迭代公式如果迭代矩阵M满

足

Mq1，则第k次迭代结果

Xk对于精确解

X*有误差

估计式：

XkX*Mqkk*10Xk1Xk 。 XX 和 XX1M1q5.2 求解线性代数方程组的迭代方法

迭代法是解线性方程组的一个重要的实用方法，特别适用于求解在实际中大量出现的系数矩阵为稀疏阵的大型线性方程组。

本节介绍求解线性方程组的Jacobi迭代法、Gauss-Seidel迭代法和松弛迭代法。

5.2.1 Jacobi迭代法

Jacobi迭代法又称简单迭代法。 1. Jacobi迭代原理 设有线性方程组Ax＝b，即

a11x1a12x2a1nxnb1axaxaxb2112222nn2axaxaxbn22nnnnn11的系数矩阵A非奇异，不妨设aii（5-5）变形为

（5-5）

0,i1,2,,n。将方程组

b12x2b13x3b1nxng1x1xbxb23x3b2nxng22211 （5-6） xnbn1x1bn2x2bnn1xn1gnbi其中bija,(ij,i,j1,2,,n),gia(i1,2,,n)。若记

iiiiaij0b21Bbn1b120bn2b13b1n1b23b2n1bn3bnn1b1nb2n 0Tgg1则方程组（5-6）可简记为

g2gn

xBxg （5-7）

选取初始向量代入迭代公式

x(k1)Bx(k)g产生向量序列

(k1)(k0,1,2,) （5-8）

x，由上述计算过程所给出的迭代法称为Jacobi

1aii迭代法，又叫简单迭代法。式（5-8）为它的迭代公式，迭代矩阵为B。式（5-8）的分量形式为

x(k1)iaj1jinijx(k)jbiaii （5-9）

这是Jacobi迭代法的计算公式。如果用系数矩阵A来表示，则有

BID1A,gD1b

1其中Ddiag(a11,a22,,ann)，D现把矩阵A分解成如下形式：

111diag(,,,)

a11a22anna11D0a21Lan1a22, ann,

00an20a12a1n0a2nU

0则ADLU。方程组

Axb改写成

xD1LUxD1b

相应的矩阵形式的迭代公式为

xk1D1LUxkD1b （5-10）

简记为

x式中，

k1Bxg （5-11）

kBD1LU,gD1b （5-12）

迭代公式（5-10）或（5-11）也称为Jacobi迭代，同时称式（5-12）中的B为Jacobi迭代矩阵。

【例5-4】用Jacobi迭代法求解线性方程组。

10x1x22x372x110x22x383xx5x42

231解 由Jacobi迭代法的计算公式（5-9），有

x0.1x0.2x7.2(k1)(k)(k)x20.1x10.2x38.3(k1) (k)(k)0.2x10.2x28.4x3取x(0)(k1)1(k)2(k)3(0,0,0)xx(1)1T，代入上式得

7.2x(1)28.3x(1)38.4x1(2)0.18.30.28.47.29.71(2)20.17.20.28.48.310.70

(2)x30.27.20.28.38.411.50如此继续下去，迭代结果见表5-1。

表5-1

k 0 1 2 3 4 5 6 7 8 9 x(k)1 x(k)2 x(k)3 0.0000 7.2000 9.7100 10.5700 10.8535 10.9510 10.9834 10.9944 10.9981 10.9994 0.0000 8.3000 10.7000 11.5700 11.8354 11.9510 11.9834 11.9981 11.9941 11.9994 0.0000 8.4000 11.5000 12.4820 12.8282 12.9414 12.9504 12.9934 12.9978 12.9992 迭代9次，得近似解x(9)(10.9994,11.9994,12.9992)T，容易验证，方

Tx(11,12,13)程组的精确解为，从表5-1中可以看出，当迭代次数

增加时，迭代结果越来越接近精确解。

2. Jacobi迭代法的MATLAB实现

function [x,k,flag]=Jacobi(A,b,delta,max1) % 求解线性方程组的迭代法,其中, % A为方程组的系数矩阵; % b为方程组的右端项;

% delta为精度要求,缺省值为1e-5; % max1为最大迭代次数,缺省值100; % x为方程组的解; % k为迭代次数;

% flag为指标变量 flag='OK!'表示迭代收敛到指标要求, % flag='fail!'表示迭代失败. if nargin<4 max1=100; end if nargin<3 delta=1e-5; end n=length(A); k=0;

x=zeros(n,1); y=zeros(n,1);flag='OK!'; while 1 for i=1:n y(i)=b(i); for j=1:n if j~=i

y(i)=y(i)-A(i,j)*x(j); end end

if abs(A(i,i))<1e-10|k==max1 flag='Fail';return; end

y(i)=y(i)/A(i,i);

end

if norm(y-x,inf)4x1x2x313x15x2x38【5-5】求解性线方程组。 2xx6x2231解：在命令窗口输入系数矩阵和右端项： >>A=[4 1 -1;1 -5 -1;2 -1 -6],b=[13 -8 -2]' 回车得到： A =

4 1 -1 1 -5 -1 2 -1 -6 b =

13 -8 -2 再输入：

>> [x,k,flag]=Jacobi(A,b) 回车得到：

x = 3.0000 k = 9 flag =OK! 2.0000 1.0000

这说明经过9次迭代得到满足精度要求的近似解

X3,2,1T。