Encontrar N de grado del polinomio de N+1 puntos

Question

Recuerdo que en la escuela el aprendizaje de cómo saber si un conjunto de números pertenecían a una función cuadrática o no.

Number | first Difference | second difference
1  
         2  
3                           2  
         4  
7                           2  
         6  
13                          2  
         8  
21  

Desde la segunda diferencia de la columna era todo lo mismo, el conjunto de números que se dijo era de 2º orden. Este mismo método se trabajó con la tercera y la cuarta, etc. las diferencias también.

Esto me llevó a la conclusión de que para cualquier conjunto de números, eventualmente llegan a una diferencia de columna de un solo número. Que, por definición, significa que todos sean del mismo.

Esto significa que, dado cualquier conjunto de n+1 puntos, existe un polinomio de grado n que pasa a través de todos ellos? O lo hace sólo funcionan si los puntos de manera uniforme un aumento de valor de x (en este caso 1). Si es así, ¿cómo puedo construir un polinomio?

Answer 1

Lo hace! Y usted puede incluso hacer la declaración más fuerte que el polinomio es de grado en la mayoría de las $n$ (al igual que con cuadráticas).

Si has visto los sistemas de ecuaciones lineales, hay una manera fácil de ver por qué este es el caso. Supongamos que usted desea un polinomio $f(x) = a_0 + a_1 x + \ldots + a_n x^n$ tal que $f(x_0) = y_0$, $f(x_1) = y_1$, \ldots, $f(x_n) = y_n$ donde asumimos $x_i \neq x_j$ si $i \neq j$. Las ecuaciones $f(x_i) = y_i$ son realmente $n+1$ ecuaciones en $n+1$ variables desconocidas $a_0,\ldots,a_n$ (es decir, en los coeficientes de la incógnita polinomio $f(x)$):

\begin{align} a_0 + x_0 a_1 + \ldots + x_0^n a_n &= y_0 \\ &\vdots\\ a_0 + x_n a_1 + \ldots + x_n^n a_n &= y_n \end{align}

o en forma de matriz

$$ \begin{pmatrix} 1 & x_0 & \cdots & x_0^n\\ 1 & x_1 & \cdots & x_1^n\\ \vdots&&&\vdots\\ 1 & x_n & \cdots & x_n^n \end{pmatrix} \begin{pmatrix} a_0\\a_1\\\vdots\\a_n \end{pmatrix} = \begin{pmatrix} y_0\\y_1\\\vdots\\y_n\end{pmatrix}. $$

El $(n+1)\times(n+1)$ matriz de la izquierda se llama la matriz de Vandermonde de $x_0,\ldots,x_n$, y (con algo de trabajo) usted puede demostrar que su determinante es siempre igual a

$$ \prod_{0 \leq i < j \leq n}(x_j - x_i), $$

que es distinto de cero si $x_j \neq x_i$$j \neq i$, al igual que nosotros asumimos, por obvias razones de arriba. De ello se sigue que la matriz es invertible, y por lo tanto existe una solución para este sistema de ecuaciones:

$$ \begin{pmatrix} a_0\\a_1\\\vdots\\a_n \end{pmatrix} = \begin{pmatrix} 1 & x_0 & \cdots & x_0^n\\ 1 & x_1 & \cdots & x_1^n\\ \vdots&&&\vdots\\ 1 & x_n & \cdots & x_n^n \end{pmatrix}^{-1}\begin{pmatrix} y_0\\y_1\\\vdots\\y_n\end{pmatrix}. $$

Lo que es más, se nota que hemos probado algo más fuerte que lo que nos propusimos. No sólo existe un polinomio de grado $n$ o menos, el polinomio es único! Es decir,

Para cualquier conjunto de $n+1$$(x_i,y_i)$$x_i \neq x_j$$i \neq j$, existe un único polinomio $f$ de grado en la mayoría de las $n$ tal que $f(x_i) = y_i$ todos los $i$.

---

Si usted está interesado, la página de Wikipedia sobre el polinomio de interpolación de algoritmos proporciona mayor detalle técnico sobre lo que estos coeficientes el aspecto escrito de forma explícita y también cómo eficientemente algunos algoritmos pueden ser implementados. Esto incluye el llamado interpolación de Lagrange método, que se deriva de la solución anterior.