Continuación simple , o continuación lineal por partes (Allgower y Georg), [1] [2] es un método de continuación de un parámetro que se adapta bien a espacios de empotrar pequeños a medianos. El algoritmo ha sido generalizado para calcular variedades de dimensiones superiores por (Allgower y Gnutzman) [3] y (Allgower y Schmidt). [4]
El algoritmo para dibujar contornos es un algoritmo de continuación simple y, dado que es fácil de visualizar, sirve como una buena introducción al algoritmo.
Trazado de contorno
El problema del trazado de contorno es encontrar los ceros (contornos) de ( una función de valor escalar suave) en el cuadrado ,
El cuadrado se divide en pequeños triángulos, generalmente mediante la introducción de puntos en las esquinas de una malla cuadrada regular. , , haciendo una tabla de los valores de en cada esquina y luego dividir cada cuadrado en dos triángulos. El valor de en las esquinas del triángulo define un interpolante lineal a trozos único a sobre cada triángulo. Una forma de escribir este interpolante en el triángulo con esquinas es como el conjunto de ecuaciones
Las primeras cuatro ecuaciones se pueden resolver para (esto asigna el triángulo original a un triángulo unitario rectángulo), luego la ecuación restante da el valor interpolado de . En toda la malla de triángulos, este interpolante lineal por partes es continuo.
El contorno del interpolante en un triángulo individual es un segmento de línea (es un intervalo en la intersección de dos planos). La ecuación para la línea se puede encontrar, sin embargo, los puntos donde la línea cruza los bordes del triángulo son los puntos finales del segmento de línea.
El contorno del interpolante lineal por partes es un conjunto de curvas formado por estos segmentos de línea. Cualquier punto en el borde conectando y Se puede escribir como
con en , y el interpolante lineal sobre el borde es
Así que estableciendo
- y
Dado que esto solo depende de los valores en el borde, cada triángulo que comparte este borde producirá el mismo punto, por lo que el contorno será continuo. Cada triángulo se puede probar de forma independiente y, si se verifican todos, se puede encontrar el conjunto completo de curvas de nivel.
Continuación lineal por partes
La continuación lineal por partes es similar al trazado de contornos (Dobkin, Levy, Thurston y Wilks), [5] pero en dimensiones más altas. El algoritmo se basa en los siguientes resultados:
Lema 1
Si F (x) mapea dentro , hay un interpolante lineal único en un simplex dimensional '(n-1)' que concuerda con los valores de la función en los vértices del simplex. |
Un simplex dimensional '(n-1)' tiene n vértices, y la función F asigna un vector 'n' a cada uno. El símplex es convexo y cualquier punto dentro del símplex es una combinación convexa de los vértices. Es decir:
Si x está en el interior de un símplex (n-1) -dimensional con n vértices , luego hay escalares positivos tal que
Si los vértices del simplex son linealmente independientes, los escalares no negativosson únicas para cada punto x, y se denominan coordenadas baricéntricas de x. Determinan el valor del interpolante único mediante la fórmula:
Lema 2
Se puede probar un símplex (n-1) -dimensional para determinar si contiene el origen. |
Básicamente hay dos pruebas. El que se utilizó por primera vez etiqueta los vértices del simplex con un vector de signos (+/-) de las coordenadas del vértice. Por ejemplo, el vértice (.5, -. 2,1.) Estaría etiquetado (+, -, +). Un símplex se llama completamente etiquetado si hay un vértice cuya etiqueta comienza con una cadena de signos "+" de longitud 0,1,2,3,4, ... n. Un simplex completamente etiquetado contiene una vecindad del origen. Esto puede resultar sorprendente, pero lo que subyace a este resultado es que para cada coordenada de un simplex completamente etiquetado hay un vector con "+" y otro con "-". Dicho de otra manera, el cubo más pequeño con aristas paralelas a los ejes de coordenadas y que cubre el simplex tiene pares de caras en lados opuestos de 0. (es decir, un "+" y un "-" para cada coordenada).
El segundo enfoque se llama etiquetado vectorial . Se basa en las coordenadas baricéntricas de los vértices del símplex. El primer paso es encontrar las coordenadas baricéntricas del origen, y luego la prueba de que el simplex contiene el origen es simplemente que todas las coordenadas baricéntricas son positivas y la suma es menor que 1.
Lema 3
Hay una triangulación (la triangulación de Coxeter-Freudenthal-Kuhn [1]) que es invariante bajo la operación de pivote dónde
|
Referencias
- ^ Eugene L. Allgower, K. Georg, "Introducción a los métodos de continuación numérica", SIAM Classics in Applied Mathematics 45, 2003.
- ^ EL Allgower, K. Georg, "Métodos simples y de continuación para aproximar puntos fijos y soluciones a sistemas de ecuaciones", Revisión de SIAM , volumen 22, 28-85, 1980.
- ^ Eugene L. Allgower, Stefan Gnutzmann, "Un algoritmo para la aproximación lineal por partes de superficies bidimensionales definidas implícitamente", SIAM Journal on Numerical Analysis , volumen 24, número 2, 452-469, 1987.
- ^ Eugene L. Allgower, Phillip H. Schmidt, "Un algoritmo para la aproximación lineal por partes de un colector definido implícitamente", SIAM Journal on Numerical Analysis , volumen 22, número 2, 322-346, abril de 1985.
- ^ David P. Dobkin , Silvio VF Levy, William P. Thurston y Allan R. Wilks, "Trazado de contorno por aproximaciones lineales por partes", ACM Transactions on Graphics , 9 (4) 389-423, 1990.