הכפלת המטריצה $A$ במטריצה $E$ משמאל(כלומר $EA$) שקולה להוספת השורה $i$ לשורה $j$ ב-$A$ כאשר היא מוכפלת ב-$\alpha$.

למעשה, בהינתן $E$, ההיפוך שלה נתון ע"י מטריצה זהה לה בצורתה אך עם סימן הפוך על האיבר ה-$ij$.
באופן כללי:

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

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

אלגוריתם למציאת פירוק $LU$

נניח כי $A$ ריבועית ורגילה וברצוננו לבנות עבורה פירוק $LU$ מהצורה:

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

• נתחיל במציאת העמודה הראשונה של $L$ והשורה הראשונה של $U$.

הכפלת השורה הראשונה ב-$L$ ב-$U$ מבינה את השורה הראשונה מ-$U$ וזו חייבת להיות זהה לשורה הראשונה מ-$A$.

לכן, נוכל בקלות למצוא את השורה הראשונה של $U$. כעת, נראה כי גם נוכל בקלות למצוא את $L$:
הכפלת $L$ בעמודה הראשונה של $U$ תיתן את העמודה הראשונה של $A$ ומכיוון ש-$u_{1,1}=a_{1,1}$ נוכל לחלץ את כל איברי העמודה הראשונה של $L$.

כך, נוכל בקלות למצוא את העמודה הראשונה של $L$.

• כעת, לאחר שמצאנו את העמודה הראשונה של $L$ והשורה הראשונה של $U$, נציג את המכפלה הזו כמכפלת בלוקים $2\times2$:

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

אנו שוב מול פירוק $LU$ עבור מטריצה קטנה יותר ונחזור על אותו התהליך של בניית העמודה הראשונה של $L_{2}$ והשורה הראשונה של $U_{2}$ (רקורסיה יהיה מאוד נחמד פה)
כך הלאה עד שנגיע לבלוק בגודל $1\times1$.

סיבוכיות האלגוריתם

פירוק עם פרמוטציה

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

ניתן לפרק עם פרמוטציה בעזרת קוד המטלאב הבא(הערה: אני לא יודע מאטלב והמתרגל אמר שמאטלב זה לא בחומר)

function [P,L,U] = LU_PIV(A) 

[m,n] = size (A);
P = eye(m,m); 
L = eye(m,m); 
U = zeros(m,n); 
tol = sqrt(eps);

for k = 1:min(m, n) 
	r = findpiv(A (k:m,k),k);
	if r ~= k 
		A([r k],1:n) = A([k r],1:n);
		L([r k],1:k-1) = L([k r],1:k-1);
		P([r k],:) = P([k r],:); 
	end 
	U(k, k:n) = A(k, k:n);
	if abs(A(k,k)) >= tol 
		L(k+1:m,k) = A(k+1:m,k)/A(k,k); 
		A(k+1:m,k+1:n) = A (k+1:m,k+1:n)- ...
						 L(k+1:m, k) *U(k,k+1:n); 
	end 
end 

function [r] = findpiv(a, k) 
pos=find(abs(a)==max(abs(a))); 
r=pos(1)+k-1;

פתרון מערכת משוואות עם $LU$

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

• שלב א': $L\underline{y}=P\underline{b}$
• שלב ב': $U\underline{x}=\underline{y}$.

פתרון בדרך זו יעיל יותר מהיפוך מטריצה.

תרגול

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

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

קיבלנו את המטריצה $U$ שלנו. כעת, נמצא את $L$:

ולכן:

כעת, נפתור את הממ"ל:

כעת, נפתור סופית:

תמונה היא מטריצה והמספרים המאכלסים אותה הם פיקסלים המייצגים "רמות האפור" (ערך בתחום $[0,1]$ כאשר $0$ הוא שחור ו-$1$ הוא לבן)
טשטוש מתקבל כאשר כל ערך של פיקסל מוחלף בממוצע משוקלל של סביבתו. (לכו לתואר בפיזיקה כדי לדעת למה זה קורה)
נמחיש את פעולת הטשטוש על עמודה בתמונה: $\underline{y}=H\underline{x}$ כאשר המטריצה $H$ מייצגת את פעולת הטשטוש - הכפלת עמודה בה יוצרת עמודה חדשה עם מריחת הערכים:

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

נסתכל על תיאור מתמטי של פעולת הטשטוש:

כאשר $Y$ היא התמונה המטושטשת ו-$X$ היא התמונה המקורית.
המטריצה $H$ מטשטשת את העמודות והשורות בנפרד.

כעת, ברורה משימת השחזור שלפנינו: בהינתן $Y$ ובידיעת $H$, ברצונינו לחלץ את $X$.
המשימה הזו היא בעצם פתרון של מלא ממ"לים כפי שראינו הנ"ל. אנו נוכל להקל על התהליך באמצעות פירוק $LU$ למטריצה $H$.

הנה שלבי השחזור:

• נסמן $Z=XH^t$. בשלב הראשון, עלינו לפתור את המשוואה $Y=HZ$.
• נקבל את $Z$ ואז נפתור את המשוואה $Z^t=HX^t$ ועם זה נסיים.
• בשני המקרים לא מדובר במשוואה אחת, אלא בסדרה שלהן.