行列のノルムと線形方程式の条件数：誘導ノルム・後退誤差・特異行列までの距離

0. この記事の要点

連立一次方程式をコンピュータで解くと、答えには必ず小さな誤差が混じります。同じ計算でも、うまく解ける問題と、ほんの少しの誤差で答えが大きくずれる問題があります。この記事では「ずれやすさ」を 1 つの数（条件数）で測り、計算した答えが何桁まで信用できるかを事前に見積もる方法を、定義と証明から組み立てます。読み終えると、行列の「大きさ」を測る物差し（ノルム）と、誤差の 2 種類の測り方（前進誤差と後退誤差）の関係を説明できるようになります。

• $\mathbb{K}^n$（$\mathbb{K}=\mathbb{R}$ または $\mathbb{C}$）のノルムはすべて同値です。これは単位球面のコンパクト性から出ます。行列の誘導ノルムは $\|A\|_1$ が列和の最大、$\|A\|_\infty$ が行和の最大、$\|A\|_2$ が最大特異値です。
• スペクトル半径（固有値の絶対値の最大）は任意の誘導ノルム以下で、逆に $\varepsilon>0$ ごとに $\|A\|\le\rho(A)+\varepsilon$ となる誘導ノルムがあります。帰結として $A^k\to0\iff\rho(A)<1$ です。
• $\kappa(A)=\|A\|\|A^{-1}\|$ は線形方程式の相対的な感度の上限で、同時に「$A$ から特異行列までの相対距離の逆数」です（2 ノルムでは等式）。
• 近似解 $\boldsymbol{y}$ の後退誤差（$\boldsymbol{y}$ を厳密解にするためのデータの最小の相対摂動。「問題をどれだけ動かせば、いま得た答えが正解になるか」という測り方）は残差から閉じた式で計算できます。ノルムで測れば Rigal–Gaches の式、成分ごとに測れば Oettli–Prager の式です。
• 前進誤差 $\lesssim$ 条件数 $\times$ 後退誤差。Hilbert 行列では後退誤差が $10^{-17}$ 程度でも、前進誤差は $\kappa_2$ に比例して $n=13$ で 1 を超えます。
• エルミート行列の固有値は $\|E\|_2$ 以上には動きません（条件数 1）。離散 Laplace 行列の条件数は閉じた形 $\cot^2(\pi h/2)$ をもち、$4/(\pi^2h^2)$ にほぼ等しいことを示します。

この記事で使う事前知識

• 固有値と固有ベクトル: $A\boldsymbol{x}=\lambda\boldsymbol{x}$ を満たす数 $\lambda$ と 0 でないベクトル $\boldsymbol{x}$ のこと。→ 固有値と固有ベクトル
• 特異値分解: 任意の行列を、ユニタリ行列・非負の対角行列・ユニタリ行列の積に分ける分解。対角成分が特異値です。→ 行列の分解と標準形
• エルミート行列: 共役転置が自分自身に等しい行列（実行列なら対称行列）。→ エルミート行列
• ユニタリ行列: 列が互いに直交する単位ベクトルをなす行列。ベクトルの長さを変えません。→ ユニタリ行列
• コンパクト: どんな開被覆からも有限個を選んで覆える、という性質。$\mathbb{R}^n$ では有界閉集合のことです（Heine–Borel）。→ コンパクト

1. 動機

数値線形代数の結果を評価するとき、2 つの問いを分けて考えます。1 つは問題の感度、すなわちデータ $(A,\boldsymbol{b})$ を少し動かしたとき解 $\boldsymbol{x}$ がどれだけ動くか、です。これは算法に関係なく問題そのものの性質で、条件数で測ります。もう 1 つは算法の安定性、すなわち計算した $\widehat{\boldsymbol{x}}$ が「少し動かしたデータの厳密解」になっているか、です。これは後退誤差で測ります。後退誤差が単位丸め $u$ の程度に小さい算法を後退安定といいます。

この 2 つを掛け合わせると前進誤差の見積もり

$$\frac{\|\widehat{\boldsymbol{x}}-\boldsymbol{x}\|}{\|\boldsymbol{x}\|}\ \lesssim\ \kappa(A)\times(\text{後退誤差})$$

が得られます。たとえば部分ピボット選択つきの Gauss 消去は（ほとんどの行列で）後退安定なので、$\kappa(A)\approx10^{k}$ なら倍精度の 16 桁のうちおよそ $k$ 桁を失う、と事前に読めます。失った桁は算法の欠陥ではなく問題の性質で、算法を替えても取り戻せません。

この記事では、その物差しを用意します。ノルムを決め、条件数を定義し、摂動定理と後退誤差の公式を証明します。以後の章（LU 分解、QR 分解、最小二乗、固有値計算、反復法）はすべてこの物差しで評価されます。スカラーの問題の条件数と後退安定性の一般論は数値解析のテーマで扱い、この記事はその行列版です。

2. 準備

$\mathbb{K}$ は $\mathbb{R}$ または $\mathbb{C}$ です。内積は $\langle\boldsymbol{x},\boldsymbol{y}\rangle=\boldsymbol{y}^{*}\boldsymbol{x}$、行列の絶対値 $|A|$ は成分ごとにとり、行列・ベクトルの不等号 $|E|\le F$ も成分ごとです。$A\in M_{m,n}(\mathbb{K})$ の特異値を $\sigma_1\ge\sigma_2\ge\cdots$ と大きい順に書き、正則な $A\in M_n(\mathbb{K})$ では $\sigma_n>0$ が最小の特異値です（特異値分解（定理 4.1）［行列の分解と標準形］）。エルミート行列の固有値は $\lambda_1\ge\cdots\ge\lambda_n$ と大きい順に並べます。

記号の注意. 線形代数のテーマでは「作用素ノルム」$\|A\|$ はユークリッドノルムから誘導されるもの（この記事の $\|A\|_2$）を指しています。この記事では複数のノルムを扱うので、添字を付けて区別します。

3. ベクトルのノルムとその同値性

定義 3.1（ノルムと p ノルム）↗

写像 $\|\cdot\|\colon\mathbb{K}^n\to[0,\infty)$ が次の 3 条件を満たすときノルムという: (i) $\|\boldsymbol{x}\|=0\iff\boldsymbol{x}=\boldsymbol{0}$、(ii) $\|\alpha\boldsymbol{x}\|=|\alpha|\|\boldsymbol{x}\|$（$\alpha\in\mathbb{K}$）、(iii) $\|\boldsymbol{x}+\boldsymbol{y}\|\le\|\boldsymbol{x}\|+\|\boldsymbol{y}\|$。$1\le p<\infty$ について $\|\boldsymbol{x}\|_p=\bigl(\sum_i|x_i|^p\bigr)^{1/p}$、$\|\boldsymbol{x}\|_\infty=\max_i|x_i|$ を p ノルムという。2 つのノルム $\|\cdot\|_\alpha,\|\cdot\|_\beta$ が同値であるとは、定数 $0<c\le C$ があって全 $\boldsymbol{x}$ で $c\|\boldsymbol{x}\|_\alpha\le\|\boldsymbol{x}\|_\beta\le C\|\boldsymbol{x}\|_\alpha$ となることをいう。

$p=1,2,\infty$ がノルムであることは、三角不等式が $p=1,\infty$ では成分ごとの三角不等式から、$p=2$ では内積のノルムの三角不等式（Cauchy–Schwarz の不等式の帰結）から出ます。この記事で使うのはこの 3 つです。

補題 3.2（有限次元のノルムの同値性）✓

$\mathbb{K}^n$ 上の任意の 2 つのノルムは同値である。

証明（補題 3.2）

同値は推移的（$c_1\|\cdot\|_\alpha\le\|\cdot\|_\beta\le C_1\|\cdot\|_\alpha$ と $c_2\|\cdot\|_\beta\le\|\cdot\|_\gamma\le C_2\|\cdot\|_\beta$ を合わせれば $c_1c_2\|\cdot\|_\alpha\le\|\cdot\|_\gamma\le C_1C_2\|\cdot\|_\alpha$）なので、任意のノルム $\|\cdot\|$ が $\|\cdot\|_2$ と同値であることを示せば十分です。$\mathbb{C}^n$ は実部と虚部に分けて $\mathbb{R}^{2n}$ と同一視し、$\|\cdot\|_2$ はそのユークリッドノルムに一致します。以下 $N=n$（実）または $N=2n$（複素）とします。

上からの評価. 標準基底 $\boldsymbol{e}_i$ で $\boldsymbol{x}=\sum_ix_i\boldsymbol{e}_i$ と書くと、(ii)(iii) と Cauchy–Schwarz の不等式（定理 4.2）［内積空間とグラム・シュミット直交化］（$\mathbb{R}^n$ のベクトル $(|x_i|)_i$ と $(\|\boldsymbol{e}_i\|)_i$ に適用）から

$$\|\boldsymbol{x}\|\le\sum_{i=1}^n|x_i|\,\|\boldsymbol{e}_i\|\le C\|\boldsymbol{x}\|_2,\qquad C=\Bigl(\sum_{i=1}^n\|\boldsymbol{e}_i\|^2\Bigr)^{1/2}.$$

連続性. (iii) から $\bigl|\|\boldsymbol{x}\|-\|\boldsymbol{y}\|\bigr|\le\|\boldsymbol{x}-\boldsymbol{y}\|\le C\|\boldsymbol{x}-\boldsymbol{y}\|_2$ なので、$f(\boldsymbol{x})=\|\boldsymbol{x}\|$ は $\mathbb{R}^N$ のユークリッド位相で連続です。同じ理由で $\|\cdot\|_2$ も連続です。

下からの評価. 単位球面 $S=\{\boldsymbol{x}:\|\boldsymbol{x}\|_2=1\}$ は、連続関数 $\|\cdot\|_2$ による閉集合 $\{1\}$ の逆像なので閉集合で、$S\subset B(0,2)$ なので有界です。Heine–Borel の定理（定理 5.2）［コンパクト性］ により $S$ はコンパクトで、空でありません。連続関数 $f$ を $S$ に制限すると、最大値・最小値の定理（系 6.2）［コンパクト性］ により最小値 $c=f(\boldsymbol{x}_{\min})$ をとります。$\boldsymbol{x}_{\min}\ne\boldsymbol{0}$ なので (i) から $c>0$ です。任意の $\boldsymbol{x}\ne\boldsymbol{0}$ について $\boldsymbol{x}/\|\boldsymbol{x}\|_2\in S$ だから、(ii) により $\|\boldsymbol{x}\|=\|\boldsymbol{x}\|_2\,f(\boldsymbol{x}/\|\boldsymbol{x}\|_2)\ge c\|\boldsymbol{x}\|_2$ です。$\boldsymbol{x}=\boldsymbol{0}$ では両辺 0 です。

∎

同値性は「収束するか」「有界か」がノルムの選び方によらないことを意味します。ただし定数は $n$ に依存し、数値計算ではこの定数が問題になります。よく使う 3 つの間の最良の定数を記録しておきます。

命題 3.3（1・2・∞ ノルムの間の定数）✓

$\boldsymbol{x}\in\mathbb{K}^n$ について

$$\|\boldsymbol{x}\|_\infty\le\|\boldsymbol{x}\|_2\le\sqrt n\,\|\boldsymbol{x}\|_\infty,\qquad \|\boldsymbol{x}\|_2\le\|\boldsymbol{x}\|_1\le\sqrt n\,\|\boldsymbol{x}\|_2,\qquad \|\boldsymbol{x}\|_\infty\le\|\boldsymbol{x}\|_1\le n\|\boldsymbol{x}\|_\infty$$

が成り立ち、各不等式で等号が成り立つ $\boldsymbol{x}\ne\boldsymbol{0}$ がある。

証明（命題 3.3）

$|x_k|=\|\boldsymbol{x}\|_\infty$ となる $k$ をとると $\|\boldsymbol{x}\|_\infty^2=|x_k|^2\le\sum_i|x_i|^2\le n\|\boldsymbol{x}\|_\infty^2$ で 1 組目が出ます。$\|\boldsymbol{x}\|_1^2=\sum_{i,j}|x_i||x_j|\ge\sum_i|x_i|^2$ で 2 組目の左が、Cauchy–Schwarz の不等式（定理 4.2）［内積空間とグラム・シュミット直交化］ を $(|x_i|)_i$ と $(1,\ldots,1)$ に適用して $\|\boldsymbol{x}\|_1\le\sqrt n\|\boldsymbol{x}\|_2$ が出ます。3 組目は $|x_k|\le\sum_i|x_i|\le n\max_i|x_i|$ です。等号は、各組の左の不等式で $\boldsymbol{x}=\boldsymbol{e}_1$、右の不等式で $\boldsymbol{x}=(1,\ldots,1)^{\mathsf{T}}$ のときに成り立ちます。

∎

4. 行列のノルム

4.1. 誘導ノルムとその公式

定義 4.1（誘導ノルム）↗

$\mathbb{K}^n$ と $\mathbb{K}^m$ にノルムを 1 つずつ固定する（記号はどちらも $\|\cdot\|$）。$A\in M_{m,n}(\mathbb{K})$ に対し

$$\|A\|=\max_{\boldsymbol{x}\ne\boldsymbol{0}}\frac{\|A\boldsymbol{x}\|}{\|\boldsymbol{x}\|}=\max_{\|\boldsymbol{x}\|=1}\|A\boldsymbol{x}\|$$

を誘導ノルム（作用素ノルム）という。p ノルムから誘導したものを $\|A\|_p$ と書く。

最大値が存在することは次のとおりです。補題 3.2 の定数で $\|\boldsymbol{y}\|\le C'\|\boldsymbol{y}\|_2$（$\boldsymbol{y}\in\mathbb{K}^m$）、$c\|\boldsymbol{x}\|_2\le\|\boldsymbol{x}\|$（$\boldsymbol{x}\in\mathbb{K}^n$）とし、各行に Cauchy–Schwarz の不等式を使うと $\|A\boldsymbol{x}\|_2\le M\|\boldsymbol{x}\|_2$（$M=(\sum_{i,j}|a_{ij}|^2)^{1/2}$）です。よって $\bigl|\|A\boldsymbol{x}\|-\|A\boldsymbol{y}\|\bigr|\le C'M\|\boldsymbol{x}-\boldsymbol{y}\|_2$ で $\boldsymbol{x}\mapsto\|A\boldsymbol{x}\|$ は連続です。集合 $\{\|\boldsymbol{x}\|=1\}$ は $\|\boldsymbol{x}\|_2\le1/c$ で有界、連続関数 $\|\cdot\|$ による $\{1\}$ の逆像なので閉で、Heine–Borel の定理（定理 5.2）［コンパクト性］ によりコンパクトです。あとは 最大値・最小値の定理（系 6.2）［コンパクト性］ を使います。定義からただちに、$\|A\boldsymbol{x}\|\le\|A\|\|\boldsymbol{x}\|$、$\|AB\|\le\|A\|\|B\|$（$\|AB\boldsymbol{x}\|\le\|A\|\|B\boldsymbol{x}\|\le\|A\|\|B\|\|\boldsymbol{x}\|$）、$\|I\|=1$ が成り立ち、$\|\cdot\|$ は $M_{m,n}(\mathbb{K})$ 上のノルムです。

命題 4.2（1・∞・2 ノルムの公式）✓

$A=(a_{ij})\in M_{m,n}(\mathbb{K})$ について

1. $\|A\|_1=\max_j\sum_i|a_{ij}|$（列和の最大）。
2. $\|A\|_\infty=\max_i\sum_j|a_{ij}|$（行和の最大）。
3. $\|A\|_2=\sigma_1$（最大特異値）。とくに $\|A^{*}\|_2=\|A\|_2$。

証明（命題 4.2）

(1) $\|A\boldsymbol{x}\|_1=\sum_i|\sum_ja_{ij}x_j|\le\sum_j|x_j|\sum_i|a_{ij}|\le\bigl(\max_j\sum_i|a_{ij}|\bigr)\|\boldsymbol{x}\|_1$ です。列和が最大の列を $j_0$ とし $\boldsymbol{x}=\boldsymbol{e}_{j_0}$ をとると $\|A\boldsymbol{x}\|_1=\sum_i|a_{ij_0}|$ で等号に達します。

(2) $|(A\boldsymbol{x})_i|\le\sum_j|a_{ij}||x_j|\le\bigl(\sum_j|a_{ij}|\bigr)\|\boldsymbol{x}\|_\infty$ から $\le$ です。行和が最大の行を $i_0$ とし、$x_j=\overline{a_{i_0j}}/|a_{i_0j}|$（$a_{i_0j}=0$ なら $x_j=1$）とおくと $\|\boldsymbol{x}\|_\infty=1$（$A\ne0$ の場合。$A=0$ なら両辺 0）で、$(A\boldsymbol{x})_{i_0}=\sum_j|a_{i_0j}|$ となり等号に達します。

(3) 作用素ノルムと最良低階数近似（命題 4.3）［行列の分解と標準形］ の 1 がそのまま $\|A\|_2=\sigma_1$ です。$A=U\Sigma V^{*}$ なら $A^{*}=V\Sigma^{\mathsf{T}}U^{*}$ は $A^{*}$ の特異値分解で、0 でない特異値は同じなので $\|A^{*}\|_2=\sigma_1$ です（$A=0$ なら両辺 0）。

∎

1 ノルムと ∞ ノルムは成分から $O(mn)$ の演算で計算できますが、2 ノルムは特異値分解が要ります。条件数の推定に $\kappa_1$ や $\kappa_\infty$ が使われるのはこのためです。

4.2. Frobenius ノルムとユニタリ不変性

定義 4.3（Frobenius ノルム）↗

$\|A\|_F=\bigl(\sum_{i,j}|a_{ij}|^2\bigr)^{1/2}=\bigl(\operatorname{tr}A^{*}A\bigr)^{1/2}$ を $A\in M_{m,n}(\mathbb{K})$ の Frobenius ノルムという。

Frobenius ノルムは $A$ を $\mathbb{K}^{mn}$ のベクトルとみた 2 ノルムなのでノルムですが、どのベクトルノルムからも誘導されません（$n\ge2$ で $\|I\|_F=\sqrt n\ne1$）。

命題 4.4（ユニタリ不変性と Frobenius ノルム）✓

$A\in M_{m,n}(\mathbb{K})$、$\operatorname{rank}A=r$ とし、$U\in M_m(\mathbb{K})$、$V\in M_n(\mathbb{K})$ をユニタリ行列とする。

1. $\|UAV\|_2=\|A\|_2$、$\|UAV\|_F=\|A\|_F$。
2. $\|A\|_F^2=\sigma_1^2+\cdots+\sigma_r^2$。
3. $\|A\|_2\le\|A\|_F\le\sqrt r\,\|A\|_2$。

証明（命題 4.4）

(1) ユニタリ行列の特徴づけ（命題 3.2）［スペクトル定理］ の 3 から $\|U\boldsymbol{y}\|_2=\|\boldsymbol{y}\|_2$ です。よって $\|UAV\boldsymbol{x}\|_2=\|AV\boldsymbol{x}\|_2$ で、$\boldsymbol{x}$ が単位球面を動くと $V\boldsymbol{x}$ も単位球面全体を動く（$V$ は等長で全単射）ので、最大値は等しく $\|UAV\|_2=\|A\|_2$ です。Frobenius ノルムは $\|A\|_F^2=\sum_j\|\boldsymbol{a}_j\|_2^2$（$\boldsymbol{a}_j$ は列）なので $\|UA\|_F=\|A\|_F$、また $\|A\|_F=\|A^{*}\|_F$ なので $\|AV\|_F=\|V^{*}A^{*}\|_F=\|A^{*}\|_F=\|A\|_F$ です。

(2) 特異値分解（定理 4.1）［行列の分解と標準形］ $A=U\Sigma V^{*}$ に (1) を使えば $\|A\|_F=\|\Sigma\|_F=(\sum_{i\le r}\sigma_i^2)^{1/2}$ です。

(3) (2) と $\|A\|_2=\sigma_1$（命題 4.2）から $\sigma_1^2\le\sum_{i\le r}\sigma_i^2\le r\sigma_1^2$ です。

∎

直交変換・ユニタリ変換は 2 ノルムで測った誤差を拡大しません。QR 分解や固有値計算の算法が直交変換を積み重ねて作られるのは、この性質のためです。

5. スペクトル半径と誘導ノルム

定義 5.1（スペクトル半径）↗

$A\in M_n(\mathbb{C})$ の固有値の絶対値の最大 $\rho(A)=\max\{|\lambda|:\lambda\text{ は }A\text{ の固有値}\}$ をスペクトル半径という。実行列は複素行列とみなす。

定理 5.2（スペクトル半径と誘導ノルム）✓

$A\in M_n(\mathbb{C})$ とする。

1. $\mathbb{C}^n$ の任意のノルムから誘導されるノルムについて $\rho(A)\le\|A\|$。
2. 任意の $\varepsilon>0$ に対し、$\mathbb{C}^n$ のあるノルム $\|\cdot\|_{A,\varepsilon}$ が存在して、それから誘導されるノルムで $\|A\|_{A,\varepsilon}\le\rho(A)+\varepsilon$。

(2) の証明の方針は次のとおりです。Schur 分解で $A$ を上三角行列 $T$ にすると、対角成分が固有値になります。邪魔なのは対角より右上の成分です。対角行列 $D$ で挟んだ $D^{-1}TD$ は、対角成分を変えずに、対角から $j-i$ だけ離れた成分に $\delta^{j-i}$ を掛けます。$\delta$ を小さくとれば右上の成分をいくらでも小さくでき、行和の最大が $\rho(A)$ にいくらでも近づきます。

証明（定理 5.2）

(1) $A\boldsymbol{x}=\lambda\boldsymbol{x}$、$\boldsymbol{x}\ne\boldsymbol{0}$ なら $|\lambda|\|\boldsymbol{x}\|=\|A\boldsymbol{x}\|\le\|A\|\|\boldsymbol{x}\|$ で、$\|\boldsymbol{x}\|>0$ で割ります。

(2) まず、正則な $S$ について $\|\boldsymbol{x}\|_S:=\|S^{-1}\boldsymbol{x}\|_\infty$ は $\mathbb{C}^n$ のノルムで（(i)〜(iii) は $\|\cdot\|_\infty$ から移る）、それから誘導されるノルムは

$$\|A\|_S=\max_{\boldsymbol{x}\ne\boldsymbol{0}}\frac{\|S^{-1}A\boldsymbol{x}\|_\infty}{\|S^{-1}\boldsymbol{x}\|_\infty}=\max_{\boldsymbol{y}\ne\boldsymbol{0}}\frac{\|S^{-1}AS\boldsymbol{y}\|_\infty}{\|\boldsymbol{y}\|_\infty}=\|S^{-1}AS\|_\infty$$

です（$\boldsymbol{y}=S^{-1}\boldsymbol{x}$ とおいた）。Schur 分解（定理 3.1）［行列の分解と標準形］ で $A=UTU^{*}$（$U$ はユニタリ、$T$ は上三角で対角成分は固有値）と書きます。$\tau=\max_i\sum_{j>i}|t_{ij}|$ とおき、$0<\delta\le1$ を $\delta\tau\le\varepsilon$ となるようにとり、$D=\operatorname{diag}(1,\delta,\ldots,\delta^{n-1})$ とします。$D^{-1}TD$ の $(i,j)$ 成分は $\delta^{j-i}t_{ij}$（$j\ge i$）で、$j=i$ では固有値、$j>i$ では $|\delta^{j-i}t_{ij}|\le\delta|t_{ij}|$ です。命題 4.2 の 2 より

$$\|D^{-1}TD\|_\infty=\max_i\Bigl(|t_{ii}|+\sum_{j>i}\delta^{j-i}|t_{ij}|\Bigr)\le\rho(A)+\delta\tau\le\rho(A)+\varepsilon$$

です。$S=UD$ とおけば $S^{-1}AS=D^{-1}U^{*}AUD=D^{-1}TD$ なので、$\|\cdot\|_{A,\varepsilon}:=\|\cdot\|_S$ が求めるノルムです。

∎

(2) のノルムは $A$ と $\varepsilon$ に依存し、$\rho(A)$ に近づけるほど通常のノルムとの同値定数 $\delta^{-(n-1)}$ が大きくなります。$\rho(\cdot)$ 自体はノルムではありません（$\rho\bigl(\begin{smallmatrix}0&1\\0&0\end{smallmatrix}\bigr)=0$）。

系 5.3（行列の冪の収束）✓

$A\in M_n(\mathbb{C})$ について、$A^k\to0$（$k\to\infty$、成分ごと、あるいは同じことだが任意の行列ノルムで）$\iff\rho(A)<1$。さらに $\rho(A)<1$ なら、任意の誘導ノルムについて定数 $c>0$ と $\theta<1$ があって $\|A^k\|\le c\,\theta^k$。

証明（系 5.3）

行列のノルムは $M_n(\mathbb{C})\cong\mathbb{C}^{n^2}$ 上のノルムなので、補題 3.2 により「成分ごとに収束」と「あるノルムで収束」と「任意のノルムで収束」は同値です。

($\Leftarrow$) $\varepsilon=(1-\rho(A))/2$ として 定理 5.2 の 2 のノルムをとると、$\theta:=\|A\|_{A,\varepsilon}\le(1+\rho(A))/2<1$ で、劣乗法性から $\|A^k\|_{A,\varepsilon}\le\theta^k\to0$ です。別の誘導ノルム $\|\cdot\|$ とは 補題 3.2 の定数 $C$ で $\|A^k\|\le C\|A^k\|_{A,\varepsilon}\le C\theta^k$ となります。

($\Rightarrow$) $|\lambda|\ge1$ の固有値 $\lambda$ と固有ベクトル $\boldsymbol{x}\ne\boldsymbol{0}$ があれば $\|A^k\boldsymbol{x}\|_2=|\lambda|^k\|\boldsymbol{x}\|_2\ge\|\boldsymbol{x}\|_2$ なので、$\|A^k\|_2\ge1$ が全 $k$ で成り立ち、$A^k\not\to0$ です。

∎

注意 5.4

同じ減衰は 冪の減衰の補題（補題 7.3）［行列の固有値評価と不等式］ としても証明されています。より精密には、Banach 環の一般論である スペクトル半径公式（定理 6.7）［有界作用素と共役作用素］ を有限次元の $M_n(\mathbb{C})$ に当てはめると $\rho(A)=\lim_k\|A^k\|^{1/k}$ が任意の誘導ノルムで成り立ちます。定理 5.2 は、この極限を待たずに「1 回の積で $\rho(A)+\varepsilon$ 以下に縮む」ノルムを作れる、という有限次元に特有の主張です。定常反復法の収束（$\rho(M^{-1}N)<1$）はこの系で判定します。

6. 逆行列の摂動と条件数

この節では $\mathbb{K}^n$ に 1 つのノルムを固定し、行列にはそれから誘導されるノルムを使います。

補題 6.1（逆行列の摂動）✓

$A\in M_n(\mathbb{K})$ を正則、$E\in M_n(\mathbb{K})$ とし、$\|A^{-1}E\|<1$ とする。このとき $A+E$ は正則で

$$\|(A+E)^{-1}\|\le\frac{\|A^{-1}\|}{1-\|A^{-1}E\|},\qquad \|(A+E)^{-1}-A^{-1}\|\le\frac{\|A^{-1}\|\,\|A^{-1}E\|}{1-\|A^{-1}E\|}.$$

証明（補題 6.1）

$F=A^{-1}E$ とおくと $\|F\|<1$ です。$(I+F)\boldsymbol{x}=\boldsymbol{0}$ なら $\|\boldsymbol{x}\|=\|F\boldsymbol{x}\|\le\|F\|\|\boldsymbol{x}\|$ で、$\|F\|<1$ から $\boldsymbol{x}=\boldsymbol{0}$ です。よって $I+F$ の核は $\{\boldsymbol{0}\}$ で、次元定理（定理 8.3）［行列と連立一次方程式］ から階数 $n$、すなわち正則です。$\boldsymbol{y}=(I+F)^{-1}\boldsymbol{z}$ とおくと $\|\boldsymbol{z}\|=\|\boldsymbol{y}+F\boldsymbol{y}\|\ge(1-\|F\|)\|\boldsymbol{y}\|$ なので $\|(I+F)^{-1}\|\le1/(1-\|F\|)$ です。

$A+E=A(I+F)$ は正則行列の積なので正則で、$(A+E)^{-1}=(I+F)^{-1}A^{-1}$ から第 1 式が出ます。また

$$(A+E)^{-1}-A^{-1}=(I+F)^{-1}\bigl(I-(I+F)\bigr)A^{-1}=-(I+F)^{-1}FA^{-1}$$

のノルムをとると第 2 式です。

∎

$\|A^{-1}E\|\le\|A^{-1}\|\|E\|$ なので、$\|E\|<1/\|A^{-1}\|$ なら仮定は満たされます。Neumann 級数（定理 6.1）［有界作用素と共役作用素］ を使えば $(I+F)^{-1}=\sum_k(-F)^k$ という表示も得られますが、評価だけなら上の直接の議論で足ります。

定義 6.2（条件数）↗

正則な $A\in M_n(\mathbb{K})$ について $\kappa(A)=\|A\|\,\|A^{-1}\|$ を（そのノルムに関する）条件数という。$p$ ノルムのとき $\kappa_p(A)$ と書く。

$1=\|I\|=\|AA^{-1}\|\le\kappa(A)$ なので $\kappa(A)\ge1$ です。$\kappa(\alpha A)=\kappa(A)$（$\alpha\ne0$）で、条件数は行列の「大きさ」ではなく「歪み」を測ります。

定理 6.3（線形方程式の摂動定理）✓

$A\in M_n(\mathbb{K})$ を正則、$\boldsymbol{b}\ne\boldsymbol{0}$、$A\boldsymbol{x}=\boldsymbol{b}$ とする。$\Delta A,\Delta\boldsymbol{b}$ が $\|A^{-1}\|\|\Delta A\|<1$ を満たし、$(A+\Delta A)(\boldsymbol{x}+\Delta\boldsymbol{x})=\boldsymbol{b}+\Delta\boldsymbol{b}$ ならば

$$\frac{\|\Delta\boldsymbol{x}\|}{\|\boldsymbol{x}\|}\le\frac{\kappa(A)}{1-\kappa(A)\dfrac{\|\Delta A\|}{\|A\|}}\left(\frac{\|\Delta A\|}{\|A\|}+\frac{\|\Delta\boldsymbol{b}\|}{\|\boldsymbol{b}\|}\right).$$

とくに $\|\Delta A\|\le\varepsilon\|A\|$、$\|\Delta\boldsymbol{b}\|\le\varepsilon\|\boldsymbol{b}\|$、$\varepsilon\kappa(A)<1$ なら $\|\Delta\boldsymbol{x}\|/\|\boldsymbol{x}\|\le2\varepsilon\kappa(A)/(1-\varepsilon\kappa(A))$。

証明（定理 6.3）

$\|A^{-1}\Delta A\|\le\|A^{-1}\|\|\Delta A\|<1$ なので、補題 6.1 により $A+\Delta A$ は正則で $\|(A+\Delta A)^{-1}\|\le\|A^{-1}\|/(1-\|A^{-1}\|\|\Delta A\|)$ です。仮定の式から $A\boldsymbol{x}=\boldsymbol{b}$ を引くと $(A+\Delta A)\Delta\boldsymbol{x}=\Delta\boldsymbol{b}-\Delta A\,\boldsymbol{x}$、すなわち $\Delta\boldsymbol{x}=(A+\Delta A)^{-1}(\Delta\boldsymbol{b}-\Delta A\,\boldsymbol{x})$ で、

$$\|\Delta\boldsymbol{x}\|\le\frac{\|A^{-1}\|}{1-\|A^{-1}\|\|\Delta A\|}\bigl(\|\Delta\boldsymbol{b}\|+\|\Delta A\|\|\boldsymbol{x}\|\bigr)$$

です。$\boldsymbol{b}\ne\boldsymbol{0}$ より $\boldsymbol{x}\ne\boldsymbol{0}$ で、$\|\boldsymbol{b}\|\le\|A\|\|\boldsymbol{x}\|$ から $\|\Delta\boldsymbol{b}\|\le\|A\|\|\boldsymbol{x}\|\cdot\|\Delta\boldsymbol{b}\|/\|\boldsymbol{b}\|$ です。これを代入して $\|\boldsymbol{x}\|$ で割り、$\|A^{-1}\|\|\Delta A\|=\kappa(A)\|\Delta A\|/\|A\|$ と書けば主張です。後半は $\|\Delta A\|/\|A\|\le\varepsilon$、$\|\Delta\boldsymbol{b}\|/\|\boldsymbol{b}\|\le\varepsilon$ を代入したものです。

∎

$\Delta A=0$ の場合、この上界は等号で達成されます。$\|A\boldsymbol{x}\|=\|A\|\|\boldsymbol{x}\|$ となる $\boldsymbol{x}$ を選んで $\boldsymbol{b}=A\boldsymbol{x}$ とし、$\|A^{-1}\Delta\boldsymbol{b}\|=\|A^{-1}\|\|\Delta\boldsymbol{b}\|$ となる向きの $\Delta\boldsymbol{b}$ をとると、$\|\Delta\boldsymbol{x}\|/\|\boldsymbol{x}\|=\|A^{-1}\|\|\Delta\boldsymbol{b}\|\cdot\|A\|/\|\boldsymbol{b}\|=\kappa(A)\|\Delta\boldsymbol{b}\|/\|\boldsymbol{b}\|$ です。つまり $\kappa(A)$ は相対誤差の拡大率の「最悪の場合」そのものです。

条件数にはもう 1 つの意味があります。$\kappa(A)$ が大きいとは、$A$ のすぐ近くに特異行列があることです。

定理 6.4（特異行列までの距離）✓

$A\in M_n(\mathbb{K})$ を正則とし、$\mathbb{K}^n$ の任意のノルムとその誘導ノルムをとる。

$$\min\left\{\frac{\|\Delta A\|}{\|A\|}:\Delta A\in M_n(\mathbb{K}),\ A+\Delta A\text{ は特異}\right\}=\frac1{\kappa(A)}$$

であり、最小は階数 1 の $\Delta A$ で達成される。2 ノルムでは $\kappa_2(A)=\sigma_1/\sigma_n$ で、最小値は $\sigma_n/\sigma_1$ である。

証明の方針は 2 段です。下界は直前の補題から出ます。$A$ に加える摂動が小さければ正則のままだからです。達成の部分では、特異にするために必要な最小の摂動を実際に作ります。ここで使う線形汎関数 $\phi$ は、ベクトルから数を 1 つ取り出す線形な量で、選んだ $\boldsymbol{w}$ ではちょうどノルムの値 1 をとり、ほかのベクトルでは $\|\boldsymbol{v}\|$ を超えないものです（2 ノルムなら $\boldsymbol{w}^{*}\boldsymbol{v}$ がそれにあたります）。これを使うと「$\boldsymbol{w}$ を $A\boldsymbol{w}$ だけずらして 0 に送る」階数 1 の摂動が書けます。

証明（定理 6.4）

下界. $\|\Delta A\|<1/\|A^{-1}\|$ なら 補題 6.1（$\|A^{-1}\Delta A\|\le\|A^{-1}\|\|\Delta A\|<1$）により $A+\Delta A$ は正則です。対偶をとると、$A+\Delta A$ が特異なら $\|\Delta A\|\ge1/\|A^{-1}\|$、すなわち $\|\Delta A\|/\|A\|\ge1/\kappa(A)$ です。

達成. 誘導ノルムの定義の最大値をとる $\boldsymbol{z}$（$\|\boldsymbol{z}\|=1$、$\|A^{-1}\boldsymbol{z}\|=\|A^{-1}\|$）を選び、$\boldsymbol{w}=A^{-1}\boldsymbol{z}/\|A^{-1}\|$ とおくと $\|\boldsymbol{w}\|=1$、$A\boldsymbol{w}=\boldsymbol{z}/\|A^{-1}\|$ です。ノルムを実現する汎関数（系 3.4）［Banach 空間の基本定理］ をノルム空間 $(\mathbb{K}^n,\|\cdot\|)$ に適用し、線形汎関数 $\phi$ で $\phi(\boldsymbol{w})=1$、全 $\boldsymbol{v}$ で $|\phi(\boldsymbol{v})|\le\|\boldsymbol{v}\|$ となるものをとります。$\Delta A\,\boldsymbol{v}:=-\phi(\boldsymbol{v})\,A\boldsymbol{w}$ と定めると $\Delta A$ は階数 1 の行列で、$(A+\Delta A)\boldsymbol{w}=A\boldsymbol{w}-A\boldsymbol{w}=\boldsymbol{0}$ なので $A+\Delta A$ は特異です。また $\|\Delta A\,\boldsymbol{v}\|=|\phi(\boldsymbol{v})|\,\|A\boldsymbol{w}\|\le\|\boldsymbol{v}\|/\|A^{-1}\|$ で、$\boldsymbol{v}=\boldsymbol{w}$ で等号なので $\|\Delta A\|=1/\|A^{-1}\|$ です。

2 ノルム. 特異値分解（定理 4.1）［行列の分解と標準形］ $A=U\Sigma V^{*}$ で $A$ は正則なので階数 $n$、$\sigma_n>0$ で、$A^{-1}=V\Sigma^{-1}U^{*}$ です。命題 4.4 の 1 から $\|A^{-1}\|_2=\|\Sigma^{-1}\|_2$ で、$\|\Sigma^{-1}\boldsymbol{x}\|_2^2=\sum_i|x_i|^2/\sigma_i^2\le\|\boldsymbol{x}\|_2^2/\sigma_n^2$（等号は $\boldsymbol{x}=\boldsymbol{e}_n$）なので $\|A^{-1}\|_2=1/\sigma_n$ です。$\|A\|_2=\sigma_1$（命題 4.2）と合わせて $\kappa_2(A)=\sigma_1/\sigma_n$ です。

∎

2 ノルムの場合、最小の摂動は $\Delta A=-\sigma_n\boldsymbol{u}_n\boldsymbol{v}_n^{*}$ で、これは Eckart–Young の定理（命題 4.3）［行列の分解と標準形］ の $k=n-1$ の場合（階数 $n-1$ 以下の行列への距離は $\sigma_n$）と同じことを言っています。「$\kappa(A)\approx10^{16}$ の行列は、倍精度の丸め 1 回分の相対摂動で特異になりうる」と読めるので、そのような行列の解に意味のある桁は期待できません。

7. 後退誤差

7.1. ノルムで測る後退誤差

定義 7.1（ノルムに関する後退誤差）↗

正則な $A\in M_n(\mathbb{K})$、$\boldsymbol{b}\in\mathbb{K}^n$ と近似解 $\boldsymbol{y}$ について

$$\eta(\boldsymbol{y})=\min\bigl\{\varepsilon\ge0:(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}+\Delta\boldsymbol{b},\ \|\Delta A\|\le\varepsilon\|A\|,\ \|\Delta\boldsymbol{b}\|\le\varepsilon\|\boldsymbol{b}\|\bigr\}$$

を $\boldsymbol{y}$ の（ノルムに関する）後退誤差という。残差を $\boldsymbol{r}=\boldsymbol{b}-A\boldsymbol{y}$ と書く。

定理 7.2（Rigal–Gaches の公式）✓

$\boldsymbol{y}\ne\boldsymbol{0}$ ならば、上の最小値は存在して

$$\eta(\boldsymbol{y})=\frac{\|\boldsymbol{r}\|}{\|A\|\,\|\boldsymbol{y}\|+\|\boldsymbol{b}\|}.$$

証明の方針は次のとおりです。残差 $\boldsymbol{r}$ は「$A$ の側の摂動」と「$\boldsymbol{b}$ の側の摂動」で打ち消すしかありません。そこで $\boldsymbol{r}$ を割合 $\alpha$ と $1-\alpha$ に分けて両者に負担させます。$\alpha$ は、$A$ と $\boldsymbol{b}$ それぞれの相対的な摂動の大きさがちょうど等しくなるように選んであります。

証明（定理 7.2）

右辺を $\eta_*$ とおきます（$A$ は正則なので $A\ne0$、分母は正）。

下界. $(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}+\Delta\boldsymbol{b}$ を書き直すと $\boldsymbol{r}=\Delta A\,\boldsymbol{y}-\Delta\boldsymbol{b}$ です。$\|\Delta A\|\le\varepsilon\|A\|$、$\|\Delta\boldsymbol{b}\|\le\varepsilon\|\boldsymbol{b}\|$ なら $\|\boldsymbol{r}\|\le\varepsilon(\|A\|\|\boldsymbol{y}\|+\|\boldsymbol{b}\|)$、すなわち $\varepsilon\ge\eta_*$ です。

達成. ノルムを実現する汎関数（系 3.4）［Banach 空間の基本定理］ で、線形汎関数 $\phi$ を $\phi(\boldsymbol{y})=\|\boldsymbol{y}\|$、$|\phi(\boldsymbol{v})|\le\|\boldsymbol{v}\|$ となるようにとります。$\alpha=\|A\|\|\boldsymbol{y}\|/(\|A\|\|\boldsymbol{y}\|+\|\boldsymbol{b}\|)\in(0,1]$ とし

$$\Delta A\,\boldsymbol{v}=\frac{\alpha\,\phi(\boldsymbol{v})}{\|\boldsymbol{y}\|}\,\boldsymbol{r},\qquad\Delta\boldsymbol{b}=-(1-\alpha)\,\boldsymbol{r}$$

と定めます。$\Delta A\,\boldsymbol{y}-\Delta\boldsymbol{b}=\alpha\boldsymbol{r}+(1-\alpha)\boldsymbol{r}=\boldsymbol{r}$ なので $(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}+\Delta\boldsymbol{b}$ です。$\|\Delta A\boldsymbol{v}\|\le\alpha\|\boldsymbol{r}\|\|\boldsymbol{v}\|/\|\boldsymbol{y}\|$ から $\|\Delta A\|\le\alpha\|\boldsymbol{r}\|/\|\boldsymbol{y}\|=\eta_*\|A\|$、また $\|\Delta\boldsymbol{b}\|=(1-\alpha)\|\boldsymbol{r}\|=\eta_*\|\boldsymbol{b}\|$ です。よって $\varepsilon=\eta_*$ は許される値で、下界と合わせて最小値は $\eta_*$ です。

∎

2 ノルムでは $\phi(\boldsymbol{v})=\boldsymbol{y}^{*}\boldsymbol{v}/\|\boldsymbol{y}\|_2$ とでき、$\Delta A$ は $\boldsymbol{r}\boldsymbol{y}^{*}$ の定数倍という具体的な階数 1 の行列になります。後退誤差は残差から計算できるのが要点です。前進誤差は真の解を知らないと計算できませんが、後退誤差は計算した $\boldsymbol{y}$ だけで評価でき、それに条件数を掛ければ前進誤差の上界になります。

系 7.3（前進誤差 ≤ 条件数 × 後退誤差）✓

$A$ を正則、$\boldsymbol{b}\ne\boldsymbol{0}$、$A\boldsymbol{x}=\boldsymbol{b}$、$\boldsymbol{y}\ne\boldsymbol{0}$ とし、$\eta=\eta(\boldsymbol{y})$ が $\eta\,\kappa(A)<1$ を満たすとする。このとき

$$\frac{\|\boldsymbol{y}-\boldsymbol{x}\|}{\|\boldsymbol{x}\|}\le\frac{2\,\kappa(A)\,\eta}{1-\kappa(A)\,\eta}.$$

証明（系 7.3）

定理 7.2 により、$\|\Delta A\|\le\eta\|A\|$、$\|\Delta\boldsymbol{b}\|\le\eta\|\boldsymbol{b}\|$ で $(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}+\Delta\boldsymbol{b}$ となる $\Delta A,\Delta\boldsymbol{b}$ があります。$\|A^{-1}\|\|\Delta A\|\le\eta\kappa(A)<1$ なので、定理 6.3 の後半を $\varepsilon=\eta$、$\Delta\boldsymbol{x}=\boldsymbol{y}-\boldsymbol{x}$ で使えば主張です。

∎

例 7.4（Hilbert 行列：後退誤差は小さく、前進誤差は κ に比例する）

Hilbert 行列 $H_n=(1/(i+j-1))_{i,j}$ を浮動小数に丸め、右辺を $\boldsymbol{b}=H_n(1,\ldots,1)^{\mathsf{T}}$（浮動小数の積）として numpy.linalg.solve（部分ピボット選択つき LU）で解きます。丸めた $(H_n,\boldsymbol{b})$ の厳密解は mpmath の 50 桁で求めて参照解とし、2 ノルムの前進誤差と Rigal–Gaches の後退誤差 $\eta$ を並べます。

# Python 3.12.10 / NumPy 2.5.2 / SciPy 1.18.1 / mpmath 1.3.0
import numpy as np
import mpmath as mp
from scipy.linalg import hilbert, invhilbert

mp.mp.dps = 50
n2 = lambda M: np.linalg.norm(M, 2)
print(" n   kappa2     forward    backward   fwd/(k*bwd)")
for n in range(4, 14):
    H = hilbert(n)                    # 浮動小数に丸めた H_n
    b = H @ np.ones(n)                # 右辺（浮動小数）
    x = np.linalg.solve(H, b)
    # 丸めた (H, b) の厳密解を 50 桁で求める
    Hm, bm = mp.matrix(H.tolist()), mp.matrix(b.tolist())
    xr = mp.lu_solve(Hm, bm)
    xr = np.array([float(v) for v in xr])
    r = bm - Hm * mp.matrix(x.tolist())   # 残差も 50 桁
    r = np.array([float(v) for v in r])
    Hinv = np.array(mp.inverse(Hm).tolist(), dtype=float)
    kap = n2(H) * n2(Hinv)            # 丸めた H の kappa_2
    fwd = n2(x - xr) / n2(xr)
    bwd = n2(r) / (n2(H) * n2(x) + n2(b))   # Rigal-Gaches
    print(f"{n:2d}  {kap:.2e}  {fwd:.2e}  {bwd:.2e}  "
          f"{fwd/(kap*bwd):.2e}")
kex = [n2(hilbert(n)) * n2(invhilbert(n, exact=True).astype(float))
       for n in (4, 8, 12)]
print("exact H_n, n=4,8,12:", " ".join(f"{k:.2e}" for k in kex))

 n   kappa2     forward    backward   fwd/(k*bwd)
 4  1.55e+04  7.34e-14  8.67e-18  5.46e-01
 5  4.77e+05  1.84e-13  2.52e-17  1.53e-02
 6  1.50e+07  6.19e-11  5.54e-17  7.47e-02
 7  4.75e+08  2.02e-09  4.09e-17  1.04e-01
 8  1.53e+10  2.12e-09  7.27e-17  1.91e-03
 9  4.93e+11  9.17e-07  1.73e-17  1.07e-01
10  1.60e+13  5.76e-05  6.86e-17  5.24e-02
11  5.22e+14  4.40e-04  2.50e-17  3.37e-02
12  1.68e+16  7.76e-03  5.00e-17  9.23e-03
13  2.17e+18  1.28e+01  1.07e-17  5.54e-01
exact H_n, n=4,8,12: 1.55e+04 1.53e+10 1.71e+16

後退誤差はどの $n$ でも単位丸め $u\approx1.1\times10^{-16}$ 以下で、算法は後退安定に振る舞っています。前進誤差は $\kappa_2$ とともにおよそ $e^{3.5n}$ の勢いで増え、$n=13$ では 1 を超えて有効な桁が残りません。最後の列は 系 7.3 の比で、$\kappa_2\eta<1$ の $n\le12$ では上界 $2/(1-\kappa_2\eta)$ 以下です。$n=13$ では $\kappa_2\eta\approx23$ で系の仮定が崩れ、前進誤差について何も保証されません。

検算. (a) 既知値: 厳密な逆行列 invhilbert(exact=True)（整数行列）から計算した $\kappa_2(H_n)$ は、丸めた行列の値と $n=4,8$ で表示桁まで一致し、$n=12$ では 2% ずれます。丸めによる $H_n$ の相対摂動 $u$ に $\kappa_2\approx10^{16}$ を掛けると $O(1)$ になるので、このずれ自体が 定理 6.4 の言う「特異に近い」状況を示しています。(b) 別精度: 参照解・残差・逆行列は mpmath の 50 桁で計算しました。(c) 次数: 前進誤差 / ($\kappa_2\eta$) が $n$ によらず $10^{-3}$〜$1$ の範囲に収まり、前進誤差が $\kappa_2$ に比例して増えることを示しています。

7.2. 成分ごとの後退誤差と Skeel の条件数

ノルムの後退誤差は $\Delta A$ の成分の大きさの釣り合いを無視します。$A$ の小さい成分（たとえば 0）に大きな摂動を許すのは不自然なので、成分ごとに測る物差しも用意します。

定義 7.5（成分ごとの後退誤差）↗

$E\in M_n(\mathbb{R})$、$\boldsymbol{f}\in\mathbb{R}^n$ を成分が非負の「許容の形」とする。近似解 $\boldsymbol{y}$ について

$$\omega_{E,\boldsymbol{f}}(\boldsymbol{y})=\inf\bigl\{\varepsilon\ge0:(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}+\Delta\boldsymbol{b},\ |\Delta A|\le\varepsilon E,\ |\Delta\boldsymbol{b}|\le\varepsilon\boldsymbol{f}\bigr\}$$

（条件を満たす $\varepsilon$ が無ければ $+\infty$）を成分ごとの後退誤差という。$E=|A|$、$\boldsymbol{f}=|\boldsymbol{b}|$ が標準的な選び方である。

定理 7.6（Oettli–Prager の公式）✓

$\boldsymbol{r}=\boldsymbol{b}-A\boldsymbol{y}$、$\boldsymbol{g}=E|\boldsymbol{y}|+\boldsymbol{f}$ とする。ある $i$ で $g_i=0$ かつ $r_i\ne0$ なら $\omega_{E,\boldsymbol{f}}(\boldsymbol{y})=+\infty$。そうでなければ下限は最小値で

$$\omega_{E,\boldsymbol{f}}(\boldsymbol{y})=\max_i\frac{|r_i|}{g_i}\qquad(0/0=0\text{ と約束する}).$$

式の読み方は次のとおりです。$|r_i|/g_i$ は $i$ 番目の方程式が許された幅（$g_i$）に対して残差をどれだけ使っているかの割合で、全方程式のうち最も厳しいものが後退誤差を決めます。$g_i=0$ かつ $r_i=0$ の方程式は動かす余地がなく、同時に動かす必要もないので、制約なしとして $0/0=0$ と約束します。

証明（定理 7.6）

下界. 条件を満たす $\Delta A,\Delta\boldsymbol{b}$ があれば $\boldsymbol{r}=\Delta A\,\boldsymbol{y}-\Delta\boldsymbol{b}$ で、成分ごとに $|r_i|\le\sum_j|\Delta a_{ij}||y_j|+|\Delta b_i|\le\varepsilon g_i$ です。$g_i=0$、$r_i\ne0$ ならこれは成り立たないので $+\infty$、そうでなければ $\varepsilon\ge|r_i|/g_i$（全 $i$）です。

達成. $\theta_i=r_i/g_i$（$g_i=0$ なら $r_i=0$ なので $\theta_i=0$）、$s_j=\overline{y_j}/|y_j|$（$y_j=0$ なら $s_j=0$）とおき、$\Delta a_{ij}=\theta_ie_{ij}s_j$、$\Delta b_i=-\theta_if_i$ と定めます。$s_jy_j=|y_j|$ なので

$$(\Delta A\,\boldsymbol{y}-\Delta\boldsymbol{b})_i=\theta_i\Bigl(\sum_je_{ij}|y_j|+f_i\Bigr)=\theta_ig_i=r_i$$

で、$(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}+\Delta\boldsymbol{b}$ です。$|\Delta a_{ij}|\le|\theta_i|e_{ij}$、$|\Delta b_i|=|\theta_i|f_i$ なので $\varepsilon=\max_i|\theta_i|$ が許されます。

∎

成分ごとの後退誤差が $u$ の程度なら、計算した解は「各成分を相対 $u$ 程度動かしたデータ」の厳密解で、データ自体が測定や丸めで相対 $u$ の誤差を含むなら、それ以上の精度は求めようがありません。これに対応する条件数が Skeel の条件数です。

定義 7.7（Skeel の条件数）↗

正則な $A$ と $\boldsymbol{x}\ne\boldsymbol{0}$ について

$$\operatorname{cond}(A,\boldsymbol{x})=\frac{\bigl\||A^{-1}||A||\boldsymbol{x}|\bigr\|_\infty}{\|\boldsymbol{x}\|_\infty},\qquad\operatorname{cond}(A)=\bigl\||A^{-1}||A|\bigr\|_\infty$$

を Skeel の条件数という。

命題 7.8（成分ごとの摂動の評価）✓

$A$ を正則、$A\boldsymbol{x}=\boldsymbol{b}$、$\boldsymbol{x}\ne\boldsymbol{0}$ とする。

1. $(A+\Delta A)(\boldsymbol{x}+\Delta\boldsymbol{x})=\boldsymbol{b}+\Delta\boldsymbol{b}$、$|\Delta A|\le\varepsilon|A|$、$|\Delta\boldsymbol{b}|\le\varepsilon|\boldsymbol{b}|$、$\varepsilon\operatorname{cond}(A)<1$ ならば $\|\Delta\boldsymbol{x}\|_\infty/\|\boldsymbol{x}\|_\infty\le2\varepsilon\operatorname{cond}(A,\boldsymbol{x})/(1-\varepsilon\operatorname{cond}(A))$。
2. 正則な対角行列 $D$ について $\operatorname{cond}(DA)=\operatorname{cond}(A)$、$\operatorname{cond}(DA,\boldsymbol{x})=\operatorname{cond}(A,\boldsymbol{x})$。
3. $\operatorname{cond}(A,\boldsymbol{x})\le\operatorname{cond}(A)\le\kappa_\infty(A)$。

証明（命題 7.8）

成分が非負のベクトル $\boldsymbol{0}\le\boldsymbol{p}\le\boldsymbol{q}$ では $\|\boldsymbol{p}\|_\infty\le\|\boldsymbol{q}\|_\infty$、成分が非負の行列 $M$ では $\|M\boldsymbol{p}\|_\infty\le\|M\|_\infty\|\boldsymbol{p}\|_\infty$ であることを使います。また $\|\,|M|\,\|_\infty=\|M\|_\infty$ です（命題 4.2 の 2 の行和の式は成分の絶対値しか見ない）。

(1) 仮定の式から $A\boldsymbol{x}=\boldsymbol{b}$ を引くと $A\Delta\boldsymbol{x}=\Delta\boldsymbol{b}-\Delta A(\boldsymbol{x}+\Delta\boldsymbol{x})$ です。$A^{-1}$ を掛けて絶対値をとり、$|\boldsymbol{b}|=|A\boldsymbol{x}|\le|A||\boldsymbol{x}|$ を使うと

$$|\Delta\boldsymbol{x}|\le\varepsilon|A^{-1}|\bigl(|\boldsymbol{b}|+|A||\boldsymbol{x}|+|A||\Delta\boldsymbol{x}|\bigr)\le2\varepsilon|A^{-1}||A||\boldsymbol{x}|+\varepsilon|A^{-1}||A||\Delta\boldsymbol{x}|$$

です。∞ ノルムをとると $\|\Delta\boldsymbol{x}\|_\infty\le2\varepsilon\operatorname{cond}(A,\boldsymbol{x})\|\boldsymbol{x}\|_\infty+\varepsilon\operatorname{cond}(A)\|\Delta\boldsymbol{x}\|_\infty$ で、移項して割れば主張です。

(2) $|(DA)^{-1}||DA|=|A^{-1}D^{-1}||DA|=|A^{-1}||D^{-1}||D||A|=|A^{-1}||A|$ です（対角行列を掛けることは行または列を定数倍することなので、絶対値と交換する）。

(3) 左の不等式は $\||A^{-1}||A||\boldsymbol{x}|\|_\infty\le\||A^{-1}||A|\|_\infty\|\boldsymbol{x}\|_\infty$、右は $\||A^{-1}||A|\|_\infty\le\||A^{-1}|\|_\infty\||A|\|_\infty=\|A^{-1}\|_\infty\|A\|_\infty$ です。

∎

例 7.9（行のスケーリングで κ∞ は変わり、Skeel の条件数は変わらない）

$B=\begin{pmatrix}2&1\\1&1\end{pmatrix}$、$B^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$ とします。$\kappa_\infty(B)=3\cdot3=9$、$|B^{-1}||B|=\begin{pmatrix}3&2\\4&3\end{pmatrix}$ なので $\operatorname{cond}(B)=7$ です。第 2 行を $t>0$ 倍した $A_t=\operatorname{diag}(1,t)B$ では $A_t^{-1}=\begin{pmatrix}1&-1/t\\-1&2/t\end{pmatrix}$ で、$0<t\le1$ のとき $\|A_t\|_\infty=3$、$\|A_t^{-1}\|_\infty=1+2/t$、$\kappa_\infty(A_t)=3+6/t$ です。$t=10^{-8}$ なら $\kappa_\infty\approx6\times10^8$ ですが、命題 7.8 の 2 により $\operatorname{cond}(A_t)=7$ のままです。方程式の両辺に同じ数を掛けても解の感度は変わらないので、成分ごとに測る限りこの「悪条件」は見かけのものです。

8. 固有値の感度とモデル行列の条件数

8.1. エルミート行列の固有値は条件数 1

系 8.1（エルミート行列の固有値の摂動）✓

$A,E\in M_n(\mathbb{C})$ をエルミート行列とし、固有値を大きい順に $\lambda_1(\cdot)\ge\cdots\ge\lambda_n(\cdot)$ と並べる。このとき全 $i$ で

$$|\lambda_i(A+E)-\lambda_i(A)|\le\|E\|_2.$$

証明（系 8.1）

Weyl の固有値不等式（定理 3.2）［行列の固有値評価と不等式］ の 3 を $B=E$ として使います。そこでの $\|E\|$ はユークリッドノルムから誘導される作用素ノルム、すなわち $\|E\|_2$ です。

∎

後退安定な算法で固有値を計算し、結果が $A+E$（$\|E\|_2\le cnu\|A\|_2$）の厳密な固有値だと分かれば、絶対誤差は $cnu\|A\|_2$ 以下です。固有値の絶対誤差が摂動のノルムを超えないので、エルミート行列の固有値問題は（絶対誤差について）条件数 1 です。ただし $\|A\|_2$ に比べて小さい固有値の相対誤差は大きくなりえます。

注意 8.2

非正規行列ではこれが成り立ちません。対角化可能な $A=V\Lambda V^{-1}$ では Bauer–Fike の定理（定理 6.2）［行列計算の認証と最適化の証明書］ により固有値の動きは $\kappa_2(V)\|E\|_2$ 以下ですが、$\kappa_2(V)$ は大きくなりえ、対角化できない行列ではさらに悪くなります。たとえば $J_\varepsilon=\begin{pmatrix}0&1\\\varepsilon&0\end{pmatrix}$ の固有値は $\pm\sqrt\varepsilon$ で、$\varepsilon=10^{-16}$ の摂動が固有値を $10^{-8}$ 動かします。$n$ 次の Jordan 細胞の左下に $\varepsilon$ を置くと、固有値は $\varepsilon^{1/n}$ の大きさまで動きます。この現象は固有値計算と GMRES の章で再び現れます。

8.2. 三重対角 Toeplitz 行列と離散 Laplace 行列

偏微分方程式の離散化で最も基本的な行列は、固有値と固有ベクトルが閉じた形で書けます。後の章（定常反復法、共役勾配法）の収束率の計算はこの補題に基づきます。

補題 8.3（三重対角 Toeplitz 行列の固有値）✓

$n\ge1$、$\alpha,\beta\in\mathbb{R}$ とし、$T\in M_n(\mathbb{R})$ を対角成分が $\alpha$、すぐ上とすぐ下の副対角成分が $\beta$、他が 0 の行列とする。$\theta_k=k\pi/(n+1)$（$k=1,\ldots,n$）とおくと、

$$T\boldsymbol{v}_k=(\alpha+2\beta\cos\theta_k)\boldsymbol{v}_k,\qquad\boldsymbol{v}_k=\bigl(\sin(j\theta_k)\bigr)_{j=1}^n\ne\boldsymbol{0}$$

であり、$\beta\ne0$ のとき $\alpha+2\beta\cos\theta_k$（$k=1,\ldots,n$）は相異なり、$T$ の固有値のすべてである。

証明（補題 8.3）

$s_j=\sin(j\theta_k)$ とおくと $s_0=0$、$s_{n+1}=\sin(k\pi)=0$ です。この約束のもとで $(T\boldsymbol{v}_k)_j=\beta s_{j-1}+\alpha s_j+\beta s_{j+1}$ が $j=1$ と $j=n$ でも成り立ちます。加法定理から $\sin((j-1)\theta)+\sin((j+1)\theta)=2\sin(j\theta)\cos\theta$ なので $(T\boldsymbol{v}_k)_j=(\alpha+2\beta\cos\theta_k)s_j$ です。$0<\theta_k<\pi$ から $s_1=\sin\theta_k\ne0$ で、$\boldsymbol{v}_k\ne\boldsymbol{0}$ です。$\cos$ は $(0,\pi)$ で狭義単調減少なので $\cos\theta_1>\cdots>\cos\theta_n$ で、$\beta\ne0$ なら $n$ 個の固有値は相異なります。$n$ 次の行列の固有値は重複度を込めて $n$ 個なので、これで全部です。

∎

系 8.4（離散 Laplace 行列の条件数）✓

$n\ge2$、$h=1/(n+1)$ とし、$L_h=h^{-2}T$（$T$ は $\alpha=2$、$\beta=-1$ の三重対角 Toeplitz 行列）とする。$L_h$ の固有値は $\lambda_k=4h^{-2}\sin^2(k\pi h/2)$（$k=1,\ldots,n$）で、

$$\kappa_2(L_h)=\cot^2\frac{\pi h}{2},\qquad\frac4{\pi^2h^2}-1\le\kappa_2(L_h)\le\frac4{\pi^2h^2}.$$

証明（系 8.4）

補題 8.3 から固有値は $h^{-2}(2-2\cos(k\pi h))=4h^{-2}\sin^2(k\pi h/2)$ で、$0<k\pi h/2<\pi/2$ では $\sin$ が正で増加なので $0<\lambda_1<\cdots<\lambda_n$ です。$L_h$ は実対称なので スペクトル定理（定理 4.2）［スペクトル定理］ で $L_h=U\Lambda U^{*}$（$U$ はユニタリ）と書け、$L_h^{-1}=U\Lambda^{-1}U^{*}$ です。命題 4.4 の 1 により $\|L_h\|_2=\|\Lambda\|_2$、$\|L_h^{-1}\|_2=\|\Lambda^{-1}\|_2$ で、対角行列では $\|\Lambda\boldsymbol{x}\|_2^2=\sum_k\lambda_k^2|x_k|^2$ から $\|\Lambda\|_2=\lambda_n$、$\|\Lambda^{-1}\|_2=1/\lambda_1$ です。よって

$$\kappa_2(L_h)=\frac{\lambda_n}{\lambda_1}=\frac{\sin^2(n\pi h/2)}{\sin^2(\pi h/2)}=\frac{\cos^2(\pi h/2)}{\sin^2(\pi h/2)}$$

です（$n\pi h/2=\pi/2-\pi h/2$）。$x=\pi h/2\in(0,\pi/2)$ について、平均値の定理（定理 3.3）［平均値の定理とテイラーの定理］ を $[0,x]$ 上の $\tan$ と $\sin$ に使うと、ある $c,c'\in(0,x)$ で $\tan x=x/\cos^2c\ge x$、$\sin x=x\cos c'\le x$ です。前者から $\cot^2x\le1/x^2$、後者から $\cot^2x=1/\sin^2x-1\ge1/x^2-1$ で、$1/x^2=4/(\pi^2h^2)$ です。

∎

格子を細かくすると条件数は $h^{-2}$ で増えます。2 次元・3 次元の離散 Laplace 行列も同じ $h^{-2}$ の増え方をし、これが反復法の反復回数の増え方（定常反復法で $h^{-2}$、共役勾配法で $h^{-1}$）の源です。

例 8.5（離散 Laplace 行列の条件数を数値で確かめる）

$L_h$ の 2 ノルムの条件数を numpy.linalg.cond（特異値分解による）で計算し、閉じた形 $\cot^2(\pi h/2)$（mpmath の 30 桁）と $4/(\pi h)^2$ を並べます。

# Python 3.12.10 / NumPy 2.5.2 / SciPy 1.18.1 / mpmath 1.3.0
import numpy as np
import mpmath as mp

mp.mp.dps = 30
print("   n   cond (SVD)   cot^2(pi h/2)  4/(pi h)^2   rel.diff")
for n in (10, 20, 40, 80, 160, 320):
    h = 1.0 / (n + 1)
    L = (2 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1)) / h**2
    k_num = np.linalg.cond(L, 2)
    k_cf = mp.cot(mp.pi * h / 2) ** 2     # 閉じた形（30 桁）
    k_as = 4 / (np.pi * h) ** 2
    rel = abs(k_num - float(k_cf)) / float(k_cf)
    print(f"{n:4d}  {k_num:.6e}  {float(k_cf):.6e}  {k_as:.6e}"
          f"  {rel:.1e}")
# 固有値そのものも閉じた形と照合（n = 20）
n = 20; h = 1.0 / (n + 1)
L = (2 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1)) / h**2
lam = np.linalg.eigvalsh(L)
k = np.arange(1, n + 1)
cf = 4 * np.sin(k * np.pi * h / 2) ** 2 / h**2
print("max |lam - closed| / lam_max =",
      f"{np.max(np.abs(lam - cf)) / cf[-1]:.1e}")

   n   cond (SVD)   cot^2(pi h/2)  4/(pi h)^2   rel.diff
  10  4.837415e+01  4.837415e+01  4.903945e+01  1.0e-15
  20  1.780643e+02  1.780643e+02  1.787306e+02  1.1e-15
  40  6.806171e+02  6.806171e+02  6.812836e+02  3.4e-14
  80  2.658407e+03  2.658407e+03  2.659073e+03  1.4e-13
 160  1.050472e+04  1.050472e+04  1.050539e+04  1.7e-13
 320  4.176028e+04  4.176028e+04  4.176094e+04  2.7e-13
max |lam - closed| / lam_max = 3.9e-16

検算. (a) 既知値: 特異値分解による条件数は閉じた形と相対 $10^{-13}$ 以下で一致し、$n=20$ の固有値も閉じた形と $\lambda_{\max}$ の相対 $4\times10^{-16}$ で一致します。(b) 別精度: 閉じた形の値は mpmath の 30 桁で計算しました。(c) 次数: $n$ を 2 倍にするごとに条件数はほぼ 4 倍になり（$h^{-2}$）、$4/(\pi h)^2$ との差は $n=10$ の $0.6653$ から $2/3\approx0.6667$ に近づき、ほとんど変わりません。これは $\cot^2x=x^{-2}-2/3+O(x^2)$ という展開と合い、系 8.4 の幅 1 の評価の内側にあります。「rel.diff」が $n$ とともに増えるのは、特異値分解で求めた最小特異値の相対誤差が、系 8.1 と同じ理屈で最大 $\kappa_2u$ 程度まで大きくなりうるためです。

9. 演習

演習 9.1易

$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ について $\kappa_1(A)$、$\kappa_\infty(A)$、$\kappa_2(A)$ を求めよ。また、2 ノルムで測って $A$ に最も近い特異行列までの距離を求めよ。

解答

$\det A=-2$、$A^{-1}=\begin{pmatrix}-2&1\\3/2&-1/2\end{pmatrix}$ です。命題 4.2 から $\|A\|_1=6$（第 2 列）、$\|A^{-1}\|_1=7/2$（第 1 列）で $\kappa_1=21$、$\|A\|_\infty=7$、$\|A^{-1}\|_\infty=3$ で $\kappa_\infty=21$ です。$A^{\mathsf{T}}A=\begin{pmatrix}10&14\\14&20\end{pmatrix}$ の固有値は $15\pm\sqrt{221}$ なので $\sigma_1=\sqrt{15+\sqrt{221}}\approx5.465$、$\sigma_1\sigma_2=|\det A|=2$ から $\sigma_2=2/\sigma_1\approx0.366$ です。$\kappa_2=\sigma_1/\sigma_2=\sigma_1^2/2=(15+\sqrt{221})/2\approx14.93$。定理 6.4 により最も近い特異行列までの 2 ノルムの距離は $\sigma_2\approx0.366$ です。

演習 9.2標準

右辺 $\boldsymbol{b}$ は正確で、$A$ だけに摂動を許す後退誤差 $\eta_A(\boldsymbol{y})=\min\{\varepsilon:(A+\Delta A)\boldsymbol{y}=\boldsymbol{b},\ \|\Delta A\|_2\le\varepsilon\|A\|_2\}$ が、$\boldsymbol{y}\ne\boldsymbol{0}$ のとき $\|\boldsymbol{r}\|_2/(\|A\|_2\|\boldsymbol{y}\|_2)$ に等しいことを示し、最小を達成する $\Delta A$ を具体的に書け。

解答

下界: $(A+\Delta A)\boldsymbol{y}=\boldsymbol{b}$ なら $\boldsymbol{r}=\Delta A\,\boldsymbol{y}$ で $\|\boldsymbol{r}\|_2\le\|\Delta A\|_2\|\boldsymbol{y}\|_2\le\varepsilon\|A\|_2\|\boldsymbol{y}\|_2$。達成: $\Delta A=\boldsymbol{r}\boldsymbol{y}^{*}/\|\boldsymbol{y}\|_2^2$ とおくと $\Delta A\,\boldsymbol{y}=\boldsymbol{r}$ で、Cauchy–Schwarz の不等式から $\|\Delta A\boldsymbol{v}\|_2=|\boldsymbol{y}^{*}\boldsymbol{v}|\|\boldsymbol{r}\|_2/\|\boldsymbol{y}\|_2^2\le\|\boldsymbol{r}\|_2\|\boldsymbol{v}\|_2/\|\boldsymbol{y}\|_2$（等号は $\boldsymbol{v}=\boldsymbol{y}$）、よって $\|\Delta A\|_2=\|\boldsymbol{r}\|_2/\|\boldsymbol{y}\|_2$ です。定理 7.2 の証明で $\alpha=1$ とした場合にあたります。

演習 9.3標準

(1) $\rho(A+B)\le\rho(A)+\rho(B)$ が成り立たない $2\times2$ 行列の例を挙げ、$\rho$ が $M_n(\mathbb{C})$ 上のノルムでないことを確かめよ。(2) $A$ が正規行列なら $\|A\|_2=\rho(A)$ であることを示せ。

解答

(1) $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$、$B=\begin{pmatrix}0&0\\1&0\end{pmatrix}$ では $\rho(A)=\rho(B)=0$ ですが、$A+B$ の固有値は $\pm1$ で $\rho(A+B)=1$ です。また $A\ne0$ で $\rho(A)=0$ なので、ノルムの公理 (i) も破れます。

(2) 正規行列のスペクトル定理（定理 8.1）［スペクトル定理］ により $A=UDU^{*}$（$U$ はユニタリ、$D$ は固有値を並べた対角行列）です。命題 4.4 の 1 から $\|A\|_2=\|D\|_2$ で、$\|D\boldsymbol{x}\|_2^2=\sum_k|d_k|^2|x_k|^2\le(\max_k|d_k|)^2\|\boldsymbol{x}\|_2^2$、等号は最大の $|d_k|$ の位置の $\boldsymbol{e}_k$ で成り立つので $\|D\|_2=\max_k|d_k|=\rho(A)$ です。非正規の (1) の $A$ では $\|A\|_2=1>0=\rho(A)$ で、定理 5.2 の 1 の不等号は真に狭くなりえます。

参考文献

• N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002 — Ch. 6（ノルム）、Ch. 7（線形方程式の摂動論、Rigal–Gaches・Oettli–Prager・Skeel の条件数）。
• G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013 — Ch. 2（行列のノルムと線形方程式の感度）。
• L. N. Trefethen and D. Bau III, Numerical Linear Algebra, SIAM, 1997 — Lectures 3, 12–15（ノルム、条件数、安定性）。
• R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, 2013 — Ch. 5（ベクトルと行列のノルム、スペクトル半径）。
• J. L. Rigal and J. Gaches, “On the compatibility of a given solution with the data of a linear system”, J. ACM 14 (1967), 543–548.
• W. Oettli and W. Prager, “Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides”, Numer. Math. 6 (1964), 405–409.