[선형대수학 #5] 선형연립방정식 풀이

수학 이야기 2013.10.29 17:43

다양한 형태의 선형 연립 방정식을 최소자승법(least square method)과 SVD(singular value decomposition), pseudo inverse 등을 이용해서 푸는 방법을 정리해 봅니다.


먼저, 풀이 방법을 요약 정리한 후에 각각에 대해서 구체적인 예와 함께 설명합니다.



1. 선형연립방정식 풀이 방법 요약


AX = B 형태

  • A의 역행렬이 존재하는 경우: X = A-1B
  • A의 역행렬이 존재하지 않는 경우: X = A+B (단, A+는 A의 pseudo inverse)


AX = 0 형태

  • A의 특이값분해(SVD)를 A = UΣVT라 할 때, X는 V의 가장 오른쪽 열벡터 (즉, A의 최소 특이값에 대응하는 right singular vector)



2. AX = B 형태


미지수의 개수가 n개, 식의 개수가 m개인 선형연립방정식은 다음과 같다 (단, m≥n).


 --- (1)


위와 같은 x에 대한 선형연립방정식(a, b는 상수)을 행렬로 표현하면


 --- (2)


 --- (3)


이 때, m = n이고 A의 역행렬이 존재할 경우 위 선형방정식 (1)을 만족하는 해는 다음과 같이 유일하게 결정된다.

 --- (4)


그러나, 실제로 부딪히는 대부분의 문제는 m>n인 경우로서 A의 역행렬도 식 (1)을 만족하는 해도 존재하지 않는다. 이 경우에는 다음과 같이 A의 의사역행렬(pseudo inverse)를 이용하여 X를 근사적으로 구한다.


 --- (5)


이 때, A의 pseudo inverse A+는 다음과 같이 계산된다.

 --- (6)


 --- (7)


(6), (7) 어느 방법을 사용하여 pseudo inverse를 계산해도 무방하나, 식 (6)은 ATA의 역행렬이 존재할 경우만 적용할 수 있다 (대부분의 실제 문제들은 ATA의 역행렬이 존재). 식 (7)은 특이값분해(SVD)를 이용해서 pseudo inverse를 계산하는 경우로서 A의 SVD가 A = UΣVT라 할 때, A의 pseudo inverse는 A+ = VΣ+UT가 된다 (단, Σ+는 Σ의 0이 아닌 원소들의 역수를 취한 후 transpose를 시킨 것).


식 (5)와 같이 pseudo inverse를 이용하여 구한 X는 ∥AX-B∥를 최소화시키는 X와 동일하다. 그리고 이와같이 pseudo inverse를 이용하여 구한 근사해를 least square solution이라고 부르고, 이러한 풀이 방식을 최소자승법(least square method)이라 부른다.



3. AX = 0 형태


미지수의 개수가 n개, 식의 개수가 m개인 AX = 0 형태의 homogeneous 선형연립방정식은 다음과 같다.


 --- (8)


이를 행렬로 표현하면


 --- (9)


 --- (10)


이러한 homogeneous 선형방정식의 해는 A의 최소 특이값(singular value)에 대응하는 right singular vector로 주어진다. 먼저 A의 특이값분해(SVD)가 다음과 같다고 하자.


 --- (11)


이 때, Σ의 대각선상에 위치한 원소들이 A의 특이값(singular)이고, U, V는 모두 직교행렬(orthogonal matrix), 특이값들은 모두 0 이상(0 또는 양수)임은 앞서 설명한 바 있다. 이제 식 (10)의 해는 A의 특이값에 0이 포함되는지 여부에 따라 다음과 같이 두 가지 경우로 나뉜다.


i) 특이값에 0이 포함된 경우

만일 A의 특이값들 중 0이 존재하면 0인 특이값에 대응하는 right singular vector (V의 열벡터)는 식 (10)을 만족하는 0이 아닌 해가 된다. 만일, 0의 값을 갖는 특이값이 여러개 존재할 경우에는 대응되는 right singular vector들이 모두 식 (10)의 해가 된다. 또한 이들 해의 임의의 일차결합도 역시 해가 된다.


ii) 특이값이 모두 양수인 경우

특이값이 모두 양수인 경우에는 식 (10)을 정확히 만족하는 해는 X = 0을 제외하고는 존재치 않는다. 따라서, 이 경우에는 근사적으로 해를 구해야 하는데 ∥AX∥를 최소로 하는 근사해는 A의 특이값들 중 최소 특이값에 대응하는 right singular vector(즉, V의 가장 오른쪽 열벡터)이다. 


☞ right singular vector가 해가 되는 이유를 간략히 설명해 보면, 예를 들어 i번째 singular value가 0 (σi = 0), 대응되는 right singular vector를 vi라 하자(vi는 V의 i번째 열벡터). 이 때, Avi = UΣVTvi인데, VTvi는 i번째 값만 1이고 나머지는 0인 n차원 열벡터가 된다(∵ V는 직교행렬). 그런데, 여기에 Σ를 곱하면 ΣVTvi은 m차원 0벡터가 된다(∵ σi = 0). 따라서, Avi = UΣVTvi = 0이 되므로 vi는 AX = 0의 해가 된다.


☞ 이를 좀더 일반적으로 보면, i번째 특이값을 σi, 대응되는 right singular vector를 vi, left singular vector ui라 했을 때 X에 vi를 대입하면 항상 Avi = σi*ui가 나온다. 따라서, σi = 0 이라면 vi는 AX = 0의 해가 되고, 모든 특이값이 양수인 경우에는 최소 특이값에 대응하는 vi가 ∥AX∥ = ∥Avi∥ = ∥σi*ui∥= σi (∵ U는 직교행렬이므로 ui는 단위벡터) 를 최소화하는 근사해가 된다. 보다 엄밀한 증명을 위해서는 임의의 벡터 X에 대해 ∥AX∥≥∥Avi∥ 임을 증명해야 하나 이는 내용상 중요치 않으므로 생략한다 (vi들이 기저를 이루기 때문에 임의의 벡터는 vi들의 일차결합으로 표현될 수 있음을 이용하면 어렵지 않게 증명할 수 있다).



4. 직선 근사 예제


예를 들어 네 점 (1, 3.5), (2, 4.3), (3, 7.2), (4, 8)을 가장 잘 근사하는 직선의 방정식을 구하는 문제를 생각해 보자.




i) 직선의 방정식을 y = ax + b로 잡은 경우


 --- (12)


 --- (13)


A의 pseudo inverse를 구하여 a, b를 구해보면 직선의 방정식은 다음과 같이 구해진다.


 --- (14)


ii) 직선의 방정식을 ax + by + c = 0으로 잡은 경우


 --- (15)


 --- (16)


A의 특이값분해(SVD)를 해 보면 특이값이 σ1 = 13.4052, σ2 = 0.8654, σ3 = 0.3620 로 나오고 이중 최소값인 σ3에 대한 right singular vector를 [a, b, c]로 했을 때의 해는 다음과 같다.


 --- (17)


이를 y에 대해 정리해 보면,


 --- (18)


i) & ii) 결과를 그림으로 비교해 보면 다음과 같다.



그림으로 봐서는 어떤게 좋은 것인지 비교가 힘들기 때문에 이를 수치적으로 비교해 보자.


먼저 근사오차를 r = y - (ax + b)로 잡고 제곱합을 구해보면

 i) y = ax+b 모델     => ∑r2 = 0.8820 (빨간색 그래프)

 ii) ax+by+c=0 모델 => ∑r2 = 0.9345 (파란색 그래프)


근사오차를 직선과의 수직거리로 잡은 경우에는 (r = |ax+by+c|/sqrt(a2+b2+c2))

 i) y = ax+b 모델     => ∑r2 = 0.1376 (빨간색 그래프)

 ii) ax+by+c=0 모델 => ∑r2 = 0.1311 (파란색 그래프)


즉, y축 방향으로의 근사오차를 고려하면 i) y = ax + b 모델이 좀더 낮은 에러를 보이고, 직선과의 수직거리를 근사오차로 생각하면 ii) ax + by + c = 0 모델이 낮은 에러를 나타낸다.


☞ 사실 실제 계산 결과를 보기 전까지는 y=ax+b로 모델을 잡고 AX=B를 푼 결과와, ax+by+c=0을 모델로 잡고 AX=0을 푼 결과가 같을지 다를지 저도 궁금했습니다만 결과는 다르게 나왔습니다. 즉, ∥y-ax-b∥를 최소화하는 해와 ∥ax+by+c∥를 최소화하는 해가 다르다는 의미일 것입니다. 생각해보면 ∥y-ax-b∥는 y의 계수를 1로 고정시켜놓고 최소해를 구하기 때문에 아무런 제약이 없는 ∥ax+by+c∥의 최소해보다 좋지 않은 결과를 보이는 것으로 해석할 수 있습니다.



[선형대수학 #1] 주요용어 및 기본공식

[선형대수학 #2] 역행렬과 행렬식(determinant)

[선형대수학 #3] 고유값과 고유벡터 (eigenvalue & eigenvector)

[선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용

[선형대수학 #5] 선형연립방정식 풀이

[선형대수학 #6] 주성분분석(PCA)의 이해와 활용


by 다크 프로그래머


저작자 표시 비영리 변경 금지
신고
  • 곰돌이만세 2014.07.09 15:14 신고 ADDR 수정/삭제 답글

    와~ 감사드립니다.

  • 질문자 2015.01.30 16:35 신고 ADDR 수정/삭제 답글

    A의 특이값분해(SVD)를 해 보면 특이값이 σ1 = 13.4052, σ2 = 0.8654, σ3 = 0.3620 로 나오고 이중 최소값인 σ3에 대한 right singular vector를 [a, b, c]로 했을 때의 해는 다음과 같다. 이부분에서 궁금한점이 있습니다 특이최소값 즉0.3620에해당하는right singular vector가AX=0에서X의값에해당되는건지를알고싶습니다.

  • 궁금이 2015.05.06 14:58 신고 ADDR 수정/삭제 답글

    궁금한게 있어서 질문 남깁니다. 식(6)에서 A^(T)*A의 역행렬이 대부분 존재한다 하셨는데,
    혹시 존재하지 않는 조건 같은게 있는지 궁금합니다.

    • BlogIcon 다크pgmr 2015.05.07 07:09 신고 수정/삭제

      따로 조건은 없습니다. A^T*A도 하나의 행렬이기 때문에 역행렬이 존재할 수도 존재하지 않을 수도 있습니다. 다만, 데이터의 개수가 충분하면 대부분 역행렬이 존재하고 데이터의 개수가 미지수의 개수보다 적으면 역행렬이 존재하지 않는다고 생각하시면 될 것 같습니다.

    • BlogIcon juhlnet 2016.01.06 20:22 신고 수정/삭제

      A 의 열들이 선형독립이면 A^TA 는 역행렬이 존재합니다. 반대로 A 의 열들이 선형종속이면 A^TA 는 역행렬이 존재하지 않구요. 다만 A 의 성분들이 랜덤하다면 수치적으로 A의 열들이 선형종속일 확율은 거의 없겠지요.

  • BlogIcon 간숙자 2015.08.07 20:28 신고 ADDR 수정/삭제 답글

    안녕하세요? 혹시 식 13에서 14를 어떻게 구하셨는지요? 혹시 알려주실수 있으신가요? 그리고 예제를 주신것은 직선의 방정식을 예로 들으셨는데요 혹시 3 order를 구할수도 있는건가요?

    • BlogIcon 다크pgmr 2015.08.07 21:55 신고 수정/삭제

      식 (13)의 풀이과정은 본문의 '2. AX = B 형태'에 대한 글 내용을 읽어보시면 됩니다. 그리고 물론 3차 식도 가능합니다. http://darkpgmr.tistory.com/56 글의 내용을 참고하시기 바랍니다.

  • 0523 2016.09.21 20:21 신고 ADDR 수정/삭제 답글

    감사합니다.
    선형대수 복습해야지해야지하다가 이제서야 보게되네요
    선형대수 리뷰 잘보고있습니다.

  • kegis 2016.10.11 14:19 신고 ADDR 수정/삭제 답글

    위의 (1),(8)식에서 X값을 구하는 방법에 대한 질문입니다
    위에 설명한것은 이해를 하겠는데 n=3 이라고 가정할때 X1, X2, X3를 구해야 하는데
    이값이 0<X1, X2, X3 <1이고 X1+X2+X3=1 이라는 조건을 만족해야 한다고 했을때
    X1, X2, X3를 어떻게 구하는지요 ?
    아무리 인터넷을 뒤져 보아도 관련자료를 찾지를 못하겠네요..
    고수님의 조언을 부탁드립니다



티스토리 툴바