אלגברה ליניארית (1) - \(80134\) | האונ’ העברית | תשפ”ו א’ | מרצה: ד”ר אלכס גורביץ’ | מתרגל: מר יואב כהן | ליקוט ועריכה: נעם לב
הסיכום הוא לא רשמי ולא עבר אישור של הסגל. אם ישנן טעויות, הן שלי ולא של הסגל.
נלמד פעולות על מטריצות שלא משנות את הקבוצת הפתרונות של המערכת, אף שהן משנות את מערכת המשוואות.
נקראות פעולות שורה אלמנטריות.
פעולות שורה אלמנטריות
כל אחת מהפעולות שומרת על מימדי המטריצה.
יהיו \(m,n\in\mathbb{N}\). פעולת שורה אלמנטריות (פש”א) הן פעולות שמתאימות לכל מטריצה בגודל \(m\times n\) מטריצה אחרת באותו גודל בהתאם לכללים מסוימים. ישנם 3 סוגים:
1. כפל בסקלר
כפל של השורה ה-\(i\) ב-\(0\neq c\in\mathbb{R}\).
\[R_{i}\to cR_{i}\]
כאשר \(R_{i}\) זו השורה ה-\(i\) של המטריצה, מלשון \(\text{Row}\).
2. הוספה של שורה אחרת כפול סקלר
הוספה של השורה ה-\(j\) המוכפלת ב-\(c\in\mathbb{R}\) לשורה ה-\(i\) (\(i\neq j\))
\[R_{i}\to R_{i}+cR_{j}\]
3. החלפת שורות
החלפת השורה ה-\(i\) והשורה ה-\(j\) (\(i\neq j\))
\[R_{i}\leftrightarrow R_{j}\]
פעולה הפוכה
תהי \(A\) מטריצה בגודל \(m\times n\).
יהי \(\mathcal{E}\) פש”א, המטריצה המתקבלת מ-\(A\) ע”י ביצוע של \(\mathcal{E}\) מסומנת ב- \(\mathcal{E}(A)\).
פש”א \(\delta,\mathcal{E}\) נקראות הפוכות זו לזו כאשר לכל מטריצה \(A\) מתקיים \(\delta(\mathcal{E}(A))=A\) וגם \(\mathcal{E}(\delta(A))=A\).
מתקיים: לכל פש”א קיימת פש”א הפוכה (ויחידה, אבל לא הוכחנו זאת).
אם \(\mathcal{E}=(R_{i}\to cR_{i})\) אז פש”א ההפוכה היא \(\delta=(R_{i}\to\frac{1}{c}R_{i})\).
אם \(\mathcal{E}=(R_{i}\to R_{i}+cR_{j})\) אז פש”א ההפוכה היא \(\delta=(R_{i}\to R_{i}-cR_{j})\).
אם \(\mathcal{E}=(R_{i}\leftrightarrow R_{j})\) אז פש”א ההפוכה היא \(\delta=\mathcal{E}\).
(העשרה שהיא הצצה לשלב יותר מתקדם בקורס: פש”א שקולה לכפל משמאל במטריצה אלמנטרית ופש”א הפוכה שקולה לכפל משמאל במטריצה האלמנטרית ההפוכה. היות ולכל מטריצה הפיכה קיימת מטריצה הפוכה אחת בדיוק, גם לכל פש”א קיימת פש”א הפוכה אחת בדיוק).
טענה [אינווריאנטיות קבוצת הפתרונות של ממ”ל תחת פש”א]
נתונות שתי ממ”ל בעלות \(m\) משוואות ו-\(n\) נעלמים כך שהמטריצה המורחבת של הממ”ל השניה מתקבלת מהמטריצה המורחבת של הממ”ל הראשונה ע”י ביצוע פש”א כלשהי. אז קבוצת הפתרונות של שתי המערכות האלה זהות.
הוכחה
[נוכיח עבור פש”א אחת, השאר כתרגיל לבית]
נוכיח את הטענה במקרה שבו \(\mathcal{E}=R_{i}\to R_{i}+cR_{j}\) (שאר המקרים - תרגיל).
כדי להראות שקבוצות הפתרונות של שתי ממ”ל האלה זהות מספיק להראות כי כל פתרון של ממ”ל הראשונה הוא פתרון של ממ”ל השניה, כי המטריצה של הממ”ל הראשונה מתקבלת מהמטריצה של הממ”ל השניה ע”י ביצוע פש”א הפוכה, לפש”א הנתונה.
נסמן את המטריצה המורחבת של הממ”ל הראשונה ב-
\[A=\left(\begin{array}{ccc|c} a_{11} & \dots & a_{1n} & b_{1}\\ \vdots & & \vdots & \vdots\\ \vdots & & \vdots & \vdots\\ a_{m1} & \dots & a_{mn} & b_{m} \end{array}\right)\]
יהי \(\begin{pmatrix}d_{1}\\ \vdots\\ d_{n} \end{pmatrix}\in\mathbb{R}^{n}\) פתרון של הממ”ל הראשונה. אז בפרט הוא פתרון של המשוואות ה-\(i\) וה-\(j\) של הממ”ל הראשונה, כלומר
\[a_{i1}d_{1}+\dots+a_{in}d_{n}=b_{i}\] \[a_{j1}d_{1}+\dots+a_{jn}d_{n}=b_{j}\]
כל משוואה פרט למשוואה ה-\(i\) בממ”ל השניה היא כמו בממ”ל הראשונה. המשוואה ה-\(i\) בממ”ל השניה היא
\[(a_{i1}+ca_{j1})x_{1}+...+(a_{in}+ca_{jn})x_{n}=b_{i}+cb_{j}\]
נציב את \(\begin{pmatrix}x_{1}\\ \vdots\\ x_{n} \end{pmatrix}=\begin{pmatrix}d_{1}\\ \vdots\\ d_{n} \end{pmatrix}\) ונקבל
\[(a_{i1}+ca_{j1})d_{1}+\dots+(a_{in}+ca_{jn})d_{n}=\] \[(a_{i1}d_{1}+\dots+a_{in}d_{n})+c(a_{j1}d_{1}+\dots+a_{jn}d_{n})=b_{i}+cb_{j}\]
זאת אומרת ש- \(\begin{pmatrix}d_{1}\\ \vdots\\ d_{n} \end{pmatrix}\) הוא פתרון של הממ”ל השניה וסיימנו.
\(\square\)
הגדרה - שקילות שורה
תהיינה \(A,B\) מטריצות בגודל \(m\times n\). אומרים כי \(B\) שקולת שורה ל-\(A\) כאשר ניתן לקבל את \(B\) מ-\(A\) ע”י ביצוע של סדרת פש”א.
מסקנה
אם נתונות שתי ממ”ל כך שהמטריצות המורחבות שלהן שקולות שורה, אז קבוצות הפתרונות של הממ”ל האלה זהות.
אלגוריתם דירוג מטריצות
החלק הבא יעסוק באלגוריתם למציאת מטריצה מדורגת מצומצמת השקולת שורה למטריצה נתונה.
עובדה (שלא נוכיח)
לכל מטריצה קיימת מטריצה מדורגת מצומצמת שקולת שורה לה והיא יחידה.
האלגוריתם
1) נשתמש בפש”א מהסוג \(R_{i}\to cR_{i}\) כדי להשיג שכל איבר מוביל יהיה שווה ל-1.
2) נשתמש בפש”א מהסוג \(R_{i}\to R_{i}+cR_{j}\) כדי להשיג שכל המספרים בעמודה של איבר מוביל (חוץ ממנו) שווים ל-0.
3) נשתמש בפש”א מהסוג \(R_{i}\leftrightarrow R_{j}\) כדי להבטיח קיום של התנאי השלישי בהגדרה של מטריצה מדורגת מצומצמת (ה-”דירוג”).
דוגמה
\[\left(\begin{array}{cccc} 0 & 2 & 4 & -2\\ 3 & 2 & -2 & -5\\ 1 & -1 & -4 & 1 \end{array}\right)\xrightarrow{R_{1}\to\frac{1}{2}R_{1}}\]
\[\left(\begin{array}{cccc} 0 & 1 & 2 & -1\\ 3 & 2 & -2 & -5\\ 1 & -1 & -4 & 1 \end{array}\right)\xrightarrow{R_{2}\to R_{2}-2R_{1}}\]
\[\left(\begin{array}{cccc} 0 & 1 & 2 & -1\\ 3 & 0 & -6 & -3\\ 1 & -1 & -4 & 1 \end{array}\right)\xrightarrow{R_{3}\to R_{3}+R_{1}}\]
\[\left(\begin{array}{cccc} 0 & 1 & 2 & -1\\ 3 & 0 & -6 & -3\\ 1 & 0 & -2 & 0 \end{array}\right)\xrightarrow{R_{2}\to\frac{1}{3}R_{2}}\]
\[\left(\begin{array}{cccc} 0 & 1 & 2 & -1\\ 1 & 0 & -2 & -1\\ 1 & 0 & -2 & 0 \end{array}\right)\xrightarrow{R_{3}\to R_{3}-R_{2}}\]
\[\left(\begin{array}{cccc} 0 & 1 & 2 & -1\\ 1 & 0 & -2 & -1\\ 0 & 0 & 0 & 1 \end{array}\right)\xrightarrow{R_{1}\to R_{1}+R_{3}}\]
\[\left(\begin{array}{cccc} 0 & 1 & 2 & 0\\ 1 & 0 & -2 & 0\\ 0 & 0 & 0 & 1 \end{array}\right)\xrightarrow{R_{1}\leftrightarrow R_{2}}\]
\[\left(\begin{array}{cccc} 1 & 0 & -2 & 0\\ 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 1 \end{array}\right)\]
שזו מטריצה מדורגת מצומצמת השקולת שורה למטריצה המקורית.
נציין שהדרך שעברנו היא לא הדרך היחידה לעשות זאת, אבל בסוף תמיד מתקבלת אותה מטריצה מדורגת מצומצמת (לא נוכיח או נשתמש בזה).
סיכום: דירוג מטריצות ואלגוריתם גאוס-ז’ורדן
הגדרה ומטרה
אלגוריתם גאוס-ז’ורדן (\(\text{Gauss-Jordan Elimination}\)) הוא שיטה אלגוריתמית במערכות ליניאריות לביצוע פעולות שורה אלמנטריות על מטריצה נתונה, במטרה להביאה לצורה מדורגת קנונית (\(\text{Reduced Row Echelon Form - RREF}\)). שיטה זו משמשת לפתרון מערכות משוואות ליניאריות, למציאת המטריצה ההופכית, ולחישוב הדרגה (\(Rank\)) של המטריצה [מושגים שנלמד בהמשך].
פעולות שורה אלמנטריות
במהלך הדירוג, מותר לבצע שלוש פעולות הפיכות על שורות המטריצה, אשר אינן משנות את מרחב הפתרונות של המערכת:
החלפת שורות: החלפה בין שורה \(R_{i}\) לשורה \(R_{j}\). מסומן: \(R_{i}\leftrightarrow R_{j}\).
כפל בסקלר: כפל כל איברי השורה \(R_{i}\) בסקלר \(\lambda\neq0\). מסומן: \(R_{i}\to\lambda R_{i}\).
הוספת שורה: הוספת כפולה של שורה \(R_{j}\) לשורה אחרת \(R_{i}\). מסומן: \(R_{i}\to R_{i}+\lambda R_{j}\).
צורה מדורגת קנונית (\(\text{RREF}\))
מטריצה תיקרא מדורגת קנונית אם מתקיימים התנאים הבאים:
כל שורות האפסים (אם ישנן) מופיעות בתחתית המטריצה.
האיבר הראשון שאינו אפס בכל שורה (הנקרא איבר מוביל או \(\text{Pivot}\)) הוא \(1\).
האיבר המוביל של כל שורה נמצא מימין לאיבר המוביל של השורה שמעליו.
בעמודה שבה יש איבר מוביל (\(1\)), כל שאר האיברים הם אפסים (גם מעל וגם מתחת).
תיאור האלגוריתם
תהי \(A\) מטריצה מסדר \(m\times n\). האלגוריתם עובד באופן איטרטיבי על עמודות ושורות המטריצה משמאל לימין:
מצא את העמודה הראשונה שאינה מכילה רק אפסים (זוהי עמודת הציר הנוכחית).
אם האיבר העליון בעמודה זו הוא \(0\), בצע החלפת שורות כדי להביא איבר שונה מאפס לראש העמודה.
בצע פעולת כפל בסקלר כדי להפוך את האיבר המוביל ל-\(1\).
השתמש באיבר המוביל (\(1\)) כדי לאפס את כל האיברים האחרים באותה עמודה (מעליו ומתחתיו) על ידי פעולת הוספת שורות.
התעלם מהשורה הנוכחית ומהעמודה הנוכחית, וחזור על התהליך עבור תת-המטריצה הנותרת.
דוגמה מספרית
נתונה המטריצה \(A\): \[A=\begin{pmatrix}0 & 2 & 4\\ 1 & 3 & 3\\ 3 & 7 & 12 \end{pmatrix}\] שלב 1: החלפת שורות ליצירת איבר מוביל ראשון. נחליף את \(R_{1}\) עם \(R_{2}\) כדי לקבל \(1\) בפינה השמאלית העליונה: \[\xrightarrow{R_{1}\leftrightarrow R_{2}}\begin{pmatrix}1 & 3 & 3\\ 0 & 2 & 4\\ 3 & 7 & 12 \end{pmatrix}\] שלב 2: איפוס מתחת לאיבר המוביל הראשון. נאפס את ה-\(3\) בשורה השלישית על ידי הפעולה \(R_{3}\to R_{3}-3R_{1}\): \[\xrightarrow{R_{3}\to R_{3}-3R_{1}}\begin{pmatrix}1 & 3 & 3\\ 0 & 2 & 4\\ 0 & -2 & 3 \end{pmatrix}\] שלב 3: טיפול באיבר המוביל השני. במטריצה שנותרה (שורות 2-3), האיבר המוביל הוא \(2\).
ננרמל אותו ל-\(1\) על ידי חלוקה ב-2 (\(R_{2}\to\frac{1}{2}R_{2}\)): \[\xrightarrow{R_{2}\to\frac{1}{2}R_{2}}\begin{pmatrix}1 & 3 & 3\\ 0 & 1 & 2\\ 0 & -2 & 3 \end{pmatrix}\] שלב 4: איפוס העמודה השנייה (מעל ומתחת).
נאפס את ה-\(-2\) בשורה השלישית (\(R_{3}\to R_{3}+2R_{2}\)) ואת ה-\(3\) בשורה הראשונה (\(R_{1}\to R_{1}-3R_{2}\)): \[\xrightarrow{\begin{subarray}{l} R_{3}\to R_{3}+2R_{2}\\ R_{1}\to R_{1}-3R_{2} \end{subarray}}\begin{pmatrix}1 & 0 & -3\\ 0 & 1 & 2\\ 0 & 0 & 7 \end{pmatrix}\] שלב 5: טיפול באיבר המוביל השלישי וסיום. ננרמל את האיבר המוביל בשורה השלישית ל-\(1\) (\(R_{3}\to\frac{1}{7}R_{3}\)): \[\xrightarrow{R_{3}\to\frac{1}{7}R_{3}}\begin{pmatrix}1 & 0 & -3\\ 0 & 1 & 2\\ 0 & 0 & 1 \end{pmatrix}\] כעת נאפס את האיברים מעל האיבר המוביל השלישי: \[\xrightarrow{\begin{subarray}{l} R_{2}\to R_{2}-2R_{3}\\ R_{1}\to R_{1}+3R_{3} \end{subarray}}\begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}\] התקבלה מטריצת היחידה, שהיא הצורה המדורגת קנונית של \(A\).
ממ”ל הומוגנית
[סוג חשוב של ממ”ל:]
ממ”ל עם מטריצה מורחבת
\[\left(\begin{array}{ccc|c} a_{11} & \dots & a_{1n} & b_{1}\\ \vdots & & \vdots & \vdots\\ \vdots & & \vdots & \vdots\\ a_{m1} & \dots & a_{mn} & b_{m} \end{array}\right)\]
נקראת הומוגנית כאשר \[b_{1}=\dots=b_{m}=0\]
תכונה [הפתרון הטריוויאלי של ממ”ל הומוגנית]
נתונה ממ”ל הומוגנית ב-\(n\) נעלמים. אז \(\begin{pmatrix}0\\ \vdots\\ 0 \end{pmatrix}\in\mathbb{R}^{n}\) היא תמיד פתרון של הממ”ל.
הפתרון הזה נקרא הפתרון הטריוויאלי.
הערה: הפתרון הטריוויאלי יכול להיות יחיד, ויכול להיות לא יחיד (כלומר יכולים להיות עוד פתרונות לממ”ל הומוגנית). אבל בכל מקרה תמיד יש לפחות פתרון אחד שהוא הפתרון הטריוויאלי.