迭代法相关证明 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):由选代收敛的充要条件，只需证(M<1,其中M=-(D+L)1U。这里L、D、U分别 是A的下三角、对角、上三角部分，满足L+D+U=A,并设Q=D+L。 由A严格对角占优，则对每个i,有a>0,因此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)<1，其中M = −(D + L) −1U。这里L、D、U分别 是A的下三角、对角、上三角部分，满足L + D + U = A，并设Q = D + L。 由A严格对角占优，则对每个i，有|aii| > 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