ベイジアン研究所

プログラミング言語(アルゴリズム的な話が中心)やガジェットの紹介をしています。時々心理学の話も。

【線型代数学入門】連立一次方程式の解法

1. 記事の目的
以下の記事で、行列の基本変形と行列の階数について述べた。本記事ではこれらの概念を用いて、連立一次方程式の開放について解説する。

camelsan.hatenablog.com

camelsan.hatenablog.com

2. 連立一次方程式
中学生の時に、未知変数二つに対して、方程式を2個用意すれば、未知変数を決定することができるということを習ったはずでる。ここではより一般的にn個の未知変数に対し、m本の連立方程式を用意した時にいつ解が求められるのか、あるいはどうやって 求められるのかを解説する。数学では非線形的な問題を線形的に近似して、連立方程式を解いて近似解を求めるというアプローチがしばしば取られる。こういった意味でも連立一次方程式の解法は重要となってくる。ここで、連立一次方程式とは次のようなものである。

n個の未知変数x_1,\dots,x_nに関するm個の一次方程式の組、


    \begin{split}
        &a_{11}x_1+a_{12}+\dots+a_{1n}x_n=c_1 \\
        &a_{21}x_1+a_{22}+\dots+a_{2n}x_n=c_2 \\
        &\vdots\\
        &a_{m1}x_1+a_{m2}+\dots+a_{mn}x_n=c_m \\
    \end{split}
\tag{1}

を連立一次方程式という。

連立方程式は常にただ一つの解を持つとは限らない。例えば、


    x_1+x_2=1

は無数の解を持つ((x_1,x_2)=(a+1,-a)aは任意の実数は全て解)

また、連立一次方程式が解をもたない時もある。例えば、


    0\cdot x_1=1

は解をもたない。

3. 拡大係数行列
連立一次方程式(1)を考える。係数a_{ij}を並べた行列

A=
    \begin{pmatrix}
        a_{11} & a_{12} & \dots & a_{1n} \\
        a_{21} & a_{22} & \dots & a_{2n} \\
        \vdots & \vdots &&\vdots \\
        a_{m1} & a_{m2} & \dots & a_{mn} \\
    \end{pmatrix}

を(1)の係数行列という。またAの右端にc_iを付け加えた行列

\hat{A}=
    \begin{pmatrix}
        a_{11} & a_{12} & \dots & a_{1n} & c_1 \\
        a_{21} & a_{22} & \dots & a_{2n} & c_2 \\
        \vdots & \vdots &&\vdots &\vdots\\
        a_{m1} & a_{m2} & \dots & a_{mn} & c_m \\
    \end{pmatrix}

を(1)の拡大係数行列という。また、

\bf{x}=
    \begin{pmatrix}
        x_1 \\
        x_2 \\
        \vdots \\
        x_n
    \end{pmatrix},
    \hat{\bf{x}}=
    \begin{pmatrix}
        x_1 \\
        x_2 \\
        \vdots \\
        x_n \\
        -1
    \end{pmatrix},
    \bf{c}=
        \begin{pmatrix}
        c_1 \\
        c_2 \\
        \vdots \\
        c_m
    \end{pmatrix}

とすると、(1)を次の(2)と(3)の形に書くことができる。


    A\bf{x}=\bf{c}
\tag{2}

    \hat{A}\hat{\bf{x}}=0
\tag{3}

4. 拡大係数行列に関する定理
任意のm次正方行列Pに対し、(3)は、


    P\hat{A}\hat{\bf{x}}=0
\tag{4}

と同じである。これは(3)と(4)の解が全く同じであることを示す。また、(4)は、\hat{\bf{A}}に左基本変形を施しても、その結果得られる新しい方程式は、元の方程式(3)と同じことを意味する。即ち、\hat{A}を左基本変形で、簡単な形にすることで、連立一次方程式の解を求めることができることを示す。また、足し算の順序を変えることで、変数の順序を変えることができる。これは、拡大係数行列の最終列以外の順番を任意に変えることができることを示す。まとめると

操作のみで、拡大係数行列をなるべく簡単な形にして、連立方程式を解く方法が考えられるのではないかというアプローチが考えられる。

上記の2点の変形で拡大係数行列は、次の定理に示す形まで変形することができる。

定理
拡大係数行列\hat{A}に、左基本変形及び、最後の列以外の列の交換を何回か行うことで、[tex\hat{A}]は図1の[tex\hat{B}]に変形することができる。

f:id:camelsan:20210227113303p:plain
図1 拡大係数行列の変形後
ただし、rは係数行列Aの階数である。
証明A=0ならば

\hat{A}=
    \begin{pmatrix}
        0 & \dots & 0 & c_1 \\
        \vdots &&\vdots&\vdots \\
        0 & \dots & 0 & c_m \\
     \end{pmatrix}

より、\hat{B}r=0の場合である。A\neq 0ならば、行の変換もしくは、n+1列以外の交換によって、(1,1)成分が0でないようにすることができる。そこで、(1,1)をかなめとして第1列を掃き出す。掃き出しに関しては以下の記事を参照。

camelsan.hatenablog.com

ここで、第2列から第n列までの第2行以下が0ならば、これが求める形である(r=1の場合)。第2列と第n列の間に0でないものがあれば、(2,2)成分を1にし、第2列の(2,2)成分以外を全て0にすることができる。この操作を可能な限り続けることで、あるrに対して、\hat{B}の形になる。

次に、rAの階数に等しいことを証明する。次のことに注意する。\hat{A}に施した基本変形により、\hat{A}の1部分であるAにも同じ基本変形が施される。従って、\hat{B}から最後の列を取り除いた(m,n)型行列をBとすると、Aの階数と、Bの階数とは次の記事の定理により等しい(BA基本変形を施されて得られている。即ちある正則行列Pに対して


    B=PA

一方、Bの階数をr_Bとすると、基本行列P^{\prime}Q^{\prime}を用いて、


    P^{\prime}BQ^{\prime}=F(r_B)

よって、


    P^{\prime}PAQ^{\prime}=F(r_B)

行列の階数は変形対象の行列のみで決定されるので、r_BAの回数でもある。従って、ABの階数は等しい。 )。

camelsan.hatenablog.com

Bの第r+j(j=1,2,\dots,n-r)から、第k(k=1,2,\dots,r)b_{k,r+j}倍を引けば、標準形F_{m,n}(r)を得る。Bの階数はrとなり、またBの階数とAの階数は等しいので、rAの階数と等しい。

5. 連立一次方程式の解法
従って、上記の定理から(3)は、


   \hat{B}\hat{\bf{x}}=0

の形になる。これは、


    \begin{split}
        & x_1 + b_{1,r+1}x_{r+1}+\dots+b_{1,n}x_n=d_1 \\
        & x_2 + b_{2,r+1}x_{r+1}+\dots+b_{2,n}x_n=d_2 \\
        & \vdots \\
        & x_r + b_{r,r+1}x_{r+1}+\dots+b_{r,n}x_n=d_r \\
        &0=d_{r+1} \\
        &\vdots \\
        &0=d_{m} \\
    \end{split}

の形になる。ここで、d_{r+1}, d_{r+2}, \dots, d_mの中に0でないものがあれば、(2)は解をもたない。d_{r+1}=d_{r+2}=\dots =d_m=0の時はx_{r+1}, x_{r+2}, \dots, x_mに任意の数、\alpha_{r+1}, \alpha_{r+2}, \dots, \alpha_mを代入し、その部分を移行すると、次の形になる。


    \begin{split}
        &x_1 = d_1-b_{1,r+1}\alpha_{r+1}-\dots -b_{1,n}\alpha_n \\
        &x_2 = d_2-b_{2,r+1}\alpha_{r+1}-\dots -b_{2,n}\alpha_n \\
        & \vdots\\
        &x_r = d_r-b_{r,r+1}\alpha_{r+1}-\dots -b_{r,n}\alpha_n \\
        &x_{r+1}=\alpha_{r+1}\\
        &\vdots\\
        &x_{n}=\alpha_{n}\\
    \end{split}

従って、次の定理が得られる。

定理
方程式(1)は、拡大係数行列\hat{A}に、左基本変形及、最終右列以外の列の変換を施して\hat{B}に変形した時、d_{r+1}=d_{r+2}=\dots=d_m=0の時に限って解を持つ。その時の解は、x_{r+1},x_{r+2},\dots,x_nに、n-r個の任意定数\alpha_{r+1},\alpha_{r+2},\dots,\alpha_n を代入し、(4)によって、x_1,x_2,\dots,x_rを定めることによって得られる。ただし、未知数の順序は、列の交換に対応して入れ替わっている。

6. 例
次の連立一次方程式を解く。


    \begin{split}
        &3x_2+3x_3-2x_4=-4 \\
        &x_1+x_2+2x_3+3x_4=2 \\
        &x_1+2x_2+3x_3+2x_4=1 \\
        &x_1+3x_2+4x_3+2x_4=-1 \\
    \end{split}

拡大係数行列\hat{A}は次のように変形される。


    \begin{split}
        \hat{A}&=
        \begin{pmatrix}
            0&3&3&-2&-4\\
            1&1&2&3&2\\
            1&2&3&2&1\\
            1&3&4&2&-1
        \end{pmatrix} \\
        &\rightarrow^{(1)}
        \begin{pmatrix}
            1&1&2&3&2\\
            0&3&3&-2&-4\\
            1&2&3&2&1\\
            1&3&4&2&-1
        \end{pmatrix} (\text{第1行と第2行を入れ替える})\\
        &\rightarrow^{(2)}
        \begin{pmatrix}
            1&1&2&3&2\\
            0&3&3&-2&-4\\
            0&1&1&-1&-1\\
            0&2&2&-1&-3
        \end{pmatrix} (\text{第1列を掃き出す})\\
        &\rightarrow^{(3)}
        \begin{pmatrix}
            1&1&2&3&2\\
            0&1&1&-1&-1\\
            0&3&3&-2&-4\\
            0&2&2&-1&-3
        \end{pmatrix} (\text{第2行と第3行を入れ替える})\\
        &\rightarrow^{(4)}
        \begin{pmatrix}
            1&0&1&4&3\\
            0&1&1&-1&-1\\
            0&0&0&1&-1\\
            0&0&0&1&-1
        \end{pmatrix} (\text{第2列を掃き出す})\\
        &\rightarrow^{(5)}
        \begin{pmatrix}
            1&0&4&1&3\\
            0&1&-1&1&-1\\
            0&0&1&0&-1\\
            0&0&1&0&-1
        \end{pmatrix} (\text{第3列と第4列を交換する})\\
        &\rightarrow^{(6)}
        \begin{pmatrix}
            1&0&0&1&7\\
            0&1&0&1&-2\\
            0&0&1&0&-1\\
            0&0&0&0&0
        \end{pmatrix} (\text{第3列を掃き出す})\\
     \end{split}

第4行が0からなるので、解は存在し、4-3=1個の任意定数を含む。(5)の操作で、第3列と第4列を交換したので、


    \begin{split}
        &x_1+x_3=7\\
        &x_2+x_3=-2\\
        &x_4=-1
    \end{split}

従って、解はx_3=\alphaとして、


x_1=7-\alpha,
x_2=-\alpha -2,
x_4=-4,
x_3=\alpha

となる。

次の記事

camelsan.hatenablog.com

7. 参考文献
[1] 線型代数入門