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

הקדמה:

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

• מתוך N+1 נקודות ידועות נתאים עקום $\ g(x)$ שעובר דרך הנקודות. העקום ימצא ע"י אינטרפולציה פולינומית.

לאחר התאמת העקום ניתן למצוא את ערכי הבינים $\ f(y)\cong g(y)$ כאשר $\ g(y)$ הוא הפולינום/ הקירוב שמצאנו ו- $\ f(y)$ הוא הפונקציה האמיתית/ הערך שאנחנו מחפשים.

מתי:

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

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

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

שיטות:

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

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

3) Splines

מציאת עקום האינטרפולציה: הפולינום $\ p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{N}x^{N}=\Sigma _{n=0}^{N}a_{n}x^{n}$

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

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

המקרה הכללי:

הפולינום: $\ p_{N}(x)=L_{0}(x)f(x_{0})+L_{1}(x)f(x_{1})+\cdots +L_{N}(x)f(x_{N})=\Sigma _{n=0}^{N}L_{n}(x)f(x_{n})$

כופלי לגרנז': $\ L_{n}(x)={\frac {\Pi _{i=0,i\neq n}^{N}(x-x_{i})}{\Pi _{i=0,i\neq N}^{N}(x_{n}-x_{i})}}={\frac {(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})(x-x_{n+1})}{(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})(x_{n}-x_{n+1})}}$

עבור 2 נקודות: $\ (x_{0},f(x_{0})),(x_{1},f(x_{1}))$

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

$\ L_{0}(x)={\frac {x-x_{1}}{x_{0}-x_{1}}}L_{1}(x)={\frac {x-x_{0}}{x_{1}-x_{0}}}$

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

$\ p(x)=L_{0}(x)f(x_{0})+L_{1}(x)f(x_{1})$

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

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

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

$\ p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}$ $\ \Leftrightarrow p(x)=b_{0}+b_{1}(x-x_{0})+b_{2}(x-x_{0})(x-x_{1})+\cdots +b_{n}(x-x_{0})(x-x_{1})\cdots (x-x_{n-1}$

• הקשר בין פולינומים מדרגות שונות עוזר לנו למצוא את ערכי $\ b_{0},b_{1},\cdots ,b_{n}$

$\ P(x_{0})=b_{0}=f(x_{0})\quad \Rightarrow b_{0}=f(x_{0})$

$\ P(x_{1})=b_{0}+b_{1}(x_{1}-x_{0})=f(x_{1})\Rightarrow b_{1}={\frac {f_{1}-f_{0}}{x_{1}-x_{0}}}$

$\ P(x_{2})=b_{0}+b_{1}(x_{1}-x_{0})+b_{2}(x-x_{0})(x-x_{1})\Rightarrow b_{2}=\left[{\frac {{\frac {f(x_{2})-f(x_{1})}{(x_{2}-x_{1})}}-{\frac {f(x_{1}-f(x_{0}}{(x_{1}-x_{0})}}}{x_{2}-x_{0}}}\right]$

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

נגדיר: $\ F[x]$ פונקציה הפרשים סופיים.

$\ F[x_{i}]=f(x_{i})$

$\ F[x_{i},x_{j}]={\frac {F(x_{i})-f(x_{j}}{x_{i}-x_{j}}}$

$\ F[x_{t},x_{i},x_{j}]={\frac {F[x_{t},x_{j}]-F[x_{i},x_{j}]}{x_{t}-x_{j}}}$

$\ \vdots$

$\ F[x_{i},x_{i-1},\cdots ,x_{0}]={\frac {F[x_{i},x_{i-1},\cdots ,x_{1}]-F[x_{i}-1,x_{i-2},\cdots ,x_{0}]}{x_{i}-x_{0}}}$

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

$\ b_{0}=f(x_{0})$

$\ b_{1}=f[x_{1},x_{0}]$

$\ b_{2}=f[x_{2},x_{1},x_{0}]$

$\ \vdots$

$\ b_{n}=f[x_{n},x_{n-1},\cdots ,x_{0}]$

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

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

3) שיטת ה- Splines

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

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

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

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

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

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

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

- הפולינום:

$\ (i=1,...,n)\quad P_{i}=a_{01}+a_{1i}x+a_{2i}x^{2}+a_{3i}x^{3}$

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

- המשוואות:

• נדרוש שהפולינום יעברו דרך הנקודות הנתונות ונדרוש רציפות: $\ P_{i}(x_{i})=P_{x+1}(x_{i})=f(x_{i})$

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

• נדרוש רציפות הנגזרת הראשונה בין כל שני מקטעים: $\ P'_{i}(x_{i})=P'_{i+1}(x_{i})$

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

• רציפות הנגזרת השניה בנקודות פנימיות: $\ P''_{i}(x_{i})=P''_{(i+1)}(x_{i})$

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

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

- תנאי גבול

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

$\ P'(x_{0})=P'_{n}(x_{n})=0$

$\ P''(x_{0})=P''_{n}(x_{i})=0$