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 차출발 차출발

댓글을 달아 주세요

  1. pnu 2010.12.15 22:20  댓글주소  수정/삭제  댓글쓰기

    좋은정보감사해요~!

  2. 1 2011.01.06 14:34  댓글주소  수정/삭제  댓글쓰기

    인터넷서 많이 찾았는데 가장 쉽게 설명하셨네요! 감사합니다~

  3. 조성욱 2011.07.30 00:36  댓글주소  수정/삭제  댓글쓰기

    한 가지 틀린 부분이 있는데요 nonsingular matrix부분에 행렬식이 0이 아닐 때 nonsingular matrix라고 하는 것 보다 SVD를 수행하였을 때 diagonal matrix의 각 항들 중 0이 존재하지 않을 때를 nonsingular matrix라고 합니다. 그외의 설명은 너무 잘해주셔서 감사합니다.

  4. Multilevel 2011.09.18 19:23  댓글주소  수정/삭제  댓글쓰기

    훌륭하십니다~!!! 좋은 정보 진심으로 감사~!!!

  5. qp 2011.10.06 15:59  댓글주소  수정/삭제  댓글쓰기

    좋은 정보 감사합니다.

  6. 제이떱 2011.12.31 23:33  댓글주소  수정/삭제  댓글쓰기

    좋은 정보 잘 보고 갑니다!

  7. BlogIcon 천재 2012.10.23 18:36  댓글주소  수정/삭제  댓글쓰기

    정말 가장 쉽게 잘 설명하셨네요.
    좋은 정보 감사합니다.
    담아갈께요~. ^^

  8. 사과나무 2013.02.06 16:47  댓글주소  수정/삭제  댓글쓰기

    오늘 세미나인데 이해를 높이고 갑니다! 감사해요.

  9. 김준형 2014.10.17 22:15  댓글주소  수정/삭제  댓글쓰기

    cholesky factorization의 문제점은 컨디션 넘버가 제곱으로 증가해서 안정도가 떨어진다는 점입니다. 만약 ill-conditioned system의 경우 ... 문제가 되죠 그리고 라운드 오프등의 에러를 발생시킵니다 제곱연산을 하기때문에 생기는 문제라서 위에 언급한것과 같은 문제점이라 할 수 있겠네요

  10. ㅎㅇㄷㅈ 2018.10.14 15:02  댓글주소  수정/삭제  댓글쓰기

    감사합니다