Interpolación polinomial

En matemáticas , en análisis numérico , la interpolación de polinomios es una técnica de interpolación de un conjunto de datos o una función mediante un polinomio . En d'autres termes, étant donné un ensemble de points (obtenu, par exemple, à la suite d'une expérience), on cherche un polynôme qui passe par tous ces points, et éventuellement vérifie d'autres conditions, de degré si possible el mas bajo.

Sin embargo, el resultado no siempre está a la altura de las expectativas: en el caso de la interpolación lagrangiana , por ejemplo, la elección de los puntos de interpolación es fundamental. La interpolación en puntos regularmente espaciados puede muy bien divergir incluso para funciones muy regulares ( fenómeno de Runge ).

Definición

En la versión más simple (interpolación lagrangiana), simplemente imponemos que el polinomio pase por todos los puntos dados. Dado un conjunto de $n + 1$ puntos (es decir, parejas de números reales ) $( x i , y i )$ ( $x i$ distintos 2 a 2), tratamos de encontrar un polinomio $p$ (con coeficientes reales) de grado $n$ como máximo que verifique :

{\ Displaystyle p (x_ {i}) = y_ {i} {\ mbox {,}} i = 0, \ ldots, n}

Los Especifica teorema isolvance que sólo hay un polinomio $p$ de grado menor que o igual a $n$ definidos por un conjunto de $n + 1$ puntos.

La interpolación de Hermite consiste en encontrar un polinomio que no solo tome los valores establecidos en la abscisa de datos, sino también la derivada, por lo que la pendiente de la curva toma un valor impuesto en cada uno de estos puntos. Por supuesto, esto requiere un polinomio de grado mayor que el polinomio de Lagrange. También podemos imponer el valor de la segunda, tercera, etc. derivadas. en cada punto. El enfoque de la interpolación newtoniana usando diferencias divididas es particularmente adecuado para construir estos polinomios.

Construcción del polinomio de interpolación de Lagrange

Supongamos que el polinomio de interpolación viene dado por:

{\ Displaystyle p (x) = a_ {n} x ^ {n} + a_ {n-1} x ^ {n-1} + \ cdots + a_ {2} x ^ {2} + a_ {1} x + a_ {0}. \ qquad (1)}

O $p$ debe comprobar:

{\ Displaystyle p (x_ {i}) = y_ {i}, \ qquad \ forall i \ in \ left \ {0,1, \ dots, n \ right \}.}

de modo que este último pase por todos los puntos a interpolar. Al integrar en la ecuación (1), obtenemos un sistema de ecuaciones lineales de incógnitas $a k$ . La escritura matricial es la siguiente:

{\ Displaystyle {\ begin {pmatrix} x_ {0} ^ {n} & x_ {0} ^ {n-1} & x_ {0} ^ {n-2} & \ ldots & x_ {0} & 1 \ \ x_ {1} ^ {n} & x_ {1} ^ {n-1} & x_ {1} ^ {n-2} & \ ldots & x_ {1} & 1 \\\ vdots & \ vdots & \ vdots && \ vdots & \ vdots \ \ x_ {n} ^ {n} & x_ {n} ^ {n-1} & x_ {n} ^ {n-2} & \ ldots & x_ {n} & 1 \ end {pmatrix}} {\ begin {pmatrix} a_ {n} \\ a_ {n-1} \\\ vdots \\ a_ {0} \ end {pmatrix}} = {\ begin {pmatrix} y_ {0} \\ y_ {1} \\\ vdots \\ y_ {n} \ end {pmatrix}}}

Para construir $p ( x )$ , basta con resolver este sistema para obtener los valores de $a k$ . Sin embargo, invertir una matriz completa es un cálculo pesado (con un método de eliminación de Gauss-Jordan , el cálculo es del orden de $2 / 3 n 3$ operaciones). Los métodos mucho más eficientes utilizan una base de polinomios lagrangianos o newtonianos para obtener una matriz diagonal o triangular respectivamente. En la práctica, el cálculo de diferencias divididas reemplaza la resolución del sistema lineal.

La matriz es una matriz del tipo de matriz de Vandermonde . Su determinante es distinto de cero, lo que demuestra el teorema de isolvance: el polinomio de interpolación existe y es único. (La unicidad también resulta del hecho de que si dos polinomios de grado menor o igual $an$ coinciden en $n + 1$ puntos, entonces son iguales).

Error de interpolación

El error de interpolación durante la aproximación de una función $f$ , es decir: cuando $y i = f ( x i )$ en la anterior, viene dado por una fórmula tipo Taylor-Young:

Si $f$ es $n + 1$ veces diferenciable sobre $I = [min ( x 0 , ..., x n , x ), max ( x 0 , ..., x n , x )]$ entonces

{\ Displaystyle \ existe \ xi \ en I \ quad f (x) -p_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)! }} \ prod _ {i = 0} ^ {n} (x-x_ {i}).}

La existencia de tal $ξ$ se demuestra aplicando iterativamente el teorema de Rolle :

Demostración

O bien . Si $x$ es un punto de interpolación, $f$ $($ $x$ $) -$ $p$ $n$ $($ $x$ $) = 0$ y la fórmula se cumple. ${\ Displaystyle x \ in \ mathbb {R}}$

En el resto de la demostración, asumimos que $x$ no es una abscisa de interpolación. Introduzcamos una función auxiliar $g$ :

{\ Displaystyle g: \ mathbb {R} \ rightarrow \ mathbb {R}: t \ rightarrow g (t) = f (t) -p_ {n} (t) - {\ frac {f (x) -p_ { n} (x)} {\ prod _ {i = 0} ^ {n} (x-x_ {i})}} \ prod _ {i = 0} ^ {n} (t-x_ {i}). }

Esta función $g$ tiene $n + 2$ raíces distintas:

{\ Displaystyle x_ {0}, \ dots, x_ {n}, x.}

Por aplicación del teorema de Rolle, $g '$ , derivada de $g$ , tiene $n +1$ raíces distintas (todas ubicadas exactamente entre dos raíces sucesivas de $g$ ). Aplicando el teorema de Rolle nuevamente $n$ veces, obtenemos que tal que (dado que la derivada de orden $n$ $+1$ de $p$ $n$ es cero ). ${\ Displaystyle \ existe \ xi \ in I}$ ${\ Displaystyle 0 = g ^ {(n + 1)} (\ xi) = f ^ {(n + 1)} (\ xi) - {\ frac {f (x) -p_ {n} (x)} {\ prod _ {i = 0} ^ {n} (x-x_ {i})}} (n + 1)!}$

Al aislar $f ( x ) - p n ( x )$ obtenemos el resultado esperado:

{\ Displaystyle f (x) -p_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)!}} \ prod _ {i = 0 } ^ {n} (x-x_ {i})}

En el caso especial donde $x i = x 0 + ih$ (puntos distribuidos uniformemente), un empeoramiento catastrófico del error de interpolación, conocido como fenómeno de Runge , suele ocurrir cuando se incrementa el número de puntos. Para un intervalo dado $[ x 0 , x n ]$ .

Referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Interpolación polinómica " ( consulte la lista de autores ) .

(En) NJ Higham , " Solución rápida de sistemas similares a Vandermonde que involucran polinomios ortogonales " , IMA Journal of Numerical Analysis , vol. 8, n o 4,1988, p. 473–486 ( DOI 10.1093 / imanum / 8.4.473 )
(en) Å Björck y V. Pereyra, " Solución de sistemas de ecuaciones de Vandermonde " , Matemáticas de la computación , American Mathematical Society, vol. 24, n o 112,1970, p. 893–903 ( DOI 10.2307 / 2004623 , JSTOR 2004623 )
(en) D. Calvetti y L. Reichel , " Inversión rápida de polinomios ortogonales de tipo matriz de Vandermonde que involucran " , OIT , vol. 33, n o 33,1993, p. 473–484 ( DOI 10.1007 / BF01990529 )
(en) Endre Süli y David F. Mayers, Introducción al análisis numérico , Cambridge University Press , 2003, p. 183-184 en Google Libros .

Ver también