动机
数学模型常以方程作结,而不是直接给出答案。边值问题离散化后可能得到大型稀疏线性系统 Ax=b;平衡模型则可能要求解非线性方程 F(x)=0。计算所得的近似值必须分别接受三个问题的检验:原问题是否有唯一解?算法在精确算术下是否收敛?有限精度如何影响结果?单凭残差小,不能完整回答这些问题。
我们先研究可重用于不同右端项的矩阵分解,再通过误差方程研究迭代,最后利用局部线性近似推导牛顿(Newton)法。虽然例子可以手算,这些区别对大型计算同样重要。
定义
设 A∈Rn×n 可逆,真解为 x∗=A−1b,近似解为 x。误差 e=x∗−x,残差 r=b−Ax,因此 Ae=r。对任何诱导范数,∥e∥≤∥A−1∥∥r∥。若 b=0 且 x∗=0,则
∥x∗∥∥e∥≤κ(A)∥b∥∥r∥,κ(A)=∥A∥∥A−1∥.
即使不知道真解,我们仍能计算残差;误差一般不能直接计算。条件数描述问题对扰动的敏感程度,稳定性则描述算法。更换算法不会使本来病态的问题变得良态,但稳定方法可避免不必要的舍入误差放大。
概念视角几何
条件数作为到奇异矩阵的距离
在欧几里得(Euclid)范数下,κ2(A)=σmax/σmin,即最大与最小奇异值之比。等价地,它的倒数是 A 到最近奇异矩阵的相对距离:
min{∥A∥2∥δA∥2:A+δA 奇异}=κ2(A)1.对 A=diag(1,ε),把 ε 换成 0 是大小为 ε=1/κ2(A) 的相对改变。病态矩阵就是只需很小的相对扰动便会变成奇异的矩阵。
主要结果
若 A∈Rn×n 的每个左上角主子矩阵均可逆,消元法给出唯一分解 A=LU,其中 L 是对角线为一的下三角矩阵,U 是上三角矩阵;每一步主元均非零。
每一步主元是相邻左上角主子式之比,故假设保证除法合法。将消元乘数放在对角线下形成 L,逆转消元操作即得 A=LU。若 LU=LU,则 L−1L=UU−1 同时是单位下三角和上三角矩阵,必为单位矩阵,所以分解唯一。
这定理并不表示浮点算术中不需要交换行。部分主元法在当前处理的列中选绝对值最大的元素交换到主元位置,得到 PA=LU。先用前代法解 Ly=Pb,再用回代法解 Ux=y。同一分解可处理多个右端项,通常不必显式计算逆矩阵。
设 x(k+1)=Bx(k)+c 有不动点 x∗。从每个初值均收敛到 x∗,当且仅当谱半径 ρ(B)<1。特别地,只要某个诱导范数满足 ∥B∥<1,便足以保证收敛。
误差满足 e(k+1)=Be(k),故 e(k)=Bke(0)。Jordan 标准形表明 Bk→0 当且仅当所有特征值的绝对值小于一:Jordan 块的幂由 k 的多项式乘特征值的幂组成。反之,若 Bv=μv,v=0 且 ∣μ∣≥1,则 Bkv=μkv 不趋于零;若 v 是复向量,它的实部或虚部就是一个不收敛的实初始误差。范数条件则直接给出 ∥Bk∥≤∥B∥k→0。
证明透视
从仿射迭代到矩阵的幂
不动点方程 x∗=Bx∗+c 只用了一次,用来消去 c:误差服从线性递推 e(k)=Bke(0);由于 x(0) 任意,“从所有初值收敛”恰好等价于 Bk→0。真正的工作在充分性。Jordan 块 μI+N(N 幂零)的 k 次幂是 j∑(jk)μk−jNj,只有有限多项,每项都是 k 的多项式乘 μk−j;当 ∣μ∣<1 时,几何衰减胜过多项式增长。必要性只需一个特征向量,μ 为复数时再用取实部的技巧。范数条件完全绕过特征值,所以只是充分条件:ρ(B)≤∥B∥。
若 A=D+L+U 的对角元素非零,Jacobi 迭代取 B=−D−1(L+U),c=D−1b。若每行严格对角占优,B 每行绝对值和均小于一,因此 ∥B∥∞<1。这只是充分条件:例如 B=(0020) 的无穷范数为 2,但 B2=0,仍从所有初值收敛。
例题
令 A=(2413),第二行减第一行的两倍,得到
L=(1201),U=(2011).当 b=(1,1)T,前代得 y=(1,−1)T,回代得 x=(1,−1)T。当 b=(3,7)T,同一分解给 y=(3,1)T 及 x=(1,1)T。直接相乘可核对两个答案。
取 A=(4213)、b=(1,2)T。Jacobi 更新为 x1(k+1)=(1−x2(k))/4、x2(k+1)=(2−2x1(k))/3。由零向量开始,前两步为 (1/4,2/3)T 和 (1/12,1/2)T。此处 ∥B∥∞=2/3,唯一不动点是 (1/10,3/5)T。几何误差上界不一定在每一步都取等号。
对 f(x)=x2−2,在非零 xk 处更新为 xk+1=(xk+2/xk)/2。从 x0=1 得 x1=3/2、x2=17/12。令 α=2;若 xk>0,则
xk+1−α=2xk(xk−α)2.接近 α 时,误差大致每步平方。这是局部结论,并非对所有初值的保证。
方法与推理
牛顿法以 F(xk)+JF(xk)s 近似 F(xk+s),解 JF(xk)s=−F(xk),再令 xk+1=xk+s;应直接解线性系统,而非形成逆 Jacobian。标量情况下,当导数非零,更新为 xk+1=xk−f(xk)/f′(xk)。若 f 在根 α 附近二次连续可微且 f′(α)=0,连续性使附近的 ∣f′∣ 有正下界。Taylor 定理遂给 ∣ek+1∣≤C∣ek∣2;初值必须足够接近,邻域亦须选得使迭代留在其中。重根不满足非零导数假设:f(x)=x2 给出 xk+1=xk/2,只有线性收敛。
即使函数光滑且根为单根,序列仍可失败。f(x)=x3−2x+2 从 0 开始会到 1,再回到 0,形成循环。导数亦可能在到达根之前为零。阻尼或保持括区的方法可能有帮助,但其保证需要另外的假设。实用停止规则应检查经尺度调整的残差和最新修正量,并设迭代上限;线性求解失败或无进展时应报告。修正量小亦可能只是停滞。
从残差到可解释的证据
关系式 Ae=r 有两种读法。第一,x 精确地解了右端受扰问题 Ax=b−r,故 ∥r∥/∥b∥ 是矩阵固定时的一种相对后向误差。第二,原问题通过 A−1 把扰动映射成解的误差;这便解释了条件数上界。若同时允许矩阵与右端改变,必须另行指定后向误差的定义。
例如 A=diag(1,ε),其中 0<ε<1,在二范数或无穷范数下有 κ(A)=1/ε。右端第二个分量扰动 δ,解的第二个分量便改变 δ/ε;即使方程精确求解,这也是模型本身的敏感性。第一个分量的扰动却不被放大,因此条件数是最坏情况上界,不必准确预测每次扰动。
主元与运算量
取 Aε=(ε111),其中 ε 非零且很小。不交换行便会使用乘数 1/ε,产生 1−1/ε;浮点计算中,大的中间值可能在回代时造成消去误差。先交换两行则主元绝对值为一,避免这次小除数。当 ε=1,矩阵可逆,所以这是数值问题,不是不存在解的证明。
稠密 n×n 消元约需 n3 阶运算,其后每次三角求解约需 n2 阶。固定矩阵配多个载荷时,重用分解很重要。稀疏消元可能产生原来为零的新元素,称为填充;成本与存储还依赖于排序。部分主元法改善实用稳健性,却不能保证病态问题一定有小前向误差。
Jacobi 与顺序更新
Jacobi 每个新分量都取自旧向量;Gauss–Seidel 立即使用已算出的新分量。当 A=D+L+U,其方程为 (D+L)x(k+1)=b−Ux(k)。左侧是对角非零的下三角系统,用前代法即可,无须求逆。其迭代矩阵为 −(D+L)−1U,同一谱半径准则适用,但收敛因子一般不同。
对前述矩阵从零开始,第一分量先得 1/4,立即代入第二分量得 (2−2(1/4))/3=1/2。第一步为 (1/4,1/2),不同于 Jacobi 的 (1/4,2/3)。这个例子不能证明哪一种方法总是更快;收敛性、排序、并行性及成本都取决于具体问题。
若已知 ∥B∥≤q<1,对 k≥1,几何级数尾和给出事后上界 ∥x∗−x(k)∥≤q∥x(k)−x(k−1)∥/(1−q)。因每一步之差至多是上一步的 q 倍,把其后差值相加即可。此证书依赖已知收缩上界;只观察到一步很小并不足够。
牛顿法的局部估计
选好邻域之后,上一节的局部说法便成为定理。
设 f 在包含根 α 的开区间上二次连续可微,且 f′(α)=0。设 ρ>0 使得在 I=[α−ρ,α+ρ] 上 ∣f′∣≥m>0、∣f′′∣≤M,并令 C=M/(2m)。若 C=0,令 δ=ρ;否则令 δ=min(ρ,1/(2C))。若 ∣x0−α∣≤δ,则每个牛顿迭代值都有定义、都属于 I,并满足
∣xk+1−α∣≤C∣xk−α∣2≤21∣xk−α∣.特别地,xk→α。
这样的 ρ 存在:f′ 连续且 f′(α)=0,所以在 α 附近某个小闭区间上 ∣f′∣≥∣f′(α)∣/2,而连续函数 f′′ 在该区间上有界。设 ∣xk−α∣≤δ,则 xk∈I,故 f′(xk)=0,xk+1=xk−f(xk)/f′(xk) 有定义。在 xk 处用泰勒定理,存在介于 xk 与 α 之间(因而属于 I)的 ξ,使
0=f(α)=f(xk)+f′(xk)(α−xk)+21f′′(ξ)(α−xk)2.除以 f′(xk) 并代入更新式,得
xk+1−α=2f′(xk)f′′(ξ)(xk−α)2,因此 ∣xk+1−α∣≤C∣xk−α∣2≤Cδ∣xk−α∣≤21∣xk−α∣,特别是 ∣xk+1−α∣≤δ。从 k=0 开始归纳,可知所有迭代值都留在 I 内,误差每步至少减半,而二次界始终成立。
证明透视
哪个假设使迭代留在好区域内
假设 f′(α)=0 只通过下界 m 进入证明,并且用了两次:一次使更新式有定义,一次出现在误差恒等式的分母中。f′′ 的界 M 控制泰勒余项。展开在 xk 处进行、在 α 处取值,而不是在 xk+1 处,所以恒等式只涉及当前的误差。
不明显的一步是选取 δ≤1/(2C)。仅有二次界并不能阻止迭代值离开 I,而在 I 之外 m 与 M 不再适用;因子 Cδ≤21 把二次界变成收缩 ∣xk+1−α∣≤21∣xk−α∣,归纳正是靠这个收缩才得以完成。对 f(x)=x2 的重根,在 0 附近任何区间上都找不到下界 m;迭代 xk+1=xk/2 仍然收敛,但只是线性收敛。没有这些界时,切线可能指向远处或近乎水平。
矩阵的扰动
右端项的扰动只是不确定性的一个来源。设 x 解 Ax=b,而 x+δx 解 (A+δA)(x+δx)=b+δb。两式相减得
Aδx=δb−δA(x+δx).
若 ∥A−1∥∥δA∥<1,由三角不等式及诱导范数的界可得
∥δx∥≤1−∥A−1∥∥δA∥∥A−1∥(∥δb∥+∥δA∥∥x∥).
此界假设受扰解存在;严格不等式也通过 (I+A−1δA)−1 的收敛 Neumann 级数保证受扰矩阵可逆。它表明相对误差同时取决于数据扰动与条件数。分母接近零时,上界可能很弱,但这并不证明实际扰动已经造成大误差。
二元牛顿系统
取 F(x,y)=(x2+y2−5,x−y−1)T,其 Jacobian 为 J=(2x12y−1)。从 (x0,y0)=(2,0) 出发,残差为 (−1,1)T。解 Js=(1,−1)T:第一个方程给出 s1=1/4,第二个给出 s2=5/4,所以下一点是 (9/4,5/4)。Jacobian 行列式是 −2(x+y),在直线 x+y=0 上这一步无法定义。根 (2,1) 存在,但仅凭根的存在并不保证任意初值都收敛。实际计算中若内层线性求解是近似的,也应检查线性系统的残差。
残差与停止规则的限制
在大型问题中,为检查误差而计算精确解通常与原问题一样困难,因此残差是可计算的证据。然而残差大小要与数据的尺度一起解读:若把整个方程乘以一个很小的常数,真解不变,绝对残差却同样缩小。相对残差在右端非零时更有意义,但仍要结合条件数;当右端为零或不同方程具有不同物理单位时,应另选合适的尺度。停止时同时记录迭代次数、残差和最新修正量,有助于区分收敛与停滞。有限精度下计算所得的残差本身也受舍入影响,因此到达舍入水平附近后不能期待持续改善。
常见误解
消元与迭代中有两个常见错误。
矩阵 (0110) 可逆(它就是自己的逆),但普通消元一开始就停下,因为第一个主元为零。LU 定理的假设针对左上角主子矩阵,而不是可逆性;一次行交换给出 PA=LU,就能处理这个矩阵。
取 B=diag(1/2,2)、c=0。初值 x(0)=(1,0)T 收敛到不动点 0,但 (0,1)T 每步加倍。谱半径定理说的是每一个初值;一次成功的计算只检验了其初始误差中出现的分量。
残差小也不一定表示误差小;尺度与条件数都有影响,下例把这种失败具体化。
反例模式
微小残差可掩盖一个单位的误差
错误说法是绝对残差小于 10−8 必定使误差小于 10−8。取 A=diag(1,10−10)、b=(1,0)T、x=(1,1)T,残差范数是 10−10,误差范数却为 1。修正后须使用 ∥e∥≤∥A−1∥∥r∥,不能省略很大的逆矩阵范数。方程的单位改变也能改变绝对残差,因此应采用相对的、与问题相适应的容差。
快速检查
快速检查
(若 ∥B∥∞=0.4,初始误差的无穷范数不大于 5,则 x(k+1)=Bx(k)+c 三步后的误差有什么上界?)
利用 e(k)=Bke(0) 及诱导范数的次乘性。
解答 · 答案
∥e(3)∥∞≤∥B∥∞3∥e(0)∥∞≤0.43⋅5=0.32。这是有保证的上界,而非必然的实际误差。
习题
练习 1.1.8
(将 (3614) 分解为 LU,其中 L 对角线为一,并解 b=(4,10)T。)
解答 · 答案
消元乘数为 6/3=2,故 L=(1201),U=(3012)。前代得 y=(4,10−2⋅4)T=(4,2)T;回代得 x2=1 及 3x1+1=4,因此 x=(1,1)T。验算:(3+1,6+4)T=(4,10)T。
练习 1.1.9
(求 B=(01/91/40) 的谱半径。迭代 x(k+1)=Bx(k)+c 是否从每个初值收敛?)
解答 · 答案
特征多项式为 λ2−1/36,特征值为 ±1/6。谱半径 1/6<1,故从每个初值都收敛。
练习 1.1.10
(对 f(x)=x2−3,从 x0=2 作两步牛顿迭代。)
解答 · 答案
更新式为 xk+1=(xk+3/xk)/2。于是 x1=(2+3/2)/2=7/4,x2=(7/4+12/7)/2=97/56≈1.73214,而 3≈1.73205。迭代值非零,两次除法均合法。
练习 1.1.11
(令 A=diag(1,10−6)、b=(1,0)T、x=(1,1)T。求残差与误差的无穷范数,并解释两者的差距。)
解答 · 答案
真解为 x∗=(1,0)T,r=b−Ax=(0,−10−6)T,e=x∗−x=(0,−1)T,范数分别为 10−6 和 1。由于 ∥A−1∥∞=106,界 ∥e∥≤∥A−1∥∥r∥ 恰好取到:逆矩阵将第二个坐标放大 106 倍。
延伸学习
稀疏存储、主元增长、后向误差、非线性系统及预处理 Krylov 方法都需要进一步的假设与分析;这些小例子不足以证明实际求解器是稳定的。