消元法通过改变方程来解线性系统;定常迭代则固定更新规则,反复改进一个向量。对稀疏矩阵,一轮更新可以只处理非零系数,避免因子分解可能产生的填充。不过,反复使用一条看似合理的公式,不代表数值一定会接近解。
Jacobi 与 Gauss–Seidel 从同一组重新排列的方程出发,差别在于一轮中读取哪些值。本节先精确说明这个差别,证明一个充分收敛条件,再回答实际问题:观察到的改变很小,何时真的保证解误差很小?这里的 Jacobi 是解线性系统的迭代,不是特征值问题中的 Jacobi 旋转法。
重新排列方程,但不要隐藏依赖关系
设 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 i i ≠ 0 a_{ii}\ne0 a ii = 0 。我们要找满足 A x = b Ax=b A x = b 的向量。重新排列第 i i i 行得到
x i = b i − ∑ j ≠ i a i j x j a i i . x_i=\frac{b_i-\sum_{j\ne i}a_{ij}x_j}{a_{ii}}. x i = a ii b i − ∑ j = i a ij x j .
用 k k k 记录完整更新轮数。Jacobi 的右方全部读取上一个向量;Gauss–Seidel 则依次访问第 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n 行,立即使用本轮已更新的分量。
写成 A = D + L + U A=D+L+U A = D + L + U ,其中 D D D 为对角矩阵,L L L 为严格下三角矩阵,U U U 为严格上三角矩阵。三者保留 A A A 各项原来的符号。
Jacobi 使用
x i ( k + 1 ) = b i − ∑ j ≠ i a i j x j ( k ) a i i , x ( k + 1 ) = B J x ( k ) + D − 1 b , B J = − D − 1 ( L + U ) . x_i^{(k+1)}=\frac{b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}}{a_{ii}},
\qquad
x^{(k+1)}=B_Jx^{(k)}+D^{-1}b,
\qquad B_J=-D^{-1}(L+U). x i ( k + 1 ) = a ii 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 ) . Gauss–Seidel 使用
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 , x ( k + 1 ) = B G x ( k ) + ( D + L ) − 1 b , B G = − ( 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
x^{(k+1)}=B_Gx^{(k)}+(D+L)^{-1}b,
\qquad B_G=-(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 ) , x ( k + 1 ) = B G x ( k ) + ( D + L ) − 1 b , B G = − ( D + L ) − 1 U . 这里的三角逆矩阵记号是在描述映射;实现 Gauss–Seidel 是作代入计算,而非显式构造该逆矩阵。
把含新值的项移到左边,就得到矩阵式。由于 D D D 与 D + L D+L D + L 都可逆,两种规则的一个向量是不动点,当且仅当它解出 A x = b Ax=b A x = b 。这证明了不动点与方程解的对应,但尚未证明迭代序列会收敛到它。
一个数组的更新,可能悄悄换了算法
以下伪代码描述单轮更新,前提是对角项非零。刻意不加外层停止循环,因为停止精度的说法还需要后面的估计。
jacobi_sweep(A, b, old):
allocate next with n entries
for i = 1,...,n:
next[i] = (b[i] - sum(A[i,j] * old[j] for j != i)) / A[i,i]
return next
gauss_seidel_sweep(A, b, x):
for i = 1,...,n:
x[i] = (b[i] - sum(A[i,j] * x[j] for j != i)) / A[i,i]
return x
第二种更新中,小索引分量已是新值,大索引分量仍是旧值。Jacobi 的各个输出可以独立计算;Gauss–Seidel 的指定次序则有前后依赖。
常见错误
(覆写输入数组会把 Jacobi 变成 Gauss–Seidel)
如果把 old 换成一边读一边覆写的向量,就变成 Gauss–Seidel 式的依赖关系,而不是 Jacobi,而且结果还取决于各行的访问次序。Jacobi 更新需要两个数组:一个只读,一个只写。
用稀疏行表示时,只把已存储的非零非对角项加起来。一轮工作量是 O ( nnz ( A ) + n ) O(\operatorname{nnz}(A)+n) O ( nnz ( A ) + n ) ,包括访问各行及对角除法;稠密实现则是 O ( n 2 ) O(n^2) O ( n 2 ) 。达到指定精度需要多少轮,是另一部分成本。单轮便宜,不表示整个求解一定便宜。
证明一个不要求对称的充分条件
使用向量范数 ∥ z ∥ ∞ = max i ∣ z i ∣ \|z\|_\infty=\max\limits_i|z_i| ∥ z ∥ ∞ = i max ∣ z i ∣ ,及其诱导矩阵范数 ∥ B ∥ ∞ = max i ∑ j ∣ b i j ∣ \|B\|_\infty=\max\limits_i\sum\limits_j|b_{ij}| ∥ B ∥ ∞ = i max j ∑ ∣ b ij ∣ 。逐行使用三角不等式,可得 ∥ B z ∥ ∞ ≤ ∥ B ∥ ∞ ∥ z ∥ ∞ \|Bz\|_\infty\leq\|B\|_\infty\|z\|_\infty ∥ B z ∥ ∞ ≤ ∥ B ∥ ∞ ∥ z ∥ ∞ 。
假设
q = max i ∑ j ≠ i ∣ a i j ∣ ∣ a i i ∣ < 1. q=\max_i\frac{\sum_{j\ne i}|a_{ij}|}{|a_{ii}|}<1. q = i max ∣ a ii ∣ ∑ j = i ∣ a ij ∣ < 1. 则 A A A 可逆,具有唯一解 x ∗ x^* x ∗ 。Jacobi 及上述排序的 Gauss–Seidel 都从任意初始向量收敛,并满足
∥ x ( k ) − x ∗ ∥ ∞ ≤ q k ∥ x ( 0 ) − x ∗ ∥ ∞ . \|x^{(k)}-x^*\|_\infty\leq q^k\|x^{(0)}-x^*\|_\infty. ∥ x ( k ) − x ∗ ∥ ∞ ≤ q k ∥ x ( 0 ) − x ∗ ∥ ∞ . 这是充分条件,不是说每个不满足它的矩阵都令迭代发散,也不要求矩阵对称。
若 A z = 0 Az=0 A z = 0 且 z ≠ 0 z\ne0 z = 0 ,选 ∣ z i ∣ = ∥ z ∥ ∞ > 0 |z_i|=\|z\|_\infty>0 ∣ z i ∣ = ∥ z ∥ ∞ > 0 的一行。该行给出 ∣ a i i ∣ ∣ z i ∣ ≤ ∑ j ≠ i ∣ a i j ∣ ∥ z ∥ ∞ |a_{ii}||z_i|\leq\sum\limits_{j\ne i}|a_{ij}|\|z\|_\infty ∣ a ii ∣∣ z i ∣ ≤ j = i ∑ ∣ a ij ∣∥ z ∥ ∞ ,与严格行占优矛盾。因此方阵可逆。
把解所满足的方程,从 Jacobi 更新式中相减,每个新误差分量都不超过该行非对角比率乘以旧的最大误差,所以整个新误差范数至多是旧值的 q q q 倍。
对 Gauss–Seidel,令旧最大误差为 E E E ,沿更新次序归纳。假设已更新分量的误差不超过 q E qE q E ,则下一行有
∣ e i n e w ∣ ≤ ∑ j < i ∣ a i j ∣ q E + ∑ j > i ∣ a i j ∣ E ∣ a i i ∣ ≤ q E , |e_i^{\mathrm{new}}|\leq
\frac{\sum_{j<i}|a_{ij}|qE+\sum_{j>i}|a_{ij}|E}{|a_{ii}|}
\leq qE, ∣ e i new ∣ ≤ ∣ a ii ∣ ∑ j < i ∣ a ij ∣ q E + ∑ j > i ∣ a ij ∣ E ≤ q E , 因为 q ≤ 1 q\leq1 q ≤ 1 ,而全部非对角比率至多是 q q q 。第一行的较小索引和为空,所以归纳起点也成立。反复使用单轮误差界,就得到定理。
把输入向量与解之差,换成任意两个输入向量之差,同一个论证也证明每个更新映射在无穷范数下都是收缩,因子至多为 q q q 。
证明透视
严格占优用在哪里 严格性在两个不同的地方出现。在零空间向量的论证中,它产生矛盾 ∣ a i i ∣ ∣ z i ∣ ≤ ( ∑ j ≠ i ∣ a i j ∣ ) ∣ z i ∣ < ∣ a i i ∣ ∣ z i ∣ |a_{ii}||z_i|\leq(\sum\limits_{j\ne i}|a_{ij}|)|z_i|\lt|a_{ii}||z_i| ∣ a ii ∣∣ z i ∣ ≤ ( j = i ∑ ∣ a ij ∣ ) ∣ z i ∣ < ∣ a ii ∣∣ z i ∣ ,所以非严格不等式不能排除零空间向量。在收缩步骤中,它提供使几何界趋于零的因子 q < 1 q\lt1 q < 1 。证明中不易察觉的一步是 Gauss–Seidel 的归纳:刚更新的分量只知道误差至多为 q E qE q E ,而不是 E E E ;正是 q ≤ 1 q\leq1 q ≤ 1 使行的估计能吸收这个较弱的信息而不损失因子 q q q 。选用最大范数,使每一行成为独立的估计,行与行之间没有耦合。
这个证明没有比较两种方法的实际收敛速度。若能证明 ∥ B J ∥ ∞ \|B_J\|_\infty ∥ B J ∥ ∞ 或 ∥ B G ∥ ∞ \|B_G\|_\infty ∥ B G ∥ ∞ 更小,就可以得到更好的界;排序也会改变 Gauss–Seidel 的分裂。因此,某个矩阵及某个排序的结论,不能直接变成所有算法的普遍快慢排名。
用同一系统比较两种新旧值规则
例题 10.1.3
(一个 Gauss–Seidel 立即利用新信息的小系统)
取
A = ( 4 1 2 3 ) , b = ( 1 2 ) , x ∗ = ( 1 / 10 3 / 5 ) . A=\begin{pmatrix}4&1\\2&3\end{pmatrix},
\qquad b=\begin{pmatrix}1\\2\end{pmatrix},
\qquad x^*=\begin{pmatrix}1/10\\3/5\end{pmatrix}. A = ( 4 2 1 3 ) , b = ( 1 2 ) , x ∗ = ( 1/10 3/5 ) . 占优界是 q = 2 / 3 q=2/3 q = 2/3 。从 ( 0 , 0 ) T (0,0)^T ( 0 , 0 ) T 出发:
例如,Gauss–Seidel 第一行先算出 1 / 4 1/4 1/4 ,第二行立即使用它,得到 ( 2 − 2 ( 1 / 4 ) ) / 3 = 1 / 2 (2-2(1/4))/3=1/2 ( 2 − 2 ( 1/4 )) /3 = 1/2 ;Jacobi 的第二行仍读取旧零值,所以得到 2 / 3 2/3 2/3 。
迭代矩阵为
B J = ( 0 − 1 / 4 − 2 / 3 0 ) , B G = ( 0 − 1 / 4 0 1 / 6 ) . B_J=\begin{pmatrix}0&-1/4\\-2/3&0\end{pmatrix},
\qquad
B_G=\begin{pmatrix}0&-1/4\\0&1/6\end{pmatrix}. B J = ( 0 − 2/3 − 1/4 0 ) , B G = ( 0 0 − 1/4 1/6 ) . 它们的无穷范数分别是 2 / 3 2/3 2/3 、1 / 4 1/4 1/4 ,所以本例可用较小的 Gauss–Seidel 范数改善收缩保证。单看这个表,并不能证明任意数据的收敛性。
概念视角 代数
把收敛看作谱的性质 误差满足 e ( k ) = B k e ( 0 ) e^{(k)}=B^ke^{(0)} e ( k ) = B k e ( 0 ) ,所以迭代对每个初始向量都收敛,当且仅当谱半径 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 。在某个诱导范数下 ∥ B ∥ < 1 \|B\|<1 ∥ B ∥ < 1 是这个条件的充分证明,而不是等价条件。对于 B J = ( 0 − 2 − 1 / 10 0 ) B_J=\begin{pmatrix}0&-2\\-1/10&0\end{pmatrix} B J = ( 0 − 1/10 − 2 0 ) ,无穷范数是 2 2 2 ,但特征值是 ± 1 / 5 \pm1/\sqrt5 ± 1/ 5 。在上述例题的方程组中,ρ ( B J ) = 1 / 6 ≈ 0.408 \rho(B_J)=1/\sqrt6\approx0.408 ρ ( B J ) = 1/ 6 ≈ 0.408 ,ρ ( B G ) = 1 / 6 \rho(B_G)=1/6 ρ ( B G ) = 1/6 。
从步差推出解误差保证
设 F ( x ) = B x + c F(x)=Bx+c F ( x ) = B x + c ,∥ B ∥ ∞ ≤ θ < 1 \|B\|_\infty\leq\theta<1 ∥ B ∥ ∞ ≤ θ < 1 (这可以是占优界 q q q ,或针对特定矩阵证明的更小上界),并设 x ( k ) = F ( x ( k − 1 ) ) x^{(k)}=F(x^{(k-1)}) x ( k ) = F ( x ( k − 1 ) ) 。令 Δ k = ∥ x ( k ) − x ( k − 1 ) ∥ ∞ \Delta_k=\|x^{(k)}-x^{(k-1)}\|_\infty Δ k = ∥ x ( k ) − x ( k − 1 ) ∥ ∞ ,x ∗ x^* x ∗ 为不动点。则对每个 k ≥ 1 k\geq1 k ≥ 1 ,
∥ x ∗ − x ( k ) ∥ ∞ ≤ θ 1 − θ Δ k . \|x^*-x^{(k)}\|_\infty\leq\frac{\theta}{1-\theta}\Delta_k. ∥ x ∗ − x ( k ) ∥ ∞ ≤ 1 − θ θ Δ k .
相邻迭代值之差满足 x ( m + 1 ) − x ( m ) = B ( x ( m ) − x ( m − 1 ) ) x^{(m+1)}-x^{(m)}=B(x^{(m)}-x^{(m-1)}) x ( m + 1 ) − x ( m ) = B ( x ( m ) − x ( m − 1 ) ) ,所以第 k k k 轮后,第 j j j 个未来步骤的长度至多是 θ j Δ k \theta^j\Delta_k θ j Δ k 。由于 θ < 1 \theta\lt1 θ < 1 ,迭代收敛到 x ∗ x^* x ∗ ,因此可把未来步骤逐项相加(望远镜求和):
∥ x ∗ − x ( k ) ∥ ∞ ≤ ∑ j = 1 ∞ θ j Δ k = θ 1 − θ Δ k . \|x^*-x^{(k)}\|_\infty
\leq\sum_{j=1}^\infty\theta^j\Delta_k
=\frac{\theta}{1-\theta}\Delta_k. ∥ x ∗ − x ( k ) ∥ ∞ ≤ j = 1 ∑ ∞ θ j Δ k = 1 − θ θ Δ k . 若 θ = 0 \theta=0 θ = 0 ,映射是常数,第一轮便到达不动点;对 k ≥ 1 k\geq1 k ≥ 1 ,零误差界仍然正确。
证明透视
为什么求和从第一个未来步骤开始 求和从 j = 1 j=1 j = 1 而不是 j = 0 j=0 j = 0 开始,因为当前向量已包含长度为 Δ k \Delta_k Δ k 的那一步:只有尚未走的步骤才对误差有贡献。收缩因子只通过相邻步差之间的关系起作用,所以更小的已证明 θ \theta θ 会直接改善保证,而没有依据的 θ \theta θ 则使保证失效。乘数 θ / ( 1 − θ ) \theta/(1-\theta) θ / ( 1 − θ ) 把观察到的一步换成对未观察尾部的界,并随 θ → 1 \theta\to1 θ → 1 而激增。
对 0 < θ < 1 0<\theta<1 0 < θ < 1 ,若要保证解误差至多为 ε \varepsilon ε ,一个充分停止条件是 Δ k ≤ ε ( 1 − θ ) / θ \Delta_k\leq\varepsilon(1-\theta)/\theta Δ k ≤ ε ( 1 − θ ) / θ 。
没有已证明的收缩因子,只因 Δ k \Delta_k Δ k 低于容差就停止,什么也保证不了:乘数可能很大。例如 θ = 0.99 \theta=0.99 θ = 0.99 时,乘数为 99,所以 10 − 6 10^{-6} 1 0 − 6 的步差只能保证误差至多 9.9 × 10 − 5 9.9\times10^{-5} 9.9 × 1 0 − 5 。
用残差及其尺度控制解误差
严格行对角占优还给出另一种保证,对任何 近似值 z z z 都适用,不论它如何产生。
设 A A A 严格行对角占优,并定义
γ = min i ( ∣ a i i ∣ − ∑ j ≠ i ∣ a i j ∣ ) > 0 , r = b − A z . \gamma=\min_i\left(|a_{ii}|-\sum_{j\ne i}|a_{ij}|\right)>0,
\qquad r=b-Az. γ = i min ∣ a ii ∣ − j = i ∑ ∣ a ij ∣ > 0 , r = b − A z . 则
∥ z − x ∗ ∥ ∞ ≤ ∥ r ∥ ∞ γ . \|z-x^*\|_\infty\leq\frac{\|r\|_\infty}{\gamma}. ∥ z − x ∗ ∥ ∞ ≤ γ ∥ r ∥ ∞ .
令 e = z − x ∗ e=z-x^* e = z − x ∗ ,就有 A e = − r Ae=-r A e = − r ,再选 ∣ e i ∣ = ∥ e ∥ ∞ |e_i|=\|e\|_\infty ∣ e i ∣ = ∥ e ∥ ∞ 的一行。三角不等式给出 ∣ a i i ∣ ∥ e ∥ ∞ ≤ ∥ r ∥ ∞ + ∑ j ≠ i ∣ a i j ∣ ∥ e ∥ ∞ |a_{ii}|\|e\|_\infty\leq\|r\|_\infty+\sum\limits_{j\ne i}|a_{ij}|\|e\|_\infty ∣ a ii ∣∥ e ∥ ∞ ≤ ∥ r ∥ ∞ + j = i ∑ ∣ a ij ∣∥ e ∥ ∞ 。把非对角项移到左边,再用下界 γ \gamma γ 即可。证明不要求对称、正定或某一种迭代映射。
残差本身有尺度。对 A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) 、b = ( 1 , ε ) T b=(1,\varepsilon)^T b = ( 1 , ε ) T 、0 < ε ≤ 1 0<\varepsilon\leq1 0 < ε ≤ 1 ,解为 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,近似值 ( 1 , 0 ) T (1,0)^T ( 1 , 0 ) T 的残差为 ( 0 , ε ) T (0,\varepsilon)^T ( 0 , ε ) T ,范数是 ε \varepsilon ε ,解误差却是 1。此时 γ = ε \gamma=\varepsilon γ = ε ,误差界正确给出 ε / ε = 1 \varepsilon/\varepsilon=1 ε / ε = 1 ,并没有把小残差误当成小前向误差。
例题 10.1.7
(保证第三个 Gauss–Seidel 迭代值)
在前面的 Gauss–Seidel 例子中,第三轮步差为 Δ 3 = 1 / 48 \Delta_3=1/48 Δ 3 = 1/48 。用已证明的 θ = 1 / 4 \theta=1/4 θ = 1/4 ,得到误差至多 ( 1 / 3 ) ( 1 / 48 ) = 1 / 144 (1/3)(1/48)=1/144 ( 1/3 ) ( 1/48 ) = 1/144 ;因为此例另外知道精确解,可以算出实际误差为 1 / 240 1/240 1/240 。若改用较松的共同因子 q = 2 / 3 q=2/3 q = 2/3 ,则只得到 2 ⋅ ( 1 / 48 ) = 1 / 24 2\cdot(1/48)=1/24 2 ⋅ ( 1/48 ) = 1/24 。有效的保证可以保守,而改善已证明的常数确实有用。
系统有唯一解,迭代仍可能发散
反例模式
解的存在唯一性,不是迭代收敛保证 令 A = ( 1 2 2 1 ) A=\begin{pmatrix}1&2\\2&1\end{pmatrix} A = ( 1 2 2 1 ) 、b = ( 3 , 3 ) T b=(3,3)^T b = ( 3 , 3 ) T 。行列式为 − 3 -3 − 3 ,所以唯一解是 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T 。
Jacobi 从零出发给出 ( 0 , 0 ) T , ( 3 , 3 ) T , ( − 3 , − 3 ) T , ( 9 , 9 ) T , … (0,0)^T,(3,3)^T,(-3,-3)^T,(9,9)^T,\ldots ( 0 , 0 ) T , ( 3 , 3 ) T , ( − 3 , − 3 ) T , ( 9 , 9 ) T , … 。沿 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T 的误差每轮乘以 − 2 -2 − 2 ,越来越大。重新排列的方程有正确不动点,但更新反而把向量推离它。
另一方面,不通过占优测试也不能证明发散。对 A = ( 1 2 1 / 10 1 ) A=\begin{pmatrix}1&2\\1/10&1\end{pmatrix} A = ( 1 1/10 2 1 ) ,Jacobi 无穷范数为 2,却有 B J 2 = ( 1 / 5 ) I B_J^2=(1/5)I B J 2 = ( 1/5 ) I 。每两轮都把任何误差缩至 1 / 5 1/5 1/5 ,所以任意起点都收敛。单轮范数测试可能失败,两轮论证却成功。
分清精确算术定理与程序算出的诊断量
程序计算的残差可能含舍入误差,每轮更新也可能有算术扰动。本节证明的是精确映射与精确残差。完整的浮点误差保证还须控制这些扰动;单是打印出“残差”二字,不会自动提供该误差界。
稀疏求解可以定期重新计算残差,而不只从最新步差猜测。每一行残差都须使用同一个完整迭代向量。
在 Gauss–Seidel 中,最后访问的方程刚刚为新值解出,所以一轮结束时恰好满足,但较早的方程已因后面分量改变而重新出现误差。在例子中,第三个迭代值的第二行残差为 0 0 0 ,第一行残差却是 − 1 / 72 -1/72 − 1/72 。只读取最后一行的残差测试因此并不足够。
两种保证的假设不同:步差界要求更新映射有已证明的收缩因子;残差界则要求已证明的残差至解误差控制,本节用严格行对角占优提供它。两者都不能单靠设置一个小容差推出。
练习与解答
快速检查
(在例子的 2 × 2 2\times2 2 × 2 系统中,说明第一个 Jacobi 向量为什么是 ( 1 / 4 , 2 / 3 ) T (1/4,2/3)^T ( 1/4 , 2/3 ) T ,第一个 Gauss–Seidel 向量却是 ( 1 / 4 , 1 / 2 ) T (1/4,1/2)^T ( 1/4 , 1/2 ) T 。伪代码中哪种修改会无意间把第一种方法变成第二种?)
解答 · 答案 两者先得到第一分量 1 / 4 1/4 1/4 。Jacobi 第二行读旧 x 1 = 0 x_1=0 x 1 = 0 ,得到 2 / 3 2/3 2/3 ;Gauss–Seidel 读刚更新的 x 1 = 1 / 4 x_1=1/4 x 1 = 1/4 ,得到 ( 2 − 1 / 2 ) / 3 = 1 / 2 (2-1/2)/3=1/2 ( 2 − 1/2 ) /3 = 1/2 。若把 Jacobi 输出直接写回输入数组,并在后面的行读取这个已修改的数组,就改变了依赖关系。分开的 old/next 数组正是为了避免这件事。
快速检查
(在例子的第三个 Jacobi 迭代值 ( 1 / 8 , 11 / 18 ) T (1/8,11/18)^T ( 1/8 , 11/18 ) T ,分别用 θ = 2 / 3 \theta=2/3 θ = 2/3 的步差界及 γ = min ( 4 − 1 , 3 − 2 ) \gamma=\min(4-1,3-2) γ = min ( 4 − 1 , 3 − 2 ) 的残差界估计误差。哪一个能保证误差至多 1 / 5 1/5 1/5 ?)
分别计算 Δ 3 \Delta_3 Δ 3 和残差 b − A x ( 3 ) b-Ax^{(3)} b − A x ( 3 ) 。
解答 · 答案 第二个迭代值是 ( 1 / 12 , 1 / 2 ) T (1/12,1/2)^T ( 1/12 , 1/2 ) T ,所以 Δ 3 = max { ∣ 1 / 8 − 1 / 12 ∣ , ∣ 11 / 18 − 1 / 2 ∣ } = max { 1 / 24 , 1 / 9 } = 1 / 9 \Delta_3=\max\{|1/8-1/12|,|11/18-1/2|\}=\max\{1/24,1/9\}=1/9 Δ 3 = max { ∣1/8 − 1/12∣ , ∣11/18 − 1/2∣ } = max { 1/24 , 1/9 } = 1/9 。步差界为 2 / 3 1 / 3 ⋅ 1 9 = 2 / 9 ≈ 0.222 > 1 / 5 \dfrac{2/3}{1/3}\cdot\dfrac19=2/9\approx0.222>1/5 1/3 2/3 ⋅ 9 1 = 2/9 ≈ 0.222 > 1/5 。
残差是 b − A x ( 3 ) = ( 1 − 1 / 2 − 11 / 18 , 2 − 1 / 4 − 11 / 6 ) T = ( − 1 / 9 , − 1 / 12 ) T b-Ax^{(3)}=(1-1/2-11/18,\ 2-1/4-11/6)^T=(-1/9,-1/12)^T b − A x ( 3 ) = ( 1 − 1/2 − 11/18 , 2 − 1/4 − 11/6 ) T = ( − 1/9 , − 1/12 ) T ,γ = 1 \gamma=1 γ = 1 ,得到界 1 / 9 ≈ 0.111 < 1 / 5 1/9\approx0.111<1/5 1/9 ≈ 0.111 < 1/5 。因此这里是残差界能证明所需精度,步差界则不能。实际误差是 1 / 40 1/40 1/40 ;一个充分界未通过,不代表近似值不准确。
快速检查
(对 A = ( 1 2 1 / 10 1 ) A=\begin{pmatrix}1&2\\1/10&1\end{pmatrix} A = ( 1 1/10 2 1 ) ,用两轮更新证明 Jacobi 收敛。对 m ≥ 1 m\ge1 m ≥ 1 ,由第 2 m 2m 2 m 与第 2 m − 2 2m-2 2 m − 2 个迭代值的差,推导第 2 m 2m 2 m 个值的停止误差界。)
计算 B J 2 B_J^2 B J 2 ,并把步差保证用于两轮映射。
解答 · 答案 A A A 的行列式为 4 / 5 4/5 4/5 ,所以解唯一。此时 B J = ( 0 − 2 − 1 / 10 0 ) B_J=\begin{pmatrix}0&-2\\-1/10&0\end{pmatrix} B J = ( 0 − 1/10 − 2 0 ) ,故 B J 2 = ( 1 / 5 ) I B_J^2=(1/5)I B J 2 = ( 1/5 ) I 。两轮仿射映射 F ∘ F F\circ F F ∘ F 的收缩因子是 1 / 5 1/5 1/5 ,不动点与原方法相同且唯一。因此偶数子序列收敛;奇数子序列是把连续映射 F F F 作用在偶数子序列上,所以也收敛。
把步差保证用于两轮映射,而不是单轮映射,得到 ∥ x ( 2 m ) − x ∗ ∥ ∞ ≤ ( 1 / 4 ) ∥ x ( 2 m ) − x ( 2 m − 2 ) ∥ ∞ \|x^{(2m)}-x^*\|_\infty\leq(1/4)\|x^{(2m)}-x^{(2m-2)}\|_\infty ∥ x ( 2 m ) − x ∗ ∥ ∞ ≤ ( 1/4 ) ∥ x ( 2 m ) − x ( 2 m − 2 ) ∥ ∞ 。若把两轮常数配上一轮步差,就不是已证明的结果。
快速检查
(设 A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) 、b = ( 1 , ε ) T b=(1,\varepsilon)^T b = ( 1 , ε ) T 、0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 ,近似值 z = ( 1 , 0 ) T z=(1,0)^T z = ( 1 , 0 ) T 。求精确解、残差、误差及 γ \gamma γ 。为什么小残差本身不能保证小前向误差?)
解答 · 答案 精确解是 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,残差 b − A z = ( 0 , ε ) T b-Az=(0,\varepsilon)^T b − A z = ( 0 , ε ) T ,解误差的无穷范数为 1。严格行占优给出 γ = ε \gamma=\varepsilon γ = ε ,所以残差界是 ε / ε = 1 \varepsilon/\varepsilon=1 ε / ε = 1 ,与实际误差一致。小残差出现在矩阵系数很小的方向,必须除以有依据的尺度。
Jacobi 对这个对角系统只需一轮精确更新,因为迭代矩阵为零。但这不表示题目的初始近似值准确,也不能因未缩放的残差很小,就在修正前提早停止。