NUM1_004 שיטות איטרטיביות לפתרון מערכות לינאריות

מבוא

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

מספר חסרונות של השיטות הישירות:

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

דוגמה לשיטה איטרטיבית היא שיטת ניוטון-רפסון. מציאת השורש של הפונקציה נעשית באמצעות סדרת קירובים תוך שימוש במשיק.

שיטות איטרציה קבועות ושיטות הרפיה

הגדרה:

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

שנרשום כמשוואה וקטורית

נחפש צורה שקולה של המשוואה:

אנחנו מחפשים נקודה קבועה כך שמתקיים:

נגדיר את האיטרציה:

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

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

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

שיטות קבועות

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

נכפיל ב- משמאל:

נוכל לרשום זאת בצורת איטרציה בנקודה קבועה:

כלומר, ה- שלנו היא:

שיטה כזו נקראת שיטה קבועה כי המטריצה שמכפילה את לא תלויה באיטרציה ולכן קבועה. כעת נביט בבחירות שונות של (שלא בהכרח קבועות), בשיטות הרפיה:

שיטות הרפיה

השיטות הבאות שנעסוק בהן נקראות שיטות הרפיה (relaxation methods)**. נביט במערכת המשוואות הלינארית בצורה הבאה:

נסמן את האיטרציה ה--ית ב-, כאשר את הרכיבים שלו נסמן ב-. אז למשל

כאשר נקרא גם הניחוש הראשוני. נביט קודם בשיטת יעקובי:

אלגוריתם: שיטת יעקובי

הגדרה:

בשיטת יעקובי (Jacobi) שנקראת גםsimultaneous relaxtion, אנו בוחרים , כאשר היא מטריצה אלכסונית המכילה רק את האלכסון הראשי של :

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

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

בנוסף, בשיטה ספציפית זו, כל חישוב רכיב תלוי רק באיטרציות הקודמות של אותו רכיב (לעומת השיטה הבאה שנלמד). לכן ניתן לחשב את כל הרכיבים של איטרציה במקביל - מה שמוביל לשם simultaneous relaxtion.

דוגמה:

עבור מערכת המשוואות:

אז:

האיטרציה היעקובית ה- נתון ע”י:

אלגוריתם: שיטת גאוס-זיידל

הגדרה:

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

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

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

דוגמה:

אם נחזור לדוגמה הקודמת, מתקיים:

ולכן, לפי שיטת גאוס-זיידל:

אלגוריתם: שיטת SOR

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

לשינוי זה על שיטת יעקובי אנו קוראים שיטת -יעקובי, ובאותו אופן עבור שיטת -גאוס-זיידל.

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

מסתבר שנגיע לפתרון מדויק הרבה יותר מהר כאשר נשתמש בשיטת -גאוס-זיידל אם נמצא בטווח . זה נקרא שיטת SOR (successive over-relaxtion), והוא נתון ע”י:

בכתיב מטריציוני, ה- שלנו הפך להיות מהצורה:

ולכן:

דוגמה:

שוב, נשתמש באותה דוגמה, ונקבל כי לפי שיטת SOR:

התכנסות שיטות איטרטיביות למערכות לינאריות

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

והשגיאה (שאנו לא יודעים לחשב אותה):

ובכל זאת, נרצה לדעת אם השיטה מתכנסת. כלומר, ש- כאשר .

מטריצת האיטרציה

בשיטות קבועות רשמנו:

נחסר בין המשוואות:

נגדיר , ונקבל:

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

זהו המקרה אם למשל:

כי:

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

התכנסות שיטה איטרטיבית

משפט:

עבור המערכת משוואות לינאריות , והשיטה האיטרטיבית:

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

ככל ש- יותר קטן, ההתכנסות יותר מהירה.

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

נוציא , כך שנמצא שנדרשים

איטרציות כדי להקטין את השגיאה ב-. לכן, נגדיר את קצב ההתכנסות:

לפעמים מגדירים את קצב ההתכנסות גם כ:

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