2026-08-27·★ 会員·16分で読めます

連立方程式の解き方 — 直接法と反復法

橋のたわみも部屋の温度もガウス過程回帰も、計算機にやらせる段では Ax=b という同じ形に化けます。消していく直接法（LU）と近づいていく反復法（共役勾配法）を、なぜ100万元の方程式が消去法で解けないのかから始めて、条件数・前処理・matrix-free まで前提知識ゼロでつなぎます。

#numerical-methods #linear-algebra #conjugate-gradient #preconditioning #sparse-matrix #algorithm

対象textタスクalgorithm

未知の量を、関係の網から逆算する

橋がどれだけたわむか。部屋の温度がどう分布するか。回路の各点の電圧がいくつになるか。分野はばらばらですが、計算機にやらせる段になると、これらは全部おなじ形の問題に化けます。

$Ax = b$

$A$ は「量どうしがどう関係しているか」を並べた表（行列）、 $b$ は外から与えられた条件、 $x$ が知りたい未知の量です。要するに、仕組み $A$ と結果 $b$ が分かっているときに、原因 $x$ を逆算する問題です。

中学で習った連立方程式と、やっていること自体は変わりません。違うのは規模だけです。学校の問題は未知数が2つか3つで、代入と消去で手が届きます。ところが橋を細かく分割すれば未知数は数万個、3次元の流体なら数百万個になります。同じ「消去」を数百万個の未知数に対してやったとき何が起きるのか — ここから先が数値計算の世界です。

そしてこれは機械学習と無縁の話ではありません。最小二乗法、ガウス過程回帰、ニュートン法的な二次最適化。どれも中心には $Ax=b$ が座っています。後半で、シミュレーションの道具とMLの道具がどこで分かれるのかを見ます。

二つの流儀 — 消していくか、近づいていくか

直接法（direct method） は、決まった手順を有限回こなせば答えが出る流儀です。中学の消去法をそのまま大規模化したもので、代表格がガウス消去法と、その手順を保存したLU分解。丸め誤差を別にすれば、出てくるのは厳密解です。

反復法（iterative method） は、適当な当てずっぽう $x_0$ から始めて少しずつ真の解へ近づける流儀です。カメラのピント合わせに似ていて、回すたびに像がくっきりしていき、「もう十分」と思ったところで手を止められます。

この二つは性格が決定的に違います。直接法は途中で止めても何も得られません。半分だけ消去された行列は、解でも解の近似でもない中間状態です。対して反復法は、いつ止めてもその時点の答えを持っています。精度と計算時間を後からダイヤルで選べるわけです。

シミュレーションの離散化誤差が3桁目にあるのに方程式だけ15桁まで解いても意味がない — この「要らない精度は買わない」という発想が、反復法が現場を席巻した理由のひとつです。

直感 — 「解く」ことは「谷底を探す」ことと同じ

反復法に入る前に、絵を1枚持っておくと後が楽になります。

$A$ が対称（ $a_{ij}=a_{ji}$ ）かつ正定値（ゼロでないどんな $v$ でも $v^\top A v > 0$ ）のとき、次の関数を考えます。

f(x) = \tfrac{1}{2}\,x^\top A x - b^\top x

(1)

$x^\top A x$ は $x$ の成分どうしの積を $A$ の重みで足したもの、 $b^\top x$ は $b$ と $x$ の内積です。変数が2つならこの $f$ は「お椀」の形になります。

大事なのはここです。 $f$ の勾配（傾き）は $\nabla f(x) = Ax - b$ で、傾きがゼロになる点＝お椀の底が、そのまま $Ax=b$ の解です。つまり対称正定値の連立方程式を解くことと、お椀の底を探すことは同じ作業で、最適化の道具箱がそっくり使えます。

ただしお椀はきれいな円形とは限りません。 $A$ の固有値がばらつくとお椀は細長い谷にひしゃげ、最急降下法（いま一番急な下り方向へ一歩進む）はひどく効率が落ちます。斜面がほぼ真横を向くので「一番急な下り」は谷を横切る方向になり、進むべき谷底沿いにはなかなか進めないのです。

FIG 1等高線が細長いほど、最急降下（モーメンタム0）は壁から壁へジグザグして進まなくなる。この「谷の細長さ」が、あとで出てくる条件数の正体です

このジグザグこそ、後で出てくる共役勾配法が退治する相手です。最適化そのものの一般論は凸性と最適化で扱っています。

直接法 — ガウス消去とLU分解

ガウス消去法は「1本目の式で2本目以降から $x_1$ を消す。次に2本目で3本目以降から $x_2$ を消す」を繰り返して三角形にし、下から順に代入して解きます。この消去手順を $A = LU$ （下三角×上三角）という形で保存しておくのがLU分解です。こうしておくと、同じ $A$ で右辺 $b$ だけ違う問題を何度も解くときに効きます。分解1回は $n$ の3乗に比例する仕事ですが、その後の代入は2乗で済むからです。 $A$ が対称正定値なら $A = LL^\top$ （コレスキー分解）が使え、仕事量はおよそ半分です。使い分けは行列分解ツアーにまとめました。

ここで実務の鉄則を一つ。逆行列を作ってはいけません。紙の上では $x = A^{-1}b$ と書きますが、計算機で $A^{-1}$ を明示的に作るのは余計に高価で、しかも精度が落ちます。使うのは常に「解く」関数（NumPyなら np.linalg.solve）です。

疎行列という現実、そして fill-in

シミュレーションから出てくる $A$ には際立った特徴があります。ほとんどの要素がゼロなのです。格子点の温度は隣としか直接関係しないので、1行あたりの非ゼロは5個や7個程度に留まります。

100万×100万を全部並べれば1兆個、倍精度で8テラバイトになり載りません。しかし非ゼロが1行7個なら700万個で、位置情報を含めても数百メガバイトです。密に持てば絶望的、疎に持てばノートPCに載る。だから疎行列専用の格納形式が使われます。

問題はここからです。疎行列に消去を進めると、もともとゼロだった場所に非ゼロが生まれます。ある行から別の行を引いた結果、空だったマスが埋まる。これを fill-in と呼びます。fill-in が進むと疎構造が壊れ、メモリも計算量も膨れ上がります。

対策として消去の順番を並べ替える手法（AMD、nested dissection など）が発達し、2次元問題ならこれでかなり戦えます。しかし3次元ではどう並べ替えても fill-in が支配的になり、直接法はメモリの壁にぶつかります。反復法は $A$ を一切書き換えません。使うのは「 $A$ とベクトルを掛ける」操作だけなので、疎構造は最初から最後まで無傷です。ここが分かれ道になります。