6.2收敛性分析-213.另外，Richardson选代法的最优参数为2W=argminp(GR)=Ai +an即当=w时，选代矩阵的谱半径达到最小，并且有1-w入n,ifw≤w,>1 - )n _ k(A) - 1ifw=w*,p(GR) =K(A) +1'入1 + 入nw)i-1,if w≥w*.（留作练习）下面考虑Jacobi,Gauss-Seidel和SOR的收敛性，先介绍两个引理引理6.12 设 Ae Cnxn 是 Hermite 的,矩阵分裂 A= M -N,其中 M 非奇异,则 M*+N 也是Hermite的，且对任意rECn有r*Ar -*Ai =u'(M* +N)u,其中=M-1N,u=-.(板书)证明.由于A是Hermite的,所以M*+N=M*+M一A也是Hermite的由于至=M-1N，所以M=N，因此Mu=MT-M=MT-N=Ar,Nu=NT-N=M-Ni=A.由M*+N的对称性可知M=M*+N-N*又（Nr)*=(M?)*,所以r*Ar-*Ai=r*Mu-*Nu= a*(M*+ N- N*)u-*Nu=r*M*u-r*N*u+r*Nu-*Nu=r*M*-*M*u+u*Nu= u*(M*+ N)u.口引理6.13设AERnxn对称，矩阵分裂A=M-N满足MT+N正定，则p(M-1N)<1当(板书)且仅当A是正定的证明.充分性.设入EC是M-1N的一个特征值,对应的特征向量为T≠0,即M-Na = ar.我们首先说明入1.假设>=1,则可得M=Nc,即Ar=0.由于A非奇异，所以=0,矛盾令=M-1N=r,=-=(1-).则由引理6.12可得(1 -[/P)r*Ar = [1 ->*(MT + N)r由于A和MT+N都是正定矩阵，所以上式右端为正,故I<1.因此p(M-1N)<1
6.2 收敛性分析 · 213 · 另外, Richardson 迭代法的最优参数为 ω∗ = arg min ω ρ(GR) = 2 λ1 + λn , 即当 ω = ω∗ 时, 迭代矩阵的谱半径达到最小, 并且有 ρ(GR) = 1 − ωλn, if ω ≤ ω∗, λ1 − λn λ1 + λn = κ(A) − 1 κ(A) + 1, if ω = ω∗, ωλ1 − 1, if ω ≥ ω∗. (留作练习) 下面考虑 Jacobi, Gauss-Seidel 和 SOR 的收敛性, 先介绍两个引理. 引理 6.12 设 A ∈ C n×n 是 Hermite 的, 矩阵分裂 A = M − N, 其中 M 非奇异, 则 M∗ + N 也是 Hermite 的, 且对任意 x ∈ C n 有 x ∗Ax − x˜ ∗Ax˜ = u ∗ (M∗ + N)u, 其中 x˜ = M−1Nx, u = x − x˜. (板书) 证明. 由于 A 是 Hermite 的, 所以 M∗ + N = M∗ + M − A 也是 Hermite 的. 由于 x˜ = M−1Nx, 所以 Mx˜ = Nx, 因此 Mu = Mx − Mx˜ = Mx − Nx = Ax, Nu = Nx − Nx˜ = Mx˜ − Nx˜ = Ax. ˜ 由 M∗ + N 的对称性可知 M = M∗ + N − N∗ . 又 (Nx) ∗ = (Mx˜) ∗ , 所以 x ∗Ax − x˜ ∗Ax˜ = x ∗Mu − x˜ ∗Nu = x ∗ (M∗ + N − N ∗ )u − x˜ ∗Nu = x ∗M∗u − x ∗N ∗u + x ∗Nu − x˜ ∗Nu = x ∗M∗u − x˜ ∗M∗u + u ∗Nu = u ∗ (M∗ + N)u. □ 引理 6.13 设 A ∈ R n×n 对称, 矩阵分裂 A = M − N 满足 MT + N 正定, 则 ρ(M−1N) < 1 当 且仅当 A 是正定的. (板书) 证明. 充分性. 设 λ ∈ C 是 M−1N 的一个特征值, 对应的特征向量为 x ̸= 0, 即 M−1Nx = λx. 我们首先说明 λ ̸= 1. 假设 λ = 1, 则可得 Mx = Nx, 即 Ax = 0. 由于 A 非奇异, 所以 x = 0, 矛盾. 令 x˜ = M−1Nx = λx, u = x − x˜ = (1 − λ)x. 则由引理 6.12 可得 (1 − |λ| 2 )x ∗Ax = |1 − λ| 2x ∗ (MT + N)x. 由于 A 和 MT + N 都是正定矩阵, 所以上式右端为正, 故 |λ| < 1. 因此 ρ(M−1N) < 1
-214.第六讲线性方程组基本选代法必要性.反证法.假设A不是正定的.由于p(M-1N)<1,所以A=M(I-M-1N)非奇异，因此存在(0)Rn,使得n≤ (μ(0) T Ar(0) <0.以z(o)为初始点，构造迭代序列2(k) = M-1Na(k-1), k=1,2,..由p(M-1N)<1可知lim r(k) = lim (M-1N)r(0) = 0.(6.12)令u()=2(k-1)-2(k),则由引理6.12可得(r(-1) Ar(x-1) - (c() Ar() = (u() (MT + N)u()由于MT+N对称正定，上式右端非负，所以(a() Ac() ≤ (2(k-1) Ar(k-1).依此类推，可得(2() Ar() ≤ (2() A2(0) =n< 0.口这与(22)矛盾.因此A一定是正定的我们首先给出SOR送代法收敛的一个必要条件定理6.14对于SOR选代法,有p(GsOR)≥|1-wl,故SOR选代法收敛的必要条件是0<W<2.(板书)证明.SOR的选代矩阵为GsOR = (D -wL)-1(1 -w)D +wU) = (I -wL)-1(1 -w)I +wU)所以 GsOR 的行列式为det (GsoR) = det (I -wL)-1) - det(1 -w)I + wU) = (1 -w)n设GsOR的特征为入1,入2，..·.入n，则A142 --- An = det (GsOR) = (1 - w)",故至少有一个特征值的模不小于[1-wl,即p(GsOR)≥/1-wl口若SOR收敛,则p(GsOR)<1,因此|1-w<1,即0<w<2定理 6.15 设 A e IRnxn 对称正定(1）若2D－A正定，则Jacobi选代法收敛(2)若0<w<2,则SOR选代法和SSOR选代法收敛(3)G-S选代法收敛.（留作课外自习，直接利用前面的引理即可）
· 214 · 第六讲 线性方程组基本迭代法 必要性. 反证法. 假设 A 不是正定的. 由于 ρ(M−1N) < 1, 所以 A = M(I − M−1N) 非奇异, 因此存在 x (0) ∈ R n , 使得 η ≜ x (0)T Ax(0) < 0. 以 x (0) 为初始点, 构造迭代序列 x (k) = M−1Nx(k−1), k = 1, 2, . . . . 由 ρ(M−1N) < 1 可知 lim k→∞ x (k) = lim k→∞ (M−1N) kx (0) = 0. (6.12) 令 u (k) = x (k−1) − x (k) , 则由引理 6.12 可得 x (k−1)T Ax(k−1) − x (k) T Ax(k) = u (k) T (MT + N)u (k) . 由于 MT + N 对称正定, 上式右端非负, 所以 x (k) T Ax(k) ≤ x (k−1)T Ax(k−1) . 依此类推, 可得 x (k) T Ax(k) ≤ x (0)T Ax(0) = η < 0. 这与 (??) 矛盾. 因此 A 一定是正定的. □ 我们首先给出 SOR 迭代法收敛的一个必要条件. 定理 6.14 对于 SOR 迭代法, 有 ρ(GSOR) ≥ |1−ω|, 故 SOR 迭代法收敛的必要条件是 0 < ω < 2. (板书) 证明. SOR 的迭代矩阵为 GSOR = (D − ωL) −1 (1 − ω)D + ωU = (I − ωL˜) −1 (1 − ω)I + ωU˜ . 所以 GSOR 的行列式为 det GSOR = det (I − ωL˜) −1 · det((1 − ω)I + ωU˜) = (1 − ω) n . 设 GSOR 的特征为 λ1, λ2, . . . , λn, 则 λ1λ2 · · · λn = det GSOR = (1 − ω) n , 故至少有一个特征值的模不小于 |1 − ω|, 即 ρ(GSOR) ≥ |1 − ω|. 若 SOR 收敛, 则 ρ(GSOR) < 1, 因此 |1 − ω| < 1, 即 0 < ω < 2. □ 定理 6.15 设 A ∈ R n×n 对称正定. (1) 若 2D − A 正定, 则 Jacobi 迭代法收敛. (2) 若 0 < ω < 2, 则 SOR 迭代法和 SSOR 迭代法收敛. (3) G-S 迭代法收敛. (留作课外自习, 直接利用前面的引理即可)