Matrix Computations-Round-off error analysis

条件数

定义

设 $||·||$ 是 $\mathbb{C}^{n\times n}$ 上的一个满足 $||I||=1$ 的范数，假定

• $A\in \mathbb{C}^{n\times n}$ 且非奇异；
• $b\in \mathbb{R}^n$ 非零;
• $\delta A\in \mathbb{C}^{n\times n}$ 且$\left|A\right|^{-1}\left|\delta A\right|<1$ .

若 $x$ 和 $\delta x$ 分别是线性方程组

$$Ax=b\quad\text{和}\quad (A+\delta A)(x+\delta x)=b+\delta b$$

的解，则

$$\frac{\|\delta x\|}{\|x\|}\leq\frac{\kappa(A)}{1-\kappa(A)\frac{\|\delta A\|}{\|A\|}}\Big(\frac{\|\delta A\|}{\|A\|}+\frac{\|\delta b\|}{\|b\|}\Big)$$

其中，$\kappa(A)=||A||·||A^{-1}||$

我们将 $\kappa(A)=||A||·||A^{-1}||$ 称之为线性方程组 $Ax=b$ 的条件数。

病态和良态

通常，如果矩阵 $A$ 的条件数 $\kappa (A)$ 很大，则称 $A$ 是病态的；反之，若矩阵 $A$ 的条件数 $\kappa (A)$ 很小，则称 $A$ 是良态的；

条件数的等价性

由矩阵范数的等价性可推出，$\mathbb{R}^{n\times n}$ 上任意两个范数下的条件数 $\kappa\alpha(A)$和 $\kappa\alpha(B)$ 都是等价的, 即存在常数 $c_1$ 和 $c_2$ , 使得

$$c_1\kappa_\alpha(A)\leq\kappa_\beta(A)\leq c_2\kappa_\alpha(A).$$

推论和定理

设 $||·||$ 是 $\mathbb{C}^{n\times n}$ 上的一个满足 $||I||=1$ 的范数，假定

• $A\in \mathbb{C}^{n\times n}$ 且非奇异；

• $\delta A\in \mathbb{C}^{n\times n}$ 且$\left|A\right|^{-1}\left|\delta A\right|<1$ .

则 $A+\delta A$ 也是非奇异的，且有

$$\frac{\left\|(A+\delta A)^{-1}-A^{-1}\right\|}{\|A^{-1}\|}\leq\frac{\kappa(A)}{1-\kappa(A)\frac{\|\delta A\|}{\|A\|}}\frac{\|\delta A\|}{\|A\|}$$

设$A\in \mathbb{C}^{n\times n}$ 且非奇异，则

$$\min\Big\{\frac{\left\|\delta A\right\|_2}{\left\|A\right\|_2}:A+\delta A\text{奇异}\Big\}=\frac{1}{\left\|A\right\|_2\left\|A^{-1}\right\|_2}=\frac{1}{\kappa_2(A)}$$

注意，该定理在谱范数意义下成立。