数値行列代数における条件数が相対誤差の上限に比例することの証明
定義 1
与えられた行列 $A \in \mathbb{R}^{m \times n}$に対して、条件数 $\kappa (A)$を次のように定義する。 $$ \kappa(A) = \left\| A \right\| \left\| A^{\dagger} \right\| = {\frac{ \sigma_{1} }{ \sigma_{r} }} $$ ここで$\left\| \cdot \right\|$はフロベニウスノルム、$A^{\dagger}$は$A$の擬似逆行列である。$\sigma_{k}$は$A$の$k$番目に大きい特異値で、$r \le \min (m, n)$は$A$のランクである。$\kappa (A)$が大きければ$A$を悪条件行列ill-conditioned matrix、小さければ良条件行列well-conditioned matrixという。
定理
線形システム $A \mathbf{x} = \mathbf{b}$を解くアルゴリズムの相対誤差の上限は条件数に比例する。 $$ \frac{\left\| \bar{\mathbf{x}} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \varepsilon c \kappa(A) $$ ここで$\varepsilon > 0$は十分に小さい定数であり、より具体的にはマシンイプシロン $\epsilon$と見なしても差し支えない。$c = c(A, \mathbf{b})$は$A$と$\mathbf{b}$によって決まる。
説明
一見すると、一般的な条件数と数値行列代数における条件数はまったく異なる定義を持つように見える。行列に対する条件数がなぜあのように定義されるのかは、次の証明を見て初めて理解できる。
証明 2
$$ A \mathbf{x} = \mathbf{b} $$ $A \in \mathbb{R}^{m \times n}$と$\mathbf{b} \in \mathbb{R}^{m}$に対して上記のような線形システムを解くアルゴリズムがあるとするとき、$m = n$かつ$A$が可逆行列でない限り最小二乗法を用いることになり、$A$と$\mathbf{b}$それぞれにわずかな摂動perturbation $\varepsilon F$と$\varepsilon \mathbf{f}$が加えられると置かなければならない。 $$ \left( A + \varepsilon F \right) \mathbf{x} = \mathbf{b} + \varepsilon \mathbf{f} $$ このときの解は$\varepsilon$に従属するので$\mathbf{x} = \mathbf{x}(\varepsilon)$と置くことができ、$\mathbf{x} (0) = \mathbf{x}$である。$\mathbf{x}(\varepsilon)$は$\varepsilon = 0$の近傍で微分可能であり、これに対するテイラー展開は次のとおりである。 $$ \mathbf{x}(\varepsilon) = \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) $$ ここで$\mathbf{x} ' (0)$は$\varepsilon$に対する微分として求めることができる。 $$ \begin{align*} \left( A + \varepsilon F \right) \mathbf{x} \left( \varepsilon \right) =& \mathbf{b} + \varepsilon \mathbf{f} \\ \implies A \mathbf{x} ' \left( \varepsilon \right) + F \mathbf{x} \left( \varepsilon \right) + \varepsilon F \mathbf{x} ' \left( \varepsilon \right) =& \mathbf{f} \\ \implies A \mathbf{x} ' \left( 0 \right) + F \mathbf{x} \left( 0 \right) =& \mathbf{f} \\ \implies \mathbf{x} ' \left( 0 \right) =& A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \left( 0 \right) \right] \end{align*} $$ これを相対誤差について表そうとすると、ノルムの三角不等式 $|a-b| \le |a| + |b|$によって次の不等式を得る。 $$ \begin{align*} \mathbf{x}(\varepsilon) =& \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) \\ \implies \mathbf{x}(\varepsilon) - \mathbf{x} =& \varepsilon A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \end{align*} $$
一般化されたコーシー・シュワルツの不等式: $$ \left\| \mathbf{x} \right\| \left\| \mathbf{y} \right\| \ge \left< \mathbf{x} , \mathbf{y} \right> $$
一般化されたコーシー・シュワルツの不等式によって次の補助不等式を得る。 $$ \begin{align*} \left\| \mathbf{b} \right\| \le& \left\| A \right\| \left\| \mathbf{x} \right\| \\ \implies {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} \le & {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} \end{align*} $$ したがって$\mathbf{x}$に対する相対誤差は次のとおりである。 $$ \begin{align*} {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} + \left\| A \right\| {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A \right\| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{b} \right\| }} + {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \end{align*} $$ ここで$\left\| F \right\| / \left\| A \right\|$と$\left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$はそれ自体がそれぞれ$A$と$\mathbf{b}$に対する相対誤差であり、$c = \left\| F \right\| / \left\| A \right\| + \left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$と置いて十分に小さい$\varepsilon$に対して$O \left( \varepsilon^2 \right)$を無視すると、求めていた結果を得る。
■