Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

概要

連立1次方程式

Undefined control sequence: \DeclareMathOperator at position 57: …{#1}}
% 演算子の定義
\̲D̲e̲c̲l̲a̲r̲e̲M̲a̲t̲h̲O̲p̲e̲r̲a̲t̲o̲r̲{\im}{ \text{Im…

% 太字の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}

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

Undefined control sequence: \b at position 198: …, \hspace{1em}
\̲b̲{x} = \begin{pm…

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}

を用いて

Undefined control sequence: \b at position 2: A\̲b̲{x} = \b{y}

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

と表すことができる。

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

Undefined control sequence: \b at position 1: \̲b̲{x} = A^{-1} \b…

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

と解くことができる。

例題

{x+y=52x+4y=14\begin{cases} \begin{align} x + y &= 5\\ 2x + 4y &= 14 \end{align} \end{cases}
(5)

を例に考えてみる。

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

変数消去法
{x+y=52x+4y=14\begin{cases} \begin{align} x + y &= 5 \tag{1}\\ 2x + 4y &= 14 \tag{2} \end{align} \end{cases}
(6)

と番号をふる。

まず(1)を2倍して(2)から引き、(2)からxxの項を消す

{x+y=52y=4\begin{cases} \begin{align} x + y &= 5 \tag{1}\\ 2y &= 4 \tag{2'} \end{align} \end{cases}
(7)

(2’)を1/2倍すればy=2y = 2であることがわかる。

またy=2y = 2を(1)から引くと

{x=3y=2\begin{cases} \begin{align} x &= 3\\ y &= 2 \end{align} \end{cases}
(8)

となる

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

変数消去法（行列表記）
{x+y=52x+4y=14\begin{cases} x + y = 5\\ 2x + 4y = 14 \end{cases}
(9)

を行列で表すと

(1124)(xy)=(514)\begin{pmatrix} 1 & 1\\ 2 & 4 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 5\\ 14 \end{pmatrix}
(10)

となり、少し移項してブロック行列で表すと

(1152414)(xy−1)=(00)\left(\begin{array}{cc|c} 1 & 1 & 5\\ 2 & 4 & 14 \end{array}\right) \left(\begin{array}{c} x\\ y\\ \hline -1 \end{array}\right) = \begin{pmatrix} 0\\ 0 \end{pmatrix}
(11)

となる。

(1152414)\left(\begin{array}{cc|c} 1 & 1 & 5\\ 2 & 4 & 14 \end{array}\right)
(12)

は、まず1行目を2倍して2行目から引くと

(115024)\left(\begin{array}{cc|c} 1 & 1 & 5\\ 0 & 2 & 4 \end{array}\right)
(13)

となる。続いて、(1,2)(1, 2)要素をゼロにしたいので次に2行目を1/2倍して

(115012)\left(\begin{array}{cc|c} 1 & 1 & 5\\ 0 & 1 & 2 \end{array}\right)
(14)

2行目を1行目から引くと

(103012)\left(\begin{array}{cc|c} 1 & 0 & 3\\ 0 & 1 & 2 \end{array}\right)
(15)

もとの式に戻すと

(103012)(xy−1)=(x−3y−2)=(00)\left(\begin{array}{cc|c} 1 & 0 & 3\\ 0 & 1 & 2 \end{array}\right) \left(\begin{array}{c} x\\ y\\ \hline -1 \end{array}\right) = \begin{pmatrix} x - 3\\ y - 2 \end{pmatrix} = \begin{pmatrix} 0\\ 0 \end{pmatrix}
(16)

より、x=3,y=2x = 3, y = 2となる

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

Undefined control sequence: \b at position 74: …egin{array}{c}
\̲b̲{x}\\ \hline -1…

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

を変形していって

Undefined control sequence: \b at position 74: …egin{array}{c}
\̲b̲{x}\\ \hline -1…

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

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

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

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

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

変数消去法と同様に、

  1. 行のスカラー倍

  2. 行のスカラー倍を別の行に加算する

  3. 行の順番を入れ替える

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

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

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

前進消去により

x1+a12′x2+⋯+a1n′xn=b1′x2+⋯+a2n′xn=b2′xn=bn′\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}
(19)

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

xn=bn′xn−1=bn−1′−an−1,n′xn⋮x1=b1′−(a12′x2+⋯+a1n′xn)\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}
(20)
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]])

解の存在と一意性

連立一次方程式 Ax=bA\boldsymbol{x} = \boldsymbol{b} の解は、次のように分類される：

  1. 一意解（unique solution）：解がただ 1 つ存在する

  2. 不定解（infinite solutions）：無限個の解が存在する

  3. 解なし（no solution）：条件を満たす解が存在しない

係数行列 AA が正方行列（n×nn \times n）かつ 正則行列（逆行列が存在する）のとき、一意解が存在する。

過剰決定系と劣決定系

過剰決定系

方程式の数mmが未知数の数nnより多い場合（m>nm > n）を 過剰決定系（overdetermined system） という

Ax=b(A は m×n 行列、m>n)A\boldsymbol{x} = \boldsymbol{b} \quad (A \text{ は } m \times n \text{ 行列、} m > n)
(21)

一般に厳密な解は存在しないが、最小二乗法で近似解を求められる。

min⁡x∥b−Ax∥2\min_{\boldsymbol{x}} \|\boldsymbol{b} - A\boldsymbol{x}\|^2
(22)

これは線形回帰問題そのもの。

劣決定系

方程式の数が未知数の数より少ない場合（m<nm < n）を 劣決定系（underdetermined system） という

Ax=b(A は m×n 行列、m<n)A\boldsymbol{x} = \boldsymbol{b} \quad (A \text{ は } m \times n \text{ 行列、} m < n)
(23)

解が無数に存在する。通常は、ノルムが最小の解を求める：

min⁡x∥x∥2subject toAx=b\min_{\boldsymbol{x}} \|\boldsymbol{x}\|^2 \quad \text{subject to} \quad A\boldsymbol{x} = \boldsymbol{b}
(24)

解の種類

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

  • rank⁡A=rank⁡[A∣b]=n⟺\operatorname{rank} A=\operatorname{rank}[A \mid b]=n \Longleftrightarrow ただ1つの解 xx

  • rank⁡A=rank⁡[A∣b]<n⟺\operatorname{rank} A=\operatorname{rank}[A \mid b]<n \Longleftrightarrow 不定解 xx

    • nn個の変数に対して手がかりが足りず、解が一意に定まらない

  • rank⁡A<rank⁡[A∣b]⟺\operatorname{rank} A<\operatorname{rank}[A \mid b] \Longleftrightarrow 解なし

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

解を持つための条件

（※(A,b)(A, \boldsymbol{b})は拡大係数行列）

証明1

解をもつ ⟹rank⁡A=rank⁡(A,b)\Longrightarrow \operatorname{rank} A=\operatorname{rank}(A, \boldsymbol{b}) について

Ax=bA \boldsymbol{x}=\boldsymbol{b} が解をもつ，すなわちこの式をみたす x\boldsymbol{x} が存在するとき、この式を書き直すと

x1a1+x2a2+⋯+xmam=bx_1 \boldsymbol{a}_{\mathbf{1}}+x_2 \boldsymbol{a}_{\mathbf{2}}+\cdots+x_m \boldsymbol{a}_m = \boldsymbol{b}
(26)

となる。特に、bb が a1,a2,…,ama_1, a_2, \ldots, a_m の一次結合でかけている。ランクの定義は、一次独立な列ベクトルの最大個数であるから、 rank⁡A=rank⁡(A,b)\operatorname{rank} A=\operatorname{rank}(A, \boldsymbol{b}) である。

rank⁡A=rank⁡(A,b)⟹\operatorname{rank} A=\operatorname{rank}(A, \boldsymbol{b}) \Longrightarrow 解をもつについて

ランクの定義は，一次独立な列ベクトルの最大個数である。特に，rank A=nA=n とすると， a1,a2,…,ama_1, a_2, \ldots, a_m から，nn 個の一次独立なベクトルが選べる。仮定より，bb は，選んだ nn 個の一次独立なベクトルの一次結合で表せる。特に

b=x1a1+x2a2+⋯+xmam\boldsymbol{b}=x_1 \boldsymbol{a}_1+x_2 \boldsymbol{a}_2+\cdots+x_m \boldsymbol{a}_m
(27)

となる x=(x1x2⋮xm)\boldsymbol{x}=\left(\begin{array}{c}x_1 \\ x_2 \\ \vdots \\ x_m\end{array}\right) が存在する。これは、 Ax=b\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b} を意味し、解をもつことが分かった。

（出所：連立一次方程式が解をもつ条件(行列)とその証明 | 数学の景色）

証明2
 連立 1 次方程式 Ax=b が解をもつ。 ⟺Im⁡A∋b⟺x1a1′+⋯+xmam′=b をみたす x=(x1⋮xm) が存在する .⟺S[a1′,⋯ ,am′]∋b⟺S[a1′,⋯ ,am′]=S[a1′,⋯ ,am′,b](∵spanのなかにあるbを追加しても張れる空間は広がらない)⟺dim⁡S[a1′,⋯ ,am′]=dim⁡S[a1′,⋯ ,am′,b]⟺rank⁡A=rank⁡(A,b)\begin{aligned} &\text { 連立 } 1 \text { 次方程式 } A \boldsymbol{x}=\boldsymbol{b} \text { が解をもつ。 }\\ &\begin{aligned} & \Longleftrightarrow \operatorname{Im} A \ni \boldsymbol{b} \\ & \Longleftrightarrow x_1 \boldsymbol{a}_1^{\prime}+\cdots+x_m \boldsymbol{a}_m^{\prime}=\boldsymbol{b} \text { をみたす } \boldsymbol{x}=\left(\begin{array}{c} x_1 \\ \vdots \\ x_m \end{array}\right) \text { が存在する } . \\ & \Longleftrightarrow S\left[\boldsymbol{a}_1^{\prime}, \cdots, \boldsymbol{a}_m^{\prime}\right] \ni \boldsymbol{b} \\ & \Longleftrightarrow S\left[\boldsymbol{a}_1^{\prime}, \cdots, \boldsymbol{a}_m^{\prime}\right] =S\left[\boldsymbol{a}_1^{\prime}, \cdots, \boldsymbol{a}_m^{\prime}, \boldsymbol{b}\right] \quad (\because \text{spanのなかにあるbを追加しても張れる空間は広がらない} )\\ & \Longleftrightarrow \operatorname{dim} S\left[\boldsymbol{a}_1^{\prime}, \cdots, \boldsymbol{a}_m^{\prime}\right]=\operatorname{dim} S\left[\boldsymbol{a}_1^{\prime}, \cdots, \boldsymbol{a}_m^{\prime}, \boldsymbol{b}\right] \\ & \Longleftrightarrow \operatorname{rank} A=\operatorname{rank}(A, \boldsymbol{b}) \end{aligned} \end{aligned}
(28)

出所：川久保勝夫. (2010). 線形代数学.

ただ1つの解を持つための条件

（※(A,b)(A, \boldsymbol{b})は拡大係数行列）

証明

解がただーつ ⟹rank⁡A=rank⁡(A,b)=n\Longrightarrow \operatorname{rank} A=\operatorname{rank}(A, \boldsymbol{b})=n について

仮定より、

x1a1+x2a2+⋯+xnan=bx_1 \boldsymbol{a}_1+x_2 \boldsymbol{a}_2+\cdots+x_n \boldsymbol{a}_n=\boldsymbol{b}
(30)

をみたす x1,x2,…,xnx_1, x_2, \ldots, x_n がただ一つである。これは， a1,a2,…,an\boldsymbol{a}_{\mathbf{1}}, \boldsymbol{a}_{\mathbf{2}}, \ldots, \boldsymbol{a}_{\boldsymbol{n}} が1次独立 であることを示している。実際，1次独立でない、すなわち

k1a1+k2a2+⋯+knan=0k_1 \boldsymbol{a}_{\mathbf{1}}+k_2 \boldsymbol{a}_{\mathbf{2}}+\cdots+k_n \boldsymbol{a}_{\boldsymbol{n}}=\mathbf{0}
(31)

をみたす (k1,k2,…,kn)≠0\left(k_1, k_2, \ldots, k_n\right) \neq \mathbf{0} が存在すると仮定すると、（1），（2）の辺々足し合わせることで x′=(x1+k1x2+k2⋮xn+kn)\boldsymbol{x}^{\prime}=\left(\begin{array}{c}x_1+k_1 \\ x_2+k_2 \\ \vdots \\ x_n+k_n\end{array}\right) も連立方程式の解になり、解の一意性に反するからである。

ランクの定義は，一次独立な列ベクトルの最大個数であったから， rank⁡A=n\operatorname{rank} A=n である。

rank⁡A=rank⁡(A,b)=n⟹\operatorname{rank} A=\operatorname{rank}(A, \boldsymbol{b})=n \Longrightarrow 解がただ一つについて

2つの解を x(1),x(2)\boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)} とおく。これが一致していることを示せばよい。 Ax(1)=b,Ax(2)=bA \boldsymbol{x}^{(1)}= \boldsymbol{b}, A \boldsymbol{x}^{(2)}=\boldsymbol{b} の辺々引くと，

A(x(1)−x(2))=0A\left(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\right)=\mathbf{0}
(32)

となる。これを展開すると，

(x1(1)−x1(2))a1+⋯+(xn(1)−xn(2))an=0\left(x_1^{(1)}-x_1^{(2)}\right) \boldsymbol{a}_{\mathbf{1}}+\cdots+\left(x_n^{(1)}-x_n^{(2)}\right) \boldsymbol{a}_{\boldsymbol{n}}=\mathbf{0}
(33)

である。ランクの定義は，一次独立な列ベクトルの最大個数より， rank⁡A=n\operatorname{rank} A=n の仮定から，a1,a2,…,ana_1, a_2, \ldots, a_n は一次独立である。すなわち，

x1(1)−x1(2)=⋯=xn(1)−xn(2)=0x_1^{(1)}-x_1^{(2)}=\cdots=x_n^{(1)}-x_n^{(2)}=0
(34)

となるから，x(1)=x(2)x^{(1)}=x^{(2)} を得る。

（出所：連立一次方程式が解をもつ条件(行列)とその証明 | 数学の景色）

AAが正則の場合

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

x=A−1yx = A^{-1} y
(35)

と解くことができる

証明

∣A∣≠0|A|\neq 0とすると、AAの逆行列A−1A^{-1}が存在する。

連立一次方程式の両辺にA−1A^{-1}をかけると

A−1(Ax)=A−1bA^{-1} (A x) = A^{-1} b
(37)

行列の積は結合法則を満たすから、上式の左辺は

(A−1A)x=Ix=x(A^{-1} A) x = I x = x
(38)

よって

x=A−1bx = A^{-1} b
(39)

逆行列の推定への応用

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

nn次元正方行列AAの逆行列は

AX=IAX = I
(40)

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

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

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

  • 結果yyから原因xxを一意に特定できる（写像y=Axy=Axは単射）⇔「\Ker Aが原点ooのみ」⇔「\Ker Aは0次元」⇔「\rank A = n（ランクが定義域の次元と同じ）」

  • どんな結果yyにも原因xxが存在する（写像y=Axy=Axは全射）⇔「ℑA\Im Aが行き先の空間（値域）に一致する」⇔「ℑA\Im Aはmm次元」⇔「\rank A = m（ランクが値域の次元と同じ）」

クラーメルの公式

証明

仮定より∣A∣≠0|A|\neq 0であるから、x=A−1b\boldsymbol{x} = A^{-1} \boldsymbol{b}という解がただひとつ存在する。

AAの列ベクトルをa1,⋯ ,an\boldsymbol{a}_1, \cdots, \boldsymbol{a}_nとすると

b=Ax=(a1,⋯ ,an)x=x1a1+⋯+xnan\def\b#1{ \boldsymbol{#1} } \b{b} = A \b{x} = (\b{a}_1, \cdots, \b{a}_n) \b{x} = x_1 \b{a}_1 + \cdots + x_n \b{a}_n
(43)

AAの第jj列をb\boldsymbol{b}で置き換えた行列の行列式を考える。

∣a1⋯b⏟第j列⋯an∣\begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \underbrace{ \boldsymbol{b} }_{第j列} &\cdots & \boldsymbol{a}_n| \end{array}
(44)

\b{b} = x_1 \b{a}_1 + \cdots + x_n \b{a}_nなので

Undefined control sequence: \b at position 68: …nderbrace{ x_1 \̲b̲{a}_1 + \cdots …

\begin{array}{ccccc}
|\boldsymbol{a}_1 & \cdots & \underbrace{ x_1 \b{a}_1 + \cdots + x_n \b{a}_n }_{第j列} &\cdots & \boldsymbol{a}_n|
\end{array}

「1つの列をcc倍すると行列式はcc倍になる」という定理より

x1∣a1⋯a1⋯an∣+x2∣a1⋯a2⋯an∣+⋯+xj∣a1⋯aj⋯an∣+⋯+xn∣a1⋯an⋯an∣x_1 \begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \boldsymbol{a}_1 &\cdots & \boldsymbol{a}_n| \end{array} + x_2 \begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \boldsymbol{a}_2 &\cdots & \boldsymbol{a}_n| \end{array} \\ + \cdots + x_j \begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \boldsymbol{a}_j &\cdots & \boldsymbol{a}_n| \end{array} + \cdots + x_n \begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \boldsymbol{a}_n &\cdots & \boldsymbol{a}_n| \end{array}
(46)

jj番目以外は2つの列が等しいため、「2つの列が等しい行列の行列式は0になる」という定理により0になり、jj番目の項のみ残る

xj∣a1⋯aj⋯an∣=xj∣A∣x_j \begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \boldsymbol{a}_j &\cdots & \boldsymbol{a}_n| \end{array} = x_j |A|
(47)

したがって、行列AAの第jj列をbbに入れ替えた行列の行列式はxj∣A∣x_j |A|と等しくなる

∣a1⋯b⋯an∣=xj∣A∣\begin{array}{ccccc} |\boldsymbol{a}_1 & \cdots & \boldsymbol{b} &\cdots & \boldsymbol{a}_n| \end{array} = x_j |A|
(48)

この両辺を∣A∣|A|で割るとクラーメルの公式になる

例：

{x1+2x2=104x1+x2=12\begin{cases} x_1 + 2 x_2 = 10\\ 4 x_1 + x_2 = 12 \end{cases}
(49)

を解け。

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

∣A∣=∣1241∣=12−8=−7|A|=\left|\begin{array}{cc} 1 & 2\\ 4 & 1 \end{array}\right| = 1^2 - 8 = -7
(50)

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

Δ1=∣102121∣=10−24=−14Δ2=∣110412∣=12−40=−28\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
(51)

よって解は

x1=Δ1∣A∣=−14−7=2x2=Δ2∣A∣=−28−7=4x_1 = \frac{\Delta_1}{|A|} = \frac{-14}{-7} = 2\\ x_2 = \frac{\Delta_2}{|A|} = \frac{-28}{-7} = 4
(52)

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

幅広い行列に使える方法

  • 掃き出し法

  • 直接解法（LU分解して解く）

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

  • 対称正定値行列（例えば回帰モデルのXTXX^T X）だと、

    • コレスキー分解（LU分解の代わりにA=LLTA=LL^Tに分解する）

    • 共役勾配法（f(x)=12xTAx−bTxf(x)=\frac{1}{2} x^T Ax - b^T xを最小化するxxを求める形で反復計算して解く）

参考：

数学
連立1次方程式
数学
同次連立1次方程式