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

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

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

מבנה כללי

מערכת כללית של 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. למשל כאשר מדובר בשדה סופי $\mathbb {F} _{3}$ במרחב מממד 2 אז מס' הפתרונות יהיה 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}$.

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

ישרים יכולים:

1. להיחתך בנקודה אחת.

2. להיות מקבילים.

3. להתלכד.

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

חקירה

כאשר המערכת נתונה בצורה שאין מספרים רק מקדמים,ׁ ניתן לנסח תנאים על המקדמים A, B ו- C מתוך הקשר בינם לבין המקדמים של המשוואה המפורשת, m ו- n: 1. פתרון יחיד

על מנת שלמערכת יהיה פתרון יחיד צריך שיתקיים: 

אם נכפיל משוואה זו ב- ${\dfrac {B_{1}}{A_{2}}}$

תתקבל המשוואה : ${\dfrac {A_{1}}{A_{2}}}\neq {\dfrac {B_{1}}{B_{2}}}$ כלומר: אם היחס בין מקדמי המשתנים של x ו- y, שונה – למערכת פתרון יחיד

2. אף פתרון- על מנת שלמערכת לא יהיה פתרון כלל צריכים להתקיים שני תנאים : $m_{1}={\dfrac {A_{1}}{B_{1}}}={\dfrac {A_{2}}{B_{2}}}=m_{2}$

וגם $n_{1}={\dfrac {C_{1}}{B_{1}}}\neq {\dfrac {C_{2}}{B_{2}}}=n_{2}$

דוגמה לחקירה היא התרגיל הבא:

${\begin{cases}x+(4-a)y=a-1\\x(2-2a)-4y=-a\end{cases}}$

${\begin{cases}-(2-2a)x-(2-2a)(4-a)y=-(2-2a)(a-1)\\x(2-2a)-4y=-a\end{cases}}$

$(-2a^{2}+10a-12)y=2a^{2}-5a+2$

תחום ההגדרה של התרגיל:

$a\neq 2a\neq 3$

$y={\dfrac {(a-2)(2a-1)}{(6-2a)(a-2)}}$

$y=a-3$

$\Downarrow$

$x=a-1-(a-4){\dfrac {(2a-1)}{2(3-a)}}$

${\dfrac {a+2}{2(a-3)}}$

פתרון יחיד:

$({\dfrac {a+2}{2(a-3)}},a-3)$

דרכי פתרון לפי רמות של מערכת משוואות ליניאריות עם פרמטרים

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

${\begin{cases}2x+3y=7a\\x-2y=-7a\end{cases}}$

דרך פתרון:

${\begin{cases}2x+3y=7a\\x-2y=-7a\end{cases}}$

${\begin{cases}2x+3y=7a\\-2x+4y=14a\end{cases}}$

$7y=21a$

$y=3a$

$\Downarrow$

$x=-a$

$(-a,3a)$

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

לדוגמה:

${\begin{cases}x+ay=a^{2}\\x+2y=5a-6a\end{cases}}$

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

${\begin{cases}x+ay=a^{2}\\x+2y=5a-6a\end{cases}}$

$(a-2)y=a^{2}-5a+6$

$y={\dfrac {(a-2)(a-3)}{(a-2)}}$

$y=a-3$

$\Downarrow$

$x+a(a-3)=a^{2}$

$x=3a$

$(3a,a-3)$

דרך פתרון שנייה: דרך זו מתאימה לשאלות בהן מתבקשת רק חקירה ללא מתן הפתרון .

${\begin{cases}x+ay=a^{2}\\x+2y=5a-6a\end{cases}}$

$(a-2)y=a^{2}-5a+6$

$y={\dfrac {(a-2)(a-3)}{(a-2)}}$

$y=a-3$

$\Downarrow$

$x+a(a-3)=a^{2}$

$x=3a$

$(3a,a-3)$