QR 분해

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

QR 분해(QR decomposition, QR factorization)는 행렬 분해의 일종으로 임의의 행렬직교행렬상삼각행렬의 곱으로 분해하는 방법이다. QR 분해는 선형 최소제곱법을 풀 때나 고유벡터를 구할 때 등의 상황에 사용되며, 그람-슈미트 직교정규화 혹은 하우스홀더 행렬, 기븐스 회전 등을 사용한다.

정의[편집]

는 임의의 정사각행렬,



직교 행렬
상삼각 행렬
단위 행렬
전치 행렬

분해 방법[편집]

그람-슈미트 방법[편집]

벡터 일차독립이라 하자. 행렬 에 대해, 그람-슈미트 직교정규화를 사용하면

사영 연산자를 이용해서

와 같이 직교정규기저 를 얻을 수 있다.

내적 노름

위 식을 다시 정리하면

가 되므로,

와 같이 놓으면 이 성립한다.

[편집]

정규 직교 행렬 의 성질을 갖고있고,

따라서, 는 다음과 같이 그람-슈미트 절차를 따라서,

그리고,

확인해보면,

이므로,
이다.
분해 된다.

그러나,

분수에의한 부동소수점연산이 관계함으로 오차가 발생할수있다.

RQ 분해와의 관계[편집]

분해는 행렬 상삼각행렬 (직각 삼각형이라고도 함) 및 직교 행렬 의 곱으로 변환한다. 분해와의 유일한 차이점은 행렬의 순서이다.

분해는 첫 번째 열에서 시작된 행렬의 열의 그람-슈미트 직교화이다.

분해는 마지막 행에서 시작하는 행렬의 행의 그람-슈미트 직교화이다.

장점과 단점[편집]

그람-슈미트 프로세스는 본질적으로 수치적으로 불안정할수있다. 투영법의 적용에는 직교화에 대한 주요한 기하학적 유추가 있지만 직교화 자체는 수치 오류가 발생하기 쉽다. 그러나 구현의 용이함이 중요한 장점이다. 사전 작성된 선형 대수 라이브러리(library)를 사용할 수 없거나 용이하지 않은 경우, 이 알고리즘을 프로토타입(prototype)에 사용할 수있는 유용한 알고리즘으로 적용할수있다.

하우스홀더 방법[편집]

하우스홀더 리플렉터(하우스홀더 변환,Householder reflection)를 이용하여 한 열씩을 상삼각행렬로 바꾸어감으로써 을 구할 수 있다. 이 방법은 행렬을 하우스홀더 행렬의 곱으로 구해주기 때문에, 직접 를 구할 필요가 없을 때 유용하다. 또, 그람-슈미트 방법과는 달리, 부동소수점 연산에서도 오차가 누적되지 않기 때문에, 실제로 더 많이 활용된다.

[편집]

먼저 행렬 의 첫 번째 열을 벡터로 변환하는 리플렉션을 찾아야한다.

에서,
벡터

따라서,

하우스홀더 행렬 에서,

확인해보면,

삼각행렬에 접근하고 있음을 알수있다. 열에서 의 성분 값을 으로 만들면 상삼각행렬을 얻게 된다.

소행렬식에서 다시 위의 절차를 반복해보면,

위와 같은 방법으로 하우스홀더 변환(Householder transformation)된 행렬을 얻고,

에서 각각 전치행렬을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고,

그리고나서,

그리고,

행렬 직교행렬이고 상삼각행렬이되고 분해된다.

기븐스 회전[편집]

기븐스 행렬은 특정위치에서 성분값을 으로 조작할수있는 방법으로 기븐스 회전을 제공한다.

이것은 임의의 행렬을 직교행렬과 특정위치의 성분값이 상삼각행렬로 분해되게 유도할수있게된다.

[편집]

으로 조작된다.

그리고 도 이러한 절차를 반복한다.

그리고 으로 조작된다.

결과로 상삼각행렬을 얻는다. 따라서,

직교행렬에서,

그리고, 이다.

로 분해된다.

함께 보기[편집]

참고[편집]

http://mathworld.wolfram.com/QRDecomposition.html