gijyutsu-keisan.com

1．連立一次方程式

連立一次方程式は通常、次のように表します。
\[ \begin{eqnarray} \left\{ \begin{array}{1} 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 \\ \cdots \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m \\ \end{array} \right. \end{eqnarray} \tag{1-1} \]
上式は行列を使って表すこともできます。 そこで、係数行列\( A \in R^{m \times n} \ \)、定数項ベクトル\( \bf{b} \in R^m \)、変数ベクトル\( \bf{x} \in R^n \)とすると、
\[ A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ & & \ddots & \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} , \bf{b} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} , \bf{x} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \tag{1-2} \]
連立一次方程式は次のように表せます。
\[ A \bf{x} = \bf{b} \tag{1-3} \]
この連立方程式は、定数項ベクトル\( \bf{b} \)のとる値によって、次のように分類されます。
  1. 同次方程式　 ：\( \bf{b}=\bf{o} \)のとき、つまり\( A \bf{x} = \bf{o} \)
  2. 非同次方程式 ：\( \bf{b} \neq \bf{o} \)のとき
連立方程式の目的は、変数ベクトル\( \bf{x} \)を求めることです。
\( A \bf{x} = \bf{b} \)を満たす解全体の集合を一般解、何らかの方法で見いだされる1つの解を特殊解と呼びます。 連立方程式の解に関する性質（構造）は、線型代数ページの線型写像の核の構造定理に詳しく述べていますので、そちらを参照ください。

2．行列の標準形

“行列の標準形”という概念は、行列の数値計算において最も重要な概念です。 これは、行列を変形すると最終的に単位行列を含む非常に簡単な形にできる、というものです。 この変形によって、連立方程式を数値計算で解くことが可能となります。
行列の標準形を実現するには、以下に示す基本変形行列を用います。

2．1．基本変形行列

基本変形行列には次の3つがあり、これらはすべて逆行列を持ちます （詳細は線型代数ページにゆずります）。

  1. 交換行列\( P(i,j) \)：
    \( i \)行（列）と\( j \)行（列）を交換します。
    単位行列\( I \)の\( i \)行\( i \)列と\( j \)行\( j \)列成分を、\( i \)行\( j \)列と\( j \)行\( i \)列成分と入れ替えたものです。
    \[ P(i,j) = \begin{pmatrix} & 1 & & \vdots & & \vdots & & & \\ & & \ddots & \vdots & & \vdots & & & \\ & \cdots & \cdots & 0 & \cdots & 1 & \cdots & \cdots & \\ & & & \vdots & \ddots & \vdots & & & \\ & \cdots & \cdots & 1 & \cdots & 0 & \cdots & \cdots & \\ & & & \vdots & & \vdots & \ddots & & \\ & & & \vdots & & \vdots & & 1 & \end{pmatrix} \tag{2.1-1} \]
    交換行列の逆行列は交換行列そのものです。
    \[ P(i,j)^{-1} = P(i,j) \]
  2. スカラー倍行列\( M(i:c) \)：
    \( i \)行（列）を\( c \)倍します。
    単位行列\( I \)の\( i \)行\( i \)列を\( c \)倍したものです。
    \[ M(i:c) = \begin{pmatrix} & 1 & & & \vdots & & & & \\ & & \ddots & & \vdots & & & & \\ & & & 1 & \vdots & & & & \\ & \cdots & \cdots & \cdots & c & \cdots & \cdots & \cdots & \\ & & & & \vdots & 1 & & & \\ & & & & \vdots & & \ddots & & \\ & & & & \vdots & & & 1 & \end{pmatrix} \tag{2.1-2} \]
    スカラー倍行列の逆行列は、次のようになります。
    \[ M(i:c)^{-1} = M(i:1/c) \]
  3. 追加行列\( A(i,j;c) \)：
    \( j \)行（列）を\( c \)倍して\( i \)行（列）に加えます。
    \[ A(i,j;c) = \begin{pmatrix} & 1 & & \vdots & & & & & \\ & & \ddots & \vdots & & & & & \\ & & & 1 & & & & & \\ & & & \vdots & \ddots & & & & \\ & \cdots & \cdots & c & \cdots & 1 & \cdots & \cdots & \\ & & & \vdots & & \vdots & \ddots & & \\ & & & \vdots & & \vdots & & 1 & \end{pmatrix} \tag{2.1-3} \]
    追加行列の逆行列は、次のようになります。
    \[ A(i,j:c)^{-1} = A(i,j:-c) \]
行列\( A \)に対し、基本変形行列\( T \)を左から掛けると行変換、右から掛けると列変換になります。
例として、交換行列を使って表現してみます。
  • 行変換：
    \[ T A = \begin{pmatrix} & 0 & 1 & 0 & \\ & 1 & 0 & 0 & \\ & 0 & 0 & 1 & \end{pmatrix} \begin{pmatrix} & \txc{blue}{ a } & \txc{blue}{ b } & \txc{blue}{ c } & \\ & \txc{red}{ d } & \txc{red}{ e } & \txc{red}{ f } & \\ & g & h & i & \end{pmatrix} = \begin{pmatrix} & \txc{red}{ d } & \txc{red}{ e } & \txc{red}{ f } & \\ & \txc{blue}{ a } & \txc{blue}{ b } & \txc{blue}{ c } & \\ & g & h & i & \end{pmatrix} \]
  • 列変換：
    \[ A T = \begin{pmatrix} & \txc{blue}{ a } & \txc{red}{ b } & c & \\ & \txc{blue}{ d } & \txc{red}{ e } & f & \\ & \txc{blue}{ g } & \txc{red}{ h } & i & \end{pmatrix} \begin{pmatrix} & 0 & 1 & 0 & \\ & 1 & 0 & 0 & \\ & 0 & 0 & 1 & \end{pmatrix} = \begin{pmatrix} & \txc{red}{ b } & \txc{blue}{ a } & c & \\ & \txc{red}{ e } & \txc{blue}{ d } & f & \\ & \txc{red}{ h } & \txc{blue}{ g } & i & \end{pmatrix} \]

2．2．基本変形による行列の標準形

先のも述べたように、“行列の標準形”という概念は、行列の数値計算において最も重要な概念で、次のようなものになります。
任意の行列\( A \in R^{m \times n} \ \)に対して、二つの正則行列\( P \in R^{n \times n}, Q \in R^{m \times m} \ \)が存在して、次の形に変形できます。
\[ Q^{-1} A P = \begin{pmatrix} & E_r & O_{r,n-r} & \\ & O_{m-r,r} & O_{m-r,n-r} & \end{pmatrix} \quad ( \because r = \mathrm{rank} A ) \tag{2.2-1} \]
正則行列\( P,Q \)は、前節の基本変形行列の組み合わせによって作られます。
この性質を上手く使えば、連立方程式は次のように書き換えられます。
\[ A \bf{x} = \bf{b} \ \rightarrow \ Q^{-1} A P ( P^{-1} \bf{x} ) = Q^{-1} \bf{b} \]
\[ \rightarrow \ \begin{pmatrix} & E_r & O_{r,n-r} & \\ & O_{m-r,r} & O_{m-r,n-r} & \end{pmatrix} \begin{pmatrix} \bf{x_r} \\ \bf{x_{n-r}} \end{pmatrix} = \begin{pmatrix} \bf{b_r} \\ \bf{b_{m-r}} \end{pmatrix} \tag{2.2-2} \]
この式からもわかるように、行列の階数\( r \)が解ベクトル\( \bf{x} \)の成分を特定できる次元（成分の数）になります。

3．連立方程式の解

3．1．行列の階数（ランク）

連立方程式を解く際、行列の階数（ランク）の概念が重要になりますので、その概要について説明します （詳細は線型代数ページで述べていますのでそちらを参照ください）。

行列の階数は、行列Aを列ベクトル表現したとき線型独立な列ベクトルの数を意味し、rank Aで表します。 Aがn次正方行列で、rank A=nの場合、Aのすべての列ベクトルは線型独立であることを意味します （この条件をフルランクと呼びます）。 また、rank A=1の場合、Aには1つの線型独立な列ベクトルしか含まれないことになります。
この性質から、rank A=nならAは逆行列を持ちますが、それ以外ならAは逆行列を持ちません。
また、前節の行列の標準形で単位行列のサイズrを決めるのもrank Aになります。 つまり、Aに線型独立な列ベクトルがr個含まれているなら、その標準形は（2.2-2）式
\[ \begin{pmatrix} & E_r & O_{r,n-r} & \\ & O_{m-r,r} & O_{m-r,n-r} & \end{pmatrix} \begin{pmatrix} \bf{x_r} \\ \bf{x_{n-r}} \end{pmatrix} = \begin{pmatrix} \bf{b_r} \\ \bf{b_{m-r}} \end{pmatrix} \tag{2.2-2} \]
になります。

3．2．同次方程式の解

\( A \in R^{m \times n}, \bf{x} \in R^n \)のとき、\( A \bf{x} = \bf{o} \)の解を求めます。
まず、行列\( A \)の階数（ランク）を
\[ r = \mathrm{rank} A \leq \min{(m,n)} \]
とします。
適当な行/列基本変形行列\( Pr \in R^{m \times m}, Pc \in R^{n \times n} \ \)を用いれば、
\[ P_r A P_c = \begin{pmatrix} E_{rr} & O_{r,n-r} & \\ O_{m-r,r} & O_{m-r,n-r} & \end{pmatrix} \tag{3.2-1} \]
と出来ます。この形を行列の標準形と呼びます （証明は線型代数ページを参照ください）。
この標準形を同次方程式に適用するには、\( A \bf{x} = \bf{o} \)の両辺に\( Pr \)を掛け、\( \bf{x} \)の前に\( P_c P_c^{-1} \)を掛けます。
\[ P_r A P_c ( P_c^{-1} \ \bf{x} ) = P_r \bf{o} = \bf{o} \]
（3.2-1）式を用いて表現すると、次のようになります。
\[ \begin{pmatrix} E_r & O \\ O & O \end{pmatrix} \left( \begin{array}{c} \bf{x'_r} \\ \bf{x'_{n-r}} \end{array} \right) = \left( \begin{array}{c} \bf{x'_r} \\ \bf{o} \end{array} \right) = \bf{o} \tag{3.2-2} \]
この式から次の結果が得られます。
  • \( \bf{x'_r} = \bf{o} \)
  • \( \bf{x'_{n-r}} \ \)は不定、つまり任意の値をとります。

3．3．非同次方程式の解

今度は\( A \bf{x} = \bf{b} \)に行列の標準形（3.2-1）式を適用すると、次のようになります。
\[ P_r A P_c ( P_c^{-1} \ \bf{x} ) = P_r \bf{b} \]
\[ \rightarrow \ \begin{pmatrix} E_{rr} & O_{r,n-r} & \\ O_{m-r,r} & O_{m-r,n-r} & \end{pmatrix} \left( \begin{array}{c} \bf{x'_r} \\ \bf{x'_{n-r}} \end{array} \right) = \left( \begin{array}{c} \bf{b'_r} \\ \bf{b'_{m-r}} \end{array} \right) \]
\[ \rightarrow \left( \begin{array}{c} \bf{x'_r} \\ \bf{o} \end{array} \right) = \left( \begin{array}{c} \bf{b'_r} \\ \bf{b'_{m-r}} \end{array} \right) \tag{3.3-1} \]
ここで、次の場合分けをします。
  1. \( b'_{r+1}, \cdots, b'_m \)のうち0でないものが存在するとき、方程式に矛盾するため“解なし”になります。
  2. \( b'_{r+1}, \cdots, b'_m \)がすべて0のとき、\( \bf{x'_{r+1}}, \cdots, \bf{x'_n} \)は任意解をとります。
    従って\( \bf{x'_{r+1}}, \cdots, \bf{x'_n} \)に対する任意係数を\( c'_{r+1}, \cdots, c'_n \)として、連立方程式を成分表示すると、次のようになります。
    \[ \begin{eqnarray} x_1' & & & & + c_{1,r+1} \ x'_{r+1} \ + \cdots + \ & c_{1n} x'_n & = b'_1 \\ & x_2' & & & + c_{2,r+1} \ x'_{r+1} \ + \cdots + \ & c_{2n} x'_n & = b'_2 \\ \ & & \ddots & & & & \cdots \\ & & & x_r' & + c_{r,r+1} \ x'_{r+1} \ + \cdots + \ & c_{rn} x'_n & = b'_r \\ & \ & & & & 0 & = b'_{r+1} \\ & \ & & & & & \cdots \\ & \ & & & & 0 & = b'_{m} \end{eqnarray} \]
    そこで\( c'_{r+1} = \cdots = c'_n = 0 \)とおけば、\( A \bf{x} = \bf{b} \)の特殊解として、\( x'_1 = b'_1, \cdots , x'_r = b'_r \ \)が得られます。 従って、連立方程式の解は次のようになります。
    \[ \begin{eqnarray} \left\{ \begin{array}{1} x'_1 = b'_1 - ( c_{1,r+1} \ x'_{r+1} + \cdots + c_{1n} x'_n ) \\ \cdots \\ x'_r = b'_r - ( c_{r,r+1} \ x'_{r+1} + \cdots + c_{rn} x'_n ) \\ x'_{r+1}, \cdots, x'_nは任意 \end{array} \right. \end{eqnarray} \qquad ( c_{ij}は任意 \ (1 \leq i \leq r, r+1 \leq j \leq n) ) \]
なお、この詳細な説明については、線型代数ページの“線型写像の核の構造定理”を参照ください。

3．4．連立方程式が解を持つ条件

まずは行列\( A \in R^{m \times n} \ \)のサイズ（行数：\( m \)、列数：\( n \)）で大別します。

  1. \( m=n \)（\( A \)は正方行列）の場合
    \[ A = \begin{pmatrix} \txc{red}{*} & \txc{red}{\cdots} & \txc{red}{*} \\ \txc{red}{\vdots} & & \txc{red}{\vdots} \\ \txc{red}{*} & \txc{red}{\cdots} & \txc{red}{*} \end{pmatrix} \]
  2. \( m \lt n \)（過少決定系）
    \[ A = \begin{pmatrix} \txc{red}{*} & \txc{red}{\cdots} & \txc{red}{*} & \cdots & * \\ \txc{red}{\vdots} & & \txc{red}{\vdots} & & \vdots \\ \txc{red}{*} & \txc{red}{\cdots} & \txc{red}{*} & \cdots & * \end{pmatrix} \]
  3. \( m \gt n \)（過剰決定系）
    \[ A = \begin{pmatrix} \txc{red}{*} & \txc{red}{\cdots} & \txc{red}{*} \\ \txc{red}{\vdots} & & \txc{red}{\vdots} \\ \txc{red}{*} & \txc{red}{\cdots} & \txc{red}{*} \\ \vdots & & \vdots \\ * & \cdots & * \end{pmatrix} \]
また、行列\( A \)の階数（ランク）を\( r = \mathrm{rank} A \)とします。
行列のサイズ（行数、列数）と階数によって、連立方程式の取る解は変わります。 下表に解の種類とその条件をまとめます。

一意に解が定ま部場合
（1）\( A \)は正方行列で、\( r = m = n \)（フルランク）
\( A \bf{x} = \bf{b} \)を解くことで、解\( \bf{x} \)は一意に定まります。

（2）\( A \)は縦長行列で、\( r = n \lt m \)
縦長行列\( A \)の階数が列数と一致するので \( A = \begin{pmatrix} A'_{nn} \\ O_{m-n,n} \ \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{nn} \bf{x_n} = \bf{b'_n} \)に書き換えられます。 これは上記（1）と同じ条件です。

特殊解
（3）\( A \)は正方行列で、\( r \lt m = n \) \( \land \bf{b_{m-r}} = \bf{o} \)
正方行列は \( A = \begin{pmatrix} A'_{rr} & O_{r,n-r} & \\ O_{n-r,r} & O_{n-r,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{rr} \bf{x_r} = \bf{b'_r} \)に書き換えられます。
従って、\( \bf{x_{n-r}} \)は一般解、\( \bf{x_r} \)は特殊解になります。

（4）\( A \)は横長行列で、\( r=m \lt n \)
横長行列は \( A = \begin{pmatrix} A'_{mm} & O_{m,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{mm} \bf{x_m} = \bf{b'} \)に書き換えられます。
従って、\( \bf{x_{m-r}} \)は一般解、\( \bf{x_r} \)は特殊解になります。

（5）\( A \)は横長行列で、\( r \lt m \lt n \) \( \land \bf{b_{m-r}} = \bf{o} \)
横長行列は \( A = \begin{pmatrix} A'_{rr} & O_{n-r,r} & \\ O_{m-r,r} & O_{n-r,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{rr} \bf{x_r} = \bf{b'_r} \)に書き換えられます。
従って、\( \bf{x_{m-r}} \)は一般解、\( \bf{x_r} \)は特殊解になります。

（6）\( A \)は縦長行列で、\( r \lt n \lt m \) \( \land \bf{b_{m-r}} = \bf{o} \)
縦長行列は \( A = \begin{pmatrix} A'_{rr} & O_{n-r,r} & \\ O_{m-r,r} & O_{n-r,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{rr} \bf{x_r} = \bf{b'_r} \)に書き換えられます。
従って、\( \bf{x_{m-r}} \)は一般解、\( \bf{x_r} \)は特殊解になります。

解なしの場合
（7）\( A \)は正方行列で、\( r \lt m = n \) \( \land \bf{b_{m-r}} \neq \bf{o} \)
正方行列は \( A = \begin{pmatrix} A'_{rr} & O_{r,n-r} & \\ O_{n-r,r} & O_{n-r,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{rr} \bf{x_r} = \bf{b'_r}, \bf{b_{n-r}} = \bf{o} \)に書き換えられます。
これは、条件である\( \bf{b_{m-r}} \neq \bf{o} \)に矛盾します。

（8）\( A \)は横長行列で、\( r\lt m \lt n \) \( \land \bf{b_{m-r}} \neq \bf{o} \)
横長行列は \( A = \begin{pmatrix} A'_{rr} & O_{n-r,r} & \\ O_{m-r,r} & O_{n-r,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{rr} \bf{x_r} = \bf{b'_r}, \bf{b_{m-r}} = \bf{o} \)に書き換えられます。
これは、条件である\( \bf{b_{m-r}} \neq \bf{o} \)に矛盾します。

（9）\( A \)は縦長行列で、\( r \lt n \lt m \) \( \land \bf{b_{m-r}} \neq \bf{o} \)
縦長行列は \( A = \begin{pmatrix} A'_{rr} & O_{n-r,r} & \\ O_{m-r,r} & O_{n-r,n-r} & \end{pmatrix} \) と変形できます。
このとき連立方程式は\( A'_{rr} \bf{x_r} = \bf{b'_r}, \bf{b_{m-r}} = \bf{o} \)に書き換えられます。
これは、条件である\( \bf{b_{m-r}} \neq \bf{o} \)に矛盾します。

参考文献

▲