¿Cómo crear fácilmente una función polinómica que dé el resultado deseado?

Question

Busco un fácil manera (fórmula o algoritmo) de crear un polinomio que da la salida preestablecida arbitraria para los primeros valores de x. Por ejemplo, la salida deseada puede ser $y = 1, 2, 3, 4, 5, 6, 100$ para $x = 1, 2, 3, 4, 5, 6, 7$ . Puedo crear una de las muchas funciones a mano como:

$y = x + (x-1)(x-2)(x-3)(x-4)(x-5)(x-6)\cdot \frac{93}{720}.$

Pero para otros resultados deseados es realmente laborioso. Por ejemplo, estoy trabajando ahora con la salida deseada $y = 2, 10, 12, 16, 17, 18, 19, 200, 300$ cuando $x = 1, 2, 3, 4, 5, 6, 7, 8, 9$ .

Notas:

$x$ es siempre un número natural positivo ( $x > 0$ ). No importa lo que ocurra para otros valores de $x$ (mayores que los indicados).
- Busco un fácil manera, ya que no sé / no tengo / no tengo experiencia con software relacionado con las matemáticas.
- También para una función polinómica (o similar sencilla), ya que mi formación matemática es bastante limitada, por lo que no conozco funciones gamma, delta u otras, series, etc.
- Esta búsqueda es simplemente por recreación, para mostrar a los amigos cómo hay diferentes soluciones a los problemas del tipo: "Encuentra el siguiente término en esta sucesión"

Answer 1

Los polinomios en la forma estándar (como suma de monomios) son en realidad el tipo de "codificación" "incorrecto" para hacer interpolación. Este puesto explica cómo muy eficazmente interpolar cualquier función polinómica, ¡sin calcular nunca los coeficientes del polinomio! En resumen, podemos expresar fácilmente cualquier secuencia polinómica dada como una serie de Newton calculando las sucesivas diferencias hacia delante de la secuencia dada, y no sólo podemos utilizar esto para calcular eficientemente los términos subsiguientes de la secuencia, sino que también podemos convertir rápidamente esta representación de nuevo a la forma polinómica estándar, de la misma manera que el post enlazado demuestra para la suma de los primeros $n$ cubos perfectos.

Para tu ejemplo, las diferencias hacia delante iteradas se calculan fácilmente a mano:

 1,  2,  3,  4,  5,  6,100,659,...
 1,  1,  1,  1,  1, 94,559,...
 0,  0,  0,  0, 93,465,...
 0,  0,  0, 93,372,...
 0,  0, 93,279,...
 0, 93,186,...
93, 93,...

Lo que también significa que puede utilice esta técnica de diferencia hacia delante (que funciona para cualquier secuencia polinómica como $1,4,9,16,25,\cdots$ ) a justifique que se puede extender polinómicamente cualquier secuencia dada como un modelo razonable .

Dicho esto, si se dan muy pocos términos de una secuencia (lo que suele ocurrir), en realidad es más fácil describirla simplemente como una lista sin patrón, porque el patrón pretendido tendría una descripción más larga que la simple enumeración de los pocos términos dados.

Answer 2

Como se menciona en un comentario, la clave es la "interpolación de Lagrange". (Véase, por ejemplo, Wikipedia o MathWorld .) La descripción formal puede resultar un poco opaca, pero en realidad la idea es bastante sencilla: Construir un polinomio a partir de partes, la mayoría de las cuales desaparecen con cada entrada, y luego hacer que la parte restante haga lo que tiene que hacer.

Por ejemplo, supongamos que desea tres entradas (distintas) $a$ , $b$ , $c$ para dar las tres salidas $p$ , $q$ , $r$ . Lagrange afirma que el polinomio deseado tiene la forma

$$h(x-b)(x-c) \;+\; j(x-c)(x-a) \;+\; k(x-a)(x-b) \tag{$ \estrella $}$$

donde $h$ , $j$ , $k$ son algunas constantes aún por determinar.

En $x=a$ dos términos de $(\star)$ desaparecen, dejando $h(a-b)(a-c)$ ; igualmente, $x=b$ produce $j(b-c)(b-a)$ mientras que $x=c$ produce $k(c-a)(c-b)$ . Por lo tanto, sólo tiene que elegir $h$ , $j$ , $k$ para obtener los resultados deseados:

$$\begin{align} h(a-b)(a-c) = p \qquad\to\qquad h = \frac{p}{(a-b)(a-c)} \\[4pt] j(b-c)(b-a) = q \qquad\to\qquad \,j = \frac{q}{(b-c)(b-a)} \\[4pt] k(c-a)(c-b) = r \qquad\to\qquad k = \frac{r}{(c-a)(c-b)} \end{align}$$

Así, podemos reescribir $(\star)$ informalmente como $\require{cancel}$ $$p\;\frac{\cancel{(x-a)}(x-b)(x-c)}{\cancel{(a-a)}(a-b)(a-c)} \;+\;q\;\frac{(x-a)\cancel{(x-b)}(x-c)}{(b-a)\cancel{(b-b)}(b-c)} \;+\;r\;\frac{(x-a)(x-b)\cancel{(x-c)}}{(c-a)(c-b)\cancel{(c-c)}} \tag{$ \star\star $}$$

Evidentemente, este tipo de cosas puede ampliarse a cualquier número de entradas y salidas.

Answer 3

Como comentó Gabriel Romon: La interpolación de Lagrange hace el truco.

Los polinomios forman un espacio vectorial (que funciona de forma muy similar al espacio de coordenadas 3D) en el que los coeficientes funcionan como coordenadas y los monomios como $x^0=1$ como base estándar ortogonal. Los polinomios de Lagrange forman otra. Se construyen a partir de los puntos de muestreo dados ( $x$ -valores). Lo bueno es que cada polinomio de Lagrange es cero en todos los puntos de muestreo menos en uno. Y en este punto de muestreo tiene el valor $1$ . Así que puede multiplicar cada uno de los polinomios de Lagrange con el valor de la función en el punto de muestreo donde tiene un valor distinto de cero y sumar sobre todos estos polinomios.

Esto parece tan fácil como $$ y = \sum_{i=1}^n y_i \cdot \ell_i(x). $$ Como puede ver, no hay $x_i$ en esta fórmula. Esto permite precalcular los polinomios de Lagrange $\ell_i$ y resolver todos sus problemas juntos en un segundo paso, siempre que todas las funciones se definan utilizando los mismos puntos de muestreo.

Answer 4

De manera similar a user21820, puede tomar diferencias sucesivas, así que con su $y = 2, 10, 12, 16, 17, 18, 19, 200, 300$ se obtendría algo así

2   10  12  16   17 18   19 200   300   
     8   2   4    1  1    1 181   100   
        -6   2   -3  0    0 180   -81   
             8   -5  3    0 180  -261   
                -13  8   -3 180  -441   
                    21  -11 183  -621   
                        -32 194  -804   
                            226  -998   
                                -1224   

y si se asume que el $-1224$ continúa a lo largo de la secuencia se podría extrapolar para obtener algo como esto:

2   10  12  16   17 18   19 200   300   -4030   -31346  -135672 -444797
     8   2   4    1  1    1 181   100   -4330   -27316  -104326 -309125
        -6   2   -3  0    0 180   -81   -4430   -22986   -77010 -204799
             8   -5  3    0 180  -261   -4349   -18556   -54024 -127789
                -13  8   -3 180  -441   -4088   -14207   -35468  -73765
                    21  -11 183  -621   -3647   -10119   -21261  -38297
                        -32 194  -804   -3026    -6472   -11142  -17036
                            226  -998   -2222    -3446    -4670   -5894
                                -1224   -1224    -1224    -1224   -1224

sugiriendo que las próximas legislaturas podrían ser $-4030,-31346,-135672,-444797$ (que parece ligeramente inverosímil con la drástica caída a valores negativos, y este comportamiento incontrolado es la razón por la que la extrapolación polinómica se considera generalmente peligrosa).

Esto también apunta a encontrar el polinomio de menor grado que se ajuste a sus datos: existe un polinomio de octavo grado en el que el coeficiente de $x^8$ es $\frac{-1224}{8!} = \frac{-17}{560}$ . Así que si considera $y-\frac{-17}{560}x^8$ y volver a tomar las diferencias, entonces la última fila será cero y la penúltima fila $5734$ lo que sugiere que el coeficiente de $x^7$ es $\frac{5734}{7!}=\frac{2867}{2520}$ . Continúe así con $y-\left(\frac{-17}{560}x^8 + \frac{2867}{2520}x^7\right)$ y así sucesivamente, y se obtiene el polinomio de menor grado que se ajusta a los datos siendo

$y=-\frac{17 {{x}^{8}}}{560}+\frac{2867 {{x}^{7}}}{2520}-\frac{143 {{x}^{6}}}{8}+\frac{55169 {{x}^{5}}}{360}-\frac{187277 {{x}^{4}}}{240}+\frac{432067 {{x}^{3}}}{180}-\frac{362567 {{x}^{2}}}{84}+\frac{143421 x}{35}-1536$