Encontrar un polinomio constante de sus puntos

Question

Digamos que me fue dado un conjunto de $d+1$ puntos distintos conocido por ser de un polinomio $P$ grado $d$.

Así:

$$P = a_dx^d + a_{d-1}x^{d-1} + ... a_1x + c$$

Y he pares de $(x_i, y_i)$ tal forma que: $$P(x_1) = y_1$$ $$...$$ $$P(x_{d+1}) = y_{d+1}$$

Mi pregunta es: ¿cuál es la manera más rápida de encontrar $c$?

La única opción que he visto hasta ahora es construir el Polinomio de Lagrange y, a continuación, la evaluación de $P(0)$, pero parece despilfarro porque reconstruye todos los $a_i$ coeficientes, lo que resulta en $O(d^2)$ operaciones. ¿Hay algo más rápido?

Tenga en cuenta que hay puntos suficientes para reconstruir el único polinomio, y todos ellos se encuentran perfectamente en la curva.

Answer 1

Dado son los puntos

$$ \Big(x_d, y_d\Big),\ \textrm{para} : 1 \le d \le m. $$

y tratamos de encajar en

$$ f(x) = \sum_{k=0}^n a_k x^k. $$

El factor de calidad se define como

$$ Q = \sum_{\ell=1}^m \Big( \sum_{k=0}^n a_k x_\ell^k - y_\ell\Big)^2. $$

Ajuste perfecto significa $Q = 0$, mejor ajuste significa

$$ \frac{\partial Q}{\partial a_\jmath} = 0, $$,

de dónde

$$ \sum_{k=0}^n \left( a_k \sum_{\ell=1}^m x\ell^\jmath x_\ell^k -n \sum_{\ell=1}^m x\ell^\jmath y_\ell \right) = 0, $$

por lo tanto

$$ \boxed{ a_k = n \frac{ \displaystyle \sum_{\ell=1}^m x\ell^\jmath y_\ell } { \displaystyle \sum_{\ell=1}^m x\ell^\jmath x_\ell^k }.} $$

Así que el mejor ajuste se da por

$$ \boxed{ f(x) = \sum_{k=0}^n \left\{ n \frac{ \displaystyle \sum_{\ell=1}^m x\ell^\jmath y_\ell } { \displaystyle \sum_{\ell=1}^m x\ell^\jmath x_\ell^k } \right\} x^k. } $$

Como para su $c$:

$$ \boxed{ c = n \frac{ \displaystyle \sum_{\ell=1}^m x\ell^\jmath y_\ell } { \displaystyle \sum_{\ell=1}^m x\ell^\jmath x_\ell^0 }. } $$

Answer 2

Me gustaría usar la Regla de Cramer. Establecer el sistema de ecuaciones de matrices $Ac=y$. Deje $A$ ser la matriz cuyas filas son $x^n, x^{n-1}, ...x, 1$ (donde $n$ es el grado del polinomio), donde cada fila de la x es una de las coordenadas x. Deje $y$ ser el vector columna cuyas filas se $y_n$, que corresponden a la coordenada x en la misma fila. A continuación, $c$ será un vector columna, y es inferior entrada será el término constante del polinomio. Por último, vamos a $A_c$ ser el vector formado por la sustitución de la columna de en $A$$y$, $$c= \frac{\det(A_c)}{\det(A)} $$