פירוק $LDV$

משפט

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

$L$ משולשת תחתונה בסיסית
$V$ מטריצה משולשת עליונה בסיסית
$P$ מטריצת פרמוטציה
$D$ אלכסונית (כאשר $\forall k \in[1,n]:\; d_{kk}\neq0$ )

פירוק $LDV$ מתקבל בקלות מפירוק $LU$ ע"י פירוק המטריצה $U=DV$ כאשר $D$ מכילה את איברי האלכסון של $U$ ושורות $V$ מנורמלות בהתאם. לכן, הדרישה להיותה של $A$ הפיכה.

הערה

בהינתן פירוק $LDV$ הדטרמיננט של $A$ הוא מכפלת איברי האלכסון של $D$ (עד כדי סימן בשל $P$ )

דוגמה

נפרק את המטריצה $A=\begin{pmatrix}1&3&1\\2&8&1\\1&10&4\end{pmatrix}$ .
פירוק ה- $LU$ הינו $\begin{pmatrix}1&3&1\\2&8&1\\1&10&4\end{pmatrix}=\begin{pmatrix}1&0&0\\2&1&0\\1&3.5&1\end{pmatrix}\begin{pmatrix}1&3&1\\0&2&-1\\0&0&6.5\end{pmatrix}$ ומפה, הדרך ל- $LDV$ קצרה ופשוטה:

\begin{pmatrix} 1&3&1 \\ 2 & 8 & 1 \\ 1 & 10 & 4 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 3.5 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 6.5 \end{pmatrix}\begin{pmatrix} 1 & 3 & 1 \\ 0 & 1 & -\frac{1}{2} \\ 0 & 0 & 1 \end{pmatrix}

שימושי פירוק $LDV$

פתרון מערכת משוואות
היפוך מטריצה: $A=LDV\implies A^{-1}=V^{-1}D^{-1}L^{-1}$
חישוב הדטרמיננטה: $|PA|=|P||A|=|LDV|$ ואז:
$|P||A|=|L||D||V|=|D|=\prod_{k=1}^n d_{kk}$

דוגמה

PA=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 3 & 1 \\ 2 & 6 & 1 \\ 1 & 10 & 4 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 7 & 0 \\ 0 & 0 & -1 \end{pmatrix}\begin{pmatrix} 1 & 3 & 1 \\ 0 & 1 & \frac{3}{7} \\ 0 & 0 & 1 \end{pmatrix}=LDV

|A|=\frac{|D|}{|P|}=\frac{1\cdot 7 \cdot (-1)}{-1}=7

פירוק $LDL^t$

כאשר $A$ ריבועית, הפיכה וסימטרית אזי, הפירוק $LDV$ שלהן יהיה:

\begin{pmatrix} 1 & 3 & 2 \\ 3 & 8 & 3 \\ 2 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ \color{blue}{3} & 1 & 0 \\ \color{red}{2} & \color{magenta}{3} & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 7 \end{pmatrix} \begin{pmatrix} 1 & \color{blue}{3} & \color{red}{2} \\ 0 & 1 & \color{magenta}{3} \\ 0 & 0 & 1 \end{pmatrix}

\begin{pmatrix} 1 & 5 & 4 \\ 5 & 27 & 18 \\ 4 & 18 & 28 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ \color{blue}{5} & 1 & 0 \\ \color{red}{4} & \color{magenta}{-1} & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 10 \end{pmatrix} \begin{pmatrix} 1 & \color{blue}{5} & \color{red}{4} \\ 0 & 1 & \color{magenta}{-1} \\ 0 & 0 & 1 \end{pmatrix}

\begin{pmatrix} 1 & 3 & 1 & 5 \\ 3 & 8 & 1 & 2 \\ 1 & 1 & 4 & 7 \\ 5 & 2 & 7 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ \color{blue}{3} & 1 & 0 & 0 \\ \color{red}{1} & \color{cyan}{2} & 1 & 0 \\ \color{magenta}{5} & \color{yellow}{13} & \color{green}{4} & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 7 & 0 \\ 0 & 0 & 0 & 34 \end{pmatrix} \begin{pmatrix} 1 & \color{blue}{3} & \color{red}{1} & \color{magenta}{5} \\ 0 & 1 & \color{cyan}{2} & \color{yellow}{13} \\ 0 & 0 & 1 & \color{green}{4} \\ 0 & 0 & 0 & 1 \end{pmatrix}

בכל הדוגמות האלו המטריצה רגילה ובכולן התקבל כי $V=L^t$ .

משפט

כל מטריצה רגילה וסימטרית $A$ ניתנת לפירוק יחיד מהצורה $A=LDL^t$ כאשר $L$ מטריצה משולשת תחתונה בסיסית ו- $D$ מטריצה אלכסונית. (כאשר $d_{kk}\neq 0$ )

נשים לב כי אם $A$ אינה רגילה תמיד נוכל לטעון שקיים לה פירוק $PA=LDV$ . בהפעלת $P$ משמאל נשברת הסימטריה(ואנחנו תמיד רוצים לשמר על הסימטריה)
מה שנעשה זה להפעיל פרמוטציות משמרות סימטריה $PAP^t=LDL^t$ .

הערה

פירוק זה לא תמיד קיים.

תרגיל

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

-\frac{d^2}{dt^2}f(t)=f_{0}(t)

נרצה להגיע מהמשוואה הנ"ל לממ"ל ומטריצה
מעתה נעבוד עם הוקטור $x_{k}=f(kT)$ עבור $k \in \mathbb{N}$ .
נניח שהיננו רוצים את הנגזרת הראשונה של הפונקציה במקום $kT$ . זו תתקבל מחישוב הפרשים סמוכים:

\frac{df(kT)}{dt} \overset{\sim}{=} \frac{f(kT)-f(kT-T)}{T}=\frac{x_{k}-x_{k-1}}{T}

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

\frac{d^2f(kT)}{dt^2} \overset{\sim}{=} \dots = \frac{x_{k+1}-2x_{k}+x_{k-1}}{T^2}

נקבע $T=1$ .

נסתכל על המטריצה $A$ בגודל $n\times n$ . היא תלת-אלכסונית וסימטרית והיא מה שמקשר אותנו למשוואת פואסון(איך? אין לי מושג. למה זה קשור?????)
נתון לנו וקטור $\underline{b}$ וברצוננו לפתור את המערכת $A\underline{x}=\underline{b}$ (וקטור זה פחות חשוב בסיפור וניתן להחליפו)

נפתור את המערכת ע"י פירוק $LDL^t$ . פירוק זה אמנם לא מובטח להתקיים אך אנו יכולים לנסות בכל זאת.

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

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

הגדרה 1

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

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

הגדרה 2

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

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

משפט

מטריצה ריבועית וסימטרית $K$ היא חיובית מוגדרת $\iff$ היא ניתנת לפירוק $LDL^t$ ללא פרמוטציה ועם מטריצה $D$ בה כל האיברים חיוביים

הוכחה: בגליון 1.

תרגיל

נתון $K$ סימטרית וחיובית מוגדרת ו- $P$ מטריצה הפיכה.
הוכיחו כי $PKP^t$ סימטרית וחיובית מוגדרת.

הוכחה:

(PKP^t)^t=(P^t)^tK^tP^t=PKP^t

לכן המטריצה סימטרית.
יהי $\underline{x} \neq 0$ .
$P$ הפיכה ולכן $P^t\underline{x} \neq0$ .

\underline{x}^tPKP^t\underline{x}=(P^t\underline{x})^tK(P^t\underline{x})=\underline{y}^tK\underline{y} > 0

לכן, $PKP^{t}$ חיובית מוגדרת.
∎

פירוק צ'ולסקי

משפט

מטריצה ריבועית, סימטרית וחיובית מוגדרת $K$ ניתנת לפירוק יחיד מהצורה $MM^t$ כאשר $M$ הינה מטריצה משולשת תחתונה עם איברי אלכסון חיוביים.

זהו פירוק צ'ולסקי.

K=LDL^t=LD^{\frac{1}{2}}\left( D^{\frac{1}{2}} \right)^tL^t=MM^t

דוגמה

\begin{pmatrix} 1 & 3 & 2 \\ 3 & 11 & 12 \\ 2 & 12 & 32 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 10 \end{pmatrix}\begin{pmatrix} 1 & 3 & 2 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{pmatrix}

\begin{align*} \begin{pmatrix} 1 & 3 & 2 \\ 3 & 11 & 12 \\ 2 & 12 & 32 \end{pmatrix}&=\begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{ 2 } & 0 \\ 0 & 0 & \sqrt{ 10 } \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{ 2 } & 0 \\ 0 & 0 & \sqrt{ 10 } \end{pmatrix}\begin{pmatrix} 1 & 3 & 2 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{pmatrix} \\ &=\begin{pmatrix} 1 & 0 & 0 \\ 3 & \sqrt{ 2 } & 0 \\ 2 & 3\sqrt{ 2 } & \sqrt{ 10 } \end{pmatrix}\begin{pmatrix} 1 & 3 & 2 \\ 0 & \sqrt{ 2 } & 3\sqrt{ 2 } \\ 0 & 0 & \sqrt{ 10 } \end{pmatrix} \end{align*}

אלגוריתם לפירוק צ'ולסקי

תהי מטריצה שאנו מניחים שלה יש פירוק צ'ולסקי.

\begin{pmatrix} k_{11} & k_{12} & \dots & k_{1,n-1} & k_{1n} \\ k_{12} & k_{22} & \dots & k_{2,n-1} & k_{2n} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ k_{1,n-1} & k_{2,n-1} & \dots & k_{n-1,n-1} & k_{n-1,n} \\ k_{1n} & k_{2n} & \dots & k_{n-1,n} & k_{nn} \end{pmatrix}=\begin{pmatrix} m_{11} & 0 & 0 & \dots & 0 \\ m_{21} & m_{22} & 0 & \dots & 0 \\ m_{31} & m_{32} & m_{33} & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ m_{n1} & m_{n2} & m_{n3} & \dots & m_{nn} \end{pmatrix}\begin{pmatrix} m_{11} & m_{21} & m_{31} & \dots & m_{n1} \\ 0 & m_{22} & m_{32} & \dots & m_{n2} \\ 0 & 0 & m_{33} & \dots & m_{n3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & m_{nn} \end{pmatrix}

הכפלה של השורה הראשונה בכל העמודות של $M^t$ נותנת:

m_{11}^2=k_{11} \implies m_{11}=\pm \sqrt{ k_{11} }

ואז:

\forall 2\leq j \leq n:\; m_{11}m_{j1}=k_{1j}\implies m_{j1}=\frac{k_{1j}}{m_{11}}

הכפלת שורה שניה בכל העמודות של $M^t$ נותנת:

m_{21}^2+m_{22}^2=k_{22} \implies m_{22}=\pm \sqrt{ k_{22}-m_{21}^2 }

\forall 3\leq j \leq n:\; m_{21}m_{j1}+m_{22}m_{j2}=k_{2j} \implies m_{j2}=\frac{k_{2j}-m_{21}m_{j1}}{m_{22}}

לכן, הכפלת שורה $i$ בכל העמודות של $M^t$ נותנת:

m_{i1}^2+m_{i2}^2+\dots+m_{ii}^2=k_{ii} \implies m_{ii}=\pm \sqrt{ k_{ii}-\sum_{j=1}^{i-1}m_{ij}^2 }

\forall i+1\leq j\leq n:\;m_{ii}m_{ji}+\sum_{p=1}^{i-1}m_{ip}m_{jp}=k_{ij} \implies m_{ji}=\frac{k_{ij}-\sum_{p=1}^{i-1}m_{ip}m_{jp}}{m_{ii}}

זה לוקח סך של $i(n-i+1)$ פעולות.

\left\{ m_{ii}=\pm \sqrt{ k_{ii}-\sum_{j=1}^{i-1}m_{ij}^2 }\;\; ;\;\; \left\{ m_{ji}=\frac{\begin{gather} k_{ij}-\sum_{p=1}^{i-1}m_{ip}m_{jp} \end{gather}}{m_{i}} \right\}_{j=i+1}^{n} \right\}_{i=1}^n

תרגול

תרגיל

נתונה המטריצה $G=\begin{pmatrix}1&1&1&1\\1&2&2&2\\1&2&3&3\\1&2&3&4\end{pmatrix}$
א. מצאו פירוק $LU$ שלה ללא פרמוטציות (אם קיים)
ב. האם המטריצה חיובית מוגדרת?

פתרון א':

\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 \\ 1 & 2 & 3 & 4 \end{pmatrix}\overrightarrow{\begin{matrix} R_{2}=R_{2}-R_{1} \\ R_{3}=R_{3}-R_{1} \\ R_{4}=R_{4}-R_{1} \end{matrix}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 2 & 2 \\ 0 & 1 & 2 & 3 \end{pmatrix}\overrightarrow{\begin{matrix} R_{3}=R_{3}-R_{2} \\ R_{4}=R_{4}-R_{2} \end{matrix}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}\overrightarrow{R_{4}=R_{4}-R_{3}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix}

נסמן: $\begin{pmatrix}1 & 1 & 1 & 1\\0 & 1 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 0 & 1\end{pmatrix}=U$ ואז: $L=\begin{pmatrix}1 & 0 & 0 & 0\\1 & 1 & 0 & 0\\1 & 1 & 1 & 0\\1 & 1 & 1 & 1\end{pmatrix}$ .

פתרון ב':
נשים לב שקיבלנו פירוק $LDL^t$ כאשר $D=I$ שהיא אלכסונית עם איברי אלכסון חיוביים. אזי, לפי משפט, היא חיובית מוגדרת.

תרגיל (מועד א' אביב 2021)

נתונה מטריצה $M$ ריבועית, ממשית ולא סימטרית המקיימת $\underline{x}^tM\underline{x}>0$ לכל $\underline{x}$ .
איזו מטריצה סימטרית וחיובית מוגדרת $Q$ תקיים: $\underline{x}^tQ\underline{x}=\underline{x}^tM\underline{x}$ לכל $\underline{x}$ ?
א. אף תשובה אינה נכונה
ב. $Q=M^tM$
ג. $Q=MM^t$
ד. $Q=0.5(M+M^t)$
ה. $Q=0.5(M-M^t)$

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

\underline{x}^t\left( \frac{1}{2}(M+M^t) \right)\underline{x}=\frac{1}{2}(\underline{x}^tM\underline{x}+\underline{x}^tM^t\underline{x})

נשים לב כי $\underline{x}^tM\underline{x}$ הוא מספר ולכן, גם אם נבצע עליו טרנספוז ערכו ישמר ולכן:

\underline{x}^t\left( \frac{1}{2}(M+M^t) \right)\underline{x}=\frac{1}{2}(\underline{x}^tM\underline{x}+\underline{x}^tM^t\underline{x})=\frac{1}{2}(\underline{x}^tM\underline{x}+\underline{x}^tM\underline{x})=\underline{x}^tM\underline{x}

כנדרש.
לכן, התשובה הנכונה היא ד'.

הערה

את ה' אפשר לפסול מיד שכן היא אנטי סימטרית.

תרגיל (מועד ב' אביב 2021)

תהא $A$ מטריצה ריבועית סימטרית וחיובית מוגדרת. ננסה להפעיל את אלגוריתם צ'ולסקי לקבלת $M$ משולשת תחתונה עם אלכסון חיובי ממש המקיימת $A=MM^t$ .
בחרו את התשובה הנכונה:
א. תהליך זה ייכשל - לא ניתן להבטיח מציאת מטריצה $M$ עם אלכסון חיובי ממש.
ב. תהליך זה ייכשל - לא ניתן להבטיח מטריצה $M$ משולשת תחתונה.
ג. תהליך זה יסתיים בהצלחה ומטריצה $M$ כזו תמצא.
ד. תהליך זה ייכשל - יש $\infty$ אפשרויות לקבלת המטריצה $M$ הם הדרישות הנ"ל.
ה. תהליך זה יסתיים בהצלחה בתנאי ש- $A$ רגילה.

לפי המשפט ממקודם התשובה הנכונה היא ג'.

3 - פירוק LDV וצ'ולסקי

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

פירוק LDV וצ'ולסקי

3 - פירוק LDV וצ'ולסקי

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

פירוק LDV וצ'ולסקי

פירוק $LDV$

שימושי פירוק $LDV$

פירוק $LDL^t$

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

פירוק צ'ולסקי

אלגוריתם לפירוק צ'ולסקי

תרגול

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

פירוק LDV וצ'ולסקי

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

פירוק LDV וצ'ולסקי

פירוק LDVLDVLDV

שימושי פירוק LDVLDVLDV

פירוק LDLtLDL^tLDLt

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

פירוק צ'ולסקי

אלגוריתם לפירוק צ'ולסקי

תרגול

פירוק $LDV$

שימושי פירוק $LDV$

פירוק $LDL^t$