QR factorization(QR 분해)란

  안녕하세요..^^* 오랜만에 글을 쓰네요. 오늘은 QR 분해에 대해서 알아 보도록 하겠습니다. Ax=b라는 행렬을 풀기 위해서 Gram-schmidt process라는 미친짓을 해서가지 QRx=b라는 것을 풀어야 하는 것일까요? 행렬이 행과 열이 커지면 커질수록 elemetary row operation로 푸는 것 보다 더 힘들어서 그런 것일까요? 실제로 컴퓨터가 계산하는 것은 저희가 배우는 가우스 소거법이나 연립방정식으로 푸는 것 보다 훨씬 빠르다고 하네요. Q가 orthonomal하게 만들어서 양변에 Q transpose를 곱해주어서 실제로 Q*t(Q)=I 이고 실제로 Q의 행렬의 역행렬을 곱하는 것이 아니라 transpose를 곱해 주어서 더 쉽게 만드는 과정이라고 할 수 있겠습니다. 프로그래밍은 잘 되어 있지만 실제 증명은 잘 없더라구요. 그래서 한번 증명해 보겠습니다.

  일단 QR 분해의 정의구요. 다들 선형대수를 하셨다면 쉽게 이해하실 수 있으실 거라고 믿습니다.

  그램 슈미트 직교화 과정을 통해서 요렇게 만들어 주는 겁니다. 그럼 A라는 행렬은 이렇게 QR로 나오는데요.

  그런데 R이 determinant가 0이면 A의 해는 무수히 많거나 없겠죠. 그러니 당연히 R은 non singular인 것을 보여줘야 합니다. 1번은 그램 슈미트 직교화 과정을 쓰면 당연히 orthonomal이 될 것이고 3번은 우리가 uppper trangular를 잡았으니까 당연히 맞겠죠. 그럼 2번을 귀류법으로 증명해 보는 겁니다. r중 하나가 0이라면 당연히 linearly independent 즉 일차독립이 안될 것이기 때문에 모순이 생기겠죠.

  어떤가요?? 생각보다 증명은 어렵지 않습니다. 행렬을 어떻게 분해해서 빨리 풀것인가라는 고민들을 해 놓은 것들이 꽤나 저는 멋있었습니다. 그럼 오늘은 여기서 이만 마치겠습니다.^^*