... の消去法を工夫したものとみなせる¹

LU分解 そのものは Gauss の消去法と無関係に定義され、 Gauss の消去法以外の方法で計算することも可能である。 Gauss の消去法は LU 分解を求めるための代表的なアルゴリズムである、 というに過ぎない。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... (証明を省略して²

大部分は簡単であるから、 自分で証明を試みるとよい。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 逆行列は下三角行列である³

証明は、 例えば桂田 [4] の第4章 (2009年9月24日現在) に書いてある。 一つの証明のアウトラインを書いておく: $A=(a_{ij})$, $B=(b_{ij})$ を共に下三角行列で、$A B=I$, $\forall i$ $a_{ii}\ne 0$ が成り立つとすると、 $b_{ij}$ が簡単に求められる。 なお、後の余談 2.1 も見よ。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... のすべての主座小行列式⁴

$A$ の $k$ 次の主座小行列 (首座小行列とも呼ぶ) とは、 $A$ の最初の $k$ 行 $k$ 列から得られる $k$ 次の正方行列のことをいう。 その行列式のことを $k$ 次の主座行列式と呼ぶ。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 適当な置換行列⁵

知らないという人がいたので、 簡単に説明しておく。$i\ne j$ のとき、 $P_{ij}:=\dsp\sum_{k\ne i,j}E_{kk}+E_{ij}+E_{ji}$ とおくと、 $P_{ij} A$ は $A$ の第 $i$ 行と第$j$ 行が入れ替えた行列となる。 いくつかの $P_{ij}$ の積として得られる行列 $P$ を置換行列という。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 回の乗除算で十分である⁶

計算にどれくらい手間がかかるかを計るために、 基本的な演算の回数を数えるという方法がある。 しばしば、 四則演算のそれぞれについて数える代りに、 乗除算の回数だけを数えて目安にする、という手段が採用される (4次元ベクトルよりは1つの数値が分かりやすい)。 もう少し詳しいことが知りたければ、 例えば桂田 [4] を見よ。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... けることになる⁷

細かい話をすると、 $L$ が単位下三角行列である場合は、 割り算の回数が $n$ 回減って、 $n^2$ 回の乗除算で解けることになる。 逆行列を知っている場合、 連立1次方程式は $n^2$ 回の掛け算で解けるが、 それと互角であることが分かる。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... これは計算で示すことも出来るし⁸

$E_{ij}E_{k\ell} =\delta_{jk}E_{i\ell}$ という公式が成り立つことに注意すれば、 $i\ne k$ であれば $(I-q_{ik}E_{ik})(I+q_{ik}E_{ik}) =I-q_{ik}^2E_{ik}^2=I-q_{ik}^2\delta_{ik}E_{ik}=I-q_{ik}^2O=I$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... まだ説明していない概念⁹

例えば、 桂田 [4] などを見よ。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...実対称行列の符号¹⁰

符号の定義とか、 Sylvester の慣性律とか、線形代数で習うべきことだと思うが、 残念ながら授業では省略されることもあるようである。 定番の齋藤 [5], 佐武 [7] などを見よ。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...これから容易に¹¹

念のため書いておくと、 $\lambda^m$ が 0 に収束するために $\vert\lambda\vert<1$ が必要で、 逆にこのとき任意の $k$ に対して ${m\choose k}\lambda^{m-k}\to 0$ ( $m\to\infty$) が分かるので、$J^m\to O$ となるための十分条件である。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...この命題の証明を直接行うことも出来るが¹²

さわりの部分は $\sin\dfrac{(j-1)n\pi}{N} +\sin\dfrac{(j+1)n\pi}{N} =2\cos\dfrac{n\pi}{N}\sin\dfrac{jn\pi}{N}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... さらに、もしこの仮定が成り立たない、すなわち¹³

ド・モルガン則など、 論理の法則を使って計算すると、機械的に計算できる。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.