2010.11.16 16:37



콜레스키 분해를 왜 사용하는가?

양정부호행렬을 하삼각행렬과 그 전치행렬의 곱으로 표현하는 것이다.
무슨말인지 어렵죠 ^^;;

하지만 콜레스키 분해는 계산상으로 매우중요합니다.
우선 LU분해에서 걸리는 시간의 절반밖에 안걸린다는 점
게다가 수치상으로 안정적이기에 다른 알고리즘과 비교했을 때
누적되는 오차가 적다는 점
이라는 큰 장점을 가지고 있습니다.

하지만 그만큼 단점도 있다.
단점은 아직 저도 찾지 못했습니다. 아시는 분은 리플을^^;;



이게 어디에 사용되는지 알아보자!

최적화 문제의 답을 수치해석적으로 구해야하는 경우가 있습니다.
목적함수가 터무니 없이 이상하게 생기지 않으면 가중최소제곱법을 반복하여 답을 구할 수가 있습니다.
이때 가중최소제곱의 답을 구할 때 콜레스키 분해를 이용하는 방법이 있다고 합니다.
이 밖에도 회귀선 추정에도 이용한다고 한다고 합니다.



그럼 콜레스키 분해에 대해서 자세히 파헤쳐 봅시다!

콜레스키 분해를 공부하기전
대칭행렬(symmetric matrix)와 정칙행렬(nonsigular matrix)이 무엇인지 알아야합니다.




대칭행렬 (symmetric matrix)

Aij = Aji 인 행렬을 말한다.
한마디로 어떤행렬의 전치행렬이 원래 행렬과 같은 행렬을 뜻한다.


예를 들어보면

행렬 A             A의 전치행렬
| 2  3 |             | 2  3  |
| 3  2 |             | 3  2  |

행렬 A 와 A의 대칭행렬이 같기 때문에 이는 대칭행렬 입니다.



정칙행렬 (nonsigular matrix)

행렬식의 값이 영이 아닌 행렬을 정칙행렬이라 합니다.
Det != 0
한마디로 역행렬을 가지는 행렬을 정칙행렬이라고도 합니다.

예를 들어보면

행렬 A                 A의 Det 행렬식 은
|  1  3  |               ( 1 * 3 )  - (3 * 1)  = 0
|  1  3  | 

행렬 A의 행렬식 값이 0이기 때문에 이는 역행렬이 존재하지 않으면서 정칙행렬이 아닙니다.




그럼 콜레스키 분해를 사용하기 위한 조건에 대해 알아 봅시다!

그럼 콜레스키 분해를 아무때나 무작정 사용하지는 않을 것입니다.
콜레스키라는 사람은
정칙행렬 A가 대칭행렬일 경우 사용할 수 있습니다. 라고 정의를 하였습니다.
한마디로 역행렬이 존재하면서 행과 열을 바꿔도 같은 행렬인 경우 사용이 가능하다는 것이죠



그럼 어떻게 분해가 가능한지 알아볼가요?

위 조건을 만족하는 행렬 A가 있습니다.
이 행렬 A의 하부삼각행렬 L 이라 하고
이 L의 전치행렬을 U 라 하면
U는 A의 상부삼각행렬이 같음을 알수 있습니다.
이 행렬의 곱 LU 는 A 와 같다는 것으로
즉 하부삼각행렬과 상부행렬의 곱은 행렬 A와 같다.

행렬 A를 하부삼각행렬과 상부삼각행렬로 나눌수 있다는 것입니다.
하부삼각행렬과 상부삼각행렬로 나눠서 계산을 한다면
연산량이 줄어들 수 밖에 없다는 것입니다.




말로 표현하니 어려우니 식으로 한번 표현해보겠습니다.

행렬 A  가 있습니다. (이는 역행렬이 존재하는 정칙행렬입니다.)
| A11   A12   A13  |
| A12   A22   A2 |
| A13   A23   A33  |

행렬 A의 전치행렬은 (행렬 A와 같기 때문에 이는 대칭행렬 입니다.)
| A11   A12   A13  |
| A12   A22   A2 |
| A13   A23   A33  |

그럼 콜레스키분해가 가능 조건에 해당 합니다.


하부삼각행렬 L을 구해봅시다.
| A11      0      0  |
| A12   A22      0  |
| A13   A23    A33 |

하부삼각행렬 L의 전치행렬 U를 구해봅시다. (이는 상부삼각행렬이랑 같음을 알 수 있습니다.)
| A11   A12   A13  |
|     0  A22   A2 |
|     0     0   A33  |

앞으로 하부삼각행렬은 L 상부삼각행렬은 U라 표현하겠습니다.


콜레스키라는 사람이 제안한 방법은  L과 U의 곱은 A와 같다는 것입니다.


이게 콜레스키 분해 입니다.^^




위의 식을 풀면 일반적인 공식도 유도가 가능합니다.

위의 식도 복잡함 감이 있습니다. 
그래서 사람들은 이미 위의 식을 쉽게 풀수 있는 방법을 찾아
공식을 유도해 냈습니다.


결과는







식의 유도가 가능하며 각 행렬의 값을 쉽게 구할 수가 있습니다.

하지만 여기서 주의할 점은 L
kk 를 구할때는 음수의 제곱근이 간간히 나오는 경우가 있습니다.
하지만 행렬 A가 양의 정부호이면 이런경우는 발생하지 않습니다.


이제 내용과 의미를 아셨다면 실전에 사용할 수 있도록 코딩 들어가셔야죠 ^^



도움이 되셨다면 리플 부탁드립니다 !
리플 하나가 큰 힘이 된답니다 ^^

Posted by 차출발 차출발