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

다양한 형태의 선형 연립 방정식을 최소자승법(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ΣV^T라 할 때, 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)은 A^TA의 역행렬이 존재할 경우만 적용할 수 있다 (대부분의 실제 문제들은 A^TA의 역행렬이 존재). 식 (7)은 특이값분해(SVD)를 이용해서 pseudo inverse를 계산하는 경우로서 A의 SVD가 A = UΣV^T라 할 때, A의 pseudo inverse는 A⁺ = VΣ⁺U^T가 된다 (단, Σ⁺는 Σ의 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ΣV^Tvi인데, V^Tvi는 i번째 값만 1이고 나머지는 0인 n차원 열벡터가 된다(∵ V는 직교행렬). 그런데, 여기에 Σ를 곱하면 ΣV^Tvi은 m차원 0벡터가 된다(∵ σi = 0). 따라서, Avi = UΣV^Tvi = 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 모델     => ∑r² = 0.8820 (빨간색 그래프)

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

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

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

 ii) ax+by+c=0 모델 => ∑r² = 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 다크 프로그래머