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

福州大学研究生课程

第6章 6.1 引言

解线性方程组的迭代方法

6.2 基本迭代法

6.3 迭代法的收敛性 6.4* 分块迭代法

上页

下页

福州大学研究生课程

6.1 引对线性方程组

言

Ax=b, (1.1) 其中A为非奇异矩阵, 当A为低阶稠密矩阵时, 第5 章讨论的选主元消去法是有效的. 但对于大型稀 疏矩阵方程组(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 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.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.可构造一阶定常迭代法

x ( 0 ) (初始向量), ( k 1) x Bx ( k ) f ( k 0,1, , ),

( 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写成三部分上页 下页

福州大学研究生课程

0 a11 a 21 0 a 22 A a n 1 ,1 a n 1 , 2 0 a nn a n 2 a n , n 1 a n1 0 a12 a1,n 1 a1n 0 a 2 , n 1 a 2 n 0 a n 1, n 0 D L U.上页

0

下页

福州大学研究生课程

即

A=D-L-U

a11 a A 21 a n1 0 a L 21 a n1

a12 a1 n a22 a2 n an 2 ann 0

a11 D

a22

ann

0 an 2

0 a12 a1n 0 a2 n U 0 上页 下页

福州大学研究生课程

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

x ( 0 ) (初始向量), ( k 1) x Bx ( k ) f ( k 0,1, , ),

( 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 ) a 22 an 1 a nn

a12 a11 0 an 2 ann

a1n a11 a2 n a22 0 上页 下页

福州大学研究生课程

下面给出雅可比迭代法(2.5)的分量计算公式, 记

x

(k )

( x , , x , , x ) ,(k ) 1 (k ) i (k ) T n

由雅可比迭代法(2.5)有

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

aii xi( k 1) aij x (jk ) j 1

i 1

j i 1

aij x (jk ) bi (i 1,2, , n).

n

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

上页

下页