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

הקדמה:

  • המטרה היא למצוא ערכי ביניים של פונקציה מתוך ערכים בדידים ידועים ומדוייקים.
  • מתוך N+1 נקודות ידועות נתאים עקום שעובר דרך הנקודות. העקום ימצא ע"י אינטרפולציה פולינומית.

לאחר התאמת העקום ניתן למצוא את ערכי הבינים כאשר הוא הפולינום/ הקירוב שמצאנו ו- הוא הפונקציה האמיתית/ הערך שאנחנו מחפשים.

מתי:

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

שיטות:

1) פולינום לגרנז'

2) פולינום ניוטון

3) Splines


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

דרך N+1 נקודות עובר אך ורק פולינום יחיד.

1) פולינום לגרנז'

המקרה הכללי:

הפולינום:

כופלי לגרנז':

עבור 2 נקודות:

כופלי לגרנז':

פולינום האיטרפולציה:

  • הפולינום עובר דרך שתי הנקודות.

חסרון השיטה: בהתווסף נתון נוסף (נקודה נוספת) יש לבצע את החישוב מחדש.


2) פולינום ניוטון - דרך נוספת לבטא פולינום

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

  • פונקציית ההפרשים הסופיים: טכניקת חישוב לערכי b

נגדיר: פונקציה הפרשים סופיים.

  • כעת ניתן לבטא את b כך:


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


3) שיטת ה- Splines

  • כללי: נחלק את התחום למקטעים ולכל מקטע נתאים פולינום.

עבור N+1 נקודות יהיה N מקטעים ולכן גם N פולינומים.

  • בין כל שני פולינומים (מקטעים) נדרוש:

- רציפות בנקודת החיבור.

- רציפות הנגזרת בנקודת החיבור.

- נגזרת שניה רציפה.

  • עבור spline קובי: נתונות n+1 נקודות.

- הפולינום:

- יש לנו 4n נעלמים (מספר הפולינום) ולכן דורשים 4n משוואות.

- המשוואות:

  • נדרוש שהפולינום יעברו דרך הנקודות הנתונות ונדרוש רציפות:

(2n משוואות, עבור נקודת קצה תהיה משוואה אחת בלבד).

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

(n-1 משוואות)

  • רציפות הנגזרת השניה בנקודות פנימיות:

(n-1 משוואות)


  • חסרות עוד 2 משוואות:

- תנאי גבול

- קו ישר בנקודות הקצה