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

הקדמה:

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

• מתוך 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={\mathrm{\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)={\mathrm{\Sigma }}_{n=0}^N{L}_n(x)f(x_n)$

כופלי לגרנז': $L_n(x)=\frac{{\mathrm{\Pi }}_{i=0,i\ne n}^N(x-x_i)}{{\mathrm{\Pi }}_{i=0,i\ne 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$ $\iff 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)\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}$

$⋮$

$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]$

$⋮$

$b_n=f[x_n,x_{n-1},\cdots ,x_0]$

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

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

3) שיטת ה- Splines

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

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

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

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

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

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

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

- הפולינום:

$(i=1,\mathrm{...},n)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{\text{'}}_i(x_i)=P{\text{'}}_{i+1}(x_i)$

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

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

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

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

- תנאי גבול

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

$P^{\prime }(x_0)=P{\text{'}}_n(x_n)=0$

$P^{″}(x_0)=P^{\prime }{\text{'}}_n(x_i)=0$