概要

概要#

連立1次方程式#

\[\begin{split} % 太字のalias \newcommand{\b}[1]{\boldsymbol{#1}} % 演算子の定義 \DeclareMathOperator{\im}{ \text{Im} } \DeclareMathOperator{\rank}{ \text{rank} } \DeclareMathOperator{\span}{ \text{Span} } \DeclareMathOperator{\Ker}{ \text{Ker} } % \begin{cases} \begin{align} a_{11} x_1 + a_{12} x_2 + &\cdots + a_{1m} x_m = y_1\\ a_{21} x_1 + a_{22} x_2 + &\cdots + a_{2m} x_m = y_2\\ &\vdots\\ a_{n1} x_1 + a_{n2} x_2 + &\cdots + a_{nm} x_m = y_n\\ \end{align} \end{cases} \end{split}\]

のような連立一次方程式は、

\[\begin{split} A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1m} \\ a_{21} & a_{22} & \cdots & a_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nm} \\ \end{pmatrix} , \hspace{1em} \b{x} = \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_m \end{pmatrix} , \hspace{1em} \b{y} = \begin{pmatrix} y_1\\ y_2\\ \vdots\\ y_n \end{pmatrix} \end{split}\]

を用いて

\[ A\b{x} = \b{y} \]

と表すことができる。

もし\(A\)に逆行列が存在するなら

\[ \b{x} = A^{-1} \b{y} \]

と解くことができる。

例題#

\[\begin{split} \begin{cases} \begin{align} x + y &= 5\\ 2x + 4y &= 14 \end{align} \end{cases} \end{split}\]

を例に考えてみる。

中学数学的な素朴な解き方だと、式を定数倍したり、式同士を差し引いたりすることで変数を消していく。この方法は変数消去法と呼ばれる。

変数消去法は行列表記にすることもできる。

まとめると、ブロック行列

\[\begin{split} \left(\begin{array}{c|c} A & y \end{array}\right) \left(\begin{array}{c} \b{x}\\ \hline -1 \end{array}\right) = \b{0} \end{split}\]

を変形していって

\[\begin{split} \left(\begin{array}{c|c} I & z \end{array}\right) \left(\begin{array}{c} \b{x}\\ \hline -1 \end{array}\right) = \b{0} \end{split}\]

という形にする。 \(\b{x} - \b{z} = \b{0}\)となり、\(\b{z}\)のところに解が現れる。

変数消去法に限らず、行列で連立一次方程式を解くときはこのパターンになる。また、変化があるのは\((A|\b{y})\)の部分だけなので、この部分だけを扱うことも多い。

ガウスの消去法（掃き出し法）#

ガウスの消去法（Gaussian elimination） あるいは 掃き出し法（row reduction） は正則行列による連立一次方程式を、ブロック行列表記にして解く方法。

変数消去法と同様に、

行のスカラー倍
行のスカラー倍を別の行に加算する
行の順番を入れ替える

といった操作を行うもので、

まず\(A\)の対角線より下の要素たちを0にしていき、その後対角線より上の要素たちを0にしていって\(I\)に到達する、という流れで計算していく

\(A\)の対角線より下の要素たちを0にする操作を 前進消去 （Forward elimination)という

前進消去により

\[\begin{split} \begin{array}{r} x_1+a_{12}^{\prime} x_2+\cdots+a_{1 n}^{\prime} x_n=b_1^{\prime} \\ x_2+\cdots+a_{2 n}^{\prime} x_n=b_2^{\prime}\\ x_n=b_n^{\prime} \end{array} \end{split}\]

の形にすると、解は次のように求まる

\[\begin{split} \begin{aligned} & x_n=b_n^{\prime} \\ & x_{n-1}=b_{n-1}^{\prime}-a_{n-1, n}^{\prime} x_n \\ & \vdots \\ & x_1=b_1^{\prime}-\left(a_{12}^{\prime} x_2+\cdots+a_{1 n}^{\prime} x_n\right) \end{aligned} \end{split}\]

import numpy as np

# 拡大係数行列
A = np.array([
    [1, 1, 5],
    [2, 4, 14],
])

a = A[0, 0]
i = 1
j = 0

A[i, :] = A[i, :] - (A[i, j] / a)
A

array([[ 1,  1,  5],
       [ 0,  2, 12]])

解の種類#

\(n\) 変数の連立一次方程式 \(A x=b\) とし、拡大係数行列を \([A \mid b]\) で表す。

\(\operatorname{rank} A=\operatorname{rank}[A \mid b]=n \Longleftrightarrow\) ただ1つの解 \(x\)
\(\operatorname{rank} A=\operatorname{rank}[A \mid b]<n \Longleftrightarrow\) 不定解 \(x\)
- \(n\)個の変数に対して手がかりが足りず、解が一意に定まらない
\(\operatorname{rank} A<\operatorname{rank}[A \mid b] \Longleftrightarrow\) 解なし

https://jfor.net/indefinite-solution/

\(A\)が正則の場合#

もし逆行列が存在するなら

\[ x = A^{-1} y \]

と解くことができる

逆行列の推定への応用#

逆行列の推定方法の一つに連立一次方程式を解く方法がある

\(n\)次元正方行列\(A\)の逆行列は

\[ AX = I \]

となるような正方行列\(X\)であるため、\(n\)組の連立一次方程式\(A\b{x}_i = \b{e}_i \hspace{0.5em} (i = 1,\dots, n)\)を解く問題として扱うことができる

\(A\)が正則でない（特異な）場合#

連立一次方程式の解の存在性と一意性の条件

結果\(y\)から原因\(x\)を一意に特定できる（写像\(y=Ax\)は単射）⇔「\(\Ker A\)が原点\(o\)のみ」⇔「\(\Ker A\)は0次元」⇔「\(\rank A = n\)（ランクが定義域の次元と同じ）」
どんな結果\(y\)にも原因\(x\)が存在する（写像\(y=Ax\)は全射）⇔「\(\Im A\)が行き先の空間（値域）に一致する」⇔「\(\Im A\)は\(m\)次元」⇔「\(\rank A = m\)（ランクが値域の次元と同じ）」

クラーメルの公式#

クラーメルの公式

\(A\)が\(n\)次の正則行列であるとき、連立1次方程式

\[ Ax =b \]

はただ1組の解をもち、その解は次のように与えられる

\[ x_j = \frac{\Delta_j}{|A|} \quad (j=1,2,\cdots, n) \]

ここで\(\Delta_j\)は行列\(A\)の第\(j\)列をベクトル\(b\)で置き換えた行列式

例：

\[\begin{split} \begin{cases} x_1 + 2 x_2 = 10\\ 4 x_1 + x_2 = 12 \end{cases} \end{split}\]

を解け。

係数行列を\(A\)とすると、その行列式は

\[\begin{split} |A|=\left|\begin{array}{cc} 1 & 2\\ 4 & 1 \end{array}\right| = 1^2 - 8 = -7 \end{split}\]

それぞれの列を\(b=(10, 12)^T\)に置き換えた行列式は

\[\begin{split} \Delta_1 = \left|\begin{array}{cc} 10 & 2\\ 12 & 1 \end{array}\right| = 10 - 24 = -14 \\ \Delta_2 = \left|\begin{array}{cc} 1 & 10\\ 4 & 12 \end{array}\right| = 12 - 40 = -28 \end{split}\]

よって解は

\[\begin{split} x_1 = \frac{\Delta_1}{|A|} = \frac{-14}{-7} = 2\\ x_2 = \frac{\Delta_2}{|A|} = \frac{-28}{-7} = 4 \end{split}\]

連立一次方程式の計算の高速化#

幅広い行列に使える方法#

掃き出し法
直接解法（LU分解して解く）

特定のタイプの行列に使える方法#

対称正定値行列（例えば回帰モデルの\(X^T X\)）だと、
- コレスキー分解（LU分解の代わりに\(A=LL^T\)に分解する）
- 共役勾配法（\(f(x)=\frac{1}{2} x^T Ax - b^T x\)を最小化する\(x\)を求める形で反復計算して解く）

参考：

概要

Contents

概要#