Interpolació polinòmica de Newton

L'interpolació polinòmica de Newton és un mètode interpolació polinòmica. Encara que només existeix un únic polinomi que interpola una sèrie de punts, hi ha diferents formes de calcular-lo. Aquest mètode és útil per a situacions que requereixen un nombre baix de punts per a interpolar, ja que a mesura que creix el nombre de punts, també ho fa el grau del polinomi.

Hi ha certs avantatges en l'ús d'aquest polinomi respecte al polinomi interpolador de Lagrange. Per exemple, si fos necessari afegir algun nou punt o nus a la funció, només caldria calcular aquest últim punt, donada la relació de recurrència existent i demostrada anteriorment.

Definició de la pendent

El primer pas per a trobar la fórmula de la interpolació és definir la pendent d'ordre n {\displaystyle n} de manera recursiva:

  • f 0 ( x i ) {\displaystyle f_{0}(x_{i})} : terme i-èsim de la seqüència
  • f 1 ( x 0 , x 1 ) = f 0 ( x 1 ) − f 0 ( x 0 ) x 1 − x 0 {\displaystyle f_{1}(x_{0},x_{1})={\frac {f_{0}(x_{1})-f_{0}(x_{0})}{x_{1}-x_{0}}}}
  • f 2 ( x 0 , x 1 , x 2 ) = f 1 ( x 1 , x 2 ) − f 1 ( x 0 , x 1 ) x 2 − x 0 {\displaystyle f_{2}(x_{0},x_{1},x_{2})={\frac {f_{1}(x_{1},x_{2})-f_{1}(x_{0},x_{1})}{x_{2}-x_{0}}}}

En general:

f i ( x 0 , x 1 , … , x i − 1 , x i ) = f i − 1 ( x 1 , … , x i − 1 , x i ) − f i − 1 ( x 0 , x 1 , … , x i − 1 ) x i − x 0 {\displaystyle f_{i}(x_{0},x_{1},\ldots ,x_{i-1},x_{i})={\frac {f_{i-1}(x_{1},\ldots ,x_{i-1},x_{i})-f_{i-1}(x_{0},x_{1},\ldots ,x_{i-1})}{x_{i}-x_{0}}}} ,

on x i − x j {\displaystyle x_{i}-x_{j}} representa la distància entre dos elements (per exemple, es pot tenir l'element en x = 3 {\displaystyle x=3} i x = 5 {\displaystyle x=5} però desconéixer el valor de la seqüència en x = 4 {\displaystyle x=4} ).

Es pot apreciar com en la definició general s'utilitza la pendent del pas anterior, f i − 1 ( x 1 , … , x i − 1 , x i ) {\displaystyle f_{i-1}(x_{1},\ldots ,x_{i-1},x_{i})} , a la qual se li resta la pendent prèvia de mateix ordre, és a dir, el subíndex dels termes es decrementa en 1 {\displaystyle 1} , com si es desplaçara, per a obtenir f i − 1 ( x 0 , x 1 , … , x i − 1 ) {\displaystyle f_{i-1}(x_{0},x_{1},\ldots ,x_{i-1})} .

Cal notar també que encara que el terme inicial sempre siga x 0 {\displaystyle x_{0}} , aquest pot ser en realitat qualsevol altre, per exemple, es pot definir f 1 ( x i − 1 , x i ) {\displaystyle f_{1}(x_{i-1},x_{i})} de manera anàloga al cas mostrat anteriorment.

Definició del polinomi

Una vegada coneixem la pendent, ja és possible definir el polinomi de grau n {\displaystyle n} de manera també recursiva:

  • p 0 ( x ) = f 0 ( x 0 ) = y 0 {\displaystyle p_{0}(x)=f_{0}(x_{0})=y_{0}} . Es defineix així ja que aquest valor és l'únic que s'ajusta a la seqüència original per al primer terme.
  • p 1 ( x ) = p 0 ( x ) + f 1 ( x 0 , x 1 ) ∗ ( x − x 0 ) {\displaystyle p_{1}(x)=p_{0}(x)+f_{1}(x_{0},x_{1})*(x-x_{0})} .[1]
  • p 2 ( x ) = p 1 ( x ) + f 2 ( x 0 , x 1 , x 2 ) ∗ ( x − x 0 ) ∗ ( x − x 1 ) {\displaystyle p_{2}(x)=p_{1}(x)+f_{2}(x_{0},x_{1},x_{2})*(x-x_{0})*(x-x_{1})} .

En general:

p i ( x ) = p i − 1 ( x ) + f i ( x 0 , x 1 , … , x i − 1 , x i ) ∏ j = 0 i − 1 ( x − x j ) {\displaystyle p_{i}(x)=p_{i-1}(x)+f_{i}(x_{0},x_{1},\ldots ,x_{i-1},x_{i})\prod _{j=0}^{i-1}(x-x_{j})}

Exemples

Posem com a exemple la seqüència f 0 {\displaystyle f_{0}} tal que f 0 ( 1 ) = 6 , f 0 ( 2 ) = 9 , f 0 ( 3 ) = 2 {\displaystyle f_{0}(1)=6,f_{0}(2)=9,f_{0}(3)=2} i f 0 ( 4 ) = 5 {\displaystyle f_{0}(4)=5} , és a dir, són els termes 6 , 9 , 2 , 5 {\displaystyle 6,9,2,5} per a x 0 = 1 {\displaystyle x_{0}=1} fins a x 3 = 4 {\displaystyle x_{3}=4} .

S'obté les pendents d'ordre 1 {\displaystyle 1} de la següent manera:

  • f 1 ( x 0 , x 1 ) = f 0 ( x 1 ) − f 0 ( x 0 ) x 1 − x 0 = 9 − 6 2 − 1 = 3 {\displaystyle f_{1}(x_{0},x_{1})={\frac {f_{0}(x_{1})-f_{0}(x_{0})}{x_{1}-x_{0}}}={\frac {9-6}{2-1}}=3}
  • f 1 ( x 1 , x 2 ) = f 0 ( x 2 ) − f 0 ( x 1 ) x 2 − x 1 = 2 − 9 3 − 2 = − 7 {\displaystyle f_{1}(x_{1},x_{2})={\frac {f_{0}(x_{2})-f_{0}(x_{1})}{x_{2}-x_{1}}}={\frac {2-9}{3-2}}=-7}
  • f 1 ( x 2 , x 3 ) = f 0 ( x 3 ) − f 0 ( x 2 ) x 3 − x 2 = 5 − 2 4 − 3 = 3 {\displaystyle f_{1}(x_{2},x_{3})={\frac {f_{0}(x_{3})-f_{0}(x_{2})}{x_{3}-x_{2}}}={\frac {5-2}{4-3}}=3}

Una vegada tenim les pendents d'ordre 1 {\displaystyle 1} , és possible obtenir les de següent ordre:

  • f 2 ( x 0 , x 1 , x 2 ) = f 1 ( x 1 , x 2 ) − f 1 ( x 0 , x 1 ) x 2 − x 0 = − 7 − 3 3 − 1 = − 5 {\displaystyle f_{2}(x_{0},x_{1},x_{2})={\frac {f_{1}(x_{1},x_{2})-f_{1}(x_{0},x_{1})}{x_{2}-x_{0}}}={\frac {-7-3}{3-1}}=-5}
  • f 2 ( x 1 , x 2 , x 3 ) = f 1 ( x 2 , x 3 ) − f 1 ( x 1 , x 2 ) x 3 − x 1 = 3 − ( − 7 ) 4 − 2 = 5 {\displaystyle f_{2}(x_{1},x_{2},x_{3})={\frac {f_{1}(x_{2},x_{3})-f_{1}(x_{1},x_{2})}{x_{3}-x_{1}}}={\frac {3-(-7)}{4-2}}=5}

Finalment, definim la pendent d'ordre 3 {\displaystyle 3} :

  • f 3 ( x 0 , x 1 , x 2 , x 3 ) = f 2 ( x 1 , x 2 , x 3 ) − f 2 ( x 0 , x 1 , x 2 ) x 3 − x 0 = 5 − ( − 5 ) 4 − 1 = 10 3 {\displaystyle f_{3}(x_{0},x_{1},x_{2},x_{3})={\frac {f_{2}(x_{1},x_{2},x_{3})-f_{2}(x_{0},x_{1},x_{2})}{x_{3}-x_{0}}}={\frac {5-(-5)}{4-1}}={\frac {10}{3}}}

Una vegada tenim la pendent, podem definir els successius polinomis:

  • p 0 ( x ) = 6 {\displaystyle p_{0}(x)=6} .
  • p 1 ( x ) = 6 + 3 ( x − 1 ) {\displaystyle p_{1}(x)=6+3(x-1)}
  • p 2 ( x ) = 6 + 3 ( x − 1 ) − 5 ( x − 1 ) ( x − 2 ) {\displaystyle p_{2}(x)=6+3(x-1)-5(x-1)(x-2)} .
  • p 3 ( x ) = 6 + 3 ( x − 1 ) − 5 ( x − 1 ) ( x − 2 ) + 10 3 ( x − 1 ) ( x − 2 ) ( x − 3 ) {\displaystyle p_{3}(x)=6+3(x-1)-5(x-1)(x-2)+{\frac {10}{3}}(x-1)(x-2)(x-3)}

Podem provar, per exemple, la interpolació lineal pel valor 1.5 {\displaystyle 1.5} , que resulta ser p 1 ( 1.5 ) = 6 + 3 ( 1.5 − 1 ) = 7.5 {\displaystyle p_{1}(1.5)=6+3(1.5-1)=7.5} . Efectivament, al ser una recta, podem veure que aquest valor és igual a 3 + 3 + 6 2 = 7.5 {\displaystyle 3+{\frac {3+6}{2}}=7.5} , el punt mitjà entre tots dos (més el punt inicial, 3 {\displaystyle 3} ).

Referències

  1. ↑ Atès que multipliquem per ( x − x 0 ) {\displaystyle (x-x_{0})} , el segon terme s'anul·la si x = x 0 {\displaystyle x=x_{0}} , reduint-se a p 0 ( x 0 ) = f ( x 0 ) {\displaystyle p_{0}(x_{0})=f(x_{0})} i preservant així la informació original de f ( x 0 ) {\displaystyle f(x_{0})} per a x 0 {\displaystyle x_{0}} . En l'altre extrem, x 1 {\displaystyle x_{1}} , en ser f 1 ( x 0 , x 1 ) {\displaystyle f_{1}(x_{0},x_{1})} la pendent (quocient entre les diferències entre dos termes i les seues abscisses) multiplicaríem per ( x 1 − x 0 ) {\displaystyle (x_{1}-x_{0})} , i obtindríem després de les substitucions f ( x 0 ) + f ( x 1 ) − f ( x 0 ) = f ( x 1 ) {\displaystyle f(x_{0})+f(x_{1})-f(x_{0})=f(x_{1})} que és el valor del segon terme de la seqüència donada i el que acompanya a x 1 {\displaystyle x_{1}} .