QR法のソースを表示

{{unreferenced|date=2021年1月20日 (水) 09:20 (UTC)}}
'''QR法'''（きゅーあーるほう、QR algorithm）は、行列Aの[[固有値]]を求める方法<ref>{{Cite web|和書|url=https://japanknowledge.com |title="固有値の数値計算法 - F. QR法", 『岩波 数学辞典』 |accessdate=2022-01-29 |publisher=JapanKnowledge}}</ref>の一つで、行列の[[QR分解]]を利用する反復計算法である。QR法は[[数値的安定性|数値解析的に安定]]な[[アルゴリズム]]である。

== 手順 ==

行列Aの次数をnとする。

まず

:<math>A_1=A</math>

とおく。以下、

:<math>A_k=Q_kR_k</math>
:<math>A_{k+1}=R_kQ_k\left(=Q_k^{-1}A_kQ_k\right)</math>
:<math>(k=1, 2, \cdots, m)</math>

と繰り返す。この繰り返し手順は[[相似|相似変換]]であるため、行列A<sub>1</sub>の固有値と行列A<sub>k</sub>の固有値はすべて一致する
（ただし、固有ベクトルは必ずしも一致しない）。したがって、固有ベクトルを求める必要があれば、行列A<sub>m+1</sub>の固有値を求めた後、
行列Aに戻って各固有値に対応する固有ベクトルをそれぞれ求めなければならない。
<!--
==計算量==
英語版にあるけどパス。
-->

== 特別な場合 ==
行列Aが[[対称行列]]である場合、
<!-- 英語版で挙げられているGolub and Van Loanの参考文献では違うのか?初版筆者は未調査 -->
相似変換後に得られる行列A<sub>m+1</sub>は
[[対角行列#三重対角行列|三重対角行列]]となる。

== 原点シフト付きQR法 ==
上記の素朴な手順では、A<sub>k</sub>が収束するまで繰り返すQR分解の回数が多くなりやすい。
このため、上記の繰り返しの手順を

:<math>A_k-\mu_kI=Q_kR_k</math>
:<math>A_{k+1}=R_kQ_k+\mu_kI\left(=Q_k^{-1}AQ_k\right)</math>
:<math>(k=1, 2, \cdots, m)</math>

と置き換えて、QR分解の回数を減らすことを狙う。
このような手順を原点移動付きQR法という。

シフト量μ<sub>k</sub>の選びかたとして、A<sub>k</sub>の右下隅の2×2小行列の2つの固有値のうちで、
A<sub>k</sub>の右下隅の値に近いものを選択する方法がよく用いられる（'''ウィルキンソンのシフト'''）。

これまでにQR法について行なわれた研究や計算法の改良は多く、それらすべてを簡潔に紹介することは不可能である。
最近（2025年）の和書であれば、文献<ref>張紹良(編)：「20世紀のトップ10アルゴリズム」、共立出版、ISBN 978-4-320-12267-3 (2022年1月15日)の第6章、山本有作：「QR法」</ref> およびそれに挙げられている参考文献などを参照されたい。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[QR分解]]
{{linear algebra}}
[[Category:数値線形代数|きゆうああるほう]]
[[Category:数学に関する記事|QRきゆうああるほう]]