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

第6章

解线性方程组的迭代方法

6.1 迭代法的基本概念 6.2 雅可比迭代法与高斯-赛德尔迭代法

6.3 超松弛迭代法 6.4* 共轭迭代法

上页

下页

6.1 迭代法的基本概念6.1.1 引 言 对线性方程组 Ax=b, (1.1) 其中A为非奇异矩阵, 当A为低阶稠密矩阵时, 第5章 讨论的选主元消去法是有效的. 但对于大型稀疏矩 阵方程组(A的阶数n很大 104,但零元素较多), 利 用迭代法求解是合适的. 本章将介绍迭代法的一些基本理论及雅可比 迭代法，高斯-赛德尔迭代法，超松弛迭代法，而 超松弛迭代法应用很广泛。 下面举简例，以便了解迭代法的思想.上页 下页

例1 求解方程组

8 x1 3 x2 2 x3 20, 4 x1 11 x2 x3 33, 6 x 3 x 12 x 36. 2 3 1记为Ax=b,其中

(1.2)

x1 8 3 2 30 A 4 11 1 , x x2 , b 33 . x 6 3 12 36 3 此方程组的精确解是x*=(3,2,1)T. 现将(1.2)改写为

上页

下页

1 3 x 2 2 x 3 20), x1 8 ( 1 x 3 33), x 2 ( 4 x1 11 1 36). x 3 12 ( 6 x1 3 x 2 或写为x=B0x+f,其中3 2 8 0 20 8 8 4 33 1 B0 11 0 11 , f 11 . 6 3 0 36 12 12 12

(1.3)

上页

下页

我们任取初始值，例如取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), 反复利用这个计算程序，得到一向量序列和一般的计

算公式(迭代公式)( ( ( x10 ) x11) x1k ) ( 0 ) (1) (1) (k ) x 2 , x x 2 , , x ( k ) x 2 , (0) (1) (k ) x3 x3 x3

x (0)

上页

下页

( ( ( x1k 1) ( 3 x2k ) 2 x3k ) 20) / 8, ( k 1) ( ( x2 ( 4 x1k ) x3k ) 33) / 11, ( k 1) (k ) (k ) ( 6 x1 3 x2 36) / 12. x3

(1.4)

简写为

x(k+1)=B0x(k) +f,

其中k表示迭代次数(k=0,1,2, ). 迭代到第10次有(10)

x

(3.000032 , 1.999838 , 0.999813 ) ;T

(10)

0.000187

( (10) x (10) x ).上页 下页

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

lim x ( k ) x k

对于任何一个方程组x=Bx+f(由Ax=b变形得到的 等价方程组),由迭代法产生的向量序列x(k)是否一定 逐步逼近方程组的解x*呢？回答是不一定. 请同学们 考虑用迭代法解下述方程组

x1 2 x2 5, x2 3 x1 5.

但 x

(k)并不是 所有的都收 敛到解x*!

上页

下页

对于给定方程组x=Bx+f,设有唯一解x*,则 x*=Bx*+f . (1.5)又设x(0)为任取的初始向量, 按下述公式构造向量序列 x(k+1)=Bx(k)+f , k=0,1,2, . (1.6) 其中k表示迭代次数. 定义1 (1)对于给定的方程组x=Bx+f , 用公式(1.6) 逐步代入求近似解的方法称为迭代法(或称为一阶定 常迭代法，这里B与k无关). B称为迭代矩阵.

(2) 如果limx(k) (k→ )存在(记为x*), 称此迭代法收敛, 显然x*就是方程组的解, 否则称此迭代法发散.上页 下页

由上述讨论，需要研究{x(k)}的收敛性. 引进误 差向量

( k 1) x ( k 1) x ,由(1.6)减去(1.5)式，得 (k+1)=B (k) (k=0,1,2, ), 递推得

( k ) B ( k 1) B k ( 0 ) .要考察{x(k)}的收敛性，就要研究B在什么条件下 有limε(k)=0 (k→∞),亦即要研究B满足什么条件时有 Bk→0(零矩阵) (k→∞) .上页 下页

6.1.2 向量序列与矩阵序列的极限定义2 设向量序列{x(k)} Rn, x(k)= (x1(k),…,xn(k))T, 如果存在x= (x1, x2, …, xn)T Rn,使

lim xk

(k ) i

xi ,

i 1,2, , n. lim x ( k ) x. ,记作k

则称向量序列{x(k)}收敛于x 显然， lim xk (k )

x lim xk

(k )

x 0.

其中 · 为任一向量范数.

上页

下页

定义3 设矩阵序列Ak={aij(k)} Rn×n及A={aij} Rn×n, 如果n2个数列极限存在，且有

i , j 1,2, , n. k 则称矩阵序列{Ak}收敛于A ,记作 lim Ak A. lim a(k ) ij

aij ,

k 1 2 2 2 A ,A , , Ak 2 0 0 0 且设| |<1,考察其极限.解 显然，当| |<1时，则有

例2 设有矩阵序列

k

k k 1 , . k

0 0 lim Ak lim A 0 0 . k k k

上页

下页

矩阵序列极限概念可以用矩阵算子范数来描述.

定理1

lim Ak A lim Ak A 0,k k

其中 · 为矩阵的任意一种算子范数. 证明 显然有

lim Ak A lim Ak A 0.k k

再利用矩阵范数的等价性, 可证定理对其它范数成立.

上页

下页

定理2 limAk=0 的充分必要条件是

lim Ak x 0, x R n .k

(1.7)

证明 对任一种矩阵范数的从属范数有

Ak x Ak x .若limAk=0, 则lim||Ak||=0, 故对一切x Rn有lim||Akx||=0. 故(1.7)式成立. 反之，若(1.7)式成立，取x为第j个坐标向量ej, 则若limAkej =0, 表示Ak的第j列元素极限均为零，当 j=1,2, …,n时就证明了limAk=0. 证毕. 下面讨论一种与迭代法(1.6)有关的矩阵序列的收 敛性, 这种序列由矩阵的幂构成,即{Bk}, 其中B Rn×n.上页 下页

定理3 设B Rn×n,则证明3个命题等价： (1) limBk =0; (2) (B)<1;

(3)至少存在一种从属的 矩阵范数||· ,使||B|| <1. ||证明 (1)=>(2) 用反证法，假定B有一个特征值 , 满足| | 1,则存在x 0,使Bx= x,由此可得||Bkx||= | |k||x||, 当k→ 时{Bkx}不收敛于零向量. 由定理2可 …… 此处隐藏：2784字，全部文档内容请下载后查看。喜欢就下载吧 ……