連立1次方程式の解法として中学時代に教わるのは代入法と加減法という2つの消去法である。複数ある未知数のどれか一つを消去し,未知数が一つ少ない連立方程式を得て,それらからさらに一つ未知数を消去する,という操作を繰り返し,最終的には未知数が一つの,直ちに解ける1次方程式へと問題を同値変形していく手法である。
中学校で習う加減法は2つの方程式をそれぞれ何倍かしたもの同士を足したり引いたりする操作を許すが,主に大学で習う掃出し法で許される基本変形(基本操作)はそれに比べると「ローテク」であり,対応する操作は「ある行に,他の行の何倍かを足し合わせる」というものに限られる。
しかも,分数を避けるため,割り算をなるべく用いないようにという余計な制約をつけると,割り算以外の演算,つまり足す・引く・掛けるの組み合わせで割り算の代用をすることになり,いささか冗長かつ見通しの悪い計算が要求されることがある。また,どの行からどの行を引くのかといった引き算の順序を正しく把握していないと計算結果がおかしくなるが,暗算でその計算を処理することが苦手な人がいる。
というわけで,掃き出し法を学ぶとなぜかそれまで苦も無く解いていた2元連立1次方程式ですらまともに解けなくなる者が現れる。したがって,掃き出し法を身に付けさせるのは案外至難の業だと思われる。もっとも,分数の計算さえ厭わなければ非常に見通しの良い式変形が可能なのだが,手計算で分数の足し算・引き算を多くこなすのは困難なので,それはそれで難しいと思われる。
ところで,基本変形としてよく挙げられるのは
(1) ある行を何倍かする;
(2) ある行に他の行の何倍かを加える;
(3) ある行と他の行を入れ替える
の3種類であるが,(3) の操作は (1) と (2) の組み合わせで実現されることが知られている。また,この基本変形は結局のところ(拡大係数)行列の行ベクトルの1次結合を生み出す操作に他ならないので,ベクトルに関する基本演算である
(a) ある行を何倍かする(スカラー乗法);
(b) ある行に他の行を加える(加法)
の2つで代用が可能である。ただ,これは先に挙げた (1),(2),(3) のセットに比べるとより一層ローテク度が増している。実際,操作 (2) は,操作 (a),(b) を
(a) 第 j 行を r 倍する;
(b) 第 i 行に(r 倍された)第 j 行を加える;
(a) 第 j 行を 1/r 倍する
のように組み合わせた複合技でもってようやく実現されることになる。第 j 行のデータをリセットしてデフォルトの状態に戻すという手間が余分にかかってしまう。
とはいえ,分数の使用を最初から認めればこの (a) と (b) のセットで十分である。
ちなみに,代入に対応する基本変形は何だろうかと最近ようやく気になったのだが,実は次のように考えると,それは加減法の一種だとみなせるのである。
2x+3y=1
に,x=-4 を代入すると,
2(-4)+3y=1
を経て 3y=1-(-8)=9 と変形できるが,これは x=-4 の両辺を2倍した 2x=-8 を 2x+3y=1 から引いて得られる式でもある。つまり,
2x+3y=1
x=-4
において,第1式から,第2式の2倍を引くことが,第1式の x に第2式の右辺の値を代入し,その結果新たに現れる定数項を右辺に移項するところまでの操作に相当するわけである。
何ということはない話であるが,これでようやく中学校で習ったテクニックと基本変形という大学で習ったテクニックとのつながりがはっきりした気がして,自分としては理解が深まったように思う。
なお,基本変形 (1),(2),(3) を用いた場合,n元連立1次方程式は多くとも何回基本変形を施せば解けるのかという演算回数の見積もりは次のようになる。
まず (1,1) 成分を要として第1列を掃き出すためには,
<場合その壱>
(1,1) 成分が 0 でないならば,(1,1) 成分で第1行を割り,その結果をそれぞれ何倍かしたものを残りの (n-1) 行から引いて第 1 列を掃き出す必要がある。これは操作 (1) を1回,操作 (2) を (n-1) 回,つまり基本変形を合計 n 回要する。
<場合その弐>
(1,1) 成分,(2,1) 成分,・・・,(i-1,1) 成分がすべて 0 で,(i,1) 成分は 0 でないとき,第1行と第i行を入れ替え,
(必要があればそうして入れ替えた後の)第 1 行を (1,1) 成分の値で割り,
(必要があればそうして割った後の)第 1 行を何倍かし,それを他の行から引くことで,その第 1 列の成分を 0 にする
という操作が必要であるが,少なくとも元の第 1 行の先頭の数値は 0 であるから,その行から引く操作は不要である。
したがって,多くとも
操作 (3) が 1 回,
操作 (1) が 1 回,
操作 (2) が (n-2) 回
となり,第 1 列を掃き出すのに合計でやはり高々 n 回の基本変形を要することになる。
第 1 列を掃き出した後には未知数が (n-1) 個の連立方程式が得られるから,第 2 列は多くとも (n-1) 回の基本変形で掃き出しが完了する。
この操作は,操作後の方程式が1つになるまで続けなければならないから,高々
n+(n-1)+...+2=(n-1)(n+2)/2 回
の操作が必要になる。
そして,必要ならば最後に得られた未知数が1つの方程式の両辺をその係数で割るという操作 (1) が必要になる。その結果得られた値を,他の (n-1) 個の方程式に代入してその未知数を消去しなければならない。
そうすると,もう1つの未知数の値が確定するので,それを残りの (n-2) 個の方程式に代入して未知数を消去しなければならない。
これらの代入操作は,操作 (1) を 1 回と,操作 (2) を合計
(n-1)+(n-2)+・・・+1=n(n-1)/2 回
必要とするので,最終的に,高々
(n-1)(n+2)/2+1+n(n-1)/2=n2回
の基本変形が必要になることになりそうである。
なお,この公式を n=2 のときに当てはめてみると,最悪でも 4 回の基本変形で問題が解けるという見積もりになる。また,未知数が3つのときは 9 回の基本変形を施せば必ず答えに到達できるはずということになる。
掃き出し法で連立方程式を解くという課題に取り組む際には,このような見積もりを念頭においておくとやりやすいかもしれない。