本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
ガウスの消去法の計算量
ガウスの消去法の計算量は$O(n^{3})$である。
前進消去と後退消去の計算量に分けて求める点がポイントです。
証明
対象とする連立一次方程式を$A\vx=\vb$とおきます。前進消去では，係数行列$A$の第$k$行より下を掃き出すために
- 第$k$行から第$k+1$行以下に対する倍率比較：$n-k$回の割り算
- 第$k$行から第$k+1$行以下に対する正規化：$(n-k)^{2}$回の掛け算
- 第$k$行から第$k+1$行以下に対する加算：$(n-k)^{2}$回の足し算
を行う必要があります。加えて，$\vb$に対しても
- 第$k$行から第$k+1$行以下に対する正規化：$n-k$回の掛け算
- 第$k$行から第$k+1$行以下に対する加算：$n-k$回の足し算
を行う必要があります。したがって，前進消去の計算回数は
\begin{align}
\sum_{k=1}^{n-1}\left\{(n-k)+2(n-k)^{2}+2(n-k)\right\}
&= \sum_{l=1}^{n-1}\left\{l+2l^{2}+2l\right\} \\[0.7em]
&= \frac{1}{2}n(n+1)+\frac{1}{3}(n-1)n(2n-1)+n(n-1) \\[0.7em]
&= \frac{1}{6}n(n-1)(4n+7)
\end{align}
\sum_{k=1}^{n-1}\left\{(n-k)+2(n-k)^{2}+2(n-k)\right\}
&= \sum_{l=1}^{n-1}\left\{l+2l^{2}+2l\right\} \\[0.7em]
&= \frac{1}{2}n(n+1)+\frac{1}{3}(n-1)n(2n-1)+n(n-1) \\[0.7em]
&= \frac{1}{6}n(n-1)(4n+7)
\end{align}
と求められます。後退消去では，第$k$行より上を掃き出すために
- 第$k$行から第$k-1$行以上に対する倍率比較：$1$回の割り算
- 第$k$行から第$k-1$行に対する正規化：$k-1$回の掛け算
- 第$k$行から第$k-1$行に対する加算：$k-1$回の足し算
を行う必要があります。したがって，後退消去の計算回数は
\begin{align}
\sum_{k=1}^{n}\left\{1+2(k-1)\right\}
&= n + \frac{2}{2}n(n-1) = n^{2}
\end{align}
\sum_{k=1}^{n}\left\{1+2(k-1)\right\}
&= n + \frac{2}{2}n(n-1) = n^{2}
\end{align}
と求められます。したがって，ガウスの消去法の計算量は，オーダー記法を用いて
\begin{align}
O\left(\frac{1}{6}n(n-1)(4n+7)+n^{2}\right) &= O(n^{3})
\end{align}
O\left(\frac{1}{6}n(n-1)(4n+7)+n^{2}\right) &= O(n^{3})
\end{align}
と表されます。
コメント