이번 강의에서 배울 내용은 바로 해가 존재하지 않는 선형연립방정식의 해를 구하는 방법이다. 이는 바로 다음 강의에서 배울 투영 행렬(Projection matrix)을 배우기 위함이다. 투영 행렬에 대해 본격적으로 공부해보기 전에 먼저 준비 운동을 해보자. 투영 행렬에 대한 이해를 돕기 위해서 말이다.
1. 해가 존재하지 않는 선형연립방정식 Ax=b (Solving Ax=b when there is no solution)
우리는 지금 까지 부분 공간(subspaces)등을 다뤄오면서 주로 null space에 관한 식 Ax=0에 대해서 공부해왔다. 투영 행렬에 대한 준비운동으로 우변에 어떤 값이 존재하는 식 Ax=b에 대해서 다시 한 번 생각해보자.
우리는 지난 강의 Lecture 8에서 어떤 시스템의 선형방정식인 Ax=b 를 만족시키는 해 x를 구할 때, b가 행렬 A의 column space상에 존재한다면 이 선형시스템은 가해 조건(solvability condition)을 만족하며 해를 구할 수 있다고 배웠다(b를 붙인 Augmented matrix를 만든 뒤 함께 소거하여 후방대입). 그러나 만약 b가 가해 조건을 만족하지 않는다면? 즉 b가 A의 column space상에 존재하지 않는다면 어떻게 될까? 가해 조건을 만족하지 않아 해가 존재하지 않는 경우 말이다. 이러한 경우에도 해를 구할 수 있을까?
질문이 약간 이상해보일 수 있다. 해가 존재하지 않는데 해를 구한다고? 말이 안되는 것 처럼 보이겠지만 사실 해를 구할 수 있다. 좀 더 정확히 이야기 하자면 애초에 해가 없기 때문에 아주 정확한 해(exact solution)는 구할 수 없지만 가장 근사한 해를 구하는 것이다. 특히 행렬 A의 미지수(unknown)보다 방정식(equation)이 더 많은 경우(m>n), rank는 m보다는 당연히 작고 최소 n이 된다. 이 경우 column 벡터의 차원이 rank보다 작기때문에 우변의 벡터 b에 상응하는 해가 없을 가능성이 훨씬 높을 것이다. 이를 overdetermined라 한다. 미지수와 방정식의 수가 같은 경우(m=n)를 determined, 방정식이 미지수보다 적을 경우(m<n) underdetermined라 한다. 그 형태는 아래와 같다.
Overdetermined는 방정식이 미지수보다 많은 경우이며 일반적으로 해가 존재하지 않는다. 해가 존재하는 경우가 있다면 우변의 b벡터가 A의 column space에 존재할 때 해(solution) x가 존재한다. 실제로 식 (1)의 overdetermined행렬에 우변 벡터 b를 붙여 Augmented matrix를 만든 다음 소거(elimination)를 통해 row reduced echelon form을 만들면 row4는 영벡터인데, b4의 원소는 0이 아닌 상수가 나온다. 애초에 식 자체가 성립이 안되기 때문에 해가 존재하지 않는다.
Determined는 미지수와 방정식의 수가 같은 경우이며, full rank일 경우 유일한 해(unique solution)를 갖는다.
Underdetermined는 미지수가 방정식보다 많은 경우이다. 이 경우엔 무수히 많은 해가 존재한다.
위와 관련해서는 나중에 행렬식(determinant)을 공부할 때 다시 살펴보도록 하자.
어쨋든 해가 없는 경우인 overdetermined에 대한 이해를 돕기 위해 예를 들어 설명을 하겠다. 인공위성의 위치를 추정하는 식이라고 생각해보자. 위치 측정값에 대한 위한 수백, 수천개의 방정식을 얻었다고 가정해보자. 이렇게 되면 미지수(unknown)보다 측정 값에 대한 방정식이 훨씬 많은 경우가 되어 overdetermined형식이 된다. 따라서 해가 존재 하지 않게 되는데, 가장 간단하게는 미지수의 수 만큼의 방정식만 남기고 나머지는 없애는 것이다. 그러나 어떤 방정식(측정값)이 좋은 것이고 어떤 것이 나쁜 데이터인지 정확히 판단하기는 어렵다. 대부분의 데이터에는 잡음(noise)이 있지만 또한 시스템의 해 x에 대한 정보도 담겨있다. 어떤 방정식을 없애야 하는지에 대한 기준은 명확하지 않다. 따라서 우리는 이 모든 데이터에 대한 방정식을 고려한 최적의 해(best solution)를 구해야 할 것이다. 곧이어 배우겠지만 이것이 최소자승법(Least square method)이며 투영행렬(projection matrix)과도 관련이 있다.
다시 overdetermined행렬의 소거를 생각해보자. 이때의 행렬의 형태는 직사각형(Rectangular)형태일 것이고 바로 위에서 언급한 것처럼 소거했을 때 pivot row아래의 row들, 즉 row4는 [0 0 0]=[1]와 같이 말이 안되는 식이 될 것이다. 소거(Elimination)에 실패한 것이다. 소거의 결과는 우리에 해가 존재하는지, 혹은 존재하지 않는지에 대한 것을 말해준다. overdetermined인 경우에는 소거가 해가 존재하지 않는다고 말해준다. 그럼 어떻게 해야 할까? 지금부터가 중요하다. 우선 아래의 행렬을 이해하는 것이 굉장히 중요하다.
식 (4)의 행렬은 우리의 문제를 이해하는데 핵심적인 역할을 하는 행렬이다. 위 행렬은 어떤 행렬일까?
여기서 한 가지 가정은 행렬 A는 m by n크기이며 m이 n보다 더 큰, 즉 m>n 의 overdetermined형태이다. 이러한 A행렬의 전치(transpose)를 A앞에 곱해주었다. 어떻게 될까? 바로 정사각행렬(square matrix)이 된다. 원래 행렬 A는 m x n이고, A의 transpose행렬은 행과 열이 뒤바뀐 n x m이다. A의 transpose행렬을 앞에 곱해주면 (n x m) * (m x n) = (n x n)이 되어 정사각행렬이 되는 것이다.
식 (4)의 또 다른 특성은 어떤 것이 있을까? 바로 대칭(symmetric)이다. 대칭 행렬(symmetric matrix)의 특성은 전치를 해도 원래 자기 자신과 똑같은 특성을 가지고 있다. 한 번 증명해보자.
전치를 해도 원래의 행렬 곱과 똑같아지는 것을 알 수 있다.
자 이제 가장 중요한 것을 확인해보자. 식 (4)는 역행렬이 존재하는가(invertible)? 식 (4)는 역행렬이 존재한다. 단 조건은 Full rank여야 한다는 것이다. 우리는 식 (5)를 통해 식 (4)가 정사각행렬이 됨을 알았다. 역행렬(Inverse matrix)의 조건은 정방행렬이면서 full rank여야 한다. 따라서 full rank라는 조건만 충족된다면 식 (4)는 역행렬이 존재한다. 사실 full rank가 되기 위한 조건은 원래 행렬의 column이 독립(independent)하면 된다.
이렇게 하여 우리는 overdetermined형태의 행렬 A의 앞에 A의 transpose를 곱해준 형태인 식 (4)의 중요한 특성 3가지를 알아보았다. 특성 3 가지를 다시 정리해보면 아래와 같다.
- Square Matrix
- Symmetric Matrix
- Invertible (if Full rank)
우리가 지금까지 식 (4)에 대한 주요 특성들을 알아본 이유는 결국 어떤 문제를 해결하기 위함이다. 맨 처음 언급한 것과 같이 우리는 Ax=b에서 방정식이 미지수보다 더 많은 형태(m>n)인 overdetermined에 대한 형태에 관한 문제를 풀고자한다. 그러나 overdetermined형태의 식은 앞서 언급한 것과 같이 방정식이 미지수보다 더 많기 때문에 해가 존재하지 않는다. 그렇다면 여기서 끝내야 할까? 아니다. 식을 정확하게 만족시키는 해를 구할 순 없어도 모든 식을 최대한 만족시키는 해(best solution)를 구하면 된다. 아래 식을 다시 보자.
식 (7)의 행렬 A는 정방행렬(square matrix)이 아니기 때문에 역행렬을 구할 수 없다. 따라서 해를 구할 수 없다. 그러나 최적의 해는 구할 수 있다. 바로 식의 양변에 A의 전치(transpose)를 곱해주는 것이다.
양변에 똑같은 행렬을 곱해줬기 때문에 식은 성립한다. 이때 식의 해(solution)에 해당하는 x에 hat(^)이 붙었다. x hat이 의미하는 것은 최적해(optimal or best solution)이다. 식을 정확히 만족시키는 해(solution)는 아니지만, A에 존재하는 모든 방정식(row, b)을 최대한 만족시키는 해를 의미하는 것이다. 식 (8)은 굉장히 중요하다.
거의 다 왔다. 이제 중요한 것은 식 (8)의 실제 해를 구하는 것이다.
은 앞서 살펴봤듯이 full rank이기만 하면 역행렬이 존재한다고 했다. 따라서 이것의 역행렬을 구하여 양변에 곱해주면 최종적인 해를 구할 수 있을 것이다.
이렇게 하여 해가 존재하지 않는 Ax=b에 대한 최적해(best solution)를 구할 수 있다. 다음 섹션에서 실제 예를 들어서 계산해보도록 하자.
2. Examples of Ax=b (overdetermined case)
- Best solution for overdetermined equation
섹션 1에서 가장 처음 봤던 식 (1)의 overdetermined 식의 해를 구해보도록 하자. 식 (1)을 다시 써보면
위의 식을 (9)와 같이 정리해보자.
식 (1)의 예제를 식 (9)의 방법을 통해 최적해(best solution) $\hat{\boldsymbol{x}}$(x hat)를 계산하였다. 계산된 결과를 원래의 식과 비교해 봤을 때 약간의 차이가 있지만 그 정도가 크지 않은 것을 알 수 있다.
결국 우리는 미지수(unknown)보다 방정식(equation)이 많아서 원래 해가 존재하지 않는 overdetermined case의 선형연립방정식에 대한 최적해를 구할 수 있었다. 비록 딱 들어맞는 정확한 해는 아니지만, 각 방정식의 정보를 최대한 반영하여 각 방정식과의 오차(error)의 합을 최대한 줄이는 쪽으로 해를 계산할 수 있었다.
아래는 식 (10)을 MATLAB으로 구현한 코드이다.
- when the solution exists in overdetermined equation
아무리 overdetermined 방정식이라도 해가 존재할 경우가 있다. 바로 우변의 벡터 b가 행렬 A의 column space에 존재할 때이다. 즉 A의 column 벡터들의 선형 조합(Linear combination)으로 b를 만들 수 있을 때를 말한다. 중간과정은 생략하고 결과만 보면 아래와 같다.
b가 A의 column space에 존재할 경우 값이 정확하게 일치하는 것을 볼 수 있다.
아래는 식 (11)의 MATLAB 코드
- Not invertible case
마지막으로 아예 최적해(best solution)조차 구할 수 없는 경우가 있다. 바로 행렬 A의 column이 dependent할 때 이다. Overdetermined system(m>n)에서 그나마 최적해라도 구하려면 행렬의 rank가 최소한 n과 같아야한다. 그러나 rank가 n보다 작을 경우엔 이 조차 불가능하다. 식(1)의 행렬을 아래와 같이 바꿔보자.
행렬 A의 col3은 col1+col2와 같다. 따라서 column vector는 종속(dependent)이다. A의 앞에 A의 transpose를 곱해보자.
연산 결과도 마찬가지로 col1+col2=col3인 것을 볼 수 있다. Full rank가 아니므로 역행렬이 존재하지 않는다. 따라서 행렬 A의 column이 dependent하면 최적해조차 구하는 것이 불가능하다. 결론적으로 ATA가 역행렬을 가지기 위해선 반드시 A의 column이 독립(independent)이어야 한다.
사실 Full rank가 아닌 행렬, 즉 rank-deficient overdetermined matrix에 대한 역행렬을 구하는 방법들이 있긴하다. 그러나 본 포스팅의 범위에서 벗어나므로 생략하도록 하겠다. 관심이 있다면 다음 링크 참조 Moore–Penrose pseudoinverse
아래는 식 (13)의 MATLAB 코드
3. 마치며
이번 포스팅에선 해가 존재하지 않는 선형연립방정식에 대한 최적해(best solution)를 구하는 방법에 대해서 알아보았다. 이번 포스팅의 내용을 잘 이해야지만 이후에 배울 투영 행렬(Projection matrix)와 최소자승법(Least square method)을 공부하는데에 무리가 없을 것이다. 잘 이해하고 넘어가도록 하자. Overdetermined system에 대해 좀 더 관심이 있다면 overdetermined-wiki를 참고하기 바란다. 그래프와 함께 잘 설명이 되어 있다.