Articles / 1月 25, 2022

Gram-Schmidt process

by Marco Taboga, PhD

Gram-Schmidt process（または手続き）は、線形独立なベクトルの集合を、元の集合によって広げられた同じ空間に渡る直交ベクトルの集合に変換できる一連の操作のことである。

予備知識

ここで、グラム・シュミット過程を理解する上で欠かせないいくつかの概念をおさらいしておきましょう。

2つのベクトルとは、それらの内積が0に等しい場合にのみ直交すると言われていること、つまり

内積が与えられると、次のようにベクトルのノルム（長さ）を定義できることを覚えておいてください。

ベクトルの集合は、その要素が単位ノルムを持ち、互いに直交している場合にのみ、直交性と呼ばれます。すなわち、個のベクトルの集合は、

以下の場合にのみ、直交正規集合のベクトルが線形独立であることを証明した。

直交集合への射影

グラム・シュミット法では次の命題を繰り返し用いるが、これはすべてのベクトルが1）直交集合への射影と2）与えられた直交集合に直交する残差に分解できることを示す。

命題は内積を備えたベクトル空間とする。また、を正規直交集合とする。任意のに対して、ここで $arepsilon _{S}$ は $u_{k}$ に対して、任意の

証明

定義すると、各に対して、ここで、以下のようになる。ステップとでは、内積がその第1引数に線形であることを利用している。ステップでは、正則集合を扱っているので、ならばという事実を使い、ステップでは、 $u_{j}$ のノルムは1に等しいという事実を使いました。したがって、上で定義した $arepsilon _{S}$ は、直交集合のすべての要素に直交しており、命題が証明される。

項はの直交集合への線形射影と呼ばれ、項 $arepsilon _{S}$ は線形射影の残差と呼ばれています。

正規化

また、グラム・シュミット処理で繰り返し使うことになる、おそらく明白な事実は、任意の非ゼロベクトルを取ってそのノルムで割ると、割った結果は単位ノルムを持つ新しいベクトルになることである。

つまり、ならば、ノルムの確定性により、

結果として、を定義でき、ノルムの正値性と絶対同値性により、以下のようになる。 6451>

手順の概要

さて、ベクトルの正規化方法と直交集合への射影と残差への分解方法がわかったので、グラム・シュミット手順を説明することにします。

ここではその概要を説明し、その後、命題として正式に表現し、技術的な詳細は命題の証明ですべて説明します。

ここでは概要です。線形独立なベクトルの集合が与えられています。

処理を始めるにあたり、最初のベクトルを正規化する、つまり

第二段階として、 $s_{2}$ を $u_{1}$ :に射影する、ここで $arepsilon _{2}$ は射影の残差である。

次に残差を正規化する：

出発ベクトルは線形独立なので、（正規化ができるように）後で証明することにする。

こうして得られた2つのベクトル $u_{1}$ と $u_{2}$ は、直交正規分布であることがわかる。

第三段階として、 $s_{3}$ を $u_{1}$ と $u_{2}$ :に射影し、その残差を計算する $arepsilon _{3}$ 。

そしてそれを正規化する： $u_{K}$ 最後の正規化残差を得るまでこの方法で進める。

プロセスの最後に、ベクトルは正規直交集合を形成する。なぜなら、

それらは正規化の結果であり、結果として単位ノルムを持つ。
それぞれの $u_{k}$ はに直交するという特性を持つ残余から得られたものである。

この概観を完成するために、の線形スパンはの線形結合として書くことができるすべてのベクトルの集合であり、それはで示され、線形空間であることを覚えておこう。

ベクトルはの線形独立結合なので、の線形結合として書ける任意のベクトルはの線形結合としても書くことができる。したがって、2つのベクトル集合のスパンは一致する。

Formal statement

我々はここでGram-Schmidt過程を命題として定式化し、その証明には手順のすべての技術的詳細が含まれている。

Proposition は内積が付いたベクタ空間とする。また、を線形独立なベクトルとする。このとき、任意のに対してとなるような直交ベクトル集合が存在する。

証明

証明は帰納法で、まずについて命題が成り立つことを証明し、次にについて成り立つなら一般についても真であることを証明します。のとき、ベクトルは単位ノルムを持ち、それだけで直交集合を構成する：他にベクトルはないので、直交条件は些細に満たされる。集合は $s_{1}$ のすべてのスカラー倍数の集合であり、それは $u_{1}$ のスカラー倍数でもある（逆もまたしかりである）。したがって、ここで、について命題が成立しているとする。すると、 $s_{k}$ を:上に投影することができ、ここで残差 $arepsilon _{k}$ はに直交していることがわかる。 $arepsilon_{k}=0$ であるとする。すると、仮定により、任意のに対して、 $α _{jl}$ はスカラーであることが分かる。したがって、つまり、 $arepsilon _{k}=0$ という仮定から、 $s_{k}$ はの線形結合であるという結論が導き出される。しかし、この命題の前提の1つはが線形独立であることなので、これは不可能である。結果的に、でなければならない。そこで残差を正規化し、単位ノルムを持つベクトルを定義すればよい。すでに $arepsilon _{k}$ がに直交していることが分かっています。このことから、 $u_{k}$ もに直交していることがわかります。よって、は直交集合である。さて、として書ける任意のベクトル（はスカラー）をとります。仮定により、式(2)は式(2370>はスカラー)とも書けるので、ステップでは式(1)、ステップでは $u_{k}$ の定義を使っていることになります。したがって、の線形結合として書けるすべてのベクトルは、の線形結合としても書けることが証明されました。仮定(3)により、完全に類似した方法で逆を証明することができます：言い換えれば、のすべての線形結合はの線形結合でもあるのです。これはを証明し、証明を終える。