6.2定常选代方法.181.一般来说，SOR方法的渐进收敛速度对参数w比较敏感，但SSOR的收敛速度对参数w不太敏感算法6.6.SSOR方法1: Given an initial guess w(0) and parameter w2: while not converge do3:for i=lto n doi-1&(++) = (1 - w) () +(k+)(k4:aijtnaijrjr,aiij=1j=i+1end for5:for i = n to 1 do6:2C(k+多)(++1) =(1 -w)(++) +(k+1)7:?haiaijjaiij=1j=i+end for8:9: end while例6.1已知二维Poisson方程-Au(r,y) = -1,(r,y)es1?+9?u(t,y)(r,y) E02422+y?其中2=(0,1)×(0,1).该方程的解析解是u(,3)用五点差分格式离散后得到一个线性方程组，分别用SOR和SSOR方法求解方程，观察参数对方法收敛的影响参见MATLAB程序Poisson_SoR_omega.m和Poisson_SSoRomega.m.下图中画出了N=8时，SOR和SSOR收敛结果与参数w取值之间的关系SOR with different SSOR with different 7070-8x88x8666560o555510050ainn4093025201.21.25131.351.451.5:1.551.61.651.71.21.251.351.451.51:551.61.651.714314图6.1.SOR和SSOR的收敛结果与w取值的关系
6.2 定常迭代方法 · 181 · † 一般来说, SOR 方法的渐进收敛速度对参数 ω 比较敏感, 但 SSOR 的收敛速度对参数 ω 不太敏 感. 算法 6.6. SSOR 方法 1: Given an initial guess v (0) and parameter ω 2: while not converge do 3: for i = 1 to n do 4: x (k+ 1 2 ) i = (1 − ω)x (k) i + ω aii ( bi − i ∑−1 j=1 aijx (k+ 1 2 ) j − ∑n j=i+1 aijx (k) j ) 5: end for 6: for i = n to 1 do 7: x (k+1) i = (1 − ω)x (k+ 1 2 ) i + ω aii ( bi − i ∑−1 j=1 aijx (k+ 1 2 ) j − ∑n j=i+1 aijx (k+1) j ) 8: end for 9: end while 例 6.1 已知二维 Poisson 方程 −∆u(x, y) = −1, (x, y) ∈ Ω u(x, y) = x 2 + y 2 4 , (x, y) ∈ ∂Ω 其中 Ω = (0, 1) × (0, 1). 该方程的解析解是 u(x, y) = x 2 + y 2 4 . 用五点差分格式离散后得到一个线性 方程组, 分别用 SOR 和 SSOR 方法求解方程, 观察参数对方法收敛的影响. 参见 MATLAB 程序 Poisson_SOR_omega.m 和 Poisson_SSOR_omega.m. 下图中画出了 N = 8 时, SOR 和 SSOR 收敛结果与参数 ω 取值之间的关系. 图 6.1. SOR 和 SSOR 的收敛结果与 ω 取值的关系
第六讲线性方程组定常选代方法.182.6.2.6AOR送代Hadjidimos于1978年提出了加速超松弛（AOR，AcceleratedOver-Relaxation）方法，迭代矩阵为GAOR = (D -L)-1[(1-w)D + (W-)L +wU)其中和w为松弛参数对应的矩阵分解为I(D-L), N=I(1-w)D + (w-)L +wU),M =w易知：(1）当=W时，AOR方法即为SOR方法；(2）当%=w=1时，AOR方法即为G-S方法：(3）当=0,w=1时，AOR方法即为Jacobi方法+AOR方法中含有两个参数，因此在理论上，通过选取合适的参数，AOR方法会收敛得更快，但也是因为含有两个参数，使得参数的选取变得更加困难，因此较少使用+与SSOR类似，我们也可以定义SAOR方法6.2.7Richardson方法Richardson方法是一类形式非常简单的算法，其迭代格式为(k+1) = r() + w(b = Ar(k),k=0,1,2..它可以看作是基于以下矩阵分裂的迭代方法：1N:M=AU对应的迭代矩阵为GR=I-WA定理6.2设AERnxn是对称正定矩阵，入i和入,分别是A的最大和最小特征值，则Richardson方法收敛当且仅当10<w<M另外,Richardson方法的最优参数为2W*=argminp(GR)Ai+An即当w二w，时，选代矩阵的谱半径达到最小，且有1-w入nifw≤w1 - 入nK(A)-1ifw=w*p(GR) :入1 + 入nk(A) + 1[w)i-1ifw≥w*
· 182 · 第六讲 线性方程组定常迭代方法 6.2.6 AOR 迭代 Hadjidimos 于 1978 年提出了 加速超松弛 (AOR , Accelerated Over-Relaxation ) 方法, 迭代矩阵为 GAOR = (D − γL) −1 [ (1 − ω)D + (ω − γ)L + ωU] , 其中 γ 和 ω 为松弛参数. 对应的矩阵分解为 M = 1 ω (D − γL), N = 1 ω [(1 − ω)D + (ω − γ)L + ωU]. 易知: (1) 当 γ = ω 时, AOR 方法即为 SOR 方法; (2) 当 γ = ω = 1 时, AOR 方法即为 G-S 方法; (3) 当 γ = 0, ω = 1 时, AOR 方法即为 Jacobi 方法. † AOR 方法中含有两个参数. 因此在理论上, 通过选取合适的参数, AOR 方法会收敛得更快. 但也 是因为含有两个参数, 使得参数的选取变得更加困难, 因此较少使用. † 与 SSOR 类似, 我们也可以定义 SAOR 方法. 6.2.7 Richardson 方法 Richardson 方法是一类形式非常简单的算法, 其迭代格式为 x (k+1) = x (k) + ω(b − Ax(k) ), k = 0, 1, 2, . . . . 它可以看作是基于以下矩阵分裂的迭代方法: M = 1 ω I, N = 1 ω I − A. 对应的迭代矩阵为 GR = I − ωA. 定理 6.2 设 A ∈ R n×n 是对称正定矩阵, λ1 和 λn 分别是 A 的最大和最小特征值, 则 Richardson 方法 收敛当且仅当 0 < ω < 1 λ1 . 另外, Richardson 方法的最优参数为 ω∗ = arg min ω ρ(GR) = 2 λ1 + λn , 即当 ω = ω∗ 时, 迭代矩阵的谱半径达到最小, 且有 ρ(GR) = 1 − ωλn if ω ≤ ω∗ λ1 − λn λ1 + λn = κ(A) − 1 κ(A) + 1 if ω = ω∗ ωλ1 − 1 if ω ≥ ω∗
6.3收敛性分析.183.十如果在每次送代时取不同的参数，即r(k+1) = r(k) + wk(b- Ar(k), k =0, 1,2,...,则每次选代的格式就不一样了，因此不再是定常选代，而是非定常（Nonstationary）迭代.此时称为非定常Richardson方法6.2.8分块选代方法前面介绍的迭代方法可以推广到分块情形.将A写All成如下的分块形式：A22[A1A12... ApA21A22..A2pA=Ap1Ap2...App设A=D-L=U,其中D,-L,-U分别是A的块App对角，块严格下三角和块严格上三角矩阵，则相应的分块Jacobi,分块Gauss-Seidel和分块SOR方法分别为·分块Jacobi选代：Aige(k),Au(k+1) = b, -= 1,2,..-,p.j=1.j+i。分块Gauss-seidel选代-4ya(k+1) _A(+1) = b, -)Aija(k)1i=1,2,...,Pj=lj=i+1·分块SOR选代一(k+1) _(k+1) = (1 - w)a() + wAmVAijaAijabis1j=i+1i=1,2,....p.6.3收敛性分析6.3.1定常选代方法的收敛性
6.3 收敛性分析 · 183 · † 如果在每次迭代时取不同的参数, 即 x (k+1) = x (k) + ωk(b − Ax(k) ), k = 0, 1, 2, . . . , 则每次迭代的格式就不一样了, 因此不再是定常迭代, 而是 非定常 (Nonstationary ) 迭代. 此时称 为 非定常 Richardson 方法. 6.2.8 分块迭代方法 前面介绍的迭代方法可以推广到分块情形. 将 A 写 成如下的分块形式: A = A11 A12 · · · A1p A21 A22 · · · A2p . . . . . . . . . . . . Ap1 Ap2 · · · App . 设 A = D − L − U, 其中 D, −L, −U 分别是 A 的块 对角, 块严格下三角和块严格上三角矩阵. 则相应的分块 Jacobi, 分块 Gauss-Seidel 和分块 SOR 方法分别为 • 分块 Jacobi 迭代: Aiix (k+1) i = bi − ∑p j=1,j̸=i Aijx (k) j , i = 1, 2, . . . , p. • 分块 Gauss-seidel 迭代: Aiix (k+1) i = bi − ∑ i−1 j=1 Aijx (k+1) j − ∑p j=i+1 Aijx (k) j , i = 1, 2, . . . , p. • 分块 SOR 迭代: x (k+1) i = (1 − ω)x (k) i + ωA−1 ii bi − ∑ i−1 j=1 Aijx (k+1) j − ∑p j=i+1 Aijx (k) j , i = 1, 2, . . . , p. 6.3 收敛性分析 6.3.1 定常迭代方法的收敛性
.184.第六讲线性方程组定常选代方法定义6.2（选代方法的收敛性）如果对任意的初始向量（(0)，都有lim 2(k)→*则称选代格式（6.8）是收敛的，否则就称其为发散的十基于矩阵分裂的送代方法，其收敛性取决于选代矩阵的谱半径矩阵谱半径设AERnxn,则称P(A) 4max [>]XEGA为A的谱半径,其中α(A)表示A的所有特征值组成的集合.谱半径与矩阵范数之间有如下的关系。引理6.3（谱半径与范数的关系）设GERnxn，则(I)对任意算子范数，有p(G)≤G;(2)反之,对任意>0,都存在一个算子范数Il·le,使得G≤p(G)+ε,其中范数·I依赖于G和ε. 所以,若 p(G)<1,则存在算子范数IL·I=,使得[Gll=<1;证明.（1)设入是G的二个特征值，对应的特征向量为r≠0,则由G工=入可得[/- = 入 = G ≤ G 故≤GI所以p(G)= max [/≤IIGIE(G)(2)用构造法证明.设G的Jordan标准型为J,即S-1GS=J.令D=diag(1,e,e?,..,en-1),则入1E入112(SD)-1G(SD) = D-1JD =12
· 184 · 第六讲 线性方程组定常迭代方法 定义 6.2 (迭代方法的收敛性) 如果对任意的初始向量 x (0) , 都有 lim k→∞ x (k) → x∗, 则称迭代格式 (6.8) 是收敛的, 否则就称其为发散的. † 基于矩阵分裂的迭代方法, 其收敛性取决于迭代矩阵的谱半径. 矩阵谱半径 设 A ∈ R n×n, 则称 ρ(A) ≜ max λ∈σ(A) |λ| 为 A 的谱半径, 其中 σ(A) 表示 A 的所有特征值组成的集合. 谱半径与矩阵范数之间有如下的关系. 引理 6.3 (谱半径与范数的关系) 设 G ∈ R n×n, 则 (1) 对任意算子范数, 有 ρ(G) ≤ ∥G∥; (2) 反之, 对任意 ε > 0, 都存在一个算子范数 ∥ · ∥ε, 使得 ∥G∥ε ≤ ρ(G) + ε, 其中范数 ∥ · ∥ε 依赖于 G 和 ε. 所以, 若 ρ(G) < 1, 则存在算子范数 ∥ · ∥ε, 使得 ∥G∥ε < 1; 证明. (1) 设 λ 是 G 的一个特征值, 对应的特征向量为 x ̸= 0, 则由 Gx = λx 可得 |λ| · ∥x∥ = ∥λx∥ = ∥Gx∥ ≤ ∥G∥ · ∥x∥. 故 |λ| ≤ ∥G∥. 所以 ρ(G) = max λ∈σ(G) |λ| ≤ ∥G∥. (2) 用构造法证明. 设 G 的 Jordan 标准型为 J, 即 S −1GS = J. 令 D = diag(1, ε, ε2 , . . . , εn−1 ), 则 (SD) −1G(SD) = D−1JD = λ1 ε . . . . . . . . . ε λ1 λ2 ε . . . . . . . . . ε λ2 . . . . . . . . .