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

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

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

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

${\begin{alignedat}{7}3x&&\;+\;&&2y&&\;-\;&&z&&\;=\;&&1&\\2x&&\;-\;&&2y&&\;+\;&&4z&&\;=\;&&-2&\\-x&&\;+\;&&{\tfrac {1}{2}}y&&\;-\;&&z&&\;=\;&&0&\end{alignedat}}$

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

${\begin{alignedat}{2}x&=&1\\y&=&-2\\z&=&-2\end{alignedat}}$

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

מבנה כללי

מערכת כללית של m משוואות עם n נעלמים יכולה להיכתב בצורה הבאה:

${\begin{alignedat}{7}a_{1_{1}}x_{1}&&\;+\;&&a_{1_{2}}x_{2}&&\;+\cdots +\;&&a_{1_{n}}x_{n}&&\;=\;&&&b_{1}\\a_{2_{1}}x_{1}&&\;+\;&&a_{2_{2}}x_{2}&&\;+\cdots +\;&&a_{2_{n}}x_{n}&&\;=\;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m_{1}}x_{1}&&\;+\;&&a_{m_{2}}x_{2}&&\;+\cdots +\;&&a_{m_{n}}x_{n}&&\;=\;&&&b_{m}.\\\end{alignedat}}$

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

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

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

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

$x_{1}{\begin{bmatrix}a_{1_{1}}\\a_{2_{1}}\\\vdots \\a_{m_{1}}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{1_{2}}\\a_{2_{2}}\\\vdots \\a_{m_{2}}\end{bmatrix}}+\cdots +x_{n}{\begin{bmatrix}a_{1_{n}}\\a_{2_{n}}\\\vdots \\a_{m_{n}}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}$

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

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

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

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

כאשר:

$A={\begin{bmatrix}a_{1_{1}}&a_{1_{2}}&\cdots &a_{1_{n}}\\a_{2_{1}}&a_{2_{2}}&\cdots &a_{2_{n}}\\\vdots &\vdots &\ddots &\vdots \\a_{m_{1}}&a_{m_{2}}&\cdots &a_{m_{n}}\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_{1_{1}}x_{1}&&\;+\;&&a_{1_{2}}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&0\\a_{2_{1}}x_{1}&&\;+\;&&a_{2_{2}}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&0\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\,\vdots \\a_{m_{1}}x_{1}&&\;+\;&&a_{m_{2}}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^{[דרושה הבהרה]}.

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

במקרה של מערכת לא הומוגנית $\ 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}$.