当前位置:首页 >> 数学 >>

第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 x
k ??

(k ) i

? xi ,

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

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

? x ? lim x
k ??

(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可知(1)不成 立,从而知| ? |<1 ,即(2)成立. (2)=>(3) 根据第5章定理18,对任意? >0,存在一 种从属范数||·? ,使||B||???(B)+?,由(2)有?(B)<1,适 || 当选取? >0,可使||B||?<1,即(3)成立. (3)=>(1) 由(3) 给出的矩阵范数||B||?<1,由于 ||Bk||??||B||?k, 可得lim||Bk||=0, 从而有limBk =0.
上页 下页

定理4 设B?Rn×n,||· ||为任一种矩阵范数,则

lim B
k ??

1 k k

? ? ( B ).

(1.8)

? ( B) ? ?? ( B k )?k ? B k k . ?1 另一方面对任意? >0,记 B? ? ?? ( B) ? ? ? B.
B? ?
k

证明 由第5章定理18,对一切k有 1 1

显然有?(B?)<1. 由定理3有limB?k=0 ,所以存在正整 数N=N(?),使当k>N 时,

即k>N 时有

? ( B) ? B

?? ( B ) ? ? ? 1
k k

Bk

k

? 1.

? ? ( B) ? ? .
上页 下页

由?的任意性即得定理结论.

6.1.3 迭代法及其收敛性
设有线性方程组 Ax=b, 其中,A=(aij)∈Rn×n为非奇异矩阵,下面研究如何建 立解Ax=b的迭代法. 将A分裂为

A=M-N.

(1.9)

其中,M为可选择的非奇异矩阵,且使Mx=d容易求 解,一般选择A的某种近似,称M为分裂矩阵.

上页

下页

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

Ax ? b ? 求解 x ? M Nx ? M b.
也就是求解线性方程组 x=Bx+f. 从而可构造一阶定常迭代法: (1.10)

?1

?1

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

(1.11)

其中 B=M-1N=M-1(M-A)=I-M-1A , f=M-1b. 称 B=I-M-1A为迭代法的迭代矩阵,选取M矩阵,就得 到解Ax=b的各种迭代法. 下面给出迭代法(1.11)式收敛的充分必要条件.
上页 下页

定理5(一阶定常迭代法的基本定理) 给定线性 方程组(1.10)及一阶定常迭代法(1.11)式,对任意选 取初始向量x(0),迭代法(1.11)式收敛的充分必要条件 是矩阵B的谱半径?(B)<1. 证明 (<=) 设?(B)<1,易知Ax=f(其中A=I-B)有 唯一解,记为x*,则 x*=Bx*+f. 误差向量 ?(k)=x(k)-x*=Bk?(0), ?(0)=x(0)-x* . 由设?(B)<1,应用定理3,有limBk=0. 于是对任意x(0) 有lim?(k)=0,limx(k)=x*. (=>) 设对任意x(0)有limx(k)=x*, 其中x(k+1)=Bx(k)+f. 显然, 极限x*是线性方程组(1.10)的解, 且对任意x(0)有 ?(k)=x(k)-x*=Bk?(0)→0 (k→?) . 由定理2知limBk=0,再由定理3,即得?(B)<1.
上页 下页

例3 考察线性方程组(1.2)给出的迭代法(1.4)式 的收敛性.
解 先求迭代矩阵B0的特征值. 由特征方程

?

?3 8

det( ?I ? B0 ) ?
可得
3

4 11 1 2

?
1 4

1 4 ?1 11

? 0.

?

det( ?I ? B0 ) ? ? ? 0.034090909? ? 0.039772727 ? 0.
解得

?1 ? ?0.3082 , ?2 ? 0.1541 ? i 0.3245 , ?2 ? 0.1541 ? i 0.3245 .

?1 ? 0.3082 ? 1, ?2 ? ?2 ? 0.3592 ? 1.
即?(B0)<1,所以用迭代法(1.4)式解(1.2)是收敛的.
上页 下页

例4 考察用迭代法解线性方程组
x(k+1)=Bx(k)+f.

? 0 2? ? 5? 的收敛性,其中 B ? ? ? 3 0 ?, f ? ? 5 ?. ? ? ? ? ? ? ?
解 特征方程为det(?I-B)= ?2-6=0,特征值

?1, 2 ? ? 6 ,
即?(B)>1,这说明用迭代法解此方程组不收敛. 迭代法的基本定理在理论上是重要的,由于 ?(B)?||B||,下面利用矩阵B的范数建立判别迭代法收 敛的充分条件.
上页 下页

定理6(迭代法收敛的充分条件) 设有线性方程组 x=Bx+f, A=(aij)∈Rn×n, 及一阶定常迭代法 x(k+1)=Bx(k)+f. 如果有B的某种算子范数||B||=q<1,则 (1) 迭代法收敛,即对任取x(0)有 limx(k)=x*,且 x*=Bx*+f.

( 2) x ? ? x ( k ) ? q k x ? ? x ( 0 ) .
( 3) x ? x
? (k )

( 4) x ? ? x ( k )

q ? x ( k ) ? x ( k ?1 ) . 1? q k q ? x (1) ? x ( 0 ) . 1? q
上页 下页

证明 由基本定理知,结论(1)是显然的. (2) 显然有关系式x*-x(k+1)=B(x*-x(k))及 x(k+1)-x(k)=B(x(k)-x(k-1)). 于是有 ① x ( k ?1) ? x ( k ) ? q x ( k ) ? x ( k ?1) ;



x ?x

?

( k ?1)

?q x ?x

?

(k )

.

反复利用②即得(2). (3) 考察 x ( k ?1) ? x ( k ) ? x ? ? x ( k ) ? ( x ? ? x ( k ?1) )

即有

? x ? ? x ( k ) ? x ? ? x ( k ?1) ? (1 ? q ) x ? ? x ( k ) , 1 q ? (k ) ( k ?1) (k ) x ?x ? x ?x ? x ( k ) ? x ( k ?1 ) . 1? q 1? q

(4) 反复利用①,则得到(4).
上页 下页

注意,定理6只给出迭代法(1.11)式收敛的充分 性,即使条件||B||<1对任何常用范数均不成立,迭代

序列仍可能收敛.
例5 迭代法x(k+1)=Bx(k)+f ,其中

? 0.9 0 ? ? 1? B?? ? 0.3 0.8 ?, f ? ? 2 ?. ? ? ? ? ? ? ?
显然||B||?=1.1, ||B||1=1.2, ||B||2=1.043, ||B||F=(1.54)1/2, 但由于?(B)=0.9<1,故由此迭代法产生的迭代序列 {x(k)}是收敛的.

上页

下页

下面考察迭代法(1.11)式的收敛速度. 假定迭代法 (1.11)式是收敛的, 即?(B)<1, 由?(k)=Bk?(0), ?(0)=x(0)-x*, 得 ? ( k ) ? B k ? ( 0 ) , ?? ( 0 ) ? 0. 于是
? (k ) ? (0)
? Bk .

根据矩阵从属范数定义,有
B k ? max (0)
?

B k? (0)

?0

?

(0)

? max (0)
?

? (k ) ?
(0)

?0

.

上页

下页

所以||Bk||是迭代k次后误差向量?(k)的范数与初始误差 向量?(0)的范数之比的最大值. 这样,迭代k次后,平 均每次迭代误差向量范数的压缩率可看成是||Bk||1/k, 若要求迭代k次后有 ? (k ) ? Bk ? ? . ? ( k ) ? ? ? (0) , 即 ? (0) 其中σ<<1,可取σ=10-s. 因为?(B)<1, 故||Bk||1/k<1, 由 ||Bk||1/k<σ1/k两边取对数得
1 ln B ? ln ? . k ? ln ? s ln 10 k? ? . 1 1 ? ln B k k ? ln B k k
1 k k



(1.12)

它表明迭代次数k与-ln||Bk||1/k成反比.
上页 下页

定义4 迭代法(1.11)式的平均收敛速度定义为
Rk ( B) ? ? ln B
1 k k

.

(1.13)

平均收敛速度Rk(B)依赖于迭代次数及所取范数,给 计算分析带来不便,由定理4可知lim||Bk||1/k=?(B), 所以lim Rk(B)=-ln?(B). 定义5 迭代法(1.11)式的渐近收敛速度定义为 R( B) ? ? ln ? ( B). (1.14) R(B)与迭代次数及矩阵B取何种范数无关,它反映了 迭代次数趋于无穷时迭代法的渐近性质,当?(B)越 小-ln?(B)越大,迭代法收敛越快,可用 ? ln ? s ln 10
k? R( B ) ? R( B ) . (1.15)

作为迭代法(1.11)式所需的迭代次数估计.
上页 下页

例如在例1中迭代法(1.4)式的迭代矩阵B0的谱半 径?(B0)=0.3592. 若要求
? (k ) ? (0)
? 10 ? 5 ,

则由(1.13)式知
R( B0 ) ? ? ln ? ( B0 ) ? 1.023876,

于是有
s ln 10 5 ? ln 10 k? ? ? 11.99, R( B0 ) 1.023876

即取k=12即可达到要求.
上页 下页

6.2 雅可比迭代法与高斯-塞德尔迭代法
6.2.1 雅可比迭代法 将线性方程组(1.1)中的系数矩阵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?

( 2.1)
上页 下页



A=D-L-U

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

a12 ? a1n ? a22 ? a2 n ? ? ? ? ? an 2 ? ann ? ? ? ? ? ? ? 0? ?

? a11 ? D?? ? ? ?

a22

? ? ? ? ? ann ? ?

0 ? an 2

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

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

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

( 2.2)

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

上页

下页

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

x

( k ?1)

? D (L ?U)x

?1

(k)

?D b
a1n ? ? ? ? a11 ? a2 n ? ? ? a22 ? ? ? ? ? 0 ? ? ?
上页 下页

?1

其Jacobi迭代矩阵为

? 0 ? ? ? ? a21 ?1 J ? D ( L ? U ) ? ? a22 ? ? ? ? ? an1 ? a ? nn

a12 ? a11 0 ? an 2 ? ann

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

x

(k )

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

由雅可比迭代法(2.2)有

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
上页 下页

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

? ? x1 ? ? x2 ? ? ? ? xn ?

1 ? [ ? a12 x2 ? ? ? a1n xn ? b1 ] a11 1 ? [? a21 x1 ? ? ? ? a2 n xn ? b2 ] a22 ? 1 ? [? an1 x1 ? an 2 x2 ? ? ? bn ] ann

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

上页

下页

建立的雅可比迭代格式为

? ( k ? 1) 1 (k) (k) (k) ? ( ? a12 x2 ? a13 x3 ? ? ? a1n xn ? b1 ) ? x1 a11 ? ? x ( k ? 1) ? 1 ( ? a x ( k ) ( ( ? a23 x3k ) ? ? ? a2 n xnk ) ? b2 ) ? 2 21 1 a22 ? ? ? ? ? x ( k ? 1) ? 1 ( ? a x ( k ) ? ? ? a (k) ? bn ) n n1 1 n n ? 1 xn ? 1 ? ann ?

上页

下页

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

? (0) ( ( x ? ( x10 ) , ? , x n0 ) )T , ? n ? ? ( k ?1) (k ) ? (bi ? ? a ij x j ) / a ii , ? xi j ?1 ? j?i ? ?( i ? 1,2, ? , n) ( k ? 0,1, ? 表示迭代次数). ?

( 2.3)

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

6.2.2 高斯-塞德尔迭代法 在 Jacobi 迭代中,计算 xi(k+1)(2? i ?n)时,使用
xj(k+1)代替xj(k) (1? j ? i-1),即有

建 立 迭 代 格 式

? ( k ?1 ) 1 x 1 ? ( ? a 12 x (2k ) ? a 13 x (3k ) ? ? ? a 1n x (nk ) ? b1 ) ? a 11 ? ? x ( k ? 1 ) ? 1 ( ? a x ( k ?1 ) ? a x ( k ) ? ? ? a x ( k ) ? b ) 21 1 23 3 2n n 2 ? 2 a 22 ? ? ? ? ? x ( k ? 1 ) ? 1 ( ? a x ( k ? 1 ) ? ? ? a x ( k ?1 ) ? bn ) n n1 1 n n ?1 n ? 1 ? a nn ?
上页 下页

或缩写为
n 1 i ?1 ( k ?1) ( k ?1) (k ) xi ? (? ? aij x j ? ? aij x j ? bi ) (i ? 1,2,?, n). aii j ?1 j ? i ?1

称为高斯-塞德尔(Gauss-Seidel)迭代法.

于是高斯-塞德尔迭代法可写为矩阵形式
x ( k ?1) ? ( D ? L) ?1Ux ( k ) ? ( D ? L) ?1 b

其Gauss-Seidel迭代矩阵为
G = (D-L)-1U
上页 下页

这就是说,选取分裂矩阵M为A的下三角部分,
即选取M= D-L(下三角阵),A=M-N,由(2.3)式得到 解Ax=b的高斯-塞德尔(Gauss-Seidel)迭代法.

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

( 2.4)

其中B=I-(D-L)-1A= (D-L)-1U≡G, f=(D-L)-1b. 称矩

阵G=(D-L)-1U为解Ax=b的高斯-塞德尔迭代法的迭
代矩阵.

上页

下页

由高斯-塞德尔迭代法(2.4)有

( D ? L) x ( k ?1) ? Ux( k ) ? b,


Dx

( k ?1)

? Lx

( k ?1)

? Ux
n

(k )

? b,

每一个分量写出来为

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

i ?1

j ? i ?1

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

即当aii?0时,有(与前面一样的式子)
i ?1 n 1 ( k ?1) ( k ?1) (k ) xi ? (bi ? ? aij x j ? ? aij x j ) ( i ? 1,2,?, n). aii j ?1 j ? i ?1
上页 下页

于是,解Ax=b的高斯-塞德尔迭代法的计算公式为
( ( ? x ( 0 ) ? ( x10 ) ,? , xn0 ) )T (初始向量), ? i ?1 n ? ( k ?1) xi ? (bi ? ? aij x (jk ?1) ? ? aij x (jk ) ) / aii , ? j ?1 j ? i ?1 ? ?( i ? 1,2,? , n) ( k ? 0,1,? 表示迭代次数). ? ( ( ? x ( 0 ) ? ( x10 ) ,? , x n0 ) )T , 或 ? ( k ?1) xi ? x i( k ) ? ?x i , ? ? i ?1 n ? ?x i ? (bi ? ? a ij x (jk ?1) ? ? a ij x (jk ) ) / a ii , ? j ?1 j?i ? ?( i ? 1,2,? , n) ( k ? 0,1,? ). ?

( 2.5)

( 2.6)

上页

下页

雅可比迭代法不使用变量的最新信息计算xi(k+1), 而由高斯-塞德尔迭代公式(2.6)可知,计算x(k+1)的第 i个分量xi(k+1)时,利用了已经计算出的最新分量xj(k+1) (j=1,2,?,i-1). 可看作雅可比迭代法的一种改进. 由 (2.6)可知,高斯—塞德尔迭代公式每迭代一次只需 计算一次矩阵与向量的乘法.

上页

下页

算法(高斯-塞德尔迭代法) 设Ax=b, 其中A∈Rn×n
为非奇异矩阵,且aii? 0(i=1,2, …,n),本算法用高斯-

塞德尔迭代法解Ax=b,数组x(n)开始存放x(0),后存
放x(k),N0为最大迭代次数. 1. xi←0.0 (i=1,2, …,n) 2. 对于k=1,2, …,N0, 对于i=1,2, …,n

xi ? (bi ? ? aij x j ?
j ?1

i ?1

j ? i ?1

?a

n

ij

x j ) / aii

迭代一次,这个算法需要运算次数至多与矩阵A的非 零元素的个数一样多.
上页 下页

例6 用高斯-塞德尔迭代法解线性方程组(1.2). 解 用高斯-塞德尔迭代公式:取x(0)=(0, 0, 0)T.
( (k ) (k ) ? x1k ?1) ? ( 20 ? 3 x 2 ? 2 x3 ) / 8, ? ( k ?1) ( ( x2 ? ( 33 ? 4 x1k ?1) ? x3k ) ) / 11, ? ? ( k ?1) ( ( x3 ? ( 36 ? 6 x1k ?1) ? 3 x 2k ?1) ) / 12. ? ( k ? 0,1,2,?).

迭代到第7次有

x ( 7 ) ? (3.000002, 1.9999987, 0.9999930)T ;

?

(7) ?

? x ?x

?

(7) ?

? 2.02 ? 10 .
上页 下页

?4

由此例可知,用高斯-塞德尔迭代法,雅可比 迭代法解线性方程组(1.2)(且取x(0)=0)均收敛,而高 斯-塞德尔迭代法比雅可比迭代法收敛较快(即取相 同的x(0),达到同样精度所需迭代次数较少),但这结 论只当A满足一定条件时才是对的.

上页

下页

例1 用雅可比迭代法解方程组

?10 x1 ? x2 ? 2 x3 ? 7.2 ? ? ? x1 ? 10 x2 ? 2 x3 ? 8.3 ? ? x ? x ? 5 x ? 4.2 ? 1 2 3
解: Jacobi 迭代格式为

精 ? 1.1 ? ? ? ? 确 x ? ? 1.2 ?. ? 1.3 ? 解 ? ?

? ( k ?1 ) 1 ( ( x1 ? ( x2k ) ? 2 x3k ) ? 7.2) ? 10 ? ? ( k ?1 ) 1 (k) (k) ? ( x1 ? 2 x3 ? 8.3) ? x2 10 ? ? ( k ?1 ) 1 ( k ) (k) ? ( x1 ? x2 ? 4.2) ? x3 5 ?
上页 下页

? ( k ?1 ) 1 ( ( x1 ? ( x2k ) ? 2 x3k ) ? 7.2) ? 10 ? ? ( k ?1 ) 1 ( k ) ( ? ( x1 ? 2 x3k ) ? 8.3) ? x2 10 ? ? ( k ?1 ) 1 ( k ) ( x3 ? ( x1 ? x2k ) ? 4.2) ? 5 ?

取 x(0)=(0,0,0)T 计算结果如下: k x1(k) x2(k) x3(k) 1 0.72 0.83 0.84 2 0.971 1.07 1.15 … … … … 11 1.099993 1.199993 1.299991 12 1.099998 1.199998 1.299997
上页 下页

例2 用Gauss-Seidel 迭代法解上题.

?10 x1 ? x2 ? 2 x3 ? 7.2 ? ? ? x1 ? 10 x2 ? 2 x3 ? 8.3 ? ? x ? x ? 5 x ? 4.2 ? 1 2 3
解:Gauss-Seidel 迭代格式为

? ( k ?1 ) 1 ( ( x1 ? ( x2k ) ? 2 x3k ) ? 7.2) ? 10 ? ? ( k ?1 ) 1 ( k ?1 ) (k) ? ( x1 ? 2 x3 ? 8.3) ? x2 10 ? ? ( k ?1 ) 1 ( k ?1 ) ( k ?1 ) ? ( x1 ? x2 ? 4.2) ? x3 5 ?
上页 下页

? ( k ?1 ) 1 ( ( x1 ? ( x2k ) ? 2 x3k ) ? 7.2) ? 10 ? ? ( k ?1 ) 1 ( k ?1 ) ( x2 ? ( x1 ? 2 x3k ) ? 8.3) ? 10 ? ? ( k ?1 ) 1 ( k ?1 ) ( k ?1 ) ? ( x1 ? x2 ? 4.2) ? x3 5 ? 取 x(0)=(0,0,0)T 计算结果如下:
k 1 … x1(k) 0.72 … x2(k) 0.902 … x3(k) 1.1644 …

8

1.099998

1.199999

1.3
上页 下页

6.2.3 雅可比迭代与高斯-塞德尔迭代收敛性
由定理5可立即得到以下结论. 定理7 设Ax=b,其中A=D-L-U为非奇异矩阵,且 对角矩阵D也奇异,则

(1) 解线性方程组的雅可比迭代法收敛的充要条
件是?(J)<1,其中J=D-1(L+U).

(2) 解线性方程组的高斯-塞德尔迭代法收敛的充
要条件是?(G)<1,其中G=(D-L)-1U.

由定理6还可得到雅可比迭代法收敛的充分条件是
||J||<1. 高斯-塞德尔迭代法收敛的充分条件是||G||<1.
上页 下页

在科学及工程计算中,要求解线性方程组Ax=b,
其矩阵A常常具有某些特性. 例如,A具有对角占优性

质或A为不可约矩阵,或A是对称正定矩阵等,下面
讨论解这些方程组的收敛性.

上页

下页

定义6(对角占优阵) 设A=(aij)n×n .

(1) 如果A的元素满足

aii ? ? aij
j ?1 j?i

n

( i ? 1,2,? , n).

称A为严格(按行)对角占优阵. (2) 如果A的元素满足

aii ? ? aij
j ?1 j?i

n

( i ? 1,2,? , n).

且上式至少有一个不等式成立,称A为弱(按行)对角 占优阵.
上页 下页

定义7(可约与不可约矩阵) 设A=(aij)n×n (n≥2), 如果存在置换阵P使 ? A11 A12 ? T P AP ? ? ( 2.7) ? 0 A ?, ? 22 ? ? 其中A11为r阶方阵,A22为n-r阶方阵(1≤r<n),则称A 为可约矩阵. 否则,如果不存在这样置换阵P使(2.7) 式成立,则称A为不可约矩阵. A为可约矩阵意即A可经过若干行列重排化为(2.7) 或Ax=b可化为两个低阶方程组求解(如果A经过两行 交换的同时进行相应两列的交换,称对A进行一次行 列重排).
上页 下页

事实上,由Ax=b可化为 PTAP(PTx)=PTb.
? y1 ? ? d1 ? T 且记 y ? P x ? ? ?, d ? P b ? ? ? ,其中yi, di为r维向量. ?y ? ?d ? ? 2? ? 2?
T

于是,求解Ax=b化为求解

? A11 y1 ? A12 y2 ? d1 , ? A22 y2 ? d 2 . ?
由上式第2个方程组求出y2,再代入第1个方程组求出y1.

显然,如果A所有元素都非零,则A为不可约阵.
上页 下页

例7 设有矩阵

? b1 c1 ? ? ? ? 4 ?1 ?1 0 ? ? ? ? a 2 b2 c2 ? 0 ? 1? ? ?, B ? ? ? 1 4 ? ? ? A? ??1 0 ?. ? ? 4 ?1 ? ? an?1 bn?1 cn?1 ? ? ? 0 ?1 ?1 4 ? ? ? ? ? an bn ? ? (ai , bi , ci 都不为零)
则A, B都是不可约矩阵.

上页

下页

定理8(对角占优定理) 如果A=(aij)n×n为严格对 角占优矩阵或A为不可约弱对角占优矩阵,则A为非 奇异矩阵. 证明 只就A为严格对角占优矩阵证明此定理. 采用反证法,假设det(A)=0,则Ax=0有非零解,记 为x=(x1, x2,?,xn)T,则 xk ? max xi ? 0 .
1? x ? n n
j ?1

由齐次方程组第k个方程
n n

?a
n

kj

x j ? 0, 及条件
n

则有 akk xk ?| ? akj x j |? ? akj x j ? xk ? akj , 即 a kk ? ? a kj ,
j ?1 j?k j ?1 j?k j ?1 j?k

这与假设矛盾,故det(A)≠0.

j ?1 j?k

上页

下页

定理9 设方程组Ax=b,如果 (1) A为严格对角占优阵,则解Ax=b的Jacobi迭 代法, Gauss-Seidel 迭代法均收敛. (2) A为弱对角占优阵,且A为不可约矩阵, 则解 Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收敛. 证明 只证(1),(2)作为练习. 因为A是严格对角占优阵,所以aii≠0(i=1,?,n).
a12 ? a11 0 ? a ? n2 a nn ? ? ? ? a1n ? ? ? a11 ? a ? ? 2n ? a 22 ? ? ? 0 ? ? ?

? ? 0 Jacobi迭代阵 ? ? a 21 ?1 J ? D ( L ? U ) ? ? ? a22 ? ? ? ? ? a n1 ? a ? nn

则||J||?<1,所以 Jacobi 迭代法收敛.

上页

下页

下面证明Gauss—Seidel 迭代法收敛.

由G=(D-L)-1U,得

det(? I ? G ) ? det[? I ? ( D ? L)?1U ] ?1 ? det[( D ? L) ]det[? ( D ? L) ? U ] ? 0. ?1 由于 det[( D ? L) ] ? 0.
所以

det[? ( D ? L) ? U ] ? 0.
i ?1

(?)
n

下面证明|?|<1. 若不然, 即|?|?1, 则

| ? aii |? ? | ? aij |? ? | ? aij | ?
j?i j ?1

j ? i ?1

?| a

ij

| (i ? 1,2,?, n).

上页

下页

| ? aii |? ? | ? aij |? ? | ? aij | ?
j?i j ?1

i ?1

j ? i ?1

?| a
a12

n

ij

| (i ? 1,2,?, n).

即矩阵

? ? a11 ? ? ? a21 ? ( D ? L) ? U ? ? ? ? ?? a ? n1

? a22
?

? an 2

a1n ? ? ? a2 n ? ?. ? ? ? ? ? ann ? ? ?

是严格对角占优矩阵,故可逆,这与(*) 式矛盾,所
以|?|<1, 从而 ?(G)<1,即Gauss—Seidel迭代法收敛.

上页

下页

如果线性方程组系数矩阵A对称正定,则有以下 的收敛定理. 定理10 设矩阵A对称, 且所有对角元素aii>0, 则 (1) 解线性方程组Ax=b的Jacobi迭代法收敛的充 分条件是A及2D-A均为正定矩阵, 其中D=(a11,…,ann). (2) 解线性方程组Ax=b的Gauss-Seidel 迭代法 收敛的充分条件是A正定. 定理证明可见文献[2],其中第(2)部分为下面定 理12的一部分. 定理表明若A对称正定,则高斯-塞 德尔法一定收敛,但雅可比法不一定收敛.
上页 下页

我们这里给出(2)的证明. 证 因为A对称,则A=D-L-LT,G=(D-L)-1LT,设 ?为迭代矩阵G =(D-L)-1LT的特征值,y为G 的对应?的 特征(复)向量,即有
(D-L)-1LTy=?y,LTy=?(D-L)y, 则内积 从而解得 (LTy, y)=?((D-L)y, y).

( LT y, y ) ?? . ( Dy, y ) ? ( Ly, y )
因为A正定,所以D也正定,故记(Dy, y)=?>0.
上页 下页

令 -(Ly, y)=a+ib,则由复向量内积的性质有

( L y, y ) ? ( y, Ly) ? ( Ly, y ) ? ?(a ? ib).
T

( L y, y ) ? a ? ib ?? ? . ( Dy, y ) ? ( Ly, y ) (? ? a ) ? ib
T

a ?b |? | ? ?1 2 2 (? ? a ) ? b 所以|?|<1, 从而?(G)<1, 故Gauss-Seidel迭代法收敛.
2 2 2

上页

下页

例8 在线性方程组Ax=b中,

?1 a a? ? ? A ? ? a 1 a ?, ?a a 1? ? ?
证明当-1/2<a<1时高斯-塞德尔法收敛,而雅可比法 只在-1/2<a<1/2时才收敛. 证明 因为当-1/2<a<1时,得A的顺序主子式

1 a ? 1 ? 1 ? 0, ? 2 ? ? 1 ? a 2 ? 0, a 1 ? 3 ? det A ? 1 ? 2a 2 ? 3a 3 ? (1 ? a )2 (1 ? 2a ) ? 0.
故A正定,所以高斯-赛德尔法收敛.
上页 下页

对雅可比法迭代矩阵



? 0 ?a ?a ? ? ? J ? D ?1 ( L ? U ) ? ? ? a 0 ? a ? , ? ?a ?a 0 ? ? ?
3 2 2 2

det(? I ? J ) ? ? ? 3? a ? 2a ? (? ? a ) (? ? 2a ) ? 0,
当?(J)=|2a|<1,即|a|<1/2时雅可比法收敛. 例如,当a=0.8时高斯-塞德尔收敛,而 ?(J)=1.6>1,雅可比不收敛,此时2D-A不是正定的.

上页

下页

注意,求线性方程组Ax=b时,如原线性方程组 换行后A满足收敛条件,则应将方程换行后再构造雅 可比迭代法及高斯迭代法. 例如,线性方程组

可换成

? 3 x1 ? 10 x2 ? ?7, ? ? 9 x1 ? 4 x2 ? 5. ? 9 x1 ? 4 x2 ? 5, ? ? 3 x1 ? 10 x2 ? ?7.

? 3 ?10 ? ? ? ? 9 ?4 ? . 即将 A ? ? ? 换成 A ? ? 9 ?4 ? 3 ?10 ? ? ?

? ? ? 显然 A 是严格对角占优矩阵, 对新线性方程组 Ax ? b 构造雅可比迭代法及高斯-塞德尔迭代法均收敛.
上页 下页

例如 已知方程组

?0.5 0 ? ? x1 ? ? 0.7 ? ? 1 ? ?? ? ? ? Ax ? ? ?0.5 1 ?0.5 ? ? x2 ? ? ? 0.8 ? ? b. ? 0 ?0.5 1 ? ? x3 ? ? 0.9 ? ? ?? ? ? ?
判断雅可比迭代法和高斯—塞德尔法的敛散性? 解 因为A的顺序主子式 1 ?05 ? 1 ? 1 ? 0, ? 2 ? ? 0.75 ? 0, ?0.5 1

? 3 ? 0.75 ? 0.25 ? 0.5 ? 0.
所以A是正定矩阵.
上页 下页

又由于

? 1 0.5 0 ? ? ? 2 D ? A ? 2 I ? A ? ? 0.5 1 0.5 ? . ? 0 0.5 1 ? ? ?
也是正定矩阵,故由定理10的(1)知,Jacobi 迭代法 收敛. 再由定理10的(2)充分条件,及利用上面的讨论

结果A是对称正定矩阵,故 Gauss—Seidel迭代法也
收敛.

上页

下页

6.3 超松弛迭代法
6.3.1 逐次超松弛迭代法
选取分裂矩阵M为带参数的下三角矩阵

M?

1

其中?>0为可选择的松弛因子. 于是, 由(1.11)可构造一个迭代法, 其迭代矩阵为 L? ? I ? ? ( D ? ? L)?1 A

?

( D ? ?L).

? ( D ? ? L) [(1 ? ? ) D ? ? U ]. 从而得到解Ax=b的逐次超松弛迭代法 (Successive Over Relaxation Method,简称SOR方法).
?1

上页

下页

解Ax=b的SOR方法为.

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

(3.1)

其中 L? ? ( D ? ? L)?1[(1 ? ? ) D ? ? U ], f ? ? ( D ? ? L)?1 b. 下面给出解Ax=b的SOR方法的分量计算公式. 记
( ( x ( k ) ? ( x1k ) ,?, xi( k ) ,?, xnk ) )T ,

由(3.1)式可得

( D ? ?L) x

( k ?1)

? [(1 ? ? ) D ? ? U ]x

(k )

? ?b,

或 Dx( k ?1) ? Dx( k ) ? ? (b ? Lx ( k ?1) ? Ux( k ) ? Dx( k ) ).
上页 下页

由此,得到解Ax=b的SOR方法的计算公式
(0) (0) ? x (0) ? ( x1 ,? , xn )T , ? i ?1 n ? ( k ?1) xi ? (1 ? ? ) xi( k ) ? ? (bi ? ? aij x (jk ?1) ? ? aij x (jk ) ) / aii ? j ?1 j?i ? ?( i ? 1, 2,? , n; k ? 0,1, 2,?), ? 松弛因子. ?

(3.2)



(0) (0) ? x (0) ? ( x1 ,? , xn )T , ? ( k ?1) xi ? xi( k ) ? ?xi , ? ? i ?1 n ? ( k ? 1) (k ) ? ?xi ? ? (bi ? ? aij x j ? ? aij x j ) / aii j ?1 j?i ? ?( i ? 1, 2,? , n; k ? 0,1, 2,?), ? 松弛因子. ?

(3.3)

上页

下页

(1) 显然,当?=1时即为Gauss—Seidel 迭代法. (2) SOR方法每迭代一次主要运算量是计算一次 矩阵与向量的乘法.

(3) 当?>1时,称为超松弛法;当?<1时,称为低 松弛法. (4) 在计算机实现时可用

max ?xi ? max xi( k ?1) ? xi( k ) ? ?
1? i ? n 1? i ? n

控制迭代终止,或用

r (k )
控制迭代终止.

?

? b ? Ax ( k )

?

??

上页

下页

SOR迭代法是Gauss—Seidel 迭代法的一种修正, 可由下述思想得到. 设已知x(k)及已计算x(k+1)的分量xj(k+1) (j=1,2,?,i-1).

~ (1) 首先用Gauss—Seidel 迭代法定义辅助量 xi( k ?1),
? i( k ?1) ? (bi ? ? aij x (jk ?1) ? x
j ?1 i ?1 j ? i ?1

?a

n

ij

x ) / aii .

(k ) j

(3.4)

~ ( k ?1) 加权平均定义 x ( k ?1) ,即 (2) 再由 x 与 xi i
(k ) i

? ? xi( k ?1) ? (1 ? ? ) xi( k ) ? ? xi( k ?1) ? xi( k ) ? ? ( xi( k ?1) ? xi( k ) ). (3.5)
将(3.4)代入(3.5)得到解Ax=b的SOR迭代(3.2)式.

上页

下页

例9 用SOR方法解线性方程组Ax=b
? ?4 1 1 1 ? ? x1 ? ? 1 ? ? ?? ? ? ? 1 ?4 1 1 ? ? x 2 ? ? 1 ? ? ? . ? 1 1 ?4 1 ? ? x 3 ? ? 1 ? ? ?? ? ? ? ? 1 1 1 ?4 ? ? x 4 ? ? 1 ?

它的精确解为x*=(-1, -1, -1, -1 )T. 解 取初始向量x(0)=0,迭代公式为
( ? x1k ?1) ? ( k ?1) ? x2 ? ( k ?1) ? x3 ? x ( k ?1) ? 4 ( ( ( ( ( ? x1k ) ? ? (1 ? 4 x1k ) ? x2k ) ? x3k ) ? x4k ) ) / 4, ( ( ( ( ( ? x2k ) ? ? (1 ? x1k ) ? 4 x2k ) ? x3k ) ? x4k ) ) / 4, ( ( ( ( ( ? x3k ) ? ? (1 ? x1k ) ? x2k ) ? 4 x3k ) ? x4k ) ) / 4, ( ( ( ( ( ? x4k ) ? ? (1 ? x1k ) ? x2k ) ? x3k ) ? 4 x4k ) ) / 4.

上页

下页

取?=1.3,第11次迭代结果为
x(11) ? (?0.99999646, 1.00000310, 0.99999953, 0.9999 ? ? ? 9912) T,
满足误差
? (k )
? 10?5 .

? (11)

2

? 0.46 ? 5. 10 ?

?
1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9

2

对?取其它值,迭代次数如表. 从此例看到,松弛因子选择 得好,会使SOR迭代法的收 敛大大加速. 本例中?=1.3是 最佳松弛因子.

迭代次数k 22 17 12 11(最少迭代次数) 14 17 23 33 53 109
上页 下页

6.3.2 SOR迭代法的收敛性
根据定理5可知SOR迭代法收敛的充分必要条件 是?(L?)<1,而?(L?)与松弛因子?有关,下面先研究? 在什么范围内, SOR迭代法才可能收敛. 定理11(SOR方法收敛的必要条件) 设解方程组 Ax=b的SOR迭代法收敛,则0<?<2.

证明 A=D-L-U,L?=(D-?L)-1[(1-?)D +?U], 由 于SOR迭代法收敛,则?(L?)<1. 设迭代矩阵L?的特征 值为?i (i=1,?,n), 则有|det(L?)|=|?1?2??n|≤[?(B? )]n<1. det( L? ) ? det[( D ? ? L)?1 ] ? det[(1 ? ? ) D ? ? U ] 即
? (? aii )?1 [? (1 ? ? )aii ] ? (1 ? ? )n ? 1. (3.6)
n n i ?1 i ?1

所以|1-?|<1,即 0<?<2.
上页 下页

定理11说明解Ax=b的SOR迭代法,只有在(0, 2) 范围内取松弛因子?,才可能收敛.

定理12(SOR方法收敛的充分条件) 设有方程组 Ax=b,如果:
(1) A为对称正定矩阵,A=D-L-LT;

(2) 0<?<2.
则解方程组 Ax=b的SOR迭代法收敛. 证明 在上述假定下,设迭代矩阵L?的任一特征 值为?,只要证明|?|<1即可.
上页 下页

事实上,设y为对应?的Lω的特征向量,即

L? y ? ?y, y ? ( y1 , y2 ,?, yn )T ? 0,
亦即

( D ? ?L) ((1 ? ? ) D ? ?L ) y ? ?y, ((1 ? ? ) D ? ?LT ) y ? ? ( D ? ?L) y.
?1 T T

有内积 (((1 ? ? ) D ? ?L ) y, y ) ? ? (( D ? ?L) y, y ), 则

( Dy, y ) ? ? ( Dy, y ) ? ? ( LT y, y ) ?? , ( Dy, y ) ? ? ( Ly, y )
(3.7)

因为A正定,所以D正定,记(Dy, y)=?>0.
令 -(Ly, y)=a+ib,则由复向量内积的性质有

( L y, y ) ? ( y, Ly) ? ( Ly, y ) ? ?(a ? ib).
T
上页 下页

? 0 ? ( Ay, y ) ? (( D ? L ? LT ) y, y ) ? ? ? 2a, (3.8)

?

( Dy, y ) ? ? ( Dy, y ) ? ? ( LT y, y ) ?? , ( Dy, y ) ? ? ( Ly, y ) (? ? ?? ? a? ) ? i?b ? . (? ? a? ) ? i?b (? ? ?? ? a? )2 ? ? 2b 2 2 ? ? . 2 2 2 (? ? a? ) ? ? b
当0<?<2时,有(分子减分母)

(? ? ?? ? a? )2 ? (? ? a? )2 ? ?? (? ? 2a )(? ? 2) ? 0.
即L?的任一特征值满足|?|<1, 故SOR迭代法收敛.
上页 下页

定理13 设有方程组 Ax=b,如果: (1) A为严格对角占优矩阵(或A为弱对角占优不可 约矩阵); (2) 0<??1. 则解方程组 Ax=b的SOR迭代法收敛. (不证明)

SOR迭代法的收敛速度与松弛因子?有关,例9 中也看到不同?的迭代次数差别. 对于SOR迭代法希望选择松弛因子?使迭代过程 (3.1)式收敛较快,在理论上即确定?opt使
0 ?? ? 2

min ? ( L? ) ? ? ( L?opt ).
上页 下页

对某些特殊类型的矩阵,建立了SOR方法最佳松 弛因子理论. 例如,对所谓具有“性质A”等条件的 线性方程组建立了最佳松弛因子公式

?opt ?

2 1 ? 1 ? ( ? ( J ))2

,

(3.9)

其中?(J) 为解 Ax=b 的雅可比迭代法的迭代矩阵的谱 半径. 由于 6.3.3 块迭代法 及 6.4 共轭梯度法 是解线性方程组的应用,大家自学. 评 注 见书p208页.
上页 下页


相关文章:
第6章解线性方程组的迭代法_图文.ppt
第6章解线性方程组的迭代法_数学_自然科学_专业资料。第6章解线性方程组的迭代法,解线性方程组的迭代法,迭代法解线性方程组,高斯迭代法解线性方程组,超松弛迭代...
第六章求解线性方程组的迭代法_图文.ppt
第六章求解线性方程组的迭代法 - 哈尔滨工程大学数值逼近与数值代数 第6章 求解线性方程组的迭代法 §1 引言 考虑线性方程组 ? a11x1 ? a12 x2...
数值分析 第6章 解线性方程组的迭代法_图文.ppt
数理学院 SCHOOL OF MATHEMATICS AND PHYSICS 第6章 解线性方程组的迭代法 6 .1 引言 6 .2 Jacobi迭代 6 .3 Gauss-Seidel迭代 6.4 超松弛迭代法(SOR) §6...
第6章 解线性方程组的迭代法_图文.ppt
第6章 解线性方程组的迭代法 - 数学系 University of Scien
数值分析第6章 解线性方程组的迭代法_图文.ppt
数值分析第6章 解线性方程组的迭代法_理学_高等教育_教育专区。数值分析课件 第6 章 解线性代数方程组的迭代法§1 引言 考虑线性方程组 ? a11x1 ? a12 x2 ...
第六章 解线性方程组的迭代法_图文.ppt
第六章 解线性方程组的迭代法 - 第七章 非线性方程求根 7.1 方程求根与二分
数值分析 第六章 解线性方程组的迭代法_图文.ppt
郑州大学研究生课程 (2011-2012学年第一学期) 数值分析 Numerical Analysis 10 第六章 解线性代数方程组的迭代法 5 0 -10 -5 0 5 10 -10 -5 5 0 第...
数值分析ppt第6章_解线性方程组的迭代法_图文.ppt
数值分析ppt第6章_解线性方程组的迭代法 - 第 6章 ? 6.1 引言 解线
数值分析ppt第6章 解线性方程组的迭代法_图文.ppt
数值分析ppt第6章 解线性方程组的迭代法_生产/经营管理_经管营销_专业资料。数值分析ppt第6章 解线性方程组的迭代法 第6章 ? 6.1 引言 解线性方程组的迭代...
第六章 解线性方程组的迭代法 - 图文 - 百度文库.ppt
第六章 解线性方程组的迭代法 - 第七章 非线性方程求根 7.1 方程求根与二分
第6章解线性方程组的迭代法_图文.ppt
第6章解线性方程组的迭代法 - 数学系 University of Scienc
第6章 解线性方程组的迭代法_图文.ppt
第6章 解线性方程组的迭代法 - 数学系 University of Scien
第六章解线性方程组的迭代法_图文.ppt
第六章解线性方程组的迭代法 - 第6章 解线性方程组的迭代法 6.1 雅可比迭代
解线性方程组的迭代法_图文.ppt
解线性方程组的迭代法 - 第6章 解线性方程组的迭代法 §6.1 迭代法的基本概
第六章求解线性方程组的迭代法_图文.ppt
第六章求解线性方程组的迭代法 - 哈尔滨工程大学数值逼近与数值代数 第6章 求解线性方程组的迭代法 §1 引言 考虑线性方程组 ? a11x1 ? a12 x2...
第6章 解线性方程组的迭代法_图文.ppt
第6章 解线性方程组的迭代法 - 第6章 解线性方程组的迭代法 6.1 引言 考
第6章 解线性方程组的迭代法_图文.ppt
第6章 解线性方程组的迭代法_经济学_高等教育_教育专区。第6 章 解线性代数方
第六章 解线性方程组的迭代法-1_图文.ppt
第6章 解线性方程组的迭代法 1 6.1 6.2 6.3 迭代法的基本概念 Ja
...课程数值分析复习---第六章 解线性方程组的迭代法_图文.pdf
郑州大学研究生课程数值分析复习---第六章 解线性方程组的迭代法_理学_高等教育
第6章线性方程组迭代法讲诉_图文.ppt
第6章线性方程组迭代法讲诉 - 第六章 解线性方程组的迭代法 1. 雅可比(Ja