前へ / 戻る / 次へ

ガウスの消去法 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$ である行列のことです。

　具体的には とします。実際、この操作で 新 $\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$ の順に値が求まったのと同じです。)

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

前へ / 戻る / 次へ