שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - הוכחה

שאלה 3 – אינטרפולציה דינמית (עמוד 10) פולינומים ממעלה $n-1$ יכולים להיות מתוארים באמצעות $n$ נקודות שונות. משפט Lagrange קובע שקיים פולינום יחיד $p(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{n-1} x^{n-1}$ המסתפק בתנאים: בהינתן $n$ נקודות $(x_1, y_1), \ldots, (x_n, y_n)$ כאשר לכל $i \ne j$ מתקיים $x_i \ne x_j$, מצאו פולינום אינטרפולציה המסתפק ב-$p(x_i) = y_i$ לכל $i$. הנוסחה לחישוב מקדמים משתמשת בקוד הפולינומים החלקית (Barycentric interpolation): $$p_{i,j}(x) = \frac{q(x) \cdot p_{i,j}(x) - r(x) \cdot p_{i+1,j}(x)}{s(x)}$$ כאשר $q(x) = y_{j+1} - x$, $r(x) = x_k - x$, $s(x) = x_{j+1} - x_k$ ו-$p_{i,j}(x)$ מייצג את הפולינום המסדר $j-i$ המחבר את הנקודות $(x_i, y_i), \ldots, (x_j, y_j)$. (א) בתנאים הנ"ל, הוכחו כי הפולינום שהתקבל הוא יחיד. (ב) תנו סדרה נסיגה לחישוב מקדמי הפולינום $p(x)$ בסדרה של שלבים דינמיים.

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

פתרון: (א) **הוכחת יחידות הפולינום:** נניח בשלילה שקיימים שני פולינומים שונים, $p(x)$ ו-$q(x)$, שמעלתם לכל היותר $n-1$, אשר מקיימים את תנאי האינטרפולציה עבור $n$ הנקודות הנתונות $(x_1, y_1), \ldots, (x_n, y_n)$. כלומר, לכל $i=1, \ldots, n$ מתקיים $p(x_i) = y_i$ וגם $q(x_i) = y_i$. נגדיר פולינום חדש, $d(x)$, בתור ההפרש ביניהם: $$d(x) = p(x) - q(x)$$ מכיוון שמעלתם של $p(x)$ ו-$q(x)$ היא לכל היותר $n-1$, גם מעלתו של $d(x)$ היא לכל היותר $n-1$. נבדוק את ערכי $d(x)$ בנקודות $x_1, \ldots, x_n$: $$d(x_i) = p(x_i) - q(x_i) = y_i - y_i = 0$$ זה נכון לכל $i=1, \ldots, n$. לפיכך, לפולינום $d(x)$ יש לפחות $n$ שורשים שונים ($x_1, \ldots, x_n$, שכן נתון שהם שונים זה מזה). **המשפט היסודי של האלגברה** קובע שפולינום ממעלה $k$ שאינו פולינום האפס יכול להיות בעל $k$ שורשים לכל היותר. במקרה שלנו, $d(x)$ הוא פולינום ממעלה לכל היותר $n-1$ ויש לו $n$ שורשים. המסקנה היחידה האפשרית היא ש-$d(x)$ הוא פולינום האפס, כלומר $d(x) = 0$ לכל $x$. אם $d(x)=0$, אז $p(x) - q(x) = 0$, ומכאן $p(x) = q(x)$. זאת סתירה להנחה הראשונית ש-$p(x)$ ו-$q(x)$ הם פולינומים שונים. לפיכך, פולינום האינטרפולציה ממעלה $n-1$ העובר דרך $n$ נקודות נתונות הוא יחיד. $\blacksquare$ (ב) **נוסחת נסיגה לחישוב מקדמי הפולינום:** כדי למצוא את מקדמי הפולינום $p(x)$ בסדרה של שלבים דינמיים, נשתמש ב**צורת ניוטון של פולינום האינטרפולציה**. בשיטה זו, הפולינום $p(x)$ נכתב בצורה הבאה: $$p(x) = c_0 + c_1(x-x_1) + c_2(x-x_1)(x-x_2) + \ldots + c_{n-1}(x-x_1)\cdots(x-x_{n-1})$$ $$p(x) = \sum_{k=0}^{n-1} c_k \prod_{j=1}^{k} (x-x_j)$$ המקדמים $c_k$ נקראים **הפרשים מחולקים** (divided differences) וניתן לחשב אותם באופן רקורסיבי (או באמצעות טבלה, בגישת **תכנות דינמי**). נסמן את ההפרש המחולק על הנקודות $x_i, \ldots, x_j$ ב-$f[x_i, \ldots, x_j]$. מקדמי פולינום ניוטון הם $c_k = f[x_1, \ldots, x_{k+1}]$. **נוסחת הנסיגה** לחישוב ההפרשים המחולקים היא: 1. **בסיס הרקורסיה (סדר 0):** ההפרשים המחולקים מסדר 0 הם פשוט ערכי ה-$y$ הנתונים: $$f[x_i] = y_i$$ 2. **הצעד הרקורסיבי (סדר $k > 0$):** הפרש מחולק מסדר $k$ המבוסס על הנקודות $x_i, \ldots, x_{i+k}$ מחושב באמצעות שני הפרשים מחולקים מסדר $k-1$: $$f[x_i, \ldots, x_{i+k}] = \frac{f[x_{i+1}, \ldots, x_{i+k}] - f[x_i, \ldots, x_{i+k-1}]}{x_{i+k} - x_i}$$ **התהליך הדינמי:** ניתן לבנות טבלת הפרשים מחולקים. השורה הראשונה בכל עמודה תיתן את המקדמים הדרושים $c_0, c_1, \ldots, c_{n-1}$. - **עמודה 0:** $f[x_1], f[x_2], \ldots, f[x_n]$ (שהם $y_1, y_2, \ldots, y_n$) - **עמודה 1:** $f[x_1, x_2], f[x_2, x_3], \ldots, f[x_{n-1}, x_n]$ - **עמודה 2:** $f[x_1, x_2, x_3], \ldots, f[x_{n-2}, x_{n-1}, x_n]$ - ... - **עמודה $n-1$:** $f[x_1, \ldots, x_n]$ המקדמים של פולינום ניוטון הם האיברים הראשונים בכל עמודה (האלכסון העליון של הטבלה): $c_0 = f[x_1]$ $c_1 = f[x_1, x_2]$ $c_2 = f[x_1, x_2, x_3]$ ... $c_{n-1} = f[x_1, x_2, \ldots, x_n]$ זוהי סדרת שלבים דינמית לחישוב רקורסיבי של מקדמי הפולינום בצורת ניוטון.