[Linear Algebra]그람 슈미트(Gram-Schmidt) 과정

그람 슈미트(Gram-Schmidt) 과정

그람 슈미트 과정은 0이 아닌 $\mathbb{R}^n$의 부분공간에서 직교 또는 정규직교 기저를 생성하는 단순한 알고리즘입니다.

import numpy as np
import numpy.linalg as LA
from sympy import *

예 1)

부분공간 W = Span{x₁, x₂}일 때 W에 직교 기저인 {v₁, v₂}을 결정해 봅니다.

$$x_1 =\begin{bmatrix}3\\6\\0\end{bmatrix},\quad x_2=\begin{bmatrix}1\\2\\2\end{bmatrix}$$

그림 1은 두 기저벡터 x₁과 x₂에 의한 부분공간 W를 나타낸 것입니다. 즉, 두 벡터는 부분공간 W의 스판으로 W = Span{x₁, x₂}를 나타낸 것입니다.

그림 1. x₁, x₂를 기저벡터로 하는 부분공간 W.

그림 1에서 나타낸 것과 같이 부분공간 W에 직교벡터는 v₁와 v₂입니다. v₁는 x₁와 같으며 그 벡터 위로 x₂의 정사영은 벡터 p입니다. 그러므로 x₂는 식 2와 같이 계산됩니다.

$$\tag{식 1}x_2 = v_2 + p$$

기사 직교적 투영에서 소개한 식 4와 5를 적용하면 p와 v₂는 식 2와 같이 계산됩니다.

\begin{align} \tag{식 2} p&=\frac{x_2x_1}{x_1x_1}x_1\\v_2& = x_2- \frac{x_2x_1}{x_1x_1}x_1\end{align}

위 계산을 위한 코드는 다음과 같습니다.

x1=np.array([3,6,0]).reshape(-1,1)
print(x1)

[[3]
 [6]
 [0]]

x2=np.array([1,2,2]).reshape(-1,1)
print(x2)

[[1]
 [2]
 [2]]

def orthoCoefS(x, y):
    x=np.dot(x.T, y)
    y=np.dot(y.T, y)
    return(x/y)

p=orthoCoefS(x2,x1)*x1
print(p)

[[1.]
 [2.]
 [0.]]

v2=x2-p
print(v2)

[[0.]
 [0.]
 [2.]]

print(x2==p+v2)

[[ True]
 [ True]
 [ True]]

위 결과와 같이 x₂는 기저 벡터인 v₁, v₂를 스판으로 하는 부분 공간이 됩니다(식 3).

$$\tag{식 3}x_2=\text{span}\{v_1,\, v_2\}$$

식 3은 x₂는 v₁의 선형 결합은 선형독립이며 그 결과가 v₂임을 의미합니다.

v=np.hstack([x1,v2])
print(v)

[[3. 0.]
 [6. 0.]
 [0. 2.]]

au=np.hstack([v, x2])
print(au)

[[3. 0. 1.]
 [6. 0. 2.]
 [0. 2. 2.]]

print(np.array(Matrix(au).rref()[0], dtype=float).round(2)))

[[1.   0.   0.33]
 [0.   1.   1.  ]
 [0.   0.   0.  ]]

Matrix(v).columnspace()

[Matrix([
     [3.0],
     [6.0],
     [  0]]),
     Matrix([
     [  0],
     [  0],
     [2.0]])]

la.matrix_rank(v)

2

위 결과에 의하면 행렬 v의 모든 열이 피벗 열이고 행렬 v의 열공간의 차원과 급수(rank)가 2로서 같습니다. 이 결과는 위 결합이 선형독립이며 v의 각 열벡터는 기저벡터들로서 x₂의 스판임을 의미합니다.

위 예의 계산과정은 다음과 같이 정리됩니다.

1. v₁ = x₁
2. x₂는 v₂와 v₁ 위로 x₂의 직교투영(정사영)인 p와의 합으로 나타낼 수 있으므로 v₂는 식 4와 같이 정리됩니다.

\begin{align}x_2& = v_2+p\\&= v_2 +\frac{x_2x_1}{x_1x_1}x_1\\ &= v_2 +\frac{x_2v_1}{v_1v_1}v_1\\ v_2 &= x_2-\frac{x_2x_1}{x_1x_1}x_1 \tag{식 4} \\ & =x_2-\frac{x_2v_1}{v_1v_1}v_1 \end{align}

식 4는 어떤 공간의 직교 기저 벡터들을 계산하는 Gram-Schmit 과정으로 식 5와 같이 일반화 할 수 있습니다. 즉, ℝⁿ의 0이 아닌 부분공간 W의 기저가 {x₁, x₂, …, x_p}라면 W에 직교기저는 {v₁, v₂, …, v_p}는 다음과 같이 계산할 수 있습니다.

\begin{align}v_1 & =x_1\\ v_2 & = x_2-\frac{x_2v_1}{v_1v_1}v_1\\ v_3& = x_3-\frac{x_3v_1}{v_1v_1}v_1-\frac{x_3v_2}{v_2v_2}v_2\tag{식 5} \\ & \qquad \vdots\\ v_p&=x_p-\frac{x_pv_1}{v_1v_1}v_1-\frac{x_pv_2}{v_2v_2}v_2- \cdots -\frac{x_pv_{p-1}}{v_{p-1}v_{p-1}}v_{p-1}\end{align}

예 2)

ℝ⁴의 부분 공간인 W의 기저 집합 {x₁, x₂, x₃}으로부터 직교 기저 벡터들을 계산해 봅니다.

$$w=\text{span}\left\{\begin{bmatrix}1\\1\\1\\1 \end{bmatrix},\; \begin{bmatrix}0\\1\\1\\1 \end{bmatrix}, \; \begin{bmatrix}0\\0\\1\\1 \end{bmatrix}\right\}$$

x1=np.array([[1],[1],[1],[1]])
x2=np.array([[0],[1],[1],[1]])
x3=np.array([[0],[0],[1],[1]])
v1=x1
v2=x2-(x2.T@v1)/(v1.T@v1)*v1
print(v2)

[[-0.75]
 [ 0.25]
 [ 0.25]
 [ 0.25]]

v3=x3-(x3.T@v1)/(v1.T@v1)*v1-(x3.T@v2)/(v2.T@v2)*v2
print(v3)

[[ 0.    ]
 [-0.6667]
 [ 0.3333]
 [ 0.3333]]

위 결과들을 요소로 구성하는 직교기저행렬은 다음과 같습니다.

print(np.c_[v1,v2,v3].round(3))

[[ 1.    -0.75   0.   ]
 [ 1.     0.25  -0.667]
 [ 1.     0.25   0.333]
 [ 1.     0.25   0.333]]

위 결과인 정규 직교 벡터는 다음 장에서 소개할 QR분해의 Q와 같습니다. numpy.linalg 모듈의 qr() 함수를 사용할 수 있습니다. 정규 직교 벡터는 고유 벡터 등과 같이 기저 벡터이므로 다양한 값으로 나타낼 수 있습니다. 그러나 벡터의 값들 사이에 비례 관계는 일치해야 합니다. 위 예에 qr()함수를 적용한 결과는 다음과 같습니다. 위 결과와 열벡터의 값들은 다르지만 각 값들의 비(ratio)는 같습니다.

Q, R=la.qr(np.hstack([x1,x2,x3]))
np.around(Q, 3)

array([[-0.5  ,  0.866,  0.   ],
           [-0.5  , -0.289,  0.816],
           [-0.5  , -0.289, -0.408],
           [-0.5  , -0.289, -0.408]])

예 3)

Gram-Schmit를 사용하여 다음 벡터들에 대한 정규 직교 벡터들을 계산해 봅니다.

$$x_1=\begin{bmatrix}0\\-1\\1 \end{bmatrix}\quad x_2=\begin{bmatrix}2\\2\\2 \end{bmatrix}\quad \begin{bmatrix}4\\4\\4 \end{bmatrix}$$

벡터 x₃ = 2x₂의 관계이므로 x₁:x₂ 또는 x₁:x₃사이의 정규직교벡터를 계산합니다. 다음은 x₁:x₂ 사이의 결과입니다.

x1=np.array([[0,-1,1]]).reshape(3,1)
x2=np.array([[2,2,2]]).reshape(3,1)
x3=np.array([[4, 4,4]]).reshape(3,1)
X=np.c_[x1, x2]
Q, R=la.qr(X)
print(Q.round(3))

[[ 0.    -0.577]
 [ 0.707 -0.577]
 [-0.707 -0.577]]

그림 2는 위 결과를 나타낸 것으로 벡터 x₂와 x₃는 배수관계에 있으므로 하나의 벡터로 간주됩니다. 벡터 x₂를 벡터 x₁로 투영할 경우 q₁은 x₁의 배수관계가 성립합니다. 그 역 역시 q₂와 x₂의 배수관계가 성립합니다. 이러한 결과는 x2와 x1의 직교관계에 기인하는 것입니다.

그림 2. x₁, x₂에 직교관계인 벡터들.