迭代法相关证明 Question I:证明定理：若线性方程组的系数矩阵Ar=b满足下列条件之一： (a)A为行严格对角占优阵，即a>∑lal,i=1,2,,n. (b)A为列严格对角占优阵，即lal>∑la,i=1,2,,n (c)A为正定对称矩性 则Gauss-Seideli迭代收敛 Proof: (a以(b):由选代收敛的充要条件，只需证(M0,因此Q可逆。现假设M存在特征值入，满足A≥1。 由A为M的特征值应有 det(AI-M)=0 考察AI-M AI-M=AI+Q-U=Q-(XQ+U) 所以 det(AI-M)=det(Q-1)det(XQ+U) 考察AQ+U,由于N≥1，显然(AQ+U)也是严格对角占优的，因此(AQ+U非奇异。dt(M M)≠0，矛盾。所以任取M的特征值有<1，即(M)<1,证毕。 (C):由下面SOR的收敛性定理可直接推出，取w=1。 ■ Question II:证明定理： (a)0<<2,是SOR选代收敛的必要条件 (b)若A为对称正定矩阵，则当0<w<2时，SOR迭代恒收敛. Proof: (a:设M=(D+wL)[(1-w)D-wU。这里L、D、U分别是A的下三角、对角、上三角部分， 满足L+D+U=A。 因为SOR收敛，所以p(M)<1,由所有特征值的模长小于1，可得 ldet(M.)<1 考察det(M),由D+wL可逆可得D可逆，M有如下表示 M=(D+wL)-1[1-)D-wU)=(I+wD-1L)-1[1-w)I-wD-1U 考察行列式 det((I+wD-L)1)=1 det((1-w)I-wD-U]=(1-w)m ldet(M)=I(1-w)"<1 所以1-<1,即0<w<2。证毕。 1
迭代法相关证明 Question I:证明定理：若线性方程组的系数矩阵Ax = b满足下列条件之一： （a） A为行严格对角占优阵，即|aii|> P i̸=j |aij |, i = 1, 2, ..., n. （b） A为列严格对角占优阵，即|aii|> P i̸=j |aji|, i = 1, 2, ..., n. （c） A为正定对称矩阵 则Gauss-Seidel迭代收敛. Proof: (a)、(b):由迭代收敛的充要条件，只需证ρ(M) 0，因此Q可逆。现假设M存在特征值λ，满足|λ| ≥ 1。 由λ为M的特征值应有 det(λI − M) = 0 考察λI − M λI − M = λI + Q −1U = Q −1 (λQ + U) 所以 det(λI − M) = det(Q −1 )det(λQ + U) 考察λQ + U，由于|λ| ≥ 1，显然(λQ + U)也是严格对角占优的，因此(λQ + U)非奇异。det(λI − M) ̸= 0，矛盾。所以任取M的特征值有|λ|<1，即ρ(M)<1，证毕。 (c):由下面SOR的收敛性定理可直接推出，取ω = 1。 ■ Question II:证明定理： (a) 0<ω<2，是SOR迭代收敛的必要条件 (b) 若A为对称正定矩阵，则当0<ω<2时，SOR迭代恒收敛. Proof: (a):设Mω = (D + ωL) −1 [(1 − ω)D − ωU]。这里L、D、U分别是A的下三角、对角、上三角部分， 满足L + D + U = A。 因为SOR收敛，所以ρ(Mω)<1，由所有特征值的模长小于1,可得 |det(Mω)|<1 考察det(Mω),由D + ωL可逆可得D可逆，Mω有如下表示 Mω = (D + ωL) −1 [(1 − ω)D − ωU] = (I + ωD−1L) −1 [(1 − ω)I − ωD−1U] 考察行列式 det((I + ωD−1L) −1 ) = 1 det[(1 − ω)I − ωD−1U] = (1 − ω) n |det(Mω)| = |(1 − ω) n |<1 所以|1 − ω|<1，即0<ω<2。证毕。 1
(b):只需证pM)0,设xLx=a+iB,则xLTx= (x*Lx)=a-i3。再由A对称正定，有x*Ar=x*(亿+D+LT)x=6+2a>0,所以有 [1-w)i-w(a-i)]=A(6+w(a+i) 两边取模长平方有 P(1)6-wa+ (ǒ+a)2+w23 分子减分母 [(1-w)6-wa2+w2B2-(6+ua)2-w2B2=-w6(6+2a)(2-w)<0 所以<1。证毕。 ◆
(b):只需证ρ(Mω)0，设x ∗Lx = α + iβ，则x ∗L T x = (x ∗Lx) ∗ = α − iβ。再由A对称正定，有x ∗Ax = x ∗ (L + D + L T )x = δ + 2α>0,所以有 [(1 − ω)δ − ω(α − iβ)] = λ(δ + ω(α + iβ)) 两边取模长平方有 |λ| 2 = [(1 − ω)δ − ωα] 2 + ω 2β 2 (δ + ωα) 2 + ω2β 2 分子减分母 [(1 − ω)δ − ωα] 2 + ω 2β 2 − (δ + ωα) 2 − ω 2β 2 = −ωδ(δ + 2α)(2 − ω)<0 所以|λ|<1。证毕。 ■ 2
