פירוק לגורמים P)LU) גם באמצעות פייתון

מה זה פירוק לגורמים? אם אתה קורא מדריך על נושא די מתקדם בתחום האלגברה הלינארית אז אתה בטוח יודע. למשל, אפשר לפרק את המספר 42 למכפלה של 6 כפול 7 (42 = 7 * 6). אפשר גם לפרק אותו למכפלה של 2 כפול 21 (42 = 2 * 21).

פירוק LU עושה משהו דומה, אבל למטריצות! אנחנו מנסים לפרק מטריצה למכפלה של שתי מטריצות אחרות, שנקראות L ו-U. כשאנחנו עובדים על מטריצות זה עוזר לנו לפתור בעיות מסובכות בצורה יותר קלה.

המטריצה L היא מטריצה "משולשת תחתונה" (Lower Triangular Matrix), שזה אומר שכל המספרים מעל לאלכסון שלה הם אפסים. המטריצה U היא מטריצה "משולשת עליונה" (Upper Triangular Matrix), שזה אומר שכל המספרים מתחת לאלכסון שלה הם אפסים.

פירוק LU

במקום להשתמש במילים גבוהות, בואו נדגים איך לעשות פירוק LU למטריצה הבאה:

$$ A = \begin{bmatrix} 1 & 4 & 1 \\ 3 & 2 & 0 \\ 2 & 3 & 4 \end{bmatrix} $$

המטרה היא למצוא מטריצות L ו- U כך שיתקיים:

$$ A = LU $$

• A - המטריצה המקורית
• L - מטריצה משולשת תחתונה
• U - מטריצה משולשת עליונה

מתחילים

נתחיל מאתחול L כמטריצת יחידה בעלת אותם ממדים כמו A, ואילו U מאותחלת עם הערכים של A:

$$ \quad U = \begin{bmatrix} 1 & 4 & 1 \\ 3 & 2 & 0 \\ 2 & 3 & 4 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

צעד אלימנציה 1 : על השורה השנייה

בשביל לאפס את הפריט הראשון בשורה השנייה עושים:

$$ R2 = r2 - 3 * r1 $$

ועורכים את U ו- L בהתאם:

$$ U = \begin{bmatrix} 1 & 4 & 1 \\ 0 & -10 & -3 \\ 2 & 3 & 4 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ \textbf{3} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

את האלימינציה של גאוס בשביל לקבל את הצורה המשולשת העליונה עושים על U ואת ההיפך שלה עושים על L:

• בשביל לעשות אלימינציה של הפריט הראשון בשורה 2, מחליפים את שורה 2 בשורה 2 המקורית פחות 3 פעמיים שורה 1. דבר מאפס את הערך מתחת לציר בעמודה הראשונה. עד לפה אלימינציה של גאוס כרגיל.
• אבל פה צריך לשים לב 🤓 ! כי זה החלק החדש: מציבים את המכפיל (3) במיקום המתאים במטריצה L כי אם כפלנו במינוס 3 בשביל האלימינציה אז הפעולה ההפוכה היא לכפול בפלוס 3.

צעד אלימנציה 2 : על השורה השלישית

באופן דומה, כדי לאפס את הערך ב-(3,1), מחליפים את השורה השלישית כך:

$$ R3 = r3 - 2 * r1 $$

ועורכים את U ו- L בהתאם:

$$ U = \begin{bmatrix} 1 & 4 & 1 \\ 0 & -10 & -3 \\ 0 & -5 & 2 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ \textbf{2} & 0 & 1 \end{bmatrix} $$

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

צעד אלימנציה 3 : על העמודה השנייה בשורה השלישית

באופן דומה, כדי לאפס את הערך ב-(3,2), מחליפים את השורה השלישית כך:

$$ R3 = r3 - \frac{1}{2} * r2 $$

ועורכים את U ו- L בהתאם:

$$ U = \begin{bmatrix} 1 & 4 & 1 \\ 0 & -10 & -3 \\ 0 & 0 & 3 \frac{1}{2} \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & \frac{\textbf{1}}{\textbf{2}} & 1 \end{bmatrix} $$

וידוא

קיבלנו תוצאה. האם היא נכונה? לצורך הבדיקה נכפול את L ב-U ונראה אם הצלחנו לקבל את המטריצה המקורית:

$$ LU =? \quad A $$

$$ \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & \frac{\textbf{1}}{\textbf{2}} & 1 \end{bmatrix} \begin{bmatrix} 1 & 4 & 1 \\ 0 & -10 & -3 \\ 0 & 0 & 3 \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 1 & 4 & 1 \\ 3 & 2 & 0 \\ 2 & 3 & 4 \end{bmatrix} $$

כן. הצלחנו🎯!! אכן השוויון מתקיים מה שאומר שהצלחנו בפירוק.

פירוק PLU

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

$$ PA = LU $$

• A - המטריצה המקורית
• P - מטריצת תמורה (permutation matrix)
• L - מטריצה משולשת תחתונה
• U - מטריצה משולשת עליונה

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

מילים כמו חול. תראה לי דוגמה

נפרק את המטריצה הבאה:

$$ A = \begin{bmatrix} 0 & 2 & 3 \\ 1 & 4 & 5 \\ 2 & 6 & 8 \end{bmatrix} $$

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

נאתחל כמו שעשינו קודם אבל הפעם לבד מ-Lו-U נוסיף מטריצה שלישית, P, שתתעד את חילופי השורות.

$$ U = \begin{bmatrix} 0 & 2 & 3 \\ 1 & 4 & 5 \\ 2 & 6 & 8 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad P = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

• U - מטריצה משולשת עליונה הזהה למטריצה שרוצים לפרק.
• L - מטריצה משולשת תחתונה המתחילה כמטריצת זהות.
• והחידוש P - מטריצת תמורה 🤓 (permutation matrix) המתחילה כמטריצת זהות שממדיה שווים למטריצה שרוצים לפרק.

כדי שנוכל לפתור, נחליף את השורה הראשונה בשנייה מה שיצור לנו עוגן בעמדה (1,1):

$$ R1 \Leftrightarrow R2 \quad \quad U = \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 2 & 6 & 8 \end{bmatrix} $$

את החילוף שעשינו ב-U נעשה גם ב-P כיוון שתפקידה של המטריצה הוא לתעד את חילופי השורות:

$$ R1 \Leftrightarrow R2 \quad P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

אבל L אינה מושפעת מחילופי השורות ועל כן תשאר ללא שינוי:

$$ R1 \Leftrightarrow R2 \quad \quad U = \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 2 & 6 & 8 \end{bmatrix} \quad P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

כל יתר הצעדים, כל עוד לא מחליפים שורות, מתנהלים כמו שעשינו בפירוק LU:

$$ R3 = r3 - 2r1 \quad P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix} \quad U = \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 0 & -2 & -2 \end{bmatrix} $$

$$ R3 = r3 + r2 \quad P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & -1 & 1 \end{bmatrix} \quad U = \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 0 & 0 & 1 \end{bmatrix} $$

וידוא

קיבלנו תוצאה. האם היא נכונה? דרך אחת לבדוק זאת היא הבאה: האם מתקיים השיוויון?

$$ PA =? \quad LU $$

$$ PA = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & 2 & 3 \\ 1 & 4 & 5 \\ 2 & 6 & 8 \end{bmatrix} = \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 2 & 6 & 8 \end{bmatrix} $$

$$ LU = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 4 & 5 \\ 0 & 2 & 3 \\ 2 & 6 & 8 \end{bmatrix} $$

התוצאות שוות מה שאומר שהצלחנו בפירוק PLU 🥳🪩🕺!

פירוק PLU באמצעות פייתון

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

לצורך הפירוק, נעזר בספריית scipy של פייתון. ככה עושים את זה:

import numpy as np
from scipy.linalg import lu

A = np.array([[0, 2, 3], [1, 4, 5], [2, 6, 8]])

p, l, u = lu(A)

np.allclose(A, p @ l @ u)

מה תוצאות הפירוק?

p

array([[0., 1., 0.],
    [0., 0., 1.],
    [1., 0., 0.]])

l

array([[1. , 0. , 0. ],
    [0. , 1. , 0. ],
    [0.5, 0.5, 1. ]])

u

array([[ 2. ,  6. ,  8. ],
    [ 0. ,  2. ,  3. ],
    [ 0. ,  0. , -0.5]])

תוצאות הפירוק עשויות להיות שונות, כיוון שפירוק PLU אינו יחודי. עם זאת, כל פירוק תקף כל עוד מתקיים השוויון: A = PLU. נכפול את הגורמים ונקבל את התוצאה:

np.allclose(A, p @ l @ u)

array([[0., 2., 3.],
    [1., 4., 5.],
    [2., 6., 8.]])

תוצאת המכפלה היא אכן המטריצה המקורית 🎉!

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

np.allclose(np.dot(np.dot(p, l), u), A)

והתוצאה:

True

קל, נכון? הספריות האלה עושות את כל עבודת הרמת המשקולות הכבדות בשבילנו! 😊

מדריכים נוספים שעשויים לעניין אותך

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

מציאת יחס הזהב בתוך סדרת מספרים עולה באמצעות (קצת) אלגברה לינארית

SVD - Singular Value Decomposition באמצעות פייתון

לכל המדריכים בנושא של למידת מכונה

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים