大型稀疏方程组可能难以直接分解,因为消元会产生新的非零项。迭代法则利用原方程反复更新近似解。这可能发挥稀疏性的优势,但更新规则不会自动收敛:矩阵、更新顺序以及松弛参数都会影响迭代。
设 A ∈ R n × n A\in\mathbb R^{n\times n} A ∈ R n × n 的对角元素非零,b ∈ R n b\in\mathbb R^n b ∈ R n 。写 A = D + L + U A=D+L+U A = D + L + U ,其中 D D D 为对角部分,L , U L,U L , U 分别为严格下、上三角部分;它们的符号与 A A A 中的项相同,有些教材则取相反符号。固定解 x ∗ x^* x ∗ 满足 A x ∗ = b Ax^*=b A x ∗ = b 。讨论收敛到唯一解时,非奇异性要么是明确假设,要么由其他假设推出。
三种更新方式
Jacobi 法只使用上一轮的分量计算每个新分量:
x i ( k + 1 ) = 1 a i i ( b i − ∑ j ≠ i a i j x j ( k ) ) , x ( k + 1 ) = B J x ( k ) + D − 1 b , B J = − D − 1 ( L + U ) . x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right),\qquad
x^{(k+1)}=B_Jx^{(k)}+D^{-1}b,\quad B_J=-D^{-1}(L+U). x i ( k + 1 ) = a ii 1 b i − j = i ∑ a ij x j ( k ) , x ( k + 1 ) = B J x ( k ) + D − 1 b , B J = − D − 1 ( L + U ) .
定义 3.1.2
(Gauss–Seidel 迭代)
Gauss–Seidel 法按 1 , … , n 1,\ldots,n 1 , … , n 的顺序,一得到新分量便立即使用:
x i ( k + 1 ) = b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) a i i , B G S = − ( D + L ) − 1 U . x_i^{(k+1)}=\frac{b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}}{a_{ii}},\qquad
B_{GS}=-(D+L)^{-1}U. x i ( k + 1 ) = a ii b i − ∑ j < i a ij x j ( k + 1 ) − ∑ j > i a ij x j ( k ) , B GS = − ( D + L ) − 1 U .
这里的逆矩阵表示解一个三角方程组;实现时不必显式构造它。改变排序通常会改变 L , U L,U L , U ,因此也改变迭代。Jacobi 的各分量更新可同时计算,而 Gauss–Seidel 在一轮中使用新近算出的值。
逐次超松弛法(SOR)将每个旧分量向当前 Gauss–Seidel 值移动一个加权步长。对实参数 ω \omega ω ,其分量公式为
x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω a i i ( b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) ) . x_i^{(k+1)}=(1-\omega)x_i^{(k)}+
\frac{\omega}{a_{ii}}\left(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\right). x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + a ii ω ( b i − j < i ∑ a ij x j ( k + 1 ) − j > i ∑ a ij x j ( k ) ) . 矩阵形式为 x ( k + 1 ) = B ω x ( k ) + ω ( D + ω L ) − 1 b x^{(k+1)}=B_\omega x^{(k)}+\omega(D+\omega L)^{-1}b x ( k + 1 ) = B ω x ( k ) + ω ( D + ω L ) − 1 b ,其中
B ω = ( D + ω L ) − 1 ( ( 1 − ω ) D − ω U ) . B_\omega=(D+\omega L)^{-1}\bigl((1-\omega)D-\omega U\bigr). B ω = ( D + ω L ) − 1 ( ( 1 − ω ) D − ω U ) .
D + ω L D+\omega L D + ω L 是三角矩阵,且与 D D D 有相同的非零对角线,因此非奇异。ω = 1 \omega=1 ω = 1 时是 Gauss–Seidel;ω = 0 \omega=0 ω = 0 时不作更新。通常 1 < ω < 2 1<\omega<2 1 < ω < 2 称为超松弛,0 < ω < 1 0<\omega<1 0 < ω < 1 称为欠松弛。
谱半径判据
对任意定常迭代 x ( k + 1 ) = B x ( k ) + c x^{(k+1)}=Bx^{(k)}+c x ( k + 1 ) = B x ( k ) + c ,若其不动点为 x ∗ x^* x ∗ ,误差满足
e ( k + 1 ) = B e ( k ) , e ( k ) = B k e ( 0 ) , e ( k ) = x ( k ) − x ∗ . e^{(k+1)}=Be^{(k)},\qquad e^{(k)}=B^ke^{(0)},\qquad e^{(k)}=x^{(k)}-x^*. e ( k + 1 ) = B e ( k ) , e ( k ) = B k e ( 0 ) , e ( k ) = x ( k ) − x ∗ .
在有限维空间中,迭代从每个初始向量收敛到 x ∗ x^* x ∗ ,当且仅当 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ;这里 ρ ( B ) \rho(B) ρ ( B ) 是 B B B 的特征值模的最大值。
若 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ,复 Jordan 分解将 B k B^k B k 表示为有限多个项的组合,每项可由 k k k 的多项式乘特征值 λ \lambda λ 的 ∣ λ ∣ k |\lambda|^k ∣ λ ∣ k 来控制,故每项趋于零,B k → 0 B^k\to0 B k → 0 。反过来,若某个特征值的模至少为一,矩阵幂作用于对应复特征向量时不能趋于零。若对所有实初始向量都收敛,则由线性性对所有复向量也趋于零,矛盾。
若 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ,则 1 不是 B B B 的特征值,故 I − B I-B I − B 可逆,不动点唯一存在且等于 ( I − B ) − 1 c (I-B)^{-1}c ( I − B ) − 1 c 。该判据讨论的是每个 初始向量。某个特殊初始误差若没有不稳定方向的分量,可能表现得更好。另外,在某个从属范数下 ∥ B ∥ < 1 \|B\|<1 ∥ B ∥ < 1 是充分条件;范数大于一却不能证明发散,因为只要 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ,矩阵幂仍可能衰减。
设 B = ( 0 10 0 0 ) B=\begin{pmatrix}0&10\\0&0\end{pmatrix} B = ( 0 0 10 0 ) 。则 ∥ B ∥ ∞ = 10 > 1 \|B\|_\infty=10>1 ∥ B ∥ ∞ = 10 > 1 ,但 B 2 = 0 B^2=0 B 2 = 0 ,所以对任意初始向量都有 e ( 2 ) = B 2 e ( 0 ) = 0 e^{(2)}=B^2e^{(0)}=0 e ( 2 ) = B 2 e ( 0 ) = 0 ,迭代两步就收敛。判据看的是 ρ ( B ) \rho(B) ρ ( B ) (这里等于 0 0 0 ),而不是某一个范数:范数小于一是充分条件,范数大于一则什么也不能说明。
命题 3.1.5
(严格行对角占优下的 Jacobi 法)
若每行都满足 ∣ a i i ∣ > ∑ j ≠ i ∣ a i j ∣ |a_{ii}|>\sum\limits_{j\ne i}|a_{ij}| ∣ a ii ∣ > j = i ∑ ∣ a ij ∣ ,则 A A A 非奇异,∥ B J ∥ ∞ < 1 \|B_J\|_\infty<1 ∥ B J ∥ ∞ < 1 ,Jacobi 法从任意初值收敛。
B J B_J B J 第 i i i 行元素的绝对值之和为 ∑ j ≠ i ∣ a i j ∣ / ∣ a i i ∣ < 1 \sum\limits_{j\ne i}|a_{ij}|/|a_{ii}|<1 j = i ∑ ∣ a ij ∣/∣ a ii ∣ < 1 ,故 ∥ B J ∥ ∞ < 1 \|B_J\|_\infty<1 ∥ B J ∥ ∞ < 1 ,从而 ρ ( B J ) < 1 \rho(B_J)<1 ρ ( B J ) < 1 ,由谱半径判据得收敛。若 A x = 0 Ax=0 A x = 0 且 ∣ x i ∣ = ∥ x ∥ ∞ > 0 |x_i|=\|x\|_\infty>0 ∣ x i ∣ = ∥ x ∥ ∞ > 0 ,第 i i i 行给出 ∣ a i i ∣ ∣ x i ∣ ≤ ∑ j ≠ i ∣ a i j ∣ ∣ x j ∣ < ∣ a i i ∣ ∣ x i ∣ |a_{ii}||x_i|\le\sum\limits_{j\ne i}|a_{ij}||x_j|<|a_{ii}||x_i| ∣ a ii ∣∣ x i ∣ ≤ j = i ∑ ∣ a ij ∣∣ x j ∣ < ∣ a ii ∣∣ x i ∣ ,矛盾;所以 A A A 非奇异。
同一假设下的 Gauss–Seidel 法。 Jacobi 的界只是直接的行和估计,因为 B J = − D − 1 ( L + U ) B_J=-D^{-1}(L+U) B J = − D − 1 ( L + U ) 的元素一目了然。Gauss–Seidel 矩阵 B G S = − ( D + L ) − 1 U B_{GS}=-(D+L)^{-1}U B GS = − ( D + L ) − 1 U 含有逆矩阵,无法用同样方式读出各行。有用的思路是:不构造逆矩阵,而是通过定义 y = B G S x y=B_{GS}x y = B GS x 的三角方程组来估计它。对每一行,把非对角权重分成对角线之前与之后两部分:
α i = 1 ∣ a i i ∣ ∑ j < i ∣ a i j ∣ , β i = 1 ∣ a i i ∣ ∑ j > i ∣ a i j ∣ . \alpha_i=\frac1{|a_{ii}|}\sum_{j<i}|a_{ij}|,\qquad
\beta_i=\frac1{|a_{ii}|}\sum_{j>i}|a_{ij}|. α i = ∣ a ii ∣ 1 j < i ∑ ∣ a ij ∣ , β i = ∣ a ii ∣ 1 j > i ∑ ∣ a ij ∣.
严格行对角占优恰好表示每个 i i i 都有 α i + β i < 1 \alpha_i+\beta_i<1 α i + β i < 1 ,并且 ∥ B J ∥ ∞ = max i ( α i + β i ) \|B_J\|_\infty=\max\limits_i(\alpha_i+\beta_i) ∥ B J ∥ ∞ = i max ( α i + β i ) 。
定理 3.1.6
(严格行对角占优下的 Gauss–Seidel 法)
若 A A A 严格行对角占优,则
∥ B G S ∥ ∞ ≤ γ : = max 1 ≤ i ≤ n β i 1 − α i ≤ ∥ B J ∥ ∞ < 1. \|B_{GS}\|_\infty\le\gamma:=\max_{1\le i\le n}\frac{\beta_i}{1-\alpha_i}\le\|B_J\|_\infty<1. ∥ B GS ∥ ∞ ≤ γ := 1 ≤ i ≤ n max 1 − α i β i ≤ ∥ B J ∥ ∞ < 1. 因此 Gauss–Seidel 从任意初始向量收敛到唯一解,且 ∥ e ( k ) ∥ ∞ ≤ γ k ∥ e ( 0 ) ∥ ∞ \|e^{(k)}\|_\infty\le\gamma^k\|e^{(0)}\|_\infty ∥ e ( k ) ∥ ∞ ≤ γ k ∥ e ( 0 ) ∥ ∞ 。
每个 α i < 1 \alpha_i<1 α i < 1 ,所以分母 1 − α i 1-\alpha_i 1 − α i 均为正,γ \gamma γ 有定义。固定满足 ∥ x ∥ ∞ = 1 \|x\|_\infty=1 ∥ x ∥ ∞ = 1 的 x x x ,令 y = B G S x y=B_{GS}x y = B GS x 。则 ( D + L ) y = − U x (D+L)y=-Ux ( D + L ) y = − U x ,其第 i i i 行为
a i i y i = − ∑ j < i a i j y j − ∑ j > i a i j x j . a_{ii}y_i=-\sum_{j<i}a_{ij}y_j-\sum_{j>i}a_{ij}x_j. a ii y i = − j < i ∑ a ij y j − j > i ∑ a ij x j . 这正是对误差 x x x 作一轮 Gauss–Seidel:j < i j<i j < i 的 y j y_j y j 是本轮已更新的分量。若 y = 0 y=0 y = 0 ,无需证明。否则取 i i i 使 ∣ y i ∣ = ∥ y ∥ ∞ |y_i|=\|y\|_\infty ∣ y i ∣ = ∥ y ∥ ∞ 。将第 i i i 行除以 ∣ a i i ∣ |a_{ii}| ∣ a ii ∣ ,并利用 ∣ y j ∣ ≤ ∥ y ∥ ∞ |y_j|\le\|y\|_\infty ∣ y j ∣ ≤ ∥ y ∥ ∞ 与 ∣ x j ∣ ≤ 1 |x_j|\le1 ∣ x j ∣ ≤ 1 :
∥ y ∥ ∞ ≤ α i ∥ y ∥ ∞ + β i , 故 ∥ y ∥ ∞ ≤ β i 1 − α i ≤ γ . \|y\|_\infty\le\alpha_i\|y\|_\infty+\beta_i,
\qquad\text{故}\qquad
\|y\|_\infty\le\frac{\beta_i}{1-\alpha_i}\le\gamma. ∥ y ∥ ∞ ≤ α i ∥ y ∥ ∞ + β i , 故 ∥ y ∥ ∞ ≤ 1 − α i β i ≤ γ . 对所有单位向量 x x x 取最大值,得 ∥ B G S ∥ ∞ ≤ γ \|B_{GS}\|_\infty\le\gamma ∥ B GS ∥ ∞ ≤ γ 。至于与 Jacobi 的比较,对每一行有
( α i + β i ) ( 1 − α i ) − β i = α i ( 1 − α i − β i ) ≥ 0 , (\alpha_i+\beta_i)(1-\alpha_i)-\beta_i=\alpha_i(1-\alpha_i-\beta_i)\ge0, ( α i + β i ) ( 1 − α i ) − β i = α i ( 1 − α i − β i ) ≥ 0 , 故 β i / ( 1 − α i ) ≤ α i + β i ≤ ∥ B J ∥ ∞ \beta_i/(1-\alpha_i)\le\alpha_i+\beta_i\le\|B_J\|_\infty β i / ( 1 − α i ) ≤ α i + β i ≤ ∥ B J ∥ ∞ 。从属范数是谱半径的上界,所以 ρ ( B G S ) ≤ γ < 1 \rho(B_{GS})\le\gamma<1 ρ ( B GS ) ≤ γ < 1 ,由谱半径定理得收敛。前面的对角占优论证说明 A A A 非奇异,所以极限就是唯一解。每轮使用一次范数界,即得所述误差估计。
证明透视
更新后的分量在估计中的作用 证明说明了新算出的值所起的作用。在第 i i i 行中,已更新的分量以总权重 α i \alpha_i α i 出现,而它们又受正在估计的同一个未知量 ∥ y ∥ ∞ \|y\|_\infty ∥ y ∥ ∞ 控制。把这一项移到左边后,所得因子不大于 Jacobi 的行和。该结论比较的是最大范数下最坏情形的一轮因子。它本身并不断言每个对角占优矩阵都有 ρ ( B G S ) ≤ ρ ( B J ) \rho(B_{GS})\le\rho(B_J) ρ ( B GS ) ≤ ρ ( B J ) ,也不断言从任意初值出发每一轮 Gauss–Seidel 的误差都较小。若用同一个置换同时重排方程与未知量,严格行对角占优得以保持,因此对每种这样的排序都收敛;但 γ \gamma γ 的值取决于哪些元素落在对角线之前。
取下文二阶比较中的矩阵 A = ( 4 1 1 3 ) A=\begin{pmatrix}4&1\\1&3\end{pmatrix} A = ( 4 1 1 3 ) ,它满足 4 > 1 4>1 4 > 1 与 3 > 1 3>1 3 > 1 ,因此严格行对角占优。其行权重为 α 1 = 0 \alpha_1=0 α 1 = 0 、β 1 = 1 / 4 \beta_1=1/4 β 1 = 1/4 、α 2 = 1 / 3 \alpha_2=1/3 α 2 = 1/3 、β 2 = 0 \beta_2=0 β 2 = 0 。于是 ∥ B J ∥ ∞ = 1 / 3 \|B_J\|_\infty=1/3 ∥ B J ∥ ∞ = 1/3 ,γ = max { 1 / 4 , 0 } = 1 / 4 \gamma=\max\{1/4,0\}=1/4 γ = max { 1/4 , 0 } = 1/4 。下文算出的 B G S B_{GS} B GS 各行绝对值之和为 1 / 4 1/4 1/4 与 1 / 12 1/12 1/12 ,所以 ∥ B G S ∥ ∞ = 1 / 4 \|B_{GS}\|_\infty=1/4 ∥ B GS ∥ ∞ = 1/4 ,此例中界恰好取到。
反例模式
Gauss–Seidel 不一定优于 Jacobi 若没有这类假设,两种方法互不占优,所以“Gauss–Seidel 总是不比 Jacobi 差”的预期并不成立。本文稍后有一个 SPD 矩阵的例子:Jacobi 发散而 Gauss–Seidel 收敛。反方向的例子是
A = ( 1 2 − 2 1 1 1 2 2 1 ) , B J = ( 0 − 2 2 − 1 0 − 1 − 2 − 2 0 ) , B G S = ( 0 − 2 2 0 2 − 3 0 0 2 ) . A=\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix},\qquad
B_J=\begin{pmatrix}0&-2&2\\-1&0&-1\\-2&-2&0\end{pmatrix},\qquad
B_{GS}=\begin{pmatrix}0&-2&2\\0&2&-3\\0&0&2\end{pmatrix}. A = 1 1 2 2 1 2 − 2 1 1 , B J = 0 − 1 − 2 − 2 0 − 2 2 − 1 0 , B GS = 0 0 0 − 2 2 0 2 − 3 2 . 这里 det A = 1 \det A=1 det A = 1 ,且没有一行对角占优。沿第一行展开 det ( λ I − B J ) \det(\lambda I-B_J) det ( λ I − B J ) 得 λ 3 \lambda^3 λ 3 ,故 B J 3 = 0 B_J^3=0 B J 3 = 0 :在精确算术下,Jacobi 从任意初值出发至多三轮便得到解。Gauss–Seidel 矩阵由逐行求解 ( D + L ) B G S = − U (D+L)B_{GS}=-U ( D + L ) B GS = − U 得到,它是上三角矩阵,特征值为 0 , 2 , 2 0,2,2 0 , 2 , 2 。初始误差 ( 1 , − 1 , 0 ) T (1,-1,0)^T ( 1 , − 1 , 0 ) T 满足 B G S ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T B_{GS}(1,-1,0)^T=2(1,-1,0)^T B GS ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T ,所以该误差每轮翻倍。
对称正定矩阵下的 Gauss–Seidel 与 SOR
现在假设 A A A 对称正定(SPD),即每个非零 v v v 满足 v T A v > 0 v^TAv>0 v T A v > 0 。则 A A A 非奇异,且所有 a i i > 0 a_{ii}>0 a ii > 0 。考虑二次函数
Q ( x ) = 1 2 x T A x − b T x . Q(x)=\frac12x^TAx-b^Tx. Q ( x ) = 2 1 x T A x − b T x .
更新第 i i i 个分量时,令 r i = b i − ( A x ) i r_i=b_i-(Ax)_i r i = b i − ( A x ) i 为当前混合向量的残差分量:本轮较早的分量已更新。SOR 将该分量改变 d = ω r i / a i i d=\omega r_i/a_{ii} d = ω r i / a ii 。展开二次函数得
Q ( x + d e i ) − Q ( x ) = − d r i + 1 2 a i i d 2 = − ω ( 2 − ω ) 2 a i i r i 2 . Q(x+de_i)-Q(x)=-d r_i+\frac12a_{ii}d^2
=-\frac{\omega(2-\omega)}{2a_{ii}}r_i^2. Q ( x + d e i ) − Q ( x ) = − d r i + 2 1 a ii d 2 = − 2 a ii ω ( 2 − ω ) r i 2 .
当 0 < ω < 2 0<\omega<2 0 < ω < 2 ,每次分量更新都会降低 Q Q Q ,除非该时刻的残差分量为零。一整轮严格降低 Q Q Q ,除非起始向量已解出 A x = b Ax=b A x = b :若每一步的下降量都为零,则遇到的每个残差都为零、没有分量改变,原残差也就为零。
若 A A A 对称正定且 0 < ω < 2 0<\omega<2 0 < ω < 2 ,则 SOR 从任意初值收敛到唯一解。结论适用于任意固定的坐标顺序;特别地,ω = 1 \omega=1 ω = 1 给出 Gauss–Seidel 的收敛性。
由 A x ∗ = b Ax^*=b A x ∗ = b ,有 Q ( x ) − Q ( x ∗ ) = 1 2 ( x − x ∗ ) T A ( x − x ∗ ) Q(x)-Q(x^*)=\tfrac12(x-x^*)^TA(x-x^*) Q ( x ) − Q ( x ∗ ) = 2 1 ( x − x ∗ ) T A ( x − x ∗ ) 。一整轮对误差的作用是线性映射 B ω B_\omega B ω 。上述计算表明,对每个非零误差,∥ B ω e ∥ A < ∥ e ∥ A \|B_\omega e\|_A<\|e\|_A ∥ B ω e ∥ A < ∥ e ∥ A ,其中 ∥ e ∥ A = e T A e \|e\|_A=\sqrt{e^TAe} ∥ e ∥ A = e T A e 。在此范数的紧单位球面上,连续函数 ∥ B ω e ∥ A \|B_\omega e\|_A ∥ B ω e ∥ A 达到一个最大值 q < 1 q<1 q < 1 。故 ∥ e ( k ) ∥ A ≤ q k ∥ e ( 0 ) ∥ A → 0 \|e^{(k)}\|_A\le q^k\|e^{(0)}\|_A\to0 ∥ e ( k ) ∥ A ≤ q k ∥ e ( 0 ) ∥ A → 0 。论证使用有限维性,才能把对每个向量的严格下降变成一个共同的压缩因子。它证明了这种 q q q 存在,但没有给出可计算的数值收敛速度。
参数范围是对 SPD 矩阵的充分保证,不是对所有矩阵的普遍结论。若 A = I A=I A = I ,则 B ω = ( 1 − ω ) I B_\omega=(1-\omega)I B ω = ( 1 − ω ) I :ω = 2 \omega=2 ω = 2 时非零误差永远交替;ω > 2 \omega>2 ω > 2 或 ω < 0 \omega<0 ω < 0 时误差大小增长;ω = 0 \omega=0 ω = 0 时不变。即使 ω ∈ ( 0 , 2 ) \omega\in(0,2) ω ∈ ( 0 , 2 ) ,任意选取也不保证比 Gauss–Seidel 更快。
在下面的二阶比较中,ω = 6 / 5 \omega=6/5 ω = 6/5 给出 ρ ( B 6 / 5 ) = 1 / 5 \rho(B_{6/5})=1/5 ρ ( B 6/5 ) = 1/5 ,比同一矩阵的 Gauss–Seidel(1 / 12 1/12 1/12 )更差。定理只保证 0 < ω < 2 0<\omega<2 0 < ω < 2 时收敛,并没有说 ω > 1 \omega>1 ω > 1 就更快。好的 ω \omega ω 必须针对手头的矩阵来选。
计算比较
取
A = ( 4 1 1 3 ) , b = ( 1 2 ) , x ∗ = ( 1 / 11 7 / 11 ) . A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\qquad b=\binom12,\qquad x^*=\binom{1/11}{7/11}. A = ( 4 1 1 3 ) , b = ( 2 1 ) , x ∗ = ( 7/11 1/11 ) . A A A 是 SPD,因为对非零 x x x 有 x T A x = 4 ( x 1 + x 2 / 4 ) 2 + ( 11 / 4 ) x 2 2 > 0 x^TAx=4(x_1+x_2/4)^2+(11/4)x_2^2>0 x T A x = 4 ( x 1 + x 2 /4 ) 2 + ( 11/4 ) x 2 2 > 0 。从零出发,一轮 Jacobi 得 ( 1 / 4 , 2 / 3 ) T (1/4,2/3)^T ( 1/4 , 2/3 ) T ;一轮 Gauss–Seidel 得 ( 1 / 4 , 7 / 12 ) T (1/4,7/12)^T ( 1/4 , 7/12 ) T 。误差矩阵及其谱半径为
B J = ( 0 − 1 / 4 − 1 / 3 0 ) , ρ ( B J ) = 1 / 12 , B G S = ( 0 − 1 / 4 0 1 / 12 ) , ρ ( B G S ) = 1 / 12. B_J=\begin{pmatrix}0&-1/4\\-1/3&0\end{pmatrix},\quad
\rho(B_J)=1/\sqrt{12},\qquad
B_{GS}=\begin{pmatrix}0&-1/4\\0&1/12\end{pmatrix},\quad
\rho(B_{GS})=1/12. B J = ( 0 − 1/3 − 1/4 0 ) , ρ ( B J ) = 1/ 12 , B GS = ( 0 0 − 1/4 1/12 ) , ρ ( B GS ) = 1/12. 取 ω = 6 / 5 \omega=6/5 ω = 6/5 的 SOR 从零出发一轮得到 ( 3 / 10 , 17 / 25 ) T (3/10,17/25)^T ( 3/10 , 17/25 ) T ,且
B 6 / 5 = ( − 1 / 5 − 3 / 10 2 / 25 − 2 / 25 ) . B_{6/5}=\begin{pmatrix}-1/5&-3/10\\2/25&-2/25\end{pmatrix}. B 6/5 = ( − 1/5 2/25 − 3/10 − 2/25 ) . 它的一对共轭特征值之积为 1 / 25 1/25 1/25 ,因此模为 1 / 5 1/5 1/5 。三个谱半径均小于一,但这个超松弛参数的渐近因子比 Gauss–Seidel 大。谱半径描述最坏情形的渐近几何因子;特殊初始误差可能衰减得更快,也不能必然预言一轮之后哪种误差较小。
例题 3.1.10
(单个 SOR 坐标更新使 Q Q Q 下降)
取 A = ( 4 1 1 3 ) A=\begin{pmatrix}4&1\\1&3\end{pmatrix} A = ( 4 1 1 3 ) 、b = ( 1 , 2 ) T b=(1,2)^T b = ( 1 , 2 ) T 、x = 0 x=0 x = 0 ,更新第一个坐标。残差分量为 r 1 = b 1 − ( A x ) 1 = 1 r_1=b_1-(Ax)_1=1 r 1 = b 1 − ( A x ) 1 = 1 ,a 11 = 4 a_{11}=4 a 11 = 4 。取 ω = 6 / 5 \omega=6/5 ω = 6/5 ,则改变量 d = ω r 1 / a 11 = 3 / 10 d=\omega r_1/a_{11}=3/10 d = ω r 1 / a 11 = 3/10 ,而
Q ( x + d e 1 ) − Q ( x ) = − d r 1 + 1 2 a 11 d 2 = − 3 10 + 9 50 = − 3 25 , Q(x+de_1)-Q(x)=-dr_1+\frac12a_{11}d^2=-\frac3{10}+\frac9{50}=-\frac3{25}, Q ( x + d e 1 ) − Q ( x ) = − d r 1 + 2 1 a 11 d 2 = − 10 3 + 50 9 = − 25 3 , 与 − ω ( 2 − ω ) r 1 2 / ( 2 a 11 ) = − ( 6 / 5 ) ( 4 / 5 ) / 8 -\omega(2-\omega)r_1^2/(2a_{11})=-(6/5)(4/5)/8 − ω ( 2 − ω ) r 1 2 / ( 2 a 11 ) = − ( 6/5 ) ( 4/5 ) /8 一致。ω = 1 \omega=1 ω = 1 时 d = 1 / 4 d=1/4 d = 1/4 ,下降量为 − 1 / 8 -1/8 − 1/8 ,是沿此坐标可达的最大下降。在端点 ω = 2 \omega=2 ω = 2 处,d = 1 / 2 d=1/2 d = 1/2 ,− 1 2 + 1 2 = 0 -\frac12+\frac12=0 − 2 1 + 2 1 = 0 :完全没有下降,所以严格下降的论证需要开区间 0 < ω < 2 0<\omega<2 0 < ω < 2 。
仅有正定性不能保证 Jacobi 收敛
反例模式
正定矩阵上 Jacobi 也可以发散 令 A A A 为对角元素为 1、其他元素均为 3 / 4 3/4 3/4 的 3 × 3 3\times3 3 × 3 矩阵。其特征值为 5 / 2 , 1 / 4 , 1 / 4 5/2,1/4,1/4 5/2 , 1/4 , 1/4 ,故为 SPD。Jacobi 的 D = I D=I D = I ,B J = I − A B_J=I-A B J = I − A 的特征值为 − 3 / 2 , 3 / 4 , 3 / 4 -3/2,3/4,3/4 − 3/2 , 3/4 , 3/4 。初始误差取 ( 1 , 1 , 1 ) T (1,1,1)^T ( 1 , 1 , 1 ) T ,则每轮乘以 − 3 / 2 -3/2 − 3/2 ,因而发散。这不与上面的 SPD 定理矛盾:该定理适用于 Gauss–Seidel 与 SOR,而非 Jacobi。严格对角占优是 Jacobi 的一个充分条件,此矩阵不满足它。
残差与停止
不必知道 x ∗ x^* x ∗ 也能计算残差 r ( k ) = b − A x ( k ) r^{(k)}=b-Ax^{(k)} r ( k ) = b − A x ( k ) 。它满足 r ( k ) = − A e ( k ) r^{(k)}=-Ae^{(k)} r ( k ) = − A e ( k ) ,故 A A A 非奇异时,在相容范数下 ∥ e ( k ) ∥ ≤ ∥ A − 1 ∥ ∥ r ( k ) ∥ \|e^{(k)}\|\le\|A^{-1}\|\|r^{(k)}\| ∥ e ( k ) ∥ ≤ ∥ A − 1 ∥∥ r ( k ) ∥ 。只有尺度和条件性允许时,小残差才能保证小的前向误差。实际中可监控缩放残差并设置最大迭代次数;相邻迭代值之差很小也可能是停滞。有限精度还限制可达到的精度,而精确算术下的收敛证明并不给出通用停止阈值。
设 A = diag ( 1 , 10 − 3 ) A=\operatorname{diag}(1,10^{-3}) A = diag ( 1 , 1 0 − 3 ) 、e = ( 0 , 1 ) T e=(0,1)^T e = ( 0 , 1 ) T 。则 r = − A e = ( 0 , − 10 − 3 ) T r=-Ae=(0,-10^{-3})^T r = − A e = ( 0 , − 1 0 − 3 ) T 的范数为 10 − 3 10^{-3} 1 0 − 3 ,而 ∥ e ∥ = 1 \|e\|=1 ∥ e ∥ = 1 。这里 ∥ A − 1 ∥ = 10 3 \|A^{-1}\|=10^3 ∥ A − 1 ∥ = 1 0 3 ,界 ∥ e ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ \|e\|\le\|A^{-1}\|\|r\| ∥ e ∥ ≤ ∥ A − 1 ∥∥ r ∥ 恰好取等。
练习与解答
快速检查
(对上述二阶例子,从零出发求第二次 Jacobi 迭代,并验证不动点为 ( 1 / 11 , 7 / 11 ) T (1/11,7/11)^T ( 1/11 , 7/11 ) T 。)
对 ( 1 / 4 , 2 / 3 ) T (1/4,2/3)^T ( 1/4 , 2/3 ) T 套用 Jacobi 公式。
解答 · 答案 从 ( 1 / 4 , 2 / 3 ) (1/4,2/3) ( 1/4 , 2/3 ) 再作 Jacobi 更新得到 ( 1 / 12 , 7 / 12 ) (1/12,7/12) ( 1/12 , 7/12 ) 。将 ( 1 / 11 , 7 / 11 ) (1/11,7/11) ( 1/11 , 7/11 ) 代入 A x = b Ax=b A x = b 即验证不动点。
快速检查
(对 SPD 矩阵,一次 SOR 分量更新在 ω = 1 \omega=1 ω = 1 时如何改变 Q Q Q ?ω = 2 \omega=2 ω = 2 时呢?)
解答 · 答案 ω = 1 \omega=1 ω = 1 时变化为 − r i 2 / ( 2 a i i ) -r_i^2/(2a_{ii}) − r i 2 / ( 2 a ii ) ,这是沿该坐标的最小值。ω = 2 \omega=2 ω = 2 时变化为零,因此严格下降证明不适用。
快速检查
(令 A = I A=I A = I 、ω = 3 / 2 \omega=3/2 ω = 3/2 ,求 k k k 轮后的误差和收敛因子。)
A = I A=I A = I 时 B ω B_\omega B ω 是什么?
解答 · 答案 B ω = − I / 2 B_\omega=-I/2 B ω = − I /2 ,故 e ( k ) = ( − 1 / 2 ) k e ( 0 ) e^{(k)}=(-1/2)^ke^{(0)} e ( k ) = ( − 1/2 ) k e ( 0 ) ,因子为 1 / 2 1/2 1/2 。
快速检查
(Jacobi 能否对 SPD 矩阵发散?给出具体矩阵和初始误差。)
找一个 SPD 矩阵,使 I − A I-A I − A 有小于 − 1 -1 − 1 的特征值。
解答 · 答案 上述 3 × 3 3\times3 3 × 3 SPD 矩阵在 ( 1 , 1 , 1 ) T (1,1,1)^T ( 1 , 1 , 1 ) T 方向的 Jacobi 特征值为 − 3 / 2 -3/2 − 3/2 ,该初始误差发散。
快速检查
(对 A = ( 2 1 1 2 ) A=\begin{pmatrix}2&1\\1&2\end{pmatrix} A = ( 2 1 1 2 ) ,求 α i , β i \alpha_i,\beta_i α i , β i 、γ \gamma γ 与 ∥ B J ∥ ∞ \|B_J\|_\infty ∥ B J ∥ ∞ 。再求 B G S B_{GS} B GS 、它的最大范数以及两个谱半径。一轮范数界相等,是否意味着渐近因子相等?)
逐行解 ( D + L ) B G S = − U (D+L)B_{GS}=-U ( D + L ) B GS = − U 。
解答 · 答案 α 1 = 0 \alpha_1=0 α 1 = 0 、β 1 = 1 / 2 \beta_1=1/2 β 1 = 1/2 、α 2 = 1 / 2 \alpha_2=1/2 α 2 = 1/2 、β 2 = 0 \beta_2=0 β 2 = 0 ,故 γ = 1 / 2 = ∥ B J ∥ ∞ \gamma=1/2=\|B_J\|_\infty γ = 1/2 = ∥ B J ∥ ∞ 。解 ( D + L ) B G S = − U (D+L)B_{GS}=-U ( D + L ) B GS = − U 得第一行 ( 0 , − 1 / 2 ) (0,-1/2) ( 0 , − 1/2 ) 、第二行 ( 0 , 1 / 4 ) (0,1/4) ( 0 , 1/4 ) ,所以 ∥ B G S ∥ ∞ = 1 / 2 \|B_{GS}\|_\infty=1/2 ∥ B GS ∥ ∞ = 1/2 。其特征值为 0 , 1 / 4 0,1/4 0 , 1/4 ,ρ ( B G S ) = 1 / 4 \rho(B_{GS})=1/4 ρ ( B GS ) = 1/4 ;而 B J B_J B J 的特征值为 ± 1 / 2 \pm1/2 ± 1/2 ,ρ ( B J ) = 1 / 2 \rho(B_J)=1/2 ρ ( B J ) = 1/2 。因此一轮范数界相等并不意味着渐近因子相等。
快速检查
(对上文不对角占优的 3 × 3 3\times3 3 × 3 例子,在右端为零时对误差 ( 1 , − 1 , 0 ) T (1,-1,0)^T ( 1 , − 1 , 0 ) T 作一轮 Gauss–Seidel,验证 B G S ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T B_{GS}(1,-1,0)^T=2(1,-1,0)^T B GS ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T 。)
解答 · 答案 取 x = ( 1 , − 1 , 0 ) T x=(1,-1,0)^T x = ( 1 , − 1 , 0 ) T ,依次得 y 1 = − ( 2 x 2 − 2 x 3 ) = 2 y_1=-(2x_2-2x_3)=2 y 1 = − ( 2 x 2 − 2 x 3 ) = 2 ,y 2 = − ( y 1 + x 3 ) = − 2 y_2=-(y_1+x_3)=-2 y 2 = − ( y 1 + x 3 ) = − 2 ,y 3 = − ( 2 y 1 + 2 y 2 ) = 0 y_3=-(2y_1+2y_2)=0 y 3 = − ( 2 y 1 + 2 y 2 ) = 0 。故 y = ( 2 , − 2 , 0 ) T = 2 x y=(2,-2,0)^T=2x y = ( 2 , − 2 , 0 ) T = 2 x 。