線形代数 · 第4回 · 動画3 · インタラクティブ教材

ガウスの消去法の計算量 ― ⅓n³ はどこから来るのか

I重要な公式

公式	名称	説明
$1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$	二乗の和	消去法の総コストを与える正確な公式
$\text{消去法} \approx \tfrac{1}{3}n^3$	ガウスの消去法の計算量	前進消去のおおよそのフロップ数
$\text{右辺ひとつあたり} \approx n^2$	三角行列の求解の計算量	前進代入（ $\tfrac{1}{2}n^2$ ）+ 後退代入（ $\tfrac{1}{2}n^2$ ）
$\text{LU の合計} = \tfrac{1}{3}n^3 + m \cdot n^2$	右辺が $m$ 個のときの LU 分解	分解は一度、解くのは $m$ 回

II可視化1 — ⅓n³ はどこから来るのか

各ステップのコスト $k^2$ を積み重ねると $x^2$ の下の面積になるので、合計はおよそ $\tfrac{1}{3}n^3$ です。

行列のサイズ n 8

III可視化2 — 縮んでいく作業中のブロック

消去の各ステップは、縮んでいく作業中のブロックだけを扱うので、そのコストは $(n{-}k)^2$ のように減っていきます。

ステップ k 0

IV可視化3 — 分解は一度、解くのは何度でも

$\tfrac{1}{3}n^3$ をかけて一度だけ分解すれば、 $m$ 回の求解はそれぞれ $n^2$ で済みます。毎回消去をやり直す場合と比べて、どれだけ得になるでしょうか。

行列のサイズ n 1,000 右辺の個数 m 100

💡 $m = 1$ では二つの方針のコストはほぼ同じです（分解することが、そのまま消去法だからです）。しかし右辺が一つ増えるごとに LU 分解が有利になり、その効果は $n/3$ に向かって大きくなっていきます。だからこそ数値計算ライブラリは、分解を一度だけ行い、どの右辺にも $L$ と $U$ を使い回すのです。

V確認クイズ

問1

$n = 100$ の行列があります。ガウスの消去法（前進消去のみ）のフロップ数はおよそいくつですか。

✅ 正解です！ ガウスの消去法にはおよそ ⅓n³ フロップかかります。これは二乗の和 n² + (n−1)² + ⋯ + 1² から来ています。

❌ 惜しい！ 思い出しましょう：総コストは二乗の和 1² + 2² + ⋯ + n² で、これはおよそ ⅓n³ に等しくなります。

解答を見る

解答：

ガウスの消去法のコストは、およそ $\tfrac{1}{3}n^3$ フロップです。

$n = 100$ のとき： $\frac{1}{3} \times 100^3 = \frac{1{,}000{,}000}{3} \approx 333{,}333$

正確な和は $1^2 + 2^2 + \cdots + 100^2 = \frac{100 \times 101 \times 201}{6} = 338{,}350$ で、近似値 $\tfrac{1}{3}n^3$ との差は 2% 以内です。

$n^2 / 2 = 5{,}000$ — これは消去法全体ではなく、三角行列の求解1回分のコストです。
$n^2 = 10{,}000$ — これは分解したあとの、右辺ひとつあたりのコストです。
$n^3 = 1{,}000{,}000$ — 3倍大きすぎます。

問2

正しいか誤りか：LU 分解を保存してあれば、右辺が1つ増えるごとに、解くのにおよそ $\tfrac{1}{3}n^3$ フロップかかる。

✅ 正解です！ 右辺が1つ増えるごとのコストは ⅓n³ ではなく、およそ n²（三角行列の求解2回）にすぎません。これこそが LU 分解の利点です！

❌ 惜しい！ L と U がすでに計算済みなら、残る仕事は何かを考えましょう。必要なのは前進代入と後退代入だけです。

解答を見る

解答：誤り

$L$ と $U$ を保存してあれば、どの右辺も三角行列の求解2回だけで解けます。

前進代入（ $Lc = b$ ）： $k$ 行目には $k{-}1$ 回の演算が必要 → 合計 $\approx \tfrac{1}{2}n^2$
後退代入（ $Ux = c$ ）： $k$ 行目には $k{-}1$ 回の演算が必要 → 合計 $\approx \tfrac{1}{2}n^2$

右辺ひとつあたりの合計コスト $= \tfrac{1}{2}n^2 + \tfrac{1}{2}n^2 = n^2$ です。 $\tfrac{1}{3}n^3$ ではありません。

これこそが LU 分解の要点です。高くつく $\tfrac{1}{3}n^3$ の仕事は、分解のときに一度だけ行います。そのあとの求解は、どれも $n^2$ だけで済み、はるかに安上がりです。

問3

$1000 \times 1000$ の連立方程式に、異なる右辺が100個あります。素朴なガウスの消去法を100回別々に実行する場合と比べて、LU 分解ではおよそ何倍速くなりますか。

ヒント： 素朴なやり方のコスト $= 100 \times \tfrac{1}{3}n^3$ 。LU 分解のコスト $= \tfrac{1}{3}n^3 + 100 \times n^2$ 。

✅ 正解です！ LU 分解は、99回の余分な消去を省くことで、約77倍の節約になります。右辺を増やしていくと、速度向上は n/3 = 333 に近づきます。

❌ 惜しい！ 両方のコストを実際に計算してみましょう：素朴なやり方 = 100 × ⅓ × 10⁹、LU 分解 = ⅓ × 10⁹ + 100 × 10⁶ を求めてから、割り算します。

解答を見る

解答：

$n = 1000$ 、 $m = 100$ のとき：

素朴なやり方： $100 \times \tfrac{1}{3}(1000)^3 = 100 \times 333{,}000{,}000 = 33{,}300{,}000{,}000 \approx 33.3 \text{ 十億フロップ（約333億フロップ）}$

LU 分解を使うやり方： $\underbrace{\tfrac{1}{3}(1000)^3}_{333{,}000{,}000} + \underbrace{100 \times (1000)^2}_{100{,}000{,}000} = 433{,}000{,}000 \approx 433 \text{ 百万フロップ（4億3300万フロップ）}$

速度向上： $\frac{33{,}300{,}000{,}000}{433{,}000{,}000} \approx 76.9 \approx \mathbf{77\times}$

答えは同じで、仕事量は 1/77 です！

なぜ333倍ではないのでしょうか。LU 分解を使うやり方でも、最初の分解に ⅓n³ かかるからです。速度向上が $n/3 = 333$ に近づくのは、 $m \to \infty$ のときだけです。

問4

$5 \times 5$ 行列では、消去法はステップ $k = 0, 1, 2, 3, 4$ と進みます。ステップ $k$ で、まだ作業が残っている小行列のサイズは $(5{-}k) \times (5{-}k)$ です。2番目の消去のステップ（ $k = 1$ ）のコストはいくつですか。

✅ 正解です！ ステップ k=0 で1行目と1列目の消去が終わると、作業する領域は 4×4 になり、コストは (5−1)² = 16 フロップです。

❌ 惜しい！ ステップ k=1 では、すでに1行と1列の消去が終わっています。まだ作業が残っている小行列のサイズは (n−k) = (5−1) = 4 です。

解答を見る

解答：

$5 \times 5$ 行列（ $n = 5$ ）の各ステップのコスト：

ステップ $k$	作業中のサイズ	コスト
$k = 0$ （1番目）	$5 \times 5$	$5^2 = 25$
$k = 1$ （2番目）	$4 \times 4$	$4^2 = 16$
$k = 2$ （3番目）	$3 \times 3$	$3^2 = 9$
$k = 3$ （4番目）	$2 \times 2$	$2^2 = 4$
$k = 4$ （5番目）	$1 \times 1$	$1^2 = 1$

ステップ $k = 1$ では1行目と1列目の消去が終わっていて、まだ作業が残っている小行列は $(5{-}1) \times (5{-}1) = 4 \times 4$ です。コストは $4^2 = \mathbf{16}$ フロップです。

検算：合計 $= 25 + 16 + 9 + 4 + 1 = 55 = \frac{5 \times 6 \times 11}{6}$ ✓

正解数：0 / 4