メインコンテンツまでスキップ

連立一次方程式の解法

連立一次方程式の解き方​

次のような連立一次方程式は、以下のようにして解くと思います。

{x1−2x2+3x3=3(1)−x1+3x2−2x3=1(2)x1−x2+6x3=11(3)\left\{ \begin{alignedat}{3.5} & x_1 - {} & 2 & x_2 + {} & 3 & x_3 = 3 & \quad (1)\\ -& x_1 + {} & 3 & x_2 - {} & 2 & x_3 = 1 & \quad (2)\\ & x_1 - {} & & x_2 + {} & 6 & x_3 = 11 & \quad (3) \end{alignedat} \right.

(1)+(2)(1) + (2) より、

x2+x3=4(4)x_2 + x_3 = 4 \quad (4)

(2)+(3)(2) + (3) より、

x2+4x3=12∴x2+2x3=6(5)\begin{alignedat} 2x_2 + 4x_3 &= 12 & \\ \therefore x_2 + 2x_3 &= 6 & \quad (5) \end{alignedat}

(4),(5)(4),(5) より、

{x2=2x3=2\left\{ \begin{aligned} x_2 &= 2 \\ x_3 &= 2 \end{aligned} \right.

よって、

{x1=1x2=2x3=2\left\{ \begin{aligned} x_1 &= 1 \\ x_2 &= 2 \\ x_3 &= 2 \end{aligned} \right.

しかし、このようなアルゴリズムでプログラムを作るのは、難しそうです。

Gauss の消去法​

線型代数で習う Gauss の消去法を使えば、システマティックに連立一次方程式を解くことができます。そのため、このアルゴリズムを用いれば連立方程式を解くプログラムを簡単に作ることができます。Gauss の消去法は、掃き出し法とも呼ばれます。

Gauss の消去法は、前進消去と後退代入の二段階から成ります。

先に線型代数の復習として、簡単に Gauss の消去法を説明しておきます。

次のように nn 個の未知数 x1,x2,x3,…,xnx_1, x_2, x_3, \dots , x_n に対して、nn 個の方程式を考えます。

{a1,1x1+a1,2x2+a1,3x3+⋯+a1,nxn=c1a2,1x1+a2,2x2+a2,3x3+⋯+a2,nxn=c2a3,1x1+a3,2x2+a3,3x3+⋯+a3,nxn=c3⋯⋅⋅an−1,1x1+an−1,2x2+an−1,3x3+⋯+an−1,nxn=cn−1an,1x1+an,2x2+an,3x3+⋯+an,nxn=cn\left\{ \begin{alignedat}{5} a_{1, 1} & x_1 + {} & a_{1, 2} & x_2 + {} & a_{1, 3} & x_3 + \dots + {} & a_{1, n} & x_n = c_1 \\ a_{2, 1} & x_1 + {} & a_{2, 2} & x_2 + {} & a_{2, 3} & x_3 + \dots + {} & a_{2, n} & x_n = c_2 \\ a_{3, 1} & x_1 + {} & a_{3, 2} & x_2 + {} & a_{3, 3} & x_3 + \dots + {} & a_{3, n} & x_n = c_3 \\ & \cdots\cdot\cdot \\ a_{n-1, 1} & x_1 + {} & a_{n-1, 2} & x_2 + {} & a_{n-1, 3} & x_3 + \dots + {} & a_{n-1, n} & x_n = c_{n-1} \\ a_{n, 1} & x_1 + {} & a_{n, 2} & x_2 + {} & a_{n, 3} & x_3 + \dots + {} & a_{n, n} & x_n = c_n \end{alignedat} \right.

この方程式系に対して、以下を行ったものは元の方程式系と同値です。

  • 二つの方程式を入れ替える
  • ある方程式に 0 でないスカラーを掛ける
  • ある方程式に他の方程式のスカラー倍を掛ける

ここで、この方程式系の拡大係数行列を考えます。

A~=(A∣c)=(a1,1a1,2a1,3…a1,nc1a2,1a2,2a2,3…a2,nc2a3,1a3,2a3,3…a3,nc3⋮⋮⋮⋱⋮⋮an−1,1an−1,2an−1,3…an−1,ncn−1,nan,1an,2an,3…an,ncn)\tilde{A} = (A|\bm{c}) = \left( \begin{array}{ccccc|c} a_{1, 1} & a_{1, 2} & a_{1, 3} & \dots & a_{1, n} & c_1 \\ a_{2, 1} & a_{2, 2} & a_{2, 3} & \dots & a_{2, n} & c_2 \\ a_{3, 1} & a_{3, 2} & a_{3, 3} & \dots & a_{3, n} & c_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n-1, 1} & a_{n-1, 2} & a_{n-1, 3} & \dots & a_{n-1, n} & c_{n-1,n} \\ a_{n, 1} & a_{n, 2} & a_{n, 3} & \dots & a_{n, n} & c_n \end{array} \right)

基本行列を次のように定義します。

  • ii 行と jj 行を入れ替える行列を Pi,jP_{i, j}
  • ii 行を λ\lambda 倍する行列を Qi,λQ_{i, \lambda}
  • ii 行に jj 行の λ\lambda 倍を加える行列を Ri,j,λR_{i, j, \lambda}
基本行列

基本行列は、次のように定義されていました。

Pi,j=(1⋱1011⋱1101⋱1)Qi,λ=(1⋱1λ1⋱1)Ri,j,λ=(1⋱1λ⋱1⋱1)\begin{aligned} P_{i, j} &= \begin{pmatrix} 1 \\ & \ddots \\ & & 1 \\ & & & 0 & & & & 1 \\ & & & & 1 \\ & & & & & \ddots \\ & & & & & & 1 \\ & & & 1 & & & & 0 \\ & & & & & & & & 1 \\ & & & & & & & & & \ddots \\ & & & & & & & & & & 1 \\ \end{pmatrix} \\ Q_{i, \lambda} &= \begin{pmatrix} 1 \\ & \ddots \\ & & 1 \\ & & & \lambda \\ & & & & 1 \\ & & & & & \ddots \\ & & & & & & 1 \\ \end{pmatrix} \\ R_{i, j, \lambda} &= \begin{pmatrix} 1 \\ & \ddots \\ & & 1 & & \lambda \\ & & & \ddots \\ & & & & 1 \\ & & & & & \ddots \\ & & & & & & 1 \\ \end{pmatrix} \end{aligned}

拡大係数行列に対して、基本行列を左から掛けて基本変形を繰り返すと、行階段行列 B~\tilde{B} が作れます。

B~=(B∣d)=(1b1,2b1,3…b1,n−1b1,nd11b2,3…b2,n−1b2,nd21…b3,n−1b3,nd3⋱⋮⋮⋮1bn−1,ndn−101dn)\tilde{B} = (B|\bm{d}) = \left( \begin{array}{cccccc|c} 1 & b_{1,2} & b_{1,3} & \dots & b_{1,n-1} & b_{1,n} & d_1 \\ & 1 & b_{2,3} & \dots & b_{2,n-1} & b_{2,n} & d_2 \\ & & 1 & \dots & b_{3,n-1} & b_{3,n} & d_3 \\ & & & \ddots & \vdots & \vdots & \vdots \\ & & & & 1 & b_{n-1,n} & d_{n-1} \\ \text{\huge{0}} & & & & & 1 & d_n \end{array} \right)

これから、作られる方程式系は次のようになりこれははじめの方程式系と同値です。

{x1+b1,2x2+b1,3x3+⋯+b1,n−1xn−1+b1,nxn=d1x2+b2,3x3+⋯+b2,n−1xn−1+b2,nxn=d2x3+⋯+b3,n−1xn−1+b3,nxn=d3…xn−1+bn−1,nxn=dn−1xn=dn\left\{ \begin{alignedat}{5} & x_1 + {} & b_{1,2} & x_2 + {} & b_{1,3} & x_3 + \dots + {} & b_{1,n-1} & x_{n-1} + {} & b_{1, n} & x_n = d_1 \\ & & & x_2 + {} & b_{2,3} & x_3 + \dots + {} & b_{2,n-1} & x_{n-1} + {} & b_{2, n} & x_n = d_2 \\ & & & & & x_3 + \dots + {} & b_{3,n-1} & x_{n-1} + {} & b_{3, n} & x_n = d_3 \\ &\dots \\ & & & & & & & x_{n-1} + {} & b_{n-1,n} & x_n = d_{n-1} \\ & & & & & & & {} & & x_n = d_n \\ \end{alignedat} \right.

これで xnx_n はすぐに求めることができます。さらに、xnx_n の解を代入すれば、xn−1x_{n-1} もすぐに求まります。xnx_n と xn−1x_{n-1} の解を代入すれば、xn−2x_{n-2} の解も求まります。これを繰り返していくことで、連立方程式を解くことができます。

実際に具体的な連立方程式を解いてみましょう。 Gauss の消去法を次の方程式系について行ってみます。

{x1−2x2+3x3=3−x1+3x2−2x3=1x1−x2+6x3=11\left\{ \begin{alignedat}{3.5} & x_1 - {} & 2 & x_2 + {} & 3 & x_3 = 3 \\ -& x_1 + {} & 3 & x_2 - {} & 2 & x_3 = 1 \\ & x_1 - {} & & x_2 + {} & 6 & x_3 = 11 \end{alignedat} \right.

まずは、前進消去を行います。基本変形を繰り返して、行階段行列を作っていきます。

A~=(1−233−13−211−1611)→R2,1,1(1−23301141−1611)→R3,1,−1(1−23301140138)→R3,2,−1(1−23301140024)→Q3,12(1−23301140012)\begin{alignedat}{2} \tilde{A} & = & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ -1 & 3 & -2 & 1 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{R_{2, 1, 1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ 0 & 1 & 1 & 4 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{R_{3, 1, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 3 & 8 \end{array} \right) \\ & \overset{R_{3, 2, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 2 & 4 \end{array} \right) \\ & \overset{Q_{3, \frac{1}{2}}}{\to} & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 1 & 2 \end{array} \right) \end{alignedat}

次に、連立方程式に戻して後退代入を行っていきます。

{x1−2x2+3x3=3x2+x3=4x3=2∴{x1−2x2=3−3×2=−3x2=4−2=2x3=2∴{x1=−3+2×2=1x2=2x3=2∴{x1=1x2=2x3=2\begin{aligned} & \left\{ \begin{alignedat}{3} x_1 - 2 & x_2 + {} & 3 & x_3 & {} = {} & 3 \\ & x_2 + {} & & x_3 & {} = {} & 4 \\ & & & x_3 & {} = {} & 2 \end{alignedat} \right. \\ & \therefore \left\{ \begin{alignedat}{3} x_1 - 2 & x_2 & & & {} = {} & 3 - 3\times 2 = -3 \\ & x_2 & & & {} = {} & 4 - 2 = 2 \\ & & & x_3 & {} = {} & 2 \end{alignedat} \right. \\ & \therefore \left\{ \begin{alignedat}{3} x_1 & & & & {} = {} & -3 + 2\times 2 = 1 \\ & x_2 & & & {} = {} & 2 \\ & & & x_3 & {} = {} & 2 \end{alignedat} \right. \\ & \therefore \left\{ \begin{aligned} x_1 &= 1 \\ x_2 &= 2 \\ x_3 &= 2 \end{aligned} \right. \end{aligned}
備考

次のように、前進消去の段階で行簡約行列を作れば、後退代入を行う必要がなくなります。これは、Gauss-Jordan の消去法と呼ばれます。 Gauss-Jordan の消去法の方が良さそうですが、実は先程のように行簡約行列まで計算しないで途中で止める Gauss の消去法の方が少し計算量が少なくなります。そのため、Gauss の消去法の方がよく使われます。

Gauss-Jordan の消去法で先程の連立方程式を解いてみます。

拡大係数行列に基本変形を繰り返すと、次のような行簡約行列が得られます。

B~=(B∣d)=(10d11d21d3⋱⋮1dn−101dn)\tilde{B} = (B|\bm{d}) = \left( \begin{array}{cccccc|c} 1 & & & & & \text{\huge{0}} & d_1 \\ & 1 & & & & & d_2 \\ & & 1 & & & & d_3 \\ & & & \ddots & & & \vdots \\ & & & & 1 & & d_{n-1} \\ \text{\huge{0}} & & & & & 1 & d_n \end{array} \right)

これから、作られる方程式系は次のようになりこれは元の方程式系と同値です。

{x1=d1x2=d2x3=d3…xn−1=dn−1xn=dn\left\{ \begin{alignedat}{6} & x_1 & & & & & & & & & & = d_1 \\ & & & x_2 & & & & & & & & = d_2 \\ & & & & & x_3 & & & & & & = d_3 \\ & \ldots \\ & & & & & & & x_{n-1} & & & & = d_{n-1} \\ & & & & & & & & & x_n & & = d_n \\ \end{alignedat} \right.

これで連立方程式を解くことができました。

実際に具体的な連立方程式を解いてみます。 Gauss-Jordan の消去法を次の方程式系について行っていきます。

{x1−2x2+3x3=3−x1+3x2−2x3=1x1−x2+6x3=11\left\{ \begin{alignedat}{3.5} & x_1 - {} & 2 & x_2 + {} & 3 & x_3 = 3 \\ -& x_1 + {} & 3 & x_2 - {} & 2 & x_3 = 1 \\ & x_1 - {} & & x_2 + {} & 6 & x_3 = 11 \end{alignedat} \right.
A~=(1−233−13−211−1611)→R2,1,1(1−23301141−1611)→R3,1,−1(1−23301140138)→R1,2,2(1051101140138)→R3,2,−1(1051101140024)→Q3,12(1051101140012)→R1,3,−5(100101140012)→R2,3,−1(100101020012)\begin{alignedat}{5} \tilde{A} & = & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ -1 & 3 & -2 & 1 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{R_{2, 1, 1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ 0 & 1 & 1 & 4 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{R_{3, 1, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -2 & 3 & 3 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 3 & 8 \end{array} \right) \\ & \overset{R_{1, 2, 2}}{\to} & & \left( \begin{array}{ccc|c} 1 & 0 & 5 & 11 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 3 & 8 \end{array} \right) \\ & \overset{R_{3, 2, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & 0 & 5 & 11 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 2 & 4 \end{array} \right) \\ & \overset{Q_{3, \frac{1}{2}}}{\to} & & \left( \begin{array}{ccc|c} 1 & 0 & 5 & 11 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 1 & 2 \end{array} \right) \\ & \overset{R_{1, 3, -5}}{\to} & & \left( \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 1 & 2 \end{array} \right) \\ & \overset{R_{2, 3, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 2 \end{array} \right) \\ \end{alignedat}
{x1+0x2+0x3=10x1+x2+0x3=20x1+0x2+x3=2∴{x1=1x2=2x3=2\left\{ \begin{alignedat}{4} & x_1 + {} & 0 & x_2 + {} & 0 & x_3 & & = 1 \\ 0 & x_1 + {} & & x_2 + {} & 0 & x_3 & & = 2 \\ 0 & x_1 + {} & 0 & x_2 + {} & & x_3 & & = 2 \end{alignedat} \right. \\ \therefore \left\{ \begin{aligned} x_1 &= 1 \\ x_2 &= 2 \\ x_3 &= 2 \end{aligned} \right.

Gauss の消去法を使ったプログラム​

Gauss の消去法を使って連立一次方程式を解くプログラムを作ってみましょう。概要を説明します。

まずは、前進消去を行います。

ii 行、ii 列が pivot となるので、ii 行目を pivot の値で割って pivot を 1 にします。 その後、その行で i+1i+1 行目以降を掃き出します。

次は、後退代入を行います。

xn=dnx_n = d_n になります。求まった xnx_n をそれよりも上の式すべてに代入して、bj,nxn(1≤j≤n−1)b_{j, n}x_n(1\leq j\leq n-1) を右辺に移動させ、dj(1≤j≤n−1)d_j(1\leq j\leq n-1) の値を更新します。こうすると、xn−1x_{n-1} が求まります。これを繰り返すと連立一次方程式が解けます。

プログラムは次のようになります。計算量は、O(n3)O(n^3) です。

Open In Colab

reversed 関数は配列の要素を反転します。

部分ピボット選択​

さきほどのプログラムを使えば、多くの様々な連立一次方程式が解けます。 しかし、次の連立方程式を解くと、次のようにエラーが出てしまいます。

{−2x2+3x3=2−x1+3x2−2x3=1x1−x2+6x3=11\left\{ \begin{alignedat}{3.5} & & -2 & x_2 + {} & 3 & x_3 = 2 \\ -& x_1 + {} & 3 & x_2 - {} & 2 & x_3 = 1 \\ & x_1 - {} & & x_2 + {} & 6 & x_3 = 11 \end{alignedat} \right.
Open In Colab

これは、前進消去の際に 0 で割る操作が起こってしまったからです。 これを解決するために、部分ピボット選択を行います。部分ピボット選択には、誤差を小さくする役割もあります。

部分ピボット選択は、pivot 列の pivot 行以降の行で絶対値が最大になる行を pivot に使うように変形することです。

先程の連立方程式なら、次のように計算していきます。1 つ目から、2 つ目への変形が部分ピボット選択によるものです。

(0−232−13−211−1611)→P1,2(−13−210−2321−1611)→Q2,−1(1−32−10−2321−1611)→R3,1,−1(1−32−10−23202412)→Q2,−12(1−32−101−32−102412)→R3,2,−2(1−32−101−32−100714)→Q3,17(1−32−101−32−10012)\begin{alignedat}{2} & & & \left( \begin{array}{ccc|c} 0 & -2 & 3 & 2 \\ -1 & 3 & -2 & 1 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{P_{1, 2}}{\to} & & \left( \begin{array}{ccc|c} -1 & 3 & -2 & 1 \\ 0 & -2 & 3 & 2 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{Q_{2, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -3 & 2 & -1 \\ 0 & -2 & 3 & 2 \\ 1 & -1 & 6 & 11 \end{array} \right) \\ & \overset{R_{3, 1, -1}}{\to} & & \left( \begin{array}{ccc|c} 1 & -3 & 2 & -1 \\ 0 & -2 & 3 & 2 \\ 0 & 2 & 4 & 12 \end{array} \right) \\ & \overset{Q_{2, -\frac{1}{2}}}{\to} & & \left( \begin{array}{ccc|c} 1 & -3 & 2 & -1 \\ 0 & 1 & -\frac{3}{2} & -1 \\ 0 & 2 & 4 & 12 \end{array} \right) \\ & \overset{R_{3, 2, -2}}{\to} & & \left( \begin{array}{ccc|c} 1 & -3 & 2 & -1 \\ 0 & 1 & -\frac{3}{2} & -1 \\ 0 & 0 & 7 & 14 \end{array} \right) \\ & \overset{Q_{3, \frac{1}{7}}}{\to} & & \left( \begin{array}{ccc|c} 1 & -3 & 2 & -1 \\ 0 & 1 & -\frac{3}{2} & -1 \\ 0 & 0 & 1 & 2 \end{array} \right) \\ \end{alignedat}

部分ピボット選択を入れると、次のようなプログラムになります。

Open In Colab

練習問題​

Gauss-Jordan の消去法を使って行簡約行列を作ることで、連立方程式を解くプログラムを作ってください。

解答
Open In Colab