小残差并不等于精确解
数值求解 A x = b Ax=b A x = b 时,我们需要算法、计算成本估计,以及判断输出意义的方法。精确的数学问题可能对数据的微小变化十分敏感;算法也可能在处理本来并不敏感的问题时引入可避免的误差。这两种不同的现象分别涉及条件性 和稳定性 ,不能混为一谈。
除非另有说明,A A A 是 n × n n\times n n × n 实矩阵。若 A A A 非奇异,则精确解唯一:x = A − 1 b x=A^{-1}b x = A − 1 b 。实际计算通常无需显式形成 A − 1 A^{-1} A − 1 ;可以先分解 A A A ,再求解三角方程组。计算结果 x ^ \widehat x x 的残差为 r = b − A x ^ r=b-A\widehat x r = b − A x ,因此
A ( x − x ^ ) = r , x − x ^ = A − 1 r . A(x-\widehat x)=r,\qquad x-\widehat x=A^{-1}r. A ( x − x ) = r , x − x = A − 1 r .
残差衡量计算结果满足给定方程的程度。它也是右端项的精确扰动:A x ^ = b − r A\widehat x=b-r A x = b − r 。但残差本身不是前向误差 x − x ^ x-\widehat x x − x 。
高斯(Gauss)消元法与 LU 分解
假设消元过程中无需交换行,也没有零主元。用每个主元行的倍数减去它下方的各行,得到上三角矩阵 U U U 。将倍数放入对角线为一的下三角矩阵 L L L ,便有 A = L U A=LU A = LU 。先用前代求解 L y = b Ly=b L y = b ,再用回代求解 U x = y Ux=y U x = y 。例如
A = ( 2 1 4 3 ) = ( 1 0 2 1 ) ( 2 1 0 1 ) . A=\begin{pmatrix}2&1\\4&3\end{pmatrix}
=\begin{pmatrix}1&0\\2&1\end{pmatrix}
\begin{pmatrix}2&1\\0&1\end{pmatrix}. A = ( 2 4 1 3 ) = ( 1 2 0 1 ) ( 2 0 1 1 ) .
若 b = ( 1 , 1 ) T b=(1,1)^T b = ( 1 , 1 ) T ,前代给出 y = ( 1 , − 1 ) T y=(1,-1)^T y = ( 1 , − 1 ) T ,回代得到 x = ( 1 , − 1 ) T x=(1,-1)^T x = ( 1 , − 1 ) T 。对于稠密矩阵,分解的运算量为 n 3 n^3 n 3 的量级;之后每增加一个右端项,求解的运算量为 n 2 n^2 n 2 的量级。因此,同一系数矩阵对应多个右端项时,只需分解一次。
非奇异矩阵仍可能有零首主元:( 0 1 1 0 ) \left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right) ( 0 1 1 0 ) 的逆就是自身。交换行可处理这种情况。部分选主元 在当前列的可用元素中选取绝对值最大的元素作为下一个主元,交换行后继续。其分解形式为 P A = L U PA=LU P A = LU ,其中 P P P 是累计的置换矩阵。先解 L y = P b Ly=Pb L y = P b ,再解 U x = y Ux=y U x = y 。选主元还能避免除以不必要地小的主元,但不保证对所有矩阵都有小误差:消元中元素仍可能大幅增长。
反例模式
非奇异矩阵未必有 LU 分解 断言:每个非奇异矩阵都可分解为 A = L U A=LU A = LU ,其中 L L L 为单位下三角矩阵,U U U 为上三角矩阵。取 A = ( 0 1 1 0 ) A=\begin{pmatrix}0&1\\1&0\end{pmatrix} A = ( 0 1 1 0 ) ,det A = − 1 \det A=-1 det A = − 1 。若 A = ( 1 0 ℓ 1 ) ( u 11 u 12 0 u 22 ) A=\begin{pmatrix}1&0\\\ell&1\end{pmatrix}\begin{pmatrix}u_{11}&u_{12}\\0&u_{22}\end{pmatrix} A = ( 1 ℓ 0 1 ) ( u 11 0 u 12 u 22 ) ,由 ( 1 , 1 ) (1,1) ( 1 , 1 ) 元得 u 11 = 0 u_{11}=0 u 11 = 0 ,再由 ( 2 , 1 ) (2,1) ( 2 , 1 ) 元得 ℓ u 11 = 0 ≠ 1 \ell u_{11}=0\ne1 ℓ u 11 = 0 = 1 ,矛盾。对非奇异的 A A A ,LU 分解存在,当且仅当 1 , … , n − 1 1,\dots,n-1 1 , … , n − 1 阶的顺序主子式都不为零;交换行便得到 P A = L U PA=LU P A = LU 。
后续选主元时,先前乘子也要随行交换
在精确算术中对下列矩阵做部分选主元消元:
A = ( 4 2 0 2 2 2 − 2 1 1 ) . A=\begin{pmatrix}4&2&0\\2&2&2\\-2&1&1\end{pmatrix}. A = 4 2 − 2 2 2 1 0 2 1 . 第 1 列最大绝对值是 4 4 4 ,因此不换行。主元下方的乘子是 ℓ 21 = 1 / 2 \ell_{21}=1/2 ℓ 21 = 1/2 和 ℓ 31 = − 1 / 2 \ell_{31}=-1/2 ℓ 31 = − 1/2 。各行减去相应乘子倍的第 1 行,得到
( 4 2 0 0 1 2 0 2 1 ) . \begin{pmatrix}4&2&0\\0&1&2\\0&2&1\end{pmatrix}. 4 0 0 2 1 2 0 2 1 . 第 2 列尚未处理的元素中,2 2 2 的绝对值大于 1 1 1 ,所以交换第 2、3 行;活动行变成 ( 0 , 2 , 1 ) (0,2,1) ( 0 , 2 , 1 ) 和 ( 0 , 1 , 2 ) (0,1,2) ( 0 , 1 , 2 ) 。同时交换两行已经保存的第 1 列乘子 :− 1 / 2 -1/2 − 1/2 现在属于第 2 行,1 / 2 1/2 1/2 属于第 3 行。下一个乘子是 1 / 2 1/2 1/2 ;第 3 行减去第 2 行的一半后得到 ( 0 , 0 , 3 / 2 ) (0,0,3/2) ( 0 , 0 , 3/2 ) 。因此
P = ( 1 0 0 0 0 1 0 1 0 ) , L = ( 1 0 0 − 1 / 2 1 0 1 / 2 1 / 2 1 ) , U = ( 4 2 0 0 2 1 0 0 3 / 2 ) . P=\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix},\qquad
L=\begin{pmatrix}1&0&0\\-1/2&1&0\\1/2&1/2&1\end{pmatrix},\qquad
U=\begin{pmatrix}4&2&0\\0&2&1\\0&0&3/2\end{pmatrix}. P = 1 0 0 0 0 1 0 1 0 , L = 1 − 1/2 1/2 0 1 1/2 0 0 1 , U = 4 0 0 2 2 0 0 1 3/2 . 不要只背规则,可以核对各行的历史:
L U = ( 4 2 0 − 2 1 1 2 2 2 ) = P A . LU=\begin{pmatrix}4&2&0\\-2&1&1\\2&2&2\end{pmatrix}=PA. LU = 4 − 2 2 2 1 2 0 1 2 = P A . 如果把原有乘子留在原位,所得乘积的第 2 行将是 ( 2 , 3 , 1 ) (2,3,1) ( 2 , 3 , 1 ) ,而不是 ( − 2 , 1 , 1 ) (-2,1,1) ( − 2 , 1 , 1 ) ,于是 P A = L U PA=LU P A = LU 不成立。乘子记录当前行曾如何被先前的主元行改变,因此必须随这一行移动。在 L L L 中,只交换当前主元之前各列里已经保存的元素;若交换最终单位下三角矩阵 L L L 的整行,就会移动对角线上的 1,破坏其形式。
一般地,在第 k k k 步,从第 k , … , n k,\ldots,n k , … , n 行的第 k k k 列中选取绝对值最大的元素。交换相应的活动行,以及 L L L 中第 1 , … , k − 1 1,\ldots,k-1 1 , … , k − 1 列已经保存的元素,若交换矩阵为 S S S ,则更新 P ← S P P\leftarrow SP P ← S P (从 P = I P=I P = I 开始)。然后把主元下方各元素除以主元,再从对应活动行中减去所得乘子倍的主元行。如果可选元素的最大绝对值为零,就不能做除法:活动列无法提供主元。对方阵而言,在精确消元中这表明矩阵奇异。这里讨论的是精确算术;舍入与元素增长需要另行分析。
得到 P A = L U PA=LU P A = LU 后,前代必须使用 P b Pb P b 。对上面的矩阵和 b = ( 6 , 6 , 0 ) T b=(6,6,0)^T b = ( 6 , 6 , 0 ) T ,先解 L y = b Ly=b L y = b 再解 U x = y Ux=y U x = y ,得 y = ( 6 , 9 , − 15 / 2 ) T y=(6,9,-15/2)^T y = ( 6 , 9 , − 15/2 ) T 、x = ( − 2 , 7 , − 5 ) T x=(-2,7,-5)^T x = ( − 2 , 7 , − 5 ) T 。A x Ax A x 的第二行为 2 ( − 2 ) + 2 ⋅ 7 + 2 ( − 5 ) = 0 2(-2)+2\cdot7+2(-5)=0 2 ( − 2 ) + 2 ⋅ 7 + 2 ( − 5 ) = 0 ,不是 6 6 6 ,所以这个向量不是解。
快速检查
(用上面的因子解 A x = ( 6 , 6 , 0 ) T Ax=(6,6,0)^T A x = ( 6 , 6 , 0 ) T 。为什么两次三角求解的第一个右端项是 P b Pb P b 而非 b b b ?)
解答 · 答案 换行给出 P b = ( 6 , 0 , 6 ) T Pb=(6,0,6)^T P b = ( 6 , 0 , 6 ) T 。对 L y = P b Ly=Pb L y = P b 作前代得到 y = ( 6 , 3 , 3 / 2 ) T y=(6,3,3/2)^T y = ( 6 , 3 , 3/2 ) T ;对 U x = y Ux=y U x = y 作回代得到 x = ( 1 , 1 , 1 ) T x=(1,1,1)^T x = ( 1 , 1 , 1 ) T 。因子代表的是 P A x = P b PAx=Pb P A x = P b ;除非 P b = b Pb=b P b = b ,否则 L y = b Ly=b L y = b 求解的是另一个方程组。
三角方程组如何求解
简写 L y = b Ly=b L y = b 、再解 U x = y Ux=y U x = y ,隐藏了未知量逐个得到的顺序。设 L L L 为对角元素均非零的下三角矩阵。第 i i i 行只含 y 1 , … , y i y_1,\ldots,y_i y 1 , … , y i ,因此前代法按以下顺序计算:
y i = b i − ∑ j = 1 i − 1 ℓ i j y j ℓ i i , i = 1 , … , n . y_i=\frac{b_i-\sum_{j=1}^{i-1}\ell_{ij}y_j}{\ell_{ii}},\qquad i=1,\ldots,n. y i = ℓ ii b i − ∑ j = 1 i − 1 ℓ ij y j , i = 1 , … , n .
空和为零,故第一步是 y 1 = b 1 / ℓ 11 y_1=b_1/\ell_{11} y 1 = b 1 / ℓ 11 。归纳地,右边各项都已算出;每一行唯一确定一个 y i y_i y i ,这也证明了解的存在与唯一性。对于对角元素非零的上三角矩阵 U U U ,从最后一行开始,回代法同理得到
x i = y i − ∑ j = i + 1 n u i j x j u i i , i = n , n − 1 , … , 1. x_i=\frac{y_i-\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}},\qquad i=n,n-1,\ldots,1. x i = u ii y i − ∑ j = i + 1 n u ij x j , i = n , n − 1 , … , 1.
稠密三角方程组各需计算 n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 个乘积,另有减法和至多 n n n 次除法;对角线全为一时无需除法。因此,已有分解后,两次求解共需 O ( n 2 ) O(n^2) O ( n 2 ) 次运算。这里统计的是精确算术运算,不包括读取数据的代价,也不保证精度;浮点求解还会产生舍入误差。
设消元已经得到 P A = L U PA=LU P A = LU ,其中 P P P 交换第一、三行,且
L = ( 1 0 0 2 1 0 − 1 3 1 ) , U = ( 2 1 − 1 0 3 2 0 0 4 ) , b = ( 3 14 5 ) . L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix},\quad
U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix},\quad
b=\begin{pmatrix}3\\14\\5\end{pmatrix}. L = 1 2 − 1 0 1 3 0 0 1 , U = 2 0 0 1 3 0 − 1 2 4 , b = 3 14 5 . 由 P A x = P b PAx=Pb P A x = P b ,第一步的右端是 P b = ( 5 , 14 , 3 ) T Pb=(5,14,3)^T P b = ( 5 , 14 , 3 ) T ,不是 b b b 。前代得到 y 1 = 5 y_1=5 y 1 = 5 ,y 2 = 14 − 2 ( 5 ) = 4 y_2=14-2(5)=4 y 2 = 14 − 2 ( 5 ) = 4 ,y 3 = 3 + y 1 − 3 y 2 = − 4 y_3=3+y_1-3y_2=-4 y 3 = 3 + y 1 − 3 y 2 = − 4 。从 U x = y Ux=y U x = y 的最后一行回代,得 x 3 = − 1 x_3=-1 x 3 = − 1 ,x 2 = ( 4 − 2 x 3 ) / 3 = 2 x_2=(4-2x_3)/3=2 x 2 = ( 4 − 2 x 3 ) /3 = 2 ,x 1 = ( 5 − x 2 + x 3 ) / 2 = 1 x_1=(5-x_2+x_3)/2=1 x 1 = ( 5 − x 2 + x 3 ) /2 = 1 。所以 x = ( 1 , 2 , − 1 ) T x=(1,2,-1)^T x = ( 1 , 2 , − 1 ) T 。不必构造 A A A 即可验算:U x = ( 5 , 4 , − 4 ) T Ux=(5,4,-4)^T U x = ( 5 , 4 , − 4 ) T 且 L U x = P b LUx=Pb LU x = P b ;由于 P P P 可逆,故 A x = b Ax=b A x = b 。
对角元素为零时,上面的除法无效,三角矩阵也奇异。但这不意味着对应方程组一定无解:diag ( 1 , 0 ) x = ( 1 , 0 ) T \operatorname{diag}(1,0)x=(1,0)^T diag ( 1 , 0 ) x = ( 1 , 0 ) T 有无穷多解,而右端改为 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T 则无解。分解过程中若有合适的行,选主元可避开零主元;这不意味着三角求解时可以除以零。
快速检查
(对下面的矩阵求解 L y = ( 2 , 1 , 4 ) T Ly=(2,1,4)^T L y = ( 2 , 1 , 4 ) T ,再求解 U x = y Ux=y U x = y 。)
L = ( 2 0 0 1 1 0 − 1 2 1 ) , U = ( 1 2 0 0 1 1 0 0 2 ) . L=\begin{pmatrix}2&0&0\\1&1&0\\-1&2&1\end{pmatrix},\qquad
U=\begin{pmatrix}1&2&0\\0&1&1\\0&0&2\end{pmatrix}. L = 2 1 − 1 0 1 2 0 0 1 , U = 1 0 0 2 1 0 0 1 2 .
解答 · 答案 前代得 y 1 = 1 y_1=1 y 1 = 1 、y 2 = 0 y_2=0 y 2 = 0 、y 3 = 5 y_3=5 y 3 = 5 ;回代得 x 3 = 5 / 2 x_3=5/2 x 3 = 5/2 、x 2 = − 5 / 2 x_2=-5/2 x 2 = − 5/2 、x 1 = 6 x_1=6 x 1 = 6 。第二次求解的右端是 y y y ,不是原来的向量。
对于实对称正定矩阵,可以使用更专门的分解 A = L L T A=LL^T A = L L T ,其中 L L L 是对角线为正的下三角矩阵。正定意味着每个非零实向量 z z z 均满足 z T A z > 0 z^TAz>0 z T A z > 0 。每一步所需的对角线平方根都是正的;例如
( 4 2 2 5 ) = ( 2 0 1 2 ) ( 2 1 0 2 ) . \begin{pmatrix}4&2\\2&5\end{pmatrix}
=\begin{pmatrix}2&0\\1&2\end{pmatrix}
\begin{pmatrix}2&1\\0&2\end{pmatrix}. ( 4 2 2 5 ) = ( 2 1 0 2 ) ( 2 0 1 2 ) .
仅有对称性并不足够:( 1 0 0 − 1 ) \left(\begin{smallmatrix}1&0\\0&-1\end{smallmatrix}\right) ( 1 0 0 − 1 ) 对称,却不可能等于 L L T LL^T L L T ,因为 z T L L T z = ∥ L T z ∥ 2 2 ≥ 0 z^TLL^Tz=\|L^Tz\|_2^2\geq0 z T L L T z = ∥ L T z ∥ 2 2 ≥ 0 。对于复 Hermitian 正定矩阵,转置需改为共轭转置。
思想史
作为数学问题的舍入误差 Alan Turing 在其1948 年关于矩阵运算舍入误差的论文 中,研究了若干线性方程求解和矩阵求逆方法的误差,包括消元法。他的分析说明,统计运算次数与评估有限精度结果的准确性是两个不同问题。这里关于残差和条件数的讨论采用现代记号,并非将这些定义归功于该论文。
条件数与误差界
使用一个向量范数及其诱导矩阵范数。
设 A A A 非奇异,并固定一个向量范数及其诱导矩阵范数。A A A 的条件数为 κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ \kappa(A)=\|A\|\,\|A^{-1}\| κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ 。
设 A A A 非奇异,A x = b Ax=b A x = b 且 b ≠ 0 b\ne0 b = 0 ,x ^ \widehat x x 的残差为 r = b − A x ^ r=b-A\widehat x r = b − A x 。则
∥ x − x ^ ∥ ∥ x ∥ ≤ κ ( A ) ∥ r ∥ ∥ b ∥ . \frac{\|x-\widehat x\|}{\|x\|}
\leq \kappa(A)\frac{\|r\|}{\|b\|}. ∥ x ∥ ∥ x − x ∥ ≤ κ ( A ) ∥ b ∥ ∥ r ∥ .
因为 x − x ^ = A − 1 r x-\widehat x=A^{-1}r x − x = A − 1 r ,所以 ∥ x − x ^ ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ \|x-\widehat x\|\le\|A^{-1}\|\,\|r\| ∥ x − x ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ 。又因为 ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ \|b\|=\|Ax\|\le\|A\|\,\|x\| ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ,所以 1 / ∥ x ∥ ≤ ∥ A ∥ / ∥ b ∥ 1/\|x\|\le\|A\|/\|b\| 1/∥ x ∥ ≤ ∥ A ∥/∥ b ∥ 。把两个不等式相乘即得所述的界。
该界可能高估实际误差,但说明了为什么相对残差小,单凭这一点不能保证相对前向误差小。取 A = diag ( 1 , 10 − 8 ) A=\operatorname{diag}(1,10^{-8}) A = diag ( 1 , 1 0 − 8 ) 、b = ( 1 , 10 − 8 ) T b=(1,10^{-8})^T b = ( 1 , 1 0 − 8 ) T 和 x ^ = ( 1 , 0 ) T \widehat x=(1,0)^T x = ( 1 , 0 ) T 。精确解为 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,残差为 ( 0 , 10 − 8 ) T (0,10^{-8})^T ( 0 , 1 0 − 8 ) T 。在 Euclidean 范数下,相对残差约为 10 − 8 10^{-8} 1 0 − 8 ,相对前向误差却为 1 / 2 1/\sqrt2 1/ 2 。这里 κ 2 ( A ) = 10 8 \kappa_2(A)=10^8 κ 2 ( A ) = 1 0 8 。
若只扰动右端项,则 A ( x + Δ x ) = b + Δ b A(x+\Delta x)=b+\Delta b A ( x + Δ x ) = b + Δ b 给出 Δ x = A − 1 Δ b \Delta x=A^{-1}\Delta b Δ x = A − 1 Δ b ,把上述残差换成 Δ b \Delta b Δ b 便得到同样的相对界。扰动 A A A 还需额外条件:若某诱导矩阵范数满足 ∥ A − 1 Δ A ∥ < 1 \|A^{-1}\Delta A\|<1 ∥ A − 1 Δ A ∥ < 1 ,则由收敛的 Neumann 级数可知 A + Δ A = A ( I + A − 1 Δ A ) A+\Delta A=A(I+A^{-1}\Delta A) A + Δ A = A ( I + A − 1 Δ A ) 可逆。没有这类条件,微小扰动也可能使近奇异矩阵变为奇异。
在明确的误差模型下,如果算法的计算结果是某个邻近问题的精确解,而且数据的相对扰动受到控制,则称该算法后向稳定。问题本身病态时,即使方法后向稳定,前向误差仍可能很大;反之,条件良好的问题也可能受到不稳定算法的损害。“残差小”必须相对于某个尺度来理解,不能单凭这句话确认其中任何一种性质。
近乎相关的方程
例题 2.1.5
(趋于零的扰动却使解发生固定变化)
考虑
A ε = ( 1 1 1 1 + ε ) , b ε = ( 2 2 + ε ) , 0 < ε ≤ 1. A_\varepsilon=\begin{pmatrix}1&1\\1&1+\varepsilon\end{pmatrix},\qquad b_\varepsilon=\binom{2}{2+\varepsilon},\qquad 0<\varepsilon\le1. A ε = ( 1 1 1 1 + ε ) , b ε = ( 2 + ε 2 ) , 0 < ε ≤ 1. 第二个方程减去第一个得到 ε x 2 = ε \varepsilon x_2=\varepsilon ε x 2 = ε ,故精确解为 x = ( 1 , 1 ) T x=(1,1)^T x = ( 1 , 1 ) T 。若将 b ε b_\varepsilon b ε 的第二个分量增加 ε \varepsilon ε ,新解为 x ^ = ( 0 , 2 ) T \widehat x=(0,2)^T x = ( 0 , 2 ) T 。数据扰动随 ε \varepsilon ε 趋于零,但解的变化始终是 ( − 1 , 1 ) T (-1,1)^T ( − 1 , 1 ) T 。这不违反在固定非奇异矩阵处的连续性:这里矩阵本身也在变化,并趋于奇异矩阵。
若把 x ^ \widehat x x 看作原方程的近似解,则 r = b ε − A ε x ^ = ( 0 , − ε ) T r=b_\varepsilon-A_\varepsilon\widehat x=(0,-\varepsilon)^T r = b ε − A ε x = ( 0 , − ε ) T 。直接计算得到
A ε − 1 = 1 ε ( 1 + ε − 1 − 1 1 ) , κ ∞ ( A ε ) = ( 2 + ε ) 2 ε , ∥ r ∥ ∞ ∥ b ε ∥ ∞ = ε 2 + ε , ∥ x − x ^ ∥ ∞ ∥ x ∥ ∞ = 1. A_\varepsilon^{-1}=\frac1\varepsilon\begin{pmatrix}1+\varepsilon&-1\\-1&1\end{pmatrix},\qquad
\kappa_\infty(A_\varepsilon)=\frac{(2+\varepsilon)^2}{\varepsilon},\qquad
\frac{\|r\|_\infty}{\|b_\varepsilon\|_\infty}=\frac{\varepsilon}{2+\varepsilon},\qquad
\frac{\|x-\widehat x\|_\infty}{\|x\|_\infty}=1. A ε − 1 = ε 1 ( 1 + ε − 1 − 1 1 ) , κ ∞ ( A ε ) = ε ( 2 + ε ) 2 , ∥ b ε ∥ ∞ ∥ r ∥ ∞ = 2 + ε ε , ∥ x ∥ ∞ ∥ x − x ∥ ∞ = 1.
一般残差界在此允许相对前向误差达到 2 + ε 2+\varepsilon 2 + ε ;实际误差为 1,说明最坏情形界不必取等号。取 ε = 10 − 4 \varepsilon=10^{-4} ε = 1 0 − 4 时,相对残差约为 5.0 × 10 − 5 5.0\times10^{-5} 5.0 × 1 0 − 5 ,相对前向误差仍为 1。部分选主元虽可改善消元的稳定性,却无法消除问题本身的敏感性。
迭代方法与停止条件
对于大型稀疏方程组,分解可能产生大量新的非零元素。另一种方法是将 A = M − N A=M-N A = M − N 分裂,其中关于 M M M 的方程容易求解,并迭代
M x ( k + 1 ) = N x ( k ) + b , x ( k + 1 ) = B x ( k ) + c , B = M − 1 N . Mx^{(k+1)}=Nx^{(k)}+b,\qquad
x^{(k+1)}=Bx^{(k)}+c,\quad B=M^{-1}N. M x ( k + 1 ) = N x ( k ) + b , x ( k + 1 ) = B x ( k ) + c , B = M − 1 N .
假设 M M M 非奇异,迭代才有定义。当 A A A 非奇异时,精确解是一个不动点。误差满足 e ( k + 1 ) = B e ( k ) e^{(k+1)}=Be^{(k)} e ( k + 1 ) = B e ( k ) ,故 e ( k ) = B k e ( 0 ) e^{(k)}=B^ke^{(0)} e ( k ) = B k e ( 0 ) 。对每个初值都收敛,当且仅当 B k → 0 B^k\to0 B k → 0 ,等价于谱半径 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 。一个方便的充分条件是某个诱导范数满足 ∥ B ∥ < 1 \|B\|<1 ∥ B ∥ < 1 。即使某个特定范数下 ∥ B ∥ > 1 \|B\|>1 ∥ B ∥ > 1 ,谱半径条件仍决定最终收敛;收敛之前可能出现暂时增长。
Jacobi 迭代将 A = D + L + U A=D+L+U A = D + L + U 分为对角、严格下三角和严格上三角部分,并取 M = D M=D M = D 。所有对角元素都必须非零。若 A = ( 4 1 1 3 ) A=\left(\begin{smallmatrix}4&1\\1&3\end{smallmatrix}\right) A = ( 4 1 1 3 ) 、b = ( 1 , 2 ) T b=(1,2)^T b = ( 1 , 2 ) T ,则
x 1 ( k + 1 ) = 1 − x 2 ( k ) 4 , x 2 ( k + 1 ) = 2 − x 1 ( k ) 3 . x_1^{(k+1)}=\frac{1-x_2^{(k)}}4,\qquad
x_2^{(k+1)}=\frac{2-x_1^{(k)}}3. x 1 ( k + 1 ) = 4 1 − x 2 ( k ) , x 2 ( k + 1 ) = 3 2 − x 1 ( k ) .
从零开始,第一步得到 ( 1 / 4 , 2 / 3 ) (1/4,2/3) ( 1/4 , 2/3 ) 。迭代矩阵的无穷范数为 1 / 3 1/3 1/3 ,所以对每个初值都收敛;精确不动点为 ( 1 / 11 , 7 / 11 ) (1/11,7/11) ( 1/11 , 7/11 ) 。Gauss–Seidel 立即使用新计算的分量,即取 M = D + L M=D+L M = D + L 。其迭代矩阵不同,不能不检查条件就仅由 Jacobi 收敛断定它也收敛。
实际停止测试在 b ≠ 0 b\ne0 b = 0 时常使用 ∥ r k ∥ / ∥ b ∥ \|r_k\|/\|b\| ∥ r k ∥/∥ b ∥ ,并设置最大迭代次数。步长 ∥ x ( k + 1 ) − x ( k ) ∥ \|x^{(k+1)}-x^{(k)}\| ∥ x ( k + 1 ) − x ( k ) ∥ 很小可能表示停滞,而非准确。条件数决定残差如何转化为前向误差,而有限精度最终限制可达到的精度。
考虑标量方程 0.01 x = 0.01 0.01x=0.01 0.01 x = 0.01 ,取分裂 M = 1 M=1 M = 1 、N = 0.99 N=0.99 N = 0.99 ,则 x ( k + 1 ) = 0.99 x ( k ) + 0.01 x^{(k+1)}=0.99x^{(k)}+0.01 x ( k + 1 ) = 0.99 x ( k ) + 0.01 ,精确解为 1 1 1 。从 x ( 0 ) = 0 x^{(0)}=0 x ( 0 ) = 0 出发,第一步 x ( 1 ) = 0.01 x^{(1)}=0.01 x ( 1 ) = 0.01 :步长为 0.01 0.01 0.01 ,误差却是 0.99 0.99 0.99 。一般地,x ( k + 1 ) − x ( k ) = ( B − I ) e ( k ) x^{(k+1)}-x^{(k)}=(B-I)e^{(k)} x ( k + 1 ) − x ( k ) = ( B − I ) e ( k ) ,所以当 ρ ( B ) \rho(B) ρ ( B ) 接近 1 1 1 时,很小的步长可能掩盖很大的误差。
练习与解答
快速检查
(不选主元,将 A A A 分解为 L U LU LU ,并求解 A x = ( 3 , 10 ) T Ax=(3,10)^T A x = ( 3 , 10 ) T 。)
A = ( 1 2 3 7 ) . A=\begin{pmatrix}1&2\\3&7\end{pmatrix}. A = ( 1 3 2 7 ) .
解答 · 答案 L = ( 1 0 3 1 ) L=\left(\begin{smallmatrix}1&0\\3&1\end{smallmatrix}\right) L = ( 1 3 0 1 ) ,U = ( 1 2 0 1 ) U=\left(\begin{smallmatrix}1&2\\0&1\end{smallmatrix}\right) U = ( 1 0 2 1 ) 。前代得 ( 3 , 1 ) T (3,1)^T ( 3 , 1 ) T ,回代得 x = ( 1 , 1 ) T x=(1,1)^T x = ( 1 , 1 ) T 。
快速检查
(对下面的数据,计算残差和精确前向误差。)
A = diag ( 1 , 10 − 6 ) , b = ( 1 10 − 6 ) , x ^ = ( 1 0 ) . A=\operatorname{diag}(1,10^{-6}),\qquad b=\begin{pmatrix}1\\10^{-6}\end{pmatrix},\qquad \widehat x=\begin{pmatrix}1\\0\end{pmatrix}. A = diag ( 1 , 1 0 − 6 ) , b = ( 1 1 0 − 6 ) , x = ( 1 0 ) .
解答 · 答案 r = ( 0 , 10 − 6 ) T r=(0,10^{-6})^T r = ( 0 , 1 0 − 6 ) T ;精确解为 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,故 x − x ^ = ( 0 , 1 ) T x-\widehat x=(0,1)^T x − x = ( 0 , 1 ) T 。
快速检查
(对下面的 Jacobi 例子,利用无穷范数证明收敛,并计算从零出发的第二次迭代。)
A = ( 4 1 1 3 ) , b = ( 1 2 ) . A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\end{pmatrix}. A = ( 4 1 1 3 ) , b = ( 1 2 ) .
解答 · 答案 B = ( 0 − 1 / 4 − 1 / 3 0 ) B=\left(\begin{smallmatrix}0&-1/4\\-1/3&0\end{smallmatrix}\right) B = ( 0 − 1/3 − 1/4 0 ) 满足 ∥ B ∥ ∞ = 1 / 3 < 1 \|B\|_\infty=1/3\lt1 ∥ B ∥ ∞ = 1/3 < 1 。代入更新式可得 x ( 2 ) = ( 1 / 12 , 7 / 12 ) T x^{(2)}=(1/12,7/12)^T x ( 2 ) = ( 1/12 , 7/12 ) T 。
矩阵与右端项的联合扰动
实际计算中,矩阵与数据往往同时带有误差。因此我们要问:当 A A A 与 b b b 同时受到扰动时,解最多会改变多少?
设定。 设 A A A 非奇异,b ≠ 0 b\neq 0 b = 0 ,x = A − 1 b x=A^{-1}b x = A − 1 b ,从而 x ≠ 0 x\neq 0 x = 0 。设 ( A + E ) ( x + δ x ) = b + d (A+E)(x+\delta x)=b+d ( A + E ) ( x + δ x ) = b + d 。用下文向量范数所诱导的矩阵范数,记 κ = κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ \kappa=\kappa(A)=\|A\|\,\|A^{-1}\| κ = κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ ,并令 α = ∥ E ∥ / ∥ A ∥ \alpha=\|E\|/\|A\| α = ∥ E ∥/∥ A ∥ ,β = ∥ d ∥ / ∥ b ∥ \beta=\|d\|/\|b\| β = ∥ d ∥/∥ b ∥ 。假设 κ α < 1 \kappa\alpha<1 κ α < 1 。
在上述假设下,A + E A+E A + E 可逆,且
∥ δ x ∥ ∥ x ∥ ≤ κ ( α + β ) 1 − κ α . \frac{\|\delta x\|}{\|x\|}\le\frac{\kappa(\alpha+\beta)}{1-\kappa\alpha}. ∥ x ∥ ∥ δ x ∥ ≤ 1 − κ α κ ( α + β ) .
证明
(Neumann 级数、吸收项与对 b 的估计)
由于 ∥ A − 1 E ∥ ≤ ∥ A − 1 ∥ ∥ E ∥ = κ α < 1 \|A^{-1}E\|\le\|A^{-1}\|\,\|E\|=\kappa\alpha<1 ∥ A − 1 E ∥ ≤ ∥ A − 1 ∥ ∥ E ∥ = κ α < 1 ,由前面的结果知 I + A − 1 E I+A^{-1}E I + A − 1 E 可逆,故 A + E = A ( I + A − 1 E ) A+E=A(I+A^{-1}E) A + E = A ( I + A − 1 E ) 可逆,δ x \delta x δ x 唯一确定。减去 A x = b Ax=b A x = b 得 A δ x = d − E x − E δ x A\,\delta x=d-Ex-E\,\delta x A δ x = d − E x − E δ x ,于是
∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ + ∥ E ∥ ∥ δ x ∥ ) . \|\delta x\|\le\|A^{-1}\|\big(\|d\|+\|E\|\,\|x\|+\|E\|\,\|\delta x\|\big). ∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ + ∥ E ∥ ∥ δ x ∥ ) . 因为 ∥ A − 1 ∥ ∥ E ∥ = κ α \|A^{-1}\|\,\|E\|=\kappa\alpha ∥ A − 1 ∥ ∥ E ∥ = κ α ,把最后一项移到左边得 ( 1 − κ α ) ∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ ) (1-\kappa\alpha)\|\delta x\|\le\|A^{-1}\|(\|d\|+\|E\|\,\|x\|) ( 1 − κ α ) ∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ ) 。1 − κ α > 0 1-\kappa\alpha>0 1 − κ α > 0 正是假设本身,所以可以两边相除。最后,由 ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ \|b\|=\|Ax\|\le\|A\|\,\|x\| ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ 得 ∥ A − 1 ∥ ∥ d ∥ / ∥ x ∥ ≤ ∥ A − 1 ∥ ∥ A ∥ ∥ d ∥ / ∥ b ∥ = κ β \|A^{-1}\|\,\|d\|/\|x\|\le\|A^{-1}\|\,\|A\|\,\|d\|/\|b\|=\kappa\beta ∥ A − 1 ∥ ∥ d ∥/∥ x ∥ ≤ ∥ A − 1 ∥ ∥ A ∥ ∥ d ∥/∥ b ∥ = κ β 。不等式 ∥ b ∥ / ∥ x ∥ ≤ ∥ A ∥ \|b\|/\|x\|\le\|A\| ∥ b ∥/∥ x ∥ ≤ ∥ A ∥ 只在这一步用到。□ \square □
证明透视
各个假设用在哪里 证明有三步。第一,κ α < 1 \kappa\alpha\lt1 κ α < 1 给出 ∥ A − 1 E ∥ < 1 \|A^{-1}E\|\lt1 ∥ A − 1 E ∥ < 1 ,从而 A + E A+E A + E 可逆,δ x \delta x δ x 才存在。第二,减去 A x = b Ax=b A x = b 后得到的方程右边也通过 E δ x E\,\delta x E δ x 含有 δ x \delta x δ x ;这一项被移到左边吸收,除以 1 − κ α 1-\kappa\alpha 1 − κ α 则要求该因子为正。第三,∥ b ∥ ≤ ∥ A ∥ ∥ x ∥ \|b\|\le\|A\|\,\|x\| ∥ b ∥ ≤ ∥ A ∥ ∥ x ∥ 只用一次,把 ∥ d ∥ / ∥ x ∥ \|d\|/\|x\| ∥ d ∥/∥ x ∥ 转成 ∥ d ∥ / ∥ b ∥ \|d\|/\|b\| ∥ d ∥/∥ b ∥ ;含 ∥ E ∥ ∥ x ∥ \|E\|\,\|x\| ∥ E ∥ ∥ x ∥ 的项不需要这一步,因为 ∥ x ∥ \|x\| ∥ x ∥ 直接约去。
此界是精确算术下的最坏情形上界。它不涉及舍入误差,具体问题中实际测得的误差可能小得多。
取 ∞ \infty ∞ -范数,A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) ,0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 ,b = ( 1 , ε ) b=(1,\varepsilon) b = ( 1 , ε ) ,E = diag ( 0 , − ε / 2 ) E=\operatorname{diag}(0,-\varepsilon/2) E = diag ( 0 , − ε /2 ) ,d = 0 d=0 d = 0 。则 x = ( 1 , 1 ) x=(1,1) x = ( 1 , 1 ) ,κ = 1 / ε \kappa=1/\varepsilon κ = 1/ ε ,α = ε / 2 \alpha=\varepsilon/2 α = ε /2 ,κ α = 1 / 2 \kappa\alpha=1/2 κ α = 1/2 ,β = 0 \beta=0 β = 0 ,所以上界为 ( 1 / 2 ) / ( 1 / 2 ) = 1 (1/2)/(1/2)=1 ( 1/2 ) / ( 1/2 ) = 1 。解 diag ( 1 , ε / 2 ) y = ( 1 , ε ) \operatorname{diag}(1,\varepsilon/2)\,y=(1,\varepsilon) diag ( 1 , ε /2 ) y = ( 1 , ε ) 得 y = ( 1 , 2 ) y=(1,2) y = ( 1 , 2 ) ,故 δ x = ( 0 , 1 ) \delta x=(0,1) δ x = ( 0 , 1 ) ,实际相对误差为 1 1 1 。上界恰好取到。
反例模式
去掉对 A 的扰动须足够小的假设 一个诱人的说法是:只要 α = ∥ E ∥ / ∥ A ∥ \alpha=\|E\|/\|A\| α = ∥ E ∥/∥ A ∥ 很小,扰动后的方程组就有相近的解。在 ∞ \infty ∞ -范数下取 A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) 、E = diag ( 0 , − ε ) E=\operatorname{diag}(0,-\varepsilon) E = diag ( 0 , − ε ) 、b = ( 1 , ε ) b=(1,\varepsilon) b = ( 1 , ε ) 。则 α = ε \alpha=\varepsilon α = ε 可以任意小,但 κ α = ( 1 / ε ) ε = 1 \kappa\alpha=(1/\varepsilon)\,\varepsilon=1 κ α = ( 1/ ε ) ε = 1 ,A + E = diag ( 1 , 0 ) A+E=\operatorname{diag}(1,0) A + E = diag ( 1 , 0 ) 是奇异的。方程组 ( A + E ) y = b (A+E)y=b ( A + E ) y = b 要求 0 ⋅ y 2 = ε ≠ 0 0\cdot y_2=\varepsilon\ne0 0 ⋅ y 2 = ε = 0 ,因此无解。修正就是定理的假设 κ α < 1 \kappa\alpha\lt1 κ α < 1 :α \alpha α 的小必须相对于 1 / κ 1/\kappa 1/ κ 衡量,而不是相对于 1 1 1 。
快速检查
(在 ∞ \infty ∞ -范数下取 A = I A=I A = I ,E = diag ( 0 , 1 / 10 ) E=\operatorname{diag}(0,1/10) E = diag ( 0 , 1/10 ) ,b = ( 1 , 1 ) b=(1,1) b = ( 1 , 1 ) ,d = ( 0 , 1 / 10 ) d=(0,1/10) d = ( 0 , 1/10 ) 。求上界与实际误差。)
先算 κ \kappa κ 、α \alpha α 和 β \beta β 。
解答 · 答案 此时 κ = 1 \kappa=1 κ = 1 ,α = β = 1 / 10 \alpha=\beta=1/10 α = β = 1/10 ,上界为 ( 2 / 10 ) / ( 9 / 10 ) = 2 / 9 (2/10)/(9/10)=2/9 ( 2/10 ) / ( 9/10 ) = 2/9 。然而由 ( A + E ) y = ( 1 , 11 / 10 ) (A+E)y=(1,11/10) ( A + E ) y = ( 1 , 11/10 ) 得 y = ( 1 , 1 ) = x y=(1,1)=x y = ( 1 , 1 ) = x ,实际误差为 0 0 0 。两个扰动互相抵消,而最坏情形上界无法察觉这一点。