פירוק 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, מסת"ב 978-1421407944.

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