直接法的好处，除了舍入误差外没有引入额外的误差。但坏处在于，计算比较复杂。为此我们引入额外的误差设计迭代法。

本章概要

迭代法分为两大步：

• 方程的改写(矩阵分裂)
  • \(AX=b\)等价变形为\(X=BX+d\)
  • 若 \(A=M-N\),则\(MX=NX+b\),若\(M\)可逆就有, \(X=M^{-1}NX+M^{-1}b\)
• 真解换成数值解
  • \(X^{(k+1)}=BX^{(k)}+d,k=0,1,\cdots\)

注意:\(B\)的选取极为关键,它绝对了收敛性.

# 迭代法

定义:若\(X=BX+d\)是\(AX=b\)的同解方程组,对\(\forall X^{(0)}\in \R^{n}\),迭代\(X^{(k+1)}=BX^{(k)}+d,k=0,1,\cdots\),得到的\(\{X^{(k)}\}\)有极限,称迭代是收敛的.

定理:(迭代收敛判定定理)迭代\(X^{(k+1)}=BX^{(k)}+d,k=0,1,\cdots\)收敛,等价于\(B\)为收敛矩阵,或者说\(B^k\rightarrow 0\),即\(\rho(B)<1\).

Proof: 记\(X^*\)为迭代方程\(X=BX+d\)的解,即 \[X^*=BX^*+d\] 误差 \[e^{(k)}=X^*-X^{(k)}\] 由\(X^{(k+1)}=BX^{(k)}+d,k=0,1,\cdots\),知 \[e^{(k+1)}=X^*-X^{(k+1)}=B(X^*-X^{(k)})=Be^{(k)}\] 于是 \[e^{(k+1)}=B^{(k+1)}e^{(0)}\] 因为\(e^{(0)}\)为有界向量,则 \[e^k\rightarrow 0\Leftrightarrow B^k\rightarrow 0\] 由第一章定理知,\(B^k\rightarrow 0\)等价于\(\rho(B)<1\).

推论:(充分条件)若\(||B||<1\),则迭代\(X^{(k+1)}=BX^{(k)}+d,k=0,1,\cdots\)收敛.

Proof:由第一章推论知道, \[\rho(B)\leq||B||<1\] 收敛.

Jacobi 迭代

Jacobi 迭代公式(分量形式,用于计算)

对\(AX=b\)的分量形式: \[\sum_{j=1}^n a_{ij}x_j=b_i,i=1,2,\cdots,n\]

1. 方程改写:若\(a_{ii}\neq 0\),则可等价改写成 \[a_{ii}x_i=b_i-\sum_{j\neq i}^n a_{ij}x_j\] 即 \[x_i=\frac{1}{a_{ii}}(b_i-\sum_{j\neq i}^n a_{ij}x_j)\]
2. 真解改数值解 任取\(X^{(0)}\in \R^{n}\),迭代方程. \[x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum_{j\neq i}^n a_{ij}x_j^{(k)})\] 即, \[ \left\{\begin{aligned} x_{1}^{(k+1)} &=\frac{-1}{a_{11}}\left(\qquad a_{12} x_{2}^{(k)}+a_{13} x_{3}^{(k)}+\cdots+a_{1 n} x_{n}^{(k)}-b_{1}\right) \\ x_{2}^{(k+1)} &=\frac{-1}{a_{22}}\left(a_{21} x_{1}^{(k)} \qquad+a_{23} x_{3}^{(k)}+\cdots+a_{2 n} x_{n}^{(k)}-b_{2}\right) \\ & \vdots \\ x_{n}^{(k+1)} &=\frac{-1}{a_{n n}}\left(a_{n 1} x_{1}^{(k)}+a_{n 2} x_{2}^{(k)}+\cdots+a_{n n-1} x_{n-1}^{(k)} \qquad-b_{n}\right) \end{aligned}\right. \]

迭代矩阵及收敛定理

记\(A=D-L-U\),其中 \[ D=\left(\begin{array}{llll} a_{11} & & & \\ & a_{22} & & \\ & & \ddots & \\ & & & a_{n n} \end{array}\right) \] \[ L=\left(\begin{array}{ccc} 0 & & \\ a_{21} & 0 & \\ \vdots & & \\ a_{n 1}&\cdots & a_{n n-1} & 0 \end{array}\right) \] \[ U=\begin{pmatrix} 0& a_{12}& \cdots & a_{1n} \\ 0& 0& & \vdots \\ \vdots & \vdots & & a_{n-1n} \\ 0& 0& \cdots & 0 \end{pmatrix} \] 于是\(AX=b\),等价于\((D-L-U)X=b\),推出 \[DX=(L+U)X+b\] 即有, \[ X=D^{-1}(L+U)X+D^{-1}b \] 从而Jacobi迭代矩阵为 \[B_J=D^{-1}(L+U)=D^{-1}(D-A)\\=I-D^{-1}A\]

命题:(对角占优性质)若\(A\)是严格对角占优,则\(A\)非奇异.

Proof:仅考虑\(A\)为严格行对角占优情形(对于列占优,只需考虑\(A^T\)即可). 用反证,若\(A\)奇异,则齐次方程组\(AX=0\)有非零解,记为\(X=(x_1,\cdots,x_n)^T\neq 0\)记\(|x_k|=\max_{i}|x_i|\neq 0\), 考虑\(AX=0\)的第\(看\)个方程, \[a_{k 1} x_{1}+a_{k2} x_{2}+\cdots+a_{k n} x_{n}=0 \] 有 \[a_{kk}=-\sum_{j\neq k}a_{kj}x_j\] 于是有, \[ \begin{split} |a_{kk}||x_k|&=|a_{kk}x_k|\\&=|-\sum_{j\neq k}a_{kj}x_j|\\&=\sum_{j\neq k}|a_{kj}||x_j|\\&=\sum_{j\neq k}|a_{kj}||x_k| \end{split} \] 从而有 \[|a_{kk}|\leq \sum_{j\neq k}|a_{kj}|\] 矛盾.

定理:(Jacodbi 迭代收敛判断定理)若\(AX=b\)的系数矩阵\(A\)满足一下的任意一条, - \(A\)为严格行对角占优 \[|a_{ii}|>\sum_{j\neq i}|a_{ij}|,i=1,\cdots,n\] - \(A\)为严格列对角占优 \[|a_{jj}|>\sum_{i\neq j}|a_{ij}|,j=1,\cdots,n\] - \(A\)的元素满足: \[\sum_{i\neq j}\frac{|a_{ij}|}{|a_{ii}|}<1,j=1,\cdots,n\]

Proof: 1. 考虑Jacobi的迭代矩阵\(B_J=I-D^{-1}A\)则, \[ B_{J}=\left(\begin{array}{ccc} 1 & & \\ & \ddots & \\ & & 1 \end{array}\right)-\left(\begin{array}{cccc} 1 & \frac{a_{12}}{a_{11}} & \cdots & \frac{a_{1 n}}{a_{11}} \\ & & & \\ \frac{a_{21}}{a_{22}} & 1 & \cdots & \frac{a_{2 n}}{a_{22}} \\ \vdots & & & \\ \frac{a_{n n}}{a_{n n}} & & \frac{a_{n n-1}}{a_{n n}} & 1 \end{array}\right) \]

\[ B_J= \left(\begin{array}{cccc} 0 & -\frac{a_{12}}{a_{11}} & \cdots & -\frac{a_{1 n}}{a_{11}} \\ -\frac{a_{21}}{a_{22}} & 0 & \cdots & -\frac{a_{2 n}}{a_{22}} \\ \vdots&\vdots&&\vdots\\ -\frac{a_{n 1}}{a_{n n}} & -\frac{a_{n 2}}{a_{n n}} & \cdots & 0 \end{array}\right) \]

即\((B_J)_{ij}=-\frac{a_{ij}}{a_{ii}},j\neq i,\quad (B_J)_{ii}=0,i=1,\cdots,n\) 于是, \[||B_J||_{\infty}=\max_{1\leq i\leq n}\]

3. 考虑Jacobi迭代矩阵\(B_J=I-D^{-1}(L+U)\),其特征多项式为:

\[ \begin{split} P_{B_J}(\lambda)&=|\lambda I-B_J|=|\lambda I-D^{-1}(L+U)|\\ &=|D^{-1}\lambda D-D^{-1}(L+U)|\\ &=|D^{-1}||\lambda D-L-U| \end{split} \]

因\(A\)严格列对角占优,则\(|a_{jj}|>\) ????????????????????

Gauss-Seidel 迭代

Guass-Seidel 迭代公式

迭代矩阵及收敛定理

定理:若\(A\)为严格的行或者列对角占优,则Guass-Seidel迭代收敛.

Proof: 若\(A\)为严格行对角占优,考虑Guass-Seidel的迭代矩阵, \[B_G=(D-L)^{-1}U\] 其特征多项式为 \[\begin{split} P_{B_G}(\lambda)&=|\lambda I-B_G|=|\lambda I-(D-L)^{-1}U|\\ &=|\lambda (D-L)^{-1}(D-L)-(D-L)^{-1}U|\\ &=|(D-L)^{-1}(\lambda D-\lambda L-U)|\\ &=|(D-L)^{-1}||\lambda D-\lambda L-U| \end{split}\] 因为\(D-L\)为下三角矩阵,显然\(|D-L|=a_{11}\cdots a_{nn}\) 记\(C=\lambda D-\lambda L-U\), \[ C=\begin{pmatrix} \lambda a_{11}& a_{12}& \cdots & a_{1n} \\ \lambda a_{21}& \lambda a_{22}& & \vdots \\ \vdots & \vdots & & a_{n-1n} \\ \lambda a_{n1}& \lambda a_{n2}& \cdots & \lambda a_{nn} \end{pmatrix} \] 于是\(|C|=0\)的根就是\(B_G\)的特征值.由收敛矩阵的判定定理,当\(|C|=0\)时,有\(|\lambda| < 1\),因为,如果有\(|\lambda|\geq 1\),则 \[ \begin{split} |C_{ii}|&=|\lambda||a_{ii}|>|\lambda|(\sum_{j=1}^{i-1}|a_{ij}|+\sum_{j=i+1}^{n}|a_{ij}|)\\ &\geq \sum_{j=1}^{i-1}|\lambda a_{ij}|+\sum_{j=i+1}^{n}|a_{ij}|=\sum_{j\neq i}|C_{ii}| \end{split} \] 于是可得\(C\)为严格对角占优矩阵,那么由之前的命题可知\(C\)为非奇异阵,即\(|C|\neq 0\),矛盾.

定理:若\(A\)为对称正定阵,则Guass-Seidel迭代收敛.

Proof: 记\(v\)为\(B_G=(D-L)^{-1}U\)从属于特征值\(\lambda\)的特征向量,即 \[(D-L)^{-1}Uv=\lambda v\] 变形 \[Uv=\lambda (D-L)v\] 因为\(A\)对称,所以有\(U=L^T\),于是 \[L^T v=\lambda (D-L)v\] 上式左乘\(v^*=\bar{v}^T\),得 \[v^*L^Tv=\lambda v^*(D-L)v\] \[v^*L^Tv=\lambda v^*Dv-\lambda v^*Lv\qquad (*)\] 记\(\delta=v^*Dv=\sum_{i=1}^{n}\bar{v_i}a_{ii}v_i=\sum_{i=1}^{n}a_{ii}|v_i|^2>0\)(因为\(A\)正定,其对角线元素大于零) 记\(v^*Lv=\alpha+i\beta\)可以发现, \(v^*L^Tv=v^*L^*v=(Lv)^*v=(Lv,v)=\bar{(v,Lv)}=\bar{v^*Lv}=\bar{\alpha+i\beta}=\alpha-i\beta\) 则\((*)\)式化为, \[ \lambda(\delta-\alpha-i\beta)=\alpha-i\beta \] 两边取模的平方得, \[ |\lambda|^2((\delta-\alpha)^2+\beta^2)=\alpha^2+\beta^2 \] 因为\(A\)正定,则有 \[\begin{split} 0<v^*Av&=v^*(D-L-U)v\\ &=v^*Dv-v^*Lv-v^*L^Tv\\ &=\delta-(\alpha+i\beta)-(\alpha-i\beta)\\ &=\delta-2\alpha \end{split}\] 考虑到, \[\begin{split} &((\delta-\alpha)^2+\beta^2)-(\alpha^2+\beta^2)\\ &=\delta^2-2\delta\alpha\\ &=\delta(\delta-2\alpha)\\ &>0 \end{split}\] 即,\(((\delta-\alpha)^2+\beta^2)>\alpha^2+\beta^2\) 从而应有\(|\lambda|<1\),迭代收敛性得证.

逐次超松驰迭代(SOR)

SOR是Gauss-Seidel迭代的加速.

计算公式

迭代矩阵

\[B_{SOR}=(D-\omega L)^{-1}((1-\omega)D+\omega U)\]

收敛定理

定理:SOR迭代的 必要条件是: \[0<\omega<2\]

Proof: 若SOR迭代收敛,则有\(\rho(B_{SOR})<1\),记SOR迭代矩阵的特征值为, \[\lambda_1,\cdots,\lambda_n\] 则,\(det(B_{SOR})=\lambda_1\cdots\lambda_n\) 于是, \[|det(B_{SOR})|=|\lambda_1\cdots\lambda_n|\leq \rho^n(B_{SOR})\] 即, \[|det(B_{SOR})|^{\frac{1}{n}}\leq \rho(B_{SOR})<1\] 另一方面, \[ det(B_{SOR})=det((D-\omega L)^{-1})det((1-\omega)D+\omega U) \] 而, \[det((D-\omega L)^{-1})=1/(a_{11}\cdots a_{nn})\] \[det((1-\omega)D+\omega U)=(1-\omega)^n (a_{11}\cdots a_{nn})\] 于是得到, \[det(B_{SOR})=det((D-\omega L)^{-1})det((1-\omega)D+\omega U)=(1-\omega)^n\] 故有, \[ |(1-\omega)^n|^{\frac{1}{n}}<1 \] \[0<\omega<2\]

注记：\(det(A)=\lambda_1\cdots\lambda_n\) 证明: 记\(A=TJT^{-1}\),其中\(T\)为可逆矩阵,\(J\)为若尔当阵. \[det(A)=det(J)=det(J_1)\cdots det(J_r)=\lambda_1^{n_1}\cdots\lambda^{n_r}_r\] 其中\(n_1+\cdots+n_r=n\),重根按重数算即得,\(det(A)=\lambda_1\cdots\lambda_n\).

定理:若\(A\)为对称正定阵,\(0<\omega<2\),则SOR迭代收敛.

Proof:与上面的定理证明类似,只需要考虑, \[B_{SOR}=(D-\omega L)^{-1}((1-\omega)D+\omega U)\] 的谱半径.

迭代停止准则及收敛速度

迭代停止准则

定理:若\(X^{(k+1)}=BX^{(k)}+d,k=0,1,\cdots\),满足 \[||B||\overset{\Delta}{=}L<1\] 则有, \[ \begin{split} (1&)||X^*-X^{(k)}||\leq\frac{L}{1-L}||X^{(k)}-X^{(k-1)}||\\ (2&)||X^*-X^{(k)}||\leq\frac{L^k}{1-L}||X^{(1)}-X^{(0)}|| \end{split} \] 其中\(X^*\)为\(AX=b\)的精确解.

Proof:考虑\(||X^{(k+1)}-X^{(k)}||\),

\[\begin{split} ||X^{(k+1)}-X^{(k)}||&=||X^*-X^{(k)}-(X^*-X^{(k+1)})||\\ &\geq||X^*-X^{(k)}||-||X^*-X^{(k+1)}||\\ &=||X^*-X^{(k)}||-||(BX^{*}+d)-(BX^{(k)}+d)||\\ &=||X^*-X^{(k)}||-||B(X^{*}-X^{(k)})||\\ &\geq ||X^*-X^{(k)}||-||B||||X^{*}-X^{(k)}|| \end{split}\]

于是, \[||X^*-X^{(k)}||\leq\frac{1}{1-L}||X^{(k+1)}-X^{(k)}||\\\] \[= \frac{1}{1-L}||B(X^{(k)}-X^{(k-1)})||\leq\frac{L}{1-L}||X^{(k)}-X^{(k-1)}||\] (1)得证.又容易发现, \[\frac{L}{1-L}||X^{(k)}-X^{(k-1)}||=\frac{L}{1-L}||B(X^{(k-1)}-X^{(k-2)})||\leq\frac{L^2}{1-L}||X^{(k-1)}-X^{(k-2)}||\] 如此反复就可以得到(2).

迭代收敛速度

\[ e^{(k+1)}=X^*-X^{(k+1)}=B(X^*-X^{(k)})=Be^{(k)}=\cdots=B^{k+1}e^{(0)} \] 即, \[ ||e^{(k)}||=||B^{k}e^{(0)}||\leq ||B^{k}||||e^{(0)}||\leq||B||^k||e^{(0)}||<\delta \] 当迭代收敛时只需考虑\(||B||^k<\delta\), 因\(B^k=TJ^kT^{-1}\)反映了特征值\(\lambda_i\) 可考虑\(\rho^k(B)<\delta\)且\(\rho(B)<1,k\)为迭代次数, 取对数有,\(k\lg\rho(B)<\lg\delta\),即\(k>\frac{\lg\delta}{\rho(B)}=\frac{-\lg\delta}{-\rho(B)}\) 称,\(R(B)=-\lg\rho(B)\)为迭代法\(X^{(k+1)}=BX^{(k)}+d\)的收敛速度.

最速下降法及共轭梯度法

对称正定方程组的求解

等价性定理

对\(AX=b\),考虑二次型 \[f(X)=\frac{1}{2}(AX,X)-(b,X)=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}x_ix_j-\sum_{j=1}^{n}b_jx_j\] 其中\(A\)对称正定,\((X,Y)=X^TY\)

引理:若\(A\)对称正定,则 (1)\((AX,Y)=(AY,X)\) (2)\(\forall x,y\in R^{n}\)及\(r\in R\),有 \[f(X+tY)=\frac{t^2}{2}(AY,Y)-t(b-AX,Y)+f(X)\] (3)\(\nabla f(X)=AX-b\overset{\Delta}{=}-r\),其中\(r=-\nabla f(X)=b-AX\).

Proof: (1) \[ (AX,Y)=X^TA^TY=X^TAY=(X^TAY)^T=Y^TA^TX=(AY,X) \] (2) \[ \begin{split} f(X+tY)=&\frac{1}{2}(A(X+tY),X+tY)-(b,X+tY)\\ =&\frac{1}{2}(AX,X)+\frac{t}{2}(AY,X)+\frac{t}{2}(AX,Y)+\frac{t^2}{2}(AY,Y)-(b,X)-t(b,Y)\\ =&\frac{1}{2}(AX,X)-(b,X)+t(AX,Y)-t(b,Y)+\frac{t^2}{2}(AY,Y)\\ =&f(X)+\frac{t^2}{2}(AY,Y)-t(b-AX,Y) \end{split} \] (3) \[f(X)=\frac{1}{2}(AX,X)-(b,X)=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}x_ix_j-\sum_{j=1}^{n}b_jx_j\] 而, \[ \nabla f(X)=\begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \vdots\\ \frac{\partial f}{\partial x_n} \end{pmatrix}=AX-b \] 验证起来是简单的.

定理:(等价性定理)若\(A\)对称正定,则求\(AX=b\)的解\(X^*\)等价于求 \[f(X)=\frac{1}{2}(AX,X)-(b,X)\] 的最小点\(X^*\).

证明:

最速下降法

\(\nabla f(X)=AX-b\overset{\Delta}{=}-r,\quad\)\(r=-\nabla f(X)=b-AX\). \(\nabla f(X)\)为函数增长最快的方向, \(r=-\nabla f(X)\)为函数下降最快的方向,所以写成这种形式。