ガウスの消去法 - じゆうちょう

ガウスの消去法

Gaussian elimination

拡大係数行列を前進消去により変形していくことで上三角行列を得て、後退代入で解を得る方法

一般に$ n 個の変数をもつ次のn元連立1次方程式を与える:

$ \begin{cases}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\\ \quad\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n \end{cases}

これを行列表示する:

$ A\bm{x}=\bm{b}

前進消去法と後退代入法

1. 前進消去

$ a_{11}\ne0 と仮定する

$ m_{i1}\coloneqq\frac{a_{i1}}{a_{11}}\quad(i=2,3\cdots,n) と定義して$ i=2,3,\cdots,n の順に$ a_{ij}^{(2)},b_{i}^{(2)} を定義する:

$ a_{ij}^{(2)}\coloneqq a_{ij}-m_{i1}a_{1j}\quad(j=2,3,\cdots,n)

$ b_{i}^{(2)}\coloneqq b_i-m_{i1}b_1

$ i,j=1，2,\cdots,n としてもいいが、$ a_{11}^{(2)},b_{1}^{(2)} を定義しても使わないので外しているあんも.icon

この$ a_{ij}^{(2)},b_{i}^{(2)} を用いて、連立方程式を変形する:

$ \begin{cases}a_{11}x_1&+&a_{12}x_2&+&\cdots&+&a_{1n}x_n&=&b_1\\ &+&a_{22}^{(2)}x_2&+&\cdots&+&a_{2n}^{(2)}x_n&=&b_2^{(2)}\\ &&&&\cdots&&\\ &+&a_{n2}^{(2)}x_2&+&\cdots&+&a_{nn}^{(2)}x_n&=&b_n^{(2)} \end{cases}

同様の操作によってn本目の式まで変形して、上三角型の連立方程式を得る:

$ \begin{cases}a_{11}x_1&+&a_{12}x_2&+&a_{13}x_3&+&\cdots&+&a_{1n}x_n&=&b_1\\ &&a_{22}^{(2)}x_2&+&a_{23}^{(2)}x_3&+&\cdots&+&a_{2n}^{(2)}x_n&=&b_2^{(2)}\\&&&&a_{33}^{(3)}x_3&+&\cdots&+&a_{3n}^{(3)}x_n&=&b_3^{(3)} \\ &&&&&&\ddots&&&&\vdots\\ &&&&&&&&a_{nn}^{(n)}x_n&=&b_n^{(n)} \end{cases}

2. 後退代入

前進消去で得られた$ a_{nn}^{(n)}x_n=b_n^{(n)} から、$ x_n=\frac{b_n^{(n)}}{a_{nn}^{(n)}} がすぐさま得られる

どんどん上に代入していけばよいので、$ x_{n-1} は次の式で得られる:

$ x_{n-1}=\frac{1}{a_{n-1 n-1}^{(n-1)}}(b_{n-1}^{(n-1)}-a_{n-1 n}^{(n-1)}x_n)