函数 $f$ 的 条件数衡量的是， 当 $f$ 的输入参数发生微小变化时，$f$ 的输出结果可能变化的幅度。 正经一点说，函数的条件数是输入发生相对变化时，输出渐进最坏相对变化的值。 条件数表征了 $f$ 对于输入误差的敏感性 (sensitivity)。

我们称一个具有低条件数的问题是良态的， 相反，高条件数的问题则是病态的。 病态问题就是说，即使输入改变（误差）很小，输出都可能发生很大变化，导致正确的解很难找到。

上面讲的条件数是对于 函数/问题 而言的，矩阵也有条件数，为啥呢？ 因为矩阵就是一个函数，$Ax$ 就是一个线性变换。

考虑线性方程组 $Ax = b$，输入参数是 $A$ 和 $b$，输出参数是 $x$。假设 $A$ 是非奇异矩阵。

1. $b$ 的误差对解的影响： 假设 $b$ 有扰动 $\Delta b$，造成绝对误差 $\Delta x = x^* - x$，其中 $x^*$ 是数值解。 $$ \begin{aligned} A x^* &= b + \Delta b \\ A(x + \Delta x) &= b + \Delta b \end{aligned} $$ 那么有 $$ \begin{aligned} &A \Delta x = \Delta b \\ \Rightarrow\quad& \Delta x = A^{-1} \Delta b \\ \Rightarrow\quad& \left\lVert \Delta x \right\rVert \leq \left\lVert A^{-1} \right\rVert \left\lVert \Delta b \right\rVert \label{eq:Delta-b-1} \end{aligned} $$ 又由 $Ax = b$ 得到 $$ \begin{aligned} &Ax = b \\ \Rightarrow\quad& \left\lVert b \right\rVert \leq \left\lVert A \right\rVert \left\lVert x \right\rVert \label{eq:Delta-b-2} \end{aligned} $$

   从 \eqref{eq:Delta-b-1} 和 \eqref{eq:Delta-b-2} 可以得到 $$ \begin{aligned} \frac{\left\lVert \Delta x \right\rVert}{\left\lVert x \right\rVert} &\leq \left\lVert A \right\rVert \left\lVert A^{-1} \right\rVert \frac{\left\lVert \Delta b \right\rVert}{\left\lVert b \right\rVert} \quad (b \neq 0) \\ \frac{\left\lVert \Delta x \right\rVert / \left\lVert x \right\rVert} {\left\lVert \Delta b \right\rVert / \left\lVert b \right\rVert} &\leq \left\lVert A \right\rVert \left\lVert A^{-1} \right\rVert \end{aligned} $$

   因此 $c = \left\lVert A \right\rVert \left\lVert A^{-1} \right\rVert$ 是当 $b$ 有微小误差 $\Delta b$ 时，相对误差放大的上界。

2. $A$ 的误差对解的影响：假设 $A$ 有扰动 $\Delta A$，$b$ 是精确的，造成绝对误差 $\Delta x = x^* - x$，其中 $x^*$ 是数值解。 $$ \begin{aligned} (A + \Delta A) x^* &= b \\ (A + \Delta A) (x + \Delta x) &= b \\ A \Delta x + \Delta A x + \Delta A \Delta x &= 0 \end{aligned} $$

   忽略二阶小量 $\Delta A \Delta x$，得到 $$ \begin{aligned} A \Delta x + \Delta A x = 0 \\ \Delta x = - A^{-1} \Delta A x \end{aligned} $$

   两边取范数 $$ \begin{aligned} \left\lVert \Delta x \right\rVert &\leq \left\lVert A^{-1} \right\rVert \left\lVert \Delta A \right\rVert \left\lVert x \right\rVert \\ \frac{\left\lVert \Delta x \right\rVert}{\left\lVert x \right\rVert} &\leq \left\lVert A^{-1} \right\rVert \left\lVert \Delta A \right\rVert \\ \frac{\left\lVert \Delta x \right\rVert}{\left\lVert x \right\rVert} &\leq \left\lVert A^{-1} \right\rVert \left\lVert A \right\rVert \frac{\left\lVert \Delta A \right\rVert}{\left\lVert A \right\rVert} \\ \frac{\left\lVert \Delta x \right\rVert / \left\lVert x \right\rVert} {\left\lVert \Delta A \right\rVert / \left\lVert A \right\rVert} &\leq \left\lVert A^{-1} \right\rVert \left\lVert A \right\rVert \end{aligned} $$

   因此 $c = \left\lVert A^{-1} \right\rVert \left\lVert A \right\rVert$ 是当 $A$ 有微小误差 $\Delta A$ 时，相对误差放大的上界。

所以综合 1、2 的结果，当输入 $A$、$b$ 有微小误差时，解 $x$ 的误差会被放大，而 $c$ 是相对误差放大的上界。

矩阵的条件数

设 $A \in \mathbb{R}^{n \times n}$ 是一个非奇异矩阵，$A$ 的 条件数 (condition number) 定义为

$$ \text{cond}(A) = \kappa(A) = \lVert A \rVert \lVert A^{-1} \rVert $$

其中，$\lVert \ \cdot \ \rVert$ 表示任意矩阵范数。

特别地，如果 $A$ 是奇异矩阵，定义 $\kappa(A) = \infty$（因为此时 $Ax=b$ 没有唯一解）。

矩阵条件数的性质：

1. $\kappa(A) \geq 1$，矩阵条件数最小为 1，意味着误差只被传播没有被放大。 $$ \kappa(A) = \lVert A \rVert \lVert A^{-1} \rVert \geq \lVert A A^{-1} \rVert = \lVert I \rVert = 1 $$
2. $\kappa(cA) = \kappa(A)$，其中 $c \neq 0$ 是一个常数。
3. $\kappa(Q) = 1$, 其中 $Q$ 是正交矩阵，这意味着当系数矩阵是正交矩阵时，误差不会被放大。

矩阵的条件数反应了线性方程组 $Ax = b$ 对于输入扰动的敏感程度/方程组的病态程度：

• 当条件数相对大时即 $\kappa(A) \gg 1$，我们说 $A$ 是 病态矩阵 (ill-conditioned matrix)，$Ax = b$ 是病态的；
• 当条件数相对小即接近 1 时，我们说 $A$ 是 良态矩阵 (well-conditioned matrix)，$Ax = b$ 是良态的。

在数值计算中，一般不用行列式来判断矩阵是否奇异，而是看矩阵的条件数，越大说明越接近奇异矩阵，越接近1越不奇异。 即使从代数上，一个矩阵是非奇异矩阵，如果它的条件数很大，从数值稳定性的角度看，它也几乎是奇异的。

但是，实际过程中如果要判断 $A$ 是否病态，计算 $A^{-1}$ 比较困难，有些情况可判定 $A$ 大概率是病态的：

• $A$ 阶梯形变换的过程中，出现小主元，这时 $A$ 可能病态。
• $A$ 某些行/列近似线性相关，这时 $A$ 可能病态。
• $A$ 元素绝对值/量级相差很大，并且无一定规则，这时 $A$ 可能病态。

Example 1.

$$ A = \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix} $$

这个矩阵是非奇异的，但是行 1 和行 2 几乎是线性相关的，$A$ 是病态的。

考虑以 $A$ 为系数矩阵的方程组 $Ax = b$：

$$ \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 2 \end{bmatrix} $$

它的精确解为 $x = [ 2, 0 ]^T$，如果 $b$ 发生微小误差 $\Delta b = [ 0, 0.0001 ]^T$， 方程组为：

$$ \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix} \begin{bmatrix} x_1 + \Delta x_1 \\ x_2 + \Delta x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 2.0001 \end{bmatrix} $$

此时方程组的解 $x = [ 1, 1 ]^T$，解的误差为 $\Delta x = [ -1, 1 ]^T$， 即 $b$ 的误差被放大了 $10^4$ 倍。

$A$ 的条件数（以无穷/行和范数）：

$$ A^{-1} = \frac{1}{1.0001 - 1} \begin{bmatrix} 1.0001 & -1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 10001 & -10000 \\ -10000 & 10000 \end{bmatrix} $$

$$ \begin{aligned} \kappa_{\infty}(A) &= \lVert A \rVert _{\infty} \lVert A^{-1} \rVert _{\infty} \\ &= (1 + 1.0001) \times (10001 + 10000) \\ &\approx 4 \times 10^4 \end{aligned} $$

Example 2.

$$ A = \begin{bmatrix} 1 & 10^4 \\ 1 & 1 \end{bmatrix}, \quad A^{-1} = \frac{1}{10^4 - 1} \begin{bmatrix} -1 & 10^4 \\ 1 & -1 \end{bmatrix} $$

$A$ 元素的量级相差很大，是病态的，它的条件数：

$$ \begin{aligned} \kappa_{\infty}(A) &= \lVert A \rVert _{\infty} \lVert A^{-1} \rVert _{\infty} \\ &= (10^4 + 1) \times \frac{1}{10^4 - 1} (10^4 + 1) \\ &= \frac{(10^4 + 1)^2}{10^4 - 1} \approx 10^4 \end{aligned} $$

Until next time!