ガウスの消去法

提供: miniwiki
移動先:案内、検索

ガウスの消去法（ガウスのしょうきょほう、英: Gaussian elimination）あるいは掃き出し法（はきだしほう、英: row reduction）とは、連立一次方程式を解くための多項式時間アルゴリズムであり、通常は問題となる連立一次方程式の係数からなる拡大係数行列に対して行われる一連の変形操作を意味する。 同様のアルゴリズムは歴史的には前漢に九章算術で初めて記述された[1]。連立一次方程式の解法以外にも

などに使われる[2][3]。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ[4]、基本的には、前進消去と後退代入という2つのステップから成る。

行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、

  • 二つの行を入れ替えるもの
  • ある行を0でない定数倍するもの
  • ある行に他のある行の定数倍を加えるもの

の三種類の操作があり、必ず行列を上三角型に変形することができる。実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分（行内の 0 でない成分のうち最も左にあるもの）が、その行の上にある行の主成分よりも、真に右側に位置する行階段形に変形される。 特に全ての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形であると呼ばれる。この最終形は一意的であり、どのような行基本変形が行われたかには依存しない。例えば、次の様な行基本変形の繰り返し（各ステップで複数の基本変形を行っている）で、三番目と四番目は共に行階段形であるが、最後の四番目が一意に定まる行簡約階段形である。

[math]\left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\ 1 & 1 & -1 & 1 \\ 3 & 11 & 5 & 35 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\ 0 & -2 & -2 & -8 \\ 0 & 2 & 2 & 8 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\ 0 & -2 & -2 & -8 \\ 0 & 0 & 0 & 0 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 0 & -2 & -3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0 \end{array}\right] [/math]

行基本変形を用いて行列を行階段形に変形することをガウス・ジョルダンの消去法（ガウス・ジョルダンのしょうきょほう、英: Gauss–Jordan elimination）という。ガウスの消去法という用語を上三角形または（簡約とは限らない）行階段形へ変換する手法を指すこともある。連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。

基本的な考え方

次の n 元m連立一次方程式を考察する。右側にある行列がその拡大係数行列である。

[math] \begin{align} &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\\ &\qquad\vdots \\ &a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_{n}= b_m \end{align}\qquad \left[\begin{array}{cccc|c} a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots \\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m \end{array}\right] [/math]

この方程式が [math]x_1 = c_1+d_{11}\lambda_1+\cdots+d_{1s}\lambda_s, x_2=c_2+d_{21}\lambda_1+\cdots+d_{2s}\lambda_s, \cdots, x_r=c_r+d_{r1}\lambda_1+\cdots+d_{rs}\lambda_s, x_{r+1}=\lambda_1,\ldots, x_n=\lambda_s[/math]（[math]n=r{+}s[/math] かつ [math]\lambda_1,..., \lambda_s[/math] は任意の定数）という解を持つとすると、これらの式は次の連立一次方程式を略記したものであると見なせる。ただし、下段に並んでいる、左辺の全ての係数が 0 である式は [math]m{-}r[/math] 本ある。 同様に右側にある行列がその拡大係数行列である。

[math]\begin{align} &1x_1 + 0x_2 + \cdots + 0x_r - d_{11}x_{r+1} -\cdots- d_{1s}x_{n} = c_1\\ &0x_1 + 1x_2 + \cdots + 0x_r - d_{21}x_{r+1} -\cdots- d_{2s}x_{n} = c_2\\ &\qquad\vdots \\ &0x_1 + 0x_2 + \cdots + 1x_r - d_{r1}x_{r+1} -\cdots- d_{rs}x_{n}= c_r \\ &0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \\ &\qquad\vdots \\ &0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \end{align}\qquad \left[\begin{array}{ccccccc|c} 1&0&\cdots&0&-d_{11}&\cdots&-d_{1s}&c_1\\ 0&1&\cdots&0&-d_{21}&\cdots&-d_{2s}&c_2\\ \vdots&\vdots&\ddots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&\cdots&1&-d_{r1}&\cdots&-d_{rs}&c_r \\ 0&0&\cdots&0&0&\cdots&0&0 \\ \vdots&\vdots&&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&\cdots&0&0&\cdots&0&0 \end{array}\right] [/math]

始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単の為、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。（最も右の列の [math]r{+}2[/math] 番目の成分以下はすべて '0'）

[math] \left[\begin{array}{ccccccc|c} 1&0&\cdots&0&-d_{11}&\cdots&-d_{1s}&c_1\\ 0&1&\cdots&0&-d_{21}&\cdots&-d_{2s}&c_2\\ \vdots&\vdots&\ddots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&\cdots&1&-d_{r1}&\cdots&-d_{rs}&c_r \\ 0&0&\cdots&0&0&\cdots&0&c_{r+1} \\ \vdots&\vdots&&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&\cdots&0&0&\cdots&0&0 \end{array}\right] [/math]

この時点で、与えられた連立一次方程式が解を持つ必要条件が [math]c_{r+1}=0[/math] であることがわかり、これは十分条件でもある。実際、[math]c_{r+1}=0[/math] とすると、上記の形の解が逆に得られていることは明らかである。 より現実的な解法としては、未知数が k 個定まった時点で残り k + 1 個の未知数を含む式が解けるため、[math]x_1[/math] から [math]x_r[/math] までの全ての変数を孤立させる必要はない。 これを行列の言葉で言えば、拡大係数行列を行簡約階段形にまで変形せずに途中で止めてしまう方がより現実的であるということになる。 つまり、拡大係数行列が次の形の行階段形に変形された時点で、それ以上の簡約化を止めるのである。このとき、対応する連立一次方程式がその右の形に表せる：

[math] \left[\begin{array}{ccccccc|c} 1&m_{12}&\cdots&m_{1r}&-d'_{11}&\cdots&-d'_{1s}&c'_1\\ 0&1&\cdots&m_{2r}&-d'_{21}&\cdots&-d'_{2s}&c'_2\\ \vdots&\vdots&\ddots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&\cdots&1&-d'_{r1}&\cdots&-d'_{rs}&c'_r \\ 0&0&\cdots&0&0&\cdots&0&0 \\ \vdots&\vdots&&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&\cdots&0&0&\cdots&0&0 \end{array}\right]\qquad \begin{align} &1x_1 + m_{12}x_2 +\cdots+ m_{1r}x_r - d'_{11}x_{r+1} -\cdots- d'_{1s}x_{n} = c'_1 \\ &0x_1 + 1x_2 + \cdots + m_{2r}x_r - d'_{21}x_{r+1} -\cdots- d'_{2s}x_{n} = c'_2 \\ &\qquad\vdots \\ &0x_1 + 0x_2 + \cdots + 1x_r - d'_{r1}x_{r+1} -\cdots- d'_{rs}x_{n} = c'_r \\ &0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \\ &\qquad\vdots \\ &0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \end{align}[/math]

従って、任意定数 [math]\lambda_1,..., \lambda_s[/math] を用いて [math]r{+}1[/math] 番目以後の s 個の変数を[math]x_{r+1}=\lambda_1, x_{r+2}=\lambda_2,..., x_{n}=\lambda_s[/math] と置き、右辺に移項して下から順に値を代入していくことで全ての解を確定できる。

例

次の連立一次方程式の解を拡大係数行列を用いずにガウスの消去法のアルゴリズムで求めてみる。 式の本数が固定されていること、式の入れ替えもまた一つの操作であることに注意すべきである。

[math]\begin{align} &2x_1 &+& 4x_2 &+& 2x_3 &+& 2x_4 &&= 8 \\ &4x_1 &+& 10x_2 &+& 3x_3 &+& 3x_4 &&= 17 \\ &2x_1 &+& 6x_2 &+& x_3 &+& x_4 &&= 9 \\ &3x_1 &+& 7x_2 &+& x_3 &+& 4x_4 &&= 11 \end{align}[/math]
  1. まず前進消去をする。
    1. 1 番目の方程式を 1/2 倍する。
      [math]\begin{align} & x_1 &+& 2x_2 &+& x_3 &+& x_4 &&= 4 \\ &4x_1 &+& 10x_2 &+& 3x_3 &+& 3x_4 &&= 17 \\ &2x_1 &+& 6x_2 &+& x_3 &+& x_4 &&= 9 \\ &3x_1 &+& 7x_2 &+& x_3 &+& 4x_4 &&= 11 \end{align}[/math]
    2. 2 番目の方程式に 1 番目の方程式の -4 倍を足す。3 番目の方程式に 1 番目の方程式の -2 倍を足す。4 番目の方程式に 1 番目の方程式の -3 倍を足す。
      [math]\begin{align} &x_1 &+& 2x_2 &+& x_3 &+& x_4 &&= 4 \\ & && 2x_2 &-& x_3 &-& x_4 &&= 1 \\ & && 2x_2 &-& x_3 &-& x_4 &&= 1 \\ & && x_2 &-& 2x_3 &+& x_4 &&= -1 \end{align}[/math]
    3. 2 番目の方程式を 1/2 倍する。
      [math]\begin{align} &x_1 &+& 2x_2 &+& x_3 &+& x_4 &&= 4 \\ & && x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &&= \frac{1}{2} \\ & && 2x_2 &-& x_3 &-& x_4 &&= 1 \\ & && x_2 &-& 2x_3 &+& x_4 &&= -1 \end{align}[/math]
    4. 3 番目の方程式に 2 番目の方程式の -2 倍を足す。4 番目の方程式に 2 番目の方程式の -1 倍を足す。
      [math]\begin{align} &x_1 &+& 2x_2 &+& x_3 &+& x_4 &&= 4 \\ & && x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &&= \frac{1}{2} \\ & && && && 0 &&= 0 \\ & && &-& \frac{3}{2}x_3 &+& \frac{3}{2}x_4 &&= -\frac{3}{2} \end{align}[/math]
    5. 3 番目の方程式と 4 番目の方程式を入れ替える。
      [math]\begin{align} &x_1 &+& 2x_2 &+& x_3 &+& x_4 &&= 4 \\ & && x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &&= \frac{1}{2} \\ & && &-& \frac{3}{2}x_3 &+& \frac{3}{2}x_4 &&= -\frac{3}{2} \\ & && && && 0 &&= 0 \end{align}[/math]
  2. 次に後退代入をする。
    1. 3 番目の方程式を [math]-\frac{2}{3}[/math] 倍する
      [math]\begin{align} &x_1 &+& 2x_2 &+& x_3 &+& x_4 &= 4 \\ & && x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &= \frac{1}{2} \\ & && && x_3 &-& x_4 &= 1 \\ & && && && 0 &= 0 \end{align}[/math]
    2. [math]x_3 = 1 + x_4[/math] を 2 番目の方程式に代入する。
      [math]\begin{align} &x_1 &+& 2x_2 &+& x_3 &+& x_4 &= 4 \\ & && x_2 && &-& x_4 &= 1 \\ & && && x_3 &-& x_4 &= 1 \\ & && && && 0 &= 0 \end{align}[/math]
    3. [math]x_3 = 1 + x_4[/math] と [math]x_2 = 1 + x_4[/math] を 1 番目の方程式に代入する。
      [math]\begin{align} x_1 + 4x_4 &= 1 \\ x_2 - x_4 &= 1 \\ x_3 - x_4 &= 1 \\ 0 &= 0 \end{align}[/math]

そこで、[math]x_4=c[/math]（"c" は任意定数）とおくと、

[math]\begin{align} x_1 &=-4c + 1 \\ x_2 &= c + 1 \\ x_3 &= c + 1 \\ x_4 &= c \end{align}[/math]

これで解が全て求まった。

一般的なアルゴリズムについては、たとえば{{#invoke:Footnotes | harvard_citation }}を見よ。

注意

  • 対角成分が 0 になる場合には、枢軸選択（ピボット選択）という式の交換を行う必要がある。
    • 対角成分が 0 になる場合以外でも、対角成分が絶対値が最大の係数になるように枢軸選択を行ったほうが、解の丸め誤差が少なくなる。ただし、これは行列要素の絶対値が同程度の大きさの場合のみ成り立ち、スケーリングを行わずに枢軸選択を行うとむしろ精度が悪化する場合もあるため、注意が必要である
    • 枢軸選択には部分選択法と完全選択法がある。絶対値が最大の係数を探索する範囲が、部分選択法は掃出し列（下方向）のみであるのに対し、完全選択法ではすべての項目（右および下方向）である。完全選択の方が計算精度は高いが計算速度およびアルゴリズムの複雑化の面で不利であるため、完全選択法の採用は現実には少ない。
  • 疎行列に対してガウスの消去法のステップを行うと疎性を損なう。
  • 前進消去の段階において対角化を目指して、後退代入を行わずに x を直接計算する方法はガウス・ジョルダンの消去法（Gauss-Jordan elimination）と呼ぶ。アルゴリズムは単純になるが、計算量は多くなる（変数が多い場合、ほぼ 1.5 倍になる）。
  • 計算量（乗算の回数）は、変数の個数を n とすると、ほぼ n3/3 になる。大部分は前進消去にかかっており、後退代入にはそれより少ないn2/2 程度である[4]。

脚注

  1. ↑ Schrijver 1998, p. 38.
  2. ↑ コルテ & フィーゲン 2009, p. 95.
  3. ↑ Schrijver 1998, p. 33.
  4. ↑ 4.0 4.1 Joel H. Ferziger; Milovan Perić; 小林敏雄、谷口伸行、坪倉誠訳 『コンピュータによる流体力学』 シュプリンガー・フェアラーク東京、2003年、88頁。ISBN 4-431-70842-1。 

参考文献

関連項目

テンプレート:Linear algebra



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ガウスの消去法&oldid=114538」から取得