数値解析 第10回 (6) 実行例、応用例、注意など

実行例

 ピボット選択ありで、ランダムな 4 元連立一次方程式を解きます。
拡大係数行列 :
  -3.5145622  -4.6372624   9.8028950   7.7799316   2.5537401
  -5.4942102  -0.8134165  -8.9400594  -0.6695192   9.4748287
  -4.0818981  -1.5462027  -6.9707814  -7.2853502  -7.4494552
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107

----- Step 1 -----

1 行目と 2 行目を交換 ( ピボット選択 )
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107
  -5.4942102  -0.8134165  -8.9400594  -0.6695192   9.4748287
  -4.0818981  -1.5462027  -6.9707814  -7.2853502  -7.4494552
  -3.5145622  -4.6372624   9.8028950   7.7799316   2.5537401

1 行目を用いた掃き出し
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107
   0.0000000  -4.4702096  -6.5692798   8.0916300  15.3168950
   0.0000000  -4.2630003  -5.2094216  -0.7762948  -3.1091191
   0.0000000  -6.9764569  11.3194464  13.3843045   6.2908205

2 行目と 4 行目を交換 ( ピボット選択 )
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107
   0.0000000  -6.9764569  11.3194464  13.3843045   6.2908205
   0.0000000  -4.2630003  -5.2094216  -0.7762948  -3.1091191
   0.0000000  -4.4702096  -6.5692798   8.0916300  15.3168950

2 行目を用いた掃き出し
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107
   0.0000000  -6.9764569  11.3194464  13.3843045   6.2908205
   0.0000000   0.0000000 -12.1262282  -8.9548436  -6.9531576
   0.0000000   0.0000000 -13.8222878  -0.4844491  11.2860114

3 行目と 4 行目を交換 ( ピボット選択 )
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107
   0.0000000  -6.9764569  11.3194464  13.3843045   6.2908205
   0.0000000   0.0000000 -13.8222878  -0.4844491  11.2860114
   0.0000000   0.0000000 -12.1262282  -8.9548436  -6.9531576

3 行目を用いた掃き出し
   6.2667432  -4.1709694   2.7041315   9.9930417   6.6635107
   0.0000000  -6.9764569  11.3194464  13.3843045   6.2908205
   0.0000000   0.0000000 -13.8222878  -0.4844491  11.2860114
   0.0000000   0.0000000   0.0000000  -8.5298387 -16.8543223

----- Step 2 -----
x :
  -0.7389604
   1.4519169
  -0.8857612
   1.9759251

検算 Ax :
   2.5537401
   9.4748287
  -7.4494552
   6.6635107

b :
   2.5537401
   9.4748287
  -7.4494552
   6.6635107

最大誤差 = 0.0000000000

応用例

 行列式や逆行列はガウスの消去法の応用で求めることができます。
Algorithm 8 ( 行列式 $|\,A\,|$ )
  1. 符号を記録するための変数 $s$ を用意し、$s=1$ とする。
  2. $A$ に対してガウスの消去法の Step 1 を実行し、 ピボット選択で行を入れ替えるごとに $s = -s$ とする。
  3. $s \times a_{11} \times \cdots a_{nn}$ を出力する。
証明 行列式の掃き出し法により。(証明終)
Algorithm 9 ( 逆行列 $A^{-1}$ ) 
  1. $A$ の右に単位行列 $E$ を並べた拡大係数行列 $(A\ E)$ に対して Step 1 を実行する。
  2. 各 $i$ について第 $i$ 行を $\dps{\frac{1}{a_{ii}}}$ 倍する。
  3. for $i = n$ downto $2$
       for $k = 1$ to $i - 1$
         第 $k$ 行から第 $i$ 行の $a_{ki}$ 倍を引く
  4. 拡大係数行列は $(E\ B)$ の形に変形されているので、 $B$ を出力する。
証明 逆行列の掃き出し法により。(証明終)
Rem.11 行列式を求める計算量は、ガウスの消去法の計算量と同程度である。

クラメルの公式は非実用的

 線形代数では次の公式も習いました:
Th.12 ( クラメルの公式 ) $A$ が $n$ 次正則行列のとき、連立一次方程式
$A\xxx=\bbb$
の解 $\xxx=(x_i)$ は次の式で与えられる:
$\dps{x_i=\frac{|\,A_j\,|}{|\,A\,|}}$
ただし $A$ の第 $j$ 列に $\bbb$ を上書きした行列を $A_j$ とする。
Ex.13 鶴亀算
$\dps{\left\{ \begin{array}{l} x + y = 7 \\ 2x + 4y = 22 \\ \end{array} \right. }$
$\dps{ A=\mat{cc}{1&1\\ 2 & 4 }, \quad \require{color} \bbb=\mat{c}{\textcolor{red}{7} \\ \textcolor{red}{22}} }$
の場合で
$\dps{ A_1=\mat{cc}{\textcolor{red}{7} & 1 \\ \textcolor{red}{22} & 4}, \quad A_2=\mat{cc}{1 & \textcolor{red}{7} \\ 2 & \textcolor{red}{22}}, }$
$\dps{ |\,A\,|=2, \quad |\,A_1\,|=6, \quad |\,A_2\,|=8 }$
より
$\dps{ x_1=\frac{|\,A_1\,|}{|\,A\,|}=3, \quad x_2=\frac{|\,A_2\,|}{|\,A\,|}=4 }$
 しかし、クラメルの公式を用いて $A\xxx=\bbb$ を解くには行列式の計算が $n+1$ 回必要であり、 Rem.11 より、それはガウスの消去法の $n$ 倍程度の時間が掛かります。 行列サイズが大きくなるほどクラメルの公式は非実用的になります。