Source: http://docplayer.es/1327658-Introduccion-a-los-metodos-de-descomposicion-de-dominio.html
Timestamp: 2018-05-21 23:25:39+00:00

Document:
Introducción a los métodos de descomposición de dominio - PDF
Download "Introducción a los métodos de descomposición de dominio"
1 Introducción a los métodos de descomposición de dominio Salim Meddahi Departamento de Matemáticas Universidad de Oviedo Francisco Javier Sayas Departamento de Matemática Aplicada Universidad de Zaragoza Junio de 1995 Introducción Las siguientes notas han surgido a partir del contenido de un ciclo de cinco conferencias que Salim Meddahi impartió en la Facultad de Ciencias de la Universidad de Zaragoza, dentro de las actividades del Seminario de Matemática Aplicada, en junio de La posterior redacción de las notas fue realizada por Javier Sayas. En este curso introducimos algunos métodos de descomposición de dominio aplicados a la resolución de problemas elípticos de segundo orden en dimensión dos. Recientemente las técnicas de descomposición de dominio han sido considerablemente desarrolladas (ver las monografías [7, 13] y las referencias allí incluidas). Estos métodos constituyen una manera natural de tratar problemas en geometrías complicadas, o bien de estudiar ecuaciones de diferente tipo en diferentes partes del dominio físico. Otra motivación importante para el estudio de dichos métodos es su adaptación al cálculo en paralelo. En general los métodos de descomposición de dominio consisten en sustituir la resolución de un sistema matricial muy grande por un proceso iterativo que precisa la resolución (a veces en paralelo) de varios sistemas de talla reducida en cada iteración. El punto crucial en los diferentes métodos de descomposición de dominio es la transmisión de la información entre los subdominios. Existen dos categorías de métodos de descomposición de dominio. La primera se basa en una partición del dominio en regiones disjuntas: la relación entre las soluciones en los subdominios se expresa mediante condiciones de continuidad en las intercaras. La segunda categoría se basa en una descomposición con recubrimiento. El ejemplo más conocido en esta categoría es el método de Schwarz en el que se resuelven problemas similares en cada subdominio intercambiando las trazas sobre las intercaras. 1
2 El curso se divide en cinco partes. En el primer capítulo introducimos en un caso simple los métodos de Schwarz multiplicativo y aditivo. En el capítulo 2 damos en un marco abstracto general la teoría de convergencia de ambos métodos que servirá de soporte para el estudio de las tres aplicaciones que presentamos en los tres siguientes capítulos. La primera es un método de descomposición de dominio con recubrimiento. Seguidamente estudiamos un método multinivel y finalmente presentamos un método de Schwarz equivalente a un método de descomposición de dominio sin recubrimiento. Para leer esta monografía bastan conocimientos elementales de las técnicas de Análisis Funcional (teoría básica de espacios de Hilbert, de distribuciones y de los espacios de Sobolev más habituales), de su aplicación a las ecuaciones en derivadas parciales lineales elípticas de segundo orden y del análisis del método de los Elementos Finitos. 2
3 1. Descripción de los métodos de Schwarz Consideremos dos dominios Ω 1 y Ω 2 acotados, con geometrías simples y una zona de solapamiento en el plano R 2. Sea Ω := Ω 1 Ω 2. Nos planteamos el problema de contorno en EDP u = f, en Ω, (P ) u Ω = 0. Ω1 Ω2 Figura 1: Un dominio formado por unión de dos dominios con geometrías sencillas 1.1. Método de Schwarz multiplicativo El método de Schwarz es un esquema iterativo para aproximar la solución del problema anterior mediante la resolución de problemas en los dominios Ω 1 y Ω 2 (ver Schwarz[19]). Dado u n, aproximación de u, se resuelve u1 n+1 = f, en Ω 1, u n+1 1 Ω1 Ω = 0, y seguidamente u n+1 1 Ω1 Ω 2 = u n Ω1 Ω 2 ; u n+1 2 = f, en Ω 2, u n+1 2 Ω2 Ω = 0, u n+1 2 Ω2 Ω 1 = u n+1 1 Ω2 Ω 1. La función u n+1 igual a u n+1 2 sobre Ω 2 y a u n+1 1 sobre Ω\Ω 2 se toma como siguiente aproximación de u, reiniciándose el proceso. 3
4 Ω1 Ω1 Ω2 Ω2 Figura 2: El método de Schwarz: se resuelve primero en el dominio Ω 1 ; la restricción del resultado a la zona de Ω 2 contenida en Ω 1 se utiliza como dato de contorno para resolver en Ω 2 donde y La formulación variacional del problema (P ) es, como siempre, u H0(Ω), 1 a(u, v) = f(v), a(u, v) := Ω f(v) := v H 1 0(Ω), u v dx, Ω fvdx. Para escribir la formulación variacional del método de descomposición de dominio consideramos H 1 0(Ω i ) (con i = 1 ó 2) con la siguiente definición H 1 0(Ω i ) := {v H 1 0(Ω) : v Ω\Ωi 0}, es decir, las funciones de H0(Ω 1 i ) se consideran extendidas por cero al resto del dominio Ω (nótese que se mantienen así dentro de H 1 (Ω)), por lo cual H0(Ω 1 i ) puede ser considerado un subespacio de H0(Ω) 1 para i = 1, 2. Con las mismas definiciones para a(, ) y f( ) consideramos los siguientes problemas: partiendo de u n H0(Ω), 1 se resuelve z 1 H0(Ω 1 1 ), (P1 n+1 ) se realiza una primera corrección a(z 1, v 1 ) = f(v 1 ) a(u n, v 1 ), v 1 H0(Ω 1 1 ), u n+ 1 2 = u n + z 1 H 1 0(Ω), se resuelve después (P2 n+1 ) z 2 H0(Ω 1 2 ), a(z 2, v 2 ) = f(v 2 ) a(u n+ 1 2, v 2 ), v 2 H0(Ω 1 2 ), 4
5 y se vuelve a corregir u n+1 = u n z2 H 1 0(Ω). El término independiente del primer problema variacional es el cálculo de una a proyección de la parte del residuo de la iteración anterior que afecta al primer subdominio, es decir, se considera f( ) a(u n, ) ( H 1 0(Ω 1 ) ) y se calcula z 1, el representante por el teorema de Riesz-Fréchet en el citado espacio con a como producto escalar. La corrección u n+ 1 2 da lugar a un nuevo residuo en el segundo subdominio y se realiza una nueva apliación del teorema de representación del dual para volver a corregir Formulación operacional del método de Schwarz multiplicativo Notemos que H 1 0(Ω i ), entendidos como subespacios de H 1 0(Ω), son cerrados, ya que, de hecho, son las clausuras respectivas de D(Ω i ). Por tanto, dado v H 1 0(Ω) podemos definir su a proyección ortogonal sobre H 1 0(Ω i ), denotada P i v, como el único elemento de H 1 0(Ω i ) que cumple Sin más que notar que a(p i v, w i ) = a(v, w i ), w i H 1 0(Ω i ). a(u, v i ) = f(v i ), v i H 1 0(Ω i ) H 1 0(Ω), i = 1, 2, donde u es la solución de la formulación variacional asociada a (P ), el algoritmo de Schwarz multiplicativo se puede reescribir de la siguiente forma: partiendo de u n H0(Ω), 1 se resuelve z 1 H0(Ω 1 1 ), se corrige a(z 1, v 1 ) = a(u u n, v 1 ), v 1 H0(Ω 1 1 ), u n+ 1 2 se resuelve en el segundo subdominio z 2 H0(Ω 1 2 ), y se corrige de nuevo = u n + z 1 H 1 0(Ω), a(z 2, v 2 ) = a(u u n+ 1 2, v 2 ), v 2 H0(Ω 1 2 ), Por tanto, aplicando la definición de P 1, u n+1 = u n z2. z 1 = P 1 (u u n ), 5
6 luego De la misma forma y componiendo u n+ 1 2 = u n + P 1 (u u n ). u n+1 = u n z2 = u n P2 (u u n+ 1 2 ) u u n+1 = (I P 2 )(I P 1 )(u u n ), siendo I el operador identidad en H 1 0(Ω). El operador (I P 2 )(I P 1 ) es llamado operador de amplificación del método. Sea la norma de operadores en L(H 1 0(Ω), H 1 0(Ω)). Entonces se demuestra ver Lions [14] el siguiente resultado: Teorema.Existe δ < 1 tal que (I P 2 )(I P 1 ) < δ. Por tanto, el método de Schwarz multiplicativo converge Método de Schwarz aditivo El método aditivo se obtiene modificando el método multiplicativo de forma que los cálculos para cada paso en cada subdominio se hagan de forma paralela, sin que la información del primero intervenga en la del segundo. Visto como problemas de contorno, conocido u n, aproximación de u, se resuelven u n+1 i = f, en Ω i, u n+1 i Ωi = u n Ωi, i = 1, 2. Como u n+1 se toma la función que en Ω\Ω 2 coincide con u n+1 1, que en Ω\Ω 1 coincide con u n+1 2, y en la intersección de los subdominios se toma u n u n+1 2 u n. Pasando a la formulación variacional (ya abreviada por medio de los operadores de proyección P i ), se tiene: dado u n H0(Ω) 1 se calculan y se corrige z i = P i (u u n ) H 1 0(Ω i ), i = 1, 2 u n+1 = u n + z 1 + z 2. Nótese que, aunque u la solución exacta aparece en el proceso, es bajo una a proyección, luego lo que aparece realmente es f. La expresión de la evolución del error del método es u u n+1 = (I P 1 P 2 )(u u n ), luego el operador de amplificación del método aditivo es I P 1 P 2. 6
7 1.4. Métodos discretos de descomposición de dominio El tratamiento numérico del problema variacional u H0(Ω), 1 (P ) a(u, v) = f(v), v H0(Ω), 1 y de problemas en los subdominios del tipo z i H0(Ω 1 i ), (P i ) a(z i, v i ) = g(v i ), v i H0(Ω 1 i ), se puede realizar por medio del método de los elementos finitos. Supongamos que Ω, Ω 1 y Ω 2 son poligonales. Sea T h una triangulación regular de Ω que respete la descomposición de Ω en los subdominios, es decir, tal que la clausura de cada Ω i sea unión de elementos de la triangulación. Definimos los espacios de elementos finitos V h := {v h H 1 0(Ω) : v h T P 1, T T h }, V h,i := V h H 1 0(Ω i ), i = 1, 2. Dada la base habitual de V h, {ϕ i }, de funciones con soporte mínimo, que valgan uno en el nodo i ésimo y cero en los demás, consideramos la matriz de rigidez A, y el vector F A i,j := a(ϕ j, ϕ i ) F i := f(ϕ i ). El método de los elementos finitos para el problema en el dominio completo se reduce a resolver el sistema A U = F. En cada Ω i realizamos una numeración local de los nodos, definimos de forma similar una base y las matrices de rigidez A 1 y A 2. Las numeraciones locales de nodos en Ω i pueden ser puestas en relación con la numeración global en Ω mediante las matrices Ri t definidas como { 1, si l es el núm. global del nodo k en Ωi, (R t i) l,k := 0, en otro caso, para i = 1, 2. Por tanto si N es el número total de grados de libertad del problema (N = dim V h ) y N i son los grados de libertad en cada subdominio, es decir, N i = dim V h,i, las matrices Ri t son matrices N N i. Multiplicadas a un vector con N i componentes, dan otro de N componentes con los mismos valores nodales en los nodos de Ω i ordenados según la 7
8 numeración global y con ceros en las demás componentes. Por tanto, una función del espacio de elementos finitos V h,i es extendida por cero al resto del dominio Ω. El operador lineal asociado a la matriz traspuesta R i es un operador de restricción, que renumera la información de los nodos de Ω que están en Ω i para adaptarla a la numeración local, e ignora los valores de los grados de libertad que no pertenecen al interior del subdominio. Nota Es sencillo comprobar que en las notaciones anteriores, A i = R i AR T i, i = 1, 2. Resolver por elementos finitos un problema del tipo (P i ) se reduce a resolver sistemas lineales A i U i = G i. Seguidamente daremos las versiones discretas de los dos algoritmos de Schwarz expuestos anteriormente. Estos algoritmos surgen de resolver con elementos finitos cada uno de los subproblemas asociados Método de Schwarz multiplicativo Conocido U n, se calcula z 1 = A 1 1 R 1 (F AU n ), se corrige (nótese que hay que extender hasta V h ) U n+ 1 2 = U n + R t 1z 1 = U n + R t 1A 1 1 R 1 (F AU n ), se calcula en el segundo subdominio y se corrige por segunda vez z 2 = A 1 2 R 2 (F AU n+ 1 2 ) U n+1 = U n R t 2 z 2. Eliminando la etapa intermedia se obtiene la siguiente expresión de la evolución del error del método U U n+1 = (I R t 2A 1 2 R 2 A)(I R t 1A 1 1 R 1 A)(U U n ). El operador matricial realiza la A proyección sobre V h,i. P i = RiA t 1 i R i 8
9 Método de Schwarz aditivo Conocido U n se calculan para i = 1, 2 y se corrige Denotemos z i = A 1 i R i (F AU n ) U n+1 = U n + R t 1z 1 + R t 2z 2 = U n + (R t 1A 1 1 R 1 + R t 2A 1 2 R 2 )(F AU n ). M 1 a Entonces el método aditivo se puede escribir := R t 1A 1 1 R 1 + R t 2A 1 2 R 2. U n+1 = U n + M 1 a (F AU n ). Por tanto, este método se puede entender matricialmente como la aplicación del método de Richardson 1 para el sistema AU = F con matriz de precondicionamiento Ma 1, es decir, se aplica el método iterativo al sistema con M 1 a = A 1. M 1 a AU = M 1 F Nota En algunos casos particulares de subdominios que no contienen nodos comunes, luego N 1 + N 2 = N, y con una adecuada numeración local y global, el método de Schwarz aditivo es igual a un método de Jacobi por bloques. De la misma forma, el método multiplicativo equivale a un método de Gauss-Seidel por bloques. Dada una matriz A simétrica y definida positiva, decimos que una matriz B es A simétrica si (ABU, V ) = (AU, BV ), U, V, es decir, si es autoadjunta respecto del producto escalar (, ) A := (A, ). Ello es equivalente a que la matriz AB sea simétrica (I simétrica). Nótese entonces que la matriz Ma 1 A es A simétrica de forma trivial. De la misma forma decimos que B es A definida positiva (abreviado A DP), si el operador matricial asociado a B es positivo con el producto escalar (, ) A, es decir, si (ABU, U) > 0, U 0. De nuevo, es fácil ver que si B es A simétrica, B es A DP si y sólo si AB es definida positiva. Por una parte U t AM 1 a AU = 2 a (R i AU) t A 1 i (R i AU) 0, U, 1 dado un sistema Bx = b se plantea un esquema iterativo consistente x n+1 = x n + (b Bx n ) = b + (I B)x n, que corrige en cada paso la solución con el residuo; el método convergerá cuando la norma matricial de I B sea suficientemente pequeña 9
10 por ser A 1 y A 2 definidas positivas. Además implica que U t AM 1 a AU = 0 R i AU = 0, i = 1, 2 y, por tanto, AU = 0, de donde se deduce que U es nulo. En consecuencia Ma 1 A es A DP. Por tanto, dada la matriz de precondicionamiento Ma 1 el sistema M 1 a AU = M 1 F puede ser resuelto, en lugar de por el método de Richardson, por el método de Gradiente Conjugado (GC en adelante) definido con el producto escalar (, ) A. De esta forma la convergencia es más rápida ( ) n cond (M U U n 1 a A) 1 A U U 0 A, cond (M 1 a A) + 1 siendo cond el cociente entre el mayor y el menor valor propio. El método de Schwarz aditivo será entendido a partir de ahora como el precondicionamiento dado por Ma 1 del sistema AU = F y su resolución mediante GC. Nótese que el coste de aplicar la matriz Ma 1 a un vector es el de resolver simultáneamente un problema por cada subdominio. El método de Schwarz multiplicativo se puede reescribir de forma similar con la matriz de precondicionamiento M 1 m := ( R t 1A 1 1 R 1 + R t 2A 1 2 R 2 R t 2A 1 2 R 2 R t 1A 1 1 R 1 ) A 1, que ya no tiene las propiedades de simetría de la del aditivo. En cambio, el método multiplicativo, en su forma iterativa, es más rápido que el aditivo, luego no necesita la aceleración de convergencia que da el GC. a 10
11 2. Teoría abstracta de los métodos de Schwarz Sean V un espacio de Hilbert, a : V V R una forma bilineal continua simétrica y V elíptica, f V. Consideramos una familia finita de subespacios cerrados de V, V i, i = 0, 1,..., J de forma que Consideramos el problema u V V = V 0 + V V J. a(u, v) = f(v), v V, que tiene solución única por el teorema de Lax-Milgram. Por el mismo resultado, las a proyecciones sobre V i P i u V i, están bien definidas para todo i Método aditivo Definimos el operador a(p i u, ϕ) = a(u, ϕ), ϕ V i, P := y sustituimos el problema variacional que determina u por una ecuación P u = F a que tenga la misma solución. Dado f, consideramos las soluciones de los problemas u i V i, para i = 0,..., J y definimos Entonces la solución de P i a(u i, ϕ) = f(ϕ), ϕ V i, F a := u u J. u V, (P ) a(u, v) = f(v), v V, 11
12 es solución de P u = F a. Por tanto, la ecuación anterior tiene solución, y si P es inversible, su única solución es la de (P ). Nótese que a(p u, v) = a(p i u, v) = a(p i u, P i v) = a(u, P i v) = a(u, P v), por la simetría de a y la definición de las proyecciones P i, luego el operador P es a simétrico, es decir, autoadjunto respecto del producto escalar a(, ). Además a(p u, u) = a(p i u, u) = a(p i u, P i u) 0, de donde los valores propios de P son no negativos. Más aún, si P u = 0 la expresión anterior implica que todos los P i u = 0. Por tanto, como V = V V J, existe una descomposición u = u u J con u j V j para todo j y u 2 a = a(u, u j ) = j=0 a(p j u, u j ) = 0, j=0 luego P es inyectivo y la ecuación tiene solución única. En dimensión finita, el objetivo es aplicar el método GC para resolver el sistema P u = F a. Si encontramos C 0 y C 1 positivos tales que para todo u, entonces y C 1 0 a(u, u) a(p u, u) C 1 a(u, u), λ max (P ) = máx v 0 λ min (P ) = máx v 0 a(p v, v) a(v, v) C 1, a(p v, v) a(v, v) C 1 0. Por tanto, todos los autovalores son estrictamente positivos, y el condicionamiento de P cumple cond (P ) C 0 C 1 El resultado siguiente debido a P.-L. Lions, ver [14], da una condición suficiente para que se tenga la cota por debajo (la constante C 0 ), que demuestra la (V, a) elipticidad de P. Lema 1 Supongamos que existe una constante C 0 tal que todo u V admite una descomposición u = u i, u i V i, 12
13 que satisface Entonces a(u i, u i ) C 0 a(u, u). a(u, u) C 0 a(p u, u). Demostración. Por la definición de los operadores de proyección P i y aplicando las desigualdades de Cauchy-Schwarz en V con el producto escalar a y en R J+1, se tiene a(u, u) = = a(u, u i ) = a(p i u, u i ) a(p i u, P i u) 1 2 a(ui, u i ) 1 2 ( a(p i u, P i u) C 0 ( ) 1 a(p i u, P i u) ( 2 a(u i, u i ) ) 1 2 a(u, u) 1 2. ) 1 2 En consecuencia a(u, u) C 0 a(p i u, P i u) = C 0 a(p i u, u) = C 0 a(p u, u), que es la cota que queríamos demostrar. Por tanto, en dimensión finita, bajo las hipótesis del lema, λ min (P ) 1 C 0. Nota En general se cumple para todo u a(p 1 u, u) = mín u= u i u i V i a(u i, u i ) y el mínimo se alcanza únicamente en la descomposición u i = P i P 1 u para todo i. Demostración. Si tenemos una descomposición cualquiera u = u i, u i V i, i, 13
14 entonces aplicando de nuevo la definición de los operadores P i y las desigualdades de Cauchy-Schwarz luego a(p 1 u, u) = = = a(p 1 u, u i ) = a(p i P 1 u, u i ) ( a(p i P 1 u, P i P 1 u) ( a(p i P 1 u, P 1 u) ) 1 ) 1 ( = a(u, P 1 u) 1 2 a(u i, u i ) a(p 1 u, u) ( 2 a(u i, u i ) ( 2 a(u i, u i ) ) 1 2 a(u i, u i ). Además la desigualdad es igualdad si y sólo si se tienen las J + 1 igualdades en la desigualdades de Cauchy-Schwarz aplicadas anteriormente, lo que ocurre si y sólo si u i = P i P 1 u,, ) 1 2 ) 1 2 = = para todo i. Partiendo de las hipótesis del Lema 1 se deduce que máx u 0 a(p 1 u, u) a(u, u) = máx u 0 mín J a(u i, u i ) a(u, u) C 0, luego en el caso finito-dimensional λ 1 min (P ) = λ max(p 1 ) C 0. El resultado que sigue estudia la cota contraria. Por conveniencia respecto de los métodos que se aplican en la práctica, el espacio V 0 es tratado de forma diferente. Lema 2 Supongamos que existen ε i,j constantes reales tales que 0 ε i,j 1, ε i,j = ε j,i y que a(u i, u j ) ε i,j a(u i, u i ) 1 2 a(uj, u j ) 1 2, 14
15 para todo u i V i, u j V j y para todo i, j = 1,..., J. Si denotamos por ρ(e) el radio espectral de la matriz (simétrica) entonces para todo u V. E := (ε i,j ) J i,j=1, a(p u, u) (ρ(e) + 1)a(u, u) Demostración. Descomponemos primero a(p u, u) = a( P i u, u) + a(p 0 u, u) y estudiaremos los dos sumandos por separado. Por la desigualdad de Cauchy-Schwarz a(p 0 u, u) a(p 0 u, P 0 u) 1 2 a(u, u) 1 2 = P0 u a a(u, u) 1 2 a(u, u), ya que la norma de P 0 como operador en V con producto escalar a(, ) es menor o igual que uno por ser una proyección ortogonal. Por otra parte a( P i u, P j u) = a(p i u, P j u) donde j=1 v t := Como E es simétrica, entonces y por otra parte, para todo v 0, luego se deduce que a( P i u, i,j=1 ε i,j a(p i u, P i u) 1 2 a(pj u, P j u) 1 2 = i,j=1 = v t Ev, ( ) a(p 1 u, P 1 u) 1 2,..., a(pj u, P J u) 1 2. E 2 = ρ(e t E) 1 2 v t Ev v t v E 2, P j u) ρ(e) j=1 = ρ(e) = ρ(e) a(p i u, P i u) = a(p i u, u) ρ(e)a( 15 P i u, P i u) 1 2 a(u, u) 1 2,
16 aplicando una vez más la desigualdad de Cauchy-Schwarz. Finalmente a( P i u, u) a( P i u, de donde se deduce el resultado. Por tanto, en el caso finitodimensional, P i u) 1 2 a(u, u) 1 2 ρ(e)a(u, u), λ max (P ) ρ(e) + 1. Nota Las hipótesis del lema implican que para todo i, ε i,i = 1, ya que basta tomar el mismo elemento como primera y segunda componente. Por tanto la traza de E es J, de donde se deduce que ρ(e) 1. Restringidos al caso en que V tenga dimensión finita, el método de Schwarz aditivo queda en su versión abstracta como sigue. Se resuelven problemas en los subespacios V i para calcular el término independiente del sistema P u = F a. Seguidamente, como P es simétrica y definida positiva respecto del producto escalar a(, ), el sistema se puede resolver mediante el método de gradiente conjugado con el anterior producto escalar. Cada paso del método GC exige multiplicar un vector por la matriz P, luego calcular las a proyecciones P i del vector, es decir, resolver un problema en el subespacio V i. La velocidad de convergencia viene controlada por el condicionamiento de P (ver sección precedente), luego se puede expresar en función de C 0 y ρ(e) Método multiplicativo Con las notaciones e hipótesis de la introducción de esta teoría abstracta nos planteamos un esquema iterativo para la resolución del problema u V, a(u, v) = f(v), v V. Dada u n aproximación de u, calculamos z 1 = u n z i = z i 1 + P i (u z i 1 ), i = 0,..., J u n+1 = z J. En cada paso se realiza la a proyección sobre uno de los subespacios del residuo del paso anterior. Esta proyección no requiere conocer u, puesto que P i u se conoce resolviendo el problema P i u V i, a(p i u, ϕ) = a(u, ϕ) = f(ϕ), ϕ V i. 16
17 Nótese que estos problemas se resolvían también para llegar a la expresión como ecuación del método aditivo. Denotamos E J := (I P J )... (I P 1 )(I P 0 ), que es el operador de amplificación del error del método. Consideramos su norma E J := sup 0 v V a(e J v, v) a(v, v), que acota la amplificación del error medido en norma a. Teorema 1 (Bramble et al [7]) Supongamos que se satisfacen las hipótesis de los lemas 1 y 2. Entonces 1 E 1. (1 + 2ρ(E) 2 )C 0 Demostración. Sean Obviamente para todo j 0, E 1 := I, E j := (I P j )... (I P 0 ), j = 0,..., J. E j = (I P j )E j 1. Denotamos por T la trasposición de un operador respecto del producto escalar a(, ). Entonces, hemos visto en el estudio del método aditivo que P T i = P i para todo i. En consecuencia es inmediato ver que E T j 1E j 1 E T j E j = E T j 1P j E j 1. Por tanto, sumando Por otra parte, luego para todo j 1. I EJ T E J = Ek 1P T k E k 1. (1) k=0 E j 1 E j = P j E j 1, j 1 I = E j 1 + P k E k 1 (2) k=0 17
18 Notemos que a(p j, ) es una forma bilineal simétrica y semidefinida positiva, luego se puede aplicar la desigualdad de Cauchy-Schwarz respecto de ella. Entonces, fijado j > 0 y aplicando (2) se tiene j 1 a(p j u, u) = a(p j u, E j 1 u) + a(p j u, P 0 u) + a(p j u, P k E k 1 u) a(p j u, u) 1 2 k=1 ( a(p j E j 1 u, E j 1 u) a(pj P 0 u, P 0 u) 1 2 ) a(p j u, P k E k 1 u). j 1 + Aplicando la segunda hipótesis (ver enunciado del lema 2) y simplificando (nótese que a(p j u, P j u) = a(p j u, u) por la definición de P j ) k=1 a(p j u, u) 1 2 j 1 a(pj E j 1 u, E j 1 u) a(pj P 0 u, P 0 u) ε j,k a(p k E k 1 u, P k E k 1 u) 1 2 = k=1 j = a(p j P 0 u, P 0 u) ε j,k a(p k E k 1 u, E k 1 u) 1 2 k=1 a(p j P 0 u, P 0 u) ε j,k a(p k E k 1 u, E k 1 u) 1 2 donde hemos aplicado que ε j,j = 1, como se indica en la subsección anterior. Sea ( ) v t := a(p 1 E 0 u, E 0 u) 1 2,..., a(pj E J 1 u, E J 1 u) 1 2. k=1 Elevando al cuadrado en la expresión anterior y aplicando que (x + y) 2 2(x 2 + y 2 ), se tiene a(p j u, u) 2a(P j P 0 u, P 0 u) + 2 (Ev) 2 i. Por tanto sumando desde j = 1,..., J, a( P j u, u) 2a( P j P 0 u, P 0 u) + 2 Ev 2 2. (3) j=1 En la demostración del Lema 2 se ve que para todo v V a( j=1 P j v, v) ρ(e)a(v, v), j=1 lo que aplicado a P 0 u demuestra, por (3), a(p u, u) = a(p 0 u, u) + a( P j u, u) j=1 a(p 0 u, u) + 2ρ(E)a(P 0 u, P 0 u) + 2 Ev 2 2 (1 + 2ρ(E))a(P 0 u, u) + 2ρ(E) 2 v 2 2, 18
19 puesto que E es simétrica. Notemos que por su definición v 2 2 = = a(p k E k 1 u, E k 1 u) = k=1 a(ek 1P T k E k 1 u, u) = k=1 = a((i E T J E J )u, u) a(p 0 u, u), aplicando (1). Puesto que ρ(e) 1 ver nota en la subsección anterior y como se cumple el Lema 1, C 1 0 a(u, u) a(p u, u) (1 + 2ρ(E) 2 ) ( a(p 0 u, u) + v 2 2) = = (1 + 2ρ(E) 2 )a((i E T J E J )u, u). Por tanto E T J E J 1 1 K, siendo De allí se deduce el resultado, puesto que K := C 0 (1 + 2ρ(E) 2 ). a(e J u, u) a(e J u, E J u) 1 2 a(u, u) 1 2 E T J E J 1 2 a(u, u), para todo u V. Nótese que el operador I E T J E J es el del método simetrizado, ya que E T J E J = (I P 0 )... (I P J 1 )(I P J )(I P J 1 )... (I P 0 ), que corresponde a volver a resolver y corregir en los subespacios en orden inverso una vez se ha llegado al último. Nótese también, que si V = V 1... V J, entonces E = I y C 0 = 1. En el caso finitodimensional el condicionamiento del sistema es 1, luego el gradiente conjugado converge en una sóla iteración. 19
20 3. Método de Schwarz con solapamiento Sea Ω un abierto poliédrico de R 2 y consideremos el problema de contorno div(a(x) u) = f, en Ω, u Ω = 0, siendo A : Ω R 2,2 suficientemente regular, simétrica y uniformemente definida positiva para todo x, y f en las condiciones habituales para estos problemas. Denotaremos a(u, v) := u t A vdx, y Ω f(v) := Ω fvdx. La formulación variacional del problema anterior es, entonces, u H0(Ω), 1 a(u, v) = f(v), v H 1 0(Ω). El problema satisface las hipótesis del teorema de Lax-Milgram, luego tiene solución única Discretización del problema Sea T H una triangulación del dominio Ω T H := {ˆΩ i ; i = 1,..., J}, regular y casi-uniforme. Por tanto el diámetro todos los ˆΩ i es un O(H). Sea δ suficientemente pequeño. Entonces construimos unos subdominios poligonales Ω i, de forma que ˆΩ i Ω i, que la distancia entre las partes de la frontera de Ω i y ˆΩ i contenidas en Ω sea un O(δ) y que el diámetro de Ω i sea un O(H + δ). Realizamos una nueva triangulación regular casi-uniforme T h de Ω que respete las descomposición en subdominios solapados y la triangulación gruesa T H, es decir, exigimos que la clausura de cada ˆΩ i y de cada Ω i sea unión de elementos de la triangulación. Definimos los espacios de elementos finitos P 1 asociados a las dos triangulaciones 2, V H := {v H 1 0(Ω) : v ˆΩi P 1, i = 1,..., J} V h := {v H 1 0(Ω) : v T P 1, T T h } Denotamos por V i := V h H 1 0(Ω i ), i = 1,..., J, 2 si tomamos 2-paralelotopos, el conjunto de interpolación será el transformado de Q 1, en lugar de P 1 20
21 a los elementos finitos con soporte en la clausura de Ω i. Finalmente V 0 := V H es empleado para poner en relación grados de libertad de todos los subdominios y evitar que la transmisión de información del método de Schwarz (de subdominio a subdominio) sea únicamente local. Figura 3: Método con solapamiento: la figura de la izquierda muestra las triangulaciones fina y gruesa; la figura de la derecha muestra cómo uno de los triángulos del mallado grueso da lugar a uno de los dominios simples. Se resuelven problemas discretos en el mallado grueso y en los subdominios. Si para cada i 0, k i es el número de subdominios Ω j con j i tales que Ω i Ω j y k 0 es el número máximo de subdominios a los que puede pertenecer un punto de Ω se tiene la siguiente propiedad: Proposición 1 En las hipótesis dadas sobre regularidad y casi-uniformidad de la triangulación gruesa (con δ suficientemente menor que H) los k i, i = 0,..., J son independientes del número de subdominios J. y Como V V J = V h V 0 = V H V h, estamos en la situación del marco abstracto de los métodos de Schwarz y podemos plantearnos el estudio de la convergencia de los métodos aditivo y multiplicativo. Obviamente, los problemas variacionales en los subespacios es decir, el cálculo de las proyecciones P i son resoluciones de problemas de elementos finitos en los subdominios cuando i 0 o en el mallado grueso de Ω con i = 0. Estudiaremos la convergencia a partir de los dos parámetros que aparecen en la teoría abstracta, C 0 y ρ(e). Estos parámetros serán puestos en relación, a su vez, con los parámetros de la discretización: H, δ y h. 21
22 Las hipótesis del Lema 2 son fáciles de verificar y ρ(e) es estimable inmediatamente a partir de la proposición anterior. El estudio de la constante C 0 es considerablemente más complicado y se realizará en apartados sucesivos. Proposición 2 Las hipótesis del Lema 2 se satisfacen con una matriz E cuyo radio espectral está acotado de la siguiente forma Demostración. Notemos que ρ(e) máx 1 i J (k i + 1). a(u i, u j ) = 0 para todo u i V i, u j V j si Ω i Ω j y que en otro caso se puede tomar, por la desigualdad de Cauchy-Schwarz ε i,j = 1. Por tanto, la fila i ésima de E tiene k i + 1 elementos iguales a 1 y los demás nulos. En consecuencia ρ(e) E = máx 1 i J y el resultado queda demostrado Resultados técnicos j=1 ε i,j = máx 1 i J (k i + 1) Durante esta sección consideraremos un dominio poligonal Ω a la que hay asociada una triangulación regular casi-uniforme T h y un espacio de elementos finitos P 1 continuos, denotado V h, con valores nulos en la frontera de Ω. Las siguientes desigualdades inversas se demuestran fácilmente pasando al triángulo de referencia y aplicando allí la equivalencia de normas en espacios de dimensión finita. Para las transformaciones de las seminormas entre elementos relacionados por transformaciones afines, ver Ciarlet [9]. Lema 3 Existe C independiente de h tal que para todo u h V h. Además u h 1,Ω Ch 1 u h 0,Ω h ( i u h (x i ) 2 ) 1 2, donde la suma se realiza sobre los nodos del mallado, define en V h una norma h uniformemente equivalente a la norma 0,Ω. Finalmente si denotamos β i,j = 1 si los nodos x i y x j son contiguos y cero en caso contrario ( i,j β i,j (u h (x i ) u h (x j )) 2 ) 1 2, (por tanto la suma se realiza sobre nodos vecinos), define en V h una seminorma h uniformemente equivalente a 1,Ω. 22
23 Sea Q h : L 2 (Ω) V h la proyección ortogonal sobre V h respecto del producto escalar de L 2 (Ω). Lema 4 Existe C independiente de h tal que para todo u H 1 0(Ω). u Q h u 0,Ω Ch u 1,Ω, Demostración. Por los resultados de interpolación de Lagrange polinómica en espacios de Sobolev y denotando I h : C 0 ( Ω) V h al operador de interpolación asociado a V h u Q h u 0,Ω u I h u 0,Ω Ch 2 u 2,Ω, para todo u H 2 (Ω). Por definición del operador de proyección ortogonal, u Q h u 0,Ω u 0,Ω para todo u L 2 (Ω). Aplicando, finalmente la teoría de espacios intermedios (ver, por ejemplo, Lions y Magenes [15] o Bramble [1], apéndice B) se tiene u Q h u 0,Ω Ch u 1,Ω para todo u H 1 (Ω). La equivalencia de la norma y la seminorma en H0(Ω) 1 prueba el resultado final. Lema 5 Existe C independiente de h tal que para todo u H 1 0(Ω). Q h u 1,Ω C u 1,Ω, Demostración. Sea ˆQ el operador de proyección ortogonal sobre P 1 respecto de L 2 ( ˆT ) en el elemento de referencia. Aplicando que en un espacio de dimensión finita todas las normas son equivalentes y que ˆQ es estable en L 2 ( ˆT ), se tienen las desigualdades ˆQû 1, ˆT ˆQû 1, ˆT Ĉ ˆQû 0, ˆT Ĉ û 0, ˆT Ĉ û 1, ˆT, para todo û H 1 ( ˆT ). Como para todo c P 0, se deduce que ˆQ(û + c) 1, ˆT = ˆQû + c 1, ˆT = ˆQû 1, ˆT, ˆQû 1, ˆT Ĉ inf c P 0 û + c 1, ˆT Ĉ û 1, ˆT, por la equivalencia de la norma cociente H 1 ( ˆT )/P 0 y la seminorma de H 1 ( ˆT ). 23

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución