En matemáticas , el método de Schwarz aditivo , que lleva el nombre de Hermann Schwarz , resuelve un problema de valor límite para una ecuación diferencial parcial aproximadamente dividiéndolo en problemas de valor límite en dominios más pequeños y sumando los resultados.
Descripción general
Las ecuaciones diferenciales parciales (PDE) se utilizan en todas las ciencias para modelar fenómenos. A los efectos de la exposición, damos un ejemplo de problema físico y el problema de valor límite (PVV) que lo acompaña. Incluso si el lector no está familiarizado con la notación, el propósito es simplemente mostrar cómo se ve un BVP cuando se escribe.
- (Problema del modelo) La distribución de calor en una placa de metal cuadrada de manera que el borde izquierdo se mantiene a 1 grado y los otros bordes se mantienen a 0 grados, después de dejarlo reposar durante un largo período de tiempo satisface el siguiente problema de valor límite:
- f xx ( x , y ) + f yy ( x , y ) = 0
- f (0, y ) = 1; f ( x , 0) = f ( x , 1) = f (1, y ) = 0
- donde f es la desconocido función , f xx y f yy denotar la segunda derivadas parciales con respecto a x e y , respectivamente.
Aquí, el dominio es el cuadrado [0,1] × [0,1].
Este problema en particular se puede resolver exactamente en papel, por lo que no se necesita una computadora. Sin embargo, este es un caso excepcional y la mayoría de los BVP no se pueden resolver con exactitud. La única posibilidad es utilizar una computadora para encontrar una solución aproximada.
Resolviendo en una computadora
Una forma típica de hacer esto es muestrear f a intervalos regulares en el cuadrado [0,1] × [0,1]. Por ejemplo, podríamos tomar 8 muestras en la dirección x en x = 0.1, 0.2, ..., 0.8 y 0.9, y 8 muestras en la dirección y en coordenadas similares . Entonces tendríamos 64 muestras del cuadrado, en lugares como (0.2,0.8) y (0.6,0.6). El objetivo del programa de computadora sería calcular el valor de f en esos 64 puntos, lo que parece más fácil 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 en el cuadrado. Para superar esto, se utiliza algún tipo de aproximación numérica de las derivadas, ver, por ejemplo, el método de los elementos finitos o las diferencias finitas . Ignoramos estas dificultades y nos concentramos en otro aspecto del problema.
Resolver problemas lineales
Cualquiera que sea el método que elijamos para resolver este problema, necesitaremos resolver un gran sistema lineal de ecuaciones . El lector puede recordar los sistemas lineales de ecuaciones de la escuela secundaria, se ven así:
- 2 a + 5 b = 12 (*)
- 6 a - 3 b = −3
Este es un sistema de 2 ecuaciones en 2 incógnitas ( a y b ). Si resolvemos el BVP anterior de la manera sugerida, necesitaremos resolver un sistema de 64 ecuaciones en 64 incógnitas. Este no es un problema difícil para las computadoras modernas, pero si usamos una mayor cantidad de muestras, incluso las computadoras modernas no pueden resolver el BVP de manera muy eficiente.
Descomposición de dominio
Lo que nos lleva a los métodos de descomposición de dominios. Si dividimos el dominio [0,1] × [0,1] en dos subdominios [0,0.5] × [0,1] y [0.5,1] × [0,1], cada uno tiene solo la mitad de la muestra puntos. Entonces, podemos intentar resolver una versión de nuestro problema de modelo en cada subdominio, pero esta vez cada subdominio tiene solo 32 puntos de muestra. Finalmente, dadas las soluciones en cada subdominio, podemos intentar reconciliarlas para obtener una solución del problema original en [0,1] × [0,1].
Tamaño de los problemas
En términos de sistemas lineales, estamos tratando de dividir el sistema de 64 ecuaciones en 64 incógnitas en dos sistemas de 32 ecuaciones en 32 incógnitas. Esta sería una clara ganancia, por la siguiente razón. Mirando hacia atrás en el sistema (*), vemos que hay 6 piezas importantes de información. Ellos son los coeficientes de un y b (2,5 en la primera línea y 6, -3 en la segunda línea), y el lado derecho (que se escribe como 12, -3). Por otro lado, si tomamos dos "sistemas" de 1 ecuación en 1 desconocido, podría verse así:
- Sistema 1: 2 a = 12
- Sistema 2: -3 b = −3
Vemos que este sistema tiene solo 4 piezas importantes de información. Esto significa que a un programa de computadora le resultará más fácil resolver dos sistemas 1 × 1 que resolver un solo sistema 2 × 2, porque el par de sistemas 1 × 1 es más simple que el sistema único 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 tiene 4160 piezas de información, mientras que los sistemas de 32 × 32 tienen cada uno 1056, o aproximadamente una cuarta parte de la información. Sistema 64 × 64.
Algoritmo de descomposición de dominio
Desafortunadamente, por razones técnicas, generalmente 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 respuesta al 64 Sistema × 64. En cambio, el siguiente algoritmo es lo que realmente sucede:
- 1) Comience con una solución aproximada del sistema 64 × 64.
- 2) A partir del sistema 64 × 64, cree dos sistemas 32 × 32 para mejorar la solución aproximada.
- 3) Resuelve los dos sistemas de 32 × 32.
- 4) Ponga las dos soluciones de 32 × 32 "juntas" para mejorar la solución aproximada al sistema de 64 × 64.
- 5) Si la solución aún no es muy buena, repita desde 2.
Hay dos formas en las que esto puede ser mejor que resolver el sistema 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. En segundo lugar, los dos sistemas de 32 × 32 no necesitan resolverse en la misma computadora, por lo que este algoritmo se puede ejecutar en paralelo para utilizar la potencia de varias computadoras.
De hecho, es poco probable que sea eficiente resolver dos sistemas de 32 × 32 en lugar de un sistema de 64 × 64 en una sola computadora (sin usar paralelismo). Sin embargo, si usamos más de dos subdominios, la imagen puede cambiar. Por ejemplo, podríamos usar cuatro problemas de 16 × 16, y existe la posibilidad de que resolverlos sea mejor que resolver un solo problema de 64 × 64, incluso si el algoritmo de descomposición del dominio necesita iterar varias veces.
Un ejemplo técnico
Aquí asumimos que el lector está familiarizado con las ecuaciones diferenciales parciales.
Estaremos resolviendo la ecuación diferencial parcial
- u xx + u yy = f (**)
Imponemos la delimitación en el infinito.
Nos descomponer el dominio R ² en dos subdominios superpuestas H 1 = (- ∞, 1] × R y H 2 = [0, + ∞) × R . En cada subdominio, estaremos resolviendo un BVP de la forma:
- u ( j ) xx + u ( j ) yy = f en H j
- u ( j ) ( x j , y ) = g ( y )
donde x 1 = 1 y x 2 = 0 y tomando la acotación en el infinito como la otra condición de frontera. Denotamos la solución u ( j ) del problema anterior por S ( f , g ). Tenga en cuenta 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 PDE en los subdominios H 1 y H 2 respectivamente. Inicialice k en 1.
- Calcule u ( j ) k + 1 = S ( f , u (3 - j ) k ( x j )) con j = 1,2.
- Aumente k en uno y repita 2 hasta que se logre la precisión suficiente.
Ver también
Referencias
- Barry Smith, Petter Bjørstad, William Gropp, Descomposición de dominios, métodos multinivel en paralelo para ecuaciones diferenciales parciales elípticas, Cambridge University Press 1996
- Andrea Toselli y Olof Widlund, Métodos de descomposición de dominios: algoritmos y teoría, Springer Series in Computational Mathematics, vol. 34 de 2004