אלגוריתם QR

באנליזה נומרית, אלגוריתם QR הוא אלגוריתם למציאת ערכים עצמיים ווקטורים עצמיים של מטריצה. סיבוכיות האלגוריתם עבור מטריצה בגודל $n\times n$ היא $𝒪(n^3)$. קיים אנלוג לאלגוריתם עבור פירוק לערכים סינגולאריים.

האלגוריתם פותח באופן עצמאי בסוף שנות החמישים על ידי מדען המחשב הבריטי ג'ון פרנסיס ועל ידי המתמטיקאית הרוסיה ורה קובלנובסקיה.

האלגוריתם

תהא מטריצה A שעבורה רוצים לחשב את הערכים העצמיים, ונגדיר A₀:=A. בצעד ה-k (כאשר k מתחיל מ-0) מחשבים פירוק QR של A_k=Q_kR_k כאשר Q_k היא מטריצה אורתוגונלית (כלומר Q^T = Q⁻¹) ו-R_k היא מטריצה משולשת עליונה. אחר כך מגדירים A_k+1 = R_kQ_k. נשיב לב כי:

$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^{𝖳}{A}_k{Q}_k,$

לכן כל A_k הן מטריצות דומות שלהן ערכים עצמאיים דומים. האלגוריתם יציב נומרית הודות להתבססות על התמרות אורתוגונליות דומות.

היסטוריה

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

לקריאה נוספת

• Trefethen, Lloyd N., and David Bau III. Numerical linear algebra. Vol. 50. Siam, 1997.