数値解析 第10回 (4) ガウスの消去法

ガウスの消去法 Step 1 ( 前進消去 )

 行基本変形を用いて、$A$ の部分が上三角行列になるように拡大係数行列 $(A\ \bbb)$ を変形します。
$(A\ \bbb)$ $\longrightarrow$ 新 $(A\ \bbb)= \dps{ \mat{ccccccc}{ a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ 0 & a_{22} & \cdots & a_{2n} & b_2 \\[-0.5em] \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & a_{nn} & b_n\\} }$
上三角行列とは、対角成分 $a_{ii}$ より下の成分が全て $0$ である行列のことです。

 具体的には
Step 1

   for $i = 1$ to $n-1$
     for $k = i + 1$ to $n$
       第 $k$ 行から第 $i$ 行の $\dps{\left(\frac{a_{ki}}{a_{ii}}\right)}$ 倍を引く

とします。実際、この操作で
新 $\dps{a_{ki}= a_{ki} - \left(\frac{a_{ki}}{a_{ii}}\right) \times a_{ii} =0}$
となりますので、$i=1$ のときに
$\require{color} \dps{ \mat{ccccccc}{ a_{11} & a_{12} & a_{13} & \cdots & a_{1n} & b_1 \\ \textcolor{red}{0} & a_{22} & a_{23} & \cdots & a_{2n} & b_2 \\ \textcolor{red}{0} & a_{32} & a_{33} &\cdots & a_{3n} & b_3 \\[-0.5em] \textcolor{red}{\vdots} & \vdots & \vdots & \ddots & \vdots & \vdots \\ \textcolor{red}{0} & a_{n2} & a_{n3} & \cdots & a_{nn} & b_n\\} }$
$i=2$ のときに
$\dps{ \mat{ccccccc}{ a_{11} & a_{12} & a_{13} & \cdots & a_{1n} & b_1 \\ 0 & a_{22} & a_{23} & \cdots & a_{2n} & b_2 \\ 0 & \textcolor{red}{0} & a_{33} &\cdots & a_{3n} & b_3 \\[-0.5em] \vdots & \textcolor{red}{\vdots} & \vdots & \ddots & \vdots & \vdots \\ 0 & \textcolor{red}{0} & a_{n3} & \cdots & a_{nn} & b_n\\} }$
という具合に $0$ が増えていきます。

ガウスの消去法 Step 2 ( 後退代入 )

 $A\xxx=\bbb$ の成分を第 $n$ 成分から逆順に辿ると
$x_n$,  $x_{n-1}$,  $\cdots$,  $x_1$
の順に値が求まってゆきます。実際、未知の数を赤字で表す
  • 第 $n$ 成分:  $a_{nn}\,\textcolor{red}{x_n} = b_n$
       $\Rightarrow$ $\textcolor{green}{x_n}$ が求まる
  • 第 $n-1$ 成分:  $a_{n-1,n-1}\,\textcolor{red}{x_{n-1}}+a_{n-1,n}\,\textcolor{green}{x_n} = b_{n-1}$
       $\Rightarrow$ $\textcolor{blue}{x_{n-1}}$ が求まる
  • 第 $n-2$ 成分:  $a_{n-2,n-2}\,\textcolor{red}{x_{n-2}}+a_{n-2,n-1}\,\textcolor{blue}{x_{n-1}}+a_{n-2,n}\,\textcolor{green}{x_n} = b_{n-2}$
       $\Rightarrow$ $x_{n-2}$ が求まる
といった具合です。( 前ページで、$z$, $y$, $x$ の順に値が求まったのと同じです。)

 具体的には
Step 2

   for $i = n$ downto $1$
     $\dps{x_i = \frac{1}{a_{ii}}\left(b_i - \sum_{j=i+1}^n a_{ij}\,x_j\right)}$

とします。プログラムでは拡大係数行列はひとつの2次元配列に格納しますので、 $b_i$ は $a_{i,n+1}$ のことです。