Los resultados del Reto Cien Dígitos-Cien-Dólares

Cumpliendo lo prometido, el profesor Lloyd Nick Trefethen, de Oxford University, publicó en la entrega de Julio/Agosto de 2002 de SIAM News su reporte sobre los resultados del reto Cien–Dígitos, Cien–Dólares al cual me referí en el matema ¿Trabaja usted en Matemática Aplicada? ¡Gánese 100 dólares!

La competencia, o "Decatlón Decimal" como la ha denominado el profesor Trefethen, constituyó otra muestra de aquello que en 1964 fue llamado, por Marshall Mac–Luhan, la aldea global. Cientos de personas de todo el mundo confrontaron sus ideas y métodos, encaminados a resolver los diez problemas del Reto, a través de la Red Mundial.

Como era de esperarse, los competidores hicieron gala de excelentes niveles de conocimiento, tecnología, talento y espíritu competitivo. Varios de los participantes mostraron tal grado de ingenio y creatividad que consiguieron sorprender gratamente al profesor Trefethen, especialista de prestigio internacional en el área del análisis numérico. Así, el producto de esta singular competencia quedará plasmado en una valiosa colección de ideas, métodos, técnicas, recursos computacionales y demás, para el provecho de los aficionados al análisis numérico.

Debió ser satisfactorio para el profesor Trefethen recibir semejante respuesta del mundo a su convocatoria. En mi opinión, merece una calurosa felicitación. Ojalá se lleven a cabo eventos similares en otras áreas de la Matemática en el futuro.

Lo que sigue es una traducción libre (con algo de edición) de gran parte del reporte del profesor Trefethen.

La aceptación del Reto

Desde el momento en que SIAM News anunció el Reto, la noticia se esparció como sucede hoy en día. La información al respecto incluida en el sitio web de SIAM y en el mío fue replicada en seis grupos de discusión en línea y en la revista Science. El tema llegó a las salas donde se toma el café, la gente se sintió involucrada y una avalancha de mensajes de correo atiborró mi casillero.

Participaron estudiantes de posgrado y pregrado, profesores universitarios, profesores de secundaria, matemáticos, físicos, empleados de industrias, y personas ya retiradas. Algunos compitieron individualmente, otros en parejas o ternas o equipos de hasta seis integrantes, número máximo permitido. En total 94 equipos de 25 países, incluidos USA, Alemania, Chile, Canadá, Sudáfrica, Finlandia, Eslovenia, Suiza, Holanda y Francia, participaron en la contienda.

Juzgué mal

En el anuncio de enero escribí: "Si alguien obtiene 50 dígitos en total, quedaré impresionado". Bueno, juzgué mal. Al final, junto a una gran cantidad de equipos de competidores que obtuvieron puntajes del orden de 20, 40 y 60 dígitos, ¡20 equipos obtuvieron puntaje perfecto de 100 dígitos! Después de ellos, cinco equipos obtuvieron un puntaje de 99, y seis equipos más obtuvieron entre 90 y 98.

Los ganadores

1	Peter Robinson	Quintessa, Ltd.	Inglaterra
2	J. Boersma J. K. M. Jansen F. H. Simons F. W. Steutel	Eindhoven University of Technology Eindhoven University of Technology Eindhoven University of Technology Eindhoven University of Technology	Holanda Holanda Holanda Holanda
3	Ruud van Damme Bernard Geurts Bert Jagers	University of Twente University of Twente University of Twente	Holanda Holanda Holanda
4	Gerhard Kirchner Alexander Ostermann Mechthild Thalhammer Peter Wagner	University of Innsbruck University of Innsbruck University of Innsbruck University of Innsbruck	Austria Austria Austria Austria
5	Gaston Gonnet Robert Israel	Eidgenössische Technische Hochschule (Zurich) University of British Columbia	Suiza Canada
6	Rolf Strebel Oscar Chinellato	Eidgenössische Technische Hochschule (Zurich) Eidgenössische Technische Hochschule (Zurich)	Suiza Suiza
7	Folkmar Bornemann	University of Munich	Alemania
8	Thomas Grund	Technical University of Chemnitz	Alemania
9	Gerd Kunert Ulf Kähler	Technical University of Chemnitz Technical University of Chemnitz	Alemania Alemania
10	Dirk Laurie	University of Stellenbosch	Sudáfrica
11	Carl Devore Toby Driscoll Eli Faulkner Jon Leighton Sven Reichard Lou Rossi	University of Delaware University of Delaware University of Delaware University of Delaware University of Delaware University of Delaware	USA USA USA USA USA USA
12	Marijke van Gans Brian Medley Bernard Beard	Christian Brothers University	Escocia Inglaterra USA
13	Martin Gander Felix Kwok Sebastien Loisel Nilima Nigam Paul Tupper	McGill University (Montreal) McGill University (Montreal) McGill University (Montreal) McGill University (Montreal) McGill University (Montreal)	Canada Canada Canada Canada Canada
14	Danny Kaplan Stan Wagon	Macalester College (St. Paul, Minnesota) Macalester College (St. Paul, Minnesota)	USA USA
15	Kim McInturff Peter S. Simon	Raytheon (California) Space Systems/Loral (California)	USA USA
16	Glenn Ierly Stefan Llewellyn Smith Robert Parker	University of California University of California University of California	USA USA USA
17	Eric Dussaud Chris Husband Hoang Nguyen Daniel Reynolds Christiaan Stolk	Rice University Rice University Rice University Rice University Rice University	USA USA USA USA USA
18	Jingfang Huang Michael Minion Michael Taylor	University of North Carolina University of North Carolina University of North Carolina	USA USA USA
19	Eddy van de Wetering	West Hartford (Connecticut)	USA
20	Paul Abbott Brett Champion Yifan Hu Daniel Lichtblau Michael Trott	University of Western Australia Wolfram Research, Inc. Wolfram Research, Inc. Wolfram Research, Inc. Wolfram Research, Inc.	Australia USA USA USA USA

En esta lista de competidores es notable la presencia de algunos prestigiosos especialistas. Gaston Gonnet, por ejemplo, es uno de los creadores de Maple. Por otra parte, Stan Wagon es un veterano de la solución de problemas. Dirige el sitio web llamado El Problema de la Semana (Problem of the Week) en Macalester y es coautor de un libro (Which Way Did the Bicycle Go?) que incluye algunos de estos problemas. Es interesante también la presencia del físico Eddy van de Wetering.

Trabajo individual y trabajo colectivo

Dirk Laurie fue uno de los cinco competidores que mostraron que un individuo sobresaliente, trabajando en forma individual, podía ser capaz de realizar completamente la tarea. Laurie es uno de los principales analistas numéricos de Sudáfrica.

Por otra parte, The Delaware Team (ganador número 11 en la tabla anterior) ejemplifica el trabajo de colaboración entre estudiantes y profesores de una universidad. Toby Driscoll y Lou Rossi son profesores asistentes. Sven Reichard y Carl Devore son estudiantes de posgrado y Eli Faulkner es un estudiante de pregrado; todos pertenecen al Departamento de Ciencias Matemáticas. Jonathan Leighton es un estudiante de educación continuada en ciencia de la computación.

The Compuserve SCIMATH Forum Team (ganador número 12) representa un tipo moderno de colaboración —los tres integrantes del equipo ¡nunca se han encontrado personalmente!—. Ellos son amigos a través de la Internet y participan regularmente en este grupo de matemática en línea. Marijke van Gans vive en la Isle of Bute en Escocia y aspira a ser estudiante de posgrado en el futuro. Brian Medly es profesor de matemáticas en una escuela secundaria en Wigan, Inglaterra. Bernard B. Beard es profesor asociado en Christian Brothers University en Memphis, Tennessee. Este trío notable intercambió ideas y archivos de computador durante meses hasta que estuvieron seguros de que habían logrado las diez respuestas correctas. Beard compiló los archivos en un documento de 55 páginas, en formato PDF, documento rebosante de entusiasmo, creatividad y algunas bellas ilustraciones.

Software, técnicas y métodos

Los participantes resolvieron los problemas utilizando toda clase de métodos implementados en Mathematica, Matlab, Maple, C/C++, Fortran y, ocasionalmente, en PARI, Visual Basic, UBASIC, Octave, Java, Pascal o GSL. (Uno de los competidores utilizó Excel pero no estuvo entre los puntajes altos.) Algunos de los participantes son matemáticos de fama mundial y se inclinaron por técnicas de solución avanzadas. Otros, académicos con diversos niveles de formación, incluidos estudiantes y aficionados, tendieron a inventar sus propias técnicas.

Hay un patrón de trabajo que funciona para estos problemas. Se puede resolver casi cualquier problema, con hasta dos o tres dígitos de precisión, mediante algún método basado en fuerza bruta. La mayoría de nosotros comienza de este modo. Para obtener más dígitos se requiere más ingenio y en muchos casos pueden obtenerse mediante alguna clase de extrapolación. Por este camino pueden obtenerse 10 dígitos —y una vez se han obtenido 10 dígitos, con frecuencia se pueden obtener, si el software que se esté usando lo permite, 50 o aun 500 dígitos—. Para cada uno de la mayoría de los problemas del Reto Cien–Dígitos, Cien–Dólares, recibí de varios equipos soluciones con 100 o más dígitos de precisión.

Existe una tercera posibilidad exhibida por algunos de los participantes en algunos de los problemas: la idea brillante, ya sea elemental o avanzada, que simplemente arrasa con el problema. La ocurrencia de esta posibilidad resulta ser emocionante pero en todos los diez problemas era posible obtener 10 dígitos por métodos ordinarios.

He pensado en escribir un artículo acerca de estos problemas pero los competidores ¡dejaron el asunto en un nivel demasiado alto! Varios de ellos han puesto soluciones en la Internet y otros colocaron reportes técnicos. ¡Con seguridad, pocos ejercicios numéricos habían sido alguna vez examinados tan minuciosamente como estos diez!

Las soluciones

El integrando es perverso porque cuando $x\rightarrow 0+$ la función

diverge en valor absoluto hacia $+\infty$ y oscila con frecuencia infinita. A menos que se encuentre una forma para usarlos ingeniosamente, los integradores automáticos en sistemas como Maple no pueden obtener diez dígitos. Muchas personas usaron la función

de Lambert, y muchos aplicaron un cambio de variable con $t=x^{-1}$ para obtener

Pero, aun así, se debe tratar con el problema de la cantidad infinita de oscilaciones. Una forma frecuente de resolver esta situación fue separar las oscilaciones para obtener una serie alternante de contribuciones a la integral, serie que puede luego ser sumada y extrapolada mediante extrapolación de Aitken u otros métodos. Muchos también usaron integración por partes una o más veces para lograr un integrando con un mejor comportamiento.

La siguiente es la solución más ingeniosa que conozco: Puesto que el coseno es la parte real de la exponencial compleja, podemos escribir

Ahora, puesto que el integrando es una función analítica, podemos adecuar contornos en el plano complejo para obtener

¡Las oscilaciones desaparecieron! Para lograr una precisión de 15 dígitos,

es suficiente de sobra, y los integradores numéricos estándar dan la respuesta en un segundo de tiempo de computador.

Problema 2. Un fotón, moviéndose con velocidad en el plano , sale de cuando en dirección este. Alrededor de cada punto reticular entero en el plano, se ha colocado un espejo circular de radio ¿Qué tan lejos del origen está el fotón cuando ?

Este es un problema elemental. Un poco de geometría proporciona una trayectoria convincente. Pero hay una trampa: El problema es mal condicionado, porque las dinámicas son caóticas. Pequeñas perturbaciones en las condiciones iniciales, o pequeñas perturbaciones introducidas durante los cálculos debidas a redondeo de errores, crecen exponencialmente con el tiempo. Después de diez unidades de tiempo, las perturbaciones se amplifican en aproximadamente once órdenes de magnitud y, como resultado, si se está trabajando con precisión estándar IEEE de 16 dígitos, no se puede calcular la respuesta con más de cinco o seis dígitos significativos. De modo que para este problema se requiere precisión extendida, con la cual puede resolverse en cualquier cantidad de sistemas de software. El fotón rebota 14 veces y termina cerca de

. (Debería haber sido más atrevido y haber pedido la solución para

Este es el único de los diez problemas que requiere precisión extendida —y, por tanto, es el único que no puede ser resuelto con Matlab estándar—. Dicho de otro modo, es el único para el cual los errores de redondeo constituyen la clave. En general, en computación científica, la convergencia rápida de algoritmos es un aspecto en el que hay una mucho mayor concentración de esfuerzo que en el control de errores de redondeo. (Sustenté esta afirmación en "The Definition of Numerical Analysis", SIAM News, noviembre de 1992.)

La norma de

es el valor singular más grande de

o, equivalentemente, la raíz cuadrada del valor propio más grande de $A^{T}A$ . Casi todos los equipos atacaron este problema trabajando con secciones finitas $N\times N$ de la matriz infinita. Para obtener

con una precisión de diez dígitos,

debe ser del orden de miles, demasiado alto para la mayoría de los sistemas de computador. Por eso, la mayoría de los participantes encontró los dígitos requeridos por extrapolación de, por ejemplo, resultados para dimensiones

Esta función está intencionalmente construida de manera tal que tenga infinitos mínimos locales —

de ellos solamente en el cuadrado unidad— pero solamente un mínimo global. Sin embargo no es difícil deducir cual de los mínimos locales es el global. Si se examina el plano de cerca, en un contorno apropiado, se encuentra que dicho mínimo global está próximo a

. Partiendo de esta conjetura inicial, se puede encontrar el mínimo global con gran precisión utilizando cualquier clase de método numérico. Como alternativa, el comando Nminimize en Mathematica encuentra el mínimo global sin mucho problema en caso de que se haga uso de las opciones SimulatedAnnealing o DifferentialEvolution.

Problema 5. Sea , donde $\Gamma (z)$ es la función gama, y sea el polinomio cúbico que mejor aproxima a sobre el disco unitario con la norma del supremo . ¿Cuál es ?

Este problema de aproximación de Chebyshev compleja fue el que ofreció mayores dificultades a los participantes, tal vez porque las funciones complejas conllevan un sabor a tema matemático avanzado con el cual no todas las personas se sienten cómodas. Ciertamente se requiere hacer uso de por lo menos un hecho del análisis complejo: Por el principio del módulo máximo,

alcanza su magnitud máxima en la frontera del dominio de aproximación y, de este modo, sólo se hace necesario considerar a

en la circunferencia unitaria. También se puede ver que es suficiente considerar polinomios con coeficientes reales.

Admiro el duro trabajo y el ingenio que desplegaron muchos de los equipos para atacar este problema. Por ejemplo, después de intentar con un método, los integrantes de SCIMATH (equipo número 11 en el listado de ganadores) escribieron: "¡Cada truco mencionado en los libros queda atascado en el lodo de este barranco!" Sin desanimarse, perseveraron hasta encontrar otro método que sí funcionó. Por otra parte, media docena de expertos hicieron uso de algoritmos y software especializados creados para ese tipo de problemas.

Problema 6. Una pulga sale de en el retículo entero bidimensional infinito y ejecuta un paseo aleatorio con preferencias distintas: En cada paso salta hacia el norte o sur con probabilidad , hacia el este con probabilidad $1/4+\varepsilon$ , y hacia el oeste con probabilidad $1/4-\varepsilon$ . La probabilidad de que la pulga retorne a en algún momento durante su correría es . ¿Cuál es $\varepsilon$ ?

Si no sopla el viento, esto es si $\varepsilon =0$ , entonces la pulga retorna al origen infinitas veces con probabilidad

. Si $\varepsilon \neq 0$ , la probabilidad de retorno es menor que

. Muchos simularon este problema mediante experimentos numéricos para obtener unos pocos dígitos. En tales simulaciones, así como en métodos más avanzados, uno debe tener el cuidado de no confundir el número esperado de retornos $\nu$ con la probabilidad de retorno

Hubo un amplio espectro de métodos de alta precisión diseñados para este problema. Algunos competidores usaron relaciones de recurrencia, unidimensionales o bidimensionales, y series infinitas. Otros usaron funciones generatrices y análisis de Fourier. Y otros formularon un problema de álgebra lineal para determinar la probabilidad en cada punto reticular, es decir determinaron una "función reticular de Green" que puede a su turno relacionarse con una integral doble. Dado $\varepsilon$ , la probabilidad de retorno puede, en efecto, escribirse explícitamente en términos de funciones elípticas pero, en cualquier caso, todo conduce a resolver una ecuación no lineal para encontrar el valor de $\varepsilon$ que da

Problema 7. Sea la matriz $20000\times 20000$ cuyas componentes son cero en todas partes excepto por los primos , , , , ... , a lo largo de la diagonal principal y el número en todas las posiciones $a_{ij}$ con , , , , ... , . ¿Cuál es la componente de $A^{-1}$ ?

Cuando propuse este problema estaba pensando en iteraciones matriciales. La matriz es demasiado grande para una solución directa en la mayoría de computadores, pero por el método del gradiente conjugado con un precondicionador diagonal se puede encontrar la respuesta en menos de veinte iteraciones. La componente

de $A^{-1}$ es la primera componente del vector solución

del sistema $Ax=e_{1}$ donde

. Prácticamente todos los participantes encontraron la respuesta mediante un método iterativo como este, usando a menudo iteraciones más simples, tales como Gauss–Seidel o un método diseñado a propósito.

Pero ¿creerían ustedes que el problema puede ser resuelto exactamente? ¡No directamente, pero sí exactamente! El número que estamos buscando es el cociente de dos determinantes (regla de Cramer) cada uno de los cuales es un entero. "Todo" lo que hay que hacer es encontrar estos enteros. Nunca soñé en algo así, pero uno de los competidores, el LinBox Team, realmente lo logró. Jean–Guillaume Dumas del LMC_IMAG en Grenoble puso a trabajar 186 procesadores durante cuatro días usando software LinBox. La matemática utilizada involucró técnicas modulares de caja negra y el teorema chino de los restos. El numerador y denominador son primos relativos y cada uno tiene exactamente $97\,390$ dígitos. El cociente es

donde cada " . . . " representa $97\,380$ dígitos omitidos. Zhendong Wan de University of Delaware verificó posteriormente el resultado en un procesador con gran memoria (4GB), tarea que requirió 12 días de nuevos cómputos.

Problema 8. Una lámina cuadrada se encuentra a la temperatura . En el instante se incrementa la temperatura a a lo largo de uno de los cuatro lados mientras se mantiene en a lo largo de los otros tres lados, y entonces el calor fluye a través de la lámina de acuerdo con $u_{t}=\Delta u$ . ¿Cuándo alcanza la temperatura el valor en el centro de la lámina?

Hay muchas formas de obtener unos pocos dígitos de precisión para este problema. Un buen comienzo, aprovechando las ventajas de la linealidad, es reformularlo de modo tal que, cuando

, la temperatura sea

en todas partes, salvo en los cuatros lados que constituyen la frontera, y en esta última sea

. Luego se encuentra el instante en el cual

en $\left( 0,0\right)$ y, aprovechando la simetría, se divide el dominio en cuatro partes y se usa una aproximación por diferencias finitas. De este modo, se pueden calcular los resultados para una sucesión de mallas de tamaños tales como $2^{-1}$ , $2^{-2}$ , ... , $2^{-6}$ y luego mejorar estos resultados, hasta diez o más dígitos, usando extrapolación de Richardson.

Sin embargo, no es necesario discretizar el problema ya que este tiene tanta estructura que puede ser resuelto utilizando series de Fourier que converjan con rapidez exponencial. En efecto, el mismo Joseph Fourier, interesado en el mantenimiento de temperaturas frescas en bodegas de vino durante los meses de verano, resolvió justamente esta clase de problema, justamente mediante este método. Es interesante notar que la temperatura en $\left( 0,0\right)$ se obtiene con 15 dígitos de precisión mediante cuatro términos de Fourier:

donde $a=\pi ^{2}/4$ . No es difícil encontrar el valor de

para el cual esta función toma el valor

depende del parámetro $\alpha$ . ¿ Cuál es el valor de para el cual alcanza su máximo?

He aquí otro perverso integrando que oscila infinitas veces. Evaluar

es ya de por sí un desafío y se debe hacer de una manera lo bastante eficiente y suave de modo que constituya la base de un procedimiento de minimización. Esto puede, en efecto, hacerse numéricamente y mediante una variedad de métodos ingeniosos como, de hecho, hizo la mayoría. Se requiere cuidado y determinación pero no conocimiento especializado.

Sin embargo, Mathematica dispone de algún conocimiento especializado relevante: ¡Sabe cómo evaluar esta integral en forma explícita! La solución involucra una función especial que data de los años treinta, conocida como la función G de Meijer, y que Mathematica puede evaluar numéricamente. Empleando entonces aritmética de precisión arbitraria, el problema se torna fácil.

Problema 10. A partir del centro de un rectángulo $10\times 1$ una partícula se mueve con movimiento browniano (i. e., realiza un paseo aleatorio bidimensional con pasos de longitud infinitesimal) hasta que golpea la frontera. ¿Cuál es la probabilidad de que golpee una de las esquinas del rectángulo?

Una forma natural de comenzar a resolver un problema como este es tratando de simular algunas trayectorias de muestra —método de Monte Carlo—. Pronto se descubre que menos de una trayectoria en un millón alcanza las esquinas. El cálculo de la probabilidad, con diez dígitos de precisión relativa, requiere algo así como ¡ $10^{26}$ muestras! De modo que se requiere más astucia y este fue un problema en el que la gente mostró gran ingenio.

Al fin de cuentas, lo que se tiene aquí es un problema de ecuaciones diferenciales parciales: Si la ecuación de Laplace se tiene sobre el rectángulo, con condiciones de frontera

sobre los lados y

en las esquinas, ¿cuál es el valor en el origen? Los expertos llaman a este número la medida armónica de las esquinas con respecto al punto $\left( 0,0\right)$ . Ella puede calcularse usando aplicaciones conformes o series de Fourier. La mayoría de equipos optó por utilizar una representación en serie rápidamente convergente. En efecto, la solución puede escribirse explícitamente en términos de la función seno elíptico de Jacobi. Una aproximación suficientemente buena para lograr los diez dígitos requeridos, basada en aproximar el rectángulo mediante una banda semiinfinita, es