제목 없음

[Section 1][Section 2][Section 3]

본 내용은 Brooks/Cole 출판사의 "Numerical Linear Algebra by Biswa Nath Datta" 의 교재를 중심으로 이상구교수의 행렬이론 강의록의 내용과 합하여 성대에서 실제 강의를 하면서 만들어진 콘텐츠입니다. 디자인 및 자바프로그램 삽입과 타자, 정리는 백명국조교와 김덕선 조교가 하고 이상구교수 sglee@skku.edu 가 수정하여 마무리 하였습니다.

여기서는 기본적인 Numerical Linear Algebra의 문제가 무엇인지를 소개하고, 이 문제들의 중요성과 이런 문제들을 computationally 풀려고 할때 마주치는 어려움이 무엇인지 지적하고자 한다.

우선 NLA(Numerical Linear Algebra)의 기본 문제들을 아래 상자에 나열하였다.

The Linear System Problem

임의의 nonsigular 행렬 와 차원 vector 가 있을 때 를 만족하는 차원 벡터 를 구하는 문제

- 위의 문제와 관련된 변형의 대표적인 문제로 와 가 각각 nXm 행렬일 때 문제 를 만족하는 nXm 행렬 를 구하는 문제를 생각할 수 있다. 따라서 행렬의 null space, 치역(range) 에 대한 orthonomal basis를 구하는 문제, 행렬의 inverse, rank, determinant, leading principal minor를 구하는 문제등이 연계되며, 다양한 정사영 행렬을 찾는 문제등이 유도된다. 이런 문제들을 손쉽게 풀기 위해서 matrix factorization이 필요하기 때문에 두 문제는 서로 아주 밀접하게 관련되어 있다.

- 과장이 아니라 위의 문제는 과학과 공학의 모든 부분에 걸쳐 이용 된다. 응용수학, 물리학, 생물학, 화학, 전기, 전자, 기계, 토목, 진동공학과 선형계획법을 포함한 많은 경제학적, 또는 사회학적 문제를 푸는데도 도움이 된다. 위의 문제의 가장 큰 이용처는 미분방정식의 수치적해법을 제공하는 부분이다.

- 물리학이나 공학의 모델은 대개 상미분방정식이나 편미분방정식을 포함한다. 이런 문제는 대개 finite diffrence method(유한차분법) 나 finite element method(유한요소법) 로 이산화 시켜 선형연립방정식으로 바뀌어지고, 이 해가 원래 미분방정식 문제의 근사해로 주어지는 것이다. (자세한 것은 6장에서 설명)

The Least-Squares Problem(LSP)

임의의 행렬 와 차원 vector 가 있을 때 의 값이 가장 작은 차원 vector 를 찾는 문제를 Least-Square Problem이라고 한다.

- 이 문제는 실험한 데이터나, signal 또는 image processing 과 같은 공학적 응용에 다항식 또는 curve fitting 이 필요한 통계적 또는 기하학적 응용분야에서 생기는 중요한 문제이다. 7 장 에서는 이러한 least-square problem의 여러 가지 자세한 예를 제시하도록 한다. LSP를 수치적으로 푸는 문제는 자연스럽게 일차연립방정식의 해법에 이르게 한다.

The Eigenvalue Problem

임의의 행렬 가 있을 때,

를 만족하는 개의 scalar들인 와 nonzero vector 를 구하는 문제를 Eigenvalue Problem이라 한다.

- 고유값문제는 전형적으로 1계동차연립미분방정식의 해를 구하거나, stability를 분석하는데서 자연스럽게 제기된 문제이다. stability 분석에서는 고유값에 대한 implicit 한 지식만 있으면 충분하고, 반면 정확한 고유값과 고유벡터을 알기 위해서는 위의 식의 explicit 한 해가 필요하다.

- 일반적으로 Eigenvalue나 Eigenvector는 일반적으로 알고 있는 Characteristic Polynomial을 이용하여 푸는 것이 일반적이다. 그러나 이 경우 5차 이상의 방정식은 일반적인 해를 구하는 데에는 손쉬운 Computational Method가 존재하지 않는다.

- 그러나 실제로 Eigenvalue를 손쉽게 구하기 위해서 다른 방법들(Decomposition)들의 방법을 이용하여 해결하곤 한다. 이러한 방법을 제시하는 것도 NLA의 한 분야이다.

- Stock market 분석, Dynamic system 등 많은 응용에서는 모든 고유값이 필요한 것이 아니라 보통 가장 큰 고유값과 가장 작은 고유값등 몇 개만 필요한다. 또 대부분의 실제 경우 행렬은 대칭이 되어 symmetric eigenvalue problem 이 된다. 이런 것들을 8장에서 다루려 한다. 그러나 실제로 현장에서 만나는 고유값 문제의 대부분은 아래와 같은 일반화된 고유값문제이다.

The Generalized Eigenvalue Problem[GEP]

임의의 주어진 행렬 와 가 있을 때

를 만족하는 scalar들인 와 0 이 아닌 vector 를 구하는 문제를 Generalized Eigenvalue Problem이라 한다.

- 실제로 공학적인 분야에서는 위의 Eigenvalue보다도 더 포괄적인 개념을 가지는 Eigenvalue의 개념이 필요한 경우가 있다. 이 경우, 위의 Eigenvalue를 연산하는 것이 문제화 되며 이를 GEP라고 한다.

- GEP는 아래의 undamped (진동이 약해지지 않는) 2nd-ordered 연립미분방정식을 모델로 하는 Vibration Analysis 분야에서 자연스럽게 제기된다.

- 또한 이것의 damped (파장의 진폭이 감쇠되는) system

은 아래의 Quadratic Eigenvalue Problem (QEP) 를 유도해 낼 수 있다. GEP 와 QEP 에 대한 자세한 내용은 8장과 9장에서 다루겠습니다.

The Quadratic Eigenvalue Problem[QEP]

임의의 주어진 행렬 , , 가 있을 때 을 만족하는 scalar들인 와 0이 아닌 vector 를 구하는 문제를 Quadratic Eigenvalue Problem이라 한다.

- NLA의 또 다른 문제중 중요한 문제로 이야기할 수 있는 문제는 Decomposition문제이다. 이러한 Decomposition문제중 가장 강력하며, 그에 따른 응용도도 가장 높은 이론은 역시 Singular Value Decomposition(이하 SVD)일 것이다.

The Singualr Value Decomposition Problem[SVDP]

임의의 주어진 크기의 행렬 가 있을 때

를 만족하는 orthogonal matrix들인 와 , 그리고 대각행렬인 을 구하는 문제를 Singular Value Decomposition Problem이라 한다.

- 위의 문제는 control theory, biomedical 공학, Digital Signal Processing(DSP), 주성분분석(Principal Component Analysis:PCA)등에 많이 쓰이며, 이에 의하여 공학 및 각종 여러 사회과학에 많이 쓰인다. 이 이론은 행렬의 rank, 정규기저, 정사영 등을 필요로 한다. SVD 는, 특히 full rank 가 아닌 행렬 A 네 대하여, LSP을 해결하는 가장 효과적이 수치적인 해법이다.

위에서 제시했던 많은 문제를 대강 어떠한 방법으로 해결할 수 있는지, 그러한 접근방법에는 어떤 것들이 있을지에 대해서 알아보자.

Linear System Problem : Linear System을 풀기 위한 가장 쉬운 방법은 Cramer's Rule이 있다. 그러나 이 방법은 Computational Method에는 적합하지 않다. 따라서 이 방법에 대해서는 새로운 대안이 필요하다. Matrix의 역행렬을 구하는 문제도 마찬가지이다. 만일 우리가 Matrix의 역행렬을 구할 수만 있다면 의 형식을 이용하여 손쉽게 그 문제를 풀 수 있겠지만, 원래 행렬이 커지면 사람의 능력은 둘째치고서라도, 컴퓨터에서도 손쉽게 구하는 방법을 찾기란 어렵다.

이러한 방법의 개선책으로는 일단 Elimination의 방법을 생각할 수 있다. 대표적으로 Gaussian Elimination이 있을 것이며, 이것에 대한 오차를 줄이기 위한 방법을 Chapter6에서 소개하고 있다.

LSP(Least Squre Problem) : 만일 크기의 full rank를 가지는 행렬 가 있다고 하자. (단 ) 이 경우 LSP를 만족하는 를 구하기 위해서는 다음과 같은 Linear System을 풀어야 한다.

위의 식을 normal equation이라 한다. 실제로 이러한 equation은 실제로 푸는 과정에서 상당히 복잡한 과정을 수반한다. 따라서 이러한 해법을 Chapter 7에서 제시한다.

Computing Eigenvalue and Eigenvector : 우리가 일반적으로 Eigenvalue나 Eigenvector를 구하기 위해서는 Characteristic Polynomial을 풀어야 한다. 이러한 Polynomial을 푸는 방법이 이제까지 연구되어온 Numerical Analysis에서 많이 소개되어 왔다. 그러나 큰 크기의 행렬에 대해서 이러한 Polynomial에 의한 접근법은 상당히 비효율적이다. 이 Polynomial에서는 Error의 발생할 소지가 크고, 또한 굉장히 Sensitive한 Perturbation을 수반한다. 이러한 예제를 Chapter 3에서 소개하고 이러한 문제점을 극복하는 방법은 차후에 소개하도록 한다.
GEP and QEP : 위의 두 문제는 다음과 같은 식으로 정리할 수 있겠다.

따라서 위의 문제는 Matrix의 Inverse를 구하는 문제와 Eigenvalue를 구하는 두가지 문제로 축약된다.

SVD : SVD는 일단 대각성분이 모두 의 eigenvalue의 square root라는 점과 의 row vector와 의 row vector가 각각 eigenvalue에 대응하는 left, right eigenvector라는 점을 감안한다면 위의 Eigenvalue와 Eigenvector문제를 해결하면 손쉽게 극복할 수 있는 문제가 된다.