-208第六讲线性方程组基本选代法所以由0≤p(A)=p(A)≤A可得lim p(A)h = 0,口即 p(A)< 1.下面给出谱半径与范数之间的一个重要关系式，有时也用来定义矩阵的谱半径定理6.3设AeIRnxn（或Cnxn),则对任意矩阵范数I·Il,有p(A) = lim(板书)证明.由谱半径与范数之间的关系可知p(A)= p(A) ≤IA另一方面，对任意>0,构造矩阵1Ae:A.p(A) +则p(Ae)<1,故 limA=0.因此存在正整数N,使得当k>N时,有IAll<1,即AkI/A^lI<1(p(A) +e)k(p(A) +e)k所以p(A) ≤LA≤p(A) +E,即对任意e>0,存在正整数N，使得当k>N时，有AK-p(A)<e)口根据极限定义可知,A→p(A)下面给出基本选代法收敛的定义定义6.4考虑基本选迭代法（6.3).如果对任意的初始向量(0)都有lim 2(k)→*k-则称基本选代法（6.3)是收敛的，否则就称其为发散的基于矩阵分裂的选代法，其收敛性取决于选代矩阵的谱半径下面考虑基本选代法（6.3）的收敛性.首先给出一个选代法收敛的充分条件引理6.4若存在算子范数·,使得G<1,则选代法（6.3)收敛(板书）证明.由z(k+1)=Gr()+g和*=G*+g可得2(+1) - * = G ((k) - a*)
· 208 · 第六讲 线性方程组基本迭代法 所以由 0 ≤ ρ(A) k = ρ(Ak ) ≤ ∥Ak∥ 可得 lim k→∞ ρ(A) k = 0, 即 ρ(A) < 1. □ 下面给出谱半径与范数之间的一个重要关系式, 有时也用来定义矩阵的谱半径. 定理 6.3 设 A ∈ R n×n (或 C n×n ), 则对任意矩阵范数 ∥ · ∥, 有 ρ(A) = lim k→∞ A k 1 k . (板书) 证明. 由谱半径与范数之间的关系可知 ρ(A) k = ρ(A k ) ≤ ∥A k ∥. 另一方面, 对任意 ε > 0, 构造矩阵 Aε = 1 ρ(A) + ε A. 则 ρ(Aε) < 1, 故 lim k→∞ Ak ε = 0. 因此存在正整数 N, 使得当 k > N 时, 有 ∥Ak ε∥ < 1, 即 Ak (ρ(A) + ε) k = ∥Ak∥ (ρ(A) + ε) k < 1. 所以 ρ(A) ≤ A k 1 k ≤ ρ(A) + ε, 即对任意 ε > 0, 存在正整数 N, 使得当 k > N 时, 有 A k 1 k − ρ(A) < ε. 根据极限定义可知, Ak 1 k → ρ(A). □ 下面给出基本迭代法收敛的定义. 定义 6.4 考虑基本迭代法 (6.3), 如果对任意的初始向量 x (0) , 都有 lim k→∞ x (k) → x∗, 则称基本迭代法 (6.3) 是收敛的, 否则就称其为发散的. b 基于矩阵分裂的迭代法, 其收敛性取决于迭代矩阵的谱半径. 下面考虑基本迭代法 (6.3) 的收敛性. 首先给出一个迭代法收敛的充分条件. 引理 6.4 若存在算子范数 ∥ · ∥, 使得 ∥G∥ < 1, 则迭代法 (6.3) 收敛. (板书) 证明. 由 x (k+1) = Gx(k) + g 和 x∗ = Gx∗ + g 可得 x (k+1) − x∗ = G x (k) − x∗
6.2收敛性分析·209.故[2(+1) - 2≤ I2() 2r依此类推，可得2(+1) ≤ IIG/k+1 (0) 1口由于IG<1,当→80时，上式右端→0,即(k+1)-=l→0.因此选代法收敛。事实上，由习题1.10可知，引理6.4条件中的算子范数可以改为任意矩阵范数我们记e()r()一为第步选代解(k)的误差向量定理6.5(基本收敛性定理)对任意初始向量r(0),选代法(6.3)收敛的充要条件是p(G)<1.(板书)证明.必要性：用反证法，假设p(G)≥1.设入为G的模最大的特征值，即I/=p(G)≥1.令≠0为其对应的特征向量.取送代初始向量(0)=*+,则() - *= G((k-1) - ) =... = Gk(r(0) - *)= Gha = ^不可能收敛到0,即方法不收敛.故假设不成立，因此p(G)<1.充分性：若p(G)<1,则由引理1.39可知，存在一个算子范数·le，使得IIGle<1.再由引理口6.4可知，方法收敛.定义6.5设G是选代矩阵，则选代法(6.3)的平均收敛速度定义为Rk(G)会- In IG*/老,渐进收敛速度定义为R(G) ≤ lim Rk(G) = - ln p(G).k→oc平均收敛速度与选代步数和所用的范数有关，但渐进收敛速度只依赖于选代矩阵的谱半径数值分析中关于收敛速度的定义：设点列[ek)]-, 收敛,且 lim ek=0. 若存在一个有界常数 0<c<o0,使得[ek+1]lim-k-→00 [ek/P则称点列[el是p次(渐进)收敛的.若1<p<2或p=1且c=0,则称点列是超线性收敛的
6.2 收敛性分析 · 209 · 故 x (k+1) − x∗ ≤ ∥G∥ x (k) − x∗ . 依此类推, 可得 x (k+1) − x∗ ≤ ∥G∥ k+1 x (0) − x∗ . 由于 ∥G∥ < 1, 当 k → ∞ 时, 上式右端 → 0, 即 x (k+1) − x∗ → 0. 因此迭代法收敛. □ b 事实上, 由习题 1.10 可知, 引理 6.4 条件中的算子范数可以改为任意矩阵范数. b 我们记 e (k) ≜ x (k) − x∗ 为第 k 步迭代解 x (k) 的误差向量. 定理 6.5 (基本收敛性定理) 对任意初始向量 x (0) , 迭代法 (6.3) 收敛的充要条件是 ρ(G) < 1. (板书) 证明. 必要性: 用反证法, 假设 ρ(G) ≥ 1. 设 λ 为 G 的模最大的特征值, 即 |λ| = ρ(G) ≥ 1. 令 x ̸= 0 为其对应的特征向量. 取迭代初始向量 x (0) = x∗ + x, 则 x (k) − x∗ = G(x (k−1) − x∗) = · · · = G k (x (0) − x∗) = G kx = λ kx, 不可能收敛到 0, 即方法不收敛. 故假设不成立, 因此 ρ(G) < 1. 充分性: 若 ρ(G) < 1, 则由引理 1.39 可知, 存在一个算子范数 ∥ · ∥ε, 使得 ∥G∥ε < 1. 再由引理 6.4 可知, 方法收敛. □ 定义 6.5 设 G 是迭代矩阵, 则迭代法 (6.3) 的平均收敛速度定义为 Rk(G) ≜ − ln ∥G k ∥ 1 k , 渐进收敛速度定义为 R(G) ≜ lim k→∞ Rk(G) = − ln ρ(G). b 平均收敛速度与迭代步数和所用的范数有关, 但渐进收敛速度只依赖于迭代矩阵的谱半径. b 数值分析中关于 收敛速度 的定义: 设点列 {εk}∞ k=1 收敛, 且 lim k→∞ εk = 0. 若存在一个有界常数 0 < c < ∞, 使得 lim k→∞ |εk+1| |εk| p = c, 则称点列 {εk} 是 p 次 (渐进) 收敛的. 若 1 < p < 2 或 p = 1 且 c = 0, 则称点列是超线性收 敛的
-210.第六讲线性方程组基本选代法定理6.6考虑选代法(6.3).如果存在某个算子范数-使得G=<1,则(1) [2(k) -≤(0) -+l;q() - 2(k-1)l;(2) I/r(k) - / ≤ :gk(1) - 2(0) /(3) Ir(k) - / ≤1-q(板书)证明.(1)由2(k)=Gz(k-1)+g和=G*+g可得2(k) = *=G((k-1) - 2*)因此有[[r(k) - */ ≤IG [r(k-1) - +l = ql(k-1) - +l(6.7)反复利用结论(2)即可得(k)-≤(0)-(2)由(k+1)=Gz(k)+g和=G++g可得2(+1) - 2() =G(() - 2(k-1)因此有Il2(k+1) - (k)l ≤qll2(k) - (k-1)l,(6.8)根据(22)，我们有(k+1)-≤l(K)-所以II2(k+1) - 2(k) = * - 2(k) + 2(+1) -*Il≥ I+ - 2(*) I[2(++1) - l≥ (1 -q)r(k) -l结合(22)可得1(+)-((2([2 - 2() ≤1(3)反复利用(22)即可得I/(k+1) = 2(k) ≤ q/ 2(1) - 2(0) 1.所以,I(+) 2(告() 2(/),*(K) ≤1.口一般来说，好的选代法应该满足[30]：(1)p(G)很小;(2)以M为系数矩阵的线性方程组比较容易求解6.2.2不可约对角占优矩阵这里我们考虑A是严格对角占优或不可约对角占优情形
· 210 · 第六讲 线性方程组基本迭代法 定理 6.6 考虑迭代法 (6.3). 如果存在某个算子范数 ∥ · ∥ 使得 ∥G∥ = q < 1, 则 (1) ∥x (k) − x∗∥ ≤ q k∥x (0) − x∗∥; (2) ∥x (k) − x∗∥ ≤ q 1 − q ∥x (k) − x (k−1)∥; (3) ∥x (k) − x∗∥ ≤ q k 1 − q ∥x (1) − x (0)∥. (板书) 证明. (1) 由 x (k) = Gx(k−1) + g 和 x∗ = Gx∗ + g 可得 x (k) − x∗ = G x (k−1) − x∗ . 因此有 ∥x (k) − x∗∥ ≤ ∥G∥ · ∥x (k−1) − x∗∥ = q∥x (k−1) − x∗∥. (6.7) 反复利用结论 (??) 即可得 ∥x (k) − x∗∥ ≤ q k∥x (0) − x∗∥. (2) 由 x (k+1) = Gx(k) + g 和 x∗ = Gx∗ + g 可得 x (k+1) − x (k) = G x (k) − x (k−1) 因此有 ∥x (k+1) − x (k) ∥ ≤ q∥x (k) − x (k−1)∥, (6.8) 根据 (??), 我们有 ∥x (k+1) − x∗∥ ≤ q∥x (k) − x∗∥. 所以 ∥x (k+1) − x (k) ∥ = ∥x∗ − x (k) + x (k+1) − x∗∥ ≥ ∥x∗ − x (k) ∥ − ∥x (k+1) − x∗∥ ≥ (1 − q)∥x (k) − x∗∥. 结合 (??) 可得 ∥x∗ − x (k) ∥ ≤ 1 1 − q ∥x (k+1) − x (k) ∥ ≤ q 1 − q ∥x (k) − x (k−1)∥. (3) 反复利用 (??) 即可得 ∥x (k+1) − x (k) ∥ ≤ q k ∥x (1) − x (0)∥. 所以 ∥x∗ − x (k) ∥ ≤ 1 1 − q ∥x (k+1) − x (k) ∥ ≤ q k 1 − q ∥x (1) − x (0)∥. □ b 一般来说, 好的迭代法应该满足 [30]: (1) ρ(G) 很小; (2) 以 M 为系数矩阵的线性方程组比较容易求解. 6.2.2 不可约对角占优矩阵 这里我们考虑 A 是严格对角占优或不可约对角占优情形
6.2收敛性分析-211.定理6.7设AERnxn，若A严格对角占优，则Jacobi选代法和G-S选代法都收敛，且[Gs≤ G]l < 1.(板书)证明.首先证明IGll<1.由于A严格行对角占优，故laijl/lail<1.所以法IG)l~ = ID-(L+ U)Il = ≥<1.[ail<i<n送下面证明|GGsl≤Gilo，只需证明|GGse≤|Gjle即可，其中e=[1,1.,1]T令=D-1L和=D-1U.则L是严格下三角矩阵，故in=0,所以(I - L)-1 = I + L + L2 +... + n-1于是IGGsle = (D-L)-1U]e = [(I -L)-1Ule=[(I + L+i? +.+ in-1)Ule≤ (1+ +2 +..+(n-1)]= (1 -)-e.(6.9)>0.即(1--0)e>0.两边同乘≥0可得由A的严格行对角占优性可知1-Ze== (-)(+) -)e,即e(-)()e.两边同乘(-)-≥可得( -)-jUle≤(+J)e口又|+U|=D-1(L+U)/=Gl,由(2a)可知|GGsle≤|Gjle,即定理结论成立当A是严格列对角占优时，该结论也成立定理6.8设 AE IRnxn,若A不可约对角占优,则Jacobi选代法和G-S选代法都收敛.进一步，若A是非负矩阵，则p(GGs) < p(G) < 1.(留作课外自习，需利用非负矩阵的相关知识，可参见[139])思考：若 AERnxn 严格对角占优且非负,则是否有结论 p(GGs)≤p(G)?
6.2 收敛性分析 · 211 · 定理 6.7 设 A ∈ R n×n , 若 A 严格对角占优, 则 Jacobi 迭代法和 G-S 迭代法都收敛, 且 ∥GGS∥∞ ≤ ∥GJ∥∞ < 1. (板书) 证明. 首先证明 ∥GJ∥∞ < 1. 由于 A 严格行对角占优, 故 P j̸=i |aij |/|aii| < 1. 所以 ∥GJ∥∞ = ∥D−1 (L + U)∥∞ = max 1≤i≤n X j̸=i |aij | |aii| < 1. 下面证明 ∥GGS∥∞ ≤ ∥GJ∥∞, 只需证明 |GGS|e ≤ |GJ |e 即可, 其中 e = [1, 1, . . . , 1]T. 令 L˜ = D−1L 和 U˜ = D−1U. 则 L˜ 是严格下三角矩阵, 故 L˜n = 0, 所以 (I − L˜) −1 = I + L˜ + L˜2 + · · · + L˜n−1 . 于是 |GGS|e = |(D − L) −1U|e = |(I − L˜) −1U˜|e = |(I + L˜ + L˜2 + · · · + L˜n−1 )U˜|e ≤ I + |L˜| + |L˜| 2 + · · · + |L˜| n−1 )|U˜|e = (I − |L˜|) −1 |U˜|e. (6.9) 由 A 的严格行对角占优性可知 1 − P j̸=i |aij | |aii| > 0, 即 (I − |L˜| − |U˜|)e > 0. 两边同乘 |L˜| ≥ 0 可得 0 ≤ |L˜|(I − |L˜| − |U˜|)e = (|L˜| − |L˜| 2 + |U˜| − |L˜| · |U˜| − |U˜|)e = (I − |L˜|)(|L˜| + |U˜|) − |U˜| e, 即 |U˜|e ≤ (I − |L˜|)(|L˜| + |U˜|)e. 两边同乘 (I − |L˜|) −1 ≥ 0 可得 (I − |L˜|) −1 |U˜|e ≤ (|L˜| + |U˜|)e. 又 |L˜| + |U˜| = |D−1 (L + U)| = |GJ |, 由 (??) 可知 |GGS|e ≤ |GJ |e, 即定理结论成立. □ b 当 A 是严格列对角占优时, 该结论也成立. 定理 6.8 设 A ∈ R n×n , 若 A 不可约对角占优, 则 Jacobi 迭代法和 G-S 迭代法都收敛. 进一步, 若 A 是非负矩阵, 则 ρ(GGS) < ρ(GJ) < 1. (留作课外自习, 需利用非负矩阵的相关知识, 可参见 [139]) 思考：若 A ∈ R n×n 严格对角占优且非负, 则是否有结论 ρ(GGS) ≤ ρ(GJ)?
-212.第六讲线性方程组基本选代法上述定理中的结论对一般矩阵并不成立：对某些矩阵，Jacobi迭代法收敛，但G-S选代法却不一定收敛，见思考题6.23关于SOR选代法，我们有下面的结论定理6.9设AERnxn若A严格对角占优且0<w<1,则SOR选代法收敛(板书)证明.反证法.假设SOR选代法不收敛，即p(GsOR)≥1.因此GsOR存在特征值入，满足[/≥1.由det(入I-GsOR)=0可知det (ΛI -(D -wL)-1(1 -w)D +wU)) = det (D -wL)-1) - det (A(D -wL) - (1 -w)D -wU)= det ((D - wL)-1) · det ( + w - 1)D - XwL - wU)= 0.又 det ((D -wL)-1)≠0, 所以det (+w - 1)D - AwL - wU) = 0由0<w≤1和[≥1可知,入+w-10.所以det(G)=0,其中XwwG=D-X+W-l-A+0-(6.10)U令>=a+ib,其中a,bER.则根据0<w≤1和≥1,可得[ + w - 1)2- [入w)2= (a + w + 1)? + 62 - w2(α? +b2)= (1 - w)((a - 1)2 +w(a? + 62 - 1) + 6b2)(6.11)≥ 0.所以Jwl[Aw]≤1又A是严格对角占优的，所以由(2)和(2a)可知,G也严格对角占优.这意味着det(G)≠0,矛盾口定理6.10 设 A E Rnxn,若 A 不可约对角占优且 0 <w ≤1,则 SOR 选代法收敛(留作课外自习）6.2.3对称正定矩阵首先给出Richardson选代法的收敛性定理6.11设AERnxn是对称正定矩阵，入1和入n分别是A的最大和最小特征值，则Richardson选代法收敛当且仅当20<w<A1
· 212 · 第六讲 线性方程组基本迭代法 b 上述定理中的结论对一般矩阵并不成立: 对某些矩阵, Jacobi 迭代法收敛, 但 G-S 迭代法却 不一定收敛, 见思考题 6.23. 关于 SOR 迭代法, 我们有下面的结论. 定理 6.9 设 A ∈ R n×n , 若 A 严格对角占优且 0 < ω ≤ 1, 则 SOR 迭代法收敛. (板书) 证明. 反证法. 假设 SOR 迭代法不收敛, 即 ρ(GSOR) ≥ 1. 因此 GSOR 存在特征值 λ, 满足 |λ| ≥ 1. 由 det(λI − GSOR) = 0 可知 det λI − (D − ωL) −1 (1 − ω)D + ωU = det (D − ωL) −1 · det λ(D − ωL) − (1 − ω)D − ωU = det (D − ωL) −1 · det (λ + ω − 1)D − λωL − ωU = 0. 又 det (D − ωL) −1 ̸= 0, 所以 det (λ + ω − 1)D − λωL − ωU = 0. 由 0 < ω ≤ 1 和 |λ| ≥ 1 可知, λ + ω − 1 ̸= 0. 所以 det(G˜) = 0, 其中 G˜ = D − λω λ + ω − 1 L − ω λ + ω − 1 U. (6.10) 令 λ = a + i b, 其中 a, b ∈ R. 则根据 0 < ω ≤ 1 和 |λ| ≥ 1, 可得 |λ + ω − 1| 2 − |λω| 2 = (a + ω + 1)2 + b 2 − ω 2 (a 2 + b 2 ) = (1 − ω) (a − 1)2 + ω(a 2 + b 2 − 1) + b 2 ≥ 0. (6.11) 所以 |ω| |λ + ω − 1| ≤ |λω| |λ + ω − 1| ≤ 1. 又 A 是严格对角占优的, 所以由 (??) 和 (??) 可知, G˜ 也严格对角占优. 这意味着 det(G˜) ̸= 0, 矛盾. □ 定理 6.10 设 A ∈ R n×n , 若 A 不可约对角占优且 0 < ω ≤ 1, 则 SOR 迭代法收敛. (留作课外自习) 6.2.3 对称正定矩阵 首先给出 Richardson 迭代法的收敛性. 定理 6.11 设 A ∈ R n×n 是对称正定矩阵, λ1 和 λn 分别是 A 的最大和最小特征值, 则 Richardson 迭代法收敛当且仅当 0 < ω < 2 λ1