Juliaと遊ぶ線形代数(5) ガウス・ジョルダン消去法とガウス消去法の比較

ガウス・ジョルダン消去法、ガウス消去法は、連立一次方程式を解くための手法です。

学校の試験では、多くの人が連立一次方程式を自力で計算しています。

しかし、理工系の科学計算では、数百万以上におよぶ大規模な連立一次方程式を扱う場面があります。そのような規模の問題を解くためには、必ずコンピュータを利用します。

そして、問題を効率的に解くために計算量を考慮する必要があります。

ワカメさん

この記事は「ガウス・ジョルダン消去法」と「ガウス消去法」についてまとめます。

この記事がカバーする内容
  • なぜガウス・ジョルダン消去法とガウス消去法が必要か
  • ガウス・ジョルダン消去法はどんな方法か
  • ガウス消去法はどんな方法か
  • ガウス・ジョルダン消去法とガウス消去法は何が違うか
スポンサーリンク

背景

ヒトデちゃん

なぜ「ガウス・ジョルダン消去法」や「ガウス消去法」が必要なのでしょうか?

高校で学ぶ\(A^{-1}\)を利用した逆行列法は、大規模な数値計算になると時間がかかるからです。

逆行列の計算は「クラメルの公式」を使っています。しかし、この公式の計算量は大きいです。

したがって、特別な理由がない限りは逆行列法は避けるべきと言えます。

逆行列法に比べ、ガウス・ジョルダン消去法、ガウス消去法は、効率的な計算を行う基本手法です。

ワカメさん

さらに効率的な計算手法にLU分解が登場してきますが、LU分解のコンセプトを理解するためにもガウス消去法は大事です。

ガウス・ジョルダン消去法

ガウス・ジョルダン消去法は、以下のステップから係数拡大行列の係数行列部分を単位行列に変形することで解を得ます。

ステップ:
  1. 任意の2つの行を入れ替える
  2. ある行を定数倍する
  3. ある行の定数倍を別の行に足す
ワカメさん

最大の絶対値を持つ行を選択し、行を入れ替える操作を「ピボット選択」と呼びます。

ガウス・ジョルダン消去法(Gauss-Jordan elimination)は「行列の基本変形」とも呼ばれます。

\[\left\{
\begin{array}{rcrcrc@{\qquad}l}
x_1 & + & x_2 &+& x_3= &3\\
4x_1 & + & 3x_2 &+& 2x_3= &8\\
9x_1 & + & 3x_2 &+& 4x_3= &7\\
\end{array}
\right.\]

は行列を使って

$$\begin{bmatrix}
1&1&1\\
4&3&2\\
9&3&4
\end{bmatrix}
\begin{bmatrix}
x_1\\
x_2\\
x_3
\end{bmatrix} =
\begin{bmatrix}
3\\
8\\
7
\end{bmatrix}$$

と表せます。これを拡大係数行列にします。

$$
\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
4 & 3 & 2 & 8 \\
9 & 3 & 4 & 7
\end{array}\right]
$$

ワカメさん

実際に拡大係数行列を\(\begin{bmatrix}{A|\boldsymbol{b}}
\end{bmatrix} \longmapsto
\begin{bmatrix}{E|A^{-1}\boldsymbol{b}}
\end{bmatrix}\)に変形してみます。

$$
\begin{aligned}
\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
4 & 3 & 2 & 8\\
9 & 3 & 4 & 7
\end{array}\right] &\longmapsto\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
9 & 3 & 4 & 7
\end{array}\right] \\
&\longmapsto\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
0 & 6 & 5 & 20
\end{array}\right] \\
& \longmapsto\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
0 & 0 & 7 & 4
\end{array}\right]\\
& \longmapsto\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
0 & 0 & 1 & 4/7
\end{array}\right]\\
&\longmapsto\left[\begin{array}{ccc|c}
1 & 0 & -1 & -1 \\
0 & 1 & 2 & 4 \\
0 & 0 & 1 & 4/7
\end{array}\right] \\
& \longmapsto\left[\begin{array}{ccc|c}
1 & 0 & 0 & -3/7 \\
0 & 1 & 2 & 4 \\
0 & 0 & 1 & 4/7
\end{array}\right]\\
& \longmapsto\left[\begin{array}{ccc|c}
1 & 0 & 0 & -3/7 \\
0 & 1 & 0 & 20/7 \\
0 & 0 & 1 & 4/7
\end{array}\right]
\end{aligned}
$$

単位行列に変形することで、\(\boldsymbol{x}=[-\dfrac{3}{7} \quad \dfrac{20}{7} \quad \dfrac{4}{7}]^T\)が得られました。

ガウス消去法

ガウス消去法(Gaussian elimination)は、同様のステップで拡大係数行列を行階段形(row echelon form)に変形して解を得ます。

ガウス消去法は「掃き出し法」とも呼ばれます。

eg1. 行階段系

$$\begin{bmatrix}
1&a_0&a_1\\
0&2&a_2\\
0&0&1
\end{bmatrix} \qquad
\begin{bmatrix}
1&a_0&a_1 & a_2\\
0& 0 & 1 & a_3\\
0&0&0&1\end{bmatrix}$$

拡大係数行列は

$$
\begin{aligned}
\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
4 & 3 & 2 & 8\\
9 & 3 & 4 & 7
\end{array}\right] & \longmapsto\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
9 & 3 & 4 & 7
\end{array}\right] \\
& \longmapsto\left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
0 & 6 & 5 & 20
\end{array}\right] \\
&\longmapsto \left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
0 & 0 & 7 & 4
\end{array}\right]\\
&\longmapsto \left[\begin{array}{ccc|c}
1 & 1 & 1 & 3 \\
0 & 1 & 2 & 4 \\
0 & 0 & 1 & 4/7
\end{array}\right]
\end{aligned}
$$

に変形できます。ここまでの操作を前進消去(forward elimination)といいます。

変形した拡大係数行列を連立方程式で表すと

\[\left\{
\begin{array}{rcrcrc@{\qquad}l}
x_1 & + & x_2 &+& x_3= &3\\
&& x_2 &+& 2x_3 = &4\\
&& && x_3= &4/7\\
\end{array}
\right.\]

です。これは

\[\left\{
\begin{array}{rcrcrc@{\qquad}l}
x_1 &= &3-x_2-x_3\\
x_2 &= &4 -2x_3\\
x_3 &= &4/7\\
\end{array}
\right.
\]

とおけます。\(x_3\)から\(x_1\)の順に解きます。この操作を後退代入(backward substitution)と呼びます。

\(\boldsymbol{x}=[-\dfrac{3}{7} \quad \dfrac{20}{7} \quad \dfrac{4}{7}]^T\)が得られました。

ワカメさん

ガウス消去法は、(1)前進消去で行階段形を作り、(2)後退代入で下からドミノ倒し的に解を得ます。

「ガウス・ジョルダン消去法」と「ガウス消去法」の比較

ヒトデちゃん

やってることが同じに思えるのですが、2つの方法にどんな違いがあるんでしょう?

計算量に違いがでます。係数行列のサイズを\(N \times N\)とすると、ガウス・ジョルダン消去法の計算量はおよそ\(O(N^3/2)\)、ガウス消去法の計算量はおよそ\(O(N^3/3)\)です。

したがって、ガウス・ジョルダン消去法の計算量は、ガウス消去法の計算量より大きいと予想できます。同じコンピュータで同じ問題を解いても、計算量が大きいと計算終了までに長い時間がかかります。

実際に比較してみます。(このコードはピボット選択を含んでいません)

ガウス・ジョルダン消去法とガウス消去法の計算時間

両者の計算時間を比較したところ、ガウス消去法はガウス・ジョルダン消去法より計算効率が良いと確認できました。

この結果から、(1)アルゴリズムで計算量が変わる、(2)計算量の大きさが計算時間に影響する、ことがわかりました。

まとめ

ガウス・ジョルダン消去法とガウス消去法
  • ガウス・ジョルダン消去法は、係数行列を前進消去で単位行列まで変形して解を得る
  • ガウス消去法は、拡大係数行列を前進消去で行階段系に変形し、後退代入によって解を得る
  • ガウス消去法はガウス・ジョルダン消去法より計算効率がいい
ヒトデちゃん

同じ問題を解いているのに、解き方で計算時間が変わるって面白いですね。

ワカメさん

紙の上だけではなく、コンピュータを動かしながら線形代数の勉強をしてみると、線形代数の理解が深まって良いと思います。

次回はLU分解についてまとめます。最後まで読んで頂きありがとうございました。

参考文献

(1): Treee July, “Numerical Analysis by Julia Series 1-Gauss Elimination” (6/24/2021アクセス)

(2): MIT, Gaussian-elimination, 9/23/2017

(3): 桂田 祐史, 連立1次方程式 I, — 計算量と直接法 —, 3/23/2018

スポンサーリンク

この記事が気にいったらシェアしてね!

ABOUT US

ワカメ
海外のデータサイエンスコースに留学する社会人大学院生. 専門: M.Eng. in Mat.Sci. & MSDS. このブログは以下2点を目的に運営しています.
1. 学び・体験の復習機会
2. 海外留学を目指す方の参考情報
*ブログ・SNSは所属組織と無関係の個人発信.