Interpolación polinomial

Polinomio de interpolación de 7 ° grado

En matemáticas numéricas , la interpolación de polinomios es la búsqueda de un polinomio que se ejecuta exactamente a través de puntos específicos (por ejemplo, de una serie de medidas). Este polinomio se llama polinomio de interpolación y se dice que interpola los puntos dados.

Aplicaciones

Los polinomios se pueden integrar y derivar muy fácilmente. Es por eso que los polinomios de interpolación aparecen en muchos lugares en la matemática numérica, por ejemplo en la integración numérica y, en consecuencia, en los métodos para la solución numérica de ecuaciones diferenciales ordinarias .

Problema

Para pares dados de valores con diferentes puntos de interpolación en pares , se busca un polinomio de grado máximo que contenga todas las ecuaciones. ${\ Displaystyle n + 1}$${\ Displaystyle (x_ {i}, \, f_ {i})}$ ${\ Displaystyle x_ {i}}$${\ Displaystyle P}$${\ Displaystyle n}$

${\ Displaystyle P (x_ {i}) = f_ {i}, \ quad i = 0, \ dotsc, n}$

Cumple. Tal polinomio siempre existe y se determina de forma única, como se mostrará a continuación.

En el caso del problema de interpolación , los polinomios con grados o menos deben buscarse en el espacio vectorial , en definitiva . Es una base de , las ecuaciones producen un sistema de ecuaciones lineales para los coeficientes de la representación de la base . Dado que un mismo polinomio se puede representar de manera diferente, dependiendo de qué base se elija para el espacio vectorial , se pueden obtener sistemas de ecuaciones muy diferentes. Si elige la base estándar , es decir, para la representación , obtiene un sistema de ecuaciones con la matriz de Vandermonde : ${\ Displaystyle P}$ ${\ Displaystyle \ Pi _ {n}}$${\ Displaystyle n}$${\ Displaystyle P \ en \ Pi _ {n}}$${\ Displaystyle \ phi _ {0}, \ dotsc, \ phi _ {n}}$${\ Displaystyle \ Pi _ {n}}$${\ Displaystyle P (x_ {i}) = f_ {i}}$${\ Displaystyle P = \ sum _ {k = 0} ^ {n} a_ {k} \ phi _ {k}}$${\ Displaystyle \ Pi _ {n}}$${\ Displaystyle \ Pi _ {n}}$${\ Displaystyle \ left \ {x ^ {k} \ mid 0 \ leq k \ leq n \ right \}}$${\ Displaystyle P}$${\ Displaystyle P (x) = \ sum _ {k = 0} ^ {n} a_ {k} x ^ {k}}$

${\ displaystyle {\ begin {pmatrix} 1 & x_ {0} & \ cdots & x_ {0} ^ {n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ 1 & x_ {n} & \ cdots & x_ {n} ^ {n} \ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\\ vdots \\ a_ {n} \ end {pmatrix}} = {\ begin {pmatrix} f_ {0} \\\ vdots \\ f_ {n} \ end {pmatrix}}}$.

Esto es normal si los puntos de apoyo son diferentes en pares, el sistema de ecuaciones se puede resolver sin ambigüedades. De esta forma, se garantiza siempre la existencia y unicidad del polinomio buscado . A pesar de la representación teóricamente simple, este sistema de ecuaciones no se utiliza en la práctica para calcular el polinomio de interpolación, ya que su solución es compleja y generalmente está mal condicionada . ${\ Displaystyle x_ {i}}$${\ Displaystyle P \ en \ Pi _ {n}}$

Método de solución

El sistema de ecuaciones anterior podría resolverse, por ejemplo, con el método de eliminación de Gauss . Sin embargo, con (ver símbolos de Landau ) el esfuerzo involucrado sería comparativamente grande. Si se selecciona una base diferente a la base estándar para describir el polinomio , se puede reducir el esfuerzo. ${\ Displaystyle {\ mathcal {O}} \ left (n ^ {3} \ right)}$${\ Displaystyle P}$

Fórmula de interpolación lagrangiana

Funciones base lagrangianas ejemplares para x ₀ = 0, x ₁ = 1, x ₂ = 2, x ₃ = 3 (n = 3)

Una representación en la base de Lagrange es más favorable para consideraciones teóricas . Las funciones básicas son los polinomios de Lagrange

${\ Displaystyle \ ell _ {i} (x) = \ prod _ {\ begin {smallmatrix} j = 0 \\ j \ neq i \ end {smallmatrix}} ^ {n} {\ frac {x-x_ {j }} {x_ {i} -x_ {j}}} = {\ frac {x-x_ {0}} {x_ {i} -x_ {0}}} \ cdots {\ frac {x-x_ {i- 1}} {x_ {i} -x_ {i-1}}} \ cdot {\ frac {x-x_ {i + 1}} {x_ {i} -x_ {i + 1}}} \ cdots {\ frac {x-x_ {n}} {x_ {i} -x_ {n}}} \ ,,}$

que se definen de modo que

${\ Displaystyle \ ell _ {i} (x_ {k}) = \ delta _ {ik} = \ left \ {{\ begin {matrix} 1 & {\ text {if}} i = k \\ 0 & { \ text {if}} i \ neq k \ end {matriz}} \ right.}$

se aplica, en el delta de Kronecker representa. Por tanto, la matriz corresponde exactamente a la matriz identidad . La solución al problema de interpolación se puede dar simplemente como ${\ Displaystyle \ delta _ {ik}}$${\ Displaystyle \ left (\ ell _ {i} \ left (x_ {j} \ right) \ right) _ {i, j = 0,1, \ dotsc, n}}$

${\ Displaystyle P (x) = \ sum _ {i = 0} ^ {n} f_ {i} \ ell _ {i} \ left (x \ right)}$

con los valores de apoyo . Esto se usa a menudo para probar la existencia de la solución al problema de interpolación. Una ventaja de la base de Lagrange es que las funciones de la base son independientes de los valores de soporte . Como resultado, diferentes conjuntos de valores de interpolación con los mismos puntos de interpolación se pueden interpolar rápidamente una vez que se han determinado las funciones básicas . Sin embargo, una desventaja de esta representación es que todos los vectores base deben recalcularse completamente cuando se agrega un solo punto de apoyo, razón por la cual este método es demasiado complejo para la mayoría de los propósitos prácticos. En el procesamiento de señales digitales, la interpolación de Lagrange se utiliza con el nombre de "Filtro de Farrow" para el remuestreo adaptativo. ${\ Displaystyle f_ {i}}$${\ Displaystyle \ ell _ {i}}$${\ Displaystyle f_ {i}}$${\ Displaystyle f_ {i}}$${\ Displaystyle x_ {i}}$${\ Displaystyle \ ell _ {i}}$

Fórmula de interpolación baricéntrica

La fórmula de interpolación lagrangiana se puede transformar en la fórmula de interpolación baricéntrica prácticamente más relevante

${\ Displaystyle P (x) = {\ frac {\ sum _ {j = 0} ^ {n} {\ frac {\ lambda _ {j} f_ {j}} {x-x_ {j}}}} { \ sum _ {j = 0} ^ {n} {\ frac {\ lambda _ {j}} {x-x_ {j}}}}} \ ,,}$

donde los pesos baricéntricos se definen de la siguiente manera

${\ Displaystyle \ lambda _ {j}: = \ prod _ {\ begin {smallmatrix} i = 0 \\ i \ neq j \ end {smallmatrix}} ^ {n} {\ frac {1} {x_ {j} -x_ {i}}} \,.}$

Los pesos se pueden calcular previamente para puntos de apoyo especificados , de modo que el esfuerzo para la evaluación de ahora sea solo . Al agregar un nuevo punto de apoyo, se deben volver a determinar los pesos. Esto tiene un costo en comparación con la redeterminación de los polinomios lagrangianos de . ${\ Displaystyle \ left (x_ {i} \ right) _ {i}}$${\ Displaystyle \ left (\ lambda _ {i} \ right) _ {i}}$${\ Displaystyle P (x)}$${\ Displaystyle {\ mathcal {O}} (n)}$${\ Displaystyle {\ mathcal {O}} (n)}$${\ Displaystyle {\ mathcal {O}} \ left (n ^ {2} \ right)}$

Algoritmo de Newton

En este procedimiento, el polinomio se representa en base a Newton para que los coeficientes se puedan determinar de manera eficiente usando el esquema de diferencias divididas . Entonces se puede realizar una evaluación eficiente del polinomio con la ayuda del esquema de Horner . ${\ Displaystyle P}$

Enfoque: base de Newton

Como enfoque para el polinomio de interpolación que está buscando, elige las funciones de base de Newton y con , para que se represente con la fórmula de interpolación de Newton ${\ Displaystyle P}$${\ Displaystyle N_ {0} (x) = 1}$${\ Displaystyle \ textstyle N_ {i} (x) = \ prod _ {j = 0} ^ {i-1} \ left (x-x_ {j} \ right) = \ left (x-x_ {0} \ derecha) \ dotsm \ left (x-x_ {i-1} \ right)}$${\ Displaystyle i = 1, \ dotsc, n}$${\ Displaystyle P}$

${\ Displaystyle P (x) = \ sum _ {i = 0} ^ {n} c_ {i} \ cdot N_ {i} (x) = c_ {0} + c_ {1} \ left (x-x_ { 0} \ right) + c_ {2} \ left (x-x_ {0} \ right) \ left (x-x_ {1} \ right) + \ dotsb + c_ {n} \ left (x-x_ {0 } \ right) \ dotsm \ left (x-x_ {n-1} \ right)}$

El sistema de ecuaciones de ecuaciones tiene entonces la forma ${\ Displaystyle P (x_ {i}) = f_ {i}}$

${\ displaystyle {\ begin {pmatrix} 1 &&&& 0 \\ 1 & (x_ {1} -x_ {0}) &&& \\ 1 & (x_ {2} -x_ {0}) & (x_ {2} - x_ {0}) (x_ {2} -x_ {1}) && \\\ vdots & \ vdots && \ ddots & \\ 1 & (x_ {n} -x_ {0}) & \ cdots && \ prod _ {i = 0} ^ {n-1} (x_ {n} -x_ {i}) \\\ end {pmatrix}} \ cdot {\ begin {pmatrix} c_ {0} \\\ vdots \\ c_ { n} \ end {pmatrix}} = {\ begin {pmatrix} f_ {0} \\\ vdots \\ f_ {n} \ end {pmatrix}}}$

A diferencia de la matriz de Vandermonde, cuando se selecciona la base estándar , cuando se selecciona la base de Newton, se obtiene una matriz triangular inferior estructurada simplemente y el sistema de ecuaciones se puede resolver fácilmente. ${\ Displaystyle \ left \ {x ^ {k} \ mid 0 \ leq k \ leq n \ right \}}$

Determinación de los coeficientes: esquema de las diferencias divididas

Los coeficientes no se determinan directamente a partir del sistema de ecuaciones anterior, sino de manera más eficiente con la ayuda de las diferencias divididas. Por inducción se prueba con la fórmula de recursividad de Aitken que se aplica a los coeficientes${\ Displaystyle c_ {i}}$${\ Displaystyle c_ {i}}$

${\ Displaystyle c_ {i} = \ left [x_ {0}, \ dotsc, x_ {i} \ right] f}$.

Aquí, para las diferencias divididas definidas recursivamente ${\ Displaystyle i <j}$${\ Displaystyle \ left [x_ {i}, \ dotsc, x_ {j} \ right] f}$

${\ Displaystyle \ left [x_ {i} \ right] f = f_ {i} \ qquad}$

${\ Displaystyle \ left [x_ {i}, \ dotsc, x_ {j} \ right] f = {\ frac {\ left [x_ {i + 1}, \ dotsc, x_ {j} \ right] f- \ izquierda [x_ {i}, \ dotsc, x_ {j-1} \ right] f} {x_ {j} -x_ {i}}}}$.

La notación con un apéndice se explica por el hecho de que a menudo se supone una función desconocida , que se interpola con valores de función conocidos . ${\ Displaystyle f}$${\ Displaystyle f}$${\ Displaystyle f_ {i} = f \ left (x_ {i} \ right)}$

El cálculo recursivo de las diferencias divididas se puede ilustrar de la siguiente manera. Los coeficientes que busca son exactamente la línea diagonal superior: ${\ Displaystyle c_ {i}}$

${\ displaystyle {\ begin {array} {crcrccrcrc} [x_ {0}] f \\ & \ Searrow \\ {} [x_ {1}] f & \ rightarrow & [x_ {0}, x_ {1}] f \\ & \ Searrow && \ Searrow \\ {} [x_ {2}] f & \ rightarrow & [x_ {1}, x_ {2}] f & \ rightarrow & [x_ {0}, x_ {1} , x_ {2}] f \\ {} \ vdots & \ vdots & \ vdots & \ vdots & \ vdots & \ ddots \\ {} & \ Searrow && \ Searrow &&& \ Searrow \\ {} [x_ {n- 1}] f & \ rightarrow & [x_ {n-2}, x_ {n-1}] f & \ rightarrow & [x_ {n-3}, x_ {n-2}, x_ {n-1}] f & \ cdots & \ rightarrow & [x_ {0}, \ ldots, x_ {n-1}] f \\ & \ busqueda && \ busqueda &&& \ busqueda && \ busqueda \\ {} [x_ {n}] f & \ rightarrow & [x_ {n-1}, x_ {n}] f & \ rightarrow & [x_ {n-2}, x_ {n-1}, x_ {n}] f & \ cdots & \ rightarrow & [x_ {1}, \ ldots, x_ {n}] f & \ rightarrow & [x_ {0}, \ ldots, x_ {n}] f \ end {array}}}$

Obviamente, al agregar un punto adicional a los pares de valores en el esquema anterior, solo se necesita agregar una línea más para calcular el coeficiente adicional . No es necesario volver a calcular los coeficientes determinados previamente . ${\ Displaystyle n + 1}$${\ Displaystyle \ left (x_ {i}, f_ {i} \ right)}$${\ Displaystyle \ left (x_ {n + 1}, f_ {n + 1} \ right)}$${\ Displaystyle c_ {n + 1} = \ left [x_ {0}, \ dotsc, x_ {n + 1} \ right] f}$${\ Displaystyle c_ {0}, \ dotsc, c_ {n}}$

Como alternativa a la definición recursiva anterior, en uno de los artículos de Marsden, por ejemplo, la diferencia dividida de una función diferenciable con suficiente frecuencia se define como el coeficiente inequívoco a la potencia más alta de un polinomio -ésimo grado que se interpola en los puntos . Si aparece un valor en la secuencia con la multiplicidad , las derivadas del polinomio deben interpolar las derivadas de la función en este punto hasta el orden . Por tanto, es verdad ${\ Displaystyle \ left [x_ {0}, \ dotsc, x_ {n} \ right] f}$${\ Displaystyle f}$${\ Displaystyle x}$${\ Displaystyle n}$${\ Displaystyle p (x)}$${\ Displaystyle f}$${\ Displaystyle x_ {0}, \ dotsc, x_ {n}}$${\ Displaystyle x_ {0}, \ dotsc, x_ {n}}$${\ Displaystyle \ nu \ geq 1}$${\ Displaystyle f}$${\ Displaystyle \ nu -1}$

${\ Displaystyle \ left [x_ {0}, \ dotsc, x_ {k} \ right] f = {\ frac {f ^ {(k)} (x ^ {*})} {k!}} \ qquad { \ text {if}} \ quad x ^ {*}: = x_ {0} = \ dotsb = x_ {k} \,.}$

Evaluación del polinomio: esquema de Horner

Una vez que se conocen los coeficientes del polinomio de interpolación , se puede evaluar de manera eficiente utilizando el esquema de Horner . Para hacer esto, se escribe en la forma (transformación simple de la fórmula de interpolación de Newton) ${\ Displaystyle c_ {i}}$${\ Displaystyle P}$${\ Displaystyle P}$

${\ Displaystyle P (x) = \ left (\ dotso \ left (c_ {n} \ left (x-x_ {n-1} \ right) + c_ {n-1} \ right) \ left (x-x_ {n-2} \ right) + \ dotsb + c_ {1} \ right) \ left (x-x_ {0} \ right) + c_ {0}}$,

por lo que se puede calcular de forma recursiva a través de ${\ Displaystyle P (x)}$

${\ Displaystyle {\ begin {alineado} b_ {n} & = c_ {n} \\ b_ {i} & = b_ {i + 1} \ left (x-x_ {i} \ right) + c_ {i} , \ qquad i = n-1, \ dotsc, 0 \\ P (x) & = b_ {0} \ end {alineado}}}$

Esto requiere un esfuerzo de . ${\ Displaystyle {\ mathcal {O}} (n)}$

Algoritmo de Neville-Aitken

Similar al algoritmo de Newton, el algoritmo de Neville-Aitken calcula la solución de forma recursiva. Para este propósito, denote el polinomio de interpolación determinado unívocamente -ésimo grado para los puntos de apoyo , donde es. Entonces se aplica la fórmula de recursividad de Aitken: ${\ Displaystyle p \ left (f | x_ {i}, \ dotsc, x_ {j} \ right)}$${\ Displaystyle k}$${\ Displaystyle k + 1}$ ${\ Displaystyle \ left (x_ {i}, f_ {i} \ right), \ dotsc, \ left (x_ {j}, f_ {j} \ right)}$${\ Displaystyle k = ji}$

${\ Displaystyle {\ begin {alineado} p (f | x_ {i}) (x) & = f_ {i}, \\ p \ left (f | x_ {i}, \ dotsc, x_ {j} \ right ) (x) & = {\ frac {\ left (x-x_ {i} \ right) p \ left (f | x_ {i + 1}, \ dotsc, x_ {j} \ right) (x) - \ izquierda (x-x_ {j} \ derecha) p \ izquierda (f | x_ {i}, \ dotsc, x_ {j-1} \ derecha) (x)} {x_ {j} -x_ {i}}} . \ end {alineado}}}$

Se puede probar sustituyendo , lo que verifica que el lado derecho de la ecuación satisface la condición de interpolación. La unicidad del polinomio de interpolación proporciona la afirmación. ${\ Displaystyle x_ {i}, \ ldots, x_ {j}}$

Según la fórmula de recursividad de Aitken, el coeficiente inequívoco de a la potencia es la diferencia entre los coeficientes de y a dividido por . Esto muestra que los elementos diagonales en el esquema de las diferencias divididas dan exactamente los coeficientes del polinomio de interpolación según el enfoque de Newton. ${\ Displaystyle p \ left (f | x_ {i}, \ dotsc, x_ {j} \ right)}$${\ Displaystyle x ^ {ji}}$${\ Displaystyle p \ left (f | x_ {i + 1}, \ dotsc, x_ {j} \ right)}$${\ Displaystyle p \ left (f | x_ {i}, \ dotsc, x_ {j-1} \ right)}$${\ Displaystyle x ^ {ji-1}}$${\ Displaystyle x_ {j} -x_ {i}}$${\ Displaystyle [x_ {0}, \ ldots, x_ {j}] f}$${\ Displaystyle c_ {j}}$${\ Displaystyle P}$

Con el esquema de Neville, la evaluación de un lugar también se puede hacer de forma recursiva: ${\ Displaystyle p \ left (f | x_ {0}, \ dotsc, x_ {n} \ right) (x) = P (x)}$${\ Displaystyle x}$

${\ displaystyle {\ begin {array} {crcrccrcrc} p (f | x_ {0}) \\ & \ Searrow \\ p (f | x_ {1}) & \ rightarrow & p (f | x_ {0}, x_ {1}) \\ & \ línea de búsqueda && \ línea de búsqueda \\ p (f | x_ {2}) & \ flecha derecha & p (f | x_ {1}, x_ {2}) & \ flecha derecha & p (f | x_ {0}, x_ {1}, x_ {2}) \\\ vdots && \ vdots && \ vdots & \ ddots \\ & \ Searrow && \ Searrow &&& \ Searrow \\ p (f | x_ {n-1 }) & \ rightarrow & p (f | x_ {n-2}, x_ {n-1}) & \ rightarrow & p (f | x_ {n-3}, x_ {n-2}, x_ {n- 1}) & \ cdots & \ rightarrow & p (f | x_ {0}, \ dotsc, x_ {n-1}) \\ & \ Searrow && \ Searrow &&& \ Searrow && \ Searrow \\ p (f | x_ {n}) & \ rightarrow & p (f | x_ {n-1}, x_ {n}) & \ rightarrow & p (f | x_ {n-2}, x_ {n-1}, x_ {n} ) & \ cdots & \ rightarrow & p (f | x_ {1}, \ dotsc, x_ {n}) & \ rightarrow & p (f | x_ {0}, \ dotsc, x_ {n}) \ end {matriz }}}$

Comparación de los métodos de solución

Si desea determinar todos los coeficientes del polinomio de interpolación , el algoritmo de Newton ofrece la menor cantidad de esfuerzo requerido para esto . El polinomio determinado de esta manera se puede evaluar con operaciones en un punto. Esta es la razón por la que el algoritmo de Newton es muy adecuado cuando el polinomio de interpolación debe evaluarse en muchos lugares. También se pueden agregar puntos de soporte adicionales de manera eficiente. Sin embargo, si los puntos de soporte o los valores de soporte están demasiado cerca unos de otros, existe el riesgo de que se eliminen al determinar las diferencias divididas. ${\ Displaystyle P}$${\ Displaystyle {\ mathcal {O}} \ left (n ^ {2} \ right)}$${\ Displaystyle {\ mathcal {O}} (n)}$

El algoritmo de Neville-Aitken, por otro lado, es muy adecuado cuando un polinomio de interpolación solo debe evaluarse en muy pocos lugares y es menos susceptible de cancelación. También se pueden agregar nuevos puntos de soporte de manera eficiente en el algoritmo Neville-Aitken. Entonces z. B. se puede lograr la precisión deseada de la interpolación en un punto agregando más y más puntos de interpolación.

Ejemplo: interpolación de la función tangente

Función tangente (azul) y su interpolante polinomial de tercer grado (rojo)

Interpolar la función en puntos dados ${\ Displaystyle f (x) = \ tan (x)}$

${\ Displaystyle x_ {0} = - 1 {,} 5}$	${\ displaystyle f (x_ {0}) = - 14 {,} 101420}$
${\ Displaystyle x_ {1} = - 0 {,} 75}$	${\ displaystyle f (x_ {1}) = - 0 {,} 931596}$
${\ Displaystyle x_ {2} = 0}$	${\ Displaystyle f (x_ {2}) = 0}$
${\ Displaystyle x_ {3} = 0 {,} 75}$	${\ displaystyle f (x_ {3}) = 0 {,} 931596}$
${\ Displaystyle x_ {4} = 1 {,} 5}$	${\ Displaystyle f (x_ {4}) = 14 {,} 101420}$

Solución con Lagrange

Las funciones base de Lagrange son

${\ Displaystyle {\ begin {alineado} \ ell _ {0} (x) & = {x-x_ {1} \ over x_ {0} -x_ {1}} \ cdot {x-x_ {2} \ over x_ {0} -x_ {2}} \ cdot {x-x_ {3} \ over x_ {0} -x_ {3}} \ cdot {x-x_ {4} \ over x_ {0} -x_ {4 }} = {1 \ over 243} x (2x-3) (4x-3) (4x + 3) \\\ ell _ {1} (x) & = {x-x_ {0} \ over x_ {1 } -x_ {0}} \ cdot {x-x_ {2} \ over x_ {1} -x_ {2}} \ cdot {x-x_ {3} \ over x_ {1} -x_ {3}} \ cdot {x-x_ {4} \ over x_ {1} -x_ {4}} = - {8 \ over 243} x (2x-3) (2x + 3) (4x-3) \\\ ell _ { 2} (x) & = {x-x_ {0} \ over x_ {2} -x_ {0}} \ cdot {x-x_ {1} \ over x_ {2} -x_ {1}} \ cdot { x-x_ {3} \ over x_ {2} -x_ {3}} \ cdot {x-x_ {4} \ over x_ {2} -x_ {4}} = {3 \ over 243} (2x + 3 ) (4x + 3) (4x-3) (2x-3) \\\ ell _ {3} (x) & = {x-x_ {0} \ over x_ {3} -x_ {0}} \ cdot {x-x_ {1} \ over x_ {3} -x_ {1}} \ cdot {x-x_ {2} \ over x_ {3} -x_ {2}} \ cdot {x-x_ {4} \ sobre x_ {3} -x_ {4}} = - {8 \ sobre 243} x (2x-3) (2x + 3) (4x + 3) \\\ ell _ {4} (x) & = {x -x_ {0} \ over x_ {4} -x_ {0}} \ cdot {x-x_ {1} \ over x_ {4} -x_ {1}} \ cdot {x-x_ {2} \ over x_ {4} -x_ {2}} \ cdot {x-x_ {3} \ over x_ {4} -x_ {3}} = {1 \ over 243} x (2x + 3) (4x-3) (4x +3) \ end {alineado}}}$

también lo es el polinomio de interpolación

${\ displaystyle {\ begin {alineado} P _ {\ text {Lagrange}} (x) = & {\ tfrac {1} {243}} {\ big (} f (x_ {0}) x (2x-3 ) (4x-3) (4x + 3) \\ & \ qquad {} -8f (x_ {1}) x (2x-3) (2x + 3) (4x-3) \\ & \ qquad {} + 3f (x_ {2}) (2x + 3) (4x + 3) (4x-3) (2x-3) \\ & \ qquad {} -8f (x_ {3}) x (2x-3) (2x + 3) (4x + 3) \\ & \ qquad {} + f (x_ {4}) x (2x + 3) (4x-3) (4x + 3) {\ big)} \\ = & - 1 {,} 477474x + 4 {,} 834848x ^ {3} \ end {alineado}}}$

Solución con Newtons

Las diferencias divididas están aquí

${\ displaystyle {\ begin {array} {rrrrrr} x_ {i} & f \ left (x_ {i} \ right) &&&& \\ - 1 {,} 50 & -14 {,} 10140 &&&& \\ &&&&& \\ - 0 {,} 75 & -0 {,} 931596 & {- 0 {,} 931596 - (- 14 {,} 1014) \ over -0 {,} 75 - (- 1 {,} 5)} = 17 {,} 5597 &&& \ \ &&&&& \\ 0 {,} 00 & 0 {,} 00000 & {0 - (- 0 {,} 931596) \ over 0 - (- 0 {,} 75)} = 1 {, } 24213 & {1 {,} 24213-17 {,} 5597 \ over 0 - (- 1 {,} 5)} = - 10 {,} 8784 && \\ &&&&& \\ 0 {,} 75 & 0 {, } 931596 & {0 {,} 931596-0 \ over 0 {,} 75-0} = 1 {,} 24213 & {1 {,} 24213-1 {,} 24213 \ over 0 {,} 75 - (- 0 {,} 75)} = 0 {,} 00000 & {0 - (- 10 {,} 8784) \ over 0 {,} 75 - (- 1 {,} 5)} = 4 {,} 83484 & \ \ &&&&& \\ 1 {,} 50 & 14 {,} 10140 & {14 {,} 10140-0 {,} 931596 \ over 1 {,} 5-0 {,} 75} = 17 {,} 5597 & { 17 {,} 5597-1 {,} 24213 \ over 1 {,} 5-0} = 10 {,} 8784 & {10 {,} 8784-0 \ over 1 {,} 5 - (- 0 {,} 75)} = 4 {,} 83484 & {4 {,} 83484-4 {,} 83484 \ over 1 {,} 5 - (- 1 {,} 5)} = 0 \\\ end {array}}}$

y es el polinomio de interpolación

${\ displaystyle {\ begin {alineado} P _ {\ text {Newton}} (x) = & - 14 {,} 1014 + 17 {,} 5597 (x + 1 {,} 5) -10 {,} 8784 (x + 1 {,} 5) (x + 0 {,} 75) \\ & {} + 4 {,} 83484 (x + 1 {,} 5) (x + 0 {,} 75) x + 0 (x + 1 {,} 5) (x + 0 {,} 75) x (x-0 {,} 75) \\ = & - 0 {,} 00005-1 {,} 4775x-0 {,} 00001x ^ {2} +4 {,} 83484x ^ {3} \ end {alineado}}}$

Si utiliza valores iniciales más precisos , el primer y tercer coeficientes desaparecen. ${\ Displaystyle f \ left (x_ {i} \ right)}$

Calidad de interpolación

Estimación de errores

Se da una función cuyos valores de función están interpolados en los puntos por el polinomio . El intervalo más pequeño que contiene los puntos de interpolación y un punto se indica con . Además, permita que ( ) tiempos sean continuamente diferenciables . Entonces existe uno para el que se aplica lo siguiente: ${\ Displaystyle f}$${\ Displaystyle n + 1}$${\ Displaystyle f_ {i}}$${\ Displaystyle x_ {i}}$${\ Displaystyle P}$${\ Displaystyle I}$${\ Displaystyle x_ {i}}$${\ Displaystyle x}$${\ Displaystyle f}$${\ Displaystyle n + 1}$${\ Displaystyle I}$${\ Displaystyle \ xi \ in I}$

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

En particular, con respecto a la norma máxima, tenemos en y con : ${\ Displaystyle [a, b]}$${\ Displaystyle w_ {n} (x) = \ prod _ {i = 0} ^ {n} (x-x_ {i})}$

${\ Displaystyle | f (x) -P (x) | \ leq {\ frac {\ | f ^ {(n + 1)} \ | _ {\ infty}} {(n + 1)!}} \ prod _ {i = 0} ^ {n} | x-x_ {i} | \ leq {\ frac {\ | f ^ {(n + 1)} \ | _ {\ infty}} {(n + 1)! }} \ | w_ {n} \ | _ {\ infty}}$

Optimización de errores según Chebyshev

Para n mayor , los puntos de Chebyshev se agrupan en los bordes del intervalo.

Por tanto, el error depende de una derivación de y del producto , es decir, los puntos de apoyo . A veces se encuentra en la posición de poder elegir los puntos de apoyo usted mismo; por ejemplo, al realizar un experimento físico, o con algunos métodos para la solución numérica de ecuaciones diferenciales . En este caso, la pregunta interesante es para qué puntos de apoyo la norma máxima es mínima. ${\ Displaystyle f}$${\ Displaystyle w_ {n} (x): = \ prod _ {i = 0} ^ {n} (x-x_ {i})}$${\ Displaystyle x_ {i}}$${\ Displaystyle \ | w_ {n} \ | _ {\ infty}}$

Los puntos de apoyo normalmente estandarizados se consideran normalmente para una prueba.

${\ Displaystyle {\ begin {alineado} w_ {n}: [- 1,1] \ rightarrow \ mathbb {R}, \ w_ {n} (x) = \ prod _ {i = 0} ^ {n} ( x-x_ {i}) \\ {\ text {con}} \ qquad \ forall \, i = 0, \ ldots, n: \ quad x_ {i} \ in [-1,1] \ ,. \ end {alineado}}}$

Ahora se puede estimar la norma máxima de la función de la siguiente manera ${\ Displaystyle w_ {n}}$

${\ Displaystyle \ | w_ {n} \ | _ {[- 1,1], \ infty} = \ max _ {x \ in [-1,1]} | w_ {n} (x) | \ geq 2 ^ {- n} \,.}$

Chebyshev ha demostrado que los ceros de los polinomios de Chebyshev ("puntos de Chebyshev") son puntos de apoyo óptimos. Los polinomios tienen ceros para . Los puntos de apoyo seleccionados de esta manera proporcionan un límite agudo a la estimación superior ${\ Displaystyle T_ {n + 1} (x) = \ cos ((n + 1) \ arccos (x))}$${\ Displaystyle t_ {k} = \ cos \ left ({\ frac {2k + 1} {2n + 2}} \ pi \ right)}$${\ Displaystyle k \ in \ {0,1, \ ldots, n \}}$

${\ Displaystyle \ | w_ {n} \ | _ {[- 1,1], \ infty} = 2 ^ {- n} \,.}$

Esta declaración se puede utilizar con la transformación

${\ displaystyle {\ begin {alineado} \ xi \ in [-1,1] & \ rightsquigarrow x = {\ frac {a + b} {2}} + {\ frac {ba} {2}} \ xi & \ in [a, b] \\ x \ in [a, b] & \ rightsquigarrow \ xi = {\ frac {2x-ab} {ba}} & \ in [-1,1] \ end {alineado}} }$

en el caso de un intervalo general . La prueba también proporciona la estimación ${\ Displaystyle [a, b] \ subconjunto \ mathbb {R}}$

${\ Displaystyle {\ begin {alineado} \ | w_ {n} \ | _ {[a, b], \ infty} = \ max _ {x \ in [a, b]} | w_ {n} (x) | = 2 \ left ({\ frac {ba} {4}} \ right) ^ {n + 1}. \ End {alineado}}}$

Interpolación polinomial de 6 puntos de interpolación equidistantes (puntos rojos) que se encuentran en la función de Runge (azul)

Lo mismo con 11 puntos de apoyo.

Fenómeno de Runge

¿Mejora la calidad de la interpolación cuando se agregan más puntos de interpolación? Generalmente no: Con puntos de apoyo equidistantes y un alto grado de polinomio, puede suceder que la función polinomial apenas se parezca a la función a interpolar, lo que también se conoce como fenómeno de Runge . En el caso límite, los polinomios tienden hacia . Si la función a interpolar se comporta de manera diferente, por ejemplo de forma periódica o asintóticamente constante, se producen fuertes oscilaciones cerca de los límites del intervalo. Las interpolaciones de polinomios en todo el intervalo son relativamente inadecuadas para tales funciones. ${\ Displaystyle x \ to \ pm \ infty}$${\ Displaystyle \ pm \ infty}$

Los puntos de interpolación de Chebyshev, que están más cerca de los límites del intervalo, pueden reducir el error general de la interpolación, pero se recomienda un cambio en el método de interpolación, por ejemplo, para la interpolación spline . Runge dio un ejemplo de este fenómeno, la función de Runge que lleva su nombre:

${\ Displaystyle f (x) = {\ frac {1} {1 + x ^ {2}}} \ ,, \ quad x \ in [-5; 5]}$

Comportamiento de convergencia

Sin embargo, existen condiciones bajo las cuales la calidad de la interpolación mejora con un número creciente de puntos de interpolación: Cuando la cuadrícula de puntos de interpolación se vuelve cada vez más "fina" y se interpola una función analítica . Más precisamente: sea una función analítica en el intervalo . Para una división de intervalo ${\ Displaystyle f}$${\ Displaystyle I = [a, b] \ subconjunto \ mathbb {R}}$

${\ Displaystyle \ Delta _ {m} = \ {a = x_ {0} ^ {(m)} <x_ {1} ^ {(m)} <\ dotsb <x_ {n_ {m}} ^ {(m )} = b \}, \ qquad m \ in \ mathbb {N}}$

deja que su norma se defina por

${\ Displaystyle \ | \ Delta _ {m} \ | = \ max _ {i} | x_ {i + 1} ^ {(m)} - x_ {i} ^ {(m)} |.}$

Para cada división de intervalo hay un polinomio claramente definido que se interpola en los puntos de interpolación . Si se cumple para una secuencia de divisiones de intervalo , entonces sigue de manera uniforme . ${\ Displaystyle \ Delta _ {m}}$${\ Displaystyle P _ {\ Delta _ {m}}}$${\ Displaystyle f}$${\ Displaystyle \ Delta _ {m}}$${\ Displaystyle \ | \ Delta _ {m} \ | \ rightarrow 0}$${\ Displaystyle P _ {\ Delta _ {m}} \ rightarrow f}$

Sin embargo, para cada secuencia también se puede encontrar una función que sea continua , de modo que no converja uniformemente al (teorema de Faber ). ${\ Displaystyle \ {\ Delta _ {m} \} _ {m \ in \ mathbb {N}}}$${\ Displaystyle I}$${\ Displaystyle f}$${\ Displaystyle \ {P _ {\ Delta _ {m}} \} _ {m \ in \ mathbb {N}}}$ ${\ Displaystyle f}$

Mejor aproximación

La relación entre el polinomio de interpolación y el polinomio que mejor aproxima la función con respecto a la norma máxima se da de la siguiente manera: ${\ Displaystyle \ | \ cdot \ | _ {\ max}}$

Dejemos que se den los siguientes objetos

• una función continua para aproximarse: ${\ Displaystyle f \ en C ([a, b])}$
• Puntos de apoyo: ${\ Displaystyle x_ {0}, \ ldots, x_ {n} \ in [a, b]}$
• Constante de Lebesgue :${\ Displaystyle \ Lambda _ {n}}$
• Polinomio de interpolación: con${\ Displaystyle P \ en P_ {n}}$${\ Displaystyle P (x_ {i}) = f (x_ {i})}$
• Mejor aproximación: con .${\ Displaystyle Q \ en P_ {n}}$${\ Displaystyle \ | fQ \ | _ {\ max} = \ min _ {R \ in P_ {n}} \ | fR \ | _ {\ max}}$

Entonces se aplica la estimación

${\ Displaystyle \ | fP \ | _ {\ max} = (1+ \ Lambda _ {n}) \ | fQ \ | _ {\ max} \,.}$

generalización

Hasta ahora, se suponía que los puntos de apoyo del polinomio de interpolación eran diferentes en pares. Este no es el caso de la interpolación de Hermit . No solo los valores de la función, sino también los valores de las derivadas del polinomio de interpolación se especifican en múltiples puntos de interpolación. ${\ Displaystyle x_ {i}}$${\ Displaystyle P}$

Constante de Lebesgue

Deje que el operador que asigna su polinomio de interpolación a una función sea definido por ${\ Displaystyle f}$${\ Displaystyle P (f)}$

${\ Displaystyle \ phi _ {n} \ dos puntos C ([a, b]) \ flecha derecha P_ {n} \ ,, \, f \ mapsto P (f) = \ sum _ {i = 0} ^ {n} f (x_ {i}) l_ {i} \ ,,}$

donde el -ésimo es Lagrange polinomio . ${\ Displaystyle l_ {i}}$${\ Displaystyle i}$

Como la constante de Lebesgue es la norma del operador designado. Para esto, se necesita un estándar y, a menudo, aquí se accede a la norma máxima.${\ Displaystyle \ Lambda _ {n}}$${\ Displaystyle \ phi _ {n}}$ ${\ Displaystyle \ | \ cdot \ | _ {\ max}}$

${\ Displaystyle \ Lambda _ {n}: = \ | \ phi _ {n} \ | _ {\ max} \,.}$

La norma se puede evaluar explícitamente

${\ Displaystyle \ Lambda _ {n} = \ max _ {x \ in [a, b]} \ sum _ {i = 0} ^ {n} | L_ {i} (x) | \,.}$

literatura

• Hans R. Schwarz, Norbert Köckler: Matemáticas numéricas . 5a edición Teubner, Stuttgart 2004, ISBN 3-519-42960-8

• Stoer, Bulirsch: Matemáticas numéricas 1 . 10ª edición. Springer Verlag, Berlín, Heidelberg, Nueva York 2007, ISBN 978-3-540-45389-5 , 2.1 Interpolación por polinomios, págs. 39–57 (Cubre los métodos de Lagrange, Neville-Aitken y Newton, la interpolación de Hermite y la estimación de errores, cada uno con ejemplos y evidencia). 
• Press, Teukolsky, Vetterling, Flannery: Recetas numéricas . El arte de la informática científica. 3ª Edición. Cambridge University Press, Cambridge 2007, ISBN 978-0-521-88407-5 , 3.2 Interpolación y extrapolación de polinomios, págs. 118-120 (algoritmo Neville-Aitken con implementación C ++). 
• Carl Runge: Sobre funciones empíricas y la interpolación entre ordenadas equidistantes . En: Revista de Matemáticas y Física . cinta 46 . BG Teubner, Leipzig 1901, pág. 224-243 ( hdl: 1908/2014 - Fenómeno de Runge). 

enlaces web

• Página de Newton, Lagrange y Cubic Spline con subprograma Java
• Explicaciones y ejemplos para la interpolación de Lagrange

Evidencia individual

1. ↑ Martin J. Marsden: Una identidad para funciones de spline con aplicaciones a la aproximación de spline de disminución de variación . En: Journal of Approximation Theory , 3, 1970, págs. 7-49.
2. ↑ Jochen Werner: 10 de abril . En: Matemáticas numéricas , 1ª edición, Vieweg Studium, Nr . 32 , Vieweg Verlagsgesellschaft, 1992, ISBN 3-528-07232-6 . - 4.1.3. (PDF; 11,7 MB) sam.math.ethz.ch
3. ^ Andrei Nikolajewitsch Kolmogorow y col.: 4 . En: Matemáticas del siglo XIX , primera edición, Birkhäuser, 1998, ISBN 3-7643-5845-9 . - books.google.de