הצגת המקור של הדף "אלגוריתם QR"

ב[[אנליזה נומרית]], '''אלגוריתם QR''' הוא [[אלגוריתם]] למציאת [[ערכים עצמיים]] ו[[וקטורים עצמיים]] של [[מטריצה]]. [[סיבוכיות]] האלגוריתם עבור מטריצה בגודל <math> n \times n </math> היא <math> \mathcal{O}(n^3) </math>. קיים אנלוג לאלגוריתם עבור פירוק ל[[פירוק לערכים סינגולריים|ערכים סינגולאריים]].

האלגוריתם פותח באופן עצמאי בסוף שנות החמישים על ידי מדען המחשב הבריטי ג'ון פרנסיס ועל ידי המתמטיקאית הרוסיה ורה קובלנובסקיה.<ref>J.G.F. Francis, "The QR Transformation, I", ''[[The Computer Journal]]'', '''4'''(3), pages 265–271 (1961, received October 1959). [[doi:10.1093/comjnl/4.3.265]]</ref><ref>{{cite journal |first=J. G. F. |last=Francis |title=The QR Transformation, II |journal=The Computer Journal |volume=4 |issue=4 |pages=332–345 |year=1962 |doi=10.1093/comjnl/4.4.332}}</ref><ref>
Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," ''USSR Computational Mathematics and Mathematical Physics'', vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: ''Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki'', vol.1, no. 4, pages 555–570 (1961). [[doi:10.1016/0041-5553(63)90168-X]]</ref>

==האלגוריתם==
תהא מטריצה ''A'' שעבורה רוצים לחשב את הערכים העצמיים, ונגדיר ''A''<sub>0</sub>:=''A''. בצעד ה-k (כאשר k מתחיל מ-0) מחשבים [[פירוק QR]] של ''A''<sub>''k''</sub>=''Q''<sub>''k''</sub>''R''<sub>''k''</sub> כאשר ''Q''<sub>''k''</sub> היא [[מטריצה אורתוגונלית]] (כלומר ''Q''<sup>''T''</sup> = ''Q''<sup>−1</sup>) ו-''R''<sub>''k''</sub> היא מטריצה משולשת עליונה. אחר כך מגדירים ''A''<sub>''k''+1</sub> = ''R''<sub>''k''</sub>''Q''<sub>''k''</sub>. נשיב לב כי:
:<math> A_{k+1} = R_k Q_k = Q_k^{-1} Q_k R_k Q_k = Q_k^{-1} A_k Q_k = Q_k^{\mathsf{T}} A_k Q_k, </math>
לכן כל ''A''<sub>''k''</sub> הן [[דמיון מטריצות|מטריצות דומות]] שלהן ערכים עצמאיים דומים. האלגוריתם [[יציבות נומרית|יציב נומרית]] הודות להתבססות על התמרות אורתוגונליות דומות.

==היסטוריה==
לאלגוריתם QR קדם אלגוריתם LR שהתבסס על [[פירוק LU]] ולא על פירוק QR. פירוק QR הוא יותר יציב ולכן אלגוריתם LR כמעט ואינו נמצא בשימוש כיום.

==לקריאה נוספת==
<div class="mw-content-ltr">
* Trefethen, Lloyd N., and David Bau III. Numerical linear algebra. Vol. 50. Siam, 1997.
</div>

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}
{{קצרמר|מתמטיקה|מדעי המחשב}}
[[קטגוריה:אלגברה ליניארית]]
[[קטגוריה:אלגוריתמים]]
[[קטגוריה:אנליזה נומרית]]