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

מוטיבציה

בהינתן $n + 1$ נקודות $(c_{0}, y_{0}), \dots, (c_{n}, y_{n}) \in F^{2}$ עם $c_{i}$ שונים זה מזה, נרצה למצוא פולינום $f \in F [x]$ ממעלה לכל היותר $n$ העובר דרכן: $f (c_{i}) = y_{i}$ .

סימון

נסמן $F [x]_{\leq n} := {f \in F [x] : de g f \leq n}$ . זהו מרחב וקטורי מעל $F$ עם בסיס ${1, x, x^{2}, \dots, x^{n}}$ וממד $n + 1$ .

המשפט

קיום ויחידות

אם $c_{0}, \dots, c_{n} \in F$ שונים זה מזה ו- $y_{0}, \dots, y_{n} \in F$ שרירותיים, אז קיים פולינום יחיד $f \in F [x]_{\leq n}$ המקיים $f (c_{i}) = y_{i}$ לכל $i = 0, \dots, n$ .

הוכחה

ניסוח מטריציוני: תנאי $f (c_{i}) = y_{i}$ לפולינום $f (x) = a_{0} + a_{1} x + \dots + a_{n} x^{n}$ שקול למערכת:

V 11 ⋮ 1 c_{0} c_{1} c_{n} c_{0}^{2} c_{1}^{2} c_{n}^{2} \dots \dots \dots c_{0}^{n} c_{1}^{n} ⋮ c_{n}^{n} a_{0} a_{1} ⋮ a_{n} = y_{0} y_{1} ⋮ y_{n}

המטריצה $V$ נקראת מטריצת ונדרמונד (Vandermonde). דטרמיננטת ונדרמונד:

det (V) = 0 \leq i < j \leq n \prod (c_{j} - c_{i})

כי $c_{i}$ שונים זה מזה, $det (V) \neq = 0$ , לכן $V$ הפיכה ויש פתרון יחיד. $■$

פולינומי לגראנז

בניה מפורשת: נגדיר לכל $i = 0, \dots, n$ את פולינום לגראנז ה- $i$ :

L_{i} (x) = \frac{j \neq = i \prod ( x - c _{j} )}{j \neq = i \prod ( c _{i} - c _{j} )}

תכונה: $L_{i} (c_{j}) = δ_{ij} = {10 j = i j \neq = i$

לכן $L_{i} \in F [x]_{\leq n}$ ו- ${L_{0}, \dots, L_{n}}$ מהווים בסיס של $F [x]_{\leq n}$ (הם בלתי תלויים ליניארית, $n + 1$ במספר).

נוסחת האינטרפולציה:

f (x) = i = 0 \sum n y_{i} L_{i} (x)

הוכחה: $f (c_{j}) = \sum_{i = 0}^{n} y_{i} L_{i} (c_{j}) = \sum_{i = 0}^{n} y_{i} δ_{ij} = y_{j}$ . $■$

דוגמה

נמצא $f \in R [x]_{\leq 2}$ עם $f (0) = 1$ , $f (1) = 3$ , $f (2) = 7$ .

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

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

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

f (x) = 1 \cdot \frac{( x - 1 ) ( x - 2 )}{2} + 3 \cdot (- x (x - 2)) + 7 \cdot \frac{x ( x - 1 )}{2}

= \frac{x ^{2} - 3 x + 2}{2} - 3 x^{2} + 6 x + \frac{7 x ^{2} - 7 x}{2} = x^{2} + x + 1

בדיקה: $f (0) = 1$ , $f (1) = 3$ , $f (2) = 7$ . נכון.

ויקי מתמטיקה

סייר

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

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

מוטיבציה

סימון

המשפט

קיום ויחידות

הוכחה

פולינומי לגראנז

דוגמה

ראה גם

מבט גרף

תוכן עניינים

קישורים חוזרים