Ax b ( D L U ) x b Dx ( L U ) x b x D 1 ( L U ) x D 1 b
于是 其中 Ax b x D 1 ( L U ) x D 1b BJ x g BJ D ( L U ), g D b
x
(k )
( k 1)
x
( k 2)
) B
k 1
( x (1) x (0) )
k
B B (k ) ( k 1) x x x x (1) x (0) 1 B 1 B
注 : (1) B 越小, 收敛越快. (2) B 接近1时, 收敛慢.
数值分析
数值分析
迭代终止标准
Ax b x M -1 Nx M -1b M -1 (b Nx ) 1 8 0 0 0 20 3 x2 2 x3 1 0 33 4 x x 1 3 11 36 6 x1 3 x2 1 0 12 0
a13 a1n a12 b1 x1 a x2 a x3 a xn a 11 11 11 11 a23 a2 n a21 b2 x1 x3 xn x2 a22 a22 a22 a22 a n1 an 2 ann1 bn xn x1 x2 x n 1 ann ann ann ann
k 0,1, 2,....
迭代到第10次,得到 x(10) (3.000032,1.999838, 0.9998813)T 已知精确解为 x (3, 2,1)T
迭代格式 x ( k 1) Bx ( k ) g 3 0 20 -2 8 8 8 1 , g 33 迭代矩阵B= - 4 0 11 11 11 - 6 36 3 0 12 12 12
数值分析
第六章 线性代数方程组的迭代解法
迭代法适用于求解大型稀疏的线性方程组，其
基本思想是通过构造迭代格式产生迭代序列，由迭代
序列来逼近原方程组的解，因此，要解决的基本问题 是：1. 如何构造迭代格式 2.迭代序列是否收敛
一 . 基本迭代法的格式及收敛性 二 . 几种实用的基本迭代法 三 . 应用实例
A 为系数矩阵，非奇异且设aii≠0；b为右端，x为解向量
A=M+N M的逆容易求得Ax =b (M+N)x=b Mx=-Nx+b x=-M-1Nx+M-1b
Ax b x Bx g,
B M 1 N , g M 1b
数值分析
数值分析
Ax b x Bx g , 基本迭代法的迭代格式 x ( k 1) Bx ( k ) g
k
k
x
(k )
B x x (1) x (0) k 1 B
ln(
1 B x
(1)
x
(0)
)
ln B
数值分析
数值分析
二.几种实用的基本迭代法

1、Jacobi迭代法

2、Gauss-Seidel迭代法
3、超松弛迭代法（SOR)

数值分析
数值分析
1、Jacobi 迭代
B M 1 N , g M 1 b
( k 0,1, 2,)
其中B R nn 称为迭代矩阵，g是已知的n维向量，
给定x (0) ,由迭代格式 x ( k 1) Bx ( k ) g 即可产生迭代序列{ x }。
当 对 x 得
( k 1)
(k )
lim x ( k ) x
(k )
x
B
k
1 B
x (1) x (0)
证明 :由x Bx g和x ( k ) Bx ( k 1) g有 x ( k ) x B( x ( k 1) x ) B( x ( k 1) x ( k ) ) B( x ( k ) x )
从而 x ( k ) x B x ( k 1) x ( k ) B x ( k ) x x
(1) 绝对误差标准。给出容许误差界 当 || x ( k ) x ( k 1) || p 时，p 1, 2, , 终止迭代， 解取为x x ( k ) . 常取p , || x ( k ) x ( k 1) || max | xi( k ) xi( k 1) |
1 1
Jacobi迭代的矩阵格式 x
( k 1)
BJ x
(k )
g
Jacobi迭代矩阵
数值分析
推导其分量形式
由 Ax b ( D L U ) x b Dx ( L U ) x b 得
数值分析
a11 x1 a12 x2 a13 x3 a1n xn b1 a22 x2 a21 x1 a23 x3 a2 n xn b2 ann xn an1 x1 an 2 x2 ann1 xn1 bn 第i个方程除以aii(i =1,2,…,n),得
数值分析
数值分析
收敛性分析
x是精确解 迭代格式为 误差向量 Ax b x Bx g x ( k ) Bx ( k 1) g

(k )
x x
(k )
B( x x
( k 1)
) B
( k 1)
B k (0) 其中 (0) x x (0)是初始误差向量，是一个确定的值
A
p
因 是A的任一特征值, 故定理得证.
定理2 (迭代法收敛的充分条件) 如果迭代格式x ( k ) Bx ( k 1) g的迭代矩阵B的某一种 范数 B 1, 则此迭代格式收敛.
数值分析
数值分析Biblioteka 定理3 如果迭代格式x ( k ) Bx ( k 1) g的迭代矩阵B满足 B 1, 则有如下的误差估计式. B (k ) x x x ( k ) x ( k 1) 1 B x
x1 (20 3 x2 2 x3 ) / 8 x2 (33 4 x1 x3 ) / 11 x (36 6 x 3 x ) / 12 1 2 3
数值分析
数值分析
迭代格式的分量形式为 (k ) (k ) x(k+1) (20 3 x 2 x 1 2 3 )/ 8 (k+1) (k ) (k ) x (33 4 x x 2 1 3 ) / 11 x(k+1) (36 6 x ( k ) 3 x ( k ) ) / 12 1 2 3
k
Bx
(k )
g 取极限
x Bx g Ax b
注：分解A是一个重要问题
数值分析
数值分析
8 例：对线性方程组Ax b，其中A= 4 6 8 解：将A分解为A M N ,其中M = 0 0
-3 2 20 33 11 -1 , b 3 12 36 0 0 0 -3 2 4 0 -1 11 0 , N = 0 12 6 3 0
(k )
B x x ( k ) x ( k 1) 1 B
数值分析
数值分析
又因为x ( k ) Bx ( k 1) g，x ( k 1) Bx ( k 2) g x
(k )

x
( k 1)
B( x
( k 1)
x
( k 2)
)
x ( k ) x ( k 1) B( x ( k 1) x ( k 2) ) B (x
数值分析
数值分析
一 . 基本迭代法的格式及收敛性
设有线性代数方程组 a11x1+a12x2+· · · · +a1nxn=b1 a21x1+a22x2+· · · · +a2nxn=b2 ..................... an1x1+an2x2+· · · · +annxn=bn 用矩阵表示： Ax =b
(0)
(k )
数值分析
数值分析
例：用迭代法求解方程组 x1 2 x2 5 3 x1 x2 5
解 : 构造迭代格式x ( k 1) Bx ( k ) g ,
( k 1) (k ) x1 5 2 x2 ， ( k 1, 2, ) ( k 1) (k ) 3 x1 5 x2 0 2 5 迭代矩阵 B , g 3 0 5
数值分析
数值分析
定义 基本迭代法x ( k 1) Bx ( k ) g产生的迭代序 列{ x ( k ) }，如果对任取初始向量x (0)都有 lim x ( k ) x，
k
则称此迭代法是收敛的，否则是发散的。 在Rn中，点列的收敛等价于每个分量的收敛。即
(k ) (k ) (k ) T 对x ( k ) ( x1 , x2 , , xn ) , T x ( x1 , x2 , , xn ) Rn , (k ) (k ) 则 lim x x lim xi xi ,( i 1, 2, , n) k k
数值分析
数值分析
Jacobi迭代的分量形式
a13 a1n a12 b1 x1 a x2 a x3 a xn a 11 11 11 11 a23 a2 n a21 b2 x1 x3 xn x2 a22 a22 a22 a22 a n1 an 2 ann1 bn xn x1 x2 x n 1 ann ann ann ann