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

→ קודם: ALG1_003הבא: ALG1_005 ←

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

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

הגדרה:

יהיו סקלרים בשדה כאשר ו-. ויהיו נעלמים.
המערכת הבאה נראת מערכת משוואת לינארית (ממ”ל) של משוואות ו- נעלמים:

האיברים נקראים מקדמים ו- נקראים מקדמים חופשיים.
אם לכל המערכת נקראת ממ”ל הומוגנית.
אם לכל המערכת נקראת ממ”ל אי-הומוגנית.
נרצה לכתוב את המערכת בצורה נוחה יותר.
לצורך זה יש לנו 2 הנחות עבודה:

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

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

פתרון של ממ”ל

הגדרה:

תהי מטריצה מסדר . פתרון לממ”ל הוא וקטור עמודה ב- המקיימת .

פעולה אלמנטרית

הגדרה:

הפעולות הבאות נקראות פעולות אלמנטריות על שורות מטריצה:

1. החלפת שורה עם שורה :

1. הכפלת שורה בסקלר :

1. הוספה לשורה כפולה של שורה :

פעולה אלמנטרית היא הפיכה

טענה:

לכל פעולה אלמנטרית קיימת פעולה אלמנטרית הפוכה (כלומר המבטלת אותה) שגם היא פעולה אלמנטרית ומאותו הסוג.

מטריצות שקולות שורה

הגדרה:

יהיו . נאמר כי המטריצה שקולת שורות למטריצה אם מתקבלת מ- ע”י ביצוע מספר סופי של פעולות אלמנטריות על שורות .

תכונות השקילות שורה

משפט:

תהי . אזי:

1. רפלקסיביות: המטריצה שקולת שורות לעצמה.
2. סימטריות: אם שקולת שורות ל-, אז שקולת שורות ל-.
3. טרנזיטיביות: אם שקולת שורות ל-, וגם שקולת שורות ל-, אז שקולת שורות ל-.

הערות:

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

אלגוריתם: דירוג מטריצה

הגדרה:

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

כיצד מדרגים מטריצה?

1. מתחילים מהעמודה הראשונה משמאל ששונה מ-.
2. מומלץ שהאיבר המוביל יהיה שווה ל-.
3. באמצעותו, ורק באמצעותו, מאפסים כלפי מטה את כל האיברים שתחתיו. נזהרים שלא לשנות את השורה המשמשת לשינוי שורות אחרות.
4. עוברים לאיבר המוביל הבא בתור תוך התקדמות כלפי מטה וימינה.
5. חוזרים על התהליך החל משלב 2 ועד לקבלת מטריצה מדורגת.

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

1. מתחילים מהעמודה האחרונה משמאל ששונה מ-.
2. חובה שהאיבר המוביל יהיה שווה ל-.
3. באמצעותו, ורק באמצעותו, מאפסים כלפי מעלה את כל האיברים שמעליו. נזהרים שלא לשנות את השורה המשמשת לשינוי שורות אחרות.
4. עוברים לאיבר המוביל הבא בתור תוך התקדמות כלפי מעלה ושמאלה.
5. חוזרים על התהליך החל משלב 2 ועד לקבלת מטריצה קנונית.

כל מטריצה שקולת שורות למטריצה קנונית יחידה

משפט:

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

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

משפט:

יהיו , אז ו- שקולות שורה אמ”ם הן שקולות שורה לאותה מטריצה קנונית .

דרגת מטריצה

הגדרה:

תהי . הדרגה של המטריצה שווה למספר השורות השונות מ- במטריצה מדורגת, השקולת שורות ל-. מסמנים: .

הערות:

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

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

3. מספיק לדרג מטריצה כדי לקבל את הדרגה. לא חייבים לקנן אותה.

מטריצת המקדמים המורחבת

הגדרה:

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

דוגמאות:

מערכות שקולות

הגדרה:

יהיו ו- שתי מערכות משוואות לינאריות. המערכות נקראות שקולות אם יש להן את אותו אוסף פתרונות.

מטריצות מקדמים מורחבות שקולות שורה גורר מערכות שקולות

משפט:

אם המטריצות ו- מסדר שקולות שורה אז המערכות ו- הן שקולות.

הערות:

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

אלגוריתם: שיטת האלימניציה של גאוס

בהינתן ממ”ל אותה נרצה לפתור, נבצע את השלבים הבאים:

1. נבנה את מטריצת המקדמים המורחבת .
2. נדרג את המטריצה .
3. נפתור את המערכת ע”י חילוץ והצבה מלמטה למעלה.
   מאוד ופעולות דירוג נותנות מערכות שקולות וכל מטריצה שקולת שורה למטריצה מדורגת, הרי שתמיד ניתן לפתור מערכת בשיטה זו.

---

דוגמאות:

1. פתרו את המערכת הבאה:

הקשר בין מספר פתרונות של ממ”ל ודרגת המטריצה

משפט:

תהי ממ”ל. כאשר ו- שדה אינסופי. אזי:

1. למערכת אין פתרונות אמ”ם .
2. למערכת פתרון יחיד אמ”ם .
3. למערכת אינסוף פתרונות אמ”ם .

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

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

מסקנה:

לממ”ל הומוגנית תמיד יש פתרון.

הוכחה:

הגדרה:

הפתרון נקרא הפתרון הטריוויאלי של המערכת.

מסקנה:

אם לממ”ל הומוגנית יש פתרון יחיד אז פתרון זה הוא בהכרח הפתרון הטריוויאלי.

מסקנה:

אם השדה הוא אינסופי ולממ”ל הומוגני יש פתרון לא טריוויאלי אז לממ”ל יש אינסוף פתרונות.

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

הגדרה:

תהי ותהי ממ”ל אי הומוגנית. הממ”ל נקראת המערכת ההומוגנית המתאימה.

הערות:

1. ממ”ל הומוגנית אחת מתאימה להרבה מאוד ממ”ל אי הומוגניות.
2. למערכת ההומוגנית תמיד תהיה פתרון אבל לאי-הומוגנית לא בהכרח.

הקשר בין פתרון ממ”ל הומוגנית ואי הומוגנית

משפט:

תהי ויהי פתרון לממ”ל אי הומוגנית . יהי פתרון אחר של הממ”ל , אז קיים פתרון של הממ”ל ההומוגנית המתאימה , כך ש:

→ קודם: ALG1_003הבא: ALG1_005 ←