Introduction to Linear Algebra Chapter 2

2019/03/24

この記事では世界標準MIT教科書 ストラング:線形代数イントロダクションの第2章をまとめる。

2.1 ベクトルと線形方程式

行ベクトルの絵・列ベクトルの絵

2変数を持つ方程式が2つ与えられ、それらが1つの解を持つ時:

方程式の行列表現

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$と呼ぶ。この行列にどのようなベクトルを掛けても、その内容は変わらない。つまり:

$$ Ix = x $$

2.2 消去の考え方

消去とは、方程式の行列表現$Ax = b$について$A$を上三角行列$U$に変換し、$Ux = c$を得ることである。

(前進)消去の手順

まず、消去に必要な用語を定義する。

M個の変数を持つ方程式がN個与えられた時、消去の手順は以下の通り。

  1. $a = 1, b = 1$
  2. 上から$a$つ目の等式$f[a]$からピボット$p$を探す
  3. aつ目の等式の下の等式$f[a + b]$について、$p$と同じ変数を持つ項の係数を、消去する項目$t$とする
  4. 乗数$t \div p$を計算する
  5. $f[a]$を乗数倍したものを$f[a + b]$から引く
  6. $b = b + 1$
  7. $b <= N$であれば手順3に戻る
  8. $a = a + 1$
  9. $a <= N - 1$であれば手順2に戻る

ピボットが0となる場合

消去の途中で等式$f[a]$のピボットが0となる時、ピボットが非零となるような方程式$f[a + b], b > 0$が存在する場合、$f[a]$と$f[a + b]$を交換することによりピボットを非零化することができる。

そのような$f[a + b]$が存在しない場合、その連立方程式は解無しもしくは無限個の解を持つ。

解無しとなる消去の破綻

以下の条件全てを満たす時、解無しとなる。

無限個の解を持つ消去の破綻

以下の条件全てを満たす時、無限個の解を持つ。

後進代入による連立方程式の解の求め方

(前進)消去により$A$から求めた$U$, $b$から求めた$c$を用いて、$Ux = c$ の下から順に方程式を解くことで連立方程式の解を得られる。この方程式を解く手順を後進代入と呼ぶ。

2.3 行列を使った消去

2.2にて述べた消去の手順を行列により表現する。

消去の1手順を表す行列$E_{ij}$

第j行の$\ell$倍を第$i$行から引くような行列を$E_{ij}$と呼び、それは対角行列$I$の(i,j)要素を$-\ell$に変えたものである。

行列積

消去の手順$EA$は行列同士の積である。行列積では以下が成り立つ。

  1. $A(BC) = (AB)C$
    • 結合法則が成り立つ
  2. 多くの場合 $AB \ne BA$
    • 可換法則が必ずしも成り立たない
  3. 行列$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つは重要。

  1. 行列$A$と$B$の各列の積

    $A$の各列ベクトルの線形結合となる。

  2. $A$の各行と行列$B$の積

    $A$の第i行が$B$全体に掛けられた結果が$AB$の第i行となる。

  3. $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つの法則に従う。

  1. $A + B = B + A$ (可換法則)
  2. $c(A + B) = cA + cB$ (分配法則)
  3. $A + (B + C) = (A + B) + C$ (結合法則)
  4. $C(A + B) = CA + CB$ (左からの分配法則)
  5. $(A + B)C = AC + BC$ (右からの分配法則)
  6. $A(BC) = (AB)C$ (ABCの結合法則)

通常$AB \neq BA$である。つまり可換法則は通常成立しない。

また、正方行列$A$については以下も成り立つ。

  1. $A^p = A \times A \times … \times A$ ($p$乗)
  2. $(A^p)(A^q) = A^{p + q}$
  3. $(A^p)^q = A^{pq}$

ブロック行列とブロック積

任意の行列はより小さな行列に切り分けることができる。この小さな行列をブロックと呼ぶ。

行列$A$の列の切り方と$B$の行の切り方が同じ場合、ブロック積$AB$の計算が可能。

$$ \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} & ... \ \\ B_{21} & B_{22} & ... \ \end{bmatrix} = \begin{bmatrix} A_{11}B_{11} + A_{12}B_{21} & ... \ \\ A_{21}B_{11} + A_{22}B_{21} & ... \ \end{bmatrix} $$

ブロックによる消去

消去をブロックを用いて簡単に表現することができる。

$$ \begin{bmatrix} \begin{array}{c|c} I & \bm{0} \\ \hline -CA^{-1} & I \end{array} \end{bmatrix} \begin{bmatrix} \begin{array}{c|c} A & B \\ \hline C & D \end{array} \end{bmatrix} = \begin{bmatrix} \begin{array}{c|c} A & B \\ \hline \bm{0} & D - CA^{-1}B \end{array} \end{bmatrix} $$

$D - CA^{-1}B$はシューアの補行列と呼ばれる。

$-CA^{-1}$は$\ell$の定義と消去の1手順を表す行列$E_{ij}$により明らか。

ここでは消去する項目を$C$, ピボット$A$で割ることを$A^{-1}$と表している。

2.5 逆行列

逆行列の定義

$A$が正方行列であるとき、$A^{-1}A = I$となるような$A^{-1}$を$A$の逆行列と呼ぶ。全ての行列が逆行列を持つわけではない。

逆行列を用いた可逆の定義

以下を全て満たす行列$A^{-1}$が存在する時、行列$A$は可逆である。

$$ A^{-1}A = I \\ AA^{-1} = I $$

逆行列の特徴

  1. 消去と行交換によって$n$個のピボットができる時、またその時に限り逆行列が存在する
  2. 行列$A$が2つ以上の異なる逆行列を持つことはない
  3. $A$が可逆ならば、$Ax = b$の唯一解は$x = A^{-1}b$である
  4. $Ax = \bm{0}$を満たす非零ベクトル$x$が存在する時、$A$は逆行列を持たない
  5. $2 \times 2$の行列$[a \ b; c \ d]$は、$ad - bc$が0でない時、またその時に限り可逆である
  6. 対角行列は対角要素に0がなければ逆行列を持つ

特徴2から、右側から掛ける逆行列(右逆行列)と左側から掛ける逆行列(左逆行列)が等しいことが分かる。

特徴5は$2 \times 2$の行列の逆行列から確認可能。また$ad - bc$を行列式と呼ぶ。(行列式について詳しくは後述)

$$ \begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix} $$

積$AB$の逆行列

$A$と$B$が可逆である時$AB$も可逆であり、以下のように表される。

$$ (AB)^{-1} = B^{-1}A^{-1} $$

3つ以上の行列の積についても同様に逆順となる。

正則行列$A$では、ある側の逆行列は自動的に反対側の逆行列となる。つまり$A^{-1}A = AA^{-1} = I$

ガウス-ジョルダンの消去法による$A^{-1}$の計算

$[A \ I] \times A^{-1} = [I \ A^{-1}]$を解くことで$A$の逆行列を計算する。この方法をガウス-ジョルダンの消去法と呼ぶ。

ガウス-ジョルダンの消去法は3つの段階に分かれる。

  1. $[A \ I]$について前進消去を行う
  2. 各ピボットの上の行についても消去を行う
  3. 各行をピボットで割る

段階3が終わった時点の、元々$I$であった部分が$A^{-1}$となる。

対称行列

行列$A$の要素$a_{ij}$について以下が成り立つ時、$A$を対称行列と呼ぶ。

$$ a_{ij} = a_{ji} $$

三重対角行列

行列$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$を掛けたものである。

$$ (E_{32}E_{31}E_{21})A = U \Longleftrightarrow A = (E_{21}^{-1}E_{31}^{-1}E_{32}^{-1})U = LU $$

$L$の要素$(i, j)$が$\ell_{ij}$となる理由

$L$の要素$(i, j)$は$\ell_{ij}$となる。

つまり、消去の手順の逆行列$E_{ij}^{-1}$は他の手順の影響を受けない。これは以下のように確かめられる。

$$ (Uの第n行) \ = \ (Aの第n行) \ - \ \sum_{i=1}^{n-1} \ell_{ni}(Uの第i行) \\ \Longleftrightarrow (Aの第n行) \ = \ (Uの第n行) \ + \ \sum_{i=1}^{n-1} \ell_{ni}(Uの第i行) $$

2つ目の等式は$A = LU$の第$n$行そのものである。 $L$の要素$(n,i)$は($U$の第$i$行)の係数となる。

つまり、$LU$は$\ell_{ij}$と$U$の要素のみに依存する。$U$や$A$に何らかの処理を加えた未知の行には依存しない。

これが$L$の要素$(i, j)$が$\ell_{ij}$となる理由である。

$L$と$U$の要素0の予測

以下の特徴により計算時間を節約できる

$A = LDU$

$L$の対角要素が全て1であるのに対し、$U$の対角要素はピボットである。$L$と$U$の対角要素が一致しないため、$LU$分解は「非対称的」と呼ばれる。

これを対称的にするには、$U$に対してピボットから成る対角行列$D$を左から掛ける。

$$ LDU = L \begin{bmatrix} d_1 & \ & \ & \ \\ \ & d_2 & \ & \ \\ \ & \ & \ddots & \ \\ \ & \ & \ & d_n \end{bmatrix} \begin{bmatrix} 1 & \frac{u_{12}}{d_1} & \frac{u_{13}}{d_1} & \vdots \\ \ & 1 & \frac{u_{23}}{d_2} & \vdots \\ \ & \ & \ddots & \vdots \\ \ & \ & \ & 1 \end{bmatrix} $$

求解: bに対する前進消去と後退代入

Aの分解によりLとUを得ると、それを用いてbに前進消去と後退代入を行うことによりxを求めることができる。これを求解と呼ぶ。

  1. 前進消去

    Lに保存されている$l_{ij}$を用いて前進消去を行い、cを得る
    $Lc = b$を解くことに等しい

  2. 後退代入

    通常通り、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$が与えられた時、これらの和, 積, 逆行列の転置は以下のようになる。

$$ (A + B)^T = A^T + B^T \\ (AB)^T = B^TA^T \\ (A^{-1})^T = (A^T)^{-1} $$

積の転置の証明には、$Ax$は$A$の列を線形結合し、$x^TA^T$は$A^T$の行を線形結合することを用いる。

内積の意味

2.4 行列操作の規則 行列積の行と列で述べたように、行と列を用いて内積と外積が説明できる。

行と列の積から1つの数を導く手順が内積であるのに対し、3のように列と行の積から行列を導く手順は外積である。

これはベクトル$x$と$y$を用いて、以下のように言い換えることができる。

$$ x^Ty $$
$$ xy^T $$

この内積の表現を用いて、$A^T$を以下のように表すことができる。

$$ (Ax)^Ty = x^T(A^Ty) $$

つまり、$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$が可逆であることが唯一の必要条件である。