기본 콘텐츠로 건너뛰기

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

댓글 쓰기

QR 분해(Decomposition)

내용

QR 분해(Decomposition)

어떤 벡터를 구성하는 직교 벡터를 계산하기 위해 Gram-Schmidt 과정을 적용하였습니다. 행렬은 이 과정에 의해 생성된 직교행렬과 그에 대응하는 행렬로 분해될 수 있습니다. 이러한 분해를 QR 분해라고 합니다.

m×n형태의 행렬 A가 선형 독립이라면 식 1과 같이 분해할 수 있습니다.

$$\begin{equation}\tag{1} \text{A} = \text{QR} \end{equation}$$
  • Q: 열공간 A에 정규직교인 m×n 차원의 행렬 (Col A)
  • R: n×n 차원의 상삼각 역행렬, 대각원소는 양수입니다.

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

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

행렬 A의 열공간은 columnspace() 함수를 사용하여 계산할 수 있습니다.

import numpy as np
import numpy.linalg as la
import sympy as sp
A=np.array([[1,0,0],[1,1,0],[1,1,1], [1,1,1]])
colA=sp.Matrix(A).columnspace()
for i in colA:
    print(f'각 열공간의 전치행렬:{i.T}, 각 열공간의 차원:{i.shape}')
각 열공간의 전치행렬:Matrix([[1, 1, 1, 1]]), 각 열공간의 차원:(4, 1)
    각 열공간의 전치행렬:Matrix([[0, 1, 1, 1]]), 각 열공간의 차원:(4, 1)
    각 열공간의 전치행렬:Matrix([[0, 0, 1, 1]]), 각 열공간의 차원:(4, 1)

위 결과에 의하면 A의 모든 열벡터들이 기저 벡터입니다. 위에서 발견한 각 열공간(열벡터)의 직교 기저를 계산하기 위해 Gram-Schmidt과정을 적용합니다.

Gram-Schmidt 과정을 적용하기 위해 사용자 정의함수인 orthoCoef()를 작성하여 적용하였습니다. 행렬 A의 각 열벡터를 각각 x1, x2, x3로 표시합니다.

def orthoCoefS(x, y):
    x=np.dot(x.T, y)
    y=np.dot(y.T, y)
    return(x/y)
x1=np.array([[1],[1],[1],[1]])
x2=np.array([[0],[1],[1],[1]])
x3=np.array([[0],[0],[1],[1]])
v1=x1;v1
array([[1],
           [1],
           [1],
           [1]])
v2=x2-orthoCoefS(x2, v1)*v1; v2
array([[-0.75],
           [ 0.25],
           [ 0.25],
           [ 0.25]])
v3=x3-orthoCoefS(x3, v1)*v1-orthoCoefS(x3, v2)*v2; v3
array([[ 0.        ],
           [-0.66666667],
           [ 0.33333333],
           [ 0.33333333]])

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

v1_u=1/la.norm(v1)*v1
v2_u=1/la.norm(v2)*v2
v3_u=1/la.norm(v3)*v3
Q=np.c_[v1_u, v2_u, v3_u]
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]])

결과 Q를 식 1에 적용하여 R을 계산할 수 있습니다. 즉, A=QR의 행렬 방정식에서 해(solution)인 R을 계산할 수 있습니다. 이 과정에서 Q는 정방 행렬이 아니므로 역행렬을 사용할 수 없으므로 Q와 A의 결합인 확대 행렬의 기약행사리꼴(rref)을 사용하여 계산할 수 있습니다.

위 확대 행렬(AM)을 나타내면 다음과 같습니다.

AM=np.hstack([Q,A])
np.around(AM, 3)
array([[ 0.5  , -0.866,  0.   ,  1.   ,  0.   ,  0.   ],
           [ 0.5  ,  0.289, -0.816,  1.   ,  1.   ,  0.   ],
           [ 0.5  ,  0.289,  0.408,  1.   ,  1.   ,  1.   ],
           [ 0.5  ,  0.289,  0.408,  1.   ,  1.   ,  1.   ]])

R은 AM을 사용하여 계산됩니다.

다음 코드 결과와 같이 확대 행렬의 결과는 4×3 행렬로 정방 행렬이 아닙니다. 그러나 R은 정의(식 1)상 정방 행렬이 되어야 합니다. AM의 rref에서 모든 원소가 0인 행을 제외하면 3×3인 정방 행렬이 되며 이 결과가 R이 됩니다.

AM_rref=sp.Matrix(AM).rref()
AM_rref
(Matrix([
     [1, 0, 0, 2.0,               1.5,               1.0],
     [0, 1, 0,   0, 0.866025403784439, 0.577350269189626],
     [0, 0, 1,   0,                 0, 0.816496580927726],
     [0, 0, 0,   0,                 0,                 0]]),
     (0, 1, 2))
R=np.array(AM_rref[0][:3,3:], dtype=float)
np.around(R,3)
array([[2.   , 1.5  , 1.   ],
           [0.   , 0.866, 0.577],
           [0.   , 0.   , 0.816]])

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

re=np.dot(Q,R)
np.around(re, 3)
array([[ 1.,  0., -0.],
           [ 1.,  1.,  0.],
           [ 1.,  1.,  1.],
           [ 1.,  1.,  1.]])
A==np.around(re, 3)
array([[ True,  True,  True],
           [ True,  True,  True],
           [ True,  True,  True],
           [ True,  True,  True]])

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

Q1,R1=la.qr(A)
np.around(Q1, 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]])
np.around(R1, 3)
array([[-2.   , -1.5  , -1.   ],
           [ 0.   , -0.866, -0.577],
           [ 0.   ,  0.   , -0.816]])
A == np.around(np.dot(Q1, R1))
array([[ True,  True,  True],
           [ True,  True,  True],
           [ True,  True,  True],
           [ True,  True,  True]])

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

A=QR에서 A와 Q의 형태는 같습니다. 그리고 Q는 A의 정규직교 행렬의 열공간으로 기저입니다. 즉, A의 모든 열이 피벗열이 되어 선형 독립이어야 합니다. 그러나 3×4형태에서 4개의 기저 벡터 ,즉 정규직교 열을 갖을 수 없습니다. 그러므로 QR 분해를 가질 수 없습니다.

QR 분해의 조건

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

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

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

A의 1열 벡터를 v1으로 하여 순차적으로 계산한 결과를 각 열의 노름(norm)으로 나누어 단위행렬로 전환합니다.

A=np.array([[-2, 1], [1, 2],[-2, 3]])
v1=A[:,0]
x2=A[:,1]
v2=x2-np.dot(x2.T,v1)/np.dot(v1.T,v1)*v1
np.around(v2, 3)
array([-0.333,  2.667,  1.667])
v1_u=v1/la.norm(v1)
v2_u=v2/la.norm(v2)
Q=np.vstack([v1_u, v2_u]).T
np.around(Q, 3)
array([[-0.667, -0.105],
           [ 0.333,  0.843],
           [-0.667,  0.527]])

위 결과로부터 R을 계산할 수 있습니다. Q는 정규 직교 행렬로서 QT=Q-1의 특성을 가지므로 다음과 같이 계산할 수 있습니다.

$$\begin{align} QR &= A\\ R &= Q^{-1}A\\ &= Q^TA \end{align}$$ 
R=np.dot(Q.T, A)
np.around(R, 3)
array([[ 3.   , -2.   ],
           [-0.   ,  3.162]])
np.dot(Q, R)
array([[-2.,  1.],
           [ 1.,  2.],
           [-2.,  3.]])
q, r=la.qr(A)
np.around(q, 3)
array([[-0.667,  0.105],
           [ 0.333, -0.843],
           [-0.667, -0.527]])
np.around(r, 3)
array([[ 3.   , -2.   ],
           [ 0.   , -3.162]])
A==np.around(np.dot(q, r))
array([[ True,  True],
           [ True,  True],
           [ True,  True]])
Labels:

댓글

댓글 쓰기

이 블로그의 인기 게시물

유사변환과 대각화

내용 유사변환 유사행렬의 특성 대각화(Diagonalization) 유사변환(Similarity transformation) 유사변환 n×n 차원의 정방 행렬 A, B 그리고 가역 행렬 P 사이에 식 1의 관계가 성립하면 행렬 A와 B는 유사하다고 하며 이 변환을 유사 변환 (similarity transformation)이라고 합니다. $$\begin{equation}\tag{1} A = PBP^{-1} \Leftrightarrow P^{-1}AP = B \end{equation}$$ 식 1의 유사 변환은 다음과 같이 고유값을 적용하여 특성 방정식 형태로 정리할 수 있습니다. $$\begin{align} B - \lambda I &= P^{-1}AP – \lambda P^{-1}P\\ &= P^{-1}(AP – \lambda P)\\ &= P^{-1}(A - \lambda I)P \end{align}$$ 위 식의 행렬식은 다음과 같이 정리됩니다. $$\begin{align} &\begin{aligned}\textsf{det}(B - \lambda I ) & = \textsf{det}(P^{-1}(AP – \lambda P))\\ &= \textsf{det}(P^{-1}) \textsf{det}((A – \lambda I)) \textsf{det}(P)\\ &= \textsf{det}(P^{-1}) \textsf{det}(P) \textsf{det}((A – \lambda I))\\ &= \textsf{det}(A – \lambda I)\end{aligned}\\ &\begin{aligned}\because \; \textsf{det}(P^{-1}) \textsf{det}(P) &= \textsf{det}(P^{-1}P)\\ &= \t
댓글 쓰기
Read more »

[matplotlib] 히스토그램(Histogram)

히스토그램(Histogram) 히스토그램은 확률분포의 그래픽적인 표현이며 막대그래프의 종류입니다. 이 그래프가 확률분포와 관계가 있으므로 통계적 요소를 나타내기 위해 많이 사용됩니다. plt.hist(X, bins=10)함수를 사용합니다. x=np.random.randn(1000) plt.hist(x, 10) plt.show() 위 그래프의 y축은 각 구간에 해당하는 갯수이다. 빈도수 대신 확률밀도를 나타내기 위해서는 위 함수의 매개변수 normed=True로 조정하여 나타낼 수 있다. 또한 매개변수 bins의 인수를 숫자로 전달할 수 있지만 리스트 객체로 지정할 수 있다. 막대그래프의 경우와 마찬가지로 각 막대의 폭은 매개변수 width에 의해 조정된다. y=np.linspace(min(x)-1, max(x)+1, 10) y array([-4.48810153, -3.54351935, -2.59893717, -1.65435499, -0.70977282, 0.23480936, 1.17939154, 2.12397372, 3.0685559 , 4.01313807]) plt.hist(x, y, normed=True) plt.show()
댓글 쓰기
Read more »

R 미분과 적분

내용 expression 미분 2차 미분 mosaic를 사용한 미분 적분 미분과 적분 R에서의 미분과 적분 함수는 expression()함수에 의해 생성된 표현식을 대상으로 합니다. expression expression(문자, 또는 식) 이 표현식의 평가는 eval() 함수에 의해 실행됩니다. > ex1<-expression(1+0:9) > ex1 expression(1 + 0:9) > eval(ex1) [1] 1 2 3 4 5 6 7 8 9 10 > ex2<-expression(u, 2, u+0:9) > ex2 expression(u, 2, u + 0:9) > ex2[1] expression(u) > ex2[2] expression(2) > ex2[3] expression(u + 0:9) > u<-0.9 > eval(ex2[3]) [1] 0.9 1.9 2.9 3.9 4.9 5.9 6.9 7.9 8.9 9.9 미분 D(표현식, 미분 변수) 함수로 미분을 실행합니다. 이 함수의 표현식은 expression() 함수로 생성된 객체이며 미분 변수는 다음 식의 분모의 변수를 의미합니다. $$\frac{d}{d \text{변수}}\text{표현식}$$ 이 함수는 어떤 함수의 미분의 결과를 표현식으로 반환합니다. > D(expression(2*x^3), "x") 2 * (3 * x^2) > eq<-expression(log(x)) > eq expression(log(x)) > D(eq, "x") 1/x > eq2<-expression(a/(1+b*exp(-d*x))); eq2 expression(a/(1 + b * exp(-d * x))) > D(eq2, "x") a * (b * (exp(-d * x) * d))/(1 + b
댓글 쓰기
Read more »