Método aditivo de Schwarz

En matemáticas , el método aditivo de Schwarz , que recibe su nombre de Hermann Schwarz , resuelve un problema de valores en la frontera para una ecuación diferencial parcial de forma aproximada dividiéndolo en problemas de valores en la frontera en dominios más pequeños y sumando los resultados.

Descripción general

Las ecuaciones diferenciales parciales (EDP) se utilizan en todas las ciencias para modelar fenómenos. A modo de ejemplo, presentamos un problema físico y su correspondiente problema de contorno (PCC). Aunque el lector no esté familiarizado con la notación, el objetivo es simplemente mostrar cómo se representa un PCC escrito.

(Problema modelo) La distribución de calor en una placa metálica cuadrada, de manera que el borde izquierdo se mantenga a 1 grado y los demás bordes a 0 grados, después de dejarla reposar durante un largo período de tiempo, satisface el siguiente problema de valores en la frontera:

${\begin{aligned}&f_{xx}(x,y)+f_{yy}(x,y)=0\\&f(0,y)=1;\;f(x,0)=f(x,1)=f(1,y)=0\end{aligned}}$

donde

f

es la función desconocida ,

f xx

y

f yy

denotan las segundas derivadas parciales con respecto a

x

e

y

, respectivamente.

Aquí, el dominio es el cuadrado $[0,1] \times [0,1]$ .

Este problema en particular se puede resolver con exactitud sobre papel, por lo que no se necesita una computadora. Sin embargo, este es un caso excepcional, y la mayoría de los problemas de contorno no se pueden resolver con exactitud. La única posibilidad es usar una computadora para encontrar una solución aproximada.

Resolver en una computadora

Una forma típica de hacerlo es muestrear $f$ a intervalos regulares en el cuadrado $[0,1] \times [0,1]$ . Por ejemplo, podríamos tomar 8 muestras en la dirección $x en$ $x = 0.1, 0.2, ..., 0.8, 0.9$ , y 8 muestras en la dirección $y$ en coordenadas similares . Tendríamos entonces 64 muestras del cuadrado, en lugares como (0.2,0.8) y (0.6,0.6). El objetivo del programa informático sería calcular el valor de $f$ en esos 64 puntos, lo cual parece más sencillo que encontrar una función abstracta del cuadrado.

Existen algunas dificultades; por ejemplo, no es posible calcular $f xx (0,5,0,5)$ conociendo f en solo 64 puntos del cuadrado. Para superar esto, se utiliza algún tipo de aproximación numérica de las derivadas, como por ejemplo el método de elementos finitos o el de diferencias finitas . Ignoramos estas dificultades y nos centramos en otro aspecto del problema.

Resolución de problemas lineales

Cualquiera que sea el método que elijamos para resolver este problema, necesitaremos resolver un sistema de ecuaciones lineales extenso . El lector quizás recuerde los sistemas de ecuaciones lineales de la escuela secundaria; tienen este aspecto:

$6a-3b=-3$

Este es un sistema de dos ecuaciones con dos incógnitas ( $a$ y $b$ ). Si resolvemos el problema de valores en la frontera (PVF) anterior de la manera sugerida, necesitaremos resolver un sistema de 64 ecuaciones con 64 incógnitas. Esto no representa un problema difícil para las computadoras modernas, pero si utilizamos un mayor número de muestras, incluso las computadoras modernas no pueden resolver el PVF de manera muy eficiente.

descomposición de dominio

Esto nos lleva a los métodos de descomposición de dominio. Si dividimos el dominio $[0,1] \times [0,1]$ en dos subdominios $[0,0.5] \times [0,1]$ y $[0.5,1] \times [0,1]$ , cada uno tiene solo la mitad de los puntos de muestra. Así que podemos intentar resolver una versión de nuestro problema modelo en cada subdominio, pero esta vez cada subdominio tiene solo 32 puntos de muestra. Finalmente, dadas las soluciones en cada subdominio, podemos intentar conciliarlas para obtener una solución del problema original en $[0,1] \times [0,1]$ .

Magnitud de los problemas

En términos de sistemas lineales, estamos intentando dividir el sistema de 64 ecuaciones con 64 incógnitas en dos sistemas de 32 ecuaciones con 32 incógnitas. Esto supondría una clara ventaja, por la siguiente razón. Al observar el sistema (*) , vemos que hay 6 datos importantes: los coeficientes de a y b (2,5 en la primera línea y 6,−3 en la segunda), y el lado derecho (que escribimos como 12,−3). Por otro lado, si tomamos dos "sistemas" de 1 ecuación con 1 incógnita, podrían verse así:

$2a=12$ $-3b=-3$

Observamos que este sistema solo contiene cuatro datos importantes. Esto significa que un programa informático tendrá más facilidad para resolver dos sistemas de 1×1 que un sistema de 2×2, ya que el par de sistemas de 1×1 es más sencillo que el sistema de 2×2. Si bien los sistemas de 64×64 y 32×32 son demasiado grandes para ilustrarlos aquí, podríamos decir, por analogía, que el sistema de 64×64 contiene 4160 datos, mientras que los sistemas de 32×32 contienen 1056 cada uno, aproximadamente una cuarta parte del sistema de 64×64.

algoritmo de descomposición de dominio

Lamentablemente, por razones técnicas, normalmente no es posible dividir nuestra cuadrícula de 64 puntos (un sistema de ecuaciones lineales de 64×64) en dos cuadrículas de 32 puntos (dos sistemas de ecuaciones lineales de 32×32) y obtener una solución para el sistema de 64×64. En su lugar, el algoritmo que se utiliza es el siguiente:

Comience con una solución aproximada del sistema de 64×64.
A partir del sistema de 64×64, cree dos sistemas de 32×32 para mejorar la solución aproximada.
Resuelve los dos sistemas de 32×32.
Combina las dos soluciones de 32×32 para mejorar la solución aproximada del sistema de 64×64.
Si la solución aún no es muy buena, repita desde el paso 2.

Existen dos maneras en que este método puede ser mejor que resolver el sistema de base 64×64. Primero, si el número de repeticiones del algoritmo es pequeño, resolver dos sistemas de 32×32 puede ser más eficiente que resolver un sistema de 64×64. Segundo, no es necesario resolver los dos sistemas de 32×32 en la misma computadora, por lo que este algoritmo puede ejecutarse en paralelo para aprovechar la potencia de múltiples computadoras.

De hecho, resolver dos sistemas de 32×32 en lugar de uno de 64×64 en un solo ordenador (sin paralelismo) probablemente no sea eficiente. Sin embargo, si utilizamos más de dos subdominios, la situación cambia. Por ejemplo, podríamos usar cuatro problemas de 16×16, y es posible que resolverlos sea más eficiente que resolver un único problema de 64×64, incluso si el algoritmo de descomposición de dominio necesita iterar varias veces.

Un ejemplo técnico

Aquí partimos de la base de que el lector está familiarizado con las ecuaciones diferenciales parciales.

Resolveremos la ecuación diferencial parcial.

Imponemos la condición de límite en el infinito.

Descomponemos el dominio $R 2$ en dos subdominios superpuestos $H 1 = (-\infty, 1] \times R$ y $H 2 = [0, +\infty) \times R$ . En cada subdominio, resolveremos un problema de contorno de la forma:

${\begin{aligned}u_{xx}^{(j)}+u_{yy}^{(j)}&=f\;\;{\text{ en }}H_{j}\\u^{(j)}(x_{j},y)&=g(y)\end{aligned}}$

donde $x 1 = 1$ y $x 2 = 0$ y tomando la condición de contorno de acotación en el infinito. Denotamos la solución $u (j)$ del problema anterior por $S(f, g)$ . Nótese que $S$ es bilineal.

El algoritmo de Schwarz procede de la siguiente manera:

Comience con soluciones aproximadas $u (1) 0$ y $u (2) 0$ de la EDP en los subdominios $H 1$ y $H 2$ respectivamente. Inicialice $k$ a 0.
Calcula $u (j) k + 1 = S(f, u (3 - j) k (x j))$ con $j = 1, 2$ .
Incremente $k$ en uno y repita el paso 2 hasta alcanzar la precisión suficiente.

Véase también

Referencias

Smith, Barry; Bjørstad, Petter; Gropp, William (1996). Descomposición de dominio, métodos multinivel paralelos para ecuaciones diferenciales parciales elípticas . Cambridge University Press. ISBN 0-521-49589-X.
Toselli, Andrea; Widlund, Olof B. (2004). Métodos de descomposición de dominio: algoritmos y teoría . Springer Series in Computational Mathematics, vol. 34. ISBN 978-3-540-20696-5.

Enlaces externos

La página oficial de Métodos de Descomposición de Dominios