概要

概要#

連立1次方程式#

\begin{array}{r} {\begin{cases} \begin{aligned} a_{11} x_{1} + a_{12} x_{2} + & \dots + a_{1 m} x_{m} = y_{1} \\ a_{21} x_{1} + a_{22} x_{2} + & \dots + a_{2 m} x_{m} = y_{2} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} + & \dots + a_{n m} x_{m} = y_{n} \end{aligned} \end{cases} \end{array}

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

\begin{array}{r} A = (\begin{array}{c} a_{11} & a_{12} & \dots & a_{1 m} \\ a_{21} & a_{22} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n m} \end{array}), x = (\begin{array}{c} x_{1} \\ x_{2} \\ ⋮ \\ x_{m} \end{array}), y = (\begin{array}{c} y_{1} \\ y_{2} \\ ⋮ \\ y_{n} \end{array}) \end{array}

を用いて

A x = y

と表すことができる。

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

x = A^{- 1} y

と解くことができる。

例題#

\begin{array}{r} {\begin{cases} \begin{aligned} x + y & = 5 \\ 2 x + 4 y & = 14 \end{aligned} \end{cases} \end{array}

を例に考えてみる。

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

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

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

\begin{array}{r} (\begin{array}{cc} A & y \end{array}) (\begin{array}{c} x \\ - 1 \end{array}) = 0 \end{array}

を変形していって

\begin{array}{r} (\begin{array}{cc} I & z \end{array}) (\begin{array}{c} x \\ - 1 \end{array}) = 0 \end{array}

という形にする。 $x - z = 0$ となり、 $z$ のところに解が現れる。

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

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

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

変数消去法と同様に、

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

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

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

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

前進消去により

\begin{array}{r} \begin{matrix} x_{1} + a_{12}^{'} x_{2} + \dots + a_{1 n}^{'} x_{n} = b_{1}^{'} \\ x_{2} + \dots + a_{2 n}^{'} x_{n} = b_{2}^{'} \\ x_{n} = b_{n}^{'} \end{matrix} \end{array}

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

\begin{array}{r} \begin{aligned} x_{n} = b_{n}^{'} \\ x_{n - 1} = b_{n - 1}^{'} - a_{n - 1, n}^{'} x_{n} \\ ⋮ \\ x_{1} = b_{1}^{'} - (a_{12}^{'} x_{2} + \dots + a_{1 n}^{'} x_{n}) \end{aligned} \end{array}

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 ∣ b]$ で表す。

$rank A = rank [A ∣ b] = n ⟺$ ただ1つの解 $x$
$rank A = rank [A ∣ b] < n ⟺$ 不定解 $x$
- $n$ 個の変数に対して手がかりが足りず、解が一意に定まらない
$rank A < rank [A ∣ b] ⟺$ 解なし

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

$A$ が正則の場合#

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

x = A^{- 1} y

と解くことができる

定理

連立一次方程式 $A x = b$ があるとする。

もし $| A | \neq 0$ なら、 $A x = b$ はただ1つの解をもち、その解は

x = A^{- 1} b

で与えられる。

逆行列の推定への応用#

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

$n$ 次元正方行列 $A$ の逆行列は

A X = I

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

$A$ が正則でない（特異な）場合#

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

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

クラーメルの公式#

クラーメルの公式

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

A x = b

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

x_{j} = \frac{Δ_{j}}{| A |} (j = 1, 2, \dots, n)

ここで $Δ_{j}$ は行列 $A$ の第 $j$ 列をベクトル $b$ で置き換えた行列式

例：

\begin{array}{r} {\begin{cases} x_{1} + 2 x_{2} = 10 \\ 4 x_{1} + x_{2} = 12 \end{cases} \end{array}

を解け。

係数行列を $A$ とすると、その行列式は

\begin{array}{r} | A | = | \begin{array}{cc} 1 & 2 \\ 4 & 1 \end{array} | = 1^{2} - 8 = - 7 \end{array}

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

\begin{array}{r} Δ_{1} = | \begin{array}{cc} 10 & 2 \\ 12 & 1 \end{array} | = 10 - 24 = - 14 \\ Δ_{2} = | \begin{array}{cc} 1 & 10 \\ 4 & 12 \end{array} | = 12 - 40 = - 28 \end{array}

よって解は

\begin{array}{r} x_{1} = \frac{Δ_{1}}{| A |} = \frac{- 14}{- 7} = 2 \\ x_{2} = \frac{Δ_{2}}{| A |} = \frac{- 28}{- 7} = 4 \end{array}

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

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

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

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

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

参考：

概要

Contents

概要#

連立1次方程式#

例題#

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

解の種類#

$A$ が正則の場合#

逆行列の推定への応用#

$A$ が正則でない（特異な）場合#

クラーメルの公式#

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

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

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

参考文献#

概要

Contents

概要#

連立1次方程式#

例題#

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

解の種類#

Aが正則の場合#

逆行列の推定への応用#

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

クラーメルの公式#

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

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

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

参考文献#

$A$ が正則の場合#

$A$ が正則でない（特異な）場合#