§ 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
AAk
k
lim 是指 ij
k
ijk aa
)(lim 对所有 1? i,j? n 成立。
等价于对任何算子范数有
kAA k as0||||
0||||?xB k? 对 任意非零向量 成立x?
§ 4 Convergence of Iterative methods
定理 设 fxBx 存在唯一解，则从任意 出发，)0(x?
迭代 fxBx kk )()1( 收敛? 0?kB
证明,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
0xB 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,00xA
记 ||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
ik
i
k
i a
rxx )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 kA,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
AAk
k
lim 是指 ij
k
ijk aa
)(lim 对所有 1? i,j? n 成立。
等价于对任何算子范数有
kAA k as0||||
0||||?xB k? 对 任意非零向量 成立x?
§ 4 Convergence of Iterative methods
定理 设 fxBx 存在唯一解，则从任意 出发，)0(x?
迭代 fxBx kk )()1( 收敛? 0?kB
证明,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
0xB 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,00xA
记 ||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
ik
i
k
i a
rxx )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 kA,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
