ガウスの消去法（掃き出し法）行基本変形行簡約階段形

ブログの説明

学校に通わないで学んだことを記しています。間違っているところが何かありましたらご指摘下さると幸いです。コメントに対する返信が遅れる可能性があります。その場合は申し訳ございません。

このブログでは広告を表示しています。このブログ内の投稿記事を検索するには右上の拡大鏡のアイコンを、アーカイブやラベル付けから投稿記事を閲覧するには左上の三重線のアイコンをクリックして下さい。

数式の表示にはMathJaxを利用させていただいています。数式の表示のためにJavaScriptが有効である必要があります。そうでない場合、訳の分からないLaTeXのコードが表示されます。幾何学図形やチャートの表示にはHTML5 CanvasやGoogle Chartを使用しています。その表示のためにもJavaScriptが有効である必要があります。

ガウスの消去法（掃き出し法）行基本変形行簡約階段形

12月 11, 2021

この投稿は連立n元一次方程式を解くためのアルゴリズムの1つであるガウスの消去法（通称：掃き出し法）について簡単にまとめたもの。逆行列を用いた解法にも若干触れた。また、R言語、GNU Octave、Maxima、Python 3、Juliaを用いた連立一次方程式の解き方についても記した。

ガウスの消去法をプログラミング言語でコーディングすることについてはこの投稿では扱わなかった。それについてはまた別の機会に。

連立n元一次方程式とは

連立一次方程式は英語ではa system of linear equationsと呼ばれている。日本語に直訳すると線形方程式系。

n元とは変数（未知数）がn個あること。一次とは代数式の次数が1つのこと。方程式を構成する代数式の各項が最大で1つの変数しか持っていないこと。代数式とは数学のお馴染みの文字式のこと。代数式には単項式と二項式と多項式がある。

2 x + 3 y 1 次 式

2 x + y^{2} 2 次 式

2 x^{2} y + 5 y 3 次 式

方程式とは2つの代数式の等しい関係を等号で表したもの。

一次方程式を直交座標系に描くと直線になる。したがって線形方程式とも呼ばれている。

連立一次方程式は一次方程式の集合なので、同じ直交座標系に直線に複数描かれ、それらの直線同士が交わるところがあればそこが連立一次方程式の解になる。

例えばGeoGebraというアプリケーション・ソフトウェアを使うと、これを視覚化してくれる。GeoGebraの入力欄に連立一次方程式を構成している各々の一次方程式を入力すると直交座標系に直線を描いてくれる。

描かれた直線同士が互いに交わった点の座標がその連立一次方程式の解。

直線同士が完全に平行になって交わるところがなければその連立一次方程式は解を持たない。

直線同士が完全に重なっている場合はその連立一次方程式は無数の解を持つ。

ちなみにGeoGebraはJava言語の仮想マシンがインストールされた複数のプラットフォームで動作し、オープンソースでかつ多言語対応。

連立n元一次方程式を行列で表す

例えば次のような連立3元一次方程式があったとする。 $a_{1}, a_{2}, \dots, a_{8}$ は係数、 $x_{1}, x_{2}, x_{3}$ は変数、 $b_{1}, b_{2}, b_{3}$ は定数。

\begin{matrix} (1) & {\begin{cases} a_{1} x_{1} & + & a_{2} x_{2} & + & a_{3} x_{3} & = & b_{1} \\ a_{4} x_{1} & + & a_{5} x_{2} & + & a_{6} x_{3} & = & b_{2} \\ a_{7} x_{2} & + & a_{8} x_{3} & = & b_{3} \end{cases} \end{matrix}

この連立一次方程式(1)の係数だけを取り出し、それを行列にして表現してみる。各変数に掛けられてある各係数を連立一次方程式の並び順とまったく同じ順番に並べればよい。そうすると次のような行列ができあがる。

{\begin{cases} a_{1} x_{1} & + & a_{2} x_{2} & + & a_{3} x_{3} & = & b_{1} \\ a_{4} x_{1} & + & a_{5} x_{2} & + & a_{6} x_{3} & = & b_{2} \\ a_{7} x_{2} & + & a_{8} x_{3} & = & b_{3} \end{cases}

↕

A = (\begin{matrix} a_{1} & a_{2} & a_{3} \\ a_{4} & a_{5} & a_{6} \\ 0 & a_{7} & a_{8} \end{matrix})

この $A$ という行列は係数行列と呼ばれているもの。その第1列が変数 $x$ の係数、第2列が変数 $y$ の係数、第3列が変数 $z$ の係数。また、係数と変数（未知数）共に欠けている項が0になることに要注意。

この係数行列 $A$ に連立一次方程式の右辺にある定数を更に含めると次のような行列ができあがる。

{\begin{cases} a_{1} x_{1} & + & a_{2} x_{2} & + & a_{3} x_{3} & = & b_{1} \\ a_{4} x_{1} & + & a_{5} x_{2} & + & a_{6} x_{3} & = & b_{2} \\ a_{7} x_{2} & + & a_{8} x_{3} & = & b_{3} \end{cases}

↕

\tilde{A} = (\begin{array}{cccc} a_{1} & a_{2} & a_{3} & b_{1} \\ a_{4} & a_{5} & a_{6} & b_{2} \\ 0 & a_{7} & a_{8} & b_{3} \end{array})

この $\tilde{A}$ という行列は拡大係数行列または拡大行列と呼ばれているもの。|（パイプ）の右側にある列ベクトル $(b_{1} b_{2} b_{3})$ は連立一次方程式の右辺ベクトルまたは定数項べクトルと呼ばれることがある。

上記の連立一次方程式(1)を係数行列と列ベクトルを用いて行列方程式 $A \vec{x} = \vec{b}$ として表すと、次のようになる。

{\begin{cases} a_{1} x_{1} & + & a_{2} x_{2} & + & a_{3} x_{3} & = & b_{1} \\ a_{4} x_{1} & + & a_{5} x_{2} & + & a_{6} x_{3} & = & b_{2} \\ a_{7} x_{2} & + & a_{8} x_{3} & = & b_{3} \end{cases}

↕

(\begin{matrix} a_{1} & a_{2} & a_{3} \\ a_{4} & a_{5} & a_{6} \\ 0 & a_{7} & a_{8} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \end{matrix})

同様にしてベクトル方程式として表すと次のようになる。

{\begin{cases} a_{1} x_{1} & + & a_{2} x_{2} & + & a_{3} x_{3} & = & b_{1} \\ a_{4} x_{1} & + & a_{5} x_{2} & + & a_{6} x_{3} & = & b_{2} \\ a_{7} x_{2} & + & a_{8} x_{3} & = & b_{3} \end{cases}

↕

x_{1} (\begin{matrix} a_{1} \\ a_{4} \\ 0 \end{matrix}) + x_{2} (\begin{matrix} a_{2} \\ a_{5} \\ a_{7} \end{matrix}) + x_{3} (\begin{matrix} a_{3} \\ a_{6} \\ a_{8} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \end{matrix})

ちなみに、各変数項に定数を乗算してそれらを加算した式は線形結合と呼ばれている。またの名を一次結合。

\sum_{i = 1}^{n} a_{i} x_{i} = a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3} + \dots + a_{n} x_{n}

では以上の操作の具体例を挙げてみる。例えば次のような連立一次方程式があったとする。xとyがその値を知りたい変数、つまり未知数。

\begin{matrix} (2) & {\begin{cases} 2 x - y = 5 \\ x - y = 3 \end{cases} \end{matrix}

数学の表記上の理由で言うまでもなく次の2つの連立一次方程式が等しいことは自明。

{\begin{cases} 2 x - y = 5 \\ x - y = 3 \end{cases} \leftrightarrow {\begin{cases} 2 x + (- 1 y) = 5 \\ 1 x + (- 1 y) = 3 \end{cases}

連立一次方程式(2)の係数行列Aと拡大係数行列 $\tilde{A}$ はそれぞれ次のように表すことができる。

A = (\begin{matrix} 2 & - 1 \\ 1 & - 1 \end{matrix})

\tilde{A} = (\begin{array}{ccc} 2 & - 1 & 5 \\ 1 & - 1 & 3 \end{array})

係数行列と列ベクトルを用いて行列方程式 $A \vec{x} = \vec{b}$ として表すと次のようになる。

(\begin{matrix} 2 & - 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} 5 \\ 3 \end{matrix})

次のように線形結合のベクトル方程式としても表現できる。

x (\begin{matrix} 2 \\ 1 \end{matrix}) + y (\begin{matrix} - 1 \\ - 1 \end{matrix}) = (\begin{matrix} 5 \\ 3 \end{matrix})

掃き出し法、ガウスの消去法

連立一次方程式を解くためのアルゴリズムにガウスの消去法と呼ばれているものがある。ガウスの消去法は日本では掃き出し法という通称で呼ばれていることが多い。

連立一次方程式の解を掃き出し法によって求めるには、まず連立一次方程式を拡大係数行列の形に直した後、その拡大係数行列が行簡約階段形と呼ばれる形になるように行基本変形と呼ばれる操作を繰り返す。

行簡約階段形は行既約階段形とも呼ばれている。

拡大係数行列の左辺、つまり係数行列の部分が正方行列であるとき、行簡約階段形は単位行列の形になる。正方行列とは行列の列と行とが同じ数であること。

行簡約階段形や単位行列がどういう行列の形であるかについては後ほど詳しく記す。

行基本変形と呼ばれている操作には次の3種類がある。ただしここでの表記の順番はその手順とは無関係。

ある行を別の行と交換すること、
ある行の全成分に0でない定数を掛けること、
ある行を定数倍した値を別の行に加えること。

次のようなバージョンもある。

ある行を別の行と交換すること、
ある行の全成分を0でない定数で割ること、
ある行を定数倍した値を別の行から引くこと。

掛け算が割り算に、足し算が引き算に置き換わっているが、割り算が分数を掛けることであり引き算が負数を足すことであることを思い起こせば、掛け算と割り算、足し算と引き算とが互換性を持つことを理解できる。

例題1.

次のような連立一次方程式があったとする。

\begin{matrix} (2) & {\begin{cases} 2 x - y = 5 \\ x - y = 3 \end{cases} \end{matrix}

この連立一次方程式(2)を掃き出し法によって解くと次のようになる。

連立一次方程式(2)を拡大係数行列として表す。
${\begin{cases} 2 x - y = 5 \\ x - y = 3 \end{cases} \leftrightarrow (\begin{array}{ccc} 2 & - 1 & 5 \\ 1 & - 1 & 3 \end{array})$
拡大係数行列の変数項の部分、つまり係数行列の部分を上記の3種類の行基本変形を用いて次のような形にするにはどうしたらよいかを考える。
$(\begin{array}{ccc} 1 & 0 & ? \\ 0 & 1 & ? \end{array})$
拡大係数行列の左上端の成分（この例題では2）はピボットと呼ばれている。このピボットをとにかく1にすると便利なので、行基本変形1を適用して第1行と第2行を交換してみる。 $R_{n}$ は拡大係数行列の第n行を指している。
$R_{1} ⇆ R_{2}$ $(\begin{array}{ccc} 2 & - 1 & 5 \\ 1 & - 1 & 3 \end{array}) \to (\begin{array}{ccc} 1 & - 1 & 3 \\ 2 & - 1 & 5 \end{array})$
ピボットを1にすることができた。
行基本変形3を適用し、第1行を-2倍し、第2行に加算してみる。
$(\begin{array}{ccc} 1 & - 1 & 3 \\ 2 & - 1 & 5 \end{array})$ $↓$ $- 2 R_{1} + R_{2} \to R_{2}$ $(\begin{array}{ccc} 1 & - 1 & 3 \\ - 2 \cdot 1 + 2 & - 2 \cdot - 1 + (- 1) & - 2 \cdot 3 + 5 \end{array})$ $↓$ $(\begin{array}{ccc} 1 & - 1 & 3 \\ 0 & 1 & - 1 \end{array})$
第2行第2列の成分もこれで1にすることができた。
行基本変形3を適用し、第2行を1倍し、つまりそのまま第1行に加算してみる。
$(\begin{array}{ccc} 1 & - 1 & 3 \\ 0 & 1 & - 1 \end{array})$ $↓$ $R_{2} + R_{1} \to R_{1}$ $(\begin{array}{ccc} 0 + 1 & 1 + (- 1) & - 1 + 3 \\ 0 & 1 & - 1 \end{array})$ $↓$ $(\begin{array}{ccc} 1 & 0 & 2 \\ 0 & 1 & - 1 \end{array})$
拡大係数行列の左辺、つまり係数行列の部分が、対角線上に1が並ぶ単位行列の形になったのでこれで完了。連立一次方程式(2)の解は
$(\begin{array}{ccc} 1 & 0 & 2 \\ 0 & 1 & - 1 \end{array}) \leftrightarrow {\begin{cases} x = 2 \\ y = - 1 \end{cases}$
と求まった。

R言語で連立一次方程式を解く

Rで答え合わせをしてみる。Rで連立一次方程式を解くためには、matrix()とc()とで係数行列と定数項の列ベクトルをまず作成する。そしてsolve()に両者を渡せばその連立一次方程式の解が返ってくる。

> A = matrix(c(2,-1,1,-1),nrow=2,ncol=2,byrow=T)
> A
     [,1] [,2]
[1,]    2   -1
[2,]    1   -1
> b = matrix(c(5,3),nrow=2,ncol=1,byrow=T)
> b
     [,1]
[1,]    5
[2,]    3
> solve(A,b)
     [,1]
[1,]    2
[2,]   -1
> q()

2と-1が返ってきた。

rref()を利用することもできる。MATLABの函数を利用するため、pracmaというパッケージが必要。Debian GNU/Linuxではr-cran-pracmaというdebパッケージをインストールする必要があった。

> A = matrix(c(2,-1,5,1,-1,3),nrow=2,ncol=3,byrow=T)
> A
     [,1] [,2] [,3]
[1,]    2   -1    5
[2,]    1   -1    3
> library(pracma)
> rref(A)
     [,1] [,2] [,3]
[1,]    1    0    2
[2,]    0    1   -1
> q()

GNU Octaveで連立一次方程式を解く

GNU Octaveでは係数行列Aと定数項の列ベクトルbを作成してlinsolve()に渡せば連立一次方程式の解が返ってくる。

octave:1> A = [2 -1; 1 -1]
A =

   2  -1
   1  -1

octave:2> b = [5;3]
b =

   5
   3

octave:3> linsolve(A,b)
ans =

   2
  -1

octave:4> quit

やはり同様に2と-1が返ってきた。

MATLAB互換なのでGNU Octaveには標準でrref()がある。拡大係数行列を作ってrref()に渡せば、ガウス＝ジョルダンの消去法によって拡大係数行列からその行簡約階段形を生成してくれる。

>> A = [2 -1 5; 1 -1 3]
A =

   2  -1   5
   1  -1   3

>> rref(A)
ans =

   1   0   2
   0   1  -1

>> quit

第3列、つまり連立一次方程式の定数項によって構成された列ベクトルの部分が2と-1であることが分かる。この方法でも同じ解を得ることができた。

Python3で連立一次方程式を解く

Python 3ではnumpy.linalg.solve()を利用する。そのためにはNumpyをimportする必要がある。Python3で連立一次方程式を解く手順は次のとおり。

>>> import numpy as np
>>> A = np.matrix('2,-1; 1,-1')
>>> print(A)
[[ 2 -1]
 [ 1 -1]]
>>> b = np.matrix('5; 3')
>>> print(b)
[[5]
 [3]]
>>> x = np.linalg.solve(A,b)
>>> print(x)
[[ 2.]
 [-1.]]
>>> quit()

Python 3でも同じく2と-1となった。

Maximaで連立一次方程式を解く

Maximaで連立一次方程式を解くには、各々の変数に連立一次方程式を構成する各々の一次方程式を割り当て、その各々の変数とその連立一次方程式の未知数をsolve()に次のようにして共に渡す。eqn1とeqn2は方程式を割り当てた任意の変数名。乗法の演算子*はMaximaでは入力時に省略できないので忘れずに。

(%i1) eqn1: 2*x - y = 5;
(%o1)                             2 x - y = 5
(%i2) eqn2: x - y = 3;
(%o2)                              x - y = 3
(%i3) solve([eqn1,eqn2],[x,y]);
(%o3)                         [[x = 2, y = - 1]]
(%i4) quit();

Juliaで連立一次方程式を解く

Juliaでは係数行列の逆行列を用いて連立一次方程式を解いてみる。inv()に行列を渡すとその逆行列が返ってくる。そして係数行列の逆行列と定数項の列ベクトルの内積を求めるか、\という演算子を使う。つまり次のようにして連立一次方程式を解くことができる。

julia> A = [2 -1; 1 -1]
2×2 Array{Int64,2}:
 2  -1
 1  -1

julia> b = [5; 3]
2-element Array{Int64,1}:
 5
 3

julia> inv(A) * b
2-element Array{Float64,1}:
  2.0
 -1.0

julia> A \ b
2-element Array{Float64,1}:
  2.0
 -1.0

julia> exit()

いずれの計算でも2.0と-1.0が得られた。したがって逆行列を利用した場合にも連立一次方程式(2)の解は同じになった。

逆行列を利用した連立一次方程式の解法

連立一次方程式を係数行列と列ベクトルとの積の形をした行列方程式 $A \vec{x} = \vec{b}$ に直してみると、逆行列には次のような関係があることが分かる。行列の右肩に乗っている指数-1がその行列の逆行列であることを示す目印。

(\begin{matrix} 2 & - 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} 5 \\ 3 \end{matrix})

{(\begin{matrix} 2 & - 1 \\ 1 & - 1 \end{matrix})}^{- 1} (\begin{matrix} 5 \\ 3 \end{matrix}) = (\begin{matrix} x \\ y \end{matrix})

行列演算における逆行列はスカラー演算における逆数と同じ役割を持っている。3の逆数は3分の1。3分の1は指数を用いて $3^{- 1}$ とも書くことができる。

3 \times 5 = 15

\frac{1}{3} \times 15 = 5

\frac{1}{3} = 3^{- 1}

掃き出し法（ガウスの消去法）を利用すると、ある行列からその逆行列を求めることもできる。その方法についてはまたの機会に。

係数行列が逆行列を持つ場合、したがってその行列式が0にならない場合、もとの連立一次方程式は必ず解を持つことが知られている。逆行列を持つ行列のことを正則行列と呼ぶので、係数行列が正則行列であるときにはガウスの消去法が適用できる。

ちなみに、行列式を求めるには、RとGNU Octaveではdet()、Python3ではnumpyをimportしてlinalg.det()、Maximaではdeterminant()、Juliaではusing LinearAlgebraを実行してからdet()のそれぞれ()内に行列を渡す。

例題2.

もう1つ、次の連立一次方程式を解いてみる。

{\begin{cases} - \frac{5}{7} - \frac{11}{7} x = - y \\ 2 y = 7 + 5 x \end{cases}

この連立一次方程式は変数項と定数項が上下に揃っていないので、それらを整頓して標準形にすることから始める必要がある。標準形というのは例えば次のような連立一次方程式の形のこと。aからdが係数、xとyが変数（未知数）、mとnが定数。

{\begin{cases} a x + b y = m \\ c x + d y = n \end{cases}

左辺の変数xの項と変数yの項と右辺の定数項がそれぞれ列方向に揃っていることが見て取れる。この形が連立一次方程式の標準形。

連立一次方程式の項に分数がある場合には計算をしやすくするために分数の分母を取り払っておくと便利。分母と同じ数をその分数に掛けるか、同じ方程式に複数の分数があればその最小公倍数を掛ける。

方程式には等号を挟んだ両辺に同じ数による同じ演算を常に施して両辺の均衡を保つ必要があることを忘れずに。

分数を持つ一次方程式を7倍して分母の7を取り払っておく。
${\begin{cases} - \frac{5}{7} - \frac{11}{7} x = - y \\ 2 y = 7 + 5 x \end{cases}$ $↓$ ${\begin{cases} 7 \cdot - \frac{5}{7} - 7 \cdot \frac{11}{7} x = 7 \cdot - y \\ 2 y = 7 + 5 x \end{cases}$ $= {\begin{cases} - 5 - 11 x = - 7 y \\ 2 y = 7 + 5 x \end{cases}$
移項によって各項の配置換えをして式を変形し、連立一次方程式を標準形を作る。移項とは方程式の特定の項を消すために両辺に同じ数の同じ演算を行い、その結果としてその項が等号の右辺と左辺の間を符号の反転を伴って移動したように見える操作。
${\begin{cases} - 5 - 11 x = - 7 y \\ 2 y = 7 + 5 x \end{cases}$ $↓$ ${\begin{cases} - 5 + 5 - 11 x + 7 y = - 7 y + 7 y + 5 \\ - 5 x + 2 y = 7 + 5 x - 5 x \end{cases}$ $= {\begin{cases} - 11 x + 7 y = 5 \\ - 5 x + 2 y = 7 \end{cases}$
上段の方程式の左辺にある-5に5を足して-5を消し、方程式の均衡を保つためにその右辺にも5を足した。上段の方程式の右辺にある-7yに7yを足して-7yを消し、方程式の均衡を保つためにその左辺にも7yを足した。さらに、下段の方程式の右辺の5xを消すために5xを引き、方程式の均衡を保つためにその左辺に-5xを加えた。これで連立一次方程式の標準形が完成した。
標準形から拡大係数行列を作成する。
${\begin{cases} - 11 x + 7 y = 5 \\ - 5 x + 2 y = 7 \end{cases} \leftrightarrow (\begin{array}{ccc} - 11 & 7 & 5 \\ - 5 & 2 & 7 \end{array})$
0でない行頭（ピボット）の絶対値が最大のものが第1行目にあることが望ましいのでそうなっていない場合は行交換をする必要があったが、この場合はその必要がない。
行基本変形3を適用し、第1行を-1倍して第2行に足してみる。 $R_{1}, R_{2}, \dots$ は行列の各行を指している。例えば $R_{2}$ は第2行。
$(\begin{array}{ccc} - 11 & 7 & 5 \\ - 5 & 2 & 7 \end{array})$ $↓$ $- R_{1} + R_{2} \to R_{2}$ $(\begin{array}{ccc} - 11 & 7 & 5 \\ - 1 \cdot - 11 + (- 5) & - 1 \cdot 7 + 2 & - 1 \cdot 5 + 7 \end{array})$ $= (\begin{array}{ccc} - 11 & 7 & 5 \\ 6 & - 5 & 2 \end{array})$
行基本変形3を適用し、第2行を2倍して第1行に足してみる。
$(\begin{array}{ccc} - 11 & 7 & 5 \\ 6 & - 5 & 2 \end{array})$ $↓$ $2 R_{2} + R_{1} \to R_{1}$ $(\begin{array}{ccc} 2 \cdot 6 + (- 11) & 2 \cdot - 5 + 7 & 2 \cdot 2 + 5 \\ 6 & - 5 & 2 \end{array})$ $= (\begin{array}{ccc} 1 & - 3 & 9 \\ 6 & - 5 & 2 \end{array})$
ピボットを1にすることができた。
行基本変形3を適用し、第1行を-6倍して第2行に足してみる。
$(\begin{array}{ccc} 1 & - 3 & 9 \\ 6 & - 5 & 2 \end{array})$ $↓$ $- 6 R_{1} + R_{2} \to R_{2}$ $(\begin{array}{ccc} 1 & - 3 & 9 \\ - 6 \cdot 1 + 6 & - 6 \cdot - 3 + (- 5) & - 6 \cdot 9 + 2 \end{array})$ $= (\begin{array}{ccc} 1 & - 3 & 9 \\ 0 & 13 & - 52 \end{array})$
行基本変形2を適用し、第2行を13分の1倍する。つまり13で割ってみる。
$(\begin{array}{ccc} 1 & - 3 & 9 \\ 0 & 13 & - 52 \end{array})$ $↓$ $\frac{1}{13} R_{2} \to R_{2}$ $(\begin{array}{ccc} 1 & - 3 & 9 \\ \frac{1}{13} \cdot 0 & \frac{1}{13} \cdot 13 & \frac{1}{13} \cdot - 52 \end{array})$ $= (\begin{array}{ccc} 1 & - 3 & 9 \\ 0 & 1 & - 4 \end{array})$
これで拡大係数行列の左辺の係数行列の部分が行階段形になった。ここまでの処理は狭義でのガウスの消去法。ここまでの処理はガウスの消去法において前進消去と呼ばれている。ここから先はガウス＝ジョーダンの消去法。
第1行第2列の-3を消すために行基本変形3を適用し、第2行を3倍して第1行に足してみる。
$(\begin{array}{ccc} 1 & - 3 & 9 \\ 0 & 1 & - 4 \end{array})$ $↓$ $3 R_{2} + R_{1} \to R_{1}$ $(\begin{array}{ccc} 3 \cdot 0 + 1 & 3 \cdot 1 + (- 3) & 3 \cdot - 4 + 9 \\ 0 & 1 & - 4 \end{array})$ $= (\begin{array}{ccc} 1 & 0 & - 3 \\ 0 & 1 & - 4 \end{array})$
これで拡大係数行列が行簡約階段形、したがって係数行列の部分が単位行列の形になった。ここでガウス＝ジョーダンの消去法が完了。
あとは拡大係数行列を連立一次方程式の形に戻せば、
$(\begin{array}{ccc} 1 & 0 & - 3 \\ 0 & 1 & - 4 \end{array}) \leftrightarrow {\begin{cases} x = - 3 \\ y = - 4 \end{cases}$
と求まったことが分かる。

ガウスの消去法では、行階段形になったところで行基本変形を中断し、連立一次方程式の形に戻し、代入法によってその解を求めることもできる。この代入は後退代入と呼ばれている。それは次のようにする。

(\begin{array}{ccc} 1 & - 3 & 9 \\ 0 & 1 & - 4 \end{array}) \leftrightarrow {\begin{cases} x - 3 y = 9 \\ y = -4 \end{cases}

↓

\begin{aligned} x - 3 \cdot -4 & = 9 \\ x & = \frac{9 + 3}{- 4} \\ x & = - \frac{12}{4} \\ x & = - 3 \end{aligned}

これは移項ではないので符号は変わらない。

そんなわけで狭義でのガウスの消去法には前進消去と後退代入との2段階がある。

Maximaで答え合わせをしてみる。

(%i1) eqn1: -(5/7) - (11/7)*x = -y;
                                 11 x    5
(%o1)                         (- ----) - - = - y
                                  7      7
(%i2) eqn2: 2*y = 7 + 5*x;
(%o2)                            2 y = 5 x + 7
(%i3) solve([eqn1,eqn2],[x,y]);
(%o3)                        [[x = - 3, y = - 4]]
(%i4) quit();

Maximaで計算してもxが-3でyが-4になった。

行階段形と行簡約階段形とピボット

ここでは、ガウスの消去法で重要な役割を果たす行階段形という概念と、ガウス＝ジョーダンの消去法で重要な役割を果たす行簡約階段形という概念について直感的に記す。

典型的な行階段形は次のような形をした行列。ただし $a_{1}, a_{2}, \dots$ は0以外の成分。

(\begin{matrix} 1 & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ 0 & 1 & a_{6} & a_{7} & a_{8} & a_{9} \\ 0 & 0 & 1 & a_{10} & a_{11} & a_{12} \\ 0 & 0 & 0 & 1 & a_{13} & a_{14} \\ 0 & 0 & 0 & 0 & 1 & a_{15} \end{matrix})

次のような行列も行階段形。

(\begin{matrix} 1 & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ 0 & 0 & 1 & a_{5} & a_{6} & a_{8} \\ 0 & 0 & 0 & 1 & a_{7} & a_{10} \\ 0 & 0 & 0 & 0 & 1 & a_{11} \end{matrix})

1が対角線上に綺麗に並んでいなくても行階段形が成り立つ。

次のような行列も行階段形。

(\begin{matrix} 0 & 1 & a_{1} & a_{2} & a_{3} & a_{4} \\ 0 & 0 & 1 & a_{5} & a_{6} & a_{8} \\ 0 & 0 & 0 & 1 & a_{7} & a_{10} \\ 0 & 0 & 0 & 0 & 1 & a_{11} \end{matrix})

次のような行列は行階段形でない。

(\begin{matrix} 1 & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ 0 & 1 & a_{6} & a_{7} & a_{8} & a_{9} \\ 0 & 0 & 0 & a_{10} & a_{11} & a_{12} \\ 0 & 0 & 0 & 0 & 1 & a_{13} \end{matrix})

各行の先頭が1でない行列は行階段形であるとは言えない。

次のような行列も行階段形ではない。

(\begin{matrix} 1 & a_{1} & a_{2} & a_{3} & a_{4} \\ 0 & 0 & 1 & a_{5} & a_{6} \\ 0 & 0 & 1 & a_{7} & a_{8} \\ 0 & 0 & 0 & 1 & a_{9} \\ 0 & 0 & 0 & 1 & a_{10} \end{matrix})

行の先頭の1はその上の行の先頭の1よりも常に右の列に位置していなければ行階段形の条件を満たさない。

ちなみに、行頭が1でない場合、同様の形をした行列は上三角行列と呼ばれている。

行簡約階段形は次のような形をした行列。つまり、行階段形の右上の成分が更に0へと削減され、行頭の1がある列がその1以外すべて0になった形。

(\begin{matrix} 1 & 0 & 0 & 0 & 0 & a_{1} \\ 0 & 1 & 0 & 0 & 0 & a_{2} \\ 0 & 0 & 1 & 0 & 0 & a_{3} \\ 0 & 0 & 0 & 1 & 0 & a_{4} \\ 0 & 0 & 0 & 0 & 1 & a_{5} \end{matrix})

次のような行列も行簡約階段形。

(\begin{matrix} 1 & 0 & a_{1} & 0 & 0 & a_{2} \\ 0 & 1 & a_{3} & 0 & 0 & a_{4} \\ 0 & 0 & 0 & 1 & 0 & a_{5} \\ 0 & 0 & 0 & 0 & 1 & a_{6} \end{matrix})

各行の先頭の成分が1であり、第2行以下の先頭の1はその上の行の先頭の1よりもすべて右側の列にあり、先頭の1がある列はその1以外すべて0なので、行簡約階段形の条件を満たしている。

次のような行列は行簡約階段形ではない。

(\begin{matrix} 1 & 0 & a_{1} & 0 & 0 & a_{2} \\ 0 & 1 & a_{3} & 0 & 0 & a_{4} \\ 0 & 0 & 0 & 1 & a_{5} & a_{6} \\ 0 & 0 & 0 & 0 & 1 & a_{7} \end{matrix})

第4行の先頭の1と同じ列に0以外の成分が含まれているので行簡約階段形の条件を満たすことができない。

0を除外して見たとき、各行の先頭の成分はピボットとも呼ばれている。ガウスの消去法においてピボットをいかに選択するかが演算の効率を決める。コンピュータで連立一次方程式の数値計算を行う場合、ピボットを適切に選択することが丸め誤差の問題を回避するために特に重要になる。

まとめ

ガウスの消去法: 英語ではGaussian Elimination。連立一次方程式（線形方程式系とも呼ばれている）を行列を用いて解く方法。; 連立一次方程式の左辺の共通する変数項と右辺の定数項を揃え、その係数と定数をその順番のとおりに行列として並べて連立一次方程式の標準形を作り、そこから係数と定数を取り出し、標準形の並び順の通りに並べて拡大係数行列を作る。そしてその拡大係数行列が行階段形になるように3種類の行基本変形を選んで行う。; ガウス＝ジョーダンの消去法と区別して称した場合のガウス消去法は、拡大係数行列が行階段形になるまで行基本変形を繰り返すものを指し、これを前進消去と呼ぶことがある。行階段形になった時点で拡大係数行列を連立一次方程式に戻し、そこから後退代入による計算を行ってその連立一次方程式の解を最終的に得る。; 計算機科学の数値計算プログラミングにおいてよく例示されているアルゴリズムはこれ。

ガウス＝ジョーダンの消去法（ガウス＝ジョルダンの消去法）: 英語ではGaussian-Jordan Elimination。日本語では掃き出し法とも呼ばれている。連立一次方程式（線形方程式系とも呼ばれている）を行列を用いて解く方法。掃き出し法やガウスの消去法と言えば数学では通常こちらを指すことが多い。; ガウスの消去法では拡大係数行列が行階段形になるまで行基本変形を繰り返すのに対し、ガウス＝ジョーダンの消去法では拡大係数行列が行簡約階段形（行既約階段形とも呼ばれている）になるまで行基本変形を繰り返す。; ガウス＝ジョーダンの消去法を選ぶかガウスの消去法を選ぶかは場合によりけり。

係数行列: 英語ではCoefficient Matrices。連立一次方程式を標準形に変形し、その左辺にある係数すべてを同じ変数同士で列を構成するように並べて行列にしたもの。 $a_{11}, \dots, a_{m n}$ は係数、 $x_{1}, \dots, x_{n}$ は未知の変数（未知数）、 $b_{1}, \dots, b_{n}$ は定数。
${\begin{cases} a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3} + \dots + a_{2 n} x_{n} = b_{2} \\ a_{31} x_{1} + a_{32} x_{2} + a_{33} x_{3} + \dots + a_{3 n} x_{n} = b_{3} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + a_{m 3} x_{3} + \dots + a_{m n} x_{n} = b_{n} \end{cases}$ $↕$ $(\begin{matrix} a_{11} & a_{12} & a_{13} & \dots & a_{1 n} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2 n} \\ a_{31} & a_{32} & a_{33} & \dots & a_{3 n} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m n} \end{matrix})$

拡大係数行列: 英語ではAugmented Matrices。単に拡大行列とも呼ばれている。連立一次方程式の標準形の右辺にある定数項の列を係数行列の右側に追加した行列のこと。 $a_{11}, \dots, a_{m n}$ は係数、 $x_{1}, \dots, x_{n}$ は未知の変数（未知数）、 $b_{1}, \dots, b_{n}$ は定数。
${\begin{cases} a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3} + \dots + a_{2 n} x_{n} = b_{2} \\ a_{31} x_{1} + a_{32} x_{2} + a_{33} x_{3} + \dots + a_{3 n} x_{n} = b_{3} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + a_{m 3} x_{3} + \dots + a_{m n} x_{n} = b_{n} \end{cases}$ $↕$ $(\begin{array}{cccccc} a_{11} & a_{12} & a_{13} & \dots & a_{1 n} & b_{1} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2 n} & b_{2} \\ a_{31} & a_{32} & a_{33} & \dots & a_{3 n} & b_{3} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m n} & b_{n} \end{array})$

行基本変形

英語ではElementary Row Operations。拡大係数行列を構成する行に対し、3種類の操作を用いて行列の成分を0に、もしくは行列の成分の係数を1にもってゆく方法。3種類の操作とは、

ある2つの行同士の位置を置き換えること（ $R_{1} ⇆ R_{2}$ ）、
ある行の各成分を共通の値で定数倍すること（ $r R_{i}$ ）、
ある行の各成分を共通の値で定数倍した各値をもう1つの行の同の一列の各成分に加算すること（ $r R_{1} + R_{2} \to R_{2}$ ）

を指している。

R_{1}, R_{2}, \dots, R_{i}

は各行または任意の行、rはなんらかの実数。行基本変形では同一行の全ての成分に同じ演算を行う必要がある。

単位行列: 英語ではIdentity Matrices。正方行列であり、かつ、対角行列であり、かつ、対角線上の成分が1のみで構成された行列のこと。行列の演算においてスカラーの1と同様の働きを持つ。; 例えば次の行列は4列4行の、つまり4次の単位行列。
$I_{4} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix})$

行列の行階段形: 英語ではRow Echelon Formと呼ばれており、頭文字を使ってREFと略されることが多い。次のような行列のこと。ただし $a_{1}, a_{2}, a_{3}, \dots$ は0でない成分。
$R E F = (\begin{matrix} 1 & a_{1} & a_{2} & a_{3} & a_{4} \\ 0 & 1 & a_{5} & a_{6} & a_{7} \\ 0 & 0 & 1 & a_{8} & a_{9} \\ 0 & 0 & 0 & 1 & a_{10} \end{matrix})$ $R E F = (\begin{matrix} 0 & 1 & a_{1} & a_{2} & a_{3} & a_{4} \\ 0 & 0 & 1 & a_{5} & a_{6} & a_{7} \\ 0 & 0 & 0 & 0 & 1 & a_{8} \end{matrix})$

行簡約階段形: 英語ではReduced Row Echelon Form。頭字語ではRREF。行列の行簡約階段形は行列の行階段形であり、かつ、行頭の1がある列がその1以外全て0になっているもの。典型的には次のような形をしている。 $a_{1}, \dots, a_{4}$ は0でない成分。
$R R E F = (\begin{matrix} 1 & 0 & 0 & 0 & a_{1} \\ 0 & 1 & 0 & 0 & a_{2} \\ 0 & 0 & 1 & 0 & a_{3} \\ 0 & 0 & 0 & 1 & a_{4} \end{matrix})$

連立n元一次方程式の標準形: 連立一次方程式を拡大係数行列に転記するためには連立一次方程式が標準形になっている必要がある。そうなっていなければ移項を使って標準形になるように式を変形することができる。; 連立n元一次方程式の標準形を一般形として記すと次のようになる。ただし $a_{11}, \dots, a_{m n}$ は係数、 $x_{1}, \dots, x_{n}$ は未知の変数（未知数）、 $b_{1}, \dots, b_{n}$ は定数。
${\begin{cases} a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3} + \dots + a_{2 n} x_{n} = b_{2} \\ a_{31} x_{1} + a_{32} x_{2} + a_{33} x_{3} + \dots + a_{3 n} x_{n} = b_{3} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + a_{m 3} x_{3} + \dots + a_{m n} x_{n} = b_{n} \end{cases}$; これを行列方程式 $A \vec{x} = \vec{b}$ として一般的に表すと次のようになる。
$(\begin{matrix} a_{11} & a_{12} & a_{13} & \dots & a_{1 n} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2 n} \\ a_{31} & a_{32} & a_{33} & \dots & a_{3 n} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m n} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ x_{n} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \\ ⋮ \\ b_{n} \end{matrix})$; これをベクトル方程式として一般的に表すと次のようになる。
$x_{1} (\begin{matrix} a_{11} \\ a_{21} \\ a_{31} \\ ⋮ \\ a_{m 1} \end{matrix}) x_{2} (\begin{matrix} a_{12} \\ a_{22} \\ a_{32} \\ ⋮ \\ a_{m 2} \end{matrix}) x_{3} (\begin{matrix} a_{13} \\ a_{23} \\ a_{33} \\ ⋮ \\ a_{m 3} \end{matrix}) \dots x_{n} (\begin{matrix} a_{1 n} \\ a_{2 n} \\ a_{3 n} \\ ⋮ \\ a_{m n} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \\ ⋮ \\ b_{n} \end{matrix})$
各列ベクトルが各未知数（各変数）によって重み付けされている関係がこの式から見て取れる。

R言語で連立一次方程式を解くには: matrix()とc()で係数行列と定数項の列ベクトルを用意し、solve()の引数として渡す。あるいはまた、pracmaというパッケージを利用してMATLAB互換のrref()を用いることができる。その際にlibrary(pracma)を実行しておく必要がある。

Python3で連立一次方程式を解くには: Numpyをimportし、numpy.matrix()で係数行列と定数項の列ベクトルを作成した後、それらをnumpy.linalg.solve()の引数として渡す。

GNU Octaveで連立一次方程式を解くには: 係数行列と定数項の列ベクトルを作成した後、linsolve()の引数としてそれらを渡す。

Maximaで連立一次方程式を解くには: 連立一次方程式を構成する各々の一次方程式をeqn1,eqn2,eqn3とし、各々の未知の変数をx,y,zとした場合、solve([eqn1,eqn2,eqn3],[x,y,z])とすることによってその解を求めることができる。

Juliaで連立一次方程式を解くには: 係数行列と定数項の列ベクトルを作成した後、演算子の\を用いるか、inv()で係数行列の逆行列を作って列ベクトルとの内積を求める。

逆行列: 英語ではMatrix InversesとかInverse Matricesなどと呼ばれることがある。ある行列の余因子行列と行列式を導き出し、それら余因子行列と行列式分の1との定数倍を求めると逆行列が出来上がる。通常のスカラー代数で言うところの逆数に当たる。逆行列は右肩に-1を添えて表されることが多い。; $a_{11}, \dots, a_{22}$ は任意の成分。
$\begin{aligned} {(\begin{array}{c} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array})}^{- 1} & = \frac{1}{a_{11} a_{22} - a_{12} a_{21}} (\begin{array}{c} a_{22} & - a_{12} \\ - a_{21} & a_{11} \end{array}) \end{aligned}$; detはその行列の行列式を表す目印。
$a_{11} a_{22} - a_{12} a_{21} = d e t (\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix})$; ちなみに、逆行列を持つ行列は正則行列と呼ばれている。

連立一次方程式が解を持つための必要十分条件は: その係数行列が正則行列であるとき。正則行列とは行列式が0でない行列のこと。行列式が0でない行列はその逆行列を持っている。

移項: 方程式を解くための方法の1つ。方程式において等号を境とした一方の辺からもう一方の辺へとある項を移動させるとき、その項の正負の符号を反転させなくてはならない操作。項が等号を跳び越えるときにその項に-1を掛けなければいけない操作であると言い換えることもできる。
$a = - b$ $↕$ $b = - a$
左辺のaが右辺に移ると-aになり、左辺の-bが右辺に移るとbになる。右辺から左辺に移る場合も同様に正負が反転する。; 英語ではTranspositionとかTransposingと呼ばれていることがあるが、こちらの用語はもっと広い意味を持っているかもしれない。方程式の式変形に限ってみても係数を消す操作がTranspositionに含まれているかもしれない。この場合には逆演算の関係にある乗法と除法が反転する。
$\begin{aligned} a x & = b \\ x & = b \cdot \frac{1}{a} = \frac{b}{a} \end{aligned}$
つまり、この方程式の左辺のaが等号を跳び越えて右辺の末尾に移動すると、逆数のa分の1を掛ける形に変わる。

このブログを検索

MathJax

学校に通わずに学ぶログ

ブログの説明

ガウスの消去法（掃き出し法）行基本変形行簡約階段形

連立n元一次方程式とは

連立n元一次方程式を行列で表す

掃き出し法、ガウスの消去法

例題1.

R言語で連立一次方程式を解く

GNU Octaveで連立一次方程式を解く

Python3で連立一次方程式を解く

Maximaで連立一次方程式を解く

Juliaで連立一次方程式を解く

逆行列を利用した連立一次方程式の解法

例題2.

行階段形と行簡約階段形とピボット

まとめ

関連投稿

コメント

コメントを投稿

このブログの人気の投稿

LATEXで数式：指数と順列などで使う添数・添字

LibreOffice 6 Calcでフォーム（ダイアログ）を作成してマクロで表示

10の補数と9の補数と2の補数と1の補数

ブログの説明

ガウスの消去法（掃き出し法） 行基本変形 行簡約階段形

連立n元一次方程式とは

連立n元一次方程式を行列で表す

掃き出し法、ガウスの消去法

例題1.

R言語で連立一次方程式を解く

GNU Octaveで連立一次方程式を解く

Python3で連立一次方程式を解く

Maximaで連立一次方程式を解く

Juliaで連立一次方程式を解く

逆行列を利用した連立一次方程式の解法

例題2.

行階段形と行簡約階段形とピボット

まとめ

関連投稿

コメント

コメントを投稿

このブログの人気の投稿

LATEXで数式：指数と順列などで使う添数・添字

LibreOffice 6 Calcでフォーム（ダイアログ）を作成してマクロで表示

10の補数と9の補数と2の補数と1の補数

ガウスの消去法（掃き出し法）行基本変形行簡約階段形