この記事では世界標準MIT教科書 ストラング:線形代数イントロダクションの第2章をまとめる。
2.1 ベクトルと線形方程式
行ベクトルの絵・列ベクトルの絵
2変数を持つ方程式が2つ与えられ、それらが1つの解を持つ時:
- 行ベクトルの絵
- 1点で交わる2つの直線で表される
- 一般的には、解が存在する場合にその解のところで交わる
- 列ベクトルの絵
- 左辺の列ベクトルの線形結合を取り、右辺のベクトル$b$を作る
- 一般的には、$Ax = b$となるような線形結合を求める
方程式の行列表現
M個の変数を持つ方程式がN個与えられた時、これらを行列の方程式$Ax = b$として表現することができる
$A$は$N \times M$の行列であり、方程式の変数に掛けられている各定数が入る。$x$は$M \times 1$のベクトルであり、各変数が入る。$b$は$M \times 1$のベクトルであり、各方程式の左辺が入る。
計算方法はChapter 1 1.3 行列 行列を用いた線形結合の表現の通り。
単位行列
主対角要素$a_{ii}$が1であり、それ以外が0であるような行列を単位行列$I$と呼ぶ。この行列にどのようなベクトルを掛けても、その内容は変わらない。つまり:
2.2 消去の考え方
消去とは、方程式の行列表現$Ax = b$について$A$を上三角行列$U$に変換し、$Ux = c$を得ることである。
(前進)消去の手順
まず、消去に必要な用語を定義する。
- ピボット
- 消去に使われる行のうち、左から見て最初に零でない係数
- 乗数$\ell$
- (消去する項目) $\div$ (ピボット)
- 消去する項目として上から$i$つ目の方程式, 左からj番目の項を使うものを$\ell_{ij}$と書く
M個の変数を持つ方程式がN個与えられた時、消去の手順は以下の通り。
- $a = 1, b = 1$
- 上から$a$つ目の等式$f[a]$からピボット$p$を探す
- aつ目の等式の下の等式$f[a + b]$について、$p$と同じ変数を持つ項の係数を、消去する項目$t$とする
- 乗数$t \div p$を計算する
- $f[a]$を乗数倍したものを$f[a + b]$から引く
- $b = b + 1$
- $b <= N$であれば手順3に戻る
- $a = a + 1$
- $a <= N - 1$であれば手順2に戻る
ピボットが0となる場合
消去の途中で等式$f[a]$のピボットが0となる時、ピボットが非零となるような方程式$f[a + b], b > 0$が存在する場合、$f[a]$と$f[a + b]$を交換することによりピボットを非零化することができる。
そのような$f[a + b]$が存在しない場合、その連立方程式は解無しもしくは無限個の解を持つ。
解無しとなる消去の破綻
以下の条件全てを満たす時、解無しとなる。
- 消去の手順の中でピボットが0になる
- 方程式の入れ替えによるピボットの非零化が不可能
- 等式 $0 =$ ($0$以外の数) が現れる
無限個の解を持つ消去の破綻
以下の条件全てを満たす時、無限個の解を持つ。
- 消去の手順の中でピボットが0になる
- 方程式の入れ替えによるピボットの非零化が不可能
- 等式 $0 = 0$ が現れる
後進代入による連立方程式の解の求め方
(前進)消去により$A$から求めた$U$, $b$から求めた$c$を用いて、$Ux = c$ の下から順に方程式を解くことで連立方程式の解を得られる。この方程式を解く手順を後進代入と呼ぶ。
2.3 行列を使った消去
2.2にて述べた消去の手順を行列により表現する。
消去の1手順を表す行列$E_{ij}$
第j行の$\ell$倍を第$i$行から引くような行列を$E_{ij}$と呼び、それは対角行列$I$の(i,j)要素を$-\ell$に変えたものである。
行列積
消去の手順$EA$は行列同士の積である。行列積では以下が成り立つ。
- $A(BC) = (AB)C$
- 結合法則が成り立つ
- 多くの場合 $AB \ne BA$
- 可換法則が必ずしも成り立たない
- 行列$B$が複数の列$b_1, b_2, b3$から成る時、$AB = A[b_1 \ b_2 \ b_3] = [Ab_1 \ Ab_2 \ Ab_3]$
- 言い換えると、$A$を任意の行列$B$に掛ける時、$A$は$B$の各列ベクトルに対して独立に掛けられる
行の交換のための行列$P_{ij}$
第i行と第j行を交換する行列を$P_{ij}$と呼び、それは対角行列$I$の第i行と第j行を交換したものである。
拡大行列
$Ax = b$について、$A$に$b$を追加の行として含めたものを拡大行列 $[A \ b]$と呼ぶ。
行列積の法則3により$E[A \ b] = [EA \ Eb]$が成り立つため、拡大行列により消去の手順を1つの行列としてまとめて行える。また、この法則は$A$と$b$の行・列どちらにも働く。
2.4 行列操作の規則
行列積の行数と列数
行列積$AB$を行うためには $A = n \times m, B = m \times p$ である必要があり、その結果は$n \times p$となる。計算量は$mnp$。
行列積の行と列
行列積$AB$は「行列$A$と$B$の各列の積」「$A$の各行と行列$B$の積」「$A$の各列と$B$の各行の積の合計」の3パターンで表現可能。特に最後の1つは重要。
-
行列$A$と$B$の各列の積
$A$の各列ベクトルの線形結合となる。
-
$A$の各行と行列$B$の積
$A$の第i行が$B$全体に掛けられた結果が$AB$の第i行となる。
-
$A$の各列と$B$の各行の積の合計
$n \times m$の行列$A$の第i列を$a_i$、$m \times p$の行列$B$の第j行を$b_j$とする。
この時$a_ib_j$は$N \times P$の行列となる。
$i$ ($1 \leq i \leq m$) について計算した行列$a_ib_i$を全て足し合わせたものは行列積$AB$となる。
行と列の積から1つの数を導く手順が内積であるのに対し、3のように列と行の積から行列を導く手順は外積である。
行列操作の法則
行列操作は以下の6つの法則に従う。
- $A + B = B + A$ (可換法則)
- $c(A + B) = cA + cB$ (分配法則)
- $A + (B + C) = (A + B) + C$ (結合法則)
- $C(A + B) = CA + CB$ (左からの分配法則)
- $(A + B)C = AC + BC$ (右からの分配法則)
- $A(BC) = (AB)C$ (ABCの結合法則)
通常$AB \neq BA$である。つまり可換法則は通常成立しない。
また、正方行列$A$については以下も成り立つ。
- $A^p = A \times A \times … \times A$ ($p$乗)
- $(A^p)(A^q) = A^{p + q}$
- $(A^p)^q = A^{pq}$
ブロック行列とブロック積
任意の行列はより小さな行列に切り分けることができる。この小さな行列をブロックと呼ぶ。
行列$A$の列の切り方と$B$の行の切り方が同じ場合、ブロック積$AB$の計算が可能。
ブロックによる消去
消去をブロックを用いて簡単に表現することができる。
$D - CA^{-1}B$はシューアの補行列と呼ばれる。
$-CA^{-1}$は$\ell$の定義と消去の1手順を表す行列$E_{ij}$により明らか。
-
$\ell$の定義
- 乗数$\ell$
- (消去する項目) $\div$ (ピボット)
- 乗数$\ell$
-
消去の1手順を表す行列$E_{ij}$
第j行の$\ell$倍を第$i$行から引くような行列を$E_{ij}$と呼び、それは対角行列$I$の(i,j)要素を$-\ell$に変えたものである。
ここでは消去する項目を$C$, ピボット$A$で割ることを$A^{-1}$と表している。
2.5 逆行列
逆行列の定義
$A$が正方行列であるとき、$A^{-1}A = I$となるような$A^{-1}$を$A$の逆行列と呼ぶ。全ての行列が逆行列を持つわけではない。
逆行列を用いた可逆の定義
以下を全て満たす行列$A^{-1}$が存在する時、行列$A$は可逆である。
逆行列の特徴
- 消去と行交換によって$n$個のピボットができる時、またその時に限り逆行列が存在する
- 行列$A$が2つ以上の異なる逆行列を持つことはない
- $A$が可逆ならば、$Ax = b$の唯一解は$x = A^{-1}b$である
- $Ax = \bm{0}$を満たす非零ベクトル$x$が存在する時、$A$は逆行列を持たない
- $2 \times 2$の行列$[a \ b; c \ d]$は、$ad - bc$が0でない時、またその時に限り可逆である
- 対角行列は対角要素に0がなければ逆行列を持つ
特徴2から、右側から掛ける逆行列(右逆行列)と左側から掛ける逆行列(左逆行列)が等しいことが分かる。
特徴5は$2 \times 2$の行列の逆行列から確認可能。また$ad - bc$を行列式と呼ぶ。(行列式について詳しくは後述)
積$AB$の逆行列
$A$と$B$が可逆である時$AB$も可逆であり、以下のように表される。
3つ以上の行列の積についても同様に逆順となる。
正則行列$A$では、ある側の逆行列は自動的に反対側の逆行列となる。つまり$A^{-1}A = AA^{-1} = I$
ガウス-ジョルダンの消去法による$A^{-1}$の計算
$[A \ I] \times A^{-1} = [I \ A^{-1}]$を解くことで$A$の逆行列を計算する。この方法をガウス-ジョルダンの消去法と呼ぶ。
ガウス-ジョルダンの消去法は3つの段階に分かれる。
- $[A \ I]$について前進消去を行う
- 各ピボットの上の行についても消去を行う
- 各行をピボットで割る
段階3が終わった時点の、元々$I$であった部分が$A^{-1}$となる。
対称行列
行列$A$の要素$a_{ij}$について以下が成り立つ時、$A$を対称行列と呼ぶ。
三重対角行列
行列$A$が非零要素が対角要素とその上下のみである時、$A$を三重対角行列と呼ぶ。この時一般に$A^{-1}$は要素0を含まない。
行列式
行列$A$のピボットの積を、$A$の行列式と呼ぶ。
$A^{-1}$は行列式による除算を伴う。つまり、行列式が0である場合は逆行列を持たない。
非可逆と可逆の対比
$A$がn個のピボットを持つ時にのみ、ガウス-ジョルダンの消去法により逆行列が求まる。
つまり$A$がn個のピボットを持つ時、かつその時に限り、$A^{-1}$が存在する。
2.6 消去 = 分解: A = LU
行列$A$が行の交換を伴わない場合、消去法の手順は$A = LU$で表すことができる。
行列$U$
$U$は消去法によって$A$から得られる、対角要素にピボットを持つ上三角行列である。2.2 消去の考え方で既に用いている。
行列$L$
$L$は消去の手順$E$の逆行列である。下三角行列であり、要素$(i,j)$に乗数$\ell_{ij}$を持つ。(理由後述)
例えば$3 \times 3$の行列$A$の場合、以下のようになる。$E_{ij}$の逆行列は要素$(i,j)$に$-1$を掛けたものである。
$L$の要素$(i, j)$が$\ell_{ij}$となる理由
$L$の要素$(i, j)$は$\ell_{ij}$となる。
つまり、消去の手順の逆行列$E_{ij}^{-1}$は他の手順の影響を受けない。これは以下のように確かめられる。
2つ目の等式は$A = LU$の第$n$行そのものである。 $L$の要素$(n,i)$は($U$の第$i$行)の係数となる。
つまり、$LU$は$\ell_{ij}$と$U$の要素のみに依存する。$U$や$A$に何らかの処理を加えた未知の行には依存しない。
これが$L$の要素$(i, j)$が$\ell_{ij}$となる理由である。
$L$と$U$の要素0の予測
以下の特徴により計算時間を節約できる
- $A$のある行が0から始まっていれば、$L$のその行も0から始まる
- $A$のある列が0から始まっていれば、$U$のその列も0から始まる
$A = LDU$
$L$の対角要素が全て1であるのに対し、$U$の対角要素はピボットである。$L$と$U$の対角要素が一致しないため、$LU$分解は「非対称的」と呼ばれる。
これを対称的にするには、$U$に対してピボットから成る対角行列$D$を左から掛ける。
求解: bに対する前進消去と後退代入
Aの分解によりLとUを得ると、それを用いてbに前進消去と後退代入を行うことによりxを求めることができる。これを求解と呼ぶ。
-
前進消去
Lに保存されている$l_{ij}$を用いて前進消去を行い、cを得る
$Lc = b$を解くことに等しい -
後退代入
通常通り、Uとcを用いて後進代入を行う。
$Ux = c$を解くことに等しい。
上記の表現を用いて、$Ux = c \Longleftrightarrow LUx = Lc \Longleftrightarrow Ax = b$となる。
消去の計算コスト
$n \times n$の行列Aについて、消去では$\frac{1}{3}(n^3 - n)$の掛け算と$\frac{1}{3}n^3$の足し算、求解では各右辺に対し$n^2$の掛け算と$n^2$の引き算が必要である。
主対角要素の上下に幅$w$の非零要素を持つものを帯行列と呼ぶ。帯行列では、分解の$\frac{1}{3}(n^3 - n)$が$nw^2$に、求解の$n^2$が$2nw$になる。
2.7 転置と置換
転置
行列Aの行を列に、列を行にすることを転置と呼び、その結果を$A^{T}$と表す。
転置は$n \times m$の行列を$m \times n$に変える。$A^{-1}$の第$i$行は第$i$列となり、第$j$行は第$j$列となる。
$A$が可逆である時、かつその時に限り$A^T$は可逆である。
行列の和, 積, 逆行列の転置
行列$A$と$B$が与えられた時、これらの和, 積, 逆行列の転置は以下のようになる。
積の転置の証明には、$Ax$は$A$の列を線形結合し、$x^TA^T$は$A^T$の行を線形結合することを用いる。
内積の意味
2.4 行列操作の規則 行列積の行と列で述べたように、行と列を用いて内積と外積が説明できる。
行と列の積から1つの数を導く手順が内積であるのに対し、3のように列と行の積から行列を導く手順は外積である。
これはベクトル$x$と$y$を用いて、以下のように言い換えることができる。
- 内積
- 外積
この内積の表現を用いて、$A^T$を以下のように表すことができる。
つまり、$Ax$と$y$の内積と、$x$と$By$の内積が等しくなるような行列$B$が$A^T$となる。
対称行列
$A^T = A$となる行列$A$を対称行列と呼ぶ。対称行列の逆行列も対称行列である。
任意の行列$R$がある時、$R^TR$と$RR^T$は正方対称行列となる。
行列$A$が対称行列であり、行の交換なしに$LDU$へと分解された時、$A = LDU = LDL^T$となる。
置換行列の転置
置換行列とは2.3 行列を使った消去 行の交換のための行列$P_{ij}$で述べた$P_{ij}$である。
$n \times n$の置換行列は$n!$個ある。このうち半分は偶置換であり、もう半分は奇置換である。
$P^{-1}$も置換行列であり、$P^{-1} = P^T$である。
行の交換を含む$PA = LU$分解
行列$A$に対して消去法を行う時、消去に必要な$P_{ij}$を全て掛けたものを$P$と表す。
予め$A$に$P$を掛けると、それ以降は交換無しに$LU$へと分解できる。つまり$PA = LU$。
この時、$A$が可逆であることが唯一の必要条件である。