Tweet
(Quien quiera ir directo al problema concreto sin conocer los pormenores del contexto, puede bajar rápidamente hasta el subtítulo PROBLEMA)
Hace ya mucho que no frecuento el foro (al menos 2 años, lo que no deja de ser una pena) pero ante los problemas sé que por aquí suelen haber respuestas para casi todo.
Al grano. Estoy trabajando en un programa (en Fortran) que usa el método de interpolación de Lagrange, en concreto, aplicado al caso particular en que la función ortogonal es ni más ni menos que un polinomio de Legendre (al que debo buscar todos sus ceros), para calcular el valor de una integral definida.
Tengo una idea esquemática de cómo encarar el programa, y desde luego no espero el código explícito ya que el aprendizaje no tiene precio. Sin embargo, me hallo ante una encrucijada.
A nivel conceptual mi principal problema es encontrar una forma eficiente de buscar todos los ceros del polinomio de Legendre (de orden arbitrario N, que se pedirá por consola).
Había pensado que, ya que los polinomios de Legendre tienden a amontonar sus ceros cerca de los extremos (en mi caso, aplicado a una integral entre -1 y 1, ya que no supone pérdida de generalidad) podría definir un intervalo logarítmico o exponencial. Sin embargo, al estudiar los casos para N pequeño, he visto que realmente no hay una diferencia importante en el orden de magnitud de la separación entre los ceros "contiguos" de la función, y supongo que el comportamiento será "similar" para Ns mayores.
La manera final que hemos pensado (entre unos compañeros) es aplicar intervalos equiespaciados, contar cuando la función cambia de signo, guardar la información, y comprobar si el número de intervalos con cambio de signo es igual al número de ceros que debe tener el polinomio (es decir, el N fijado por consola). Si no se da el caso, se redirecciona al comienzo del programa para definir un intervalo (automáticamente) considerablemente más pequeño.
El objetivo de esto es obviamente encontrar todos y cada uno de los ceros del polinomio de Legendre de la forma más eficiente posible.
Véase que una vez localizados los intervalos donde la función cambia de signo (y tras haber corroborado que tenemos el mismo número de intervalos donde la función cambia de signo que de ceros) tan solo hay que aplicar un método concreto (Newton-Rhapson, bisección, métodos híbridos, etc) para encontrar la coordenada concreta que posee cada cero.
Mi pregunta es: ¿Conocéis (o se os ocurre) algún algorismo/procedimiento más eficiente que el que he propuesto? Tengo la sensación de que el mío usa hasta cierto punto la fuerza bruta (un poco como las bombas de Turing xD).
Gracias por la atención y un cordial saludo a todos (y felicidades por mantener la web tan activa pod).
PD1: Entiendo que no haya expuesto correctamente el problema y no se comprenda, es un follón explicarlo al tuntún en un puñado de líneas. Si alguien necesita que formule en otros términos la pregunta, adelante.
PD2: En teoría hay un cierto límite de entrega, pero al ser pura curiosidad no tengo prisa alguna. Si alguien quiere discutirlo y entretenerse iré visitando lo más asiduamente que pueda el foro con tal de poder mantener una discusión activa.
Hace ya mucho que no frecuento el foro (al menos 2 años, lo que no deja de ser una pena) pero ante los problemas sé que por aquí suelen haber respuestas para casi todo.
Al grano. Estoy trabajando en un programa (en Fortran) que usa el método de interpolación de Lagrange, en concreto, aplicado al caso particular en que la función ortogonal es ni más ni menos que un polinomio de Legendre (al que debo buscar todos sus ceros), para calcular el valor de una integral definida.
Tengo una idea esquemática de cómo encarar el programa, y desde luego no espero el código explícito ya que el aprendizaje no tiene precio. Sin embargo, me hallo ante una encrucijada.
PROBLEMA
A nivel conceptual mi principal problema es encontrar una forma eficiente de buscar todos los ceros del polinomio de Legendre (de orden arbitrario N, que se pedirá por consola).
Había pensado que, ya que los polinomios de Legendre tienden a amontonar sus ceros cerca de los extremos (en mi caso, aplicado a una integral entre -1 y 1, ya que no supone pérdida de generalidad) podría definir un intervalo logarítmico o exponencial. Sin embargo, al estudiar los casos para N pequeño, he visto que realmente no hay una diferencia importante en el orden de magnitud de la separación entre los ceros "contiguos" de la función, y supongo que el comportamiento será "similar" para Ns mayores.
La manera final que hemos pensado (entre unos compañeros) es aplicar intervalos equiespaciados, contar cuando la función cambia de signo, guardar la información, y comprobar si el número de intervalos con cambio de signo es igual al número de ceros que debe tener el polinomio (es decir, el N fijado por consola). Si no se da el caso, se redirecciona al comienzo del programa para definir un intervalo (automáticamente) considerablemente más pequeño.
El objetivo de esto es obviamente encontrar todos y cada uno de los ceros del polinomio de Legendre de la forma más eficiente posible.
Véase que una vez localizados los intervalos donde la función cambia de signo (y tras haber corroborado que tenemos el mismo número de intervalos donde la función cambia de signo que de ceros) tan solo hay que aplicar un método concreto (Newton-Rhapson, bisección, métodos híbridos, etc) para encontrar la coordenada concreta que posee cada cero.
Mi pregunta es: ¿Conocéis (o se os ocurre) algún algorismo/procedimiento más eficiente que el que he propuesto? Tengo la sensación de que el mío usa hasta cierto punto la fuerza bruta (un poco como las bombas de Turing xD).
Gracias por la atención y un cordial saludo a todos (y felicidades por mantener la web tan activa pod).
PD1: Entiendo que no haya expuesto correctamente el problema y no se comprenda, es un follón explicarlo al tuntún en un puñado de líneas. Si alguien necesita que formule en otros términos la pregunta, adelante.
PD2: En teoría hay un cierto límite de entrega, pero al ser pura curiosidad no tengo prisa alguna. Si alguien quiere discutirlo y entretenerse iré visitando lo más asiduamente que pueda el foro con tal de poder mantener una discusión activa.
Comentario