חזור לתיקייה: תרגול

8 - מערכת משוואות ליניארית(ממל)

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • פתירת מערכות של משוואות
  • קביעת דרגות חופש(ד"ח) ומספר פתרונות
  • משפטי דרגות
  • עוד מערכות של משוואות
  • תרגילי נכון/לא נכון למטרת הבהרות

8 - מערכת משוואות ליניארית(ממל)

01040166

אלגברה אמ

רשימות תרגול לקריאה בשבת

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

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

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

{2x1+7x2−3x4=54x1−3x3=4⋮\begin{cases} 2x_{1}+7x_{2}-3x_{4}=5 \\ 4x_{1}-3x_{3}=4 \\ \vdots \end{cases}⎩⎨⎧​2x1​+7x2​−3x4​=54x1​−3x3​=4⋮​

איך נפתור מערכת משוואות עם כל מספר של משתנים ואיזה מספרים שאנו רוצים בצורה יעילה ומובנת?

(270−340−30⋮)A(x1x2x3x4)x⃗=(54⋮)b⃗\underset{A}{\begin{pmatrix} 2&7&0&-3 \\ 4&0&-3&0 \\ \vdots \end{pmatrix}}\underset{\vec{x}}{\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix}}=\underset{\vec{b}}{\begin{pmatrix} 5 \\ 4 \\ \vdots \end{pmatrix}}A​24⋮​70​0−3​−30​​​x​x1​x2​x3​x4​​​​=b​54⋮​​​

כאשר נקרא ל-AAA מטריצת המקדמים, ל-x⃗\vec{x}x וקטור הנעלמים ול-b⃗\vec{b}b הוקטור החופשי.
אנחנו הולכים לדרג מערכת משוואות כך:

(270−3540−304⋮⋮)\left(\begin{array}{cccc|c} 2&7&0&-3&5 \\ 4&0&-3&0&4 \\ \vdots&&&&\vdots \end{array}\right)​24⋮​70​0−3​−30​54⋮​​

אם הגענו לצורה (00005)\left(\begin{array}{cccc|c}0&0&0&0&5\end{array}\right)(0​0​0​0​5​) אין פתרון כי לא יכול להיות ש-0=50=50=5.
אם הגענו לצורה הזו: (1000101000001020001300000)\left(\begin{array}{cccc|c}1&0&0&0&1\\ 0&1&0&0&0\\ 0&0&1&0&2\\ 0&0&0&1&3\\ 0&0&0&0&0\end{array}\right)​10000​01000​00100​00010​10230​​ אז יש פתרון יחיד שכן יש ווקטור משתנים: (1023)\begin{pmatrix}1&0&2&3\end{pmatrix}(1​0​2​3​).
אם הגענו למצב בו יש יותר משנים מאשר שורות שאינן אפסים, יש לנו ∞\infty∞ פתרונות עם מספר דרגות החופש של מספר הנעלמים שאין לנו משוואה בשבילם.
נניח: (120320014000000)\left(\begin{array}{cccc|c}1&2&0&3&2\\ 0&0&1&4&0\\ 0&0&0&0&0\end{array}\right)​100​200​010​340​200​​ אזי המשוואות שיש לנו הינן {x1+2x2+3x4=2x3+4x4=0\begin{cases}x_{1}+2x_{2}+3x_{4}=2\\ x_{3}+4x_{4}=0\end{cases}{x1​+2x2​+3x4​=2x3​+4x4​=0​ ויש לנו ∞\infty∞ פתרונות, עם 2 דרגות חופש.
נבחר באופן חופשי את מי שאין בעמודתו איבר מוביל, במקרה הזה, נבחר את x2x_{2}x2​ ו-x4x_{4}x4​ ונתאים את x1x_{1}x1​ ו-x3x_{3}x3​ בהתאם למשתנים החופשיים שלנו כך: (2−2x2−3x4x24x4x4)\begin{pmatrix}2-2x_{2}-3x_{4}&x_{2}&4x_{4}&x_{4}\end{pmatrix}(2−2x2​−3x4​​x2​​4x4​​x4​​). בדרך כלל נכתוב במקום x3,x4x_{3},x_{4}x3​,x4​ אותיות יווניות כגון α,β\alpha,\betaα,β.

קביעת דרגות חופש(ד"ח) ומספר פתרונות

התנאי המתמטי כדי לקבוע שלמטריצה אין פתרון הוא r(A)<r(A∣b)r(A)<r(A|b)r(A)<r(A∣b).
אם מתקיים r(A)=r(A∣b)r(A)=r(A|b)r(A)=r(A∣b) יכולה לסמן ∞\infty∞ פתרונות או פתרון יחיד:

  • אם r(A)=nr(A)=nr(A)=n אזי יש פתרון יחיד.
  • אם r(A)<nr(A)<nr(A)<n אזי יש ∞\infty∞ פתרונות.
תרגיל

קבעו לאילו ערכים של α\alphaα יש למערכת הבאה פתרון יחיד/∞\infty∞/∅\emptyset∅.

{αx+y+z=0x+αy+z=αx+y+αz=α2\begin{cases} \alpha x+y+z=0 \\ x+\alpha y+z=\alpha \\ x+y+\alpha z=\alpha^2 \end{cases}⎩⎨⎧​αx+y+z=0x+αy+z=αx+y+αz=α2​

נציב במטריצה:

(α1101α1α11αα2)\left(\begin{array}{ccc|c} \alpha&1&1&0 \\ 1&\alpha&1&\alpha \\ 1&1&\alpha&\alpha^2 \end{array}\right)​α11​1α1​11α​0αα2​​

נדרג את המטריצה שלנו(ראינו דירוג זה בתרגול הקודם)

→(1α1α01−αα−1α(α−1)00(r−α)(α+2)(1−α)(1+α)2)\to \left(\begin{array}{ccc|c} 1&\alpha&1&\alpha \\ 0&1-\alpha&\alpha-1&\alpha(\alpha-1) \\ 0&0&(r-\alpha)(\alpha+2)&(1-\alpha)(1+\alpha)^2 \end{array}\right)→​100​α1−α0​1α−1(r−α)(α+2)​αα(α−1)(1−α)(1+α)2​​

נחלק למקרים:

α=−2\alpha=-2α=−2α=1\alpha=1α=1α≠1,−2\alpha\neq 1,-2α=1,−2
נציב ונקבל:
(1−21−203−360003)\left(\begin{array}{ccc|c}1&-2&1&-2\\ 0&3&-3&6\\ 0&0&0&3\end{array}\right)​100​−230​1−30​−263​​
ראו מה קיבלנו בשורה האחרונה
לכן אין פתרון.
r(A)=2<r(A∣b)=3r(A)=2<r(A|b)=3r(A)=2<r(A∣b)=3		נציב ונקבל:
(111100000000)\left(\begin{array}{ccc|c}1&1&1&1\\ 0&0&0&0\\ 0&0&0&0\end{array}\right)​100​100​100​100​​
נראה כי:
r(A)=r(A∣b)=1<n=3r(A)=r(A|b)=1<n=3r(A)=r(A∣b)=1<n=3
ולכן, יש ∞\infty∞ פתרונות עם 2 ד"ח.		r(A)=r(A∣b)=3=nr(A)=r(A|b)=3=nr(A)=r(A∣b)=3=n
ולכן, יש פתרון 1.
תרגיל

כעת, מצאו את הפתרון הכללי במקרה של ∞\infty∞ פתרונות ובמקרה של פתרון יחיד מצאו אותו.

במקרה זה צריך לקנן על מנת למצוא את הפתרון.

  • במקרה של אינסוף פתונות:
(1−x2−x3x2x3)\begin{pmatrix} 1-x_{2}-x_{3}&x_{2}&x_{3} \end{pmatrix}(1−x2​−x3​​x2​​x3​​)
  • במקרה של יחיד:

נקנן את המטריצה שלנו:

R3=1(1−α)(α+2)R3R2=11−αR2→(1α1α01−1−α001(1+α)2α+2)R1=R1−R3R2=R2+R3→(1α0α−(1+α)2α+2010−α+(1+α)2α+2001(1+α)2α+2)\overrightarrow{\begin{matrix} R_{3}=\frac{1}{(1-\alpha)(\alpha+2)R_{3}} \\ R_{2}=\frac{1}{1-\alpha}R_{2} \end{matrix}}\left(\begin{array}{ccc|c} 1&\alpha&1&\alpha \\ 0&1&-1&-\alpha \\ 0&0&1&\frac{(1+\alpha)^2}{\alpha+2} \end{array}\right)\overrightarrow{\begin{matrix} R_{1}=R_{1}-R_{3} \\ R_{2}=R_{2}+R_{3} \end{matrix}}\left(\begin{array}{ccc|c} 1&\alpha&0&\alpha-\frac{(1+\alpha)^2}{\alpha+2} \\ 0&1&0&-\alpha+\frac{(1+\alpha)^2}{\alpha+2} \\ 0&0&1&\frac{(1+\alpha)^2}{\alpha+2} \end{array}\right)R3​=(1−α)(α+2)R3​1​R2​=1−α1​R2​​​​100​α10​1−11​α−αα+2(1+α)2​​​R1​=R1​−R3​R2​=R2​+R3​​​​100​α10​001​α−α+2(1+α)2​−α+α+2(1+α)2​α+2(1+α)2​​​

במצב הזה:

(∗−α+(1+α)2α+2(1+α)2α+2)\begin{pmatrix} &*&-\alpha+\frac{(1+\alpha)^2}{\alpha+2}& \frac{(1+\alpha)^2}{\alpha+2} \end{pmatrix}(​∗​−α+α+2(1+α)2​​α+2(1+α)2​​)

המשתנה x1x_{1}x1​ דורש ניקוי של ה-α\alphaα מהשורה הראשונה ואין זמן בתרגול זה לעשות את זה.

משפטי דרגות

  1. אם r(Am×m)=nr(A_{m\times m})=nr(Am×m​)=n ⇐ צורתה הקנונית היא III (עם/בלי שורות אפסים למטה)
  2. מתקיים: r(A)<r(A∣b)r(A)<r(A|b)r(A)<r(A∣b).
  3. מתקיים: r(Am×n)≤min⁡{m,n}r(A_{m\times n})\leq \min\{ m,n \}r(Am×n​)≤min{m,n}.

עוד מערכות של משוואות

תרגיל

עבור אילו ערכי kkk יהיה ∞/1/∅\infty/1/\emptyset∞/1/∅ פתרונות.

(k12k0k−1−1k2+k−20010)\left(\begin{array}{ccc|c} k&1&2&k \\ 0&k-1&-1&k^2+k-2 \\ 0&0&1&0 \end{array}\right)​k00​1k−10​2−11​kk2+k−20​​

לאור המצב כי המטריצה הינה מדורגת:

k=1k=1k=1k=0k=0k=0k≠0,1k\neq 0,1k=0,1
נציב:
(112100−100010)\left(\begin{array}{ccc|c}1&1&2&1\\ 0&0&-1&0\\ 0&0&1&0\end{array}\right)​100​100​2−11​100​​
r(A)=2=r(A∣b)<3=nr(A)=2=r(A|b)<3=nr(A)=2=r(A∣b)<3=n
ולכן יש ∞\infty∞ פתרונות
עם ד"ח אחת.		נציב:
(01200−1−1−20010)\left(\begin{array}{ccc|c}0&1&2&0\\ 0&-1&-1&-2\\ 0&0&1&0\end{array}\right)​000​1−10​2−11​0−20​​
היא אינה מדורגת ולכן נדרג אותה:
⇓R2=R2+R1\Downarrow R_{2}=R_{2}+R_{1}⇓R2​=R2​+R1​
(0120001−2001002)\left(\begin{array}{ccc|c}0&1&2&0\\ 0&0&1&-2\\ 0&0&\cancel{1}0&\cancel{0}2\end{array}\right)​000​100​2110​0−202​​
ולכן, אין פתרון.		r(A)=r(A∣b)=3=nr(A)=r(A|b)=3=nr(A)=r(A∣b)=3=n
ולכן, יש פתרון יחיד

בשביל למצוא את הפתרון הכללי כאשר k=1k=1k=1 נקנן את המטריצה:

(112100−100010)→(110100100000)\left(\begin{array}{ccc|c}1&1&2&1\\ 0&0&-1&0\\ 0&0&1&0\end{array}\right)\to\left(\begin{array}{ccc|c} 1&1&0&1 \\ 0&0&1&0 \\ 0&0&0&0 \end{array}\right)​100​100​2−11​100​​→​100​100​010​100​​

ולכן, הפתרון הכללי הינו:

(1−x2x20)\begin{pmatrix} 1-x_{2} & x_{2}&0 \end{pmatrix}(1−x2​​x2​​0​)
תרגיל

עבור אילו ערכי kkk יהיה ∞/1/∅\infty/1/\emptyset∞/1/∅ פתרונות.

(k−11k30k−20400k−3k−3000k−4)\left(\begin{array}{ccc|c} k-1&1&k&3 \\ 0&k-2&0&4 \\ 0&0&k-3&k-3 \\ 0&0&0&k-4 \end{array}\right)​k−1000​1k−200​k0k−30​34k−3k−4​​

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

הערה

בגלל שמטריצה זו בעייתית, אנו לא בטוחים כיצד לחלק למקרים. האם לחלק ל-k≠1,2,3k\neq 1,2,3k=1,2,3 ולהתעסק עם 444 ככלי או k≠1,2,3,4k\neq 1,2,3,4k=1,2,3,4 או k≠4k\neq4k=4.
כעת נראה מדוע זה k≠4k\neq4k=4:
גלית משננת לנו בראש "חלוקה למקרים לפי איברים מובילים" חוץ במקרים מסויימים - זה אחד מהמקרים. נשים לב כי אם k=4k=4k=4 אין פתרון, כך שזה לא משנה לשאר הפתרונות.

k≠4k\neq 4k=4k=4k=4k=4
∅\emptyset∅(3020010000)\left(\begin{array}{ccc|c}3&&&\\ 0&2&&\\ 0&0&1&\\ 0&0&0&0\end{array}\right)​3000​200​10​0​​
ולכן, יש פתרון יחיד.
תרגיל

מעל Z5\mathbb{Z}_{5}Z5​:

(k2−kk−11k+1k−100k3k−1−2000k−1k2+k−2)\left(\begin{array}{cccc|c} k^2-k&k-1&1&k+1&k-1 \\ 0&0&k&3k-1&-2 \\ 0&0&0&k-1&k^2+k-2 \end{array}\right)​k2−k00​k−100​1k0​k+13k−1k−1​k−1−2k2+k−2​​

במטריצה הזו, מכיוון שהיא מעל Z5\mathbb{Z}_{5}Z5​ ניתן לעשות אותה יותר יפה באמצעות הפיכת כל ה-(−)(-)(−)ים ל-+++ים המתאימים שלהם ב-Z5\mathbb{Z}_{5}Z5​ כגון −1-1−1 הופך ל-+4+4+4. אנו יכולים להשאיר את המטריצה כך כי אנו יודעים מה זה (−)(-)(−).
תחילה, נראה כי המטריצה מדורגת ונסמן איברים מובילים ואז נחלק למקרים:

k=1k=1k=1k=0k=0k=0k≠0,1k\neq 0,1k=0,1
נציב:
(001200012−200000)\left(\begin{array}{cccc|c}0&0&1&2&0\\ 0&0&1&2&-2\\ 0&0&0&0&0\end{array}\right)​000​000​110​220​0−20​​
נסיים לדרג:
(001200000−200000)\left(\begin{array}{cccc|c}0&0&1&2&0\\ 0&0&0&0&-2\\ 0&0&0&0&0\end{array}\right)​000​000​100​200​0−20​​
ולכן אין פתרון.
∅\emptyset∅		נציב:
(0−111−1000−1−2000−1−2)\left(\begin{array}{cccc|c}0&-1&1&1&-1\\ 0&0&0&-1&-2\\0&0&0&-1&-2 \end{array}\right)​000​−100​100​1−1−1​−1−2−2​​
נבטל את השורה האחרונה עם השורה הלפני האחרונה
על מנת שהמטריצה תהיה מדורגת.
r(A)=2=r(A∣b)<n=4r(A)=2=r(A|b)<n=4r(A)=2=r(A∣b)<n=4
ולכן גם פה יש ∞\infty∞ פתרונות עם 2 ד"ח
ולכן, יש בדיוק 525^252 פתרונות.
נמצא פתרון כללי:
(01−10−10001200000)\left(\begin{array}{cccc|c}0&1&-1&0&-1\\ 0&0&0&1&2\\ 0&0&0&0&0\end{array}\right)​000​100​−100​010​−120​​
נבחר משתנים חופשיים שאינם תלויים אחד בשני
ולכן הפתרון שלנו יהיה:
(x14+x3x32)\begin{pmatrix}x_{1}&4+x_{3}&x_{3}&2\end{pmatrix}(x1​​4+x3​​x3​​2​)		מלכתחילה יש 3 משוואות על 4 נעלמים ולכן אין מצב בו יהיה פתרון יחיד.
נראה כי:
r(A)=3=r(A∣b)<4=nr(A)=3=r(A|b)<4=nr(A)=3=r(A∣b)<4=n
ולכן, יש "∞\infty∞" פתרונות עם ד"ח 1.
במקרה הזה, מכיוון שאנו על Z5\mathbb{Z}_{5}Z5​ יהיו 5 פתרונות(ראו משפט).
משפט

מספר הפתרונות במערכת מעל Zp\mathbb{Z}_{p}Zp​ עם ד"ח kkk הוא: pkp^kpk.

תרגילי נכון/לא נכון למטרת הבהרות

תרגיל (נכון/לא נכון)

אם ל-Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b פתרון יחיד ⇐ Ax⃗=c⃗A\vec{x}=\vec{c}Ax=c פתרון יחיד לכל c⃗\vec{c}c.

באינטואיציה נחשוב כי כאשר דירגנו הגענו מ-(A∣b)(A|b)(A∣b) ל-(I∣∗)(I|*)(I∣∗) ואז לא איכפת לנו ממה יש ב-bbb.
אבל זה אינו נכון, כי אנו יכולים לקחת ccc עם מספר שורות אחר ואז יכול להיות לנו 0=ci0=c_{i}0=ci​ ל-iii כלשהו ואז לא יהיה פתרון.
תשובה: לא נכון.
נראה דוגמה נגדית:

(A∣b)=(107018000)(A∣c)=(1001005)(A|b)=\left(\begin{array}{cc|c} 1&0&7 \\ 0&1&8 \\ 0&0&0 \end{array}\right) \qquad (A|c)=\left(\begin{array}{cc|c} 1&0& \\ 0&1& \\ 0&0&5 \end{array}\right)(A∣b)=​100​010​780​​(A∣c)=​100​010​5​​

ואז, אין פתרון ל-(A∣c)(A|c)(A∣c).

תרגיל (נכון/לא נכון)

אם ל-An×nx⃗=b⃗\underset{n\times n}{A}\vec{x}=\vec{b}n×nA​x=b פתרון יחיד ⇐ Ax⃗=c⃗A\vec{x}=\vec{c}Ax=c פתרון יחיד לכל c⃗\vec{c}c.

מכיוון שזוהי מטריצה ריבועית והיא מטריצת היחידה כשהיא מקוננת, אזי, אין שורה ריקה לחלוטין ובכל שורה יש משתנה 1 אשר הינו קיים במשוואה ולכן יש פתרון אחד.
תשובה: נכון.
הוכחה:
נתון כי r(An×n)=r(A∣b)n×n+1=nr(A_{n\times n})=r(A|b)_{n\times n+1}=nr(An×n​)=r(A∣b)n×n+1​=n
ולכן: n=r(A)≤r(A∣c)≤nn=r(A)\leq r(A|c)\leq nn=r(A)≤r(A∣c)≤n ולכן: r(A)n×n=r(A∣c)=nr(A)_{n\times n}=r(A|c)=nr(A)n×n​=r(A∣c)=n.
∎

תרגיל (נכון/לא נכון)

  1. אם r(Am×n)=mr(A_{m\times n})=mr(Am×n​)=m ⇐ למערכת Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b יש פתרון לכל bbb.
  2. אם r(Am×n)=nr(A_{m\times n})=nr(Am×n​)=n ⇐ למערכת Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b יש פתרון לכל bbb.

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

(1001005)\left(\begin{array}{cc|c} 1&0 \\ 0&1 \\ 0&0&5 \end{array}\right)​100​010​5​​

נראה כי אין פתרון.
לכן טענה (2) אינה נכונה.

שיעורי בית (HW)

כתבו בבית הוכחה לטענה 1️ כמו שכתבנו ממקודם.