פירוק LU

באנליזה נומרית ובאלגברה ליניארית, פירוק LU הוא פירוק של מטריצה למכפלה של מטריצה משולשית תחתונה (לרוב מסומנת באות L, כסימן למילה Lower) ומטריצה משולשית עליונה (לרוב מסומנת באות U, כסימן למילה Upper). הפירוק הומצא על ידי אלן טיורינג. השימוש העיקרי של הפירוק הוא באלגוריתם לפתרון מערכת ריבועית של משוואות ליניאריות.

$A=LU\,$

לדוגמה, עבור מטריצה A בגודל 3x3 הפירוק יראה כך:

${\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{bmatrix}}={\begin{bmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\\\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}$

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

לא כל מטריצה ניתן לפרק בצורה זו. אולם, כל מטריצה ניתנת לפירוק LU בהינתן שמבצעים שינוי בסדר השורות או העמודות שלה. כלומר, בהינתן מטריצת פרמוטציות (חילופים) ריבועית $P$ הפועלת על שורות המטריצה, ניתן לקבל:

$PA=LU$

פירוק LU בצורה כזו, נקרא פירוק עם Partial Pivoting, בניגוד לפירוק Full Pivoting, בו מעורבות מטריצות פרמוטציות מימין ומשמאל:

$PAQ=LU$

למרות שפירוק זה הוא תמיד יציב נומרית, ברוב המקרים אין בו צורך, שכן מספיק להשתמש ב-Partial Pivoting, שהוא בעל סיבוכיות חישוב קטנה יותר. עם זאת, יתרון של ה-Full Pivoting הוא היותו פירוק "מגלה דרגה" (Rank Revealing).

יתרונות של פירוק LU על פני חישובים אחרים הוא סיבוכיות קטנה (בהיבט הקבוע) ביחס לפירוקים אחרים כגון SVD ו-QR, היתרון שניתן לחשב אותו "In place" (מבלי לבצע הקצאות זיכרון למטריצות נוספות). יתרון חשוב נוסף הוא שהפירוק יעיל מאוד כשהוא מופעל על מטריצות דלילות. תהליך ה Pivoting מאפשר ליצור אזורים גדולים של אפסים, כך שבאופן תאורטי הסיבוכיות תלויה רק במספר האיברים שאינם אפס, בניגוד לגודל המטריצה.

במקרה המיוחד שבו המטריצה $A$ היא הרמיטית מוגדרת חיובית אפשר לפרק אותה באופן הבא:

$A=LL^{*}$

פירוק זה נקרא "פירוק שולסקי".

לקריאה נוספת

• Golub, Gene H.; Van Loan, Charles F. (2013), Matrix Computations (4th ed.), Johns Hopkins, ISBN 978-1421407944.

קישורים חיצוניים

מדיה וקבצים בנושא פירוק LU בוויקישיתוף

• פירוק LU, באתר MathWorld (באנגלית)

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