Continuación lineal por partes

La 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 incrustación pequeños y 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.

El problema del trazado de contornos es encontrar los ceros (contornos) de ( una función escalar suave) en el cuadrado , ${\displaystyle f(x,y)=0\,}$${\displaystyle f(\cdot )\,}$${\displaystyle 0\leq x\leq 1,0\leq y\leq 1\,}$

El cuadrado se divide en pequeños triángulos, generalmente introduciendo puntos en las esquinas de una malla cuadrada regular , , haciendo una tabla de los valores de en cada esquina , y luego dividiendo cada cuadrado en dos triángulos. El valor de en las esquinas del triángulo define un interpolador lineal por partes único para sobre cada triángulo. Una forma de escribir este interpolador en el triángulo con esquinas es como el conjunto de ecuaciones ${\displaystyle ih_{x}\leq x\leq (i+1)h_{x}\,}$${\displaystyle jh_{y}\leq y\leq (j+1)h_{y}\,}$${\displaystyle f(x_{i},y_{j})\,}$${\estilo de visualización (i,j)\,}$${\displaystyle f(x_{i},y_{j})\,}$${\displaystyle lf(x,y)\,}$${\displaystyle f(\cdot )\,}$${\displaystyle (x_{0},y_{0}),~(x_{1},y_{1}),~(x_{2},y_{2})\,}$

${\displaystyle (x,y)=(x_{0},y_{0})+(x_{1}-x_{0},y_{1}-y_{0})s+(x_{2}-x_ {0},y_{2}-y_{0})t\,}$

${\displaystyle 0\leq s\,}$

${\estilo de visualización 0\leq t\,}$

${\displaystyle s+t\leq 1\,}$

${\displaystyle lf(x,y)=f(x_{0},y_{0})+(f(x_{1},y_{1})-f(x_{0},y_{0}))s+(f(x_{2},y_{2})-f(x_{0},y_{0}))t\,}$

Las primeras cuatro ecuaciones se pueden resolver para (esto convierte el triángulo original en un triángulo unitario rectángulo), luego la ecuación restante da el valor interpolado de . En toda la malla de triángulos, este interpolador lineal por partes es continuo. ${\estilo de visualización (s,t)\,}$${\displaystyle f(\cdot )\,}$

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). Se puede encontrar la ecuación de la línea, 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 interpolador lineal por partes es un conjunto de curvas formadas por estos segmentos de línea. Cualquier punto en el borde que conecta y se puede escribir como ${\displaystyle (x_{0},y_{0})\,}$${\displaystyle (x_{1},y_{1})\,}$

${\displaystyle (x,y)=(x_{0},y_{0})+t(x_{1}-x_{0},y_{1}-y_{0}),\,}$

con en , y el interpolante lineal sobre el borde es ${\estilo de visualización t\,}$${\estilo de visualización (0,1)\,}$

${\displaystyle f\sim f_{0}+t(f_{1}-f_{0})\,}$

Así que estableciendo${\estilo de visualización f=0\,}$

${\displaystyle t=-f_{0}/(f_{1}-f_{0})\,}$y${\displaystyle (x,y)=(x_{0},y_{0})-f_{0}*(x_{1}-x_{0},y_{1}-y_{0})/(f_{1}-f_{0})\,}$

Como esto solo depende de los valores de la arista, cada triángulo que comparte esta arista 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 contorno.

La continuación lineal por partes es similar al trazado de contornos (Dobkin, Levy, Thurston y Wilks), ^[5] pero en dimensiones superiores. El algoritmo se basa en los siguientes resultados:

Un símplex de dimensión '(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 de dimensión (n-1) con n vértices , entonces existen escalares positivos tales que ${\displaystyle v_{i}}$${\displaystyle 0<\alpha _{i}}$

Si los vértices del símplex son linealmente independientes, los escalares no negativos son únicos para cada punto x y se denominan coordenadas baricéntricas de x. Determinan el valor del interpolador único mediante la fórmula: ${\estilo de visualización \alpha}$

Básicamente existen dos tests. El primero que se utilizó etiqueta los vértices del símplex 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 dice que está completamente etiquetado si hay un vértice cuya etiqueta comienza con una cadena de signos "+" de longitud 0,1,2,3,4,...n. Un símplex completamente etiquetado contiene un entorno del origen. Esto puede resultar sorprendente, pero lo que subyace a este resultado es que para cada coordenada de un símplex completamente etiquetado hay un vector con "+" y otro con un "-". Dicho de otro modo, el cubo más pequeño con aristas paralelas a los ejes de coordenadas y que cubre el símplex tiene pares de caras en lados opuestos de 0. (es decir, un "+" y un "-" para cada coordenada).

El segundo enfoque se denomina etiquetado vectorial y 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, a continuación, la prueba de que el símplex contiene el origen consiste simplemente en que todas las coordenadas baricéntricas sean positivas y la suma sea menor que 1.