Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
באנליזה נומרית, אלגוריתם QR הוא אלגוריתם למציאת ערכים עצמיים ווקטורים עצמיים של מטריצה. סיבוכיות האלגוריתם עבור מטריצה בגודל היא . קיים אנלוג לאלגוריתם עבור פירוק לערכים סינגולאריים.
האלגוריתם פותח באופן עצמאי בסוף שנות החמישים על ידי מדען המחשב הבריטי ג'ון פרנסיס ועל ידי המתמטיקאית הרוסיה ורה קובלנובסקיה.[1][2][3]
תהא מטריצה A שעבורה רוצים לחשב את הערכים העצמיים, ונגדיר A0:=A. בצעד ה-k (כאשר k מתחיל מ-0) מחשבים פירוק QR של Ak=QkRk כאשר Qk היא מטריצה אורתוגונלית (כלומר QT = Q−1) ו-Rk היא מטריצה משולשת עליונה. אחר כך מגדירים Ak+1 = RkQk. נשיב לב כי:
לכן כל Ak הן מטריצות דומות שלהן ערכים עצמאיים דומים. האלגוריתם יציב נומרית הודות להתבססות על התמרות אורתוגונליות דומות.
לאלגוריתם QR קדם אלגוריתם LR שהתבסס על פירוק LU ולא על פירוק QR. פירוק QR הוא יותר יציב ולכן אלגוריתם LR כמעט ואינו נמצא בשימוש כיום.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.