などその他多くの場合に連立1次方程式を解く問題へ帰着して近似解を求める方法が考えられている.このように,数値計算において連立1次方程式を解くことや行列計算が非常に重要. 最近のコンピュータの発達によって時間的 or 経済的にも可能になった.
n次元連立1次方程式
\begin{eqnarray} \left\{ \begin{array}{l} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1\\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2\\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n = b_n\\ \end{array} \right. \end{eqnarray}$$ \mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{pmatrix}, \vec{x} = \begin{pmatrix} x_{1}\\ x_{2}\\ \vdots \\ x_{n} \\ \end{pmatrix}, \vec{b}= \begin{pmatrix} b_{1}\\ b_{2}\\ \vdots \\ b_{n}\\ \end{pmatrix} $$とおけば,
\begin{eqnarray} \mathbf{A}\vec{x} = \vec{b} \end{eqnarray}$\mathbf{A}$が正則ならば,連立方程式の解は,
\begin{eqnarray} \vec{x} = \mathbf{A}^{-1} \vec{b} \end{eqnarray}クラメールの公式(G.Cramer)で表すと,
\begin{eqnarray} x_j = \frac{|\mathbf{A}_j|}{|\mathbf{A}|}, (j=1,2,\cdots , n) \end{eqnarray}連立方程式の解法として数学的に完全. しかし,計算を考えると,
行列式の計算回数
$$ |\mathbf{A}| = \text{sign}(\epsilon) \sum_{\epsilon}a_{1\epsilon(1)}a_{2\epsilon(2)}a_{3\epsilon(3)}\cdots a_{n\epsilon(n)}\\ $$$\text{sign}(\epsilon) = \left\{ \begin{array}{l} +1, (\text{偶順列} ) \\ -1,(\text{奇順列} ) \\ \end{array} \right. $
行列式の乗算回数は,
より,$(n-1) n!$ 回
よって,以上より,n元連立1次方程式の解をクラメールの公式で求めると,乗除算回数は,
\begin{eqnarray} C(n) = (n+1)(n-1)n! + n \end{eqnarray}ex. 20元連立1次方程式の場合:
$$ C(20) = 21 \cdot 19 \cdot 20! + 20 = 9.7 \times 10^{20} \text{回} $$import scipy as sp
C = lambda n: (n + 1) * (n - 1) * sp.math.factorial(n) + n
C(20)
970727901262479360020
計算量は,
$$ O( (n+1)(n-1)n! + n) = O(n^2 n!) $$$n$元を$1 - 50$まで変えて乗除算回数を計算してグラフを書く.
import scipy as sp
import matplotlib.pyplot as plt
%matplotlib inline
n = sp.arange(1, 50+1)
C_sp = (n+1) * (n-1) * sp.special.factorial(n) + n
plt.plot(n, C_sp)
plt.xlabel("$n$")
plt.yscale("log")
plt.yticks(10.**sp.arange(0, 70+5, 5))
plt.ylabel("$C(n)$(log-scale)[num]")
plt.grid(True)
plt.show()
$10^{12}$FLOPS(=Floating point Operations Per Second) 1秒間に処理される浮動小数点演算の回数コンピュータの回数)のコンピュータで20元連立1次方程式を解くと,
$$ C(20) = 9.7 \times 10^{20} $$1秒間に$10^{12}$回処理することより,
$$ C(20) / 10^{12} [\text{ s}] $$年換算すると,
$$ C(20) / ( 10^{12} \cdot 3600 \cdot 24 \cdot 365 ) = 30.8[\text{年}] $$30年以上かかかる.
C(20) / (10**12 * 3600 * 24 * 365)
30.781579821869588
import scipy as sp
import matplotlib.pyplot as plt
%matplotlib inline
n = sp.arange(1, 50+1)
C_sp = (n+1) * (n-1) * sp.special.factorial(n) + n
plt.plot(n, C_sp/(10**12 * 3600 * 24 * 365))
plt.xlabel("$n$")
plt.yscale("log")
plt.yticks(10.**sp.arange(-15, 50+5, 5))
plt.ylabel("$C(n)$(when $10^{12}$FLOPS)(log-scale)[year]")
plt.grid(True)
plt.show()
50元連立一次方程式では,$10^{48}$年かかる!
したがって,クラメールの公式は,数学的解法としては明快で完全だが, コンピュータを使う数値計算法としては何らかの工夫が必要となる.
ただし,このクラメールの公式のケースでは行列式の計算量がネックになっているので,その計算量を落とせれば使えるかもしれない. こちらの記事では,行列式の計算量を三角行列を使って$O(n^3)$にしている.
ほかの方法では,
がある.