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

תזכורות

אלימינצית גאוס

אנו עושים שימוש בפעולות בסיסיות כדי לפתור ממ"ל ע"י פעולות על המטריצה המורחבת $[A,\underline{b}]$ של הבעיה.

\begin{pmatrix} 1 & 2 & 1 \\ 2 & 6 & 1 \\ 1 & 1 & 4 \end{pmatrix}\begin{pmatrix} x \\ y \\ z \end{pmatrix}=\begin{pmatrix} 2 \\ 7 \\ 3 \end{pmatrix}\implies (A|\underline{b})=\left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 2 & 6 & 1 & 7 \\ 1 & 1 & 4 & 3 \end{array}\right)

נפעיל סדרת פעולות בסיסיות:

\implies \left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -1 & 3 \\ 0 & -1 & 3 & 1 \end{array}\right)\implies \left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -1 & 3 \\ 0 & 0 & 2.5 & 2.5 \end{array}\right)\implies z=1 \implies y=2 \implies x=-3

נסתכל כעת באופן מעט שונה על התהליך.

\begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 2 & 6 & 1 & 7 \\ 1 & 1 & 4 & 3 \end{array}\right)=\left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -1 & 3 \\ 1 & 1 & 4 & 3 \end{array}\right)

נשים לב שזוהי בעצם מטריצה אלמנטרית. אפשר להמשיך ולהכפיל מטריצות ובסוף להגיע לאותה התוצאה.

\underbracket{\begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}}_{E_{1}}\underbracket{\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{pmatrix}}_{E_{2}}\underbracket{\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \frac{1}{2} & 1 \end{pmatrix}}_{E_{3}}\cdot \left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 2 & 6 & 1 & 7 \\ 1 & 1 & 4 & 3 \end{array}\right)=\left(\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -1 & 3 \\ 0 & 0 & 2.5 & 2.5 \end{array}\right)

נביט שוב במטריצות האלו. נשים לב כי הן בעל מבנה מיוחד:

כל איברי אלכסונן הם $1$ -ים. (זאת כי לכל שורה פעולתנו משמרת את השורה ומוסיפה/מחסירה לה שורה אחרת המוכפלת בסקלר)
אלה מטריצות משולשות תחתונות (כי תמיד אנו מצרים לשורה שורות מעליה)

מטריצות אלו נקראות מטריצות משולשות תחתונות בסיסיות.

הערה

נשים לב כי לכל מטריצה שכזו במקרה הזה בלבד יש רק שינוי אחד ל- $I$ וזו בגלל שכל מטריצה פה בלבד טיפלה בנושא אחד בלבד.

נסתכל שוב על המטריצה הזו ונחשב את $E_{i}^{-1}$ לכל אחת מהן. במקום ללכת בדרך הרגילה, נוכל לראות טריק: מכיוון שהמטריצה הזו היא בעצם אפקט, אנחנו הופכים את ההאפקט ומקבלים את ההפיכה.

E_{1}^{-1}=L_{1}=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \qquad E_{2}^{-1}=L_{2}=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \qquad E_{3}^{-1}=L_{3}=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -\frac{1}{2} & 1 \end{pmatrix}

נשים לב כי גם הן משולשות תחתונות בסיסיות כמו המטריצות ממקודם.

עד כה, לקחנו ממ"ל $A\underline{x}=\underline{b}$ והמרנו אותה במערכת השקולה לה $E_{3}E_{2}E_{1}A\underline{x}=E_{3}E_{2}E_{1}\underline{b}$ .
מה קרה למטריצה בסוף? קיבלנו מטריצה משולשת עליונה $\begin{pmatrix}1&2&1\\0&2&-1\\0&0&2.5\end{pmatrix}$ כפול מטריצות משולשות תחתונות בסיסיות. נסמן אותה ב- $U$ (כן, זה אותו $U$ של ה- $LU$ )

הערה (מדוע המערכות שקולות)

כיוון שהמטריצות שהכפלנו ריבועיות והפיכות.

\begin{matrix} E_{3}E_{2}E_{1}A\underline{x}=E_{3}E_{2}E_{1}\underline{b} \\ \Downarrow \\ U\underline{x}=E_{3}E_{2}E_{1}\underline{b} \\ \Downarrow \\ \underline{b}=(E_{3}E_{2}E_{1})^{-1}U\underline{x}\underset{\begin{matrix} \downarrow \\ \R{\text{לפי משפט מאלגברה}} \end{matrix}}{=} L_{1}L_{2}L_{3}U\underline{x} \end{matrix}

הערה

המכפלה $L=L_{1}L_{2}L_{3}$ מתקבלת ללא חישובים כלל(מדוע??)

נשים לב כי כפל של כל המטריצות המשולשות תחתונות בסיסיות נותן לנו עוד מטריצה משולשת תחתונה בסיסית:

L=L_{1}L_{2}L_{3}=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -\frac{1}{2} & 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}

ואז:

\underline{b}=LU\underline{x}

מערכת המשוואות המקורית הפכה למערכת משוואת של כפולה של מטריצה משולשת עליונה( $U$ ) במטריצה משולשת תחתונה( $L$ ). כעת, נגלה עוד דבר מעניין ביותר:

\underline{b}=A\underline{x}=LU\underline{x}

\Downarrow

A=LU=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 2 & -1 \\ 0 & 0 & 2.5 \end{pmatrix}

הערה

פירוק זה לא תלוי ב- $b$ כלל וכולו נובע מ- $A$ עצמה.

לא כל מטריצה ריבועית ניתנת לפירוק $LU$ . עוד מעט נראה גרסה למשפט שיפתור לנו את כל הבעיות.

הפירוק באופן כללי

הגדרה 1 (מטריצה רגילה)

מטריצה $A$ נקראת מטריצה רגילה אם היא ריבועית וניתן לפרקה למכפלה מהצורה $A=LU$ כאשר

$L$ מטריצה משולשת תחתונה בסיסית.
$U$ מטריצה משולשת עליונה כלשהי עם איברי אלכסון ראשי שונים מאפס.

משפט

הפירוק הנ"ל עבור מטריצה רגילה הינו יחיד!

כרגע, נביט רק על מטריצות רגילות ובהמשך נראה מה קורה כשהפירוק נכשל.
השימוש המרכזי לפירוק $LU$ הוא לטובת פתרון ממ"לים.

\underline{b}=A\underline{x}=LU\underline{x}=L(U\underline{x})=L\underline{y}

כצעד ראשון עלינו לפתור את המערכת הבאה ע"י החלפה קדמית - זהו תהליך סדרתי שיתחיל בחישוב $y_{1}$ ויעבור ל- $y_{2}$ וכך עד $y_{n}$ :

\begin{pmatrix} 1 & 0 & 0 & 0 & \dots & 0 \\ \ell_{12} & 1 & 0 & 0 & \dots & 0 \\ \ell_{31} & \ell_{32} & 1 & 0 & \dots & 0 \\ \ell_{41} & \ell_{42} & \ell_{43} & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \ell_{n1} & \ell_{n2} & \ell_{n3} & \ell_{n4} & \dots & 1 \end{pmatrix}\begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \vdots \\ y_{n} \end{pmatrix}=\begin{pmatrix} b_{1} \\ b_{2} \\ b_{3} \\ b_{4} \\ \vdots \\ b_{n} \end{pmatrix}

האם יכול להיות מצב שלמערכת משוואות זו אין פתרון? לא! זאת מכיוון ש- $|A|=1$ ולכן, לפי משפט, המטריצה הפיכה ולכן קיים פתרון.
למערכת זו קל למצוא פתרון ולכן מאוד קל למצוא את מה שצריך. כעת, נמצא את מה שאנחנו צריכים ע"י פתירה בהחלפה אחורית - מתחילים בחישוב $x_{n}$ ואז ממשיכים עד ל- $x_{1}$ .

\begin{pmatrix} u_{11} & u_{12} & u_{13} & u_{14} & \dots & u_{1n} \\ 0 & u_{22} & u_{23} & u_{24} & \dots & u_{2n} \\ 0 & 0 & u_{33} & u_{34} & \dots & u_{3n} \\ 0 & 0 & 0 & u_{44} & \dots & u_{4n} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & u_{nn} \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ \vdots \\ x_{n} \end{pmatrix}=\begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \vdots \\ y_{n} \end{pmatrix}

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

מסקנה (לסיכום)

בהינתן מערכת משוואת $A\underline{x}=\underline{b}$ עם מטריצה $A$ רגילה נוכל לבחור באחת משתי האפשרויות הבאות:

חישוב פירוק $A=UL$ ואז חישוב הפתרון עי"י החלפה קדמית ואז אחורית.
חישוב המטריצה ההפיכה $A^{-1}$ ואז חישוב הפתרון ע"י $A^{-1}\underline{b}$ .

הפתרון הראשון עדיף בהרבה שכן הוא הרבה יותר קל והרבה פחות פרוץ לטעויות.

כמות החישובים בפירוק $UL$

חישוב המכפלה הסופית:
כמות החישובים הנדרשים לחישוב המכפלה של מטריצה בגודל $n\times n$ בוקטור היא $n^2$ פעולות.
כמות החישובים הנדרשים לתהליך החלפה קדמי/אחורי הוא $\frac{1}{2}n^2$ כאשר אנו סופרים רק מכפלות וחלוקות כשווי מעמד

כשמחשבים רואים שמציאת הפתרון אחרי חישוב $A^{-1}$ זהה לחישוב הפתרון לאחר שמוצאים פירוק $LU$ . לכן, ההבדל ביעילות יבוא בהכרח ממציאת $LU$ ומציאת $A^{-1}$ .

מספר הפעולות הנדרש לפעולות $LU$ הוא $\frac{n^3}{3}$ פעולות. (אולי נקבל את זה בתרגיל בית להוכחה)
כמה חישובים נדרשים לחישוב $A^{-1}$ ?

AX=I

מתקבלות $n$ מערכות משוואות שיש לפתור:

\begin{matrix} A\begin{pmatrix} x_{11} \\ x_{21} \\ x_{31} \\ x_{41} \\ \vdots \\ x_{n1} \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} & A\begin{pmatrix} x_{12} \\ x_{22} \\ x_{32} \\ x_{42} \\ \vdots \\ x_{n2} \end{pmatrix}=\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} & \dots & A\begin{pmatrix} x_{1n} \\ x_{2n} \\ x_{3n} \\ x_{4n} \\ \vdots \\ x_{nn} \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix} \end{matrix}

נדרש לפתור את כל המערכות הללו על מנת למצוא את $A^{-1}$ . נשים לב שכדי לעשות את זה נוכל לעשות:

לקחת את $A$ ולבצע לו פירוק $LU$ וזה $\frac{n^3}{3}$ פעולות
לכל אחת מ- $n$ המערכות נבצע תהליך החלפה אחורית/קדמית - $n^3$

ולכן, בסה"כ חישוב הפתרון הוא $4 \frac{n^3}{3}$ .
הוא עובד בעצם פי 4 יותר קשה מאשר פירוק ה- $LU$ לבדו.

הערה

אמנם הסיבוכיות זהה $\Theta(n^3)$ אבל בעולם האמיתי יש הבדל עצום בזמן.

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

פרמוטציות

דוגמה

תהי $A=\begin{pmatrix}0&3&1\\2&6&1\\1&0&4\end{pmatrix}\in \mathbb{R}^{3\times3}$ . נשים לב כי היא לא רגילה מכיוון שלא קיימת $L$ כנדרש.
נדרש לשנות מעט את המטריצה שכן איבר האפס $a_{11}$ לא יכול לשמש כאיבר ציר ולכן התהליך נתקע.
כל מה שעלינו לעשות הוא לשנות את סדר השורות וזאת ע"י פעולת הפרמוטציה:

PA=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 0 & 3 & 1 \\ 2 & 6 & 1 \\ 1 & 0 & 4 \end{pmatrix}=\begin{pmatrix} 2 & 6 & 1 \\ 0 & 3 & 1 \\ 1 & 0 & 4 \end{pmatrix}

יש פה מקום להתלבט האם להחליף עם השנייה או עם השלישית את השורה הראשונה. נשים לב כי נקבל פתרון שונה לכל אחת מהאופציות.
כעת נמשיך כרגיל:

E_{1}PA=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -\frac{1}{2} & 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 6 & 1 \\ 0 & 3 & 1 \\ 1 & 0 & 4 \end{pmatrix}=\begin{pmatrix} 2 & 6 & 1 \\ 0 & 3 & 1 \\ 0 & -3 & 3.5 \end{pmatrix}

E_{2}E_{1}PA=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} 2 & 6 & 1 \\ 0 & 3 & 1 \\ 0 & -3 & 3.5 \end{pmatrix}=\begin{pmatrix} 2 & 6 & 1 \\ 0 & 3 & 1 \\ 0 & 0 & 4.5 \end{pmatrix}=U

כעת נמצא את $L$ . נתחיל מהתכונות שאותן אנו יודעים: $\begin{pmatrix}1&0&0\\ \square & 1 & 0\\ \square & \square & 1\end{pmatrix}$
כעת, נמלא את שאר התאים:

L=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \frac{1}{2} & -1 & 1 \end{pmatrix}

נשים לב כי לבסוף קיבלנו פה $PA=LU$ .

במקרה הכללי, תהליך הפירוק "יזרום" כרגיל, ובכל פעם שנתקל באיבר ציר בעייתי(מאופס), נחליף את השורה בה הוא נמצא באחת השורות מתחתיו.
אנו לא רוצים לשתול באמצע המטריצות הבסיסיות איזו $P$ שכזו, מה נוכל לעשות מבלי לעשות את הפירוק פעמיים? הוא אמר שהוא לא נכנס לזה ושעושים את זה עם שמירת פוינטר לכל שורה.

הערה

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

הגדרה 2 (מטריצת פרמוטציה)

מטריצת פרמוטציה היא מטריצת יחידה ששורותיה עורבלו.
בכל עמודה במטריצה זו איבר אחד שונה מאפס וערכו $1$ וכנ"ל לגבי השורות.

דוגמה (מציאת פירוק

UL

)

נמצא כעת פירוק $UL$ למטריצה $A=\begin{pmatrix}0&2&3&4\\2&1&1&1\\4&4&5&6\\2&2&2&2\end{pmatrix}$ .
הצעד הראשון שנעשה יהיה פרמוטציה שכן $0$ לא יכול להיות איבר מוביל. $P_{1}A=\begin{pmatrix}0 & 1 & 0 & 0\\1 & 0 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix}0 & 2 & 3 & 4\\2 & 1 & 1 & 1\\4 & 4 & 5 & 6\\2 & 2 & 2 & 2\end{pmatrix}=\begin{pmatrix}2 & 1 & 1 & 1\\0 & 2 & 3 & 4\\4 & 4 & 5 & 6\\2 & 2 & 2 & 2\end{pmatrix}$
כעת, נוכל לבצע עליה פעולות אלמנטריות באמצעות מטריצות בסיסיות:

E_{2}E_{1}P_{1}A=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 4 & 4 & 5 & 6 \\ 2 & 2 & 2 & 2 \end{pmatrix}=\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 0 & 2 & 3 & 4 \\ 0 & 1 & 1 & 1 \end{pmatrix}

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

P_{2}P_{1}A=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 2 & 3 & 4 \\ 2 & 1 & 1 & 1 \\ 4 & 4 & 5 & 6 \\ 2 & 2 & 2 & 2 \end{pmatrix}=\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 2 & 2 & 2 & 2 \\ 4 & 4 & 5 & 6 \end{pmatrix}

נפתור מחדש:

E_{2}E_{1}P_{2}P_{1}A=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -2 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 2 & 2 & 2 & 2 \\ 4 & 4 & 5 & 6 \end{pmatrix}=\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \end{pmatrix}

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

הערה

אין אנו נדרש לכתוב את הקוד הזה לכן זה בגדר העשרה חלקית.

כעת, נמשיך בפירוק:

E_{4}E_{3}E_{2}E_{1}P_{2}P_{1}A=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -\frac{1}{2} & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \end{pmatrix}=\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 0 & 0 & -\frac{1}{2} & -1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

כעת, נוכל לאגרן ולקבל:

PA=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & \frac{1}{2} & 1 & 0 \\ 2 & 1 & 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & 1 & 1 \\ 0 & 2 & 3 & 4 \\ 0 & 0 & -\frac{1}{2} & -1 \\ 0 & 0 & 0 & 0 \end{pmatrix}=LU

הערה

אין דרך לצפות מראש את כל הפרמוטציות הנחוצות.

משפט

כל מטריצה ריבועית $A$ ניתנת לפירוק מהצורה $PA=LU$ כאשר

$P$ מטריצת פרמוטציה המחליפה סדר שורות
$L$ מטריצה משולשת תחתונה בסיסית
$U$ מטריצה משולשת עליונה כלשהי

הערה (האם העובדה שאין יחידות משפיעה על הפתרון?)

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

בהינתן המערכת $A\underline{x}=\underline{b}$ והפירוק $PA=LU$ , כיצד יחושב $\underline{x}$ ?

PAx=Pb

LU\underline{x}=Pb

נפתור מערכת משוואות באמצעות החלפה קדמית: $L\underline{y}=P\underline{b}$ ואז נפתור באמצעות החלפה אחורית $U\underline{x}=\underline{y}$ .

חישוב דטטרמיננט בעזרת פירוק $LU$

נזכר שפירוק $UL$ נראה כך:

PA=LU

נוכל לקחת את הדטרמיננט לשני האגפים:

|P||A|=|PA|=|LU|=|U||L|

לפי משפט מאלגברה: הדרטרמיננטה של מטריצה משולשת היא מכפלת איברי האלכסון.

\begin{cases} |P|=\pm1 \\ |L|=1 \\ |U|=\prod_{k=1}^n u_{kk} \end{cases} \implies |A|=\pm u_{11}u_{22}\dots u_{nn}

משפט

עבור מטריצה ריבועית $A$ עם הפירוק $PA=LU$ , אם כל איברי האלכסון הראשי של $U$ שונים מאפס, אזי $A$ הפיכה.

באמצעות פירוק $LU$ ניתן לחשב את הדטרמיננט של מטריצה בסיבוכיות $\frac{n^3}{3}$ (כאשר הזמן מגיע ממציאת הפירוק ולא מהחישוב שלאחריו)
החלופה היא נוסחת המינורים של קרמר שדורשת $n!$ פעולות ולכן פירוק $LU$ עדיף מאוד.

פירוק $LU$ למטריצות לא ריבועיות

טענה

כל מטריצה ניתנת לפירוק $LU$ (עם פרמוטציה), גם אם אינה ריבועית

כעת, נחקור ונראה כי הטענה הזו נכונה.
נתחיל ממטריצה לא ריבועית בלי צורך בפרמוטציות. נכפיל אותה במטריצות בסיסיות כך:
1 - פירוק LU 2026-04-16 13.59.17.excalidraw.svg
כעת, נתחיל למצוא את הבסיסיות שלב אחר שלב:
1 - פירוק LU 2026-04-16 14.06.43.excalidraw.svg
נמשיך כך ולבסוף נגיע ליצור הזה:
1 - פירוק LU 2026-04-16 14.17.22.excalidraw.svg
נוכל כעת לחלק את המטריצות הללו לשני בלוקים ולהתייחס לכפל ככה:
1 - פירוק LU 2026-04-16 14.19.04.excalidraw.svg
נשים לב כי $U_{2}$ היא מטריצת האפס ולכן:

A=L_{1}U_{1}+L_{2}\cdot 0=L_{1}U_{2}

כעת, נסתכל גם על מטריצה עם פרמוטציות:

PA=L_{1}U_{2}

(סליחה, לא היה לי כח לצייר עוד מלא מטריצות)

משפט

כל מטריצה ניתנת לפירוק $LU$ (עם פרמוטציה) גם אם אינה ריבועית

הערה

נראה איך נראת מטריצה שהינה רחבה יותר מאשר ארוכה:
1 - פירוק LU 2026-04-16 15.14.03.excalidraw.svg

שיטות לבחירת $Pivot$ מוצלח

ישנם הרבה מצבים שבהם נרצה להחליף את הסדר השורות בחוכמה. נתחיל בדוגמה:

דוגמה

\begin{pmatrix} 10^{-5} & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \end{pmatrix}

נתחיל בלבצע פתרון מושלם בעזרת גאוס:

\begin{pmatrix} 1 & 0 \\ -10^{5} & 1 \end{pmatrix}\begin{pmatrix} 10^{-5} & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ -10^5 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix}\implies \begin{pmatrix} 10^{-5} & 1 \\ 0 & 1-10^{-5} \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 \\ -10^5 \end{pmatrix}

הפתרון למערכת זו הוא:

y=-\frac{10^5}{1-10^5} \implies x=\frac{10^5}{1-10^{5}}

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

\begin{pmatrix} 1 & 0 \\ -10^{5} & 1 \end{pmatrix}\begin{pmatrix} 10^{-5} & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ -10^5 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix}\implies \begin{pmatrix} 10^{-5} & 1 \\ 0 & {\color{orange} 1-10^{-5}} \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 \\ -10^5 \end{pmatrix}

התוצאה של הביטוי הזה תעוגל קלות לאור מגבלות המחשב ואז:

y=\frac{-10^5}{-10^5}\implies x=\frac{1}{10^{-5}}(1-1)={\color{red} 0}

המספר $y$ יצא לא רחוק ממה שהוא יצא במקור, אבל ב- $x$ קיבלנו כעת תוצאה שונה.
איך נתקן זאת? בעזרת פרמוטציות

כעת, נבצע את אותו הדבר אבל נחליף את סדר השורות:

\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 10^{-5} & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix}\implies \begin{pmatrix} 1 & 1 \\ 10^{-5} & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 0 \\ 1 \end{pmatrix}

כעת, נכפיל ב- $10^{-5}$ את השורה העליונה ומחסיר - בכך אנו מקטינים את המספר ולכן האי דיוק לא יתקיים:

\begin{pmatrix} 1 & 0 \\ -10^{-5} & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 10^{-5} & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ -10^{-5} & 1 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix}

\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 0 \\ 1 \end{pmatrix}

כעת, קיבלנו את התוצאות הרצויות.

אלגוריתם $partial\; pivoting$

נניח וכעת אנחנו בעמודה $n$ , נעבור על כל השורות שנמצאות באינדקס גדול מ- $n$ ונבחר כ- $pivot$ את המספר הכי גדול בערך מוחלט.

דוגמה

\begin{pmatrix} 10^{-5} & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \end{pmatrix}\implies \begin{pmatrix} 1 & 10^5 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 10^5 \\ 0 \end{pmatrix}

כעת, לפי איך שהגדרנו אל האלגוריתם, אנחנו יכולים להתחיל לפתור, אז בואו ננסה לעשות זאת:

\begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 10^5 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}\begin{pmatrix} 10^5 \\ 0 \end{pmatrix}

\begin{pmatrix} 1 & 10^5 \\ 0 & -10^5 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 10^5 \\ -10^5 \end{pmatrix}\implies \begin{cases} y=1 \\ x=10^5-10^5={\color{red} 0} \end{cases}

שוב פעם יש בעיה. למה זה קרה? כי בפנים יש מספר ענק נוסף.

הערה (אלגוריתם

full\; pivoting

)

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

PAQ=LU

כאשר $P$ היא פרמוטציה לשורות ו- $Q$ היא פרמוטציה לעמודות.

הערה (להערה)

זה אלוגריתם לא מומלץ שכן יש לו מחיר עצום!

פירוק $LDL^T$ ו- $Cholesky$

פירוק $LDV$

ראינו כי כל מטריצה $A$ ניתנת לפירוק מהצורה $PA=LU$ . כאשר אנו עוסקים במטריצות ריבועיות, אם כל איברי האלכסון של $U$ שונים מאפס, אנו יודעים כי המטריצה הפיכה(כי הדטרמיננטה שלה שונה מ- $0$ ).
משתי עובדות אלו נובע הפירוק הבא:

משפט

כל מטריצה $A$ ריבועית והפיכה ניתנת לפירוק מהצורה $PA=LDV$ כאשר

$P$ היא מטריצת פרמוטציה המחליפה סדר שורות
$L$ מטריצה משולשת תחתונה בסיסית
$V$ מטריצה משולשת עליונה בסיסית
$D$ מטריצה אלכסונית בה כל איברי האלכסון שונים מאפס.

דוגמה

ראינו בתחילת ההרצאה את הדוגמה הזו:

A=LU=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 2 & -1 \\ 0 & 0 & 2.5 \end{pmatrix}

כעת, נרצה שגם המשולשת העליונה תהיה בסיסית. לכת, נבצע את זה:

A=LU=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2.5 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & -\frac{1}{2} \\ 0 & 0 & 1 \end{pmatrix}

הערה

כשמטריצה אלכסונית מכפילה מטריצה כלשהי משמאל, איברי האלכסון מכפילים את השורות.

דוגמה (למה הגבלנו את הדיון למטריצות הפיכות?)

A=LU=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 2 & -1 \\ 0 & 0 & 0 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & -\frac{1}{2} \\ 0 & 0 & 1 \end{pmatrix}

פה נראה כי אין שום בעיה אם המטריצה אינה הפיכה. אך פה נוכל לראות בעיה:

A=LU=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 0 & -1 \\ 0 & 0 & 0 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -\frac{1}{2} & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}\begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & {\color{orange}?} \\ 0 & 0 & 1 \end{pmatrix}

איך נוכל להחזיר את ה- $-1$ שהיה שם ממקודם? לא משנה איזה איבר נשים באלכסון, לא נוכל לקבל גם $0$ באלכסון וגם $-1$ כפי שהיה במקור. זאת מכיוון שנדרש להכפיל משהו ב- $0$ ולקבל $-1$ מה שלא אפשרי.

משפט

דטרמיננט המטריצה הוא כפולת איברי האלכסון של המטריצה האלכסונית $D$ עם סימן שנקבע ע"י הפרמוטציות.

מטריצות סימטריות

הגדרה 3 (מטריצה סימטרית)

מטריצה סימטרית היא מטריצה ריבועית המקיימת $A=A^{t}$ .

משפט

כל מטריצה ניתנת לפירוק כסכום של מטריצה סימטרית ומטריצה אנטי-סימטרית:

A=\frac{A+A^t}{2}+\frac{A-A^t}{2}

כעת, נלך למטריצות סימטריות והפיכות ונמצא להם פירוק $LDV$ חכם ויפה. נוכל לפרק אותה בדרך הרגילה כך:

PA=LDV

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

PAP^{t}=LDV

בואו נראה למה זה משמר סימטריה:

(PAP^t)^t=(P^t)^tA^tP^t \underset{\begin{matrix} \downarrow \\ A^t=A \end{matrix}}{=}PAP^t

ולכן, לפי הגדרה $PAP^t$ סימטרית. לכן, זה מה שנעשה.
כאן היינו רוצים לטעון כי כל מטריצה סימטרית והפיכה מקיימת $PAP^t=LDL^t$ אך זה לא נכון, למה?

דוגמה

A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\implies P^tAP=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

נשים לב כי פה, עם $P$ ו- $P^t$ הגענו בדיוק לאותה מטריצה ואין לנו דרך גם לשמור על הסימטריות וגם להחליף בין השורות ולכן לא נוכל לפרק.
לכן, לא כל מטריצה סימטרית והפיכה תאפשר פירוק שכזה.

הערה

פירוק שניתן לעשות בתצורה $PAP^t=LDL^t$ אמור להיות זול פי 2 מפירוק $UL$ רגיל בשל הסימטריה.
כלומר, נדרשות רק $\frac{n^3}{6}$ פעולות. עם זאת, על מנת להשיג רווח חישובי זה, יש לפעול בדרך אלגוריתמית שונה שנראה בתרגול.

עד כה עבדנו עם כמה סוגי מטריצות:

תחילה ראינו כי לכל המטריצות האפשריות קיים פירוק $PA=UL$ .
לאחר מכן ראינו כי למטריצות ריבועיות מתקיים כי $U$ משולשת עליונה.
הקטנו את התחום שלנו והסתכלנו רק על מטריצות הפיכות, בהן האלכסון שונה מאפס.
לאחר מכן, הקטנו עוד יותר את התחום וניסינו להסתכל על מטריצות שלהן קיים פירוק $PAP^t=LDL^t$ .
כעת, נעבור לדון במטריצות חיוביות חצי מוגדרות שהינן סימטריות. עבורן פירוק הנ"ל מובטח.

מטריצות חיוביות מוגדרות

הגדרה 4 (מטריצה חיובית מוגדרת)

מטריצה ריבועית וסימטרית $K$ הינה חיובית מוגדרת אם היא מקיימת:

\forall \underline{x}\neq0:\; \underline{x}^tK\underline{x}>0

נסמן תכונה זו ע"י $K \succ0$ .

דוגמה

נרצה לדעת האם המטריצה $K=\begin{pmatrix}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\end{pmatrix}$ היא חיובית מוגדרת. איך נגלה זאת?
עבור הוקטור $\begin{pmatrix}-1\\1\\0\end{pmatrix}$ יתקיים כי $\begin{pmatrix}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\end{pmatrix}\begin{pmatrix}-1\\1\\0\end{pmatrix}=\begin{pmatrix}0\\0\\0\end{pmatrix}$ ואז יתקבל $\begin{pmatrix}-1 & 1 & 0\end{pmatrix}\begin{pmatrix}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\end{pmatrix}\begin{pmatrix}-1\\1\\0\end{pmatrix}=0$ ולכן התכונה לא מתקיימת.

משפט

מטריצה ריבועית, סימטרית וחיובית מוגדרת $K$ הינה בהרכח הפיכה.

הוכחה:
נניח בשלילה כי קיימת מטריצה חיובית מוגדרת לא הפיכה.
אזי, קיים וקטור $\underline{x}$ שאינו טריויאלי שמאפס את המכפלה $K\underline{x}$ . אזי, ברור שיתקיים $\underline{x}^tK\underline{x}=0$
⇐ המטריצה אינה חיובית מוגדרת - סתירה.
⇐ המטריצה הפיכה.
∎

הגדרה 5 (מטריצה חיובית חצי מוגדרת)

מטריצה ריבועית וסימטרית $K$ הינה חיובית חצי מוגדרת אם היא מקיימת

\forall \underline{x}\neq0:\; \underline{x}^tK\underline{x}\geq 0

נשים לב כי נוכל להציג את התנאי בתצורה אחרת:

\begin{pmatrix} x_{1} & x_{2} & x_{3} \end{pmatrix}\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}=\begin{pmatrix} x_{1} & x_{2} & x_{3} \end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}\begin{pmatrix} 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}=\left(\begin{pmatrix} 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}\right)^2\geq 0

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

דוגמה

עבור אילו ערכי $a$ יתקיים כי המטריצה $K$ תהיה חיובית מוגדרת או חצי מוגדרת?

K=\begin{pmatrix} 1 & a \\ a & 1 \end{pmatrix}

נתחיל בלפתח את הביטוי הנובע מההגדרה:

\begin{pmatrix} x_{1} & x_{2} \end{pmatrix}\begin{pmatrix} 1 & a \\ a & 1 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}=\begin{pmatrix} x_{1} & x_{2} \end{pmatrix}\begin{pmatrix} x_{1}+ax_{2} \\ ax_{1}+x_{2} \end{pmatrix}=x_{1}^2+2ax_{1}x_{2}+x_{2}^2=(x_{1}+ax_{2})^2+(1-a^2)x_{2}^2

עבור $a=1$ מתקיים:

\begin{cases} (1-a^2)x_{2}^2=0 \\ \forall x_{1}=-x_{2}:\; (x_{1}+ax_{2})^2=0 \end{cases}

ולכן המטריצה היא חיובית חצי מוגדרת. כך גם עבור $a=-1$ .
עבור $a=\frac{1}{2}$ אז הדרך לאפס את החלק השני היא לאפס את $x_{2}$ ואז, כדי לאפס את החלק הראשון צריך שגם $x_{1}$ יהיה אפס ולכן, המטריצה היא חיובית מוגדרת.

נשים לב כי המטריצה הזו היא:

חיובית מוגדרת עבור כל $|a|<1$ שכן לא ימצא וקטור שיביא את הביטוי הנל ל- $0$ .
חיובית חצי מוגדרת עבור $|a|=1$ כי ניתן לאפס את הביטוי אך לא ניתן להגיע לערך שלילי
עבור $|a|>1$ המטריצה אינה חיובית מוגדרת או חצי מוגדרת.

דוגמה

\begin{pmatrix} d_{1} & 0 & 0 \\ 0 & d_{2} & 0 \\ 0 & 0 & d_{3} \end{pmatrix}

נרצה לראות מתי המטריצה הנ"ל חיובית מוגדרת/חצי מוגדרת:

\begin{pmatrix} x_{1} & x_{2} & x_{3} \end{pmatrix}\begin{pmatrix} d_{1} & 0 & 0 \\ 0 & d_{2} & 0 \\ 0 & 0 & d_{3} \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}=\begin{pmatrix} x_{1} & x_{2} & x_{3} \end{pmatrix}\begin{pmatrix} d_{1}x_{1} \\ d_{2}x_{2} \\ d_{3}x_{3} \end{pmatrix}=d_{1}x_{1}^2+d_{2}x_{2}^2+d_{3}x_{3}^2

נשים לב כי רק עבור $d_{1},d_{2},d_{3}>0$ מתקיים כי המטריצה היא חיובית מוגדרת ואם $d_{1},d_{2},d_{3}\geq 0$ המטריצה היא חיובית חצי מוגדרת.

עבור מטריצה אלכסונית מתקיים:

\underline{x}^tD\underline{x}=\begin{pmatrix} x_{1} & x_{2} & \dots & x_{n} \end{pmatrix}\begin{pmatrix} d_{11} \\ & d_{22} \\ & & \ddots \\ & & & d_{nn} \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{pmatrix}=\sum_{k=1}^n d_{kk}x_{k}^2

מסקנה

אם כל איברי האלכסון של מטריצה אלכסונית $D$ חיוביים ממש, המטריצה תהיה חיובית מוגדרת.
אם האיברים באלכסון אי שליליים, המטריצה חיובית חצי מוגדרת.

הערה

תתכן מטריצה לא סימטרית אשר הינה חיובית מוגדרת.
דוגמה: $K=\begin{pmatrix}1 & 0\\a & 2\end{pmatrix}$ . נבדוק לפי הגדרה:

\underline{x}^tK\underline{x}=\begin{pmatrix} x & y \end{pmatrix}\begin{pmatrix} 1 & 0 \\ a & 2 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} x & y \end{pmatrix}\begin{pmatrix} x \\ ax+2y \end{pmatrix}=x^2+axy+2y^2=\left( x+\frac{a}{2}y \right)^2+\left( 2-\frac{a^2}{4} \right)y^2

\implies \forall |a|<\sqrt{ 8 }:\; K \succ0

בקורס אנחנו לרוב נדבר רק על מטריצות סימטריות בהקשר של חיוביות מוגדרות.

מטריצות $Gram$

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

K=A^tA

כאשר $A$ היא מטריצה כלשהי (לא חייבת להיות ריבועית או סימטרית)
הוכחת סימטריות: $(A^tA)^t=A^t(A^t)^t=A^tA$ כנדרש.
נוכיח כי $K$ חיובית חצי מוגדרת:

\underline{x}^t(A^tA)\underline{x}=x^tA^tA\underline{x}=(Ax)^t(Ax)\underset{\begin{matrix} \downarrow \\ \R{\text{כשמכפילים וקטור}} \\ \R{\text{בטרנספוז של עצמו}} \\ \R{\text{מקבלים את סכום}} \\ \R{\text{ריבועיו ולכן אי-שלילי}} \end{matrix}}{\geq} 0

מבנה שכזה נקרא מטריצת גראם.

משפט

מטריצת גראם היא בהרכח חיובית חצי מוגדרת.

הוכחה: ראו הנ"ל.
בואו נכיר סימון חדש:

K=A^tA\implies \underline{x}^tA^tA\underline{x}=||A\underline{x}||_{2}^2\geq 0

הערה

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

משפט

תהי $K=A^tA$ מטריצת גראם כאשר $A$ מטריצה כלשהי.
אם עמודותיה של $A$ בת"ל, אזי $K$ היא חיובית מוגדרת.

הוכחה:
אם עמודות $A$ בת"ל, לא קיים וקטור שייתן כי $A\underline{x}=\underline{0}$ למעט הוקטור הטריויאלי.
לכן, הביטוי הנ"ל לא יתאפס לכל וקטור $\underline{x}\neq0$ . לכן, המטריצה חיובית מוגדרת.
∎

משפט

אם $C$ מטריצה חיובית מוגדרת ואם $A$ מטריצה בעלת עמודות בת"ל, אזי $A^tCA$ הינה מטריצה חיובית מוגדרת.

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

K=A^tCA\implies \forall x\neq 0:\; \underline{x}^tA^tC \underbracket{A\underline{x}}_{z}=\underline{z}^tC\underline{z} \underset{\begin{matrix} \downarrow \\ C \succ 0 \end{matrix}}{>} 0

∎

פירוק $Cholesky$

ראינו כי ניתן לנסות לפרק מטריצות סימטריות והפיכות לתצורה $PAP^t=LDL^t$ וזה לא תמיד עובד.

משפט

מטריצה סימטרית וחיובית מוגדרת $K$ היא בהרכח מטריצה רגילה וקיים לה הפירוק הבא ללא צורך בפרמטוציה:

K=LDL^t

ובפירוק זה אלכסון המטריצה $D$ חיובי ממש.

הוכחה:

\begin{matrix} \R{\text{ברור}} \\ \R{\text{סתאאאם... בקורס זה המשפט מובא ללא הוכחה}} \end{matrix}

∎

הערה

המשפט נכון גם כאשר מעורבות פרמוטציות, כי גם אז המטריצה נותרת $PD$ .

בואו נוכיח כי האלכסון חיובי.
הוכחה:
תהי $K \succ 0$ ולכן, $K=LDL^t$ . בנוסף, לפי הגדרה: $\forall x\neq 0:\; x^tLDL^tx >0$ . נסמן $x^tL=z^t$ ואז:

\forall z\neq0:\; z^tDZ>0

לכן, לפי הגדרה, $D$ חיובית מוגדרת ולכן, האלכסון שלה חיובי.
∎

כעת, נסתכל על דבר מעניין. נקח תחילה את $D$ ונפעיל שורש על כל איברי האלכסון. נסמן זאת $D^{\frac{1}{2}}$ ואז:

K=LDL^t=LD^{\frac{1}{2}}D^{\frac{1}{2}}L^t

נשים לב כי שתי המטריצות הראשונות הן השחלוף של שתי האחחרונות. נסמנן $M,M^t$ בהתאמה ואז:

K=M\cdot M^t

נשים לב בנוסף, כי המטריצה $M$ היא משולשת תחתונה. נקרא ל- $M$ השורש של $K$ .
זהו פירוק צ'ולסקי והוא מעין "הוצאת שורש" משולש למטריצה $K$ בעלות של $\frac{n^3}{6}$ פעולות.

1 - פירוק LU

אלגוריתמים נומריים

פירוק LU

1 - פירוק LU

אלגוריתמים נומריים

פירוק LU

תזכורות

אלימינצית גאוס

הפירוק באופן כללי

כמות החישובים בפירוק $UL$

פרמוטציות

חישוב דטטרמיננט בעזרת פירוק $LU$

פירוק $LU$ למטריצות לא ריבועיות

שיטות לבחירת $Pivot$ מוצלח

אלגוריתם $partial\; pivoting$

פירוק $LDL^T$ ו- $Cholesky$

פירוק $LDV$

מטריצות סימטריות

מטריצות חיוביות מוגדרות

מטריצות $Gram$

פירוק $Cholesky$

אלגוריתמים נומריים

פירוק LU

אלגוריתמים נומריים

פירוק LU

תזכורות

אלימינצית גאוס

הפירוק באופן כללי

כמות החישובים בפירוק ULULUL

פרמוטציות

חישוב דטטרמיננט בעזרת פירוק LULULU

פירוק LULULU למטריצות לא ריבועיות

שיטות לבחירת PivotPivotPivot מוצלח

אלגוריתם partial pivotingpartial\; pivotingpartialpivoting

פירוק LDLTLDL^TLDLT ו-CholeskyCholeskyCholesky

פירוק LDVLDVLDV

מטריצות סימטריות

מטריצות חיוביות מוגדרות

מטריצות GramGramGram

פירוק CholeskyCholeskyCholesky

כמות החישובים בפירוק $UL$

חישוב דטטרמיננט בעזרת פירוק $LU$

פירוק $LU$ למטריצות לא ריבועיות

שיטות לבחירת $Pivot$ מוצלח

אלגוריתם $partial\; pivoting$

פירוק $LDL^T$ ו- $Cholesky$

פירוק $LDV$

מטריצות $Gram$

פירוק $Cholesky$