מערכת משוואות לינארית

הגדרת משוואה לינארית

הגדרה 1: משוואה לינארית משוואה לינארית היא משוואה שבה כל המשתנים ממעלה ראשונה, מהצורה $\alpha _{1}x_{1}+\alpha _{2}x_{2}+\alpha _{3}x_{3}+...+\alpha _{n}x_{n}=b$, או בצורה יותר אלגנטית, משוואה לינארית היא ביטוי מהצורה $\sum _{i=1}^{n}\alpha _{i}x_{i}=b$, האיברים $\alpha _{i}$ נקראים המקדמים, האיברים $x_{i}$ נקראים הנעלמים, והאיבר $b$ נקרא המקדם החופשי, מקדמי המשוואה הם סקלרים משדה כלשהוא.

הגדרה 2: פתרון משוואה לינארית פתרון המשוואה הלינארית $\sum _{i=1}^{n}\alpha _{i}x_{i}=b$, היא nיה, כלומר קבוצה סדורה מהצורה $(z_{1},z_{2},z_{3}...z_{n})$, שאם נציב אותה בהתאמה במקום כל אחד מהנלעמים, נקבל פתרון, כלומר יתקיים $\sum _{i=1}^{n}\alpha _{i}z_{i}=b$

הגדרת מערכת משוואות לינארית

הגדרה 3: מערכת משוואות לינארית מערכת משוואות לינארית מסדר $m\times n$)(קרי: "$m$ על $n$"), היא מערכת שבה $m$ משוואות לינארית, ו$n$ נעלמים בכל משוואה, מערכת משוואות לינארית מסדר כללי $m\times n$ נראית כך: ${\begin{array}{rcr}\alpha _{11}x_{1}+\alpha _{12}x_{2}+\alpha _{13}x_{3}+...+\alpha _{1n}x_{n}=b_{1}&\\\alpha _{21}x_{1}+\alpha _{22}x_{2}+\alpha _{23}x_{3}+...+\alpha _{2n}x_{n}=b_{2}&\\...&\\...&\\...&\\\alpha _{m1}x_{1}+\alpha _{m2}x_{2}+\alpha _{m3}x_{3}+...+\alpha _{mn}x_{n}=b_{m}\end{array}}$ או בצורה האלגנטית ${\begin{array}{lcl}\sum _{i=1}^{n}\alpha _{1i}x_{i}=b_{1}\ \\\sum _{i=1}^{n}\ \alpha _{2i}x_{i}=b_{2}\ \\&\\....&\\\sum _{i=1}^{n}\ \alpha _{mi}x_{i}=b_{m}\ \end{array}}$

הגדרה 4: מטריצת המקדמים של מערכת לינארית מטריצת המקדמים של המערכת הלינארית ${\begin{array}{rcr}\alpha _{11}x_{1}+\alpha _{12}x_{2}+\alpha _{13}x_{3}+...+\alpha _{1n}x_{n}=b_{1}&\\\alpha _{21}x_{1}+\alpha _{22}x_{2}+\alpha _{23}x_{3}+...+\alpha _{2n}x_{n}=b_{2}&\\...&\\...&\\...&\\\alpha _{m1}x_{1}+\alpha _{m2}x_{2}+\alpha _{m3}x_{3}+...+\alpha _{mn}x_{n}=b_{m}\end{array}}$ נראית כך ${\begin{pmatrix}a_{11}&a_{12}&a_{13}&....&a_{1n}\\a_{21}&a_{22}&a_{23}&....&a_{2n}\\a_{31}&a_{32}&a_{33}&....&a_{3n}\\...&...&...&...&...\\a_{m1}&a_{m2}&a_{m3}&....&a_{mn}\end{pmatrix}}{\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\...\\b_{n}\end{pmatrix}}$, כלומר זו המטריצה שבה במקום ה$(m,n)$ מופיע המקדם $a_{mn}$

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

כתיב מטריציאלי של מערכת משוואות לינארית

הגדרה 5: כתיב מטריציאלי של מערכת משוואות לינארית את המערכת ${\begin{array}{rcr}\alpha _{11}x_{1}+\alpha _{12}x_{2}+\alpha _{13}x_{3}+...+\alpha _{1n}x_{n}=b_{1}&\\\alpha _{21}x_{1}+\alpha _{22}x_{2}+\alpha _{23}x_{3}+...+\alpha _{2n}x_{n}=b_{2}&\\...&\\...&\\...&\\\alpha _{m1}x_{1}+\alpha _{m2}x_{2}+\alpha _{m3}x_{3}+...+\alpha _{mn}x_{n}=b_{m}\end{array}}$ נוכל לכתוב ככפל מטריצות, בצורה $A{\boldsymbol {x}}={\boldsymbol {b}}$, כלומר ${\begin{pmatrix}a_{11}&a_{12}&a_{13}&....&a_{1n}\\a_{21}&a_{22}&a_{23}&....&a_{2n}\\a_{31}&a_{32}&a_{33}&....&a_{3n}\\...&...&...&...&...\\a_{m1}&a_{m2}&a_{m3}&....&a_{mn}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\...\\x_{m}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\...\\b_{m}\end{pmatrix}}$

מערכת משוואות לינארית הומוגנית

הגדרה 6: מערכת משוואות לינארית הומוגנית מערכת משוואות לינארית הומוגנית, היא מערכת משוואות לינארית שעמודת המקדמים החופשיים שלה כולה $0$ כלומר מהצורה ${\begin{array}{lcl}\sum _{i=1}^{n}\alpha _{1i}x_{i}=0\ \\\sum _{i=1}^{n}\ \alpha _{2i}x_{i}=0\ \\&\\....&\\\sum _{i=1}^{n}\ \alpha _{mi}x_{i}=0\ \end{array}}$ או בכתיב מטריציאלי $A{\boldsymbol {x}}={\boldsymbol {0}}$.

משפט 1: הבטחת קיום הפתרון לכל מערכת משוואות לינארית הומוגנית הוכחה נוכיח לגבי מערכת משוואות לינארית הומוגנית כללית, שנראית כך ${\begin{pmatrix}a_{11}&a_{12}&a_{13}&....&a_{1n}\\a_{21}&a_{22}&a_{23}&....&a_{2n}\\a_{31}&a_{32}&a_{33}&....&a_{3n}\\...&...&...&...&...\\a_{m1}&a_{m2}&a_{m3}&....&a_{mn}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\...\\x_{m}\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\...\\0\end{pmatrix}}$ נציב את הnיה $(0,0,0...0)$ שבה n אפסים, ונקבל ${\begin{pmatrix}a_{11}&a_{12}&a_{13}&....&a_{1n}\\a_{21}&a_{22}&a_{23}&....&a_{2n}\\a_{31}&a_{32}&a_{33}&....&a_{3n}\\...&...&...&...&...\\a_{m1}&a_{m2}&a_{m3}&....&a_{mn}\end{pmatrix}}{\begin{pmatrix}0\\0\\0\\...\\0\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\...\\0\end{pmatrix}}$ וזה אכן פתרון, אם משתמשים בכתיב מטריציאלי, אז נציב במשוואה $A{\boldsymbol {x}}={\boldsymbol {0}}$ את הוקטור ${\boldsymbol {x}}={\boldsymbol {0}}$, ונקבל שאכן מתקיים לפי תכונות כפל בסקלר וכפל מרטיצות, השוויון ${\boldsymbol {A}}{\boldsymbol {x}}={\boldsymbol {0}}$, ובכך הבטחנו את קיומו של פתרון אחד לפחות.

שקילות בין מערכות לינאריות

הגדרה 7: מערכות לינאריות שקולות נכתוב שזוג מערכות לינארית, $A{\boldsymbol {x}}={\boldsymbol {b}},M{\boldsymbol {r}}={\boldsymbol {y}}$ שקולות שורה, אם ורק אם יש להן את אותה קבוצה הפתרונות, כלומר אם כאשר הnיה $(z_{1},z_{2},z_{3}...z_{n})$ פותרת את המערכת $A{\boldsymbol {x}}={\boldsymbol {b}}$, היא פותרת גם את $M{\boldsymbol {r}}={\boldsymbol {y}}$, ולהפך.

הגדרה 8: מערכת משוואות לינארית לא הומוגנית מערכת משוואות לינארית לא הומוגנית, היא מערכת שבה בעמודת המקדמים החופשיים יש לפחות איבר אחד שהוא לא אפס, כלומר במערכת ${\begin{pmatrix}a_{11}&a_{12}&a_{13}&....&a_{1n}\\a_{21}&a_{22}&a_{23}&....&a_{2n}\\a_{31}&a_{32}&a_{33}&....&a_{3n}\\...&...&...&...&...\\a_{m1}&a_{m2}&a_{m3}&....&a_{mn}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\...\\x_{m}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\...\\b_{m}\end{pmatrix}}$, צריך שמתוך העמודה ${\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\...\\b_{m}\end{pmatrix}}$, יתקיים לפחות לאיבר אחד $b_{n}$, השוויון $b_{n}\not =0$.

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

על פעולות אלמנטריות

הגדרה 9: פעולות שורה אלמנטריות ישנן כ3 פעולות שורה אלמנטריות, והן: 1. החלפת סדר הופעת המשוואות, מסומן כ$R_{m}\longleftrightarrow R_{n}$ 2. כפל אחת מהמשוואות בסלקר שונה מ0, מסומן כ$R_{m}\longrightarrow \alpha R_{m}$ 3. הוספת כפולה בסלקר של אחת מהמשוואות במערכת לאחרת, מסומן כ$R_{m}\longrightarrow R_{m}+\alpha R_{i}$

משפט 2: שינוי אלמנטרי במערכת משוואות לינארית לא משפיע על מרחב הפתרונות שלה הוכחה: 2 נתחיל בשינוי האלמנטרי $R_{m}\longleftrightarrow R_{n}$, הרי בשתי המערכות(האחת לפני השינוי, והאחת שאחריו) מופיעות בדיוק אותן המשוואות, רק בסדר שונה, אז ברור שמרחב הפתרונות לא השתנה. $\blacksquare$ כעת נעבור לשינוי אלמנטרי מהצורה $R_{m}\longrightarrow \alpha R_{m}$, השינוי $R_{m}\longrightarrow \alpha R_{m}$ משנה רק את השורה ה$m$ של המערכת, כלומר שאר המשוואות ישארו אותו הדבר, והמשוואה שכפלנו בסקלר $t$ תהפוך מהצורה $\alpha _{1}x_{1}+\alpha _{2}x_{2}+\alpha _{3}x_{3}+...+\alpha _{n}x_{n}=b$, למשוואה מהצורה $t\alpha _{1}x_{1}+\alpha _{2}x_{2}+t\alpha _{3}x_{3}+...+t\alpha _{n}x_{n}=tb$, כעת, נניח שהnיה $(z_{1},z_{2},z_{3}...z_{n})$ פותרת את המשוואה, כלומר $\alpha _{1}z_{1}+\alpha _{2}z_{2}+\alpha _{3}z_{3}+...+\alpha _{n}z_{n}=b$, אם נכפול את שני אגפי המשוואה בסקלר $t$ נקבל שמתקיים $t(\alpha _{1}z_{1}+\alpha _{2}z_{2}+\alpha _{3}z_{3}+...+\alpha _{n}z_{n})=tb$, כלומר $t\alpha _{1}z_{1}+t\alpha _{2}z_{2}+t\alpha _{3}z_{3}+...+t\alpha _{n}z_{n}=tb$, אבל זו משוואה מהצורה שקיבלנו מקודם, לאחר כפילת המשוואה בסקלר $t$, כלומר הnיה $(z_{1},z_{2},z_{3}...z_{n})$ היא גם פתרון של המשוואה $t\alpha _{1}x_{1}+\alpha _{2}x_{2}+t\alpha _{3}x_{3}+...+t\alpha _{n}x_{n}=tb$, כנדרש. $\blacksquare$ כעת נעבור להוכחה שאם הnיה $(z_{1},z_{2},z_{3}...z_{n})$ פותרת את המערכת, אזי היא גם תפתור את המערכת לאחר השינוי $R_{m}\longrightarrow R_{m}+\alpha R_{i}$, כיוון שהפעולה משנה רק את המשוואה ה$m$, נוכיח לגביה. אנחנו יודעים שהnיה $(z_{1},z_{2},z_{3}...z_{n})$ פותרת את המשוואה $\alpha _{1}x_{1}+\alpha _{2}x_{2}+\alpha _{3}x_{3}+...+\alpha _{n}x_{n}=b$, שהיא השורה ה$m$, ואנחנו גם יודעים שהnיה $(z_{1},z_{2},z_{3}...z_{n})$ פותרת את המשוואה $\beta _{1}x_{1}+\beta _{2}x_{2}+\beta _{3}x_{3}+...+\beta _{n}x_{n}=y$, שהיא השורה ה$i$. לפי ההוכחה הקודמת, הnיה שלנו תפתור גם את המשוואה $t\beta _{1}x_{1}+t\beta _{2}x_{2}+t\beta _{3}x_{3}+...+t\beta _{n}x_{n}=ty$, כעת נסתכל על המשוואה $R_{m}\longrightarrow R_{m}+\alpha R_{i}$, שנראת כך $(t\beta _{1}+\alpha _{1})x_{1}+(t\beta _{2}+\alpha _{2})x_{2}+(t\beta _{3}+\alpha _{3})x_{3}+...+(t\beta _{n}+\alpha _{n})x_{n}=b+ty$, נפתח סוגריים ונקבל את המשוואה $t\beta _{1}x_{1}+\alpha _{1}x_{1}+t\beta _{2}x_{2}+\alpha _{2}x_{2}+t\beta _{3}x_{3}+\alpha _{3}x_{3}+...+t\beta _{n}x_{n}+\alpha _{n}x_{n}=b+ty$, אם נציב את הnיה שפותרת את המערכת, $(z_{1},z_{2},z_{3}...z_{n})$, נקבל את המשוואה $t\beta _{1}z_{1}+\alpha _{1}z_{1}+t\beta _{2}z_{2}+\alpha _{2}z_{2}+t\beta _{3}z_{3}+\alpha _{3}z_{3}+...+t\beta _{n}z_{n}+\alpha _{n}z_{n}=b+ty$, אבל ניתן לראות, שזה הוא סכום של שתי משוואות שאנחנו יודעים שמתקיימות, הסכום הוא $(t\beta _{1}z_{1}+t\beta _{2}z_{2}+t\beta _{2}z_{2}+t\beta _{3}z_{3}...+t\beta _{n}z_{n})+(\alpha _{1}z_{1}+\alpha _{2}z_{2}+\alpha _{3}z_{3}...+\alpha _{n}z_{n})=b+ty$, ולכן המשוואה אכן מתקיימת והnיה פותרת את המשוואה ולכן גם את המערכת. $\blacksquare$ הערה: בהוכחה האחרונה, הוכחתי שאם nיה פותרת את המערכת היא תפתור אותה גם לאחר השינוי האלמנטרי, יש עוד כיוון והוא להוכיח שאם nיה פותרת את המערכת לאחר השינוי האלמנטרי היא תפתור אותו גם ללא השינוי, כיוון זה די טריוויאלי ונבנה על מה שהוכחנו כבר, ולכן השמטתי אותו(רעיון ההוכחה הוא לבצע את הפעולה האלמנטרית ההפוכה, בזמן שמסתמכים על כך שהשינוי האלמנטרי לא משנה את מרחב הפתרונות של המערכת, כפי שכבר הוכחנו.

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

דירוג מטריצה

הגדרה 10: איבר פותח איבר במטריצה, הוא איבר פותח, אם ורק אם הוא האיבר הראשון מצד שמאל בשורה שלו, שהוא לא $0$, כלומר האיבר $a_{ij}$ הוא איבר פותח במטריצה, אם ורק אם לכל $a_{iv}$, כאשר $0<v<j$ מתקיים $a_{iv}=0$. דוגמא: במטריצה ${\begin{pmatrix}0&2&4&1\\4&2&0&7\\0&0&0&5\\0&9&0&4\end{pmatrix}}$, האיברים הפותחים הם האיברים במקומות ה$(1,2),(2,1),(3,4),(4,2)$, כלומר $2,4,5,9$ בהתאמה לסדר השורות מלמעלה למטה.

הגדרה 11: איבר חופשי איבר במטריצה הוא איבר חופשי אם ורק אם הוא לא איבר פותח. דוגמא: במטריצה הקודמת, ${\begin{pmatrix}0&2&4&1\\4&2&0&7\\0&0&0&5\\0&9&0&4\end{pmatrix}}$, כל איבר שהוא לא במקום ה$(1,2),(2,1),(3,4),(4,2)$, הוא איבר פותח.

הגדרה 12: מטריצה מדורגת מטריצה תיקרא מטריצה מדורגת(או מטריצת מדרגות) אם ורק אם מתקיימים שני תנאים, הראשון הוא שאם קיימת שורת אפסים אז היא נמצאת מתחת לשורות שהן לא שורות אפסים, והתנאי השני הוא שבכל שורה האיבר הפותח נמצא לפחות מקום אחד ימינה מהשורה שמעליה, כלומר אם בשורה $R_{i}$ יש איבר פותח במקום השני, אז בשורה $R_{i+1}$ האיבר הפותח חייב להיות לפחות במקום השלישי. דוגמא: המטריצה ${\begin{pmatrix}1&6&4&2\\0&5&4&3\\0&0&3&2\\0&0&0&7\end{pmatrix}}$ היא מטריצה מדורגת, כיוון שמתקיימים שני התנאים. דוגמא 2: המטריצה ${\begin{pmatrix}0&2&4&1\\4&2&0&7\\0&0&0&5\\0&9&0&4\end{pmatrix}}$ ממקודם היא לא מטריצה מדורגת, כיוון שבשורה הראשונה והרביעית האיבר הפותח נמצא במקום הראשון.

הצגה קנונית של מטריצה

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

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

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

שיטת האלימינציה של גאוס לפתרון מערכת משוואות לינארית

הגדרה 15: אלימינציית גאוס כדי למצוא את קבוצת הפתרונות של מערכת משוואות לינארית בפשטות יתר, נשתמש באלימינציית גאוס. בשיטה הזו, נביא את מטריצת המקדמים של המערכת הלינארית שלנו אל צורה מדורגת, ושם הפתרון כבר ימצא, אופן השיטה הוא למצוא איבר שקל לאפס איתו את שאר האיברים בעמודה שלו,ובכך לדרג בפשטות את המטריצה. דוגמא: ניקח את המערכת משוואות הלינארית $8x_{1}+7x_{2}=5,x_{1}+5x_{2}=7$, מטריצת המקדמים שלה נראית כך: ${\begin{pmatrix}8&7&5\\1&5&7\end{pmatrix}}$, נבצע דירוג, ואז נסביר את המעברים:${\begin{pmatrix}8&7&5\\1&5&7\end{pmatrix}}{\overset {R_{1}\longleftrightarrow R_{2}}{\longrightarrow }}{\begin{pmatrix}1&5&7\\8&7&5\end{pmatrix}}{\overset {R_{2}\longrightarrow R_{2}+(-8)R_{1}}{\longrightarrow }}{\begin{pmatrix}1&5&7\\0&-33&-51\end{pmatrix}}{\overset {R_{2}\longrightarrow {\frac {1}{-33}}R_{2}}{\longrightarrow }}{\begin{pmatrix}1&5&7\\0&1&{\frac {-51}{-33}}\end{pmatrix}}$ הסבר: במעבר הראשון ראינו שיש לנו איבר שנוח לעבוד איתו בשורה השנייה, ולכן החלפנו בין השורות, לאחר מכן במעבר השני איפסנו את האיבר שמתחת ל1 בעזרת פעולת שורה אלמנטרית, ובמעבר האחרון הכפלנו את השורה השניי באיבר ההופכי של $-33$ על מנת לקבל את הפיתרון בקלות.

משפט 3: כמות הפתרונות של מערכת משוואות לינארית לא הומוגנית היא פתרון כללי+הפתרון למערכת ההומוגנית כלומר, אם נסמן $M=\{{\boldsymbol {v}},A{\boldsymbol {v}}={\boldsymbol {0}}\},N=\{{\boldsymbol {v}},A{\boldsymbol {v}}={\boldsymbol {b}}\}$, כלומר הראשונה היא קבוצה הפתרונות של המערכת הלא הומוגנית, והשנייה היא קבוצת הפתרונות של המערכת ההומוגנית, אזי אם ${\boldsymbol {v_{0}}}\in N$, מתקיים $N=M+{\boldsymbol {v_{0}}}$. הוכחה: נניח שמתקיים ${\boldsymbol {v_{0}}}\in N$, ונראה הכלה דו כיוונית בין $N,M+{\boldsymbol {v_{0}}}$, בכיוון הראשון, לכל ${\boldsymbol {v}}\in M$ מתקיים $A({\boldsymbol {v}}+{\boldsymbol {v_{0}}})=A{\boldsymbol {v}}+A{\boldsymbol {v_{0}}}=b+0=b$, ולכן ${\boldsymbol {v}}+{\boldsymbol {v_{0}}}\in N$. בכיוון השני, יהי ${\boldsymbol {h}}\in N$, נרשום ${\boldsymbol {h}}={\boldsymbol {h}}+{\boldsymbol {v_{0}-v_{0}=v_{0}+(h-v_{0})}}$, ומתקיים $A({\boldsymbol {h-v_{0})=}}A{\boldsymbol {h}}-A{\boldsymbol {v_{0}}}=b-b=0$, ולכן $A({\boldsymbol {h-v_{0})=}}A{\boldsymbol {h}}-A{\boldsymbol {v_{0}}}=b-b=0{\boldsymbol {h}}\in {\boldsymbol {v_{0}}}+M$ וסיימנו.