מבוא לשיטות נומריות/מציאת שורשים של משוואה

הקדמה:

  • באמצעות איטרציות נרצה למצוא פתרון (שורשים) של משוואה.
  • ההנחה: - פונקציה רציפה.

מתי:

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

שיטות פתרון:

א) שיטות תחום:

1) חציית התחום.

2) אינטרפולציה לינארית.


ב) שיטות פתוחות:

1) ניוטון-רפסון.

2) חיתוך.

3) איטרציות רצופות.


א) שיטת תחום:


1) חציית התחום:

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

  • שלבי פתרון:

1) מנחשים 2 פתרונות התחלתיים כך שסימני הפוכים.

2) מבצעים איטרציות עוקבות

3) אם אז

אם אז


תיאור גרפי:

תיאור גרפי

פתרון התחלתי:


4) אם אז הוא הפתרון המבוקש ויש לעצור את האיטרציות.


התכנסות:

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

כאשר:

- הדיוק הנדרש מאיתנו

- גודל התחום הראשון

n - מספר האיטרציות


נחלץ את n (מספר האיטרציות):


יתרונות השיטה:

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

חסרונות השיטה:

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


2) שיטת האינטרפולציה הלינארית

דומה לשיטת חציית התחום, השוני הוא באופן חישוב הנקודה החדשה .

נבצע אינטרפולציה לינארית של 2 הפתרונות הנוכחיים, קירוב לינארי של f(X) וחיפוש השורש של הקירוב.

* משוואת הישר:

עבור 2 נקודות נרצה למצוא את הישר המחבר בינהן

נקודת החיתוך של ישר זה עם ציר X:


  • האלגוריתם:

1) נמצא שני פתרונות התחלתיים כך ש:

2) נחשב פתרון חדש (שהוא החיתוך עם ציר X של הישר המחבר בין 2 פתרונות התחלתיים אל:

3) נחשב את

4) עדכון הפתרון:

  • אם אז הוא הפתרון המבוקש.
  • אם אז
  • אם אז


  • תיאור גרפי:
תיאור גרפי
  • השיטה לא עובדת עבור פונקציות "שטוחות":
פונקציה שטוחה

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


התכנסות:

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


ב) שיטות פתוחות

1) שיטת ניטון-רפסון:

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

- קירוב למשיק

  • נחשב את נקודת החיתוך עם ציר x של קירוב זה:


  • האיטרציה הכללית:


  • תיאור גרפי:
תיאור גרפי



  • הפתרון עלול להתבדר כאשר הנגזרת הראשונה קרובה לאפס:
תיאור גרפי


  • התכנסות:


כאשר:

- הוא הפתרון האמיתי - לא ידוע.

- השגיאה באיטרציה n+1.

  • קצב ההתכנסות ריבועי (R=2)

  • הפתרון עלול לא להתכנס כאשר בסביבת הפתרון.


2) שיטת החיתוך:

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

שיפוע המיתר:

  • נציב ביטוי זה באיטרציה הכללית של ניוטון-רפסון:

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


  • בדומה לשיטת ניוטון-רפסון הפתרון עלול להתבדר:
תיאור גרפי



  • התכנסות: נפתח ביטוי לשגיאה עבור האיטרציה ה- n+1 (בדומה לשיטת ניוטון-רפסון):

כאשר:

- הפתרון האמיתי והלא ידוע.

- הגדרת השגיאה.


  • קצב ההתכנסות:

  • R > 1 : מדובר בהתכנסות סופר-לינארית.
  • אם אז השיטה קורסת.


3) שיטת האיטרציות הרצופות - משמשת לבעיות מסובכות במיוחד.

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

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

  • תיאור גרפי:
תיאור גרפי



  • שלבי הפתרון:

1) נמצא פתרון התחלתי

2) עדכון הפתרון:

  • ההתכנסות של השיטה לינארית רק כאשר - תנאי להתכנסות
  • - השגיאה באיטרציה ה- n+1