动机
离散化模型、拟合系数或同时满足多个限制,都会产生线性方程组 Ax=b。方程本身不会告诉我们计算向量是否准确:我们既需要求解方法,也需要判断数据扰动的影响。本节 A 是实方阵,除非另有说明,向量和矩阵范数互相相容。
消元及选主元
精确算术下,高斯(Gauss)消元法以等价的上三角系统取代原系统。在第 k 列,用第 k 行的倍数消去下方该列的元素。得到 Ux=c 后,从最后一个方程向上回代。除法要求主元非零;即使原矩阵非奇异,原有行次序也可能产生零主元,此时交换行可能让计算继续。
例如
[0213][x1x2]=[15]原次序的第一主元为零。交换两行后,方程是 2x1+3x2=5、x2=1,回代得 x1=x2=1。因此特定次序出现零主元本身并不代表矩阵奇异。
定义 3.1.2
(部分选主元与 PA=LU)
部分选主元法在当前列的主元行及其下各行中,选绝对值最大的元素,并把其行移到主元位置。若这些元素均为零,方阵必为奇异;非奇异方阵不会出现此情况。用置换矩阵 P 记录换行,得到 PA=LU,其中 L 为对角线全为一的下三角矩阵,U 为上三角矩阵。先解 Ly=Pb,再解 Ux=y;多个右端可重用同一分解。
选大主元的原因之一是部分选主元法的消元乘数绝对值不超过一,减少一个误差放大来源。但运算中的矩阵元素仍可能增长,病态问题亦仍对扰动敏感;选主元不是万能的准确性保证。
残差与误差
设 A 非奇异,x 是 Ax=b 的精确解,x 是计算向量,其残差为 r=b−Ax。对一个向量范数及与之相容的矩阵范数,A 的条件数为 κ(A)=∥A∥∥A−1∥。
因为 Ax=b,
A(x−x)=r,x−x=A−1r.
由范数相容性得 ∥x−x∥≤∥A−1∥∥r∥。若 b=0,结合 ∥b∥≤∥A∥∥x∥,可得
∥x∥∥x−x∥≤κ(A)∥b∥∥r∥,κ(A)=∥A∥∥A−1∥.
条件数、残差和误差必须使用相容的同一范数。此界可能偏松,但指出条件数大时,小相对残差未必意味小相对误差;此外上式假设残差精确计算,实际计算的残差本身也有舍入误差。
具体反例:令 A=diag(1,10−6)、b=(1,10−6)T、x=(1,0)T。精确解为 (1,1)T,而 r=(0,10−6)T。无穷范数下相对残差为 10−6,相对误差却是 1;κ∞(A)=106,上述界容许此情况。第二方程的绝对残差虽小,对应解分量却完全错误。
数据扰动
固定 A,将 b 改为 b+Δb,新解为 x+Δx。两组方程相减得 AΔx=Δb。取范数并利用 ∥b∥≤∥A∥∥x∥,对 b=0 得
∥x∥∥Δx∥≤κ(A)∥b∥∥Δb∥.
这是容许任意方向扰动的最坏情况界,不代表每个扰动都被完整条件数放大。若 A 也受扰动,需要另一个界及确保扰动后矩阵非奇异的条件。改变单位会改变坐标,也可能改变范数条件数,却不会凭空为数据增添信息。与其引用一个不说明范数及缩放的条件数,不如审视实际的测量不确定度与关心的变量。
另一个消元计算
例题 3.1.5
(2×2 系统的部分选主元)
取 A=[2413]、b=(5,13)T。由于 ∣4∣>∣2∣,部分选主元法先换行;第二行的乘数为 1/2,得到 4x+3y=13 和 −y/2=−3/2。回代得 y=3、x=1。相应分解为
P=[0110],L=[11/201],U=[403−1/2].直接相乘可验证 LU=PA,同时检查乘数及行次序。右端亦须置换;解 Ly=b 而非 Ly=Pb 会得到另一系统。求解时无须明确计算 A−1,直接使用三角系统即可;逆矩阵则有助分析敏感度。
奇异例子 A=[1224] 的行相依。若 b=(1,2)T,有无限多个解满足 x1+2x2=1;若 b=(1,3)T,两式矛盾。奇异性因此可能意味解不唯一或无解,视右端而定;奇异矩阵没有有限的普通逆矩阵条件数。
范数与矩阵扰动
诱导矩阵范数定义为 ∥A∥=v=0max∥Av∥/∥v∥,因此 ∥Av∥≤∥A∥∥v∥。无穷向量范数的诱导矩阵范数等于绝对行和的最大值。非奇异矩阵的条件数至少为一,因为 1=∥I∥=∥AA−1∥≤∥A∥∥A−1∥。在此范数意义下,一是最佳条件数;分量尺度或其他误差度量仍可能呈现不同敏感度。
现在设矩阵与右端都改变,(A+E)(x+Δx)=b+Δb,其中 Ax=b 且 A 非奇异。整理得
(I+A−1E)Δx=A−1(Δb−Ex).
若 ∥A−1E∥<1,则 I+A−1E 可逆,且 ∥(I+A−1E)−1∥≤1/(1−∥A−1E∥)。因此扰动后的系统有唯一解,且对 b=0,
∥x∥∥Δx∥≤1−∥A−1E∥κ(A)(∥b∥∥Δb∥+∥A∥∥E∥).
证明
(先用 Neumann 级数,再用误差恒等式)
令 F=−A−1E,则 ∥F∥<1。由于 ∥Fk∥≤∥F∥k,级数 k≥0∑Fk 的部分和构成 Cauchy 序列,故收敛到某个 S,且 ∥S∥≤k∑∥F∥k=1/(1−∥F∥)。裂项求和给出 (I−F)k=0∑KFk=I−FK+1→I,因子次序相反时也一样,所以 S=(I+A−1E)−1。于是 A+E=A(I+A−1E) 是可逆矩阵之积,扰动后的系统有唯一解 x+Δx。
把 S 作用于整理后的恒等式,得
∥Δx∥≤1−∥A−1E∥∥A−1∥(∥Δb∥+∥E∥∥x∥).由 b=0 也有 x=0。两边除以 ∥x∥,并把 ∥b∥≤∥A∥∥x∥ 写成 ∥Δb∥/∥x∥≤∥A∥∥Δb∥/∥b∥。提出 ∥A∥∥A−1∥=κ(A) 便得所述的界。
证明透视
哪个假设确保扰动后仍可求解
论证有两个不同任务。条件 ∥A−1E∥<1 先令 Neumann 级数收敛,从而确立扰动后的系统有唯一解。完成这一步,才可在误差恒等式两侧乘以逆矩阵并估计范数。额外假设 b=0 是为了定义相对误差的比值,并非可逆性所需。大条件数表示可容许数据误差可能被放大,不代表解的代数恒等式失效。
分母十分重要:若扰动可以使矩阵奇异,就无法由此得到统一有限界。此条件充分而非必要,某些更大的扰动仍可保持可逆。这也解释了即使右端精确,矩阵的不确定度仍会影响解。
反例模式
极小的相对扰动也可能使矩阵奇异
很容易想把假设换成“矩阵的相对扰动很小”。取 A=diag(1,10−6)、E=diag(0,−10−6)。在无穷范数下 ∥E∥/∥A∥=10−6,但 A+E=diag(1,0) 奇异,(A+E)y=(0,1)T 无解。定理的假设恰好不成立:A−1E=diag(0,−1) 的范数为一。正确的小量条件是 ∥A−1E∥<1;由于 ∥A−1E∥≤κ(A)∥E∥/∥A∥,条件 ∥E∥/∥A∥<1/κ(A) 足以保证它。
缩放例子
令 A=diag(1000,1)、b=(1000,1)T。解是 (1,1)T,而 κ∞(A)=1000。把第一条方程乘以 1/1000,矩阵变为单位矩阵,其无穷范数条件数为一。精确解没有改变,但两个新右端分量发生同样大小绝对扰动的含义改变了。若原本以物理单位量度不确定度,必须随方程一起转换,然后才比较误差界。缩放可改善数值行为,但原始测量仍限制准确度。
计算解的后向误差
残差也有后向解释。给定 x 和 r=b−Ax,同一向量是 Ax=b−r 的精确解。因此 b=0 时,∥r∥/∥b∥ 衡量一个足以解释结果的右端扰动。若也容许改变 A,它未必是最小后向误差;当 A 和 b 的不确定度或单位不同时,这个区别尤其重要。
例如 A=[2112]、b=(3,3)T、x=(1,0.99)T,则 Ax=(2.99,2.98)T,r=(0.01,0.02)T。无穷范数下右端后向误差为 0.02/3。精确解为 (1,1)T,相对前向误差为 0.01。由 ∥A∥∞=3 及 ∥A−1∥∞=1,条件数为 3,残差界给出至多 3(0.02/3)=0.02,与实际误差一致。误差界不必达到等号才有用。
消元为何保持方程组
交换方程、以非零数乘方程,以及把一条方程的倍数加到另一条,都是可逆行运算。对系数矩阵及右端同时运算,可保持解集。每个运算相当于左乘可逆初等矩阵;这些矩阵的乘积把 A 化成 U,整理乘积并记录换行,便得到 PA=LU。次序十分重要:较后的换行也须反映在构造 L 所记录的先前乘数中。
对角线非零的三角系统有唯一解:最后一条方程决定最后一个未知数,然后以归纳法逐个向上决定。若对角元素为零,普通回代公式不能除以它;须另行检查是否相容及是否有自由变量。软件遇到奇异或数值困难时应报告,而非悄悄除以极小或零主元并声称结果可靠。
条件与算法质量
A=I 时,问题在任何诱导范数下都有最佳条件;但若算法故意返回 2b,误差仍然很大。这说明良好条件本身不保证任意方法准确。相反,稳定求解病态系统可以得到小后向误差,前向误差却大得多;当输入数据不确定时,后者可能无法避免。区分两者有助判断应改善算法、取得更精确测量,还是改变问题的表述。
下面最后一道练习使用对角矩阵 A=diag(1,0.01),因此可以直接看出误差方向及放大。b 的第二分量很小,绝对扰动 0.001 是该分量的十分之一;除以对应对角元素 0.01 后,解改变 0.1。范数相对残差却把 0.001 与 b 最大分量一比较,所以可能掩盖某个分量的大相对扰动。当分量尺度不同时,逐分量分析可能更能反映测量模型。无论选用哪个尺度,都须清楚说明它如何对应实际数据。
常见错误
沿用选主元的 2×2 例子的因子,若解 Ly=b 而非 Ly=Pb,得 y=(5,21/2)T,再得 x=(17,−21)T。这个向量解的是 4x1+3x2=5、2x1+x2=13:A 的行已交换,右端却保留原次序。只有先把 b 置换成 Pb=(13,5)T,才得到正确解 (1,3)T。
精确消元成立,浮点版本仍可能失败。对 [ε111]x=(1,2)T,取 ε=10−20,精确解两个分量与一的距离都小于 10−19。若不换行,二进制双精度使用乘数 1020,把 1−1020 和 2−1020 都舍入为 −1020,得 x2=1,再得 x1=(1−1)/ε=0。部分选主元法先交换两行,乘数变为 ε,在工作精度下两个分量都是一。
总结
精确算术中,消元及回代可解非奇异方阵系统;部分选主元法选较大的可用主元,并以 P 记录换行。重用分解 PA=LU 时,须把相同置换施于每个右端。有限算术中,即使精确消元有效,也须留意小主元、中间元素增长和舍入。
残差显示候选向量多接近满足所写方程,也提供右端后向误差。条件数在指定范数下界定扰动对解的影响;小残差配合大条件数,仍可能容许可观的前向误差。条件界描述最坏情况,并非预测每个误差方向都被同样放大。
比较两个系统时,除矩阵和范数外,还应记录单位与缩放。重新缩放方程会改变扰动的范数描述,却不改变产生数据的物理测量。数据不确定时,赋予显示位数意义之前,须先结合这些不确定度解读数值结果。
练习
快速检查
(消元求解 2x+y=5、4x+3y=13,并检查残差。)
解答 · 答案
第二式减第一式两倍得 y=3,故 x=1;代入两式均成立,残差为零。
快速检查
(求 A=diag(2,0.5) 的 κ∞(A)。)
计算 A 及 A−1 的行和。
解答 · 答案
无穷范数是绝对行和最大值:∥A∥∞=2,∥A−1∥∞=2,条件数为 4。
快速检查
(若非奇异系统的计算向量在精确算术下残差为零,可得什么结论?)
利用 A(x−x)=r。
解答 · 答案
由 A(x−x)=0 和非奇异性得 x=x。这要求精确零残差;舍入后显示零并不足以证明。
快速检查
(对 A=diag(1,0.01)、b=(1,0.01)T,取 x=(1,0.9)T。求精确解、残差、相对无穷范数残差及相对无穷范数误差,与条件数界比较;并说明为何残差可视为仅扰动右端的后向误差。)
解答 · 答案
精确解为 x=(1,1)T。因 Ax=(1,0.009)T,所以 r=(0,0.001)T;∥b∥∞=1,相对残差为 0.001。误差为 (0,0.1)T,相对无穷范数为 0.1。由 ∥A∥∞=1、∥A−1∥∞=100,条件数界为 100(0.001)=0.1,本例恰达等号。最后 Ax=b−r,故 x 精确地解了右端扰动 −r 后的系统。即使前向误差是相对残差的一百倍,这个后向结论仍然成立。