5.8 条件数：逆行列と線形方程式系
この節では、行列およびベクトルのノルムの応用として、行列の逆行列や線形方程式系の解を数値的に求めた際に発生する誤差の上限を評価する問題を考えます。
非特異な行列 \(A \in M_n\) の逆行列をデジタル計算機上で浮動小数点演算によって計算する場合、丸め誤差や打ち切り誤差は避けられません。さらに、行列 \(A\) の各要素が実験や測定によって得られる場合、それ自体に誤差が含まれていることもあります。では、計算誤差やデータ誤差は、計算された逆行列の要素にどのような影響を与えるでしょうか？
多くのアルゴリズムにおいて、計算中の丸め誤差とデータ誤差は同様のモデルで表すことができます。ある行列ノルム \( \| \cdot \| \) が与えられており、\(A \in M_n\) が非特異であるとします。実際に計算で扱うのは \(B = A + \Delta A\) であり、次の条件を仮定します。
\|A^{-1}\Delta A\| \lt 1
この条件により、\(B\) が非特異であることが保証されます。なぜなら、\(B = A(I + A^{-1}\Delta A)\) かつ \(\rho(A^{-1}\Delta A) \le \|A^{-1}\Delta A\| \lt 1\) であるため、\(-1 \notin \sigma(A^{-1}\Delta A)\) だからです。
次の式が成り立ちます。
A^{-1}(\Delta A)B^{-1} = A^{-1}(B - A)B^{-1} = A^{-1} - B^{-1}
したがって、
\|A^{-1} - B^{-1}\| = \|A^{-1}\Delta A B^{-1}\| \le \|A^{-1}\Delta A\| \|B^{-1}\|
また、\(B^{-1} = A^{-1} - A^{-1}(\Delta A)B^{-1}\) から、
\|B^{-1}\| \le \|A^{-1}\| + \|A^{-1}\Delta A B^{-1}\| \le \|A^{-1}\| + \|A^{-1}\Delta A\| \|B^{-1}\|
これを変形すると、次の不等式が得られます。
\|B^{-1}\| = \|(A + \Delta A)^{-1}\| \le \frac{\|A^{-1}\|}{1 - \|A^{-1}\Delta A\|}
これと前の結果を組み合わせると、次の評価式を得ます。
\|A^{-1} - B^{-1}\| \le \frac{\|A^{-1}\| \|A^{-1}\Delta A\|}{1 - \|A^{-1}\Delta A\|}
したがって、相対誤差の上限は次のようになります。
\frac{\|A^{-1} - (A + \Delta A)^{-1}\|}{\|A^{-1}\|} \le
\frac{\|A^{-1}\| \|A\|}{1 - \|A^{-1}\Delta A\|} \frac{\|\Delta A\|}{\|A\|}
ここで、行列ノルムに関して定義される「条件数（condition number）」を次のように定めます。
\kappa(A) =
\begin{cases}
\|A^{-1}\|\|A\| & A \text{が非特異な場合} \\
\infty & A \text{が特異な場合}
\end{cases}
任意の行列ノルムに対して、
\(\kappa(A) = \|A^{-1}\|\|A\| \ge \|A^{-1}A\| = \|I\| \ge 1\) が成り立ちます。
したがって、次の上限評価式が得られます。
\frac{\|A^{-1} - (A + \Delta A)^{-1}\|}{\|A^{-1}\|}
\le
\frac{\kappa(A)}{1 - \|A^{-1}\Delta A\|} \frac{\|\Delta A\|}{\|A\|}
さらに仮定を強化して、次の条件を満たすとします。
\|A^{-1}\| \|\Delta A\| \lt 1
このとき、\(\|A^{-1}\|\|\Delta A\| = \kappa(A) \frac{\|\Delta A\|}{\|A\|}\) であることから、先の評価式は次のように書けます。
\frac{\|A^{-1} - (A + \Delta A)^{-1}\|}{\|A^{-1}\|}
\le
\frac{\kappa(A)}{1 - \kappa(A)\frac{\|\Delta A\|}{\|A\|}} \frac{\|\Delta A\|}{\|A\|}
これは、データ誤差 \(\frac{\|\Delta A\|}{\|A\|}\) と行列の条件数 \(\kappa(A)\) に基づく、逆行列計算誤差の「事前評価（a priori bound）」です。つまり、計算を実行する前に既知の情報から誤差の上限を予測できるという意味を持ちます。
もし \( \|A^{-1}\|\|A\| \) が 1 より小さいだけでなく、非常に小さい場合、式 (5.8.6) の右辺はおおよそ \( \kappa(A)\|A\| / \|A\| \) のオーダーとなります。したがって、条件数 \( \kappa(A) \) が大きくない限り、逆行列における相対誤差はデータの相対誤差と同程度であると考えるのが妥当です。
逆行列の計算において、行列 \( A \) の条件数 \( \kappa(A) \) が大きい場合、\( A \) は「悪条件（ill-conditioned）」または「条件が悪い（poorly conditioned）」と呼ばれます。逆に、\( \kappa(A) \) が小さい（1に近い）場合には「良条件（well-conditioned）」、さらに \( \kappa(A) = 1 \) の場合には「完全に良条件（perfectly conditioned）」と呼びます。もちろん、これらの条件に関する評価は特定の行列ノルム \( \| \cdot \| \) に依存します。
演習1： \( A \in M_n \) が正則であり、スペクトルノルムが用いられているとき、なぜ \( \kappa(A) = \dfrac{\sigma_1(A)}{\sigma_n(A)} \)（最大特異値と最小特異値の比）となるのかを説明しなさい。
演習2： \( U, V \in M_n \) がユニタリ行列であり、(5.8.3) においてユニタリ不変ノルムが用いられている場合、なぜ \( \kappa(A) = \kappa(UAV) \) が成り立つのかを説明しなさい。すなわち、ユニタリ変換を行っても行列の条件数（すなわち条件の良さ）は悪化しません。この性質は、数値線形代数における多くの安定なアルゴリズムの基礎となっています。
演習3： \( A \in M_n \) が正則なとき、スペクトルノルムに関して \( \kappa(A) = 1 \) が成り立つのは、\( A \) がユニタリ行列のスカラー倍である場合に限ることを説明しなさい。
演習4： 任意の \( A, B \in M_n \) に対して、どのような行列ノルムでも次が成り立つことを示しなさい。
\kappa(AB) \le \kappa(A)\kappa(B)
したがって、一連の変換を受ける行列の条件数の増加に対して上界を与えることができます。もしそれぞれの変換がユニタリである場合、何が言えるでしょうか？
同様の考察により、連立一次方程式の解の精度に対して、事前に（a priori）誤差の上界を与えることができます。
線形方程式系
A x = b, \quad A \in M_n \text{（正則）}, \quad b \in \mathbb{C}^n \text{（非零）}
を解きたいとします。しかし、計算誤差やデータの不確かさのため、実際には次のような摂動を受けた系を（正確に）解くことになります。
(A + \Delta A)\,\tilde{x} = b + \Delta b, \quad
A,\,\Delta A \in M_n, \ b,\,\Delta b \in \mathbb{C}^n, \
\tilde{x} = x + \Delta x
ここで、\(\tilde{x}\) と \(x\) の差、すなわち \(\Delta x\) はどの程度大きくなりうるでしょうか？
行列ノルムおよびそれに両立するベクトルノルムを用いることで、解の相対誤差を、データの相対誤差および行列 \(A\) の条件数 \( \kappa(A) \) の関数として評価する上界を導くことができます。
行列ノルム \( \| \cdot \| \) を \( M_n \) 上に、またそれと両立するベクトルノルム \( \| \cdot \| \) を \( \mathbb{C}^n \) 上に定め、再び不等式 (5.8.0) が成り立つと仮定します。線形方程式 \( A x = b \) が与えられているとき、実際に解く系は次のようになります。
(A + \Delta A)\,\tilde{x} \\
= (A + \Delta A)(x + \Delta x) \\
= A x + (\Delta A)x + (A + \Delta A)\Delta x \\
= b + (\Delta A)x + (A + \Delta A)\Delta x \\
= b + \Delta b
したがって、次の関係式が得られます。
(\Delta A)x + (A + \Delta A)\Delta x = \Delta b
よって、次の式が導かれます。
\Delta x = (A + \Delta A)^{-1}(\Delta b - (\Delta A)x)
このとき、ノルムを取ると
\|\Delta x\| = \|(A + \Delta A)^{-1}(\Delta b - (\Delta A)x)\| \\
\le \| (A + \Delta A)^{-1} \| \big( \| \Delta b \| + \| (\Delta A)x \| \big)
ここで (5.8.2) と両立性を用いると、次が得られます。
\|\Delta x\| \le
\frac{\|A^{-1}\|}{1 - \|A^{-1}\Delta A\|}
\big( \|\Delta b\| + \|\Delta A\|\,\|x\| \big)
したがって、両辺を \(\|x\|\) で割ると、次の相対誤差の評価式が得られます。
\frac{\|\Delta x\|}{\|x\|}
\le
\frac{\|A^{-1}\|\,\|A\|}{1 - \|A^{-1}\Delta A\|}
\left(
\frac{\|\Delta b\|}{\|A\|\,\|x\|} + \frac{\|\Delta A\|}{\|A\|}
\right)
ここで条件数 \( \kappa(A) = \|A^{-1}\|\,\|A\| \) の定義と、\( \|b\| = \|A x\| \le \|A\| \|x\| \) を用いると、次が得られます。
\frac{\|\Delta x\|}{\|x\|}
\le
\frac{\kappa(A)}{1 - \|A^{-1}\Delta A\|}
\left(
\frac{\|\Delta b\|}{\|b\|} + \frac{\|\Delta A\|}{\|A\|}
\right)
さらに、より強い仮定 (5.8.6) を再び適用すれば、より単純な上界が得られます。
\frac{\|\Delta x\|}{\|x\|}
\le
\frac{\kappa(A)}{1 - \kappa(A)\frac{\|\Delta A\|}{\|A\|}}
\left(
\frac{\|\Delta b\|}{\|b\|} + \frac{\|\Delta A\|}{\|A\|}
\right)
この上界式は (5.8.6) と同様の性質と意味を持っています。すなわち、連立方程式の係数行列が良条件であれば、解の相対誤差はデータの相対誤差と同程度のオーダーになります。
次に、方程式 (5.8.7) の計算解 \( \hat{x} \) が与えられている場合、その解を用いて事後的な（a posteriori）誤差の上界を求めることができます。ここでも、行列ノルム \( \| \cdot \| \) がベクトルノルムと両立しているとします。真の解を \( x \)、残差ベクトルを \( r = b - A\hat{x} \) とおくと、次のように変形できます。
A^{-1}r = A^{-1}(b - A\hat{x}) = A^{-1}b - \hat{x} = x - \hat{x}
したがって、\(\|x - \hat{x}\| = \|A^{-1}r\| \le \|A^{-1}\|\,\|r\|\) となります。また、\(\|b\| = \|A x\| \le \|A\|\|x\|\) より、\(1 \le \|A\|\|x\|/\|b\|\) です。
これらを組み合わせると、次が導かれます。
\|x - \hat{x}\|
\le \|A^{-1}\|\,\|r\|
\le
\frac{\|A\|\|x\|}{\|b\|}\,\|A^{-1}\|\,\|r\|
= \|A\|\|A^{-1}\|\,\frac{\|r\|}{\|b\|}\,\|x\|
したがって、計算解と真の解の相対誤差には次の上界が成り立ちます。
\frac{\|x - \hat{x}\|}{\|x\|}
\le
\kappa(A)\,\frac{\|r\|}{\|b\|}
ここで、条件数 \( \kappa(A) \) を計算する際に用いる行列ノルムは、ベクトルノルムと両立している必要があります。問題が良条件であれば、解の相対誤差は残差の大きさと同程度になります。しかし、悪条件の問題では、残差が小さく見えても、真の解から大きく離れている可能性があります。
行列ノルムを用いた誤差評価に共通する特徴は、その「保守性（conservatism）」です。すなわち、実際の誤差が小さい場合でも、上界は大きくなることがあります。しかし、要素が中程度の大きさを持つ行列 \( A \) の条件数が非常に大きい場合、\( A^{-1} \) には大きな成分を含むことが避けられず、数値計算においては十分な注意が必要です。
もし \(A x = b\) であり、\(C = [c_{ij}] = A^{-1}\) とおくと、恒等式 \(x = Cb\) を \(b_j\) の成分に関して微分すると次の関係が得られます。
\frac{\partial x_i}{\partial b_j} = c_{ij}, \quad i, j = 1, \ldots, n
さらに、\(C = A^{-1}\) を \(A\) の関数と考えると、\(C\) の各成分は \(A\) の成分に関する有理関数であるため、微分可能です。恒等式 \(CA = I\) から次が成り立ちます。
\sum_{p=1}^{n} c_{ip} a_{pq} = \delta_{iq}, \quad i, q = 1, \ldots, n
この式を \(a_{jk}\) に関して微分すると、
\sum_{p=1}^{n}
\frac{\partial c_{ip}}{\partial a_{jk}} a_{pq}
+ \delta_{pq,jk} c_{ip}
= 0
添字の整理を行うと次の形になります。
\sum_{p=1}^{n}
\frac{\partial c_{ip}}{\partial a_{jk}} a_{pq}
+ \delta_{qk} c_{ij} = 0
したがって次の関係が得られます。
\sum_{p=1}^{n}
\frac{\partial c_{ip}}{\partial a_{jk}} a_{pk}
= -\delta_{qk} c_{ij},
\quad i, j, k = 1, \ldots, n
次に、恒等式 \(x = Cb\) を \(a_{jk}\) に関して微分します。
\frac{\partial x_i}{\partial a_{jk}}
= \sum_{p=1}^{n}
\frac{\partial c_{ip}}{\partial a_{jk}} b_p
ここで、\(b_p = \sum_{q=1}^{n} a_{pq} x_q\) であることを代入すると、
\frac{\partial x_i}{\partial a_{jk}}
= \sum_{p=1}^{n} \sum_{q=1}^{n}
\frac{\partial c_{ip}}{\partial a_{jk}} a_{pq} x_q
これを整理すると次のようになります。
\frac{\partial x_i}{\partial a_{jk}}
= \sum_{q=1}^{n}
\left(
\sum_{p=1}^{n}
\frac{\partial c_{ip}}{\partial a_{jk}} a_{pq}
\right) x_q
= \sum_{q=1}^{n}
\left(
- \delta_{qk} c_{ij}
\right) x_q
= - c_{ij} x_k
よって、次の恒等式が得られます。
\frac{\partial x_i}{\partial a_{jk}}
= - c_{ij}
\sum_{p=1}^{n} c_{kp} b_p
したがって、式 (5.8.11) と (5.8.12) は、もし \(C = A^{-1}\) の成分の中に比較的大きな値が含まれている場合、解 \(x\) のある成分が、\(b\) や \(A\) のある成分の摂動に対して大きく、避けられない感度を持つことを警告しています。
行列解析の総本山
コメント