Version corta:
El teorema de convolución establece que [mathcal \ mathcal F \ {f \ star g \} = \ mathcal F \ {f \} \ cdot \ mathcal F \ {g \} [/ math], y por lo tanto la convolución de [mathcal ] f [/ math] y [math] g [/ math] (básicamente equivalente a su producto polinomial) pueden realizarse multiplicando sus transformadas de Fourier por elementos y luego tomando la transformada inversa de Fourier del resultado.
Versión larga :
Digamos que tengo una línea, [matemáticas] p (x) = ax + b [/ matemáticas]. Una forma de almacenar la información para esta línea es simplemente codificando los coeficientes como la tupla [math] (a, b) [/ math]. Dados dos puntos distintos [matemática] (x_1, p (x_1)) [/ matemática] y [matemática] (x_2, p (x_2)) [/ matemática] en nuestra línea, podemos identificar de manera única la función [matemática] p ( x) [/ math] escribiendo la ecuación para la línea entre nuestros dos puntos. Por lo tanto, podríamos almacenar la línea simplemente registrando sus valores en [math] x_1 [/ math] y [math] x_2 [/ math].
- Cómo resolverlo y (x) ” = h / (y (x)) ^ 2 donde h es constante
- ¿Hay alguna prueba matemática de que es imposible encontrar una ecuación (algoritmo) para generar todos los números primos?
- Cómo resolver [matemáticas] \ log \ frac {7} {4} + \ log \ frac {8} {7} [/ matemáticas]
- ¿Cómo funciona la multiplicación de matrices para obtener el enésimo número de Fibonacci?
- ¿Cuántos algoritmos diferentes existen para resolver un sistema de ecuaciones?
Si ha tomado álgebra lineal, puede reconocer que nuestra recuperación de la línea [matemática] p (x) [/ matemática] de sus valores en dos puntos proviene del siguiente sistema de ecuaciones:
[matemáticas] \ begin {align *} & b + ax_1 = p (x_1) \\ & b + ax_2 = p (x_2) \ end {align *} [/ math]
De hecho, podemos generalizar esta idea preguntando: dado un polinomio [matemático] p (x) = a_nx ^ n + \ dots + a_1x + a_0 [/ matemático] de grado [matemático] n [/ matemático], ¿podemos determinar de manera única? los coeficientes de los valores de [matemática] p (x) [/ matemática] en [matemática] n + 1 [/ matemática] puntos distintos [matemática] x_1, x_2, \ puntos, x_ {n + 1} [/ matemática] ? Podemos establecer un sistema de ecuaciones de la siguiente manera:
[matemáticas] \ begin {align *} & a_0 + a_1x_1 + \ dots + a_nx_1 ^ n = p (x_1) \\ & \ vdots \\ & a_0 + a_1x_ {n + 1} + \ dots + a_nx_ {n + 1} ^ n = p (x_ {n + 1}) \ end {align *} [/ math]
Este sistema tiene una solución única si la matriz cuadrada
[matemáticas] \ begin {bmatrix} 1 & x_1 & \ dots & x_1 ^ n \\\ vdots & \ vdots & \ vdots & \ vdots \\ 1 & x_ {n + 1} & \ dots & x_ {n + 1} ^ n \ end {bmatrix} [/ math]
No es singular. De hecho, esta matriz es una matriz de Vandermonde y, por lo tanto, no es singular porque [math] x_1, \ dots, x_ {n + 1} [/ math] son todos distintos.
Bien, ahora sabemos que cada polinomio de grado [matemático] n [/ matemático] puede identificarse de manera única por sus valores en [matemático] n + 1 [/ matemático] puntos distintos. Lo que esto significa para la multiplicación polinómica es que, en lugar de trabajar con coeficientes, podemos trabajar con valores en estos puntos. Sea [matemático] f [/ matemático] un polinomio de grado [matemático] n [/ matemático], sea [matemático] g [/ matemático] sea un polinomio de grado [matemático] m [/ matemático], y elija [matemático ] n + m + 1 [/ math] puntos distintos [math] x_1, x_2, \ dots, x_ {n + m + 1} [/ math]. Entonces, como sabemos que [math] fg [/ math] tiene un grado [math] n + m [/ math], se puede identificar de forma única por sus valores en estos puntos. Esto nos lleva al siguiente procedimiento para multiplicar [matemáticas] f [/ matemáticas] y [matemáticas] g [/ matemáticas]:
- Evalúe [math] f [/ math] y [math] g [/ math] en [math] x_1, x_2, \ dots, x_ {n + m + 1} [/ math].
- Multiplique sus valores en estos puntos para obtener los valores de [math] fg [/ math], usando el hecho de que [math] (fg) (x_k) = f (x_k) g (x_k) [/ math].
- Realice la interpolación polinómica (a través del sistema de ecuaciones descrito anteriormente) para recuperar los coeficientes de [math] fg [/ math].
Consideremos el paso 1: evaluación polinómica. Queremos algún método que tome un conjunto de coeficientes polinómicos como entrada y salida de los valores del polinomio en los puntos [matemática] x_1, x_2, \ puntos, x_ {n + m + 1} [/ matemática]. De hecho, podemos representar esto como una multiplicación matricial:
[matemáticas] \ begin {bmatrix} 1 & x_1 & \ dots & x_1 ^ {n + m} \\\ vdots & \ vdots & \ vdots & \ vdots \\ 1 & x_ {n + m + 1} & \ dots & x_ {n + m + 1} ^ {n + m} \ end {bmatrix} \ begin {bmatrix} a_0 \\\ vdots \\ a_ {n + m} \ end {bmatrix} [/ math]
Aquí hay una sutileza: si [matemática] f [/ matemática] o [matemática] g [/ matemática] tienen un grado menor que [matemática] n + m [/ matemática], necesitamos rellenar con ceros para convertir ambos en grados [matemática] n + m [/ matemática] polinomios.
¿Qué tan rápido es esta multiplicación? Bueno, sin saber nada más, debería llevar [matemática] O (n ^ 2) [/ matemática] tiempo, pero aún tenemos la capacidad de elegir nuestros puntos [matemática] x_1, x_2, \ puntos, x_ {n + m + 1} [/ matemáticas]. De hecho, resulta que si elegimos las raíces de la unidad de grado [matemáticas] n + m + 1 [/ matemáticas], nuestra matriz (llamada matriz de Transformación de Fourier discreta) posee simetrías que nos permiten realizar la multiplicación en [ math] O (n \ log n) [/ math] mediante un algoritmo de divide y vencerás.
¿Recuerdas la matriz que discutimos antes cuando hablamos de la interpolación polinómica? Básicamente es lo mismo que nuestra matriz FFT, lo cual tiene sentido porque la interpolación es lo opuesto a la evaluación polinómica.
Expresado en el lenguaje de la transformación de Fourier, nuestro algoritmo es ahora el siguiente:
- Tome la transformada de Fourier de [matemáticas] f [/ matemáticas] y [matemáticas] g [/ matemáticas].
- Multiplique las entradas de los dos vectores del paso 1.
- Tome la transformada inversa de Fourier del resultado.
Resulta que la transformación inversa de Fourier es esencialmente otra transformación de Fourier, por lo que los pasos 1 y 3 se realizan en [matemáticas] O (n \ log n) [/ matemáticas], mientras que el paso 2 se realiza en [matemáticas] O (n )[/matemáticas]. Por lo tanto, este proceso nos permite realizar una multiplicación polinómica en [matemáticas] O (n \ log n) [/ matemáticas] en lugar de [matemáticas] O (n ^ 2) [/ matemáticas].