グラム・シュミット・アルゴリズム(Gram-Schmidt Algorithm)は、有限の線形独立なベクトルを取ったとき、これらのベクトルが張る部分空間と同じ部分空間を張るための正規直交系を作り出します。
- 正規直交系とは何か？
- グラム・シュミット・アルゴリズムはどのようにして正規直交系を作るか？
- グラム・シュミット・アルゴリズムは何に利用できるか？
正規直交系
まず「正規直交系」って何ですか？
正規直交系(Orthonormal system)は、以下ふたつの条件を満たすベクトル集合です。
正規直交系のベクトルを\(q_1,…,q_k\)とすると、これらのベクトルは
- 全てのベクトルの長さは１: \(|| q_i || =1\)
- あらゆるベクトルの内積は０: \(q_{i}^{T} q_{j} = 0 \quad (i\neq j) \)
を満たします。
正規直交系のベクトルは線形独立であり、基底です。
以下、正規直交系のベクトルが線形独立となる証明です。
正規直交系のベクトルを\(q_1,…,q_k\)とおくと、線形結合は
$$\beta q_1+…+\beta_k q_k = 0$$
このとき、\(q_i\)とそれぞれのベクトルの内積をとると、\(q_{i} ^{T} q_j = 0\)、\(q_{i}^{T} q_i = 1\)より
$$\begin{aligned}0 &= a_{i} ^{T} (\beta q_1+…+\beta_k q_k)\\
&= \beta_1(q_{i} ^{T} q_1)+…+ \beta_1(q_{i} ^{T} q_1)\\
&= \beta_i
\end{aligned}$$
このとき\(\beta_i = 0\)である。\(\beta_1 q_1+…+\beta_k q_k = 0\)を満たすには、全ての\(\beta_i\)が0でなければいけない。
したがって、正規直交系のベクトルの線形結合は、線形独立である。
正規直交系のベクトルを正規直交基底(orthonormal basis)とも呼びます。
グラム・シュミット・アルゴリズム
グラム・シュミット・アルゴリズムは「直交化」「線形従属か確認」「正規化」の３ステップを実行し、ベクトル集合\(a_1,…,a_k\)から正規直交基底\(q_1,…q_k\)を作ります。
ここではグラム・シュミット・アルゴリズム(Gram-Schmidt Algorithm)の特徴をまとめます。
プロセス
グラム・シュミット・アルゴリズムは以下のステップを繰り返します。
\(a_1,…,a_k\)をn-ベクトルとすると
for \(i = 1,…,k\)において
- 直交化：\(\tilde{q_i}=a_i -(q_{1}^{T}a_i)q_1-…-(q_{i-1}^{T}a_i)q_{i-1}\)
- 線形従属か確認：\(\tilde{q_i}=0\)であれば、終了
- 正規化：\(q_i = \tilde{q_i} / \lVert\tilde{q_i}\lVert\)
直交化の式は何を意味しているんでしょうか？
正射影ベクトル(orthogonal projection)の公式です。ここでは、例えば、\(i=j、j<k\)とすると、\(i=j-1\)までに得た\( q_1,…,q_{j-1}\)の正規直交基底に対して直交する\(\tilde{q_j}\)をベクトル\(a_j\)から作ります。
数式だけ追うのではなく、Wikipediaのアニメーションがイメージを掴みやすいです。
数学記号は異なりますが、\(i = 1,2,3\) から順に、互いに直交するベクトルを作っています。
なぜ線形従属であることを確認する必要があるんでしょう？「\(\tilde{q_i}=0\)であれば、終了」ってどういう意味です？
\(k\)本の正規直交基底\(q_1,…q_k\)を作るため、与えられたベクトルが線形独立である必要があるからです。
\(i = j、j<k\)とし、\(\tilde{q_j}\)について考えてみます。
\(\tilde{q_j}=0\)ならば、直交化の式を変換すると
$$a_j = (q_{1}^{T}a_j)q_1 + … + (q_{j-1}^{T}a_j)q_{j-1}$$
となります。
これは\(a_j\)が\(q_1,…,q_{j-1}\)の線形結合であることを示します。
このとき、\(q_1,…,q_{j-1}\)のそれぞれは、\(a_1,…,a_{j-1}\)の線形結合です。
したがって、\(a_j\)は\(a_1,…,a_{j-1}\)の線形結合とも捉えられます。
つまり、\(\tilde{q_j}=0\)ならば、\(a_1,…,a_{j}\)は線形従属と言えます。この結果は、より大きな集合\(a_1,…,a_{k}\)が線形従属であることを意味します。
グラム・シュミット・アルゴリズムは、線形従属であるベクトルを入力すると、\(\tilde{q_i}=0\)となり、アルゴリズムを停止します。
最後の正規化は、\(\tilde{q_i}\)の長さを１にする操作です。
線形独立・従属判定への利用
グラム・シュミット・アルゴリズムは、単に正規直交基底を作るだけでなく、与えられたベクトル集合の線形独立・従属判定にも利用できます。
\(a_1,…a_k\)のベクトルが与えられ、グラム・シュミット・アルゴリズムを実行したとき、以下２つの結論を導けます。
- \(i=k\)までに\(\tilde{q_i} \neq 0\)ならば、入力ベクトルは線形独立。
- \(i=k\)までに\(\tilde{q_i}=0\)となれば、入力ベクトルは線形従属。
Juliaで確認
Juliaでグラム・シュミット・アルゴリズムを追ってみます。
簡単な例として、２つのベクトル\(a_1, a_2\)を使って、グラム・シュミット・アルゴリズムを実行してみます。
グラム・シュミット・アルゴリズムから\(q_1, q_2\)が得られ、これらが正規直交系の基底になります。
これら2本のベクトルは互いに直交しています。\(q_{i}^{T} q_{i} = 1, \quad q_{i}^{T} q_j = 0\)ですから、\(Q^{T}Q\)は単位行列\(I\)になります。
まとめ
以下、グラム・シュミット・アルゴリズムについてまとめます。
- 線形独立なベクトル集合から正規直交基底を作る方法
- アルゴリズムは\(i=k\)となるまでに3stepを繰り返す
- 直交化
- 線形従属の確認
- 正規化
- 入力ベクトルの線形独立・従属判定にも利用可能
- \(Q^T Q\)は単位行列
正直、今のところ実務で見かける機会がないですが、良い復習になりました。
この記事は以上です。最後まで読んで頂きありがとうございました。
参考資料
(1) Wikipedia, Gram–Schmidt process (2022/3/21アクセス)
この記事は「グラム・シュミット・アルゴリズム」についてまとめます。