כיצד לבצע פקטוריזציה של LU?

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

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

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

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

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

צעדים

1
התחל במשוואת המטריצה. ביסודו, ניתן לכתוב מערכת משוואות במונחים של משוואת מטריצה Ax = b, {\ displaystyle A \ mathbf {x} = \ mathbf {b},} $A {\ mathbf {x}} = {\ mathbf {b}},$ כאשר מטריצה A {\ displaystyle A} $א$ פועלת על וקטור x { \ displaystyle \ mathbf {x}} ${\ mathbf {x}}$ להפקת וקטור אחר ב. {\ displaystyle \ mathbf {b}.} ${\ mathbf {b}}.$ לרוב אנו רוצים לדעת x, {\ displaystyle \ mathbf {x},} ${\ mathbf {x}},$ וזה לא יוצא מן הכלל. בפקטוריזציה LU נראה כי אנו יכולים להגדיר את היחס A = LU, {\ displaystyle A = LU,} $A = lu,$ כאשר L {\ displaystyle L} $ל$ ו- U {\ displaystyle U} $U$ הן מטריצות משולשות.
- ${\ begin {pmatrix} 2and4and1 \\ - 1and1and3 \\ 3and2and5 \ end {pmatrix}} {\ mathbf {x}} = {\ begin {pmatrix} 2 \\ 1 \\ 7 \ end {pmatrix}}$
2
צמצם שורה $א$ לצורת דרג-שורה. צורת הדרג השורה תהפוך למטריקס U שלנו . {\ Displaystyle U.} $U.$
- R2 → 2R2 + R1, R3 → 2R3−3R1 {\ displaystyle R_ {2} \ to 2R_ {2} + R_ {1}, \ R_ {3} \ to 2R_ {3} -3R_ {1}} $R _ {{2}} \ to 2r _ {{2}} + r _ {{1}}, \ r _ {{3}} \ to 2r _ {{3}} - 3r _ {{1}}$
  - ${\ begin {pmatrix} 2and4and1 \\ 0and6and7 \\ 0and-8and7 \ end {pmatrix}}$
- R3 → 3R3 + 4R2 {\ displaystyle R_ {3} \ to 3R_ {3} + 4R_ {2}} $R _ {{3}} \ עד 3r _ {{3}} + 4r _ {{2}}$
  - ${\ begin {pmatrix} 2and4and1 \\ 0and6and7 \\ 0and0and49 \ end {pmatrix}} = u$
- המטריצה נמצאת כעת בצורת הדרג.
כדי לפתור מערכות של שלוש משוואות ליניאריות או יותר, בדרך כלל ממירים את הבעיה למטריצה מוגברת ושורה מקטינה משם.
3
השג $l$ ידי ביטול שלבי הצמצום שלך בשורה. שלב זה עשוי להיות מעט מסובך בהתחלה, אך למעשה אנו בונים מטריצה על ידי מעבר אחורה.
- בואו נסתכל על הפחתת השורה האחרונה R3 → 3R3 + 4R2. {\ Displaystyle R_ {3} \ ל- 3R_ {3} + 4R_ {2}.} $R _ {{3}} \ עד 3r _ {{3}} + 4r _ {{2}}.$ מצאנו את השורה החדשה 3 על ידי החלפתה בשילוב ליניארי של הישן שורות של המטריצה. כעת, אנו רוצים למצוא את השורה 3 הישנה, כל כך פשוט לפתור אותה.
  - $R _ {{3}} ^ {{{\ text {old}}}} \ אל {\ frac {r _ {{3}} - 4r _ {{2}}} {3}}$
- זה מבטל את צמצום השורה השנייה. עכשיו, שמנו את זה בצורה של מטריצה. בואו נקרא למטריצה הזו S2. {\ Displaystyle S_ {2}.} $S _ {{2}}.$ וקטור העמודות מימין פשוט מבהיר את מה שאנחנו עושים - המטריצה הזו שאנחנו בונים היא טרנספורמציה לינארית שעושה את אותו הדבר כמו שכתבנו לעיל. שימו לב, מכיוון שלא עשינו שום דבר לשתי השורות העליונות, האלמנטים המתקבלים לשתי השורות במטריצה זו זהים למטריצת הזהות. רק השורה השלישית משתנה.
  - ${\ begin {pmatrix} 1and0and0 \\ 0and1and0 \\ 0and-1,33and0,33 \ end {pmatrix}} {\ begin {pmatrix} r _ {{1}} \\ r _ {{2}} \\ r _ {{ 3}} \ end {pmatrix}}$
- בנה את המטריצה שמבטלת את צמצום השורה הראשונה. באופן דומה, אנו פותרים את השורה 2 ו- 3 הישנה. אנו נקרא למטריצה זו S1. {\ Displaystyle S_ {1}.} $S _ {{1}}.$
  - $R _ {{2}} ^ {{{\ text {old}}}} = {\ frac {r _ {{2}} - r _ {{1}}} {2}}$
  - $R _ {{3}} ^ {{{\ text {old}}}} = {\ frac {r _ {{3}} + 3r _ {{1}}} {2}}$
  - $S _ {{1}} = {\ התחל {pmatrix} 1and0and0 \\ - 0,5and0,5and0 \\ 1,5and0and0,5 \ end {pmatrix}}$
- הכפל את המטריצות S {\ displaystyle S} $ס$ לפי הסדר שמצאנו אותן. פירוש הדבר ש- S2S1 = L. {\ Displaystyle S_ {2} S_ {1} = L.} $S _ {{2}} s _ {{1}} = l.$ אם ביצעת את הכפל כהלכה, אתה אמור לקבל מטריצה משולשת תחתונה.
  - $L = {\ begin {pmatrix} 1and0and0 \\ - 0,5and0,5and0 \\ 1,5and-0,67and0,17 \ end {pmatrix}}$
4
השכתוב המשוואה מטריקס גרזן = b {\ displaystyle a \ mathbf {x} = \ mathbf {ב}} ${\ mathbf {x}} = {\ mathbf {b}}$ ב במונחים של lu {\ displaystyle lu} $lu$ . עכשיו שיש לנו שתי מטריצות, אנחנו יכולים לראות למטה כי L {\ displaystyle L} $ל$ מתנהג על וקטור Ux {\ displaystyle U \ mathbf {x}} $U {\ mathbf {x}}$ יציאות ב. {\ Displaystyle \ mathbf {ב}.} ${\ mathbf {b}}.$
- $L (u {\ mathbf {x}}) = {\ mathbf {b}}$
- מכיוון ש- $U {\ mathbf {x}}$ הוא וקטור, תן ${\ mathbf {y}} = u {\ mathbf {x}}.$ לאחר מכן, אנו רואים כי $L {\ mathbf {y}} = {\ mathbf {b}}.$ המטרה כאן היא לפתור הראשון עבור ${\ mathbf {y}},$ מכן חבר לתוך $U {\ mathbf {x}} = {\ mathbf {y}}$ כדי לפתור עבור ${\ mathbf {x}}.$
זה נקרא פקטוריזציה LU - היא מפרקת מטריצה לשתי מטריצות משולשות - למשולש עליון ולמשולש תחתון - ולאחר ההתקנה המתאימה, הפתרונות נמצאים על ידי החלפת גב.
5
פתר עבור ${\ mathbf {y}}$ . מכיוון שאנו עוסקים במטריצות משולשות, החלפת גב היא הדרך ללכת.
- $L {\ mathbf {y}} = {\ התחל {pmatrix} y _ {{1}} \\ - {\ frac {1} {2}} y _ {{1}} + {\ frac {1} {2} } y _ {{2}} \\ {\ frac {3} {2}} y _ {{1}} - {\ frac {2} {3}} y _ {{2}} + {\ frac {1} { 6}} y _ {{3}} \ end {pmatrix}} = {\ התחל {pmatrix} 2 \\ 1 \\ 7 \ end {pmatrix}}$
- ${\ mathbf {y}} = {\ התחל {pmatrix} 2 \\ 4 \\ 40 \ end {pmatrix}}$
6
פתר עבור ${\ mathbf {x}}$ . זה יכלול שוב החלפה אחורית מכיוון ש- U {\ displaystyle U} $U$ הוא משולש.
- $U {\ mathbf {x}} = {\ התחל {pmatrix} 2x _ {{1}} + 4x _ {{2}} + x _ {{3}} \\ 6x _ {{2}} + 7x _ {{3}} \\ 49x _ {{3}} \ end {pmatrix}} = {\ begin {pmatrix} 2 \\ 4 \\ 40 \ end {pmatrix}}$
- ${\ mathbf {x}} = {\ התחל {pmatrix} 51,759 \\ - 0,29 \\ 40/49 \ end {pmatrix}}$
- למרות ששיטה זו אולי לא נראית לך יעילה במיוחד (ואכן, פקטוריזציה של LU למערכות של שלוש משוואות אינה טובה יותר מצמצום שורה), מחשבים מצוידים היטב לבצע החלפת גב, כך שהתוצאות באמת מוצגות כמספר משוואות עולה.

קרא גם: איך להיות בקיא בנושא הכימיה ההטרוציקלית?