[선형대수학 #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))

 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를 어떻게 구하는지요 ?
    아무리 인터넷을 뒤져 보아도 관련자료를 찾지를 못하겠네요..
    고수님의 조언을 부탁드립니다

    • BlogIcon 다크pgmr 2017.09.04 14:26 신고 수정/삭제

      simplex 알고리즘 등과 같이 constrained optimization 쪽으로 찾아보시면 좋을 듯 싶습니다.

  • 초보자 2018.04.30 13:24 신고 ADDR 수정/삭제 답글

    다크님..

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

    이 부분이 이해가 잘 안됩니다.
    OpenCV로 해보고 있는데요.
    SVD::compute(A, w, u, v);
    를 하여 w가 σ1 = 13.4052, σ2 = 0.8654, σ3 = 0.3620 와 같이 나오는데.. 여기서
    최소값인 σ3를 사용해서 어떻게 σ3에 대한 right singular vector를 구하는거죠?..

    • BlogIcon 다크pgmr 2018.04.30 14:21 신고 수정/삭제

      SVD::compute(A, w, u, v)에서 v의 열벡터들이 right singular vector들입니다.

    • 초보자 2018.04.30 16:37 신고 수정/삭제

      감사합니다!

    • 초보자 2018.04.30 17:01 신고 수정/삭제

      다크님.. 특이값이 음수로 나오면 음수값이 제일 작은 값이 되는건가요? 아니면 절대값으로 봐야하는건가요?

    • BlogIcon 다크pgmr 2018.04.30 17:53 신고 수정/삭제

      특이값은 음수로 나오지 않습니다. 항상 양수로 나오도록 하는게 암묵적인 약속입니다. 왜냐하면 특이값이 음수인 경우에는 특이값을 양수로 만들고 대신에 대응되는 singular vector를 음수로 만들면 되기 때문입니다. 특이값 및 특이값 분해에 대한 이론적인 부분에 대해서는 http://darkpgmr.tistory.com/106 글을 읽어보시면 좋을 것 같습니다.

    • 초보자 2018.04.30 19:56 신고 수정/삭제

      감사합니다!

  • C++ 2018.07.09 14:14 신고 ADDR 수정/삭제 답글

    다크님 좋은 글 항상 잘 보고있습니다.
    벌써 이 글만 3번째 봤네요.
    오타가 하나 있는거 같아서 댓글 남깁니다.
    점과 직선 사이의 거리 공식이 잘못된 것 같습니다.

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

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

    • BlogIcon 다크pgmr 2018.07.10 11:21 신고 수정/삭제

      덕분에 에러를 수정했습니다. 감사합니다. ^^

  • 더워추워 2018.07.24 08:36 신고 ADDR 수정/삭제 답글

    수도 인버스에 관해 공부하는중에 좋은글을 보게 되어 감사합니다.
    윗 글에서 행이 열보다 많은 m>n인 경우라고 하셨는데
    행이 열보다 작은 m<n인 경우는 어떤가요??
    단순 계산은 위글처럼 되는것 같은데
    식보다 미지수가 많은 경우라 해가 무한하여 타당한 참값을 결정하기 힘들어 근사값또한 결정이 힘들듯 한데 어떻게 생각해야 하는지 궁금합니다.
    이해가 부족하여 두서없이 글을쓴점 죄송합니다ㅎㅎㅎㅎ

    • BlogIcon 다크pgmr 2018.07.25 14:51 신고 수정/삭제

      underdetermined 문제(m<n)의 경우에는 최적해라는 것이 존재하기 어렵습니다. 예를 들어, 점 2개를 가지고 원을 결정해야 한다면 어떤 원을 잡아야 할까요. 두 점을 지나는 원은 무한히 많으며 그 모든 원들이 다 해가 됩니다. 그 중에 어떤 원은 타당한 원이고 어떤 원은 타당하지 않은 원이다라고 구분할 수는 없으며 모두 동등한 해입니다. 다만, 주어진 constraint(두 점을 지난다)를 만족하되 반지름이 최소화되는 원을 구하라라는 것처럼 부가적인 조건이 추가된다면 최적해를 구하는 것이 가능해질 수 있습니다.

    • 더워추워 2018.07.25 15:41 신고 수정/삭제

      답변 감사합니다.
      말씀대로 underdetermined 문제의 경우 데이터에 비해 미지수가 많으므로 무한개의 해가 구해질 것이라 생각했는데 수도인버스를 이용하여 계산을 하면 하나의 해가 구해지네요
      이때 구해진 해가 최적해가 아니라면 어떤 의미를 가지는 해라고 생각해야 하나요?

    • BlogIcon 다크pgmr 2018.07.25 17:19 신고 수정/삭제

      underdetermined 문제의 경우 pseudo inverse로 구해지는 해가 어떤 의미를 갖는 해인지는 저도 모릅니다. 수식적으로야 수많은 해들 중에서 어떤 어떤 특정한 해가 반환되는 것이겠지만 가치 판단의 기준(좋은 해, 나쁜 해)이 없는 상태에서그 해에 의미를 부여하는 것은 어렵다고 생각됩니다. 그럼에도 불구하고 굳이 수식적으로 따져보자면 Ax = b라는 문제가 있고, A = UΣVT로 분해된다고 할 때, V의 열벡터들은 n차원 공간을 구성하는 기저(basis) 벡터들로 볼 수 있습니다. 이 때, Ax = b를 만족하는 무수히 많은 해들 중에서 pseudo inverse로 구한 해는 이 해를 V 공간에 투영했을 때 그 norm이 최소화 되는 해입니다. 수식적으로야 그렇긴 하지만 이것을 원래의 파라미터 공간에서 직관적으로 해석할 방법은 제 능력으로는 어렵습니다.

  • MalMa 2018.11.12 13:31 신고 ADDR 수정/삭제 답글

    안녕하세여 다크pgmr님 블로그보고 공부를 많이하고있는 Vision 새내기 사원입니다.
    SVD관련하여 많이 참고하고 공부하고있습니다. 다른 사이트 보면서 Line fitting을 공부하던중
    AX=0 SVD하여 a,b를 얻었는데 이는 r = ax+by+c 최적화 값으로 보이며
    r = abs(ax+by+c)/sqrt(a^2+b^2) 를 최적화 하는 값이 아닌 것 같습니다.

    http://people.inf.ethz.ch/arbenz/MatlabKurs/node85.html 여기를 참조하였으며
    QR decomposition을 사용 합니다.
    Px = [1:10]
    Py = [ 0.2 1.0 2.6 3.6 4.9 5.3 6.5 7.8 8.0 9.0]
    데이터를 갖고 계산한 결과
    QR Fitting r^2 = 0.513810718
    기존방법 SVD r^2 = 0.533856626
    을 얻었습니다.

    • BlogIcon 다크pgmr 2018.11.15 18:37 신고 수정/삭제

      네. svd로 구한 해는 ||AX||를 최소화하는 해이니 수직거리를 최소화하는 해는 아닙니다. 감사합니다