[Linear Algebra] QR 분해(Decomposition)

QR 분해(Decomposition)

임의의 벡터와 관련된 직교 벡터를 계산하기 위해 Gram-Schmidt 과정을 적용하였습니다. 이 과정을 사용하여 식 1과 같이 행렬을 구성하는 벡터들의 직교벡터들로 구성된 직교행렬과 그에 대응하는 행렬로 분해될 수 있습니다. 이러한 분해를 QR 분해(Decomposition)라고 합니다. 즉, m × n 형태의 행렬 A가 선형독립이라면 식 1과 같이 분해할 수 있습니다.

$$\begin{align}\tag{식 1} \text{A} = \text{QR} \end{align}$$

• Q: 열공간 A에 정규직교인 m×n 차원의 행렬 (Col A)
• R: n×n 차원의 상삼각 역행렬, 대각원소는 양수입니다.

예 1)

다음 행렬 A의 QR 분해를 계산합니다.

$$A=\begin{bmatrix} 1& 0 & 0 \\1& 1& 0\\1& 1& 1\\1& 1 & 1 \end{bmatrix}$$

행렬 A를 구성하는 열 벡터들이 기저벡터인지를 확인합니다. 즉, 선형독립인지를 확인합니다. rref() 메서드를 적용합니다.

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

A=np.array([[1,0,0],[1,1,0],[1,1,1], [1,1,1]])
Matrix(A).rref()

(Matrix([
 [1, 0, 0],
 [0, 1, 0],
 [0, 0, 1],
 [0, 0, 0]]),
 (0, 1, 2))

위 결과에 의하면 A의 모든 열벡터들이 기저 벡터입니다. 각 벡터들에 직교 기저는 Gram-Schmidt 과정을 적용하여 계산할 수 있습니다.

a1, a2, a3=A[:,0], A[:,1], A[:,2]
v1=a1
v2=a2-(a2@v1)/(v1@v1)*v1
print(v1)
print(v2)

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

v3=a3-(a3@v1)/(v1@v1)*v1-(a3@v2)/(v2@v2)*v2
print(v3.round(3))

[ 0.    -0.667  0.333  0.333]

Q는 정규직교이므로 각 벡터를 단위 벡터로 수정합니다.

q1=v1/la.norm(v1)
q2=v2/la.norm(v2)
q3=v3/la.norm(v3)
Q=np.c_[q1,q2,q3]
print(Q.round(3))

[[ 0.5   -0.866  0.   ]
 [ 0.5    0.289 -0.816]
 [ 0.5    0.289  0.408]
 [ 0.5    0.289  0.408]]

결과 Q를 식 1에 적용하여 R을 결정합니다. Q는 정규 직교 행렬로서 Q^T = Q^-1의 특성을 가지므로 식 2와 같이 계산할 수 있습니다.

\begin{align}\tag{식 2}QR & =A\\ R&=Q^{-1}A\\&=Q^TA \end{align}

R=Q.T@A
print(R.round(3))

[[2.    1.5   1.   ]
 [0.    0.866 0.577]
 [0.    0.    0.816]]

이 결과로부터 분해를 확인해 봅니다.

np.allclose(A,Q@R)

True

행렬의 QR 분해는 np.linalg.qr() 함수를 사용하여 계산할 수 있습니다. 이 함수는 두 가지 결과, 즉 Q, R을 튜플로 반환합니다. 또한 위에서 계산한 결과와 반대의 부호를 가질 수 있으나 바뀐 부호는 Q, R에 공통적으로 적용되기 때문에 최종 결과는 동일합니다.

Q1,R1=la.qr(A)
print(Q1.round(3))

[[-0.5    0.866  0.   ]
 [-0.5   -0.289  0.816]
 [-0.5   -0.289 -0.408]
 [-0.5   -0.289 -0.408]]

print(R1.round(3))

[[-2.    -1.5   -1.   ]
 [ 0.    -0.866 -0.577]
 [ 0.     0.    -0.816]]

np.allclose(A, Q1@R1)

True

예 2)

3×4 형태의 행렬 A는 QR 분해를 가질 수 있습니까?

A = QR에서 A와 Q의 형태는 같습니다. 그리고 Q는 정규직교 행렬로 A의 열공간이며 기저입니다. 즉, A의 모든 열이 피벗열이 되어 선형 독립이어야 합니다. 3×4형태의 행렬을 표준행렬로 선형시스템을 생성하면 식의 수가 변수의 수보다 작습니다. 자유변수가 존재하므로 선형종속입니다. 그러므로 A의 QR 분해는 계산되지 않습니다.

QR 분해의 조건

모든 가역행렬 = 선형 독립 = QR 분해 가능

예 3)

Gram-Schmidt과정을 사용하여 행렬 A는 QR 분해를 실행해 봅니다.

$$A=\begin{bmatrix}-2& 1\\1& 2\\-2& 3 \end{bmatrix}$$

A의 1열 벡터를 v₁으로 하여 각 열벡터에 대해 Gram-Schmidt 과정을 적용합니다.

A=np.array([[-2, 1], [1, 2],[-2, 3]])
a1, a2=A[:,0], A[:,1]
v1=a1
v2=a2-(a2@v1)/(v1@v1)*v1
print(v1)
print(v2.round(3))

[-2  1 -2]
[-0.333  2.667  1.667]

위 결과벡터를 단위벡터로 수정하여 결합한 행렬이 Q가 됩니다.

q1=v1/la.norm(v1)
q2=v2/la.norm(v2)
Q=np.c_[q1, q2]
print(Q.round(3))

[[-0.667 -0.105]
 [ 0.333  0.843]
 [-0.667  0.527]]

위 결과로부터 식 2를 적용하여 R을 계산할 수 있습니다.

R=Q.T@A
print(R.round(3))

[[ 3.     -2.    ]
 [-0.      3.1623]]

print(Q@R)

[[-2.  1.]
 [ 1.  2.]
 [-2.  3.]]

q, r=la.qr(A)
print(q)

[[-0.6667  0.1054]
 [ 0.3333 -0.8433]
 [-0.6667 -0.527 ]]

print(r)

[[ 3.     -2.    ]
 [ 0.     -3.1623]]

np.allclose(A, q@r)

True