2.3_扰动分析

2.3 扰动分析

在实际应用中, 所给的数据 (系数矩阵 AA 和右端项 bb ) 往往是通过实验或观测等方式获得的, 因此通常是带有误差的, 这也导致最后求得的数值解也是有误差的. 本节就讨论原始数据误差对最后数值解的影响.

2.3.1 矩阵条件数

定义2.1 考虑线性方程组 Ax=bAx = b , 如果 AA 或 bb 的微小变化会导致解的巨大变化, 则称此线性方程组是病态的, 反之则是良态的.

例2.5 考虑线性方程组 Ax=bAx = b ，其中 A=[1111.0001]A = \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix} ， b=[2,2]Tb = [2,2]^{\mathsf{T}} ，可求得其解为 x=[2,0]Tx = [2,0]^{\mathsf{T}} 。如果 bb 的第二个元素出现细微的偏差，变为 b=[2,2.0001]Tb = [2,2.0001]^{\mathsf{T}} ，则解就变为 x=[1,1]Tx = [1,1]^{\mathsf{T}} 。由此可见，当右端项出现细微变化时，解会出现很大的变化，因此该线性方程组是病态的。

线性方程组是否病态主要取决于其系数矩阵. 怎样来判断一个矩阵是否病态? 目前比较常用的一个指标就是矩阵条件数.

定义2.2 设 AA 非奇异, ∥⋅∥\|\cdot\| 是任一算子范数, 则称

κ(A)≜∥A−1∥∥A∥\kappa (A) \triangleq \| A ^ {- 1} \| \| A \|

为 AA 的条件数.

常用的矩阵条件数有

κ2(A)≜∥A−1∥2∥A∥2,κ1(A)≜∥A−1∥1∥A∥1,κ∞(A)≜∥A−1∥∞∥A∥∞.\kappa_ {2} (A) \triangleq \| A ^ {- 1} \| _ {2} \| A \| _ {2}, \quad \kappa_ {1} (A) \triangleq \| A ^ {- 1} \| _ {1} \| A \| _ {1}, \quad \kappa_ {\infty} (A) \triangleq \| A ^ {- 1} \| _ {\infty} \| A \| _ {\infty}.

κ2(A)\kappa_{2}(A) 也称为谱条件数, 当 AA 对称时, 有

κ2(A)=max⁡1≤i≤n∣λi∣min⁡1≤i≤n∣λi∣.\kappa_{2}(A) = \frac{\max\limits_{1\leq i\leq n}|\lambda_{i}|}{\min\limits_{1\leq i\leq n}|\lambda_{i}|}.

一般情况下, 如果没有特别指出, 则 κ(A)\kappa(A) 指的是矩阵 AA 的谱条件数.

例2.6 设 A=[1111.0001]A = \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix} , 则 A−1=[10001−10000−1000010000]A^{-1} = \begin{bmatrix} 10001 & -10000 \\ -10000 & 10000 \end{bmatrix} , 因此

κ2(A)≈4.0002×104,κ1(A)=κ∞≈4.0004×104.\kappa_ {2} (A) \approx 4. 0 0 0 2 \times 1 0 ^ {4}, \quad \kappa_ {1} (A) = \kappa_ {\infty} \approx 4. 0 0 0 4 \times 1 0 ^ {4}.

由此可见, AA 是非常病态的

条件数是衡量一个矩阵是否病态的主要指标。当矩阵条件数比较大时，我们就称这个矩阵是病态（或者坏条件）的。由 (2.17) 可知，如果矩阵是病态的，则近似解的误差受数据扰动的影响就可能会很大。
如果一个矩阵的某列的2-范数明显远远小于其他列，则该矩阵通常是病态的.

例2.7 Hilbert矩阵是一个典型的病态矩阵, 其定义如下:

Hn=[hij]n×n,其 中hij=1i+j−1.H _ {n} = [ h _ {i j} ] _ {n \times n}, \quad \text {其 中} \quad h _ {i j} = {\frac {1}{i + j - 1}}.

可以验证 HnH_{n} 是对称正定的，但随着 nn 的增长，其条件数会快速增长，见下表：

表 2.1. Hilbert 矩阵的条件数

2.3.2 δx\delta x 与 x^\hat{x} 的关系

设 x∗x_{*} 是精确解, x^\hat{x} 是通过数值计算得到的近似解. 假定 x^\hat{x} 满足线性方程组

(A+δA)x^=b+δb.(A + \delta A) \hat {x} = b + \delta b.

下面讨论 δx≜x^−x∗\delta x \triangleq \hat{x} - x_{*} 的大小, 即向后误差分析.

定理2.13 设 ∥⋅∥\|\cdot\| 是任一向量范数（当该范数作用在矩阵上时就是相应的导出范数），则 δx\delta x 与 x^\hat{x} 满足下面的关系式

∥δx∥∥x^∥≤∥A−1∥∥A∥(∥δA∥∥A∥+∥δb∥∥A∥∥x^∥).\frac {\| \delta x \|}{\| \hat {x} \|} \leq \| A ^ {- 1} \| \| A \| \left(\frac {\| \delta A \|}{\| A \|} + \frac {\| \delta b \|}{\| A \| \| \hat {x} \|}\right).

当 δb=0\delta b = 0 时，有

∥δx∥∥x^∥≤κ(A)∥δA∥∥A∥,(2.19)\frac {\| \delta x \|}{\| \hat {x} \|} \leq \kappa (A) \frac {\| \delta A \|}{\| A \|}, \tag {2.19}

其中 κ(A)≜∥A−1∥∥A∥\kappa (A)\triangleq \| A^{-1}\| \| A\| (板书)

证明. 由等式 (A+δA)x^=b+δb=Ax∗+δb(A + \delta A)\hat{x} = b + \delta b = Ax_{*} + \delta b 可知 A(x^−x∗)=−δAx^+δbA(\hat{x} - x_{*}) = -\delta A\hat{x} + \delta b , 即

δx=A−1(−δAx^+δb).\delta x = A ^ {- 1} \left(- \delta A \hat {x} + \delta b\right).

所以

∥δx∥≤∥A−1∥⋅(∥δA∥⋅∥x^∥+∥δb∥),(2.20)\left\| \delta x \right\| \leq \left\| A ^ {- 1} \right\| \cdot \left(\left\| \delta A \right\| \cdot \left\| \hat {x} \right\| + \left\| \delta b \right\|\right), \tag {2.20}

即

∥δx∥∥x^∥≤∥A−1∥⋅∥A∥(∥δA∥∥A∥+∥δb∥∥A∥⋅∥x^∥).\frac {\| \delta x \|}{\| \hat {x} \|} \leq \| A ^ {- 1} \| \cdot \| A \| \left(\frac {\| \delta A \|}{\| A \|} + \frac {\| \delta b \|}{\| A \| \cdot \| \hat {x} \|}\right).

若 δb=0\delta b = 0 ，则可得

∥δx∥∥x^∥≤κ(A)∥δA∥∥A∥.\frac {\| \delta x \|}{\| \hat {x} \|} \leq \kappa (A) \frac {\| \delta A \|}{\| A \|}.

由(2.17)可知，如果矩阵是病态的，则近似解的误差受数据扰动的影响就可能会很大。

2.3.3 δx\delta x 与 x∗x_{*} 的关系

引理2.14 设 ∥⋅∥\| \cdot \| 是任一算子范数, B∈Rn×nB \in \mathbb{R}^{n \times n} . 若 ∥B∥<1\| B \| < 1 , 则 I−BI - B 可逆, 且有

(I−B)−1=∑k=0∞Bk和∥(I−B)−1∥≤11−∥B∥.(I - B) ^ {- 1} = \sum_ {k = 0} ^ {\infty} B ^ {k} \qquad {\text {和}} \qquad \| (I - B) ^ {- 1} \| \leq {\frac {1}{1 - \| B \|}}.

(板书)

证明. 由 ∥B∥<1\|B\| < 1 可知 ρ(B)<1\rho(B) < 1 , 所以 I−BI - B 的特征值都具有正实部, 故 I−BI - B 非奇异.

下面证明 (I−B)−1=∑k=0∞Bk(I - B)^{-1} = \sum_{k=0}^{\infty} B^{k} . 首先证明级数 ∑k=0∞Bk\sum_{k=0}^{\infty} B^{k} 收敛, 即其每个分量所对应的级数都收敛. 记 bij(k)b_{ij}^{(k)} 为 BkB^{k} 的第 (i,j)(i,j) 元素. 由范数的等价性可知, 存在常数 cc 使得对任意矩阵 X∈Rn×nX \in \mathbb{R}^{n \times n} 都有 ∥X∥F≤c∥X∥\|X\|_{F} \leq c \|X\| . 所以

∣bij(k)∣≤∥Bk∥F≤c∥Bk∥≤c∥B∥k.\left| b _ {i j} ^ {(k)} \right| \leq \left\| B ^ {k} \right\| _ {F} \leq c \left\| B ^ {k} \right\| \leq c \| B \| ^ {k}.

注意, 这里的常数 cc 与 BB 和 kk 都无关. 由条件 ∥B∥<1\| B\| < 1 可知, 级数 ∑k=0∞c∥B∥k\sum_{k = 0}^{\infty}c\| B\|^k 收敛, 所以级数 ∑k=0∞bij(k)\sum_{k = 0}^{\infty}b_{ij}^{(k)} 也收敛, 即 ∑k=0∞Bk\sum_{k = 0}^{\infty}B^{k} 收敛.

因为 lim⁡k→∞∥Bk∥=0\lim_{k\to \infty}\| B^k\| = 0 ，且 (I−B)(I+B+B2+⋯+Bk)=I−Bk+1(I - B)(I + B + B^{2} + \dots +B^{k}) = I - B^{k + 1} ，两边取极限可得

(I−B)∑k=0∞Bk=lim⁡k→∞(I−Bk+1)=I,(I - B) \sum_ {k = 0} ^ {\infty} B ^ {k} = \lim _ {k \rightarrow \infty} (I - B ^ {k + 1}) = I,

即

(I−B)−1=∑k=0∞Bk,(I - B) ^ {- 1} = \sum_ {k = 0} ^ {\infty} B ^ {k},

且

∥(I−B)−1∥=∥∑k=0∞Bk∥≤∑k=0∞∥Bk∥≤∑k=0∞∥B∥k=11−∥B∥.\| (I - B) ^ {- 1} \| = \left\| \sum_ {k = 0} ^ {\infty} B ^ {k} \right\| \leq \sum_ {k = 0} ^ {\infty} \| B ^ {k} \| \leq \sum_ {k = 0} ^ {\infty} \| B \| ^ {k} = \frac {1}{1 - \| B \|}.

由 (A+δA)x^=b+δb(A + \delta A)\hat{x} = b + \delta b 可得

δx=(A+δA)−1(b+δb−Ax∗−δAx∗)=(I+A−1δA)−1A−1(−δAx∗+δb).\begin{array}{l} \delta x = (A + \delta A) ^ {- 1} (b + \delta b - A x _ {*} - \delta A x _ {*}) \\ = (I + A ^ {- 1} \delta A) ^ {- 1} A ^ {- 1} (- \delta A x _ {*} + \delta b). \\ \end{array}

假定 ∥δA∥\| \delta A\| 很小, 满足 ∥A−1δA∥≤∥A−1∥∥δA∥<1\| A^{-1}\delta A\| \leq \| A^{-1}\| \| \delta A\| < 1 ，则由引理2.14可得

∥δx∥∥x∗∥≤∥(I+A−1δA)−1∥∥A−1∥(∥δA∥+∥δb∥∥x∗∥)≤∥A−1∥1−∥A−1∥∥δA∥(∥δA∥+∥δb∥∥x∗∥)\begin{array}{l} \frac {\| \delta x \|}{\| x _ {*} \|} \leq \| (I + A ^ {- 1} \delta A) ^ {- 1} \| \| A ^ {- 1} \| \left(\| \delta A \| + \frac {\| \delta b \|}{\| x _ {*} \|}\right) \\ \leq \frac {\| A ^ {- 1} \|}{1 - \| A ^ {- 1} \| \| \delta A \|} \left(\| \delta A \| + \frac {\| \delta b \|}{\| x _ {*} \|}\right) \\ \end{array}
=∥A−1∥∥A∥1−∥A−1∥∥A∥∥δA∥∥A∥(∥δA∥∥A∥+∥δb∥∥A∥∥x∗∥)≤κ(A)1−κ(A)∥δA∥∥A∥(∥δA∥∥A∥+∥δb∥∥b∥)\begin{array}{l} = \frac {\| A ^ {- 1} \| \| A \|}{1 - \| A ^ {- 1} \| \| A \| \frac {\| \delta A \|}{\| A \|}} \left(\frac {\| \delta A \|}{\| A \|} + \frac {\| \delta b \|}{\| A \| \| x _ {*} \|}\right) \\ \leq \frac {\kappa (A)}{1 - \kappa (A) \frac {\| \delta A \|}{\| A \|}} \left(\frac {\| \delta A \|}{\| A \|} + \frac {\| \delta b \|}{\| b \|}\right) \\ \end{array}

当 ∥δA∥→0\| \delta A\| \to 0 时，我们可得

∥δx∥∥x∗∥≤κ(A)1−κ(A)∥δA∥∥A∥(∥δA∥∥A∥+∥δb∥∥b∥)→κ(A)∥δb∥∥b∥.\frac {\| \delta x \|}{\| x _ {*} \|} \leq \frac {\kappa (A)}{1 - \kappa (A) \frac {\| \delta A \|}{\| A \|}} \left(\frac {\| \delta A \|}{\| A \|} + \frac {\| \delta b \|}{\| b \|}\right)\rightarrow \kappa (A) \frac {\| \delta b \|}{\| b \|}.

定理2.15 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 非奇异且 ∥A−1∥∥δA∥<1\| A^{-1} \| \|\delta A\| < 1 ，则

∥δx∥∥x∗∥≤κ(A)1−κ(A)∥δA∥∥A∥(∥δA∥∥A∥+∥δb∥∥b∥).(2.21)\frac {\| \delta x \|}{\| x _ {*} \|} \leq \frac {\kappa (A)}{1 - \kappa (A) \frac {\| \delta A \|}{\| A \|}} \left(\frac {\| \delta A \|}{\| A \|} + \frac {\| \delta b \|}{\| b \|}\right). \tag {2.21}

如果 ∣∣δA∣∣=0||\delta A|| = 0 ，则

1κ(A)∥δb∥∥b∥≤∥δx∥∥x∗∥≤κ(A)∥δb∥∥b∥.(2.22)\frac {1}{\kappa (A)} \frac {\| \delta b \|}{\| b \|} \leq \frac {\| \delta x \|}{\| x _ {*} \|} \leq \kappa (A) \frac {\| \delta b \|}{\| b \|}. \tag {2.22}

(板书)

证明. 只需证明 (2.19) 中的左边一个不等式即可. 由于 δA=0\delta A = 0 , 所以 Aδx=δbA \delta x = \delta b . 两边取范数, 然后同除 ∥x∗∥\|x_*\| 可得

∥A∥⋅∥δx∥∥x∗∥≥∥Aδx∥∥A−1b∥≥∥δb∥∥A−1∥⋅∥b∥.\frac {\| A \| \cdot \| \delta x \|}{\| x _ {*} \|} \geq \frac {\| A \delta x \|}{\| A ^ {- 1} b \|} \geq \frac {\| \delta b \|}{\| A ^ {- 1} \| \cdot \| b \|}.

所以结论成立.

定理2.16 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 非奇异, 则有

min⁡{∥δA∥2∥A∥2:A+δA奇 异}=1κ2(A)\min \left\{\frac {\| \delta A \| _ {2}}{\| A \| _ {2}}: A + \delta A \text {奇 异} \right\} = \frac {1}{\kappa_ {2} (A)}

(板书)

证明. 记 d≜min⁡{∥δA∥2:A+δA 奇异}d \triangleq \min \left\{\| \delta A \|_2 : A + \delta A \text{ 奇异} \right\} , 只需证明 d=1∥A−1∥2d = \frac{1}{\|A^{-1}\|_2} .

先证明 d≥1∥A−1∥2d \geq \frac{1}{\|A^{-1}\|_2} . 若 ∥δA∥2<∥A−1∥2−1\|\delta A\|_2 < \|A^{-1}\|_2^{-1} , 则

∥A−1δA∥2≤∥A−1∥2⋅∥δA∥2<1.\| A ^ {- 1} \delta A \| _ {2} \leq \| A ^ {- 1} \| _ {2} \cdot \| \delta A \| _ {2} < 1.

由引理2.14可知 I+A−1δAI + A^{-1}\delta A 非奇异.因此 A+δA=A(I+A−1δA)A + \delta A = A(I + A^{-1}\delta A) 也非奇异,这表明使得 A+δAA + \delta A 奇异的 δA\delta A 必须满足 ∥δA∥2≥∥A−1∥2−1\| \delta A\| _2\geq \| A^{-1}\| _2^{-1} ，即

d≥1∥A−1∥2.d \geq \frac {1}{\| A ^ {- 1} \| _ {2}}.

下面证明 d≤1∥A−1∥2d \leq \frac{1}{\|A^{-1}\|_2} , 即证明存在 δA\delta A 满足 ∥δA∥2=∥A−1∥2−1\| \delta A \|_2 = \| A^{-1} \|_2^{-1} 使得 A+δAA + \delta A 奇异. 由范数的定义可知

∥A−1∥2=max⁡∥x∥2=1∥A−1x∥2,\| A ^ {- 1} \| _ {2} = \max _ {\| x \| _ {2} = 1} \| A ^ {- 1} x \| _ {2},

故存在 xx 满足 ∥x∥2=1\| x\| _2 = 1 使得

∥A−1∥2=∥A−1x∥2.\| A ^ {- 1} \| _ {2} = \| A ^ {- 1} x \| _ {2}.

令 y=A−1x/∥A−1x∥2y = A^{-1}x / \| A^{-1}x\| _2 ，则 ∥y∥2=1\| y\| _2 = 1 ，且

∥xyT∥2=max⁡∥z∥2=1∥xyTz∥2=max⁡∥z∥2=1∣yTz∣⋅∥x∥2=max⁡∥z∥2=1∣yTz∣.\| x y ^ {\mathsf {T}} \| _ {2} = \max _ {\| z \| _ {2} = 1} \| x y ^ {\mathsf {T}} z \| _ {2} = \max _ {\| z \| _ {2} = 1} | y ^ {\mathsf {T}} z | \cdot \| x \| _ {2} = \max _ {\| z \| _ {2} = 1} | y ^ {\mathsf {T}} z |.

由于 ∣yTz∣≤∥y∥2⋅∥z∥2=1|y^{\mathsf{T}}z|\leq \| y\|_{2}\cdot \| z\|_{2} = 1 ，且当 z=yz = y 时有 ∣yTz∣=1|y^{\mathsf{T}}z| = 1 ，所以 ∥xyT∥2=1.\| xy^{\mathsf{T}}\|_{2} = 1. 构造

δA=−xyT∥A−1∥2,\delta A = - \frac {x y ^ {\mathsf {T}}}{\| A ^ {- 1} \| _ {2}},

则

∥δA∥2=∥xyT∥2∥A−1∥2=1∥A−1∥2.\| \delta A \| _ {2} = \frac {\| x y ^ {\mathsf {T}} \| _ {2}}{\| A ^ {- 1} \| _ {2}} = \frac {1}{\| A ^ {- 1} \| _ {2}}.

下面证明 A+δAA + \delta A 奇异. 我们只需证明以 A+δAA + \delta A 为系数矩阵的齐次线性方程组有非零解. 由于 ∥A−1x∥2=∥A−1∥2\| A^{-1}x\|_2 = \| A^{-1}\|_2 , 容易验证

(A+δA)y=AA−1x∥A−1x∥2−xyT∥A−1∥2y=x∥A−1∥2−x∥A−1∥2=0,(A + \delta A) y = A \frac {A ^ {- 1} x}{\| A ^ {- 1} x \| _ {2}} - \frac {x y ^ {\mathsf {T}}}{\| A ^ {- 1} \| _ {2}} y = \frac {x}{\| A ^ {- 1} \| _ {2}} - \frac {x}{\| A ^ {- 1} \| _ {2}} = 0,

即 A+δAA + \delta A 奇异, 所以 d≤1∥A−1∥2d \leq \frac{1}{\|A^{-1}\|_2} .

综上可得

d=min⁡{∥δA∥2:A+δA奇 异}=1∥A−1∥2.d = \min \left\{\| \delta A \| _ {2}: A + \delta A \text {奇 异} \right\} = {\frac {1}{\| A ^ {- 1} \| _ {2}}}.

定理2.16的结论对所有 pp -范数都成立，参见[49,80].

度量

distp(A)≜min⁡{∥δA∥p∥A∥p:A+δA奇 异}=1κp(A),\mathrm {d i s t} _ {p} (A) \triangleq \min \left\{\frac {\| \delta A \| _ {p}}{\| A \| _ {p}} : A + \delta A \text {奇 异} \right\} = \frac {1}{\kappa_ {p} (A)},

表示 AA 距离奇异矩阵集合的相对距离

2.3.4 δx\delta x 与残量的关系

这是研究线性方程组的扰动理论的一个较实用的方法.

记残量 (残差) 为 r=b−Ax^r = b - A\hat{x} , 则有

δx=x^−x∗=x^−A−1b=A−1(Ax^−b)=−A−1r,\delta x = \hat {x} - x _ {*} = \hat {x} - A ^ {- 1} b = A ^ {- 1} (A \hat {x} - b) = - A ^ {- 1} r,

所以可得

∥δx∥≤∥A−1∥∥r∥.\| \delta x \| \leq \| A ^ {- 1} \| \| r \|.

这个估计式的优点是不用去估计 δA\delta A 和 δb\delta b 的大小. 由于在实际计算中, rr 通常是可以计算的, 因此该估计式比较实用.

定理2.17 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 非奇异, ∥⋅∥\|\cdot\| 为任一算子范数. 记 r=b−Ax^r = b - A\hat{x} , 则

(1) 若存在 A^\hat{A} 满足 A^x^=b\hat{A} \hat{x} = b , 则 ∥A^−A∥≥∥r∥∥x^∥\| \hat{A} - A \| \geq \frac{\|r\|}{\|\hat{x}\|} ;

(2) 存在 δA\delta A 满足 ∥δA∥=∥r∥∥x^∥\| \delta A \| = \frac{\| r \|}{\| \hat{x} \|} , 使得 (A+δA)x^=b(A + \delta A) \hat{x} = b .

(板书)

证明. (1) 由 A^x^=b\hat{A}\hat{x} = b 可知

(A^−A)x^=b−Ax^=r.(\hat {A} - A) \hat {x} = b - A \hat {x} = r.

所以有

∥r∥=∥(A^−A)x^∥≤∥A^−A∥⋅∥x^∥,\| r \| = \| (\hat {A} - A) \hat {x} \| \leq \| \hat {A} - A \| \cdot \| \hat {x} \|,

即

∥A^−A∥≥∥r∥∥x^∥.\| \hat {A} - A \| \geq \frac {\| r \|}{\| \hat {x} \|}.

(2) 以 2-范数为例, 取 δA=rx^T∥x^∥22\delta A = \frac{r\hat{x}^{\mathsf{T}}}{\|\hat{x}\|_{2}^{2}} 即可.

2.3.5 相对扰动分析

前面给出了解的误差 δx\delta x 的界是与条件数 κ(A)\kappa(A) , δA\delta A 和 δb\delta b 成比例的. 在许多情况下, 这个界是令人满意的. 但有时会相差很大, 这个界就不能很好的反映实际计算中解的误差.

例2.8 设 A=[γ001],b=[γ1]A = \begin{bmatrix} \gamma & 0 \\ 0 & 1 \end{bmatrix}, b = \begin{bmatrix} \gamma \\ 1 \end{bmatrix} , 其中 γ>1\gamma > 1 . 则 Ax=bAx = b 的精确解为 x∗=[11]x_* = \begin{bmatrix} 1 \\ 1 \end{bmatrix} , 任何合理的直接法求得的解的误差都很小. 但系数矩阵的谱条件数为 κ2(A)=γ\kappa_2(A) = \gamma , 当 γ\gamma 很大时, κ2(A)\kappa_2(A) 也很大, 因此误差界 (2.17) 和 (2.18) 可以是很大.

针对这个问题, 我们按分量进行分析. 记

δA=[δa11δa22],δb=[δb1δb2],\delta A = \left[ \begin{array}{c c} \delta a _ {1 1} & \\ & \delta a _ {2 2} \end{array} \right], \quad \delta b = \left[ \begin{array}{c} \delta b _ {1} \\ \delta b _ {2} \end{array} \right],

并设 ∣δaij∣≤ε∣aij∣,∣δbi∣≤ε∣bi∣|\delta a_{ij}|\leq \varepsilon |a_{ij}|,|\delta b_i|\leq \varepsilon |b_i| .则

δx=[x^1−x1x^2−x2]=[δb1+b1δa11+a11−1δb2+b2δa22+a22−1]=[δb1+γδa11+γ−1δb2+1δa22+1−1]=[δb1−δa11δa11+γδb2−δa22δa22+1].\delta x = \left[ \begin{array}{c} \hat {x} _ {1} - x _ {1} \\ \hat {x} _ {2} - x _ {2} \end{array} \right] = \left[ \begin{array}{c} \frac {\delta b _ {1} + b _ {1}}{\delta a _ {1 1} + a _ {1 1}} - 1 \\ \frac {\delta b _ {2} + b _ {2}}{\delta a _ {2 2} + a _ {2 2}} - 1 \end{array} \right] = \left[ \begin{array}{c} \frac {\delta b _ {1} + \gamma}{\delta a _ {1 1} + \gamma} - 1 \\ \frac {\delta b _ {2} + 1}{\delta a _ {2 2} + 1} - 1 \end{array} \right] = \left[ \begin{array}{c} \frac {\delta b _ {1} - \delta a _ {1 1}}{\delta a _ {1 1} + \gamma} \\ \frac {\delta b _ {2} - \delta a _ {2 2}}{\delta a _ {2 2} + 1} \end{array} \right].

故

∥δx∥∞≤2ε1−ε.\| \delta x \| _ {\infty} \leq \frac {2 \varepsilon}{1 - \varepsilon}.

如果 δb=0\delta b = 0 ，则

∥δx∥∞≤ε1−ε.\| \delta x \| _ {\infty} \leq \frac {\varepsilon}{1 - \varepsilon}.

这个界与 (2.17) 或 (2.18) 相差约 γ\gamma 倍

相对条件数

为了得到更好误差界，我们引入相对条件数 κcr(A)\kappa_{cr}(A) ，即

κcr(A)≜∥∣A−1∣∣A∣∥,\kappa_ {c r} (A) \triangleq \left\| | A ^ {- 1} | | A | \right\|,

有时也称为Bauer条件数或Skeel条件数

假定 δA\delta A 和 δb\delta b 满足 ∣δA∣≤ε∣A∣|\delta A| \leq \varepsilon |A| 和 ∣δb∣≤ε∣b∣|\delta b| \leq \varepsilon |b| . 则由 (A+δA)x^=b+δb(A + \delta A)\hat{x} = b + \delta b 可得

∣δx∣=∣A−1(−δAx^+δb)∣≤∣A−1∣(∣δA∣∣x^∣+∣δb∣)≤∣A−1∣(ε∣A∣∣x^∣+ε∣b∣)=ε∣A−1∣(∣A∣∣x^∣+∣b∣).(2.23)\begin{array}{l} \left| \delta x \right| = \left| A ^ {- 1} \left(- \delta A \hat {x} + \delta b\right) \right| \\ \leq \left| A ^ {- 1} \right| \left(\left| \delta A \right| \left| \hat {x} \right| + \left| \delta b \right|\right) \\ \leq \left| A ^ {- 1} \right| (\varepsilon | A | | \hat {x} | + \varepsilon | b |) \\ = \varepsilon \left| A ^ {- 1} \right| \left(| A | | \hat {x} | + | b |\right). \tag {2.23} \\ \end{array}

若 δb=0\delta b = 0 ，则有

∥δx∥=∥∣δx∣∥≤ε∥∣A−1∣∣A∣∣x^∣∥≤ε∥∣A−1∣∣A∣∥∥x^∥,\left\| \delta x \right\| = \left\| | \delta x | \right\| \leq \varepsilon \left\| | A ^ {- 1} | | A | | \hat {x} | \right\| \leq \varepsilon \left\| | A ^ {- 1} | | A | \right\| \| \hat {x} \|,

即

∥δx∥∥x^∥≤∥∣A−1∣∣A∣∥ε=κcr(A)ε.(2.24)\frac {\left\| \delta x \right\|}{\left\| \hat {x} \right\|} \leq \left\| | A ^ {- 1} | | A | \right\| \varepsilon = \kappa_ {c r} (A) \varepsilon . \tag {2.24}

相对条件数有下面的性质

引理2.18 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 非奇异, D∈Rn×nD \in \mathbb{R}^{n \times n} 为非奇异对角矩阵, 则

κcr(DA)=κcr(A).\kappa_ {c r} (D A) = \kappa_ {c r} (A).

定理2.19 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 非奇异. 使得 ∣δA∣≤ε∣A∣|\delta A| \leq \varepsilon |A| , ∣δb∣≤ε∣b∣|\delta b| \leq \varepsilon |b| 成立, 且满足

(A+δA)x^=b+δb(A + \delta A) \hat {x} = b + \delta b

的最小的 ε>0\varepsilon > 0 称为按分量的相对向后误差, 其表达式为

ε=max⁡1≤i≤n∣ri∣(∣A∣∣x^∣+∣b∣)i,\varepsilon = \max _ {1 \leq i \leq n} \frac {\left| r _ {i} \right|}{\left(\left| A \right| \left| \hat {x} \right| + \left| b \right|\right) _ {i}},

其中 r=b−Ax^r = b - A\hat{x}

更多关于数值计算的稳定性和矩阵扰动分析方面的知识, 可以参考 [70, 122, 148].

Previous2.2_特殊方程组的求解
Next2.4_误差分析