連立一次方程式

連立一次方程式
　　　ａ₁₁ｘ₁＋ａ₁₂ｘ₂＋・・・＋ａ_1nｘ₁＝ｂ₁
　　　ａ₂₁ｘ₁＋ａ₂₂ｘ₂＋・・・＋ａ_2nｘ_n＝ｂ₂
　　　　　：　　　：　　　　　　　：　　：
　　　ａ_n1ｘ₁＋ａ_n2ｘ₂＋・・・＋ａ_nnｘ_n＝ｂ_n
を解く代表的な方法に、ガウスの消去法があります。

数値例：連立一次方程式の解法の復習

次の連立一次方程式を例にしましょう。
　　　２ｘ＋４ｙ　　　＝１０　　・・・Ａ
　　　３ｘ＋　ｙ＋５ｚ＝２０　　・・・Ｂ
　　　　　　３ｙ＋２ｚ＝１２　　・・・Ｃ
●ステップ１
Ａを、ｘの係数２で割る。
　　　　ｘ＋２ｙ　　　＝　５　　・・・Ａ⁽¹⁾
Ｂから、Ａ⁽¹⁾にｘの係数３をかけたものを引く。
　　　３ｘ＋　ｙ＋５ｚ＝２０
　－）３ｘ＋６ｙ　　　＝１５
　　　　　－５ｙ＋５ｚ＝　５
Ｃから、Ａ⁽¹⁾にｘの係数０をかけたものを引く（実際にはＣのまま）。
　　　　　　３ｙ＋２ｚ＝１２
ここまでで、Ａ、Ｂ、Ｃは次のようになりました。
　　　　ｘ＋２ｙ　　　＝　５　　・・・Ａ⁽¹⁾
　　　　　－５ｙ＋５ｚ＝　５　　・・・Ｂ⁽¹⁾
　　　　　　３ｙ＋２ｚ＝１２　　・・・Ｃ⁽¹⁾
●ステップ２
Ｂを、ｙの係数（－５）で割る。
　　　　　　　ｙ－　ｚ＝－１　　・・・Ｂ⁽²⁾
Ａから、Ｂ⁽²⁾にｙの係数２をかけたものを引く。
　　　　ｘ　　　＋２ｚ＝　７)
Ｃから、Ｂ⁽²⁾にｙの係数３をかけたものを引く。
　　　　　　　　　５ｚ＝　５
ここまでで、Ａ、Ｂ、Ｃは次のようになりました。
　　　　ｘ　　　＋２ｚ＝　７　　・・・Ａ⁽²⁾
　　　　　　　ｙ－　ｚ＝－１　　・・・Ｂ⁽²⁾
　　　　　　　　　５ｚ＝１５　　・・・Ｃ⁽²⁾
●ステップ３
Ｃを、ｚの係数５で割る。
　　　　　　　　　　ｚ＝　３　　・・・Ｃ⁽³⁾
Ａから、Ｃ⁽²⁾にｚの係数２をかけたものを引く。
　　　　ｘ　　　　　　＝　１
Ｂから、Ｃ⁽²⁾にｚの係数（－１）をかけたものを引く。
　　　　ｘ　　　　　　＝　１
　　　　　　　ｙ　　　＝　２
この結果、次の解が得られました。
　　　　ｘ　　　　　　＝　１　　・・・Ａ⁽³⁾
　　　　　　　ｙ　　　＝　２　　・・・Ｂ⁽³⁾
　　　　　　　　　　ｚ＝　３　　・・・Ｃ⁽³⁾

ｘをｘ₁、ｙをｘ₂、ｚを₃とし、Ａを式１、Ｂを式２、Ｃを式３と番号をつければ、ステップｉで、変数ｉ、式ｉが特別な処理になっていることに注意してください。

計算表による整理

上の計算は、次の表にまとめることができます。

　　　　　─────────────
　　　　　　１　　２　　３　　　４
　　　　　　ｘ　　ｙ　　ｚ　　　ｂ
ステップ０─────────────
　　１　　　２　　４　　０　　１０
　　２　　　３　　１　　５　　２０
　　３　　　０　　３　　２　　１２
ステップ１─────────────
　　１　　　１　　２　　０　　　５
　　２　　　０　－５　　５　　　５
　　３　　　０　　３　　２　　１２
ステップ２─────────────
　　１　　　１　　０　　２　　　７
　　２　　　０　　１　－１　　－１
　　３　　　０　　０　　５　　１５
ステップ３─────────────
　　１　　　１　　０　　０　　　１
　　２　　　０　　１　　０　　　２
　　３　　　０　　０　　１　　　３
　　　　　─────────────

アルゴリズム

例えば、ステップ１の表は、次の式で計算できます。
ステップ１の値　　　ステップ０の値
（１,１）の　１：(1,1)/(1,1)＝２／２＝１
（１,２）の　２：(1,2)/(1,1)＝４／２＝２
（１,３）の　０：(1,3)/(1,1)＝０／２＝０
（１,４）の１０：(1,4)/(1,1)＝１０／２＝５
（２,１）の　０：(2,1)-(2,1)*(1,1)/(1,1)＝　３－３×２／２＝　０
（２,２）の－５：(2,2)-(2,1)*(1,2)/(1,1)＝　１－３×４／２＝－５
（２,３）の　５：(2,3)-(2,1)*(1,3)/(1,1)＝　５－３×０／２＝　５
（２,４）の　５：(2,4)-(2,1)*(1,4)/(1,1)＝２０－３×１０／２＝　５
（３,１）の　０：(3,1)-(3,1)*(1,1)/(1,1)＝　０－０×２／２＝　０
（３,２）の　０：(3,2)-(3,1)*(1,2)/(1,1)＝　３－０×４／２＝　３
（３,３）の　５：(3,3)-(3,1)*(1,3)/(1,1)＝　２－０×０／２＝　２
（３,４）の１２：(3,4)-(3,1)*(1,4)/(1,1)＝１２－０×１０／２＝１２
ステップ３の値は、ステップ２の値を用いて同様に計算できます。

この関係を一般化すれば、ステップｋからステップｋ＋１への変化は、
　　　ａ_ij＝ａ_ij/ａ_kk　　　　　　　（ｉ＝ｋのとき）
　　　　　＝ａ_ij－ａ_ik×ａ_kj/ａ_kk　（ｉ≠ｋのとき）
と表現できます。
　なお、この ａ_kk をピボットといいます。

上記のアルゴリズムは、次の問題では、ピボット（対角線の要素）が０になり計算できません。
　　　　　　３ｙ＋２ｚ＝１２
　　　２ｘ＋４ｙ　　　＝１０
　　　３ｘ＋　ｙ＋５ｚ＝２０
ピボットが０でなくても、
　　　εｘ＋３ｙ＋２ｚ＝１２　　　ε＝０.０００００１
　　　２ｘ＋４ｙ　　　＝１０
　　　３ｘ＋　ｙ＋５ｚ＝２０
のような場合には、誤差が生じてしまいます。

それを避けるために、ステップのたびに、ピボットになる変数の絶対値が最大になるように、式の順序を入れ替えることが必要になります。

計算プログラム