logo

グラム-シュミット直交化 📂線形代数

グラム-シュミット直交化

定理

すべての有限次元内積空間は正規直交基底を持つ。

説明

存在性の証明というものは大抵そうであるように、長くもなく重要ではないように見えるが、とてつもなく重要な定理だ。線形代数学を支える多くの論理がまさにこの正規直交基底が存在することに依存しているからだ。

証明

内積空間 $(V, \left\langle \cdot , \cdot \right\rangle)$ を生成する基底の一つを $\left\{ \mathbf{x}_{1} , \cdots , \mathbf{x}_{n} \right\}$ としよう。新しいベクトル

$$ \mathbf{v}_{1} := {{ \mathbf{x}_{1} } \over { \left\| \mathbf{x}_{1} \right\| }} $$

および

$$ {\color{blue} \mathbf{v}_{2}} := {{ {\color{red} \mathbf{x}_{2} - ( \mathbf{x}_{2} \cdot \mathbf{v}_{1} ) \mathbf{v}_{1} } } \over { \left\| \mathbf{x}_{2} - ( \mathbf{x}_{2} \cdot \mathbf{v}_{1} ) \mathbf{v}_{1} \right\| }} = {{ \mathbf{x}_{2} - \text{Proj} ( \mathbf{x}_{1} ) } \over { \left\| \mathbf{x}_{2} - \text{Proj} ( \mathbf{x}_{1} ) \right\| }} $$

を定義しよう。

20180120\_134426.png

図に示すように $\mathbf{v}_{1} \perp \mathbf{v}_{2}$ が成り立つ。このようなプロセスは

$$ \mathbf{v}_{k} := {{ \mathbf{x}_{k} - \text{Proj} ( \mathbf{x}_{k-1} ) } \over { \left\| \mathbf{x}_{k} - \text{Proj} ( \mathbf{x}_{k-1} ) \right\| }} $$ に対して繰り返すことができるため、直交基底 $\left\{ \mathbf{v}_{1} , \cdots , \mathbf{v}_{n} \right\}$ を見つけることができる。定義によって $\mathbf{v}_{1} , \cdots , \mathbf{v}_{n}$ はすべてその大きさが $1$ なので、 $\left\{ \mathbf{v}_{1} , \cdots , \mathbf{v}_{n} \right\}$ は正規直交ベクトルとなる。


実際には正規化は大きさが1になるようにノルムを割ればよく、重要なことは射影を利用して直交ベクトルを見つけることである。

コード

グラム・シュミットの直交化定理の証明はそれ自体がアルゴリズムのようなものだ。実際に与えられたランダム行列 X に対して正規直交化を行った行列 V は、各行ベクトル間の内積が $0$ であり、大きさが $1$ であることを確認できる。

julia> X = randn(3, 3)
3×3 Matrix{Float64}:
  0.0582107   0.414695  0.730785
 -0.740409   -0.885193  0.302674
  1.25107     0.840262  0.176503

julia> V = gram_schmidt(X)
3×3 Matrix{Float64}:
  0.0400097   0.739513  0.671952
 -0.508902   -0.563652  0.650626
  0.859894   -0.367989  0.353788

julia> V[1,:]'V[2,:], V[1,:]'V[3,:], V[2,:]'V[3,:]
(0.0, -8.326672684688674e-17, 1.1102230246251565e-16)

julia> norm(V[1,:]), norm(V[2,:]), norm(V[3,:])
(1.0, 0.9999999999999999, 1.0)

次はグラム・シュミットの直交正規化を行列で実行するジュリアコードだ。

using LinearAlgebra

function gram_schmidt(A)
    U = deepcopy(A)
    for i in axes(A, 1)
        for j in 1:(i-1)
            U[:, i] -= (U[:, i]'U[:, j])*U[:, j]/norm(U[:, j])
        end
        U[:, i] /= norm(U[:, i])
    end
    return U
end

X = randn(3, 3)
V = gram_schmidt(X)

V[1,:]'V[2,:], V[1,:]'V[3,:], V[2,:]'V[3,:]
norm(V[1,:]), norm(V[2,:]), norm(V[3,:])

リャプノフスペクトラム

リャプノフスペクトラムリャプノフスペクトラムを計算する際は、次のように正規直交行列 Uと共にユニットボールの軸がどのように変わるかを測定する直交行列 Vを同時に計算する関数が必要です。

using LinearAlgebra

function gram_schmidt(J)
    N = size(J, 1)
    U, V = deepcopy(J), deepcopy(J)
    U[:,1] = V[:,1] / norm(V[:,1])
    for j in 2:N
        for jp in 1:(j-1)
            V[:,j] -= (J[:,j]'U[:,jp])*U[:,jp]
        end
        U[:,j] = V[:,j] / norm(V[:,j])
    end
    return U, V
end

参照