扰动理论

本节要解决的问题

求解线性代数方程组

$Ax = b$

设计一个算法 $alg(A, b)$, 求出一个数值解

$$\hat x = alg(A, b)$$

数值解 $\hat x$，相当于求解下面扰动后的方程：

$(A + \delta A)\hat x = b + \delta b$

数值解与真解的差为：

$\delta x = \hat x - x$

则误差的的上界是多少？

$\delta x$ 的上界

$$\begin{align} \delta A x + (A + \delta A)\delta x =&\delta b\\ \delta x =& A^{-1}(-\delta A \hat x + \delta b) \end{align}$$

$$\| \delta x \| \leq \| A^{-1} \|( \| \delta A \|\cdot \| \hat x \| + \| \delta b \|)$$

$$\frac{ \| \delta x \|}{ \| \hat x \|} \leq \| A^{-1} \|\cdot \| A \|\cdot \left(\frac{ \| \delta A \|}{ \| A \|} + \frac{ \| \delta b \| }{ \| A \| \| \hat x \| } \right).$$

从而引用 条件数 的概念：

$$\kappa (A) = \| A^{-1} \|\cdot \| A \|.$$

注意：

• 上面的上界通过 $\hat x$ 依赖于 $\delta x$ 本身。
• 但这个上界比较实用。

改进 $\delta x$ 的上界

引理 2.1：

• 矩阵序列的每个分量收敛即可得到矩阵序列的收敛。
• 通过范数把矩阵序列收敛的问题转化数列收敛的问题。
• 灵活理解, 如果把 $X$ 变为 $-X$ 引理是否仍然成立？

$$\delta A x + (A + \delta A)\delta x = \delta b$$

不进行合并，直接算 $\delta x$

$$\begin{align} \delta x =& (A + \delta A)^{-1}(-\delta A x + \delta b) \\ = & [A(I + A^{-1}\delta A)]^{-1}(-\delta A x + \delta b) \\ = & (I + A^{-1}\delta A)^{-1}A^{-1}(-\delta A x + \delta b) \end{align}$$

$$\begin{aligned} \frac{\|\delta x\|}{\|x\|} & \leq\left\|\left(I+A^{-1} \delta A\right)^{-1}\right\| \cdot\left\|A^{-1}\right\|\left(\|\delta A\|+\frac{\|\delta b\|}{\|x\|}\right) \\ & \leq \frac{\left\|A^{-1}\right\|}{1-\left\|A^{-1}\right\| \cdot\|\delta A\|} \left(\|\delta A\|+\frac{\|\delta b\|}{\|x\|}\right) \text { by Lemma } 2.1 \\ &=\frac{\left\|A^{-1}\right\|\cdot \|A\|}{1-\left\|A^{-1}\right\| \cdot \|A\| \cdot \frac{ \| \delta A \| }{ \| A \| }}\left( \frac{\|\delta A\|}{\|A\|}+\frac{\|\delta b\|}{\|A\| \cdot\|x\|}\right) \\ & \leq \frac{\kappa(A)}{1-\kappa(A)\frac{\|\delta A\|}{ \| A \| }}\left(\frac{\|\delta A\|}{\|A\|}+\frac{\|\delta b\|}{\|b\|}\right) \end{aligned}$$

定理 2.1

• 反证法证明最小值至少是 $\frac{1}{\|A\|_2}$。
• 构造性证明最小值一定可以达到
• 为什么选择矩阵的 2 范数？

到病态问题的距离就是条件数的倒数。

$$\delta x = \hat x - x = \hat x - A^{-1}b = A^{-1}(A\hat x - b) = A^{-1}r$$

定理 2.2

• 给出了残量的范数和矩阵 $A$ 扰动的范数 $\| \delta A \|$ 之间的关系。
• 这里假设右端 $b$ 没有扰动。
• 与前面的向后误差的比较