§ 4 迭代法的收敛性 /* Convergence of Iterative methods */
的收敛条件 fxBx kk ??? ??? )()1(
*)1()1( xxe kk ??? ?? ?? )()()( *)()*()( kkk eBxxBfxBfxB ??????? ???????
)0()( eBe kk ?? ? ||||||||...|||||||||||| )0()1()( eBeBe kkk ??? ?????? ?
充分条件, ||B|| < 1 ???? kB k as0||||
0|||| )( ?? ke?
必要条件, kk Bke ???? as0)( ??？
定义 设,
.)(,)( )( nnnnkijknnij RaAaA ??? ???
A A k
k
?
? ?lim 是指 ij
k
ij k a a ? ? ?
) ( lim 对所有 1? i,j ? n 成立。
等价于对
任何算子范数有
???? kAA k as0||||
0|||| ?xB k ? 对 任意非零向量 成立 x?
§ 4 Convergence of Iterative methods
定理 设 fxBx ??? ?? 存在唯一解，则从任意 出发,)0(x?
迭代 fxBx kk ??? ??? )()1( 收敛 ? 0 ? k B
证明,Bk ? 0 || Bk || ? 0 0
||||
||||m a x
0
?
? x
xB k
x ?
?
??
“?”：对任意非零向量
有 x?
0|||||||| |||| ?? kk Bx xB ?
?
“?”：取
则
Tix )0...1...0()( ??
第 i 位 0)( ?kijb
0?? ?xB k 对 任意非零向量 成立 x?
从任意 出发,记,则 )0(x? *)0()0( xxe ??? ??
0)0()( ??? ?? eBe kk as k ? ?
}{ )(kx? 收敛
But hey,you don’t
seriously expect me to compute Bk
whenever I want to check
the convergence,do you?
§ 4 Convergence of Iterative methods
定理 Bk ? 0 ? ? ( B ) < 1
证明：,?” 若 ? 是 B 的 eigenvalue,则 ?k 是 Bk 的 eigenvalue 。
则 [? (B)]k = [ max | ? | ]k = | ?mk | ? ? ( Bk ) ? || Bk || ? 0
? ? (B) < 1 ?
“?” 首先需要一个引理 /* Lemma */
对任意 ? > 0,存在算子范数 || · || 使得 || A || ? ? (A) ? ? 。
由 ? (B) < 1 可知存在算子范数 || · || 使得 || B || < 1。
|| Bk || ? || B ||k ? 0 as k ? ? Bk ? 0
迭代从任意向量出发收敛 Bk ? 0 ? ( B ) < 1
证明,对 A 做 Jordan 分解，有,其中
,, ?i 为 A 的 eigen value。
令,则有
易证,
是由 导出的算子范数。
所以只要取 ? < ?,就有 || A ||? < ? (A) ? ? 。
?
?
?
?
?
?
?
?
?
?
??
rJ
J
APP,,,
1
1
inini
i
iJ
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
01
?
?
?r
i
i nn
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? 1
2
1
n
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
r
r
A P DPD
?
?
??
?
?
??
1
1
11
????? ????? ???? )()||(m a x|||||||| 1111 AA P DPDA iri
11 ||)(|||||| xPDx v ?? ??
§ 4 Convergence of Iterative methods
定理 （充分条件） 若存在一个矩阵范数使得 || B || = q < 1,
则 迭代收敛，且有下列误差估计,
①
||||1||*|| )1()()( ????? kkk xxqqxx ????
②
||||1||*|| )0()1()( xxqqxx
k
k ???? ?
???
证明,①
)*(
)*(*
)1()()(
)1()(
?
?
????
???
kkk
kk
xxxxB
xxBxx ???? ????
| | )||||*( | |||*|| )1()()()( ?????? kkkk xxxxqxx ?????? ?
② )(...)( )0()1(1)2()1()1()( xxBxxBxx kkkkk ?????? ?????? ????
|||||||| )0()1(1)1()( xxqxx kkk ???? ??? ??
§ 4 Convergence of Iterative methods
定理 （充分条件） 若 A 为 严格对角占优阵 /* strictly
diagonally dominant matrix */ 则解 的 Jacobi 和 Gauss -
Seidel 迭代均收敛。
bxA ?? ?
证明,首先需要一个引理 /* Lemma */
若 A 为 SDD阵，则 det(A) ? 0，且所有的 aii ? 0。
证明,若不然，即 det(A) = 0，则 A 是奇异阵。
存在非零向量 使得 T
nxxxx ),,( 210 ?? ?,00 ?? ?xA
记 ||m a x||
1 inim xx ??? ?
?
?n
i
iim xa
1
0
??
??
??
mi
imm
mi
iimmmm axxaxa ||||||
显然
我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别
证明：任何一个 | ? | ? 1 都 不可能 是对应迭代阵的
特征根，即 | ?I ? B | ? 0 。
Jacobi,BJ = ?D?1( L + U )
|)(||| 1 ULDIBI ???? ???
|||||)(| 11 ULDDULDD ?????? ?? ??
aii ? 0
ija
ija ?
?
?
?
?
?
?
?
?
?
nna
a
?
? 11
如果 | ? | ? 1 则 ?
?
??
ij ijiiii
aaa |||||| ? 是 SDD阵
| ?I ? B | ? 0 ?
HW,
p.76 #1
关于 Gauss-Seidel迭代的证明
与此类似 (p.73)。
另一种证明引理的方法利用
Ger?gorin Disc Theorem (p.72)。
§ 5 松弛法 /* Relaxation Methods */
换个角度看 Gauss - Seidel 方法,
??
??
?
?
?? ???
n
ij
k
jij
i
j
k
iiji
ii
k
i xaxabax
1
)(
1
1
)1()1( ][1
ii
k
ik
i a
rx )1()( ??? 其中 ri(k+1) = ? ?
< ?
? ??
ij ij
kjijkjiji xaxab )()1(
/* residual */
相当于在 的基础上 加个余项 生成 。 )(kix )1( ?kix
下面令,希望通过选取合适的 ? 来
加速收敛，这就是 松弛法 /* Relaxation Methods */ 。 ii
k
i k
i
k
i a
r x x ) 1 ( ) ( ) 1 ( ? ? ? ? ?
0 < ? < 1 低松弛法 /* Under- Relaxation methods */
? = 1 Gauss - Seidel 法
? > 1 (渐次 )超松弛法 /* Successive Over- Relaxation
methods */
§ 5 Relaxation Methods
写成 矩阵形式,
ii
k
ikiki arxx
)1()()1( ?? ?? ? ??
?<
? ??????
ij
i
k
jij
ij
k
jijii
k
i bxaxaax ][)1(
)()1()( ??
][)1( )()1(1)()1( bxUxLDxx kkkk ????? ?????? ??? ??
bLDxUDLDx kk ??? ????? 1)(1)1( )(])1[()( ??? ??????
?H f
?松弛迭代阵
定理 设 A 可逆，且 aii ? 0,松弛法从任意 出发对
某个 ? 收敛 ? ? ( H? ) < 1。
)0(x?
Oooooh come on!
It’s way too complicated to compute H?,
and you can’t expect me to get
its spectral radius right!
There’s gotta be a short cut …
§ 5 Relaxation Methods
定理 （ Kahan 必要条件） 设 A 可逆，且 aii ? 0,松弛法
从任意 出发收敛 ? 0 < ? < 2 。 )0(x?
证明,从 出发 ])1[()( 1 UDLDH ???
? ???? ?
?
?
?
n
i
iH
1
)de t ( ??
利用,而且收敛 ? | ?i | < 1 总成立
可知收敛 ? | det(H?) | < 1
?
?
? ?
???
n
i iiaLD
LD
1
1 1
)d e t (
1))d e t ( (
??
?
?
????
n
i
ii
n aUD
1
)1())1d e t ( ( ???
nH )1()d e t ( ?? ??
? | det(H?) | ? | 1 ? ? |n < 1 ? 0 < ? < 2
§ 5 Relaxation Methods
定理 （ Ostrowski-Reich 充分条件） 若 A 对称正定，且有
0 < ? < 2，则 松弛法从任意 出发收敛 。 )0(x?
Q,What factor determines the speed of convergence?
考察迭代 fxBx kk ??? ??? )()1(,设 B 有特征根 ?1,…, ?n 对
应 n 个线性无关的特征向量 。则从任意 出
发,可表为 的线性组合，即
n?? ??,...,1 )0(x
?
*)0()0( xxe ??? ?? n?? ??,...,1
?
?
?
n
i
iie
1
)0( ?? ?? ?
?
??
n
i
i
k
ii
kk eBe
1
)0()( ??? ???
~ )0()]([ eB k ??A,The smaller ? ( B ) is,the faster the iterations will converge,
对于 SOR法，希望找 ? 使得 ? ( H? ) 最小 。
§ 5 Relaxation Methods
定理 若 A 为 对称正定三对角阵,则
且 SOR的 最佳松弛因子 /* optimal choice of ? for SOR method */
为,此时 。
1)]([)( 2 <?? JSG BB ??
2)]([11
2
JB?
? ??? 1)( ?? ?? ?H
例,
???
?
???
??
???
?
???
??
2
1,
21
12 bA ?，考虑迭代格式 )( )()()1( bxAxx kkk ???? ???? ?
问,? ? 取何值可使迭代收敛？
? ? 取何值时迭代收敛最快？
解,考察 B = I + ? A 的特征根 ?1 = 1+ ?,?2 = 1+ 3?
? 收敛要求 ? ( B )<1 ?2/3 < ? < 0
? ? (B) = max { | 1+ ? |,| 1+ 3? | }
当 ? 取何值时 最小？
?2/3 ?1/3 0
?
? = ? 1/2
HW,p.77 #5 #7
§ 5 Relaxation Methods
Lab 08,SOR Method
Use the SOR method to solve a given n× n linear system
with an initial approximation and a set of ?’s,
Input
There are several sets of inputs,For each set,
The 1st line contains an integer 100 ? n ? 0 which is the size of a
matrix,n = ?1 signals the end of file,
The following n lines contain the
augmented matrix in the following format,
The numbers are separated by spaces and new lines,
The next line contains a real number TOL,which is the tolerance
for || · ||? norm,and an integer N ? 0 which is the maximum number of
iterations,
The last line of each test case contains an integer m > 0,followed
by m real ?’ s,
bxA ???
0)0( ?? ?x
nnnn
n
n
baa
baa
baa
.,,
.,,.,,.,,.,,
.,,
.,,
1
2221
1111
§ 5 Relaxation Methods
Output (? represents a space)
For each ?,there must be a set of outputs in the following format,
? The 1st line contains an ? and the corresponding number of iterations
taken,In the C printf,
fprintf(outfile,"%4.2f?%d\n",omega,iter_no );
The corresponding solution or error messages are to be printed as the
following,
? Each entry of the solution is to be printed as in the C fprintf,
fprintf(outfile,"%12.8f\n",x );
? If the matrix A has a zero column,print the message, Matrix?has?
a?zero?column,??No? unique?solution?exists.\n”,
? If the method fails to give a solution after N iterations,print the message
,Maximum?number?of? iterations?exceeded.\n”,
? If there is an entry of that is out of the range [ ?2127,2127 ],print the
message, No? convergence.\n”,
The outputs of two test cases must be seperated by a blank line,
)(kx?
注意：检查每个 aii时，先向下
找 最大元,若非 0则 交换 到对角线上；
否则向上找 最大元,若非 0则
将该行 加 到第 i 行上。
§ 5 Relaxation Methods
Sample Input
(? represents a space)
3
4?–1?0?1
–1?4?–1?4
0?–1?4?–3
0.000001?1000
2?1.05?1.2
3
10?–1?0?9
–1?10?–2?7
0?–4?10?6
0.000000001?1000
1?1
–1
Sample Output
(? represents a space)
1.05?7
??0.50000000
??1.00000000
?–0.50000000
1.20?11
??0.49999997
??0.99999998
?–0.50000002
1.00?10
??1.00000000
??1.00000000
??1.00000000
的收敛条件 fxBx kk ??? ??? )()1(
*)1()1( xxe kk ??? ?? ?? )()()( *)()*()( kkk eBxxBfxBfxB ??????? ???????
)0()( eBe kk ?? ? ||||||||...|||||||||||| )0()1()( eBeBe kkk ??? ?????? ?
充分条件, ||B|| < 1 ???? kB k as0||||
0|||| )( ?? ke?
必要条件, kk Bke ???? as0)( ??？
定义 设,
.)(,)( )( nnnnkijknnij RaAaA ??? ???
A A k
k
?
? ?lim 是指 ij
k
ij k a a ? ? ?
) ( lim 对所有 1? i,j ? n 成立。
等价于对
任何算子范数有
???? kAA k as0||||
0|||| ?xB k ? 对 任意非零向量 成立 x?
§ 4 Convergence of Iterative methods
定理 设 fxBx ??? ?? 存在唯一解，则从任意 出发,)0(x?
迭代 fxBx kk ??? ??? )()1( 收敛 ? 0 ? k B
证明,Bk ? 0 || Bk || ? 0 0
||||
||||m a x
0
?
? x
xB k
x ?
?
??
“?”：对任意非零向量
有 x?
0|||||||| |||| ?? kk Bx xB ?
?
“?”：取
则
Tix )0...1...0()( ??
第 i 位 0)( ?kijb
0?? ?xB k 对 任意非零向量 成立 x?
从任意 出发,记,则 )0(x? *)0()0( xxe ??? ??
0)0()( ??? ?? eBe kk as k ? ?
}{ )(kx? 收敛
But hey,you don’t
seriously expect me to compute Bk
whenever I want to check
the convergence,do you?
§ 4 Convergence of Iterative methods
定理 Bk ? 0 ? ? ( B ) < 1
证明：,?” 若 ? 是 B 的 eigenvalue,则 ?k 是 Bk 的 eigenvalue 。
则 [? (B)]k = [ max | ? | ]k = | ?mk | ? ? ( Bk ) ? || Bk || ? 0
? ? (B) < 1 ?
“?” 首先需要一个引理 /* Lemma */
对任意 ? > 0,存在算子范数 || · || 使得 || A || ? ? (A) ? ? 。
由 ? (B) < 1 可知存在算子范数 || · || 使得 || B || < 1。
|| Bk || ? || B ||k ? 0 as k ? ? Bk ? 0
迭代从任意向量出发收敛 Bk ? 0 ? ( B ) < 1
证明,对 A 做 Jordan 分解，有,其中
,, ?i 为 A 的 eigen value。
令,则有
易证,
是由 导出的算子范数。
所以只要取 ? < ?,就有 || A ||? < ? (A) ? ? 。
?
?
?
?
?
?
?
?
?
?
??
rJ
J
APP,,,
1
1
inini
i
iJ
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
01
?
?
?r
i
i nn
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? 1
2
1
n
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
r
r
A P DPD
?
?
??
?
?
??
1
1
11
????? ????? ???? )()||(m a x|||||||| 1111 AA P DPDA iri
11 ||)(|||||| xPDx v ?? ??
§ 4 Convergence of Iterative methods
定理 （充分条件） 若存在一个矩阵范数使得 || B || = q < 1,
则 迭代收敛，且有下列误差估计,
①
||||1||*|| )1()()( ????? kkk xxqqxx ????
②
||||1||*|| )0()1()( xxqqxx
k
k ???? ?
???
证明,①
)*(
)*(*
)1()()(
)1()(
?
?
????
???
kkk
kk
xxxxB
xxBxx ???? ????
| | )||||*( | |||*|| )1()()()( ?????? kkkk xxxxqxx ?????? ?
② )(...)( )0()1(1)2()1()1()( xxBxxBxx kkkkk ?????? ?????? ????
|||||||| )0()1(1)1()( xxqxx kkk ???? ??? ??
§ 4 Convergence of Iterative methods
定理 （充分条件） 若 A 为 严格对角占优阵 /* strictly
diagonally dominant matrix */ 则解 的 Jacobi 和 Gauss -
Seidel 迭代均收敛。
bxA ?? ?
证明,首先需要一个引理 /* Lemma */
若 A 为 SDD阵，则 det(A) ? 0，且所有的 aii ? 0。
证明,若不然，即 det(A) = 0，则 A 是奇异阵。
存在非零向量 使得 T
nxxxx ),,( 210 ?? ?,00 ?? ?xA
记 ||m a x||
1 inim xx ??? ?
?
?n
i
iim xa
1
0
??
??
??
mi
imm
mi
iimmmm axxaxa ||||||
显然
我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别
证明：任何一个 | ? | ? 1 都 不可能 是对应迭代阵的
特征根，即 | ?I ? B | ? 0 。
Jacobi,BJ = ?D?1( L + U )
|)(||| 1 ULDIBI ???? ???
|||||)(| 11 ULDDULDD ?????? ?? ??
aii ? 0
ija
ija ?
?
?
?
?
?
?
?
?
?
nna
a
?
? 11
如果 | ? | ? 1 则 ?
?
??
ij ijiiii
aaa |||||| ? 是 SDD阵
| ?I ? B | ? 0 ?
HW,
p.76 #1
关于 Gauss-Seidel迭代的证明
与此类似 (p.73)。
另一种证明引理的方法利用
Ger?gorin Disc Theorem (p.72)。
§ 5 松弛法 /* Relaxation Methods */
换个角度看 Gauss - Seidel 方法,
??
??
?
?
?? ???
n
ij
k
jij
i
j
k
iiji
ii
k
i xaxabax
1
)(
1
1
)1()1( ][1
ii
k
ik
i a
rx )1()( ??? 其中 ri(k+1) = ? ?
< ?
? ??
ij ij
kjijkjiji xaxab )()1(
/* residual */
相当于在 的基础上 加个余项 生成 。 )(kix )1( ?kix
下面令,希望通过选取合适的 ? 来
加速收敛，这就是 松弛法 /* Relaxation Methods */ 。 ii
k
i k
i
k
i a
r x x ) 1 ( ) ( ) 1 ( ? ? ? ? ?
0 < ? < 1 低松弛法 /* Under- Relaxation methods */
? = 1 Gauss - Seidel 法
? > 1 (渐次 )超松弛法 /* Successive Over- Relaxation
methods */
§ 5 Relaxation Methods
写成 矩阵形式,
ii
k
ikiki arxx
)1()()1( ?? ?? ? ??
?<
? ??????
ij
i
k
jij
ij
k
jijii
k
i bxaxaax ][)1(
)()1()( ??
][)1( )()1(1)()1( bxUxLDxx kkkk ????? ?????? ??? ??
bLDxUDLDx kk ??? ????? 1)(1)1( )(])1[()( ??? ??????
?H f
?松弛迭代阵
定理 设 A 可逆，且 aii ? 0,松弛法从任意 出发对
某个 ? 收敛 ? ? ( H? ) < 1。
)0(x?
Oooooh come on!
It’s way too complicated to compute H?,
and you can’t expect me to get
its spectral radius right!
There’s gotta be a short cut …
§ 5 Relaxation Methods
定理 （ Kahan 必要条件） 设 A 可逆，且 aii ? 0,松弛法
从任意 出发收敛 ? 0 < ? < 2 。 )0(x?
证明,从 出发 ])1[()( 1 UDLDH ???
? ???? ?
?
?
?
n
i
iH
1
)de t ( ??
利用,而且收敛 ? | ?i | < 1 总成立
可知收敛 ? | det(H?) | < 1
?
?
? ?
???
n
i iiaLD
LD
1
1 1
)d e t (
1))d e t ( (
??
?
?
????
n
i
ii
n aUD
1
)1())1d e t ( ( ???
nH )1()d e t ( ?? ??
? | det(H?) | ? | 1 ? ? |n < 1 ? 0 < ? < 2
§ 5 Relaxation Methods
定理 （ Ostrowski-Reich 充分条件） 若 A 对称正定，且有
0 < ? < 2，则 松弛法从任意 出发收敛 。 )0(x?
Q,What factor determines the speed of convergence?
考察迭代 fxBx kk ??? ??? )()1(,设 B 有特征根 ?1,…, ?n 对
应 n 个线性无关的特征向量 。则从任意 出
发,可表为 的线性组合，即
n?? ??,...,1 )0(x
?
*)0()0( xxe ??? ?? n?? ??,...,1
?
?
?
n
i
iie
1
)0( ?? ?? ?
?
??
n
i
i
k
ii
kk eBe
1
)0()( ??? ???
~ )0()]([ eB k ??A,The smaller ? ( B ) is,the faster the iterations will converge,
对于 SOR法，希望找 ? 使得 ? ( H? ) 最小 。
§ 5 Relaxation Methods
定理 若 A 为 对称正定三对角阵,则
且 SOR的 最佳松弛因子 /* optimal choice of ? for SOR method */
为,此时 。
1)]([)( 2 <?? JSG BB ??
2)]([11
2
JB?
? ??? 1)( ?? ?? ?H
例,
???
?
???
??
???
?
???
??
2
1,
21
12 bA ?，考虑迭代格式 )( )()()1( bxAxx kkk ???? ???? ?
问,? ? 取何值可使迭代收敛？
? ? 取何值时迭代收敛最快？
解,考察 B = I + ? A 的特征根 ?1 = 1+ ?,?2 = 1+ 3?
? 收敛要求 ? ( B )<1 ?2/3 < ? < 0
? ? (B) = max { | 1+ ? |,| 1+ 3? | }
当 ? 取何值时 最小？
?2/3 ?1/3 0
?
? = ? 1/2
HW,p.77 #5 #7
§ 5 Relaxation Methods
Lab 08,SOR Method
Use the SOR method to solve a given n× n linear system
with an initial approximation and a set of ?’s,
Input
There are several sets of inputs,For each set,
The 1st line contains an integer 100 ? n ? 0 which is the size of a
matrix,n = ?1 signals the end of file,
The following n lines contain the
augmented matrix in the following format,
The numbers are separated by spaces and new lines,
The next line contains a real number TOL,which is the tolerance
for || · ||? norm,and an integer N ? 0 which is the maximum number of
iterations,
The last line of each test case contains an integer m > 0,followed
by m real ?’ s,
bxA ???
0)0( ?? ?x
nnnn
n
n
baa
baa
baa
.,,
.,,.,,.,,.,,
.,,
.,,
1
2221
1111
§ 5 Relaxation Methods
Output (? represents a space)
For each ?,there must be a set of outputs in the following format,
? The 1st line contains an ? and the corresponding number of iterations
taken,In the C printf,
fprintf(outfile,"%4.2f?%d\n",omega,iter_no );
The corresponding solution or error messages are to be printed as the
following,
? Each entry of the solution is to be printed as in the C fprintf,
fprintf(outfile,"%12.8f\n",x );
? If the matrix A has a zero column,print the message, Matrix?has?
a?zero?column,??No? unique?solution?exists.\n”,
? If the method fails to give a solution after N iterations,print the message
,Maximum?number?of? iterations?exceeded.\n”,
? If there is an entry of that is out of the range [ ?2127,2127 ],print the
message, No? convergence.\n”,
The outputs of two test cases must be seperated by a blank line,
)(kx?
注意：检查每个 aii时，先向下
找 最大元,若非 0则 交换 到对角线上；
否则向上找 最大元,若非 0则
将该行 加 到第 i 行上。
§ 5 Relaxation Methods
Sample Input
(? represents a space)
3
4?–1?0?1
–1?4?–1?4
0?–1?4?–3
0.000001?1000
2?1.05?1.2
3
10?–1?0?9
–1?10?–2?7
0?–4?10?6
0.000000001?1000
1?1
–1
Sample Output
(? represents a space)
1.05?7
??0.50000000
??1.00000000
?–0.50000000
1.20?11
??0.49999997
??0.99999998
?–0.50000002
1.00?10
??1.00000000
??1.00000000
??1.00000000
