数值分析 第3章 解线性方程组的迭代法

解线性方程组的迭代方法 1 引言 2 基本迭代法

3 迭代法的收敛性

上页

下页

1 引对线性方程组

言

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

例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 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 20 2 0 8 8 8 4 33 1 B0 11 0 , f 11 . 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), 反复利用这个计算程序，得到一向量序列和一般的计

算公式(迭代公式)

x (0)

x x x

(0) 1 (0) 2 (0) 3

x x (1) (k ) , x x ,L , x x x x (1) 1 (1) 2 (1) 3

(k ) 1 (k ) 2 (k ) 3

,L 上页 下页

( k 1) (k ) (k ) x1 ( 3 x2 2 x3 20) / 8, ( k 1) (k ) (k ) x ( 4 x x 2 1 3 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次有

x

(10)

(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,…. 其中k表示迭代次数.

(1.6)

定义1 (1)对于给定的方程组x=Bx+f , 用公式(1.6) 逐步代入求近似解的方法称为迭代法(或称为一阶定 常迭代法，这里B与k无关). B称为迭代矩阵.

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

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

( k 1) x ( k 1) x ,x*=Bx*+f . x(k+1)=Bx(k)+f , k=0,1,2,…. (1.5) (1.6)

(1.6)减去(1.5)式得：ε(k+1)=Bε(k) (k=0,1,2,… ) 递推得

(k )

B

( k 1)

L B .k (0)

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

2 基本迭代法设线性方程组 Ax=b, (2.1) 其中，A=(aij)∈Rn×n为非奇异矩阵，下面研究任何建 立Ax=b的各种迭代法. 将A分裂为 A=M-N. (2.2) 其中，M为可选择的非奇异矩阵，且使Mx=d容易求 解，一般选择A的某种近似，称M为分裂矩阵.

上页

下页

于是，求解Ax=b转化为求解Mx=Nx+b ,即求解

Ax b 求解 x M 1 Nx M 1b.可构造一阶定常迭代法(0) x (初始向量), ( k 1) (k ) Bx f (k 0,1,L , ), x

(2.3)

其中 B=M-1N=M-1(M-A)=I-M-1A , f=M-1b. 称 B=I-M-1A为迭代法的迭代矩阵，选取M矩阵，就得 到解Ax=b的各种迭代法. 设aii 0 (i=1,2,…,n),并将A写成三部分上页 下页

a11 a22 A O

0 0 a21 M M O an 1,1 an 1,2 L ann an 2 L an1 a1,n 1 a2,n 1 M 0 a1n a2 n M an 1,n 0

0 an ,n 1

0

0 a12 L 0 L O D L U.

上页

下页

即

A=D-L-U

a11 a12 L a a22 L 21 A M M a n1 a n 2 L 0 a 0 21 L M M a n1 a n 2 L

a1 n a2 n M ann 0

a11 D

a22 O

ann

0 a12 L 0 L U O

a1n a2 n M 0 上页 下页

2.1 雅可比(Jacobi)迭代法 设aii 0 (i=1,2,…,n),选取M为A的对角元素部分, 即选取M=D(对角阵),A=D-N,由(2.3)式得到解方 程组Ax=b的雅可比(Jacobi)迭代法. 又称简单迭代法.(0) x (初始向量), ( k 1) (k ) x Bx f (k 0,1,L , ),

(2.5)

其中B=I-D-1A=D-1(L+U)=J, f=D-1b. 称J为解Ax=b的 雅可比迭代法的迭代矩阵.

上页

下页

于是雅可比迭代法可写为矩阵形式

x ( k 1 ) D 1 ( L U ) x ( k ) D 1 b其Jacobi迭代矩阵为

0 a21 1 BJ D ( L U ) a22 M a n1 a nn

a12 a11 0 M an 2 ann

L L

L

a1n a11 a2 n a22 M 0 上页 下页

下面给出雅可比迭代法(2.5)的分量计算公式, 记(k) T x ( k ) ( x1( k ) ,L , xi( k ) , L , xn ) ,

由雅可比迭代法(2.5)有

Dx( k 1) ( L U ) x ( k ) b,每一个分量写出来为( k 1) i

aii x

aij xj 1

i 1

(k ) j

j i 1

axij

n

(k ) j

bi (i 1, 2,L , n).

即当aii 0时，有i 1 n 1 xi( k 1) ( aij x (jk ) aij x (jk ) bi ) (i 1, 2,L , n). aii j 1 j i 1

上页

下页

即由方程组Ax=b得到的 等 价 方 程 组

1 a12 x2 L a1n xn b1 ] x1 a [ 11 1 x2 [ a21 x1 L a2 n xn b2 ] a22 M 1 [ an1 x1 an 2 x2 L bn ] xn ann

其中 aii(i) 0 (i=1,2,…,n)

上页

下页

建立的雅可比迭代格式为

( k 1) 1 (k ) (k ) (k ) x ( a x a x L a x 12 2 13 3 1n n b1 ) 1 a11 ( k 1) 1 (k ) (k ) (k ) a23 x3 L a2 n xn b2 ) x2 ( a21 x1 a22 M ( k 1) 1 (k ) (k ) bn ) xn a ( an1 x1 L an n 1 xn 1 nn 上页 下页

于是，解Ax=b的雅可比迭代法的计算公式为

(0) (0) (0) T x ( x , L , x 1 n ) , n ( k 1) (k ) x ( b a x i i ij j ) / aii , j 1 j i (i 1, 2, L , n) (k 0,1, L 表示迭代次数).

(2.6)

由(2.6)式可知，雅可比迭代法计算公式简单， 每迭代一次只需计算一次矩阵和向量的乘法且计算 过程中原始矩阵A始终不变.上页 下页

本文来源：https://www.bwwdw.com/article/lcei.html