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

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

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

מבנה כללי

מערכת כללית של m משוואות עם n נעלמים $x_{1},\dots ,x_{n}$ יכולה להיכתב בצורה הבאה:

${\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;=\;&&&b_{m}.\\\end{alignedat}}$

כאשר $a_{1_{1}},\ a_{1_{2}},...,\ a_{m_{n}}$ הם המקדמים של המשתנים ו-$b_{1},\ b_{2},...,b_{m}$ הם המקדמים החופשיים במשוואות.

בדרך כלל המקדמים והמשתנים שייכים לשדה (למשל שדה הממשיים, המרוכבים, או הרציונליים), או לחוג כדוגמת חוג השלמים.

הצגה באמצעות וקטורים

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

$x_{1}{\begin{bmatrix}a_{11}\\a_{21}\\\vdots \\a_{m1}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{12}\\a_{22}\\\vdots \\a_{m2}\end{bmatrix}}+\cdots +x_{n}{\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots \\a_{mn}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}$

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

הצגה באמצעות מטריצות

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

$A{\mathbf {x}}={\mathbf {b}}$

כאשר:

$A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}},\quad {\mathbf {x}}={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\quad {\mathbf {b}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}$

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

פתרון המערכת

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

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

1. למערכת קיימים אינסוף פתרונות (או סופי אבל יותר מאחד במקרה של פתרון מעל שדה סופי)
2. למערכת פתרון יחיד
3. למערכת אין פתרון (הקבוצה הריקה)

מערכת הומוגנית

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

${\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&0\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&0\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\,\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;=\;&&&0.\\\end{alignedat}}$

מערכת כזאת ניתנת לייצוג באמצעות המשוואה $A{\textbf {x}}={\textbf {0}}$, כאשר A הוא מטריצה, x הוא וקטור עמודה של המשתנים, ו0 מסמל את וקטור האפס.

פתרונות

לכל מערכת הומוגנית יש פתרון הנקרא פתרון טריוויאלי, ובו כל המשתנים שווים ל-0 (כלומר: $\ x_{1}=...=x_{n}=0$). לשאר הפתרונות יש תכונות נוספות:

• אם $\ \mathbf {u}$ ו-$\ \mathbf {v}$ הם וקטורים המייצגים פתרונות של המערכת, אז גם וקטור הסכום $\ \mathbf {u} +\mathbf {v}$ מייצג פתרון.
• אם $\ \mathbf {u}$ הוא וקטור המייצג פתרונות של המערכת, אזי לכל סקלר $\ r$ גם הווקטור $\ r\mathbf {u}$ מייצג פתרון.

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

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

משפט: מעל שדה אינסופי, אם למערכת הומוגנית יש פתרון לא טריוויאלי, אז יש לה אינסוף פתרונות. מעל שדה בגודל q, מספר הפתרונות הוא תמיד חזקה של q. למשל כאשר מדובר בשדה סופי Z₃ תחת R² אז מס' הפתרונות יהיה 9=3², כלומר q בחזקת המימד הוא מס' הפתרונות.

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

במקרה של מערכת לא הומוגנית $\ A\mathbf {x} =\mathbf {b}$, מרחב הפתרונות הוא מרחב אפיני (או ישריה), כלומר: מרחב וקטורי + קבוע. במקרה זה הפתרון הכללי שווה לצירוף לינארי כלשהו של פתרונות ממרחב הפתרונות של המערכת ההומוגנית ועוד (ה)פתרון (ה)פרטי של המערכת הלא-הומוגנית.

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

משפט: אם הפתרון יחיד אזי מטריצת המקדמים A היא מטריצה הפיכה משמאל כלומר קיימת מטריצה P מסדר $\ n\times m$ כך ש $\ PA=I_{n}$ והפתרון נתון על ידי $\ \mathbf {x} =P\mathbf {b}$.

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

דוגמה: המקרה הדו-ממדי (פירוש גאומטרי)

פתרון המשוואות x-y=−1 ו-3x+y=9 הוא הנקודה (2,3)

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

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

עבור מערכת עם $\ n$ משתנים, כל משוואה מייצג מרחב $\ n-1$ ממדי, המשוכנים במרחב $\ n$-ממדי אחד.

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

$\ y=m_{1}x+n_{1}$

$\ y=m_{2}x+n_{2}$

כל משוואה כזו (מעל הממשיים) מגדירה ישר במישור האוקלידי, ופתרון המערכת הוא נקודת החיתוך בין שני הישרים. למערכת אין פתרון אם שני הישרים שונים אך מקבילים זה לזה, ולפיכך אינם נחתכים. במצב זה שיפועי הישרים שווים, כלומר $\ m_{1}=m_{2}$, אך $\ n_{1}\neq n_{2}$. למערכת אינסוף פתרונות אם שני הישרים מתלכדים, כלומר, שתי המשוואות מייצגות את אותו ישר. במצב זה $\ m_{1}=m_{2}$, וגם $\ n_{1}=n_{2}$. למערכת פתרון יחיד בכל מקרה אחר, כלומר כאשר $\ m_{1}\neq m_{2}$. במקרה זה שני הישרים נחתכים בנקודה אחת $(x,y)$ שהיא נקודת הפתרון, וערכה הוא $({\frac {n_{2}-n_{1}}{m_{1}-m_{2}}},{\frac {m_{1}n_{2}-n_{1}m_{2}}{m_{1}-m_{2}}})$.

התנהגות כללית

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

1. בדרך כלל, למערכת עם יותר נעלמים מאשר משוואות, יהיו אינסוף פתרונות (או סופי אבל יותר מאחד במקרה של פתרון מעל שדה סופי).
2. בדרך כלל, למערכת עם אותו מספר נעלמים ומשוואות יהיה פתרון יחיד.
3. בדרך כלל, למערכת עם יותר משוואות מאשר נעלמים לא יהיו פתרונות.

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

דרכים לפתרון

פתרון באמצעות הצבה

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

לדוגמה, פתרון המשוואות:

${\begin{alignedat}{7}x&&\;+\;&&3y&&\;-\;&&2z&&\;=\;&&5&\\3x&&\;+\;&&5y&&\;+\;&&6z&&\;=\;&&7&\\2x&&\;+\;&&4y&&\;+\;&&3z&&\;=\;&&8&\end{alignedat}}$

מחלצים את $\ x$ מהמשוואה הראשונה ומקבלים $\ x=5+2z-3y$. מציבים במשוואה השנייה והשלישית ומקבלים:

${\begin{alignedat}{5}-4y&&\;+\;&&12z&&\;=\;&&-8&\\-2y&&\;+\;&&7z&&\;=\;&&-2&\end{alignedat}}$

מחלצים את $\ y$ מהמשוואה הראשונה ומקבלים $\ y=2+3z$. מציבים במשוואה השנייה ומקבלים $\ z=2$. עכשיו ידוע:

${\begin{alignedat}{7}x&&\;=\;&&5&&\;+\;&&2z&&\;-\;&&3y&\\y&&\;=\;&&2&&\;+\;&&3z&&&&&\\z&&\;=\;&&2&&&&&&&&&\end{alignedat}}$

הצבת $\ z=2$ במשוואה השנייה נותנת $\ y=8$, והצבת $\ z=2$ ו-$\ y=8$ במשוואה השלישית נותנת $\ x=-15$. לכן הפתרון הוא השלשה $\ (x,y,z)=(-15,8,2)$.

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

ערך מורחב – דירוג מטריצות

ניתן לפתור את המשוואה על ידי ההצגה באמצעות מטריצה לעיל. מבצעים על המטריצה פעולות עד לקבלת מטריצה מדורגת קנונית, שממנה הפתרון נובע באופן מיידי. שיטה זו נקראת שיטת גאוס-ז'ורדן או "שיטת האלימינציה של גאוס". שיטה זו לפתרון מערכת משוואות לינאריות מבוססת על חיבור, חיסור והכפלה של משוואות בסקלר על מנת להגיע לצורה הקנונית (צורת המדרגות) בה פתרון המשוואות מיידי. בשיטה זו מבודדים באופן שיטתי את המשתנים רק באמצעות פעולות לינאריות על מערכת המשוואות שאינן משנות את קבוצת הפתרונות של המערכת: חיבור וחיסור משוואות, כפל משוואה בסקלר. בהצגה מטריציונית פעולות אלה מתבטאות בחיבור או חיסור שורות, החלפת שורות, כפל שורה בקבוע מספרי והוספתה לשורה אחרת. המטרה הסופית היא להגיע למטריצת מדרגות (קנונית) באמצעות פעולות אלה, ממנה אפשר לקרוא ישירות את הפתרון. (דוגמה)

נוסחת קרמר

ערך מורחב – נוסחת קרמר

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

נוסחת קרמר קובעת שאם $\ A\mathbf {x} =\mathbf {b}$ היא המשוואה, אזי הרכיב ה-$\ k$ של וקטור הפתרון $\mathbf {x}$ נתון על ידי

$\ x_{k}={\frac {\det A_{k}}{\det A}}$

כאשר $\ A_{k}$ היא המטריצה המתקבלת על ידי החלפת העמודה ה-$\ k$ שבמטריצה $\ A$ בווקטור $\mathbf {b}$.

לדוגמה, עבור המערכת

$\ a\mathbf {x} +b\mathbf {y} =e$

$\ c\mathbf {x} +d\mathbf {y} =f$

בנעלמים x ו y (מודגשים), הפתרון נתון על ידי הנוסחאות $\mathbf {x} ={\frac {\begin{vmatrix}e&b\\f&d\end{vmatrix}}{\begin{vmatrix}a&b\\c&d\end{vmatrix}}}={ed-bf \over ad-bc}$ ו- $\mathbf {y} ={\frac {\begin{vmatrix}a&e\\c&f\end{vmatrix}}{\begin{vmatrix}a&b\\c&d\end{vmatrix}}}={af-ec \over ad-bc}$.