解线性方程组的迭代法

设线性方程组为

Ax=b

其中，A为n阶非奇异矩阵，x∈Rn，b∈Rn，b≠0。

当A为低阶稠密矩阵，直接法是比较好的方法。当A为高阶稀疏矩阵，例如偏微分方程数值解所产生的方阵，这时采用迭代法比较合适了。不过，这里所谓低阶与高阶并没有明显的分界，在高性能计算机面前，一万阶也不算高。所谓稀疏矩阵，笼统地说，就是零元素占绝大多数的矩阵，反之就是稠密矩阵了。

1.迭代法的一般理论

将Ax=b等价地改写为方程组

x=Gx+f

其实，就是将原方程组等价变形为不动点方程的格式，以便于进行不动点迭代。任取初始向量x(0)，作 x(1)=Gx(0)+f， x(2)=Gx(1)+f， ……

x(k+1)=Gx(k)+f，k=0,1,2,⋅⋅⋅

G称为迭代矩阵。

如果向量序列{x(k)}是收敛的，假设limx(k)=x*，或者limx(k)−x*=0，则

k→∞

k→∞

x*=Gx*+f

也就是说x*是x=Gx+f的解，即Ax=b的解，而它与初始向量x(0)的选取无关。

如何保证该向量序列收敛呢？ 设误差ε(k)=x(k)−x*，则

ε(k+1)=x(k+1)−x*=Gx(k)+f−(Gx*+f)=G(x(k)−x*)=Gε(k)，k=0,1,2,⋅⋅⋅

1

因此，

ε(k)=Gε(k−1)=G2ε(k−2)=G3ε(k−3)=⋅⋅⋅=Gkε(0)，k=0,1,2,⋅⋅⋅

为了保证对任意初始向量x(0)，{ε(k)}收敛，必须且只须{Gk}收敛。那么，如何保证{Gk}收敛，{Gk}若收敛，会收敛到哪里？这就需要如下一个引理。 引理1.设B∈Cn×n，则{Bk}收敛当且仅当ρ(B)<1。如果ρ(B)<1，则limBk=0。

k→∞

证明略。

但ρ(G)<1这个条件并不好判定。我们知道矩阵的谱半径小于等于其任何一个相容矩阵范数。

推论1.设i为Cn×n上相容的矩阵范数，G<1，则对任意x(0)，{x(k)}都收敛到方程组Ax=b的解x*。

以下是误差估计问题。为了使矩阵范数定义比较宽(不仅仅是Cn×n上的，最好适用于任意阶矩阵。)并且具有相容性，我们选取i为i1,i2,i∞,iF等。 定理2.如果G<1，则由x(k+1)=Gx(k)+f产生的序列{x(k)}必收敛到方程组 的解x*，并且有如下的误差估计

G

x(k)−x*≤x(k)−x(k−1)−−−−−−−−−(1)

1−G

G

x(k)−x*≤x(0)−x(*)−−−−−−−−−(2)

1−G

证明：

关于收敛性已经在前面证明了。以下只证明误差估计。

任取m>k∈N+，

k

k

x(m)−x(m−1)=Gx(m−1)+f−(Gx(m−2)+f)=G(x(m−1)−x(m−2))≤G⋅x(m−1)−x(m−2)≤G⋅x(m−2)−x(m−3)≤G⋅x(m−3)−x(m−4)≤⋅⋅⋅≤G因此，对任意m>k，有

2

3

m−k

⋅x(k)−x(k−1)

2

x(m)−x(k)=x(m)−x(m−1)+x(m−1)−x(m−2)+⋅⋅⋅+x(k+1)−x(k)≤x(m)−x(m−1)+x(m−1)−x(m−2)+⋅⋅⋅+x(k+1)−x(k)≤G

m−k

x(k)−x(k−1)+G

2

m−k

m−1−k

x(k)−x(k−1)+⋅⋅⋅+G

G(1−G1−G

k+1−km−k

x(k)−x(k−1)x(k)−x(k−1)≤

G1−G

x(k)−x(k−1)

=(G+G+⋅⋅⋅+G

)x(k)−x(k−1)=

)

取m→∞，则有

x(m)−x(*)≤

G1−G

x(k)−x(k−1)(极限的保不等式性)

2

x(m+1)−x(m)=Gx(m)+f−(Gx(m−1)+f)=G(x(m)−x(m−1))≤G⋅x(m)−x(m−1)≤G⋅x(m−1)−x(m−2) ≤⋅⋅⋅≤G

m

⋅x(1)−x(0)

因此，对任意m>k，有

x(m)−x(k)≤x(m)−x(m−1)+x(m−1)−x(m−2)+⋅⋅⋅+x(k+1)−x(k) ≤G =(G

m−1

⋅x(1)−x(0)+G+G

m−2

m−2

⋅x(1)−x(0)+⋅⋅⋅+G⋅x(1)−x(0)

G(1−G=

1−G

k

m−k

k

m−1

+⋅⋅⋅+G)x(1)−x(0)

k

)

x(1)−x(0)

G

≤x(1)−x(0)

1−G

k

取m→∞，则有

x*−x(k)

G≤x(1)−x(0)(极限的保不等式性) 1−G

k

至此，结论证明完毕！

式(1)称为事后误差估计，为停机标准；式(2)称为事前误差估计，是预先估 计迭代次数。

以下是方程组Ax=b化为不动点方程组的矩阵分裂法。 假设A=M−N，其中M为非奇异矩阵。则Ax=b可以改写为

(M−N)x=Mx−Nx=b，即x=M−1Nx+M−1b=Gx+f。其中，G=M−1N， f=M−1b。我们称A=M−N为A的一个分裂。

(0)(0)T

任取初始向量x(0)=(x1(0),x2,⋅⋅⋅,xn)，得到迭代格式

3

x(k+1)=Gx(k)+f，k=0,1,2,⋅⋅⋅

若ρ(G)<1，则迭代格式是收敛的，极限向量x*为方程组Ax=b的解。

4