פירוק אינטרפולטיבי

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

באנליזה נומרית פירוק אינטרפולטיבי (Interpolative decomposition) מציג מטריצה כמכפלה של שתי מטריצות, האחת בנויה מחלק מהעמודות של המטריצה המקורית, והשנייה מכילה תת-מטריצת יחידה וכל שאר האיברים שלה קטנים מ-2 בגודלם.

הרעיון של הפירוק, ומכאן גם שמו, הוא להציג מטריצה עם יתירות בעמודות (היתירות מתבטאת בדרגה נמוכה יותר ממספר העמודות) כהרחבה (או אינטרפולציה) של עמודות נבחרות מתוך המטריצה.

באנאליזה נומרית משתמשים בפירוק לא רק עבור המקרה שבו הדרגה נמוכה, אלא גם עבור המקרה שבו הדרגה הנומרית נמוכה, ואז הפירוק המתקבל מקרב את המטריצה המקורית בדיוק החישוב.

את הפירוק אפשר באופן דומה לבצע על שורות במקום עמודות.

הגדרה

תהי מטריצה בגודל מדרגה , אז ניתן להציג את כ:

כאשר:

  • היא תת-קבוצה של אינדקסים בגודל מתוך .
  • המטריצה היא מטריצה בגודל שמכילה את העמודות באינדקס של .
  • היא מטריצה בגודל שכל ערכיה בעלי נורמה קטנה מ-2. ל יש תת-מטריצת יחידה בגודל .

דוגמה

אם היא מטריצה בגודל מדרגה 2 :

אז הפירוק האינטרפולטיבי שלה ע"פ עמודות הוא:

ולפי שורות:

אלגוריתם לחישוב הפירוק

עבור מטריצה בגודל , נחשב באופן הבא את הפירוק האינטרפולטיבי שלה מסדר :

נחשב פירוק QR של A עם פרמוטצית עמודות: AP=QR
נסמן:  כאשר  היא מטריצה ,   היא מטריצה בגודל, ו  היא מטריצה 
נסמן:  כאשר  היא מטריצה  ו  היא מטריצה 
נחשב:  ונשים לב שקיימים  אינדקסים  כך ש 
נחשב:  כאשר  היא מטריצת היחידה בגודל 
ונקבל: 

לקריאה נוספת