1 連立方程式

1.1 表現方法

言うまでも無く連立1次方程式(Linear Equations)は、次のような形をしている。

$$\begin{aligned}a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1N}x_N&=... ...a_{M1}x_1+a_{M2}x_2+a_{M3}x_3+\cdots+a_{MN}x_N&=b_M \end{aligned}$$

ここでは、$M=N$の場合を考える。$M \ne N$のようなものは、ここでの講義 のレベルを超えるので、興味がある人は自分で学習すること。このよう な連立1次方程式を計算することは、実際に工学の問題でしばしば現れる。例えば、 編微分方程式を離散化して解く場合などである。その場合、方程式の次元数がか なり大きく、100万元くらいは普通である。100万といっても、3次元 問題だと、 $100 \times 100 \times 100$程度であるので、まだまだ精度は荒い。　　　　　　　　　　　

式(1)は行列とベクトルで書くと、式がすっきりして 考えやすくなる。書き直すと、

$$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$$ (2)

となるのは、以前学習したとおりである。それぞれの行列とベクトルは、

$$\begin{aligned}\boldsymbol{A}&= \begin{pmatrix}a_{11} & a_{12} ... ...rix}b_1 \\ b_2 \\ b_3 \\ \vdots\\ b_N \end{pmatrix} \end{aligned}$$

を表す。行列は大文字の太文字(bold)スタイル、ベクトルは小文字 の太文字スタイル、それぞれの成分は標準スタイルで表されることが多い。

ここで、解く問題は行列 $\boldsymbol{A}$が $N \times N$の正方行列で、その行列式が ゼロでないものとする。要するに、普通に解ける連立方程式である。ここで、 解くべき問題は、既知の $\boldsymbol{A}$と $\boldsymbol{b}$から、行列方程式()を満たす、 $\boldsymbol{x}$を求めることになる。この行列方 程式解く過程で、 $\boldsymbol{A}$の逆行列や行列式の値を求めることができる。逆 行列や行列式は連立方程式と密接にかかわっているのである。

通常、連立1次方程式(1)は

$$\begin{aligned}\begin{pmatrix}a_{11} & a_{12} & a_{13} & \cdots... ...rix}b_1 \\ b_2 \\ b_3 \\ \vdots\\ b_N \end{pmatrix} \end{aligned}$$

と書き表せる。このようにすると、見通しがかなり良くなる。皆さんも、 今後連立方程式を書くときは、行列とベクトルで書く方が良いであろう。 ちょっとばかり格好良い。

行列やベクトルを使うと、格好良いばかりでなくコンピューターで扱いやすく なる。例えば、行列 $\boldsymbol{A}$の要素$a_{ij}$はプログラム中では2次元配 列a[i][j]として扱える。同様にベクトル$b_k$は1次元配列 b[k]として扱える。

1.2 計算方法

連立1次方程式は、クラメールの公式により、解のベクトル $\boldsymbol{x}$は四則演 算で計算できる。行列 $\boldsymbol{A}$が正則 $(\det A \neq 0)$ならば、解は

$$x_j =\frac{1}{\det A} \begin{vmatrix}a_{11} & a_{12} & a_{13} & \cdot... ... a_{N3} & \cdots & a_{1j-1} & b_{1j} & a_{1j+1} & \cdots & a_{NN} \end{vmatrix}$$ (5)

である。これは、2つの行列式を計算する必要があり、計算量 が大変多くなる。したがって、$N \geq 4$の場合は推奨できない。

次に考えられるのは、 $\boldsymbol{A}$の逆行列 $\boldsymbol{A}^{-1}$を用いて、 $\boldsymbol{x}=\boldsymbol{A}^{-1}\boldsymbol{b}$から計算する方法である。この方法も、計算量と精 度の面で問題がある。

連立1次方程式の計算方法は大別して、2通りある。１つは、ここで学習す る消去法で、他方は反復法と言われる方法である。どちらが良いかは、係数行列 $\boldsymbol{A}$の性質に依存する。一般に、 $\boldsymbol{A}$が密なとき、即ちほとんどの要 素がゼロでないときは、消去法が有利である。一方、殆どの要素が ゼロで、 $\boldsymbol{A}$が疎のとき、反復法が有利である。

ここでは消去法を学習するが、反復法について簡単に紹介しておく。まず、 係数行列を $\boldsymbol{A}=\boldsymbol{B}-\boldsymbol{C}$と変形します。すると、元の連立1次方程 式は、 $\boldsymbol{B}\boldsymbol{x}=\boldsymbol{C}\boldsymbol{x}+\boldsymbol{b}$となる。これを解くために、 漸化式 $\boldsymbol{B}\boldsymbol{x}^{(k+1)}=\boldsymbol{C}\boldsymbol{x}^{(k)}+\boldsymbol{b}$とする。もし、 初期値 $\boldsymbol{x}^{(0)}$が良ければ、 $\boldsymbol{x}^{(\infty)}$は真の解 $\boldsymbol{x}$に 収束する。もちろん、 $\boldsymbol{B}$は容易に計算できる連立1次方程式になるよ うに選ぶ。この選び方により、ヤコビの反復法やガウス・ザイデル法、 SOR法などがある。

ホームページ: Yamamoto's laboratory
著者: 山本昌志