QR 分解(一般形)
A を 行列、 とします。このとき、m 次の正則行列 S と n 次の置換行列 P があって
と書けます。ただし、B は対角成分が 0 でないような r 次の上三角行列。
ここで、 を QR 分解(後述)して と表せたとします。ただし Q は m 次の unitary 行列、R は対角成分が 0 でないような m 次の上三角行列。すると
ですが、ここで
(ただし は r 次の、 は (m - r) 次の、対角成分が 0 でないような上三角行列)
と書き表すと
… (*)
で、 は上三角行列同士の積なのでやはり上三角行列であり、対角成分は 0 ではありません。したがって、(*) の右辺は上三角型の 行列なので、これを R とおけば
と、unitary 行列と上三角型の行列に分解できたことになります。これを 行列の QR 分解と言います。
正則行列の QR 分解
では、A を m 次の正則行列に限った場合の QR 分解の手順を説明します。以下の手順に従って、順次 を作ります。
Step 1
k := 1 , とおく。
Step 2
とおく。
ならば とおいて、 を
で定めて Step 4 へ。そうでなければ Step 3 へ。
Step 3
とおき、
とおくと、明らかに かつ
である。
とおいて (Hausholder 行列) とおくと
によって が定まる。 とおいて Step 4 へ。
Step 4
k := k + 1 とおく。k = m なら Step 5 へ、そうでなければ Step 2 へ。
Step 5
は unitary かつ だから
とおけばよい。