LU Decomposition Algorithm

LU Decomposition 정칙 정방 행렬 (Non-singular Square Matrix) 은 분해가 가능하다. 분해는 형태의 Linear System 을 직접적으로 (directly) 푸는 효율적인 방법이다. 일단 분해를 해놓으면 의 값에 상관없이 두번의 후 대입 (back substitution) 만으로 해를 구할 수 있다. 분해는 유일한 형태가 아니며, 그 형태에 따라 Doolittle, Crout, Cholesky 분해 알고리즘으로 나눠진다. 먼저 일반적인 형태를 알아보고 각각의…

Continue reading →

Schur / Real Schur Decomposition

Schur Decomposition (Complex) Schur Decomposition 은 정사각행렬 를 unitary 행렬 와 상삼각행렬 로 분해하는 방법이다. 즉, 로 분해된다. 이것은 Hermitian 행렬의 고유값 분해 의 일반화된 형태다. 즉, 가 실수 대칭행렬이거나 복소수 Hermitian 행렬이라면 는 대각행렬 가 된다. 행렬 는 대각화 가능 여부와는 별도로 하나의 고유값 와 그 고유벡터 를 가진다. 그러면 를 이용해서 임의의 unitary…

Continue reading →

3 ways of QR Decomposition and Hessenberg matrix

QR Decomposition 분해는 세가지 방법이 있다. 가장 기본적인 Gram-Schmidt 방법은 의 각 열들을 첫번째 열에 맞추어 차례로 직교화하는 방법을 사용한다. 결과적으로 은 Gram-Schmidt 과정에 따라 상삼각행렬이 된다. 나머지 두 방법 (Givens, Householder) 은 Gram-Schmidt 보다 효율적이다. 이 방법들은 가우스 소거 과정에서 나타났던 행 소거행렬 대신에 직교행렬 를 이용해 열 소거를 해서 최종적으로 상삼각행렬 로 변환한다….

Continue reading →