Bivariate range functions with superior convergence order

Resumen Técnico: Funciones de Rango Bivariadas con Orden de Convergencia Superior

1. El Problema

En campos como el modelado geométrico, la gráficos por computadora y la robótica, es fundamental realizar cálculos certificados para problemas como la intersección de superficies, la geometría constructiva de sólidos (CSG), el trazado de rayos (ray-tracing) y la detección de colisiones. La herramienta central para esto son las funciones de rango (o funciones de inclusión), que calculan un intervalo garantizado que contiene el rango de una función $f$ sobre un dominio dado $B$ (típicamente una caja, simplex o bola).

El desafío principal radica en la eficacia (la "estrechez" o precisión del intervalo estimado) y la eficiencia computacional.

• Las funciones de rango tradicionales, basadas en expansiones de Taylor, tienen un orden de convergencia cuadrático ($m=2$). Esto significa que el error de la estimación disminuye proporcionalmente al cuadrado del ancho del dominio.
• Aunque teóricamente se pueden usar expansiones de Taylor de grado superior, el orden de convergencia sigue siendo cuadrático en la práctica estándar.
• Se necesitan métodos con orden de convergencia superior ($m > 2$, es decir, cúbico o cuártico) para lograr algoritmos de búsqueda de raíces más rápidos y precisos, pero estos métodos a menudo conllevan un alto costo computacional o son difíciles de implementar.

2. Metodología

Los autores proponen nuevas funciones de rango bivariadas basadas en la generalización del marco Cornelius–Lohner (CL). La idea central de este marco es descomponer la función $f$ en una parte exacta $g$ y un resto $R_g$:
$$f(x) = g(x) + R_g(x)$$
Donde el rango de $f$ se estima como la suma del rango de $g$ y una cota del rango del resto $R_g$. Para lograr un orden de convergencia superior, se requiere que el error de la aproximación de $g$ y la cota de $R_g$ decrezcan rápidamente (orden $m$).

El artículo introduce tres nuevas familias de funciones de rango basadas en diferentes esquemas de interpolación:

1. Formas de Taylor Centradas Generalizadas (Sección 2):

   • Se basan en la expansión de Taylor de $f$ alrededor del punto medio de la caja.
   • Se separan los primeros $m$ términos del polinomio de Taylor.
   • Se demuestra que si se calcula el rango exacto del polinomio de Taylor de grado $m-1$ y se acota el resto adecuadamente, se logra un orden de convergencia $m$.
   • Se implementan formas de orden 2, 3 y 4 ($T_{2,n}, T_{3,n}, T_{4,n}$).

2. Forma Lagrange Recursiva (Sección 3):

   • Inspirada en construcciones univariadas, utiliza interpolación Lagrange bicuadrática en una cuadrícula $3 \times 3$ (esquinas, puntos medios de aristas y centro).
   • El error de la interpolación se acota recursivamente aplicando la misma lógica a las derivadas parciales de orden superior.
   • Se logra un orden de convergencia cúbico ($m=3$).
   • La forma se denota como $L_{3,n}$.

3. Forma Hermite Recursiva (Sección 4):

   • Utiliza interpolación Hermite bicúbica, que interpola la función y sus derivadas parciales de primer orden en las esquinas de la caja.
   • Similar a la forma Lagrange, el error se acota recursivamente sobre las derivadas.
   • Se logra un orden de convergencia cuártico ($m=4$).
   • La forma se denota como $H_{4,n}$.

Implementación:

• Las funciones se implementaron en el lenguaje Julia.
• Se utilizan Programas de Línea Recta (SLP) y diferenciación automática simbólica de listas de código para mejorar el rendimiento.
• Para los polinomios de bajo grado, se utilizan expresiones algebraicas exactas para calcular los rangos de las partes polinómicas ($g$), evitando errores de redondeo en esa etapa crítica.

3. Contribuciones Clave

• Nuevas Funciones de Rango: Introducción de las primeras funciones de rango bivariadas con órdenes de convergencia cúbico y cuártico basadas en interpolación de Taylor, Lagrange y Hermite dentro del marco CL generalizado.
• Análisis Teórico: Demostración formal de que estas nuevas formas cumplen con los órdenes de convergencia $m=3$ y $m=4$ bajo el teorema generalizado de Cornelius-Lohner.
• Validación Experimental: Implementación completa y pruebas exhaustivas que comparan la eficiencia y eficacia de estas nuevas formas frente a las formas de Taylor tradicionales.
• Identificación del "Punto Dulce" (Sweet Spot): Determinación empírica de que el orden cúbico ($m=3$) ofrece el mejor equilibrio entre precisión y costo computacional.

4. Resultados Experimentales

Los experimentos se realizaron sobre cuatro polinomios de prueba de grado variable (desde grado 10 hasta 18) y se evaluaron en 1024 cajas subdivididas.

• Convergencia: Los gráficos log-log confirman que las nuevas formas alcanzan los órdenes de convergencia teóricos ($O(r^2)$, $O(r^3)$, $O(r^4)$).
• Eficacia (Precisión):
  • Todas las formas con orden superior ($m \ge 3$) son significativamente más precisas (intervalos más estrechos) que la base lineal $T_2$.
  • La mejora de eficacia al pasar de $m=3$ a $m=4$ es marginal (los intervalos son solo ligeramente más estrechos).
• Eficiencia (Tiempo y Memoria):
  • Las formas de Taylor de orden superior ($T_3, T_4$) tienen un costo computacional muy similar a la base $T_2$, a veces incluso más rápido debido a optimizaciones.
  • Las formas Lagrange ($L_3$) y Hermite ($H_4$) son más costosas si se evalúan individualmente. Sin embargo, en algoritmos de subdivisión, permiten compartir cálculos (derivadas en esquinas y puntos medios).
  • Resultado clave: Cuando se activa el "compartir datos" (shared), la forma Lagrange de orden 3 ($L_3$) se convierte en el método más eficiente, superando a la base $T_2$ en tiempo de ejecución y uso de memoria, mientras mantiene una alta precisión.
• Comparación Visual: Los mapas de calor muestran que $T_3$ es consistentemente más preciso que $T_2$, y que $L_3$ y $T_3$ compiten en precisión dependiendo de la forma local de la función, sin un ganador absoluto en todos los casos.

5. Significado y Conclusiones

El trabajo establece un nuevo estado del arte para las funciones de rango bivariadas en el contexto de la aritmética de intervalos.

• Optimización Práctica: La conclusión principal es que el orden cúbico ($m=3$) representa el "punto dulce" óptimo. Ofrece una mejora sustancial en la precisión sobre los métodos cuadráticos tradicionales, con un costo computacional manejable (especialmente con la forma Lagrange compartida), mientras que el orden cuártico ($m=4$) ofrece mejoras de precisión marginales a un costo de implementación y ejecución significativamente mayor.
• Impacto en Aplicaciones: Estos métodos permitirán algoritmos de búsqueda de raíces y trazado de curvas más rápidos y robustos, reduciendo el número de subdivisiones necesarias para aislar soluciones.
• Futuro: Los autores señalan que el marco es extensible a órdenes superiores y funciones multivariadas, y planean integrar estas funciones en aplicaciones completas de trazado de curvas y aislamiento de raíces para demostrar su impacto holístico.

En resumen, el artículo demuestra que es posible y práctico superar la barrera de la convergencia cuadrática en funciones de rango bivariadas, ofreciendo herramientas computacionalmente viables que mejoran la eficiencia de los algoritmos geométricos certificados.