PROYECTO FIN DE CARRERA - bibing.us.esbibing.us.es/proyectos/abreproy/5414/fichero/Memoria.pdf · deduce la ecuación de convección-difusión no estacionaria en forma integral, @u

UNIVERSIDAD DE SEVILLA

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA

DEPARTAMENTO DE MATEMÁTICA APLICADA II

PROYECTO FIN DE CARRERA

Aplicación de técnicas de precondicionamiento al

problema del SMS

Autor: JOSÉ VICENTE LORENZO GÓMEZ

Tutor: BOSCO GARCÍA ARCHILLA

2014

Mi gratitud a Bosco García Archillapor el tiempo que me ha dedicadoa lo largo de estos nueve meses.

I

II

Índice general

1. Introducción 1

1.1. Presentación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1. El problema de convección-difusión . . . . . . . . . . . . . . . . . . . . . . . 31.2.2. El método de los elementos nitos . . . . . . . . . . . . . . . . . . . . . . . 51.2.3. Discretización de la ecuación de convección-difusión estacionaria . . . . . . 111.2.4. Técnicas de estabilización. Shishkin Mesh Simulation (SMS ) . . . . . . . . 121.2.5. Similitud con el problema de Stokes . . . . . . . . . . . . . . . . . . . . . . 17

1.3. Objeto del proyecto y campo de aplicación . . . . . . . . . . . . . . . . . . . . . . . 191.3.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.3.2. Alcance y campo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.4. Referencias y programas de cálculo . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2. Métodos iterativos para el SMS 21

2.1. Métodos iterativos frente a métodos directos . . . . . . . . . . . . . . . . . . . . . . 212.2. Cotas para el error relativo del vector solución . . . . . . . . . . . . . . . . . . . . 242.3. Métodos iterativos de subespacios de Krylov . . . . . . . . . . . . . . . . . . . . . . 27

2.3.1. Subespacios de Krylov. Obtención de bases ortogonales mediante el algoritmode Lanczos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.2. El método del gradiente conjugado . . . . . . . . . . . . . . . . . . . . . . . 292.3.3. El método MINRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4. Precondicionamiento de sistema lineales . . . . . . . . . . . . . . . . . . . . . . . . 332.4.1. Necesidad del precondicionamiento . . . . . . . . . . . . . . . . . . . . . . . 332.4.2. Métodos iterativos precondicionados . . . . . . . . . . . . . . . . . . . . . . 342.4.3. Método multigrid algebraico . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.4. Matriz inversa del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.4.5. Precondicionador ideal por bloques . . . . . . . . . . . . . . . . . . . . . . . 40

2.4.5.1. Implementación del precondicionador ideal por bloques . . . . . . 412.4.5.2. Precondicionamiento de S y C = AS−1At . . . . . . . . . . . . . . 41

2.4.6. Precondicionador diagonal por bloques . . . . . . . . . . . . . . . . . . . . . 422.4.7. Generalización del precondicionador por bloques . . . . . . . . . . . . . . . 43

3. Resultados numéricos 45

3.1. Comparación de la resolución de sistemas lineales con laplaciano discreto o matrizS del SMS utilizando AMG-PCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2. SMS con campo de velocidades uniforme. Comparación de los precondicionadorespor bloques ideal y diagonal con ~b = [2, 3] . . . . . . . . . . . . . . . . . . . . . . . 52

3.3. SMS con campo de velocidades circular. Comparación con~b =[2y(1− x2

),−2x

(1− y2

)]de los precondicionadores por bloques ideal y diagonal . . . . . . . . . . . . . . . . 54

3.4. Aproximación exacta del complemento de Schur, Q = C . . . . . . . . . . . . . . . 58

4. Conclusiones 61

III

IV ÍNDICE GENERAL

Anexos 63

A. Implementación en MATLAB 65A.1. Método MINRES precondicionado para el SMS . . . . . . . . . . . . . . . . . . . . 66A.2. Precondicionador general para el método SMS . . . . . . . . . . . . . . . . . . . . 69A.3. Modicaciones en amg_grids_setup.m de IFISS . . . . . . . . . . . . . . . . . . . 70

B. Resultados numéricos adicionales 71B.1. Método SMS con campo de velocidades uniforme. Comparación de los precondicio-

nadores por bloques ideal y diagonal con ~b = [2, 3] . . . . . . . . . . . . . . . . . . 71B.1.1. Red uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71B.1.2. Red no uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

B.2. Método SMS con campo de velocidades circular. Comparación de los precondicio-nadores por bloques ideal y diagonal con ~b =

[2y(1− x2

),−2x

(1− y2

)]. . . . . 79

B.2.1. Red uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79B.2.2. Red no uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

B.3. Campo de velocidades no circular. Aproximación exacta del complemento de Schur,Q = C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85B.3.1. Red uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85B.3.2. Red no uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

B.4. Campo de velocidades circular. Aproximación exacta del complemento de Schur,Q = C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88B.4.1. Red uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88B.4.2. Red no uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Bibliografía 91

Capítulo 1

Introducción

1.1. Presentación

El auge que en las últimas décadas han tenido las técnicas de simulación y el diseño asistidopor ordenador ha sido una consecuencia natural de la rápida evolución que ha experimentado esteúltimo a unos costes que, por otra parte, han ido reduciéndose [6, 27, 37]. Esta tendencia ha permi-tido abordar problemas cada vez más complejos, cuyos modelos incluyen fenómenos que antes eranecesario obviar con el objeto de poder obtener resultados en tiempos razonables. La modelizaciónde los detalles aparentemente más insignicantes conlleva un mayor conocimiento del problemabajo estudio, y en especial, la optimización de la eciencia y los costes de los diseños desarrolla-dos. Sin embargo, ahora que se hace cada vez más evidente que las tecnologías de integración enel silicio están llegando a su límite [22, 23], y ante la incertidumbre de las nuevas herramientasde computación que debieran surgir en años venideros [10, 12, 39], parece lógico poner un mayorénfasis en el estudio de métodos numéricos más ecientes que permitan acelerar la obtención deresultados.

El método de los elementos nitos constituye, a día de hoy, la técnica por excelencia para lasimulación de fenómenos físicos en el ámbito industrial y de investigación [24]. Es sabido que granparte del tiempo empleado en la resolución de un problema mediante este método se reparte entreel mallado del dominio bajo estudio, especialmente cuando se tienen geometrías complicadas [4],y la resolución de los sistemas de ecuaciones lineales resultantes de las ecuaciones diferencialesen derivadas parciales. Esto último adquiere especial relevancia en problemas no lineales, comopueden ser las ecuaciones de Navier-Stokes, donde se hace necesario realizar varias iteracioneshasta la convergencia [13, 32], en cada una de las cuales se resuelve un sistema lineal de tamañoconsiderable. Si además se considera el problema no estacionario, se repite este procedimiento encada paso temporal, lo que pone aún más de relieve la necesidad de acelerar la resolución de lossistemas de ecuaciones resultantes. Conviene resaltar que las matrices de coecientes obtenidas enel método de elementos nitos poseen una estructura bastante especial, ya que a raíz del malladodel dominio presentan un elevado número de elementos nulos.

La eliminación gaussiana convencional constituye un procedimiento general para la resoluciónde sistemas lineales, pero llegados a este punto se revela como una técnica bastante inecienteo, al menos, bastante menos eciente que otras existentes. En ese sentido, conviene en mayormedida el empleo de métodos iterativos de resolución, como pueden ser el de Jacobi, Gauss-Seidelo de sobrerrelajación. Sin embargo, estos presentan enormes inconvenientes que disuaden de suuso en la práctica, bien por no asegurar la convergencia, o bien por hacerlo en un número noacotado de iteraciones. Como alternativa surgen los métodos directos basados en la eliminacióngaussiana [11], que funcionan adecuadamente cuando se tienen miles de grados de libertad, peroque resultan inviables para dimensiones mucho mayores. De forma general, los métodos directosson competitivos para EDP en un dominio bidimensional, siendo necesario recurrir a métodositerativos para resolver EDP tridimensionales [13]. Para salvar el inconveniente expuesto en lastécnicas iterativas convencionales, surgen los métodos iterativos de subespacios de Krylov, basados

1

2 CAPÍTULO 1. INTRODUCCIÓN

en la sucesiva proyección del residuo resultante en cada iteración sobre un subespacio vectorialderivado de la matriz del sistema. La propiedad fundamental de estas técnicas es que se asegurala convergencia en, a lo sumo, un número de iteraciones igual al tamaño del sistema que se quiereresolver.

No obstante, con un mallado que en la mayoría de los casos de interés industrial dispone demás de 107 nodos [24], parece lógico pensar que ni siquiera asegurar la convergencia en ese númerode iteraciones es suciente. Es aquí donde se halla el interés de las técnicas de precondicionamientopara los métodos iterativos de resolución. Grosso modo, esto consiste en resolver un sistema deecuaciones diferente al original y con la misma solución, pero con mejores propiedades desde elpunto de vista de la convergencia. La forma más natural de precondicionar el sistema de ecuacioneses premultiplicar a ambos lados de la igualdad por una matriz. De esta forma se pretende reducir,entre otros, el número de condición del sistema resultante, disminuyendo las iteraciones necesariaspara lograr la convergencia. En la práctica, esto se lleva a cabo mediante el connamiento (cluste-ring) de autovalores a pequeñas regiones de la recta real. Para los métodos iterativos empleados nisiquiera es necesario computar esta matriz de precondicionamiento, sino que basta con obtener elresultado de la acción de esta sobre un vector genérico. Este detalle es importante porque permiteel empleo del método multigrid algebraico como un precondicionador que proporciona resultadosrazonablemente buenos para operadores elípticos.

Quizá la mayor desventaja que presenta el precondicionamiento es que no existe una metodolo-gía general para su desarrollo. Por tanto, se hace necesario recurrir a un estudio exhaustivo de laspropiedades de la matriz del sistema, o bien a precondicionadores ya existentes que presenten unbuen funcionamiento en problemas similares. Esta última forma de proceder es la que se adoptaen este trabajo.

CAPÍTULO 1. INTRODUCCIÓN 3

1.2. Antecedentes

1.2.1. El problema de convección-difusión

La ecuación de convección-difusión [15, 25, 28, 35] es uno de los modelos más extendidos enciencias e ingeniería puesto que estudia los fenómenos de transporte de una magnitud física en elseno de un uido en movimiento, ya sea la concentración de una sustancia, la temperatura o lacantidad de movimiento [33]. Los dos principales agentes motores de este transporte, y que dannombre al problema, son la difusión y la convección. En el primer caso, la variación espacial de lamagnitud bajo estudio genera un ujo proporcional a dicho gradiente. Es el caso de la ley de Fickpara las concentraciones de especies, de la ley de Fourier para la conducción del calor, o de la leyde Newton para la viscosidad, que obedecen a un modelo matemático de la forma1

~q = −ε∇u, (1.2.1)

donde ~q representa el ujo por unidad de supercie, ε es un coeciente de difusión, constanteen la mayoría de situaciones, y u es el campo escalar que representa la magnitud física cuyadistribución se quiere conocer.

Por otra parte, la convección regula el transporte debido al movimiento del propio uido, quearrastra en su corriente especies químicas, su propia temperatura y cantidad de movimiento. Porúltimo, puede existir también la inuencia de fuentes externas, como pueden ser los gradientes depresión o las fuerzas másicas que actúan sobre el uido.

Así, la variación temporal de la magnitud física bajo estudio en un volumen de control Ω concontorno ∂Ω se puede determinar por medio de un balance trivial en el mismo. De esta forma, sededuce la ecuación de convección-difusión no estacionaria en forma integral,

ˆΩ

∂u

∂td$︸︷︷︸

V ariacion temporal

= −ˆ∂Ω

~q · ~ndσ︸︷︷︸T ermino difusivo

−ˆ∂Ω

(~bu)· ~ndσ︸︷︷︸

T ermino convectivo

+

ˆΩ

fd$︸︷︷︸T ermino fuente

, (1.2.2)

donde ~n es el vector normal al contorno ∂Ω que apunta hacia el exterior del dominio Ω; ~b esel campo de velocidades del uido, que a menudo se asume incompresible, por lo que ∇ ·~b = 0;y f es un término fuente o sumidero. Aplicando el teorema de la divergencia se tiene la ecuaciónanterior expresada únicamente mediante integrales de volumen,

ˆΩ

∂u

∂td$ +

ˆΩ

∇ ·(~bu)d$ =

ˆΩ

ε∇2ud$ +

ˆΩ

fd$.

Y como se debe cumplir para todo volumen de control Ω, se obtiene inmediatamente la ecuaciónde convección-difusión en forma diferencial,

∂u

∂t+∇ ·

(~bu)

= ε∇2u+ f. (1.2.3)

Considerando en adelante la hipótesis de incompresibilidad del uido se tiene nalmente

∂u

∂t+~b · ∇u = ε∇2u+ f. (1.2.4)

A la vista de (1.2.4) surge el concepto de derivada material o sustancial,

Du

Dt=∂u

∂t+~b · ∇u, (1.2.5)

que se interpreta como la variación de u asociada a un punto material cuando se sigue a dichopunto en su movimiento [33]. Este operador tiene su justicación en el hecho de haber adoptado

1El modelado de la viscosidad en los uidos newtonianos incompresibles es ligeramente distinto dado que seescribe en forma tensorial, en concreto, τ ′ij = µ (vi,j + vj,i), donde τ ′ij recibe el nombre de tensor de esfuerzosviscosos, y µ es la viscosidad dinámica.


una descripción euleriana del movimiento del uido, en la que el tiempo y las variables espacialesson independientes.

Obsérvese que u podría ser también un campo vectorial, en cuyo caso se tendría una ecuaciónpara cada componente, estando cada una de ellas desacoplada del resto.


1.2.2. El método de los elementos nitos2

Entre los métodos numéricos de simulación utilizados con más profusión en la industria seencuentra el método de los elementos nitos. Desarrollado en la segunda mitad del siglo XX [17,19], este método se ha impuesto sobre muchos otros existentes por sus buenas prestaciones enla resolución de problemas denidos sobre geometrías complejas [4]. Para ello divide el dominioen un número por lo general elevado de subdominios o elementos, cuyos interiores son disjuntos,recibiendo el conjunto de ellos el nombre de triangulación [9].

En adelante suponemos un dominio Ω bidimensional con un contorno ∂Ω poligonal, de formaque es posible dividirlo en un conjunto de triángulos ∆k que denen una triangulación T h. Por otraparte, consideramos que los vértices de triángulos vecinos coinciden, por lo que en ciertos puntos,llamados nodos, se encuentran los vértices de varios elementos distintos. Es decir, rodeando cadanodo existe un conjunto de triángulos que tienen a ese nodo como vértice. Si se etiquetan los nodoscon un índice j, entonces para cada uno de ellos se dene una función φj que es no nula en dichoselementos. Se dice que estas funciones son de pequeño soporte porque fuera de ellos toman siemprevalor nulo. La aproximación más simple, y la que se considera en este trabajo, es aquella que empleafunciones lineales, llamada P1. De modo que φj es una función lineal en cada triángulo, que tomavalor unidad en el nodo j y cero en todos los demás nodos de la red. Esto es, para cada elemento ncon vértices i, j, k, solo hay tres funciones base φi, φj , φk que no toman valor nulo en puntos del

mismo; y la función asociada al nodo j en el elemento n tiene la forma φ(n)j = a

(n)j x+ b

(n)j y+ c

(n)j ,

donde a(n)j , b(n)

j , c(n)j son constantes que se determinan de forma que se cumplan las condiciones

φ(n)j (xi) = 0, φ(n)

j (xj) = 1, φ(n)j (xk) = 0. Por tanto, φj es continua en Ω pero su pendiente es

discontinua en las aristas de los elementos en los que alguno de sus vértices coincide con el nodoxj .

No es difícil darse cuenta de que las funciones descritas guardan cierta similitud con los poli-nomios interpoladores de Lagrange, por lo que una solución aproximada del problema diferencialpuede expresarse como el sumatorio de dichas funciones multiplicadas por el valor aproximado dela función incógnita en cada nodo, y extendido a todos los nodos del dominio. Es decir,

u (x, y) ≈N∑j=1

ujφj (x, y) . (1.2.6)

Si fuéramos capaces de obtener los valores nodales uj , tendríamos la aproximación buscada.Esta es la idea de fondo en el método de los elementos nitos, que proporciona un procedimientopara hallar estos valores. Como no podía ser de otra forma, para ello es necesario recurrir a laEDP que modela el problema bajo estudio, convirtiendo esta en un sistema lineal de ecuacionescuyo vector incógnita contiene precisamente una aproximación a los valores que toma la funciónbuscada en los nodos. Para profundizar en este punto consideramos el problema

L (u) = f en Ω, (1.2.7)

αu+ β∂u

∂n= g en ∂Ω. (1.2.8)

Aunque en lo que sigue se considera, por sencillez, de la forma siguiente,

u = gD en ∂ΩD,∂u

∂n= gN en ∂ΩN , (1.2.9)

∂ΩD ∪ ∂ΩN = ∂Ω, ∂ΩD ∩ ∂ΩN = ∅. (1.2.10)

En (1.2.7), L es un operador diferencial lineal que contiene hasta derivadas de segundo orden.Con un operador de este tipo se modelan la transmisión del calor por conducción, la propagaciónde ondas electromagnéticas, el problema del potencial y los fenómenos de transporte, entre otros.

2Esta sección es, en cuanto a estructura y formalismo matemático, un extracto de ELMAN et al. [13, Chapter1].


Para estos problemas, las derivadas espaciales de segundo orden suelen manifestarse en la formadel laplaciano, ∇2, de forma que se tiene

L = ν∂

∂t+ µ

∂2

∂t2−∇2 +D, (1.2.11)

donde ahora D solo incluye derivadas espaciales de primer orden a lo sumo. En lo que sigueconsideramos ν = µ = 0, por lo que centramos nuestra atención en la situación estacionaria,suponiendo que esta existe. En estos casos, se dice que u es una solución clásica [16, 13] de (1.2.7)-(1.2.8) si tiene derivadas segundas continuas en Ω, derivadas primeras continuas en ΩN = Ω \∂ΩDy es continua en ΩD = Ω \ ∂ΩN , siendo Ω la adherencia3 de Ω. Es decir,

u ∈ C2 (Ω) ,

u ∈ C1(ΩN),

u ∈ C0(ΩD),

Sin embargo, cuando se tienen dominios no regulares o términos fuente discontinuos, la funciónu que satisface (1.2.7) puede no ser lo sucientemente regular como para ser solución clásica.Estas situaciones, bastante frecuentes en la práctica, requieren una descripción alternativa menosrestrictiva que la anterior, conocida como formulación débil del problema [16]. Para ello se hace usode un conjunto de funciones prueba v (test functions), de forma que multiplicando e integrando en(1.2.7) se tiene

ˆΩ

vL (u) d$ =

ˆΩ

vfd$. (1.2.12)

La formulación anterior del problema tiene sentido siempre que las integrales estén bien deni-das. En ese caso, es inmediato comprobar que una solución clásica del problema verica (1.2.12).Lo realmente interesante aquí es que, si v es sucientemente suave, entonces la regularidad exigiblea u puede ser reducida mediante una integración por partes, lo que en el cálculo multivariable setraduce en la aplicación del teorema de la divergencia. Recordando la denición que se hizo de L en(1.2.11), y teniendo en cuenta las condiciones de contorno dadas en (1.2.9), (1.2.12) se transformaen

ˆΩ

∇v · ∇u+ vD (u) d$ =

ˆΩ

vfd$ +

ˆ∂Ω

v∂u

∂ndσ. (1.2.13)

Al reducir los requisitos sobre u, que ahora no está obligada a ser de clase C2 en Ω, el problemapuede tener una solución, llamada solución débil, que no siempre es lo sucientemente suave comopara ser considerada solución clásica. De todos modos, es importante señalar que, si esta soluciónclásica existe, entonces coincide con la solución débil del problema [13].

Para ahondar en la necesidad de que las integrales anteriores se encuentren bien denidasintroducimos el espacio de funciones de cuadrado integrable,

L2 (Ω) =

u : Ω→ R

∣∣∣∣ˆΩ

u2 <∞, (1.2.14)

y se dene la norma en L2 como

‖u‖L2 =

(ˆΩ

u2d$

) 12

. (1.2.15)

3La adherencia de Ω, denotada por Ω, es el conjunto de puntos x tales que toda n-bola B (x) contiene al menosun punto de Ω. Para mayor detalle consultar APOSTOL [1]. A efectos prácticos, en este trabajo basta considerarque Ω consiste en el conjunto de puntos que forman el dominio Ω y su contorno ∂Ω.


Teniendo en cuenta que, por ser L lineal, ∇v ·∇u+vD (u) = ∂v∂x

∂u∂x + ∂v

∂y∂u∂y +av ∂u∂x +bv ∂u∂y +cvu,

el miembro de la izquierda de (1.2.13) se encuentra bien denido si u, v, ∂u∂x ,∂u∂y ,

∂v∂x ,

∂v∂y ∈ L2, lo

cual se puede probar haciendo uso de la desigualdad de Cauchy-Schwarz [13]. Por tanto, si Ω ⊂ R2,restringimos nuestra atención al espacio de funciones de Sobolev H1 dado por

H1 (Ω) =

u : Ω→ R

∣∣∣∣u, ∂u∂x, ∂u∂y ∈ L2 (Ω)

. (1.2.16)

Y se denen los espacios de solución y de prueba [13, 20] como

H1E =

u ∈ H1 (Ω) |u = gD en ∂ΩD

, (1.2.17)

H10 =

v ∈ H1 (Ω) |v = 0 en ∂ΩD

. (1.2.18)

A la vista de lo anterior, si adicionalmente f y gN son funciones de L2, se puede denir laformulación débil de (1.2.7) que se emplea en la práctica como el problema de encontrar u ∈ H1

E

tal queˆ

Ω

∇v · ∇u+ vD (u) d$ =

ˆΩ

vfd$ +

ˆ∂ΩN

vgNdσ, ∀v ∈ H10. (1.2.19)

La idea del método de los elementos nitos consiste en aproximar u por medio de un subespaciode dimensión nita del espacio solución, ShE ∈ H1

E . Obsérvese que las funciones de este espaciocumplen de forma automática las condiciones de tipo Dirichlet en la frontera. Asumimos queSh0 ⊂ H1

0 es un subespacio vectorial n-dimensional, siendo φ1, ..., φn una base del mismo. A lasfunciones φi se les conoce como funciones base (shape functions o trial functions). Para asegurarel cumplimiento de las condiciones Dirichlet se extiende la base con las funciones ϕj de forma que∑nDj=1 u

Dj ϕj aproxima a gD en ∂ΩD, aunque aquí supondremos que dicha aproximación es exacta.

Si tenemos en cuenta dicha suposición, entonces la aproximación de elementos nitos cumple que

uh =

n∑j=1

ujφj +

nD∑j=1

uDj ϕj ∈ ShE . (1.2.20)

Queda por resolver cómo se eligen las funciones de prueba v. Pues bien, en la forma másextendida de elementos nitos dichas funciones coinciden con las funciones base, lo que se conocecomo método de aproximación de Galerkin. Existen otras variantes, conocidas como de Petrov-Galerkin, en las que funciones de prueba y funciones base no coinciden. Identicando ambos tiposde funciones, y sustituyendo en (1.2.19), resulta que se tiene una ecuación por cada función deforma, es decir, una por nodo, y tantas incógnitas como valores nodales es preciso hallar. Portanto, se tienen tantas ecuaciones como incógnitas,

n∑j=1

uj

ˆΩ

∇φi · ∇φj + φiD (φj) d$ =

=

ˆΩ

φifd$ +

ˆ∂ΩN

φigNdσ −nD∑j=1

uDj

ˆΩ

∇φi · ∇ϕj + φiD (ϕj) d$, (1.2.21)

donde se ha hecho uso de la linealidad del operador diferencial D.Con el n de simplicar la notación, siendo u, v ∈ H1, es habitual denir las formas bilineales

l (u, v) =

ˆΩ

∇u · ∇vd$, (1.2.22)

b (u, v) =

ˆΩ

uD (v) d$. (1.2.23)

Obsérvese que el operador l (u, v) es simétrico, es decir, l (u, v) = l (v, u), no así b (u, v). Porotra parte,


(u, v) =

ˆΩ

uvd$, (1.2.24)

〈u, v〉∂Ω =

ˆ∂Ω

uvdσ. (1.2.25)

De forma que (1.2.21) se pueda expresar como

n∑j=1

[l (φi, φj) + b (φi, φj)]uj =

= (φi, f) + 〈φi, gN 〉∂ΩN−

nD∑j=1

[l (φi, ϕj) + b (φi, ϕj)]uDj , (1.2.26)

que nalmente se representa en forma matricial, dando lugar a lo que se conoce como sistemade Galerkin,

Auk = fk, (1.2.27)

en el que A recibe el nombre de matriz de rigidez del sistema. El modo en que se obtie-nen las funciones base, que solo son no nulas en unos pocos elementos del dominio, otorga unaestructura dispersa a la matriz de coecientes del sistema lineal (1.2.27). La construcción deesta matriz es un problema de cuadratura sobre un dominio bidimensional. Para automatizareste proceso se suele convertir cada elemento k, denido por las coordenadas de sus vértices(x

(k)1 , y

(k)1

),(x

(k)2 , y

(k)2

),(x

(k)3 , y

(k)3

), en un triángulo de referencia ∆ref con vértices

(0, 0) , (1, 0) , (0, 1) en el plano (ξ, η). Para ello se utiliza la transformación isoparamétrica dadapor

x (ξ, η) = x1χ1 (ξ, η) + x2χ2 (ξ, η) + x3χ3 (ξ, η)y (ξ, η) = y1χ1 (ξ, η) + y2χ2 (ξ, η) + y3χ3 (ξ, η)

, (1.2.28)

donde se utilizan las funciones base P1 en el elemento de referencia,

χ1 (ξ, η) = 1− ξ − ηχ2 (ξ, η) = ξχ3 (ξ, η) = η

. (1.2.29)

Mediante el cambio de variables dado por (1.2.28)-(1.2.29), se puede realizar una transformacióndesde el elemento de referencia a uno especíco de la triangulación. Sin embargo, en este caso nosinteresa efectuar el proceso en sentido contrario para expresar las integrales en función de las nuevascoordenadas. Para ello, hay que hallar la inversa del cambio, si esta existe. Así, supongamos unafunción ψ (ξ, η) diferenciable, en cuyo caso se obtienen mediante la regla de la cadena sus derivadasparciales

∂ψ

∂ξ=∂ψ

∂x

∂x

∂ξ+∂ψ

∂y

∂y

∂ξ,

∂ψ

∂η=∂ψ

∂x

∂x

∂η+∂ψ

∂y

∂y

∂η,

que se pueden expresar en forma matricial como

(∂ψ∂ξ

∂ψ∂η

)=(∂ψ∂x

∂ψ∂y

)(∂x∂ξ

∂x∂η

∂y∂ξ

∂y∂η

), (1.2.30)

en la que aparece la matriz jacobiana del cambio, J , que para las funciones base P1 es constante,


J =

(∂x∂ξ

∂x∂η

∂y∂ξ

∂y∂η

)=

(x2 − x1 x3 − x1

y2 − y1 y3 − y1

). (1.2.31)

Para que el cambio de variables sea invertible, el determinante de la matriz jacobiana debe serno nulo, como se comprueba a continuación.

|J | =∣∣∣∣x2 − x1 x3 − x1

y2 − y1 y3 − y1

∣∣∣∣ =

∣∣∣∣∣∣1 1 1x1 x2 x3

y1 y2 y3

∣∣∣∣∣∣ = 2 |∆k| =|∆k||∆ref |

6= 0,

donde |∆k| denota el área del elemento k. Por tanto, podemos estar seguros de que existe latransformación del elemento ∆k al ∆ref , de modo que se puede invertir el cambio de variables,

∂ψ

∂x=∂ψ

∂ξ

∂ξ

∂x+∂ψ

∂η

∂η

∂x,

∂ψ

∂y=∂ψ

∂ξ

∂ξ

∂y+∂ψ

∂η

∂η

∂y,

que en forma matricial resulta

(∂ψ∂x

∂ψ∂y

)=(∂ψ∂ξ

∂ψ∂η

)( ∂ξ∂x

∂ξ∂y

∂η∂x

∂η∂y

). (1.2.32)

Donde queda por determinar los coecientes ∂ξ∂x ,

∂ξ∂y ,

∂η∂x ,

∂η∂y . Para ello se aplica la regla de

Cramer en (1.2.30),

∂ψ

∂x=

∣∣∣∣∣∂ψ∂ξ ∂y∂ξ

∂ψ∂η

∂y∂η

∣∣∣∣∣|J |

=1

|J |

(∂y

∂η

∂ψ

∂ξ− ∂y

∂ξ

∂ψ

∂η

),

∂ψ

∂y=

∣∣∣∣∣∂x∂ξ ∂ψ∂ξ

∂x∂η

∂ψ∂η

∣∣∣∣∣|J |

=1

|J |

(∂x

∂ξ

∂ψ

∂η− ∂x

∂η

∂ψ

∂ξ

).

Y adoptando de nuevo una representación matricial se tiene

(∂ψ∂x

∂ψ∂y

)=(∂ψ∂ξ

∂ψ∂η

)( ∂ξ∂x

∂ξ∂y

∂η∂x

∂η∂y

)=

1

|J |

(∂ψ∂ξ

∂ψ∂η

)( ∂y∂η −∂x∂η−∂y∂ξ

∂x∂ξ

)=

=1

2 |∆k|

(∂ψ∂ξ

∂ψ∂η

)(y3 − y1 x1 − x3

y1 − y2 x2 − x1

). (1.2.33)

Dado que las funciones base P1 son de pequeño soporte, solo tres de ellas son no nulas en cadaelemento4. Es una práctica habitual calcular la matriz de rigidez de cada elemento k y despuésensamblarlas todas en una matriz de rigidez global,

n∑j=1

( ∑∆k∈Th

ˆ∆k

∇φi · ∇φj + φiD (φj) d$

)uj =

=∑

∆k∈Th

ˆ∆k

φifd$ +∑

∆k∈Th

ˆ∂ΩN∩∂∆k

φigNdσ−

nD∑j=1

uDj

( ∑∆k∈Th

ˆ∆k

∇φi · ∇ϕj + φiD (ϕj)

)d$.

4Esto se suele expresar diciendo que en dicha discretización los elementos tienen tres grados de libertad.


Si se denotan las funciones base no nulas en el elemento k porφ

(k)i

i=1,...,nk

con nk = 3 el

número de grados de libertad de cada elemento, tomando D = a ∂∂x + b ∂∂y + c, la matriz de rigidez

del elemento k se calcula como

a(k)ij =

ˆ∆k

(∂φ

(k)i

∂x

∂φ(k)j

∂x+∂φ

(k)i

∂y

∂φ(k)j

∂y+

+aφ(k)i

∂φ(k)j

∂x+ bφ

(k)i

∂φ(k)j

∂y+ cφ

(k)i φ

(k)j

)dxdy. (1.2.34)

Y teniendo en cuenta (1.2.33),

a(k)ij =

ˆ∆ref

1

2 |∆k|

((y

(k)3 − y(k)

1

) ∂χi∂ξ

+(y

(k)1 − y(k)

2

) ∂χi∂η

)((

y(k)3 − y(k)

1

) ∂χj∂ξ

+(y

(k)1 − y(k)

2

) ∂χj∂η

)+

+1

2 |∆k|

((x

(k)1 − x(k)

3

) ∂χi∂ξ

+(x

(k)2 − x(k)

1

) ∂χi∂η

)((

x(k)1 − x(k)

3

) ∂χj∂ξ

+(x

(k)2 − x(k)

1

) ∂χj∂η

)+

+aχi

((y

(k)3 − y(k)

1

) ∂χj∂ξ

+(y

(k)1 − y(k)

2

) ∂χj∂η

)+

+ bχi

((x

(k)1 − x(k)

3

) ∂χj∂ξ

+(x

(k)2 − x(k)

1

) ∂χj∂η

)+ 2 |∆k| cχiχjdξdη. (1.2.35)

De forma exacta, para el elemento de referencia considerado, la integral doble se calcularíacomo

´ 1

0

´ 1−η0

Φ (ξ, η) dξdη. Obsérvese que para las funciones base P1, las derivadas parciales∂χi∂ξ ,

∂χj∂η son constantes, de forma que si los coecientes a, b y c son también constantes o polinomios, lamatriz de rigidez se obtiene de forma trivial. Esto ocurre, por ejemplo, con la matriz que se derivadel laplaciano. En otro caso, suele ser necesario recurrir a reglas de cuadratura numérica.


1.2.3. Discretización de la ecuación de convección-difusión estacionaria

El problema de convección-difusión estacionario (no dependiente del tiempo) consiste en unaecuación diferencial en derivadas parciales que, con las condiciones de contorno adecuadas, mo-dela la distribución en el régimen permanente de un contaminante en el seno de un uido cuyomovimiento viene dado por un campo de velocidades estacionario y conocido de antemano, ~b,

− ε∇2u+~b · ∇u = f, en Ω, (1.2.36)

u = gD en ∂ΩD,∂u

∂n= gN en ∂ΩN . (1.2.37)

En cuanto a la frontera ∂Ω, esta se divide en una región sobre la que se imponen condicionesDirichlet, ∂ΩD, y otra sobre la que se tienen condiciones de contorno de Neumann, ∂ΩN , de talmodo que se cumple que el contorno completo es la unión disjunta de ambas regiones, ∂Ω =∂ΩD ∪ ∂ΩN . Por otra parte, si se considera el vector normal exterior al contorno, ~n, se distinguena su vez tres regiones diferentes en función de que el uido entre o salga a través de él,

∂Ω+ =x ∈ ∂Ω | ~b · ~n > 0

∂Ω0 =

x ∈ ∂Ω | ~b · ~n = 0

∂Ω− =

x ∈ ∂Ω | ~b · ~n < 0

, (1.2.38)

donde es importante destacar que ∂Ω− ∈ ∂ΩD. Identicando el operador diferencial L =

−ε∇2 +~b ·∇ se tiene que D =~bε ·∇, por lo que es inmediato obtener el sistema de Galerkin a partir

de (1.2.21),

n∑j=1

uj

ˆΩ

ε∇φi · ∇φj + φi~b · ∇φjd$ =

=

ˆφifd$ +

ˆ∂ΩN

εφigNdσ −nD∑j=1

uDj

ˆΩ

ε∇φi · ∇ϕj + φi~b · ∇ϕjd$. (1.2.39)

Una cuestión que es importante señalar, en cuanto que condiciona la resolución del sistema linealresultante, es que la forma bilineal b (φi, φj) no es simétrica, por lo que la matriz de coecientesA tampoco lo es. Esto implica que no se puedan emplear los métodos del gradiente conjugado yMINRES, siendo necesario recurrir a métodos para matrices no simétricas como, por ejemplo, elmétodo GMRES (Generalized Minimum Residual method), basado en el proceso de Arnoldi. Elprincipal inconveniente de los procedimientos para matrices no simétricas es, en general, su mayorcosto y requerimiento de memoria. Sin embargo, tampoco esto será un problema puesto que eneste trabajo se resuelve la ecuación de convección-difusión mediante un método que genera unamatriz simétrica.


1.2.4. Técnicas de estabilización. Shishkin Mesh Simulation (SMS)5

La ecuación de convección-difusión es un problema lineal que presenta ciertas dicultades encondiciones de convección dominante, es decir, cuando el parámetro ε

|~b|Les sucientemente pe-

queño, siendo L una longitud característica del dominio considerado. En concreto, la apariciónde capas límite en regiones del contorno introduce oscilaciones espurias que contaminan la solu-ción numérica del problema de elementos nitos asociado. Para evitarlo, se hace necesario utilizarredes tan nas que convierten el cálculo de la aproximación numérica en una tarea prohibitiva.No obstante, desde hace unas décadas han aparecido múltiples métodos de estabilización, siendomuy utilizadas la técnica SUPG (Streamline Up-wind Petrov-Galerkin) [3, 8, 21, 28, 31, 35] o lasmallas Shishkin [25, 35]. Este último es un procedimiento de mallado adaptativo consistente enel empleo de dos redes que contienen el mismo número de elementos, aunque una de ellas ocupauna región más reducida y es en la que se encuentra incluida la capa límite. Esta técnica presentael inconveniente de no adaptarse bien a dominios irregulares. En García-Archilla [18] se proponeun método basado en la simulación de mallas Shishkin que obtiene la solución en el interior deldominio eliminando la oscilaciones espurias sin resolver de forma exhaustiva la capa límite. Grossomodo, consiste en la resolución de un problema de optimización de elementos nitos sujeto a unaserie de restricciones, del que se deriva un sistema de ecuaciones lineal cuya solución incluye ladel problema de elementos nitos. Presenta la ventaja de que no resuelve las capas límites, por loque se ahorra un elevado número de ecuaciones asociadas a los nodos donde aparecen. Hay quemencionar que dicho método presenta un funcionamiento adecuado cuando se utilizan funcionesbase de tipo P1.

Problema 1. Sea el problema dado por

− ε∇2u+~b · ∇u+ cu = f, en Ω, (1.2.40)

sujeto a las condiciones de contorno establecidas en (1.2.37). Suponemos que el dominio Ωpresenta un contorno poligonal o poliédrico. Sea Th una partición de dicho dominio en elementosque tienen solo caras y vértices en común. Para cada uno de estos elementos τ ∈ Th, sea N (τ) elconjunto de sus vértices, y sea

N h = ∪τ∈ThN (τ)

el conjunto de todos los vértices de Th. Por otra parte, se dene el espacio Xh de funciones baseP1, que se compone de

Xh = X−h ⊕ Vh ⊕X+h ,

con φh ∈ Vh si ϕh = 0 en ∂ΩD

φh ∈ X−h si ϕh = 0 en ∂ΩD \ ∂Ω−.

φh ∈ X+h si ϕh = 0 en ∂Ω−

Se elige uDh ∈ X−h ⊕X

+h que sea una buena aproximación a las condiciones de contorno Dirichlet,

de forma que la aproximación buscada en el dominio es uh ∈ uDh + Vh que satisface

a (uh, φi) = (f, φi) + ε 〈gN , φi〉∂ΩN, ∀φi ∈ Vh, (1.2.41)

dondea (v, w) = εl (v, w) +

(~b · ∇v + cv, w

), v, w ∈ H1 (Ω) .

Por otra parte, se dene también el operador

Lh (vh) = ~b · ∇vh + cvh, ∀vh ∈ Vh. (1.2.42)

5Extracto de García-Archilla [18].


Para incluir el efecto de estabilización del método SUPG, se tiene, en lugar de (1.2.41),

ah (uh, φi) = (f, φi)h + ε 〈gN , φi〉∂ΩN, ∀φi ∈ Vh, (1.2.43)

con

ah (uh, φi) = a (uh, φi) +∑τ∈Th

δτ

(Lτ (uh) ,~b · ∇φi

)τ, (1.2.44)

(f, φi)h = (f, φi) +∑τ∈Th

δτ

(f,~b · ∇φi

)τ, (1.2.45)

donde δτ es un parámetro que se debe ajustar adecuadamente y Lτ es Lh restringido al elementoτ .

A continuación se dene ∂Ω0+D =

(∂Ω+ ∪ ∂Ω0

)∩ ∂ΩD. Consideramos un dominio adecuado

Ω+h a especicar6, y tal que ∂Ω0+

D ∈ ∂Ω+h . Se denota por Nδ y por Nδ el conjunto de vértices en

∂Ω+h \ ∂ΩD y sus índices, respectivamente, es decir,

Nδ = N(∂Ω+

h \ ∂ΩD),

Nδ = j ∈ N | xj ∈ Nδ .

El problema consiste en encontrar la aproximación uh ∈ uDh + Vh que verica

mınuh∈uDh +Vh,t∈RNδ

1

2‖Lh (uh)− f‖2L2(Ω\Ω+

h ) , (1.2.46)

sujeto a las restricciones

ah (uh, φi) +∑j∈Nδ

tjφi (xj) = (f, φi)h + ε 〈gN , φi〉∂ΩN, ∀φi ∈ Vh. (1.2.47)

Recordando la expresión de uh,

uh =

n∑j=1

ujφj +

nD∑j=1

uDj ϕj ,

y teniendo en cuenta que Lh es un operador lineal, se obtiene la función lagrangiana del pro-blema de optimización planteado en (1.2.46)-(1.2.47),

L =1

2

ˆΩ\Ω+

h

n∑j=1

ujLh (φj) +

nD∑j=1

uDj Lh (ϕj)− f

2

d$+

+

n∑i=1

zi

n∑j=1

ujah (φj , φi) +

nD∑j=1

uDj ah (ϕj , φi) +∑j∈Nδ

tjφi (xj)− (f, φi)h − ε 〈gN , φi〉∂ΩN

,

donde zi es el multiplicador de Lagrange asociado a la restricción i-ésima de (1.2.47).Derivando respecto de las variables del problema e igualando a cero se obtienen las condiciones

que debe vericar la solución óptima,

∂L∂uk

= 0, ∀φk ∈ Vh ⇒

6La construcción de Ω+h se detalla en [18] y queda fuera del alcance de este trabajo.


ˆΩ\Ω+

h

n∑j=1

ujLh (φj) +

nD∑j=1

uDj Lh (ϕj)− f

Lh (φk) d$ +

n∑i=1

ziah (φk, φi) = 0⇒

ˆΩ\Ω+

h

Lh (φk)Lh (uh) d$ +

n∑i=1

ziah (φk, φi) =

ˆΩ\Ω+

h

Lh (φk) fd$,

∂L∂tk

= 0, ∀k ∈ Nδ ⇒n∑i=1

ziφi (xk) = 0, ∀k ∈ Nδ.

Problema 2. Resolver el problema anterior equivale a encontrar uh ∈ uDh +Vh, zh ∈ Vh y t ∈ RNδ

tales que

(Lh (uh) , Lh (φi))L2(Ω\Ω+h ) + ah (φi, zh) = (Lh (φi) , f)L2(Ω\Ω+

h ) , ∀φi ∈ Vh, (1.2.48)

zh (xj) = 0, ∀j ∈ Nδ, (1.2.49)

ah (uh, φi) +∑j∈Nδ

tjφi (xj) = (f, φi)h + ε 〈gN , φi〉∂ΩN, ∀φi ∈ Vh, (1.2.50)

donde los multiplicadores de Lagrange z1, ..., zn asociados a las restricciones dadas en (1.2.50)se encuentran recogidos en la función zh ∈ Vh, cuyo valor en cada nodo es el correspondientemultiplicador.

Sean φ1, ..., φn ∈ Vh las funciones base que toman valor unidad en un solo nodo y cero en elresto. Denimos las matrices A y S de dimensión n× n, cuyos elementos vienen dados por

aij = ah (φi, φj) , 1 ≤ i, j ≤ n, (1.2.51)

sij = (Lh (φi) , Lh (φj))L2(Ω\Ω+h ) , 1 ≤ i, j ≤ n. (1.2.52)

Sea la matriz E de orden n×m cuyas columnas son las de la matriz identidad n×n correspon-dientes a los índices recogidos en Nδ. Entonces, los valores nodales de uh, los valores tj , ∀j ∈ Nδ,y los valores nodales de zh se obtienen resolviendo un sistema lineal de ecuaciones cuya matriz decoecientes es simétrica, S 0 At

0 0 Et

A E 0

. (1.2.53)

Problema 3. El sistema de ecuaciones dado en (1.2.48)-(1.2.50) proporciona los valores nodalesde uh, los valores tj , ∀j ∈ Nδ, y los valores nodales de zh. No obstante, únicamente los primerosresultan de interés. Es fácil darse cuenta de que las incógnitas tj solo aparecen en (1.2.50), concre-tamente en aquellas ecuaciones correspondientes a funciones base tales que φi (xj) 6= 0, ∀j ∈ Nδ,por lo que podemos eliminarlas al no resultar de interés. Esto quiere decir que se desechan las mrestricciones de (1.2.50) asociadas a las funciones base de los nodos de Nδ.

Por otra parte, teniendo en cuenta (1.2.49), los valores que toma zh no son desconocidos en losnodos j ∈ Nδ. De hecho, al ser nulos, las funciones base φi (xj) 6= 0, ∀j ∈ Nδ no aparecen en eldesarrollo de zh, con lo que para el cálculo de uh y zh basta con resolver el sistema


(Lh (uh) , Lh (φi))L2(Ω\Ω+h ) + ah (φi, zh) = (Lh (φi) , f)L2(Ω\Ω+

h ) , ∀φi ∈ Vh, (1.2.54)

ah (uh, φi) = (f, φi)h + ε 〈gN , φi〉∂ΩN, ∀φi ∈ Vh | φi (xj) = 0, ∀j ∈ Nδ. (1.2.55)

Por tanto, se tiene ahora un sistema lineal cuya matriz de coecientes sigue siendo simétrica,pero la matriz A es ahora rectangular de orden (n−m)× n.

Problema 4. Problema del SMS (Shishkin Mesh Simulation).

Consideramos por último el caso particular del problema general dado en (1.2.40), con c = 0.Por otra parte, supondremos que solo tenemos condiciones de tipo Dirichlet en la frontera, por loque ∂ΩN = ∅ en (1.2.37). Haciendo efectivas estas especicaciones, se tiene

(~b · ∇uh,~b · ∇φi

)L2(Ω\Ω+

h )+ ah (φi, zh) =

(~b · ∇φi, f

)L2(Ω\Ω+

h ), ∀φi ∈ Vh, (1.2.56)

ah (uh, φi) = (f, φi) +∑τ∈Th

δτ

(f,~b · ∇φi

)τ, ∀φi ∈ Vh | φi (xj) = 0, ∀j ∈ Nδ, (1.2.57)

donde

ah (v, w) = εl (v, w) +(~b · ∇v, w

)+∑τ∈Th

δτ

(~b · ∇v,~b · ∇w

)τ, v, w ∈ H1 (Ω) . (1.2.58)

Este será, en adelante, el sistema lineal bajo estudio, para el que se eligen las funciones base detipo P1. Recordemos que esto quiere decir que se consideran aproximaciones lineales a trozos. Lamatriz S es simétrica y de orden n× n, y la matriz A tiene dimensión (n−m)× n, por lo que elsistema resultante es simétrico. Llamamos matriz de rigidez del método SMS a

K =

(S At

A 0

), (1.2.59)

con

sij =

ˆΩ\Ω+

h

(~b · ∇φi

)(~b · ∇φj

)d$, 1 ≤ i, j ≤ n,

aij = ε

ˆΩ

∇φi · ∇φjd$ +

ˆΩ

(~b · ∇φi

)φjd$ +

∑τ∈Th

δτ

ˆτ

(~b · ∇φi

)(~b · ∇φj

)d$,

∀φi ∈ Vh | φi (xj) = 0, ∀j ∈ Nδ.

Para los problemas en los que K no tiene autovalores nulos, solo resultan de interés las pro-piedades de dicha matriz. Por tanto, en los estudios posteriores no se hará mención al vector detérminos independientes.


Denición. Las matrices reales y simétricas, R y T son congruentes si R = PTP t para algunamatriz P no singular.

Teorema. (Ley de inercia de Sylvester) Matrices congruentes tienen el mismo número de auto-valores positivos, negativos y nulos.

La demostración de este teorema se puede consultar en [34].Mediante una transformación congruente, la matriz dada en (1.2.59) se puede expresar como(

S At

A 0

)=

(I 0

AS−1 I

)(S 00 −AS−1At

)(I S−1At

0 I

). (1.2.60)

Como consecuencia, la matriz de coecientes del método SMS es indenida, puesto que para losproblemas de interés se demuestra en [18] que S es denida positiva. Por tanto, sus autovalores sontodos positivos, y por otra parte, −AS−1At es denida negativa y sus autovalores son negativos.

Esto es importante a la hora de elegir un método iterativo de resolución basado en subespaciosde Krylov. Así, el método del gradiente conjugado converge en el caso de matrices simétricas ydenidas positivas, pero puede fallar con matrices indenidas. En este caso es aconsejable recurriral método MINRES, que conlleva un mayor número de operaciones por iteración, pero resulta másrobusto.


1.2.5. Similitud con el problema de Stokes7

Las ecuaciones de Stokes constituyen un modelo de ujo incompresible y viscoso a bajos númerosde Reynolds. Se utilizan para simular el movimiento de un uido que se mueve a baja velocidad yconnado en un espacio de reducidas dimensiones. Vienen dadas por el sistema

−∇2~u+∇p = 0,∇ · ~u = 0,

(1.2.61)

donde ~u representa la velocidad del uido y p es el campo de presiones. La primera ecuaciónes consecuencia del teorema de conservación de la cantidad de movimiento aplicado a un volumenuido, mientras que la segunda representa la conservación de la masa. Las ecuaciones anterioresestán sujetas a condiciones de contorno en la frontera del dominio dadas por

~u = ~b en ∂ΩD,∂~u

∂n− ~np = ~s en ∂ΩN , (1.2.62)

siendo ∂~u∂n = ~n ·∇~u, y el contorno del dominio la unión disjunta de las fronteras donde se aplican

condiciones Dirichlet y Neumann, es decir, ∂Ω = ∂ΩD ∪ ∂ΩN . Por otra parte, son válidas en esteproblema las deniciones recogidas en (1.2.38).

En este caso, se aproxima la solución al problema por

~uh =

nu∑j=1

uj~φj +

nD∑j=1

uDj ~ϕj ∈ XhE , (1.2.63)

ph =

np∑k=1

pkψk ∈Mh, (1.2.64)

siendo XhE yMh subespacios de dimensión nita de H1

E y L2, respectivamente, y donde ~φi sonlas funciones base asociadas al campo de velocidades, y ψk las correspondientes a la distribuciónde presiones. Esta forma de proceder, en el que las dos funciones de interés son aproximadaspor espacios distintos, se denomina método de elementos nitos mixtos. No en vano se tiene que~φj ∈ Xh

0 , j = 1, ..., nu, con Xh0 ⊂ H1

0; ~ϕj ∈ XhE , j = 1, ..., nD, con Xh

E ⊂ H1E ; y ψk ∈ Mh,

k = 1, ..., np conMh ⊂ L2 (Ω), siendo

H1E =

~u ∈ H1 (Ω) | ~u = ~b en ∂ΩD

, (1.2.65)

H10 =

~v ∈ H1 (Ω) | ~u = ~0 en ∂ΩD

. (1.2.66)

Conviene recordar que las funciones base ~ϕj , con j = 1, ..., nD, interpolan ~b en la frontera deldominio donde existan condiciones Dirichlet, pues solo coinciden con el valor exacto en los nodosde la misma. Por tanto, no es estrictamente exacto armar que ~uh ∈ Xh

E .La discretización de elementos nitos del problema de Stokes da lugar a un sistema lineal

de ecuaciones conocido como problema de punto de silla (saddle point problem), que surge confrecuencia en otras áreas de las matemáticas y la física, y cuya resolución ha sido ampliamenteestudiada [2, 5]. Este sistema tiene una estructura en bloques como la que sigue,(

A Bt

B 0

)(ukpk

)=

(fg

), (1.2.67)

donde

A = [aij ]nu×nu , aij =

ˆΩ

∇~φi : ∇ ~φjd$, (1.2.68)

B = [bkj ]np×nu , bkj = −ˆ

Ω

ψk∇ · ~φjd$, (1.2.69)

7Extracto de ELMAN et al. [13, Chapter 5].


f = [fi]nu×1 , fi =

ˆ∂ΩN

~s · ~φid$ −nD∑j=1

uDj

ˆΩ

∇~φi : ∇ ~ϕjd$, (1.2.70)

g = [gk]np×1 , gk =

nD∑j=1

uDj

ˆΩ

ψk∇ · ~ϕjd$, (1.2.71)

Haciendo uso de la ley de inercia de Sylvester se llega a la conclusión de que la matriz decoecientes en (1.2.67) es indenida, del mismo modo que ocurre en el SMS. Se hace patente que,aunque modelan fenómenos muy diferentes, ambos problemas requieren la resolución de un sistemalineal de ecuaciones cuyas matrices de coecientes presentan características comunes, a saber:

Son matrices dispersas, simétricas e indenidas.

Presentan una estructura en bloques en la que el bloque (1, 1) es denido positivo, los bloques(1, 2) y (2, 1) son rectangulares, y el bloque (2, 2) es nulo.

Ello sugiere el empleo en el SMS de las técnicas de precondicionamiento bien conocidas para elproblema de Stokes. Desde la óptica del sistema lineal resultante, cabe mencionar como diferenciasutil entre ambos problemas el hecho de que en las ecuaciones de Stokes, si la velocidad está jadaen todo el contorno, entonces (1.2.67) no tiene solución única. Esto se debe a que, como aparece en(1.2.61) el gradiente de la presión, esta se encuentra determinada salvo una constante, no existiendouna condición de contorno de tipo Neumann que la je. De esta forma, se debe imponer algunarestricción adicional, siendo habitual que el valor medio de la distribución de presiones sea nulo.


1.3. Objeto del proyecto y campo de aplicación

1.3.1. Objetivo

En el presente trabajo se estudian métodos de precondicionamiento para el sistema lineal disper-so (1.2.59), que surge en la discretización de elementos nitos del problema de convección-difusiónestacionaria cuando se utiliza la técnica de estabilización SMS. Este sistema de ecuaciones guardacierta similitud con el que se tiene tras discretizar el problema de Stokes. Es por esta razón quese estudia el comportamiento de algunos de los precondicionadores conocidos y efectivos para esteúltimo problema. Se medirá la bondad del precondicionador en términos del coste computacionaldel método iterativo empleado para converger a la solución, y del error relativo relativo con que lohaga.

1.3.2. Alcance y campo de aplicación

Este trabajo se enmarca dentro de la mecánica de uidos computacional (CFD), que recogeaspectos puntuales de las siguientes disciplinas relacionadas con la ingeniería:

Mecánica de uidos y fenómenos de transporte. Se pretende acelerar la resolución de unsistema lineal de ecuaciones que permite simular el transporte convectivo y difusivo de uncampo escalar que puede representar la concentración de un contaminante en un uido o ladistribución de temperaturas en el mismo. La aplicación del método SMS es de interés ensituaciones de convección dominante, donde es característica la aparición de delgadas capaslímites en los contornos del dominio donde hay jadas condiciones de tipo Dirichlet. En ellasse produce un cambio muy rápido de la magnitud bajo estudio, siendo obligado el empleo demallas muy nas que encarecen considerablemente la resolución del problema.

Matemática aplicada. La convección-difusión estacionaria se modela mediante una EcuaciónDiferencial en Derivadas Parciales con las condiciones de contorno apropiadas, que se resuelveutilizando el método de los elementos nitos. De manera concisa, esta técnica consiste enrepresentar la solución aproximada del problema en un espacio de funciones sencillas dedimensión nita. La solución del problema pasa por la resolución de un sistema lineal deecuaciones que se puede afrontar empleando, entre otras técnicas, métodos iterativos basadosen subespacios de Krylov, lo que conlleva el empleo de herramientas del Álgebra Lineal.Asimismo, los algoritmos de resolución utilizados se enmarcan dentro del Análisis Numérico.

Programación y análisis de algoritmos.

Como ya comentamos, no existe un procedimiento general para la obtención de precondicionadores.Por tanto, los que en este trabajo se utilicen no serán válidos, en general, para la resolución de otrosproblemas. Sin embargo, un objetivo que se persigue es comprender de forma somera cómo funcio-nan las técnicas de precondicionamiento para métodos iterativos de resolución de sistemas lineales,lo que sí resulta de aplicación para la búsqueda de precondicionadores en otros problemas, por muydistintos que sean. Por otra parte, se pretende acelerar la resolución del problema de convección-difusión estacionario, lo que resulta de interés para la simulación en ingeniería medioambiental yen transmisión del calor.


1.4. Referencias y programas de cálculo

Este trabajo se centra en la resolución eciente del sistema de ecuaciones resultante en el métodode estabilización propuesto en [18]. Su estructura guarda cierta similitud con el que se obtiene parael problema de Stokes, por lo que parece lógico intentar utilizar las técnicas de precondicionamientoexistentes para este. En relación a esto, Elman, Silvester y Wathen, estudian en [13] cómo agilizarlos métodos iterativos cuando se emplea el método de los elementos nitos para resolver ujosincompresibles. De esta forma, realizan un recorrido por las ecuaciones de Poisson, convección-difusión y Stokes, para llegar nalmente al problema de Navier-Stokes. Son de especial interés paraeste trabajo las técnicas que sugieren para precondicionar los sistemas que surgen de la ecuaciónde Poisson y el problema de Stokes.

La experimentación se ha llevado a cabo implementando los algoritmos en MATLAB 7.6.0 [26].Para ello, ha resultado de enorme utilidad el paquete de código abierto recogido en el SoftwareIFISS [14], desarrollado con propósito didáctico por David Silvester, Howard Elman y AlisonRamage, y disponible para su descarga libre desde el sitio web de la Universidad de Manchester.Esta herramienta ha sido concebida, principalmente, para trabajar las ideas y algoritmos que seproponen en ELMAN et al. [13]. La implementación del método multigrid algebraico que se hautilizado es, con ligeras modicaciones, la que se encuentra disponible en este paquete de software.También el precondicionador diagonal por bloques que se ha probado se ha tomado del mismopaquete. Debemos destacar lo útil que ha resultado el programa de prueba para resolver sistemaslineales (solver), que forma parte del paquete, y que dispone de numerosas opciones de resolucióncon precondicionadores para los cuatro problemas que se estudian en el libro.

Capítulo 2

Métodos iterativos para el SMS

2.1. Métodos iterativos frente a métodos directos

El empleo de los métodos iterativos frente al de los métodos directos se justica por la ca-racterística dispersa que presentan las matrices que surgen en los problemas de elementos nitos.Debido a esto, el producto de una matriz por un vector resulta una operación barata en términoscomputacionales. De esta forma, si fuese posible encontrar una representación del vector solucióncomo combinación lineal de productos sucesivos de la matriz del sistema por un vector concreto,esto se llevaría a cabo con un costo relativamente bajo. Por otra parte, los métodos directos sefundamentan en la eliminación gaussiana tradicional, que puede resultar poco eciente cuando granparte de las entradas de la matriz son nulas.

En el presente trabajo, el único método directo al que se recurre es la barra invertida (backs-lash) de MATLAB, cuya implementación en un lenguaje de bajo nivel hace que resulte en todoslos casos más eciente que el empleo de cualquier procedimiento programado con el lenguaje espe-cíco de MATLAB. Esta función emplea algoritmos que generan poco llenado (ll-in) de la matrizde coecientes. Sin embargo, en problemas sobre dominios tridimensionales el llenado generadoes lo sucientemente alto como para provocar que el operador backslash sea inviable a poco queaumente el orden del sistema de ecuaciones, en cuyo caso es frecuente que la operación no puedellevarse a cabo de forma satisfactoria. Por ello, es en estos casos en los que se vuelve absolutamen-te imprescindible el uso de métodos iterativos de resolución de sistemas lineales. Estas técnicasobtienen benecio del elevado número de ceros que contienen las matrices de coecientes. En estepunto conviene denir el concepto de densidad de una matriz, bastante frecuente en métodos desimulación numérica en los que surgen matrices dispersas. Esta se dene como el cociente entre elnúmero de entradas no nulas de la matriz y el numero total de elementos en la misma. No es difícilllegar a la conclusión de que las matrices dispersas tienen una densidad bastante reducida. Detodo lo anterior se deduce que el comportamiento va a ser análogo en problemas bidimensionales ytridimensionales, salvo quizá por el tamaño del sistema resultante. Sin embargo, es en estos últimosdonde los métodos iterativos encuentran su verdadera utilidad.

Los métodos iterativos clásicos más conocidos son el de Jacobi, Gauss-Seidel y sobrerrelajaciónsucesiva (SOR). Sin embargo, estas técnicas nunca se utilizan tal cual en aplicaciones donde serequiere una alta eciencia en la resolución de sistemas lineales. En todo caso, se emplean integradoscomo algún paso de suavizado en procedimientos más complejos. Tal es el caso del método multigridalgebraico. En la actualidad, el uso de estas técnicas se restringe a ciertas áreas de la ingenieríadonde aún se mantienen por su enorme sencillez [7, 42]. La idea básica que subyace bajo estosmétodos es la separación (splitting) de la matriz de coecientes A en dos operadores, de forma queA = M −N , y tal que la inversa de M es fácil de obtener. De esta forma, para la igualdad Ax = b,se tiene que

Mx = Nx+ b⇒ x = M−1Nx+M−1b = Tx+ f.

De la expresión anterior se puede obtener un procedimiento iterativo conocido como algoritmo

21

22 CAPÍTULO 2. MÉTODOS ITERATIVOS PARA EL SMS

de Richardson. Este método consiste en una iteración de punto jo, procedimiento bastante exten-dido en la resolución de sistemas no lineales que surgen en múltiples áreas de la ingeniería, comopuede ser en el tratamiento de la radiación en transmisión del calor. Así,

x(j) = M−1 (M −A)x(j−1) +M−1b = x(j−1) +M−1(b−Ax(j−1)

). (2.1.1)

El error en cada iteración se obtiene como e(j) = x(j) − x =(Tx(j−1) + f

)− (Tx+ f) =

T(x(j−1) − x

)= Te(j−1). De forma general,

e(j) = T je(0). (2.1.2)

Y de esta expresión se puede deducir la condición para que la norma euclídea del error sereduzca en cada iteración, de modo que el método iterativo converja a la solución buscada.

Teorema 5. La condición necesaria y suciente para que T j → 0 conforme j → ∞ es queρ (T ) < 1, siendo ρ (T ) = max |λj (T )| el radio espectral de T.

Los métodos de Jacobi, Gauss-Seidel y sobrerrelajación sucesiva se diferencian en la elección dela matrizM . Suponiendo que la matriz A no tiene elementos nulos en su diagonal, lo cual se puedelograr mediante una adecuada ordenación de sus las y columnas, se tiene la descomposición

A = D − L− U = D(I −D−1L−D−1U

), (2.1.3)

donde D es la matriz diagonal cuya diagonal coincide con la de A, y −L y −U son las matricestriangular inferior y superior de A, respectivamente.

Método de Jacobi

En el método de Jacobi se realiza la elección trivial M = D y N = L + U . Se puede probarque el método de Jacobi converge para matrices de diagonal estrictamente dominante [7], es decir,aquellas en las que se cumple que

|aii| >∑j 6=i

|aij | , ∀i = 1, ..., n. (2.1.4)

Método de Gauss-Seidel

En este caso se elige M = D−L y N = U . De nuevo la convergencia se asegura si la matriz Aes de diagonal estrictamente dominante [7].

Método de sobrerrelajación sucesiva (SOR)

Ahora M = Dω − L y N =

(1ω − 1

)D + U con ω > 0. En este caso, que A sea una matriz de

diagonal estrictamente dominante no es condición suciente para la convergencia de la iteración deRichardson. Sin embargo, si A es simétrica y denida positiva, la condición necesaria y sucientepara la convergencia del método es que 0 < ω < 2 [4, 7].

En todos los casos se observa que el cálculo del vector solución en cada iteración solo requiere lasolución de la iteración anterior. Los métodos iterativos que presentan mejores prestaciones en laresolución de sistemas lineales hacen, de alguna manera, uso de información obtenida en todas lasiteraciones anteriores. De esta forma, la corrección de la solución se lleva a cabo con más criterioque en los métodos clásicos, y sobre todo, con un profundo signicado geométrico del que estoscarecen. En realidad, el gran inconveniente que presentan estos métodos es que el cumplimientode la condición de parada suele requerir un número prohibitivo de iteraciones en sistemas linealesde gran tamaño, es más, ni siquiera convergen a la solución exacta en una cantidad nita deiteraciones.

En este sentido, los métodos iterativos basados en subespacios de Krylov reducen drásticamentelas iteraciones para lograr la convergencia, y lo que es más, garantizan la convergencia a la solución

CAPÍTULO 2. MÉTODOS ITERATIVOS PARA EL SMS 23

exacta del problema en, como máximo, un número de iteraciones igual al tamaño de la matriz decoecientes. Esto se deduce en virtud del teorema de Cayley-Hamilton, y posee una explicacióngeométrica que se esbozará más adelante, y que permite intuir de forma clara la utilidad delprecondicionamiento.


2.2. Cotas para el error relativo del vector solución

Dada la importancia que tienen los autovalores y autovectores de la matriz de coecientes enlos métodos iterativos de resolución, se expone aquí una breve discusión de sistemas de ecuacionesen función de dichos autovalores. En adelante se limita el estudio a sistemas simétricos, que tienenciertas propiedades interesantes y, además, aparecen con bastante frecuencia en la práctica.

Sea el siguiente sistema lineal cuya matriz de coecientes reales A es simétrica, es decir, secumple que A = At, x∗ es el vector solución y b es el vector de términos independientes,

Ax∗ = b. (2.2.1)

Puesto que la matriz A es simétrica, se verica que sus autovalores son todos reales y susautovectores forman una base ortogonal. Entonces, A resulta ser diagonalizable ortogonalmente, yse puede descomponer de la forma A = PDP−1, siendo P una matriz ortogonal y que cumple portanto que P−1 = P t. Las columnas de P son los autovectores de A, y como estos forman una baseortogonal, es posible expresar x y b como combinación lineal de estos autovectores. Por tanto, setiene que b = P b y x∗ = Px, con b =

[β1 ... βn

], x =

[α1 ... αn

], y αi, βi ∈ R. Como es

obvio, ambas ternas de coecientes se encuentran relacionadas por medio de (2.2.1). Por tanto,

x∗ = A−1b =(PD−1P−1

) (P b)

= PD−1b.

Luego x = D−1b. Conocidos los autovectores vi de la matriz A, es posible expresar la solucióndel sistema (2.2.1) como combinación lineal de estos y de los coecientes hallados previamente,

x∗ =

n∑i=1

βiλivi. (2.2.2)

Analizando la expresión (2.2.2) se observa que tres situaciones distintas son posibles:

1. Si para algún k = 1, ..., n se tiene que λk = 0 y βk 6= 0, el sistema resulta ser incompatible.

2. Si para algún k = 1, ..., n se tiene que λk = 0 y βk = 0, el sistema es compatible indetermina-do. Lo que ocurre en estas circunstancias es que el vector de términos independientes tieneproyección nula en la dirección dada por vi, y además dicha dirección pertenece a Nul(A),por lo que en realidad cualquier valor del coeciente αk daría lugar a una solución x∗ capazde vericar (2.2.1). Así, se tendría que

A

αkvk +

n∑i=1,i6=k

βiλivi

x = αkAvk +

n∑i=1,i6=k

βiλiAvi =

n∑i=1,i6=k

βiAvi = b.

3. Por último, siempre que λk 6= 0 el sistema dado por (2.2.1) resulta ser compatible determi-nado.

Tras este breve análisis, se acota superior e inferiormente la norma euclídea del vector solución enfunción de la del vector de términos independientes. Para ello, se parte de la expresión (2.2.2), y

recordando que los autovectores son ortogonales, se deduce que ‖x∗‖2 =∑ni=1

(βiλi

)2

. Si se denota

por |λi|max y |λi|mın al mayor y menor autovalor de A en valor absoluto, respectivamente, se

tiene que ‖b‖2|λi|2max

≤ ‖x∗‖2 ≤ ‖b‖2|λi|2mın

. Dado que se trata en todo caso de valores positivos, se tiene

nalmente que

‖b‖|λi|max

≤ ‖x∗‖ ≤ ‖b‖|λi|mın

. (2.2.3)

En los métodos iterativos que se emplean, la tolerancia se suele especicar en términos del errorrelativo del vector de términos independientes que se obtiene al aproximar la solución por x. Esdecir, deniendo el residuo de la solución aproximada como r = b−Ax, se impone que


‖r‖‖b‖≤ TOL. (2.2.4)

Recordando de nuevo la expresión del vector de términos independientes como combinaciónlineal de la base de autovectores, y deniendo una relación análoga para la solución aproximada,se pueden obtener algunas relaciones útiles. Así, expresamos la aproximación a la solución como

x =

n∑i=1

γiλivi. (2.2.5)

De forma que

r = b−Ax =

n∑i=1

βivi −n∑i=1

γiλiAvi =

n∑i=1

βivi −n∑i=1

γivi =

n∑i=1

(βi − γi) vi

⇒ ‖r‖2 =

n∑i=1

(βi − γi)2, ‖b‖2 =

n∑i=1

β2i ⇒

‖r‖2

‖b‖2=

∑ni=1 (βi − γi)2∑n

i=1 β2i

≤ TOL2. (2.2.6)

Un análisis semejante se puede llevar a cabo para el error relativo del vector solución, denidocomo

ε =‖x− x∗‖‖x∗‖

. (2.2.7)

Puesto que lo que se pretende es minimizar el error relativo del vector solución, más que elresiduo relativo, conviene poner de maniesto qué relación existe entre ambos términos. De hecho,cabe preguntarse qué cota se tiene para el error relativo de la solución imponiendo una ciertatolerancia al residuo. En principio, parece lógico pensar que un residuo relativo reducido implicaun error relativo de la solución también reducido. Sin embargo, esto puede no ser necesariamentecierto, como se verá a continuación. Elevando (2.2.7) al cuadrado, se tiene

ε2 =‖x− x∗‖2

‖x∗‖2=

∑ni=1

(βi−γi)2

λ2i∑n

i=1β2i

λ2i

.

Y de esta expresión se puede obtener una cota inferior y otra superior para el error. En ellas,aparecen TOLsup y TOLinf , que son las cotas superior e inferior para el residuo relativo, respec-tivamente. Es decir,

TOLinf ≤‖r‖‖b‖≤ TOLsup. (2.2.8)

Por tanto,

ε2 =

∑ni=1

(βi−γi)2

λ2i∑n

i=1β2i

λ2i

≤1

|λi|2mın

∑ni=1 (βi − γi)2

1|λi|2max

∑ni=1 β

2i

=|λi|2max|λi|2mın

∑ni=1 (βi − γi)2∑n

i=1 β2i

=

=|λi|2max|λi|2mın

‖r‖2

‖b‖2≤ |λi|

2max

|λi|2mınTOL2

sup,

donde se ha empleado la relación dada en (2.2.6). De manera análoga, se tiene

ε2 ≥ |λi|2mın

|λi|2maxTOL2

inf .


Por lo que se deduce que, conocidas las cotas superiores e inferiores para el error relativo delvector de términos independientes, se tienen cotas superiores e inferiores para el error relativo delvector solución,

|λi|mın|λi|max

TOLinf ≤ ε ≤|λi|max|λi|mın

TOLsup. (2.2.9)

Como es natural, la cota superior resulta de mayor interés para el problema que se aborda, ypermite emplear un concepto empleado con profusión en el campo de los métodos numéricos, comoes el número de condición de una matriz,

κ =|λi|max|λi|mın

≥ 1. (2.2.10)

De modo que tolerancias pequeñas para el residuo relativo al término independiente no implicanerrores relativos del mismo orden para la solución del sistema. A efectos prácticos, cuando serealizan cálculos por computador, las tolerancias mínimas que se pueden utilizar deben ser mayoresque el número de máquina, es decir, TOLinf ≥ ε y TOLsup ≥ ε. De lo contrario, no es posiblealcanzar la convergencia de los métodos iterativos utilizados. Por tanto,

ε

κ≤ ε ≤ κTOLsup, (2.2.11)

y la mejor cota superior que se puede obtener para el error relativo del vector solución sería κε.Obsérvese de nuevo que, para una matriz de coecientes dada, esta cota podría no asegurar unasolución aproximada aceptable. Por tanto, uno de los objetivos del precondicionamiento pasará porreducir el número de condición, dado que el número de máquina viene dado por las característicasfísicas del propio computador.


2.3. Métodos iterativos de subespacios de Krylov1

2.3.1. Subespacios de Krylov. Obtención de bases ortogonales medianteel algoritmo de Lanczos

La utilidad de los métodos de subespacios de Krylov [36] radica en el hecho de que, si A es unamatriz dispersa, el producto Ax es poco costoso. Por tanto, no es caro obtener las componentesdel subespacio de Krylov de dimensión k, dado por

Kk (A, x) = spanx,Ax,A2x,A3x, ..., Ak−1x

. (2.3.1)

Kk (A, x) constituye una base de un subespacio k-dimensional de Rn cuando los vectores x,..., Ak−1x son linealmente independientes. Sin embargo, los vectores Ajx no son ortogonales ytienden al autovector asociado al autovalor dominante al incrementar j, por lo que la base está malcondicionada. Para corregir este inconveniente, el método de Lanczos de ortogonalización subyaceen buena parte de los métodos iterativos que emplean subespacios de Krylov.

El hecho de que busquemos aproximar la solución x por una combinación lineal de vectoresde Kk (A, x) halla su motivación en el teorema de Cayley-Hamilton, que arma que toda matrizcuadrada A de orden n anula su propio polinomio característico,

c (z) =

n∏j=1

(λj − z) =

n∑j=0

cjzj ,

es decir,

c (A) = 0.

De donde se deduce que es posible expresar A−1 como combinación lineal de las n− 1 primeraspotencias de A siempre que det (A) 6= 0, puesto que

c (A) =

n∑j=0

cjAj = 0⇒ c0A

−1 +

n∑j=1

cjAj−1 = 0⇒

A−1 = qn−1 (A) = −∑nj=1 cjA

j−1

det (A). (2.3.2)

Por tanto, para el sistema lineal Au = f se tendría u = A−1f = qn−1 (A) f . Sin embargo,ya sabemos que n suele ser lo bastante elevado como para que el procedimiento anterior resulteprohibitivo. La idea es aproximar la solución u por una combinación lineal de vectores de Kk (A, x),obviamente con k n, de forma que

y =

k−1∑j=0

αjAjx = qk−1 (A)x ∈ Kk (A, x) .

Siendo de importancia capital la adecuada elección del polinomio qk−1.El método de Lanczos [7, 13, 36, 40] es una particularización del algoritmo de Arnoldi [7] para

matrices simétricas que permite estimar los autovalores de las mismas. Ambas técnicas calculan deforma explícita bases ortogonales para subespacios de Krylov, por lo que conducen a algoritmosde resolución para sistemas lineales. De hecho, el método de Lanczos se encuentra en la raíz delos algoritmos del gradiente conjugado y del método MINRES, en los que de manera gradual seconstruye una base ortonormal del subespacio de Krylov Kk (A, r0). Esto se lleva a cabo mediantela relación de recurrencia dada por

γj+1v(j+1) = Av(j) − δjv(j) − γjv(j−1), 1 ≤ j ≤ k, (2.3.3)

1Esta sección es un extracto de ELMAN et al. [13, Chapters 2,6] y STRANG [40].


siendo los vectores v(j) ortonormales, δj =⟨Av(j), v(j)

⟩y γj+1 tal que

∥∥v(j+1)∥∥ = 1. La relación

(2.3.3) da lugar a la matriz tridiagonal

Tk = tridiag [γj , δj , γj+1] . (2.3.4)

De forma que si Vk =[v(1), v(2), ..., v(k)

]entonces se cumple que V tkAVk = Tk, puesto que

la matriz Vk, al tener todas sus columnas ortogonales entre sí y de norma unidad, satisface queV tkVk = Ik. De lo anterior se deduce que, si k = n, A y Tk tienen los mismos autovalores. Sinembargo, para k < n los autovalores de Tk son cada vez una mejor estimación de los k autovaloresmayores de A a medida que k se acerca a n.

Algorithm 1 EL ALGORITMO DE LANCZOS

Require: A, v(1) Nj = 0v(0) = 0γ1 =

∥∥v(1)∥∥

v(1) ← v(1)

γ1

for j = 1 : (N − 1) doδj =

⟨Av(j), v(j)

⟩v(j+1) = (A− δjI) v(j) − γjv(j−1)

γj+1 =∥∥v(j+1)

∥∥v(j+1) ← v(j+1)

γj+1

end for


2.3.2. El método del gradiente conjugado

El método del gradiente conjugado [4, 7, 36, 40], propuesto por Hestenes y Stiefel, es el másconocido de los métodos de subespacios de Krylov. Es importante destacar que su aplicación serestringe a sistemas lineales cuya matriz de coecientes es simétrica y denida positiva. Parte deuna estimación inicial de la solución, que suele ser el vector nulo, y la va corrigiendo en cadaiteración mediante direcciones de búsqueda que son ortogonales entre sí en la norma denida porA. Debido a esto, dichas direcciones resultan ser linealmente independientes, lo que garantiza que,a diferencia del método de descenso más rápido, el gradiente conjugado pueda obtener la soluciónexacta en un número acotado de iteraciones. Esto se intuye mejor si se tiene en cuenta que, encada iteración, el residuo obtenido es ortogonal a los obtenidos en las iteraciones anteriores. Deesta forma, si se parte de r(0) es evidente que al realizar la iteración n-ésima el residuo resultanteestá obligado a ser estrictamente nulo, lo que implica que u(n) = u. En la práctica no tiene sentidocompletar n iteraciones, sino que se establece una condición de parada sobre la norma del residuorelativa al término independiente, o bien se impone un número máximo de iteraciones.

Algorithm 2 EL MÉTODO DEL GRADIENTE CONJUGADO

Require: A, f , u(0), TOL, Nk = 0r(0) = f −Au(0)

while‖r(k)‖‖f‖ ≥ TOL and k < N do

if k = 0 thenp(k) = r(k)

elsep(k) = r(k) + βk−1p

(k−1)

end if

αk =〈r(k),r(k)〉〈Ap(k),p(k)〉

u(k+1) = u(k) + αkp(k)

r(k+1) = r(k) − αkAp(k)

βk =〈r(k+1),r(k+1)〉〈r(k),r(k)〉

k = k + 1end while

Es posible demostrar que los residuos normalizados generados por el método del gradienteconjugado conforman un conjunto ortonormal que satisface la recurrencia de tres términos (2.3.3)del algoritmo de Lanczos [13]. Por otra parte, no es difícil comprobar que la solución en la iteraciónk-ésima pertenece al subespacio de Krylov u(0) +Kk

(A, r(0)

). En concreto, se tiene que

u− u(0) = A−1r(0) = qn−1 (A) r(0),

u(k) = u(0) + qk−1 (A) r(0) ∈ u(0) +Kk(A, r(0)

). (2.3.5)

La cuestión es determinar cómo se elige la secuencia de polinomios q para que u(k) converja a u.En la práctica se tiene u(k) = u(k−1) +αk−1r

(k−1), de manera que la elección de α da lugar a variosmétodos, como el de descenso más rápido o el propio gradiente conjugado. En este último, el valor

se elige de forma que cada iteración minimice la norma en A del error,∥∥e(k)

∥∥A

=√⟨

Ae(k), e(k)⟩,

entre todas las direcciones posibles de búsqueda, siendo

e(k) = u− u(k). (2.3.6)

De la expresión (2.3.5) se deduce que

e(k) = e(0) − qk−1 (A) r(0) = (I −Aqk−1 (A)) e(0) = pk (A) e(0),


donde pk (z) = 1−zqk−1 (z), de modo que pk (0) = 1. Por otra parte, como ya dijimos, el vectoru(k) generado por el método del gradiente conjugado minimiza la norma en A del error, por lo que∥∥∥e(k)

∥∥∥A

= mınpk∈Πk,pk(0)=1

∥∥∥pk (A) e(0)∥∥∥A. (2.3.7)

Si se expresa el error inicial como combinación lineal de los autovectores deA, e(0) =∑nj=1 γjv

(j)

se tiene que

∥∥∥e(k)∥∥∥A


∥∥∥∥∥∥n∑j=1

γjpk (λj) v(j)

∥∥∥∥∥∥A

≤

mınpk∈Πk,pk(0)=1

maxj|pk (λj)|

∥∥∥∥∥∥n∑j=1

γjv(j)

∥∥∥∥∥∥A


maxj|pk (λj)|

∥∥∥e(0)∥∥∥A.

Si se considera que todos los autovalores λj son positivos (dado que A es denida positiva) yque se encuentran distribuidos en el intervalo [a, b], de forma que a = λmin (A) y b = λmax (A),entonces haciendo uso de las propiedades de los polinomios de Chebyshev es posible deducir unaexpresión para el orden de convergencia del método que depende del número de condición de A [7],∥∥∥e(k)

∥∥∥A≤ 2

(√κ− 1√κ+ 1

)k ∥∥∥e(0)∥∥∥A. (2.3.8)

La expresión (2.3.8) sugiere que un número de condición cercano a la unidad implica unaconvergencia en pocas iteraciones. Sin embargo, se puede tener también una convergencia rápidacuando el número de condición es elevado, si se logran connar los autovalores a pocas regionesreducidas de la recta real.

Asimismo, se puede hallar el número máximo de iteraciones necesarias para alcanzar una tole-

rancia ε =‖e(k)‖

A

‖e(0)‖A

a partir de (2.3.8),

kmax =log (ε/2)

log(√

κ−1√κ+1

) . (2.3.9)


2.3.3. El método MINRES

El método del residuo mínimo (MINRES) [13] obtenido por Paige y Saunders [29] se deriva delalgoritmo de Lanczos. Es aplicable a matrices simétricas, ya sean indenidas o denidas positivas,aunque para estas últimas el coste computacional se reduce optando por el gradiente conjugado.El hecho de que la matriz A sea indenida puede provocar que la matriz tridiagonal Tk denidaen (2.3.5) sea singular, lo cual supone un obstáculo para el método del gradiente conjugado. Elmétodo MINRES resuelve este inconveniente reduciendo por mínimos cuadrados la norma euclídeadel residuo en cada iteración,

∥∥r(k)∥∥.

Algorithm 3 EL MÉTODO MINRES

Require: A, f , u(0), TOL, Nv(0) = w(0) = w(1) = 0j = 1r(1) = f −Au(0)

v(1) = r(1)

γ1 =√⟨

v(1), v(1)⟩

η = γ1

s0 = s1 = 0c0 = c1 = 1

while‖r(k)‖‖f‖ ≥ TOL and j < N do

v(j) = v(j)

γj

δj =⟨Av(j), v(j)

⟩v(j+1) = Av(j) − δj

γjv(j) − γj

γj−1v(j−1)

γj+1 =√⟨

v(j+1), v(j+1)⟩

α0 = cjδj − cj−1sjγj

α1 =√α2

0 + γ2j+1

α2 = sjδj + cj−1cjγjα3 = sj−1γjcj+1 = α0

α1

sj+1 =γj+1

α1

w(j+1) = v(j)−α3w(j−1)−α2w

(j)

α1

u(j) = u(j−1) + cj+1ηw(j+1)

η = −sj+1ηj = j + 1

end while

Análogamente a como se hizo con el gradiente conjugado, se puede deducir una cota para latasa de convergencia del método MINRES [13],∥∥∥r(k)

∥∥∥ ≤ mınpk∈Πk,pk(0)=1

maxj|pk (λj)|

∥∥∥r(0)∥∥∥ . (2.3.10)

De nuevo, la convergencia del método depende solo de los autovalores de la matriz de coe-cientes. Esto es consecuencia de que dicha matriz sea simétrica y, por tanto, sus autovectoresortogonales. Lo que hace que se necesite un mayor número de iteraciones para resolver con MIN-RES un sistema indenido que con con el gradiente conjugado uno denido positivo es el hechode que, en el primero, los autovalores se distribuyen a ambos lados del eje real. Por tanto, el po-linomio pk debe valer la unidad en el origen, y además, tomar valores reducidos a ambos ladosdel mismo, lo cual complica la búsqueda. La consecuencia inmediata es que se recurre de nuevo alprecondicionamiento para connar los autovalores y así acelerar la convergencia del método. Paraeste procedimiento se deduce una expresión del orden de convergencia similar a la presentada en(2.3.10),


∥∥∥r(k)∥∥∥M≤ mınpk∈Πk,pk(0)=1

maxj|pk (λj)|

∥∥∥r(0)∥∥∥M, (2.3.11)

donde ahora los autovalores λj son los de M−1A.


2.4. Precondicionamiento de sistema lineales

2.4.1. Necesidad del precondicionamiento

Como ya se argumentó con anterioridad, el precondicionamiento se convierte en una técnicaimprescindible cuando se utilizan métodos iterativos de resolución de sistemas lineales. Esto consisteen sustituir el sistema original por otro con idéntica solución, pero con mejores propiedades de caraa la convergencia de los métodos iterativos. De esta manera, si se tiene (2.2.1), es evidente que, siM es una matriz cuadrada de rango completo y del mismo orden que A, el sistema precondicionado

M−1Ax∗ = M−1b (2.4.1)

presenta la misma solución que el anterior. De ser posible, elegiríamos siempre M−1 = A−1,puesto que proporciona directamente la solución del problema. Sin embargo, esta elección es ex-tremadamente costosa, por lo que debemos conformarnos con buscar una matriz M que satisfagatres propiedades básicas:

Debe ser una buena aproximación de A en el sentido de que la acción de su inversa sobre Adebería tener el efecto de connar los autovalores de la matriz M−1A. En esta situación laconvergencia se alcanzaría en pocas iteraciones.

El sistema precondicionado M−1A debe tener un número de condición reducido.

La solución de Mz = r no debe ser costosa en términos computacionales2.

El método del gradiente conjugado está restringido a sistemas lineales cuya matriz de coecienteses simétrica y denida positiva (SPD), por lo que si el nuevo sistema que se va a resolver es (2.4.1),entonces M−1A debe ser también SPD. En efecto, el producto de dos matrices SPD es una matrizdenida positiva, aunque no es simétrica en general [7]. Por ello se suele considerar una variantede (2.4.1), en la que M se descompone como

M = HHt, (2.4.2)

y se estudia el sistema lineal resultante

H−1AH−ty = H−1b, y = Htx. (2.4.3)

La matriz de coecientes H−1AH−t es simétrica y denida positiva, por lo que se puede aplicarel método del gradiente conjugado. En la práctica, no es necesario obtener la matriz H, sino quebasta con ser capaces de calcular la acción de la inversa de M de forma sencilla.

Condición de parada del método iterativo

Los métodos del gradiente conjugado y MINRES implementados en MATLAB presentan comocondición de parada en cada iteración el cumplimiento de la restricción∥∥b−Ax(k)

∥∥‖b‖

≤ TOL,

para cierta tolerancia TOL. Esta es la forma natural de proceder en tanto que se conoce el valorexacto del término independiente, mientras que se busca el valor exacto del vector solución y, portanto, no se conoce el error en cada iteración. Para matrices simétricas con un número de condiciónelevado, el cumplimiento de esta condición no garantiza un error relativo reducido en la solución.Este fenómeno no tiene que ver con errores numéricos, sino con el hecho de que la tolerancia se jasobre una magnitud diferente a aquella sobre la que se pretende resolver el sistema. También escomún especicar un número máximo de iteraciones que efectúa el método, y que no tiene sentidoque sea mayor que el orden del sistema que se desea resolver.

2A modo de ejemplo, en algunas ocasiones se utiliza como precondicionador la diagonal del sistema original.


El objetivo primero de cualquier precondicionador es acelerar la convergencia del método ite-rativo sobre el que se utiliza. Sin embargo, ya se mostró que ello solo no basta, puesto que, amenudo, imponer que la norma del residuo sea menor que una tolerancia reducida no conlleva unerror aceptable en la solución. En este caso, la convergencia se lograría al cabo de un reducidonúmero de iteraciones, pero es probable que la solución obtenida no fuera aceptable. Por tanto,hay que asegurar que el precondicionador utilizado permita una convergencia útil. Como resumende lo anterior, se buscan dos nalidades:

1. Reducir el número de iteraciones del procedimiento empleado en cada caso, lo que se tra-duce en una convergencia rápida. Esto se consigue mediante un connamiento ecaz de losautovalores de la matriz de coecientes.

2. Acotar de manera signicativa el error de la solución por la tolerancia impuesta al residuorelativo. Es decir, conseguir que la convergencia sea útil, en el sentido de que la soluciónaproximada obtenida sea aceptable. Para ello, hay que reducir en la mayor medida posibleel número de condición de la matriz de coecientes, o lo que es lo mismo, conseguir que elmayor y menor autovalor en magnitud sean lo más parecido posible.

En resumen, el sistema precondicionado debe tener un número reducido de autovalores distintos, yademás, el cociente entre el mayor y el menor en magnitud debe ser también reducido. No es difícilver entonces que el mejor precondicionador que podemos tener es aquel que transforma la matriz decoecientes en un múltiplo de la matriz identidad, puesto que esta tiene un único autovalor distintoy el número de condición resulta ser la unidad. Es decir, el mejor precondicionador para un sistemaes la inversa de la matriz de coecientes, lo cual resulta evidente. El principal inconveniente que seencuentra aquí es, como ya dijimos, que el cálculo de la matriz inversa es tremendamente costosoen términos computacionales, por lo que resulta inviable en la práctica.

2.4.2. Métodos iterativos precondicionados

El precondicionamiento se puede incluir de forma sencilla en los métodos del gradiente conju-gado y MINRES. De este modo eludimos realizar el producto M−1A para luego efectuar algunode estos dos procedimientos, lo que resulta extremadamente caro. Como es natural, los algorit-mos que se muestran coinciden con los de los métodos del gradiente conjugado y MINRES sinprecondicionar para el caso particular en que M = I.

Algorithm 4 EL MÉTODO DEL GRADIENTE CONJUGADO PRECONDICIONADO

Require: A, f , u(0), TOL, N , Mk = 0r(0) = f −Au(0)

Solve Mz(0) = r(0)

while‖r(k)‖‖f‖ ≥ TOL and k < N do

if k = 0 thenp(k) = z(k)

elsep(k) = z(k) + βk−1p

(k−1)

end if

αk =〈z(k),r(k)〉〈Ap(k),p(k)〉

u(k+1) = u(k) + αkp(k)

r(k+1) = r(k) − αkAp(k)

Solve Mz(k+1) = r(k+1)

βk =〈z(k+1),r(k+1)〉〈z(k),r(k)〉

k = k + 1end while


Algorithm 5 EL MÉTODO MINRES PRECONDICIONADO

Require: A, f , u(0), TOL, N , Mv(0) = w(0) = w(1) = 0j = 1v(1) = f −Au(0)

Solve Mz(1) = v(1)

γ1 =√⟨

z(1), v(1)⟩

η = γ1

s0 = s1 = 0c0 = c1 = 1

while‖r(k)‖‖f‖ ≥ TOL and j < N do

z(j) = z(j)

γj

δj =⟨Az(j), z(j)

⟩v(j+1) = Az(j) − δj

γjv(j) − γj

γj−1v(j−1)

Solve Mz(j+1) = v(j+1)

γj+1 =√⟨

z(j+1), v(j+1)⟩

α0 = cjδj − cj−1sjγj

α1 =√α2

0 + γ2j+1

α2 = sjδj + cj−1cjγjα3 = sj−1γjcj+1 = α0

α1

sj+1 =γj+1

α1

w(j+1) = z(j)−α3w(j−1)−α2w

(j)

α1

u(j) = u(j−1) + cj+1ηw(j+1)

η = −sj+1ηj = j + 1

end while


2.4.3. Método multigrid algebraico

El método multigrid [36, 38] se revela como una técnica bastante eciente para la resolución delsistema de ecuaciones que surge en la discretización de elementos nitos del problema de Poisson. Ensu formulación original, esta técnica requiere información geométrica extensa acerca del mallado deldominio. Grosso modo, consiste en la descomposición de la red (grid en inglés) en dos subespacios,correspondientes a una red basta compuesta por elementos de tamaño característico 2h, y a otrared na con elementos de tamaño h. De esta forma, se tiene que para una red bidimensional,el número de elementos en la red na es aproximadamente cuatro veces mayor que el presenteen la red basta, siendo ocho veces mayor en el caso tridimensional, o el doble para el caso, mássimple, unidimensional. Por una parte, se tiene el espacio S2h de funciones lineales (o polinómicas)a trozos sobre la red basta; y por otra, el espacio Sh de funciones lineales (o polinómicas) a trozossobre la red na, de tal manera que S2h ⊂ Sh. Por último, es necesario denir los operadores detransferencia entre las dos redes, que permiten trasladar funciones de una a otra. Así, se dispone deloperador de prolongación, Ih2h, consistente en la práctica en una matriz P que permite pasar de lared basta a la na, S2h → Sh. Y por otro lado, surge el operador de restricción, I2h

h , materializadopor la matriz R = P t, que permite el cambio de la red na a la red basta.

La idea fundamental del método multigrid es que, partiendo de una estimación inicial de lasolución del sistema lineal, el error se puede representar como la suma de una componente enla red basta, más otra en la red na, que por razones obvias, no es posible expresar en la redbasta. Una vez establecidos los operadores de transferencia, se comienza por un suavizado quereduce rápidamente la componente del error que no ha podido ser representada en la red basta. Elsuavizado consiste en dos o tres iteraciones de algún método iterativo de resolución, como el métodode Jacobi o el método de Gauss-Seidel. De esta forma, si el suavizado fuera ideal, entonces el errorpodría ser representado perfectamente en el espacio de funciones de la red basta. A continuación, seresuelve por un método directo un sistema lineal de orden cuatro veces menor que el original paraproblemas bidimensionales, del que se obtiene el error en la red basta. Dicho error se representa enla red na con el operador de prolongación, y se utiliza para corregir la estimación de la solucióninicial. Por último, el requerimiento de simetría en el operador que representa al método multigrid,conlleva el empleo de un suavizado posterior con el mismo método iterativo y número de iteraciones.Esta simetría es importante porque permitirá utilizar el método multigrid para precondicionar elgradiente conjugado o el MINRES. En relación a esto último, es interesante mencionar que parael problema de Poisson, y bajo ciertas circunstancias adicionales, se alcanza la convergencia en unnúmero de iteraciones independiente de la dimensión del problema discreto.

Hasta ahora se han comentado las ideas generales del método multigrid más sencillo, que utilizaúnicamente dos redes. El objetivo que se persigue sigue siendo resolver un sistema de ecuaciones dedimensión prohibitiva para los métodos directos. Sin embargo, hemos visto que nalmente se pasaa resolver un sistema de dimensión cuatro veces menor que el original. Esto plantea una cuestiónbastante natural, y es que, si resolver el sistema original por métodos directos era complicado,probablemente hacer lo propio con el sistema de orden cuatro veces menor lo siga siendo. Por ello,en la práctica se opta por construir varios niveles de redes. A modo de ejemplo, la red original delproblema constituiría la red na, a partir de la cual se obtiene una red más basta mediante unprimer juego de operadores de transferencia. Como el sistema resultante sigue teniendo dimensiónconsiderable, se obtiene una red más basta de la red basta inicial, que se podría considerar ahoracomo una red na. La aparición del nuevo nivel lleva asociada unos operadores de transferenciaque la relacionan con el nivel superior. De esta forma, se pueden construir redes sucesivas cadavez más bastas, hasta llegar a disponer de una que tenga asociado un sistema de ecuacioneslo sucientemente reducido como para que pueda ser resuelto por métodos directos de maneraeciente. Una vez obtenido el error en la red más basta, se recorre el camino inverso pasando porlos niveles cada vez más nos, en los que se va obteniendo el error correspondiente mediante eloperador de prolongación asociado, sin olvidar el suavizado posterior. Esta forma de proceder, enla que primero se desciende a la red más basta para luego retornar por el mismo camino se conocecomo ciclo V. Si la red inicial se concibe como el primer nivel, para cada nivel l se tiene que elorden del sistema lineal resultante se reduce aproximadamente en un factor de 4l−1 para problemasbidimensionales, y en 8l−1 para dominios tridimensionales. De forma general, para dominios de


dimensión d, la reducción se lleva a cabo por un factor 2d(l−1).La construcción de los operadores de transferencia es una cuestión de importancia porque

da lugar a la existencia de diversas variantes del método. Originalmente, para ello se requeríainformación geométrica de la red, dando lugar al método multigrid geométrico. Sin embargo, poralguna razón, esta información puede no estar disponible o ser poco accesible. Para salvar esteobstáculo, surge una variante que se basa en relaciones algebraicas para obtener los operadores, yque se conoce como método multigrid algebraico (AMG) [36, 41, 38]. El método AMG presenta elinconveniente de que requiere determinar de forma experimental los valores de los parámetros quese utilizan para discriminar elementos de la matriz original [30].

El método multigrid algebraico incluido en el software IFISS ha sido diseñado para que seael usuario quien determine el número de niveles que quiere construir. Sin embargo, dado que enla red más basta se lleva a cabo la resolución de un sistema lineal por un método directo3, se haconsiderado más realista modicar el algoritmo para que construya un número de niveles tal queel sistema nal que se resuelve tenga un tamaño comprendido entre 80 y 400, de forma que susolución no suponga un obstáculo en aplicaciones reales. Se puede estimar el número de nivelesnecesario como

l ≈ 1 +ln n0

nf

d ln 2, (2.4.4)

siendo no el orden del sistema inicial, y nf el del sistema que nalmente se resuelve. La formaexacta de proceder es ir creando niveles hasta que se tenga un sistema lineal cuyo tamaño seencuentre comprendido entre los límites especicados.

3Concretamente la barra invertida (backslash) de MATLAB.


2.4.4. Matriz inversa del sistema

Dada la matriz de coecientes K denida en (1.2.59), con S de orden n × n y A de orden(n−m)× n, consideramos el precondicionador

M−1 =

(Z BJ D

), (2.4.5)

e imponemos que de modo general se cumpla M−1K =

(λI 00 σI

), con λ, σ ∈ R,

(Z BJ D

)(S At

A 0

)=

(ZS +BA ZAt

JS +DA JAt

)=

(λI 00 σI

).

Por lo que

ZS +BA = λI, (2.4.6)

ZAt = 0, (2.4.7)

JS +DA = 0, (2.4.8)

JAt = σI. (2.4.9)

A partir de (2.4.8) y (2.4.9) se deduce

−DAS−1At = σI ⇒ D = −σ(AS−1At

)−1,

J = −DAS−1 = σ(AS−1At

)−1AS−1.

Por otra parte, de (2.4.6) se obtiene

Z = (λI −BA)S−1,

y sustituyendo en (2.4.7),

ZAt = (λI −BA)S−1At = λS−1At −BAS−1At = 0⇒

B = λS−1At(AS−1At

)−1,

Z = λS−1(I − S−1At

(AS−1At

)−1AS−1

).

Luego,

M−1 =

(λS−1

(I −At

(AS−1At

)−1AS−1

)λS−1At

(AS−1At

)−1

σ(AS−1At

)−1AS−1 −σ

(AS−1At

)−1

). (2.4.10)

Si se cumple que S = St, como en el problema bajo estudio, entonces K es simétrica. Si ademásλ = σ entonces también M−1 es simétrica.

Se dene el complemento de Schur de la matriz ampliada K como

C = AS−1At, (2.4.11)

de forma que


M−1 =

(λS−1

(I −AtC−1AS−1

)λS−1AtC−1

σC−1AS−1 −σC−1

). (2.4.12)

Por tanto, el precondicionador requiere calcular la inversa de las matrices S y C, tarea que noresulta sencilla, especialmente en el caso del complemento de Schur. La matriz inversa se obtendríaigualando λ = σ = 1,

K−1 =

(S−1

(I −AtC−1AS−1

)S−1AtC−1

C−1AS−1 −C−1

). (2.4.13)

Resulta interesante obtener la descomposición del precondicionador como el producto de unamatriz por su transpuesta. Para la inversa se tiene que

H−1 =

(Z 0

RAS−1 −R

), (2.4.14)

y de ahí,

H−tH−1 =

(Zt S−1AtRt

0 −Rt)(

Z 0RAS−1 −R

)=

=

(ZtZ + S−1AtRtRAS−1 −S−1AtRtR

−RtRAS−1 RtR

)=

=

(S−1

(I − S−1AtC−1AS−1

)S−1AtC−1

C−1AS−1 −C−1

),

donde se ha tenido en cuenta que ZtZ = S−1 y que C−1admite una factorización de la forma−RtR. En este punto hay que hacer una aclaración, puesto que la matriz S es simétrica denidapositiva, entonces xtSx > 0, ∀x 6= 0, y resulta que xtCx = xtAS−1Atx = (Atx)

tS−1Atx =

ytS−1y > 0, ∀x 6= 0. Es decir, el complemento de Schur así denido es simétrico denido positivo,por lo que no existe una factorización de Cholesky de la forma −RtR, a no ser que la matriz Rtenga elementos complejos, lo que no resulta de interés4. El hecho de que no pueda realizarse lafactorización mencionada de la inversa dada en (2.4.13) es resultado de que la matriz K del sistemasea indenida.

4Si R es una matriz de números reales, se tiene que xtRtRx = (Rx)t (Rx) = ‖Rx‖2 > 0, ∀x 6= 0. Por tanto, parauna matriz denida negativa no es posible encontrar una factorización como la anterior.


2.4.5. Precondicionador ideal por bloques

Cuando la matriz de coecientes del sistema es indenida se debe emplear el método MIN-RES para su resolución. Sin embargo, para preservar la simetría en el sistema precondicionado,el precondicionador empleado debe ser simétrico y denido positivo [13], por lo que tenemos queolvidarnos de usar alguna aproximación de la inversa presentada en (2.4.13). Observamos que sitenemos un precondicionador de la forma

M−1 =

(V −1

(I +AtQ−1AV −1

)−V −1AtQ−1

−Q−1AV −1 Q−1

), (2.4.15)

que se puede expresar también como

M−1 =

(V −1 0

0 Q−1

)(I +AQ−1AV −1 −AtQ−1

−AV −1 I

), (2.4.16)

es posible escribir M−1 = H−tH−1, por lo que podemos armar que el precondicionador essimétrico y denido positivo. Así,

H−1 =

(Z 0

−RAV −1 R

), (2.4.17)

con ZtZ = S−1 y RtR = Q−1.En (2.4.15), V −1 es una aproximación para la acción de la inversa de S, y Q−1 para la inversa

del complemento de Schur, dado que el cálculo de ambas matrices resulta extremadamente costoso.Por tanto, en condiciones ideales V −1 = S−1 y Q−1 = C−1.

Se puede demostrar que, en las condiciones anteriores y utilizando el precondicionador dado en(2.4.15), el método MINRES converge en dos iteraciones como máximo. Por esta razón damos aM−1 el calicativo de ideal5, puesto que solo K−1 conseguiría una convergencia más rápida. Así,en la situación ideal en que V −1 = S−1 y Q−1 = C−1, la acción del precondicionador sobre elsistema original resulta ser

M−1K =

(S−1 0

0 Q−1

)(I +AtQ−1AS−1 −AtQ−1

−AS−1 I

)(S At

A 0

)=

=

(S−1 0

0 Q−1

)(S At +AtQ−1AS−1At

0 −Q−1

)=

=

(I 2S−1At

0 −I

),

y considerando el problema de autovalores(I 2S−1At

0 −I

)(up

)= λ

(up

), (2.4.18)

se obtiene el sistema de ecuaciones

u+ 2S−1Atp = λu, (2.4.19)

− p = λp. (2.4.20)

En (2.4.20), si p 6= 0 entonces λ = −1 con autovector

(−S−1Atp

p

)y multiplicidad n−m.

5Este concepto de ideal es distinto al que se da a los precondicionadores en ELMAN et al. [13], donde con ello sequiere decir que V = S, Q = C, y la acción de sus inversas se obtiene con alta precisión por medio de algún métododirecto.


Por otra parte, si p = 0 es fácil deducir que λ = 1 con multiplicidad n, y el autovector asociado

sería

(u0

).

Por tanto, el sistema precondicionado de esta forma tiene dos autovalores distintos y el métodoMINRES converge en dos iteraciones a lo sumo.

2.4.5.1. Implementación del precondicionador ideal por bloques

En la práctica no es imprescindible disponer del precondicionador de manera explícita, sino quebasta con conocer el resultado que proporciona su multiplicación por un vector cualquiera. Estedetalle es de gran relevancia, dado que permite prescindir de cálculos innecesarios. Considérese

que se desea conocer el resultado de la operación M−1

(xy

)en función de los que se obtienen al

efectuar los productos intermedios V −1 y Q−1,

M−1

(xy

)=

(V −1

(I +AtQ−1AV −1

)−V −1AtQ−1

−Q−1AV −1 Q−1

)(xy

)=

=

(V −1x+ V −1AtQ−1AV −1x− V −1AtQ−1y

−Q−1AV −1x+Q−1y

)=

=

((V −1x

)− V −1

(AtQ−1

(y −A

(V −1x

)))Q−1

(y −A

(V −1x

)) ),

donde se realizan las siguientes denicionesW1 (x) = V −1x

W2 (x, y) = Q−1 (y −AW1 (x))

W3 (x, y) = V −1 (AtW2 (x, y))

, (2.4.21)

de modo que

M−1

(xy

)=

(W1 (x)−W3 (x, y)

W2 (x, y)

). (2.4.22)

Como Q es simétrica y denida positiva, la acción de Q−1 se puede obtener utilizando el métododel gradiente conjugado. Sin embargo, se busca siempre que esta matriz Q sea tal que su inversasea sencilla de aplicar, por ejemplo, cuando se trata de una matriz diagonal. De esta forma, sepuede prescindir de recurrir a un método iterativo.

En resumen, este precondicionador para el método MINRES emplearía, a lo sumo, tres gra-dientes conjugados en cada iteración, para el cálculo de W1, W2 y W3. No es complicado llegar ala conclusión de que este procedimiento puede resultar muy costoso en términos de cálculo.

2.4.5.2. Precondicionamiento de S y C = AS−1At

Como se deduce de las expresiones (2.4.21) y (2.4.22), obtener el resultado de la acción delprecondicionadorM−1 pasa por calcular la acción de las inversas de S y C. Ello equivale a resolverun sistema lineal de ecuaciones, y al tratarse de matrices SPD, resulta lógico recurrir al empleodel gradiente conjugado. Sin embargo, ya dijimos que para que este sea ecaz es necesario utilizartécnicas de precondicionamiento. En ese sentido, dado que la construcción de la matriz S presentacierta semejanza con la del operador laplaciano, un ciclo V del método multigrid algebraico sepostula como un precondicionador bastante efectivo. La matriz S no se corresponde exactamentecon el operador laplaciano de la ecuación de Poisson, por lo que los buenos resultados que elmétodo AMG proporciona con este no se replican necesariamente con aquella. Sin embargo, losexperimentos numéricos que se presentan más adelante muestran que, aunque el funcionamientoempeora de manera perceptible, sigue siendo recomendable utilizar el método multigrid algebraicopara precondicionar la matriz S.


Por otra parte, estimar la inversa del complemento de Schur es bastante más complejo. Consi-deraciones que atienden a la discretización de los operadores diferenciales asociados a las matricesS y A sugieren aproximar el complemento de Schur bien por la matriz identidad, bien por la matrizde masa de la discretización,

γij =

ˆΩ

φiφjd$, (2.4.23)

Γ = [γij ] . (2.4.24)

Esta última tiene como componentes los productos internos de las funciones base, por lo que no esdifícil llegar a la conclusión de que va a presentar una estructura dispersa.

2.4.6. Precondicionador diagonal por bloques

El precondicionamiento por bloques propuesto puede resultar tan costoso que, aunque el nú-mero de iteraciones del método MINRES se reduzca drásticamente, el tiempo de computación nodisminuya demasiado o incluso aumente. La razón, como ya se indicó, se encuentra en las itera-ciones que deben realizar internamente las tres aplicaciones del método del gradiente conjugadopor cada iteración del MINRES, dos de los cuales llevan a cabo un ciclo V en cada una de ellas.Por tanto, una alternativa bastante razonable consiste en prescindir de la exactitud en los métodositerativos intermedios del precondicionamiento, puesto que lo realmente importante es el métodoiterativo externo. Así, para el problema de Stokes, Elman, Silvester y Wathen proponen en [13]el empleo de un precondicionador que estima directamente la acción de S−1 utilizando un ciclo Vcon el método multigrid algebraico, eliminando el gradiente conjugado. Por otra parte, la acciónde la inversa de Q se realiza utilizando únicamente la diagonal de la matriz de masa del problema,Q = diag (Γ), de modo que la resolución del sistema asociado resulta trivial.

M−1 =

(V −1 0

0 Q−1

). (2.4.25)

Se puede probar que si V −1 = S−1 y Q−1 = C−1, entonces la convergencia del método MINRESse completa en tres iteraciones a lo sumo [13, 5]. Así, a partir del problema de autovalores(

S−1 00 C−1

)(S At

A 0

)(up

)= λ

(up

), (2.4.26)

se obtiene el sistema de ecuaciones

u+ S−1Atp = λu, (2.4.27)

C−1Au = λp. (2.4.28)

Si λ 6= 1, de (2.4.27) se deduce que u = −S−1At

1−λ p, y sustituyendo en (2.4.28) y recordando queAS−1At = C, se tiene nalmente (

λ2 − λ− 1)p = 0. (2.4.29)

De modo que si p no es el vector nulo, entonces λ = 1±√

52 con autovectores asociados

(−S

−1At

1−λ p

p

)y multiplicidades n−m.

Por otra parte, si p = 0, se tiene que cumplir que Au = 0 dado que C−1 es denida positiva. Y

entonces, de (2.4.27) se tiene que λ = 1 con autovector

(u0

)tal que u ∈ Null (A). Este autovalor

tiene al menos multiplicidad m, que es la dimensión del espacio nulo de la matriz A si esta es derango completo.

Por tanto, el sistema precondicionado tiene únicamente tres autovalores distintos y el métodoMINRES convergerá a la solución exacta en tres iteraciones a lo sumo.


2.4.7. Generalización del precondicionador por bloques

No es difícil darse cuenta de que el precondicionador diagonal por bloques coincide con elprecondicionador por bloques cuando la matriz A es nula. De esta forma, con el objeto de ganar enclaridad, resulta más conveniente trabajar con un único precondicionador con forma más general,

M−1 =

(V −1

(I + ρ2AtQ−1AV −1

)−ρV −1AtQ−1

−ρQ−1AV −1 Q−1

). (2.4.30)

Donde se tiene el precondicionador ideal cuando ρ = 1, y el precondicionador diagonal cuandoρ = 0. Por otra parte, la implementación sugerida en (2.4.21) sigue teniendo validez si denimosahora

W1 (x) = V −1x

W2 (x, y) = Q−1 (y − ρAW1 (x))

W3 (x, y) = ρV −1 (AtW2 (x, y))

. (2.4.31)

Experimentalmente se comprueba que la elección ρ = 1 minimiza las iteraciones del métodoMINRES a costa de realizar un mayor número de ciclos V, mientras que ρ = 0 produce el fenómenoopuesto. De un modo más general, si consideramos que ρ actúa como la ponderación de un términocorrectivo y puede tomar cualquier valor real, se observa que al alejarnos de la unidad en cualquierdirección, se incrementan las iteraciones del MINRES. En realidad, la elección óptima de esteparámetro atiende a cómo varían el número de iteraciones y los ciclos V realizados, así comoa la proporción del coste computacional asociado a los ciclos V requeridos en cada iteración deMINRES.

Se puede ilustrar lo anterior de forma sencilla. Sea CC el coste computacional del métodoiterativo, magnitud que queremos minimizar y que se puede medir en tiempo, número de ops, osimilar;MIT , el número de iteraciones que efectúa el método MINRES hasta lograr la convergencia;PMCC, el coste computacional de cada iteración del método MINRES precondicionado; PCC,el coste computacional por iteración del precondicionamiento; MCC, el coste computacional poriteración del método MINRES, sin tener en cuenta el asociado al precondicionador; V CC y n, elcoste de un ciclo V y el número de ellos por cada iteración, respectivamente. Entonces se cumplende forma aproximada las siguientes relaciones algebraicas,

CC = MIT PMCC = MIT (PCC +MCC) = MIT MCC

(1 +

PCC

MCC

)⇒

CC

MCC= MIT

(1 +

PCC

MCC

)= MIT

(1 + n

V CC

MCC

)⇒

∆

(CC

MCC

)=

(1 + n

V CC

MCC

)∆MIT +

V CC

MCCMIT ∆n. (2.4.32)

De (2.4.32) se deduce que la variación del coste computacional depende en gran medida delparámetro V CC

MCC , es decir, del cociente entre el coste de un ciclo V y el coste de llevar a cabo lasoperaciones de una iteración del método MINRES sin precondicionar.

Por otra parte, como ya adelantamos al tratar el precondicionamiento del complemento deSchur, resulta ventajoso optar por Q = I, Q = Γ o Q = diag (Γ), donde Γ denota la matriz demasa de la discretización de elementos nitos. De forma general,

Q = ωf (Γ) + (1− ω) I, 0 ≤ ω ≤ 1. (2.4.33)

Como se comentó anteriormente y se mostrará más adelante con resultados experimentales, eluso de gradientes conjugados en el precondicionador del método MINRES es extraordinariamentecostoso, lo que hace que sea inviable en la práctica. Especialmente cuando se trate de resolver lasegunda ecuación de (2.4.31), donde se hace uso del gradiente conjugado sin precondicionar. Porello, puede resultar conveniente hacer f (Γ) = diag (Γ), cuya inversa se obtiene de forma inmediata,así como sustituir el resto de gradientes conjugados por un único ciclo V6.

6Recordemos que de esta forma se implementa en IFISS el precondicionador para el problema de Stokes.


Por tanto, el precondicionador propuesto en (2.4.30) y (2.4.33) está completamente caracteri-zado si se jan los dos parámetros ρ y ω. La elección óptima está ligada a ensayos experimentalesmás que a estudios teóricos.

Capítulo 3

Resultados numéricos

3.1. Comparación de la resolución de sistemas lineales con

laplaciano discreto o matriz S del SMS utilizando AMG-

PCG

Recordemos que la aproximación de elementos nitos del operador laplaciano, L, y la matriz Sdel método SMS tienen una estructura que guarda cierta similitud. Así, considerando condicionesde contorno Dirichlet homogéneas,

lij =

ˆΩ

∇φi · ∇φjd$, (3.1.1)

sij =

ˆΩ\Ω+

h

(~b · ∇φi

)(~b · ∇φj

)d$ =

ˆΩ\Ω+

h

∇ ·(~bφi

)∇ ·(~bφj

)d$, (3.1.2)

donde se ha tenido en cuenta que el campo de velocidades verica ∇ · ~b = 0. La semejanzaentre ambos operadores se hace más evidente si se tiene en cuenta el siguiente desarrollo para laaproximación del laplaciano,

lij =

d∑k=1

ˆΩ

(~ek · ∇φi) (~ek · ∇φj) d$, (3.1.3)

donde ~ek son los vectores ortonormales1 para la base canónica del espacio euclídeo Rd. Por otraparte, si se expresa el campo de velocidades en dicha base,

~b =

d∑k=1

βk~ek, (3.1.4)

se tiene

sij =

d∑k=1

d∑l=1

ˆΩ\Ω+

h

βkβl (~ek · ∇φi) (~el · ∇φj) d$,

donde recordemos que las componentes βk son dependientes de las coordenadas en general. Ovisto de otra forma, la matriz S es el primer sumando del desarrollo similar a (3.1.3),

d∑k=1

ˆΩ\Ω+

h

(~bk · ∇φi

)(~bk · ∇φj

)d$,

1Se cumple que ~ei · ~ej = δij .

45

46 CAPÍTULO 3. RESULTADOS NUMÉRICOS

donde ~b1 = ~b y ~bi ·~bj =∣∣∣~bi∣∣∣ ∣∣∣~bj∣∣∣ δij .

A raíz de lo anterior cabe preguntarse si las técnicas de precondicionamiento que proporcionanresultados satisfactorios en la resolución de la ecuación de Poisson resultan de interés para pre-condicionar la matriz S. En particular, se compara el comportamiento de ambos problemas anteel gradiente conjugado precondicionado con el método multigrid algebraico (AMG-PCG2), que esuna estrategia óptima para resolver el problema de Poisson [13]. Con este n se consideran dosproblemas de referencia.

En cada uno de ellos, se parte de un campo escalar u (x, y) conocido que verica la ecuaciónde Poisson. Esta ecuación diferencial en derivadas parciales da lugar a un problema de elementosnitos consistente en la resolución del sistema lineal de ecuaciones,

Luk = fk. (3.1.5)

La idea es comparar la eciencia en la resolución, mediante el método AMG-PCG, de (3.1.5) yde

Su∗k = f∗k . (3.1.6)

Para ello se evalúa u (x, y) en los nodos, y se calcula el vector independiente de forma trivialcomo fk = Luk o f∗k = Su∗k, según proceda. A continuación se resuelve el sistema de ecuacio-nes utilizando el AMG-PCG. En los experimentos numéricos cuyos resultados se adjuntan se haconsiderado la matriz S derivada de un campo de velocidades uniforme, en concreto ~b = [2, 3].Mencionamos esto porque se mostrará que la forma del campo de velocidades particular de ca-da problema tiene una inuencia notable en la efectividad de los precondicionadores propuestos.Sin embargo, experimentos posteriores demuestran que dicha inuencia no se ejerce a través delprecondicionamiento de la matriz S. Es más, se comprueba que, para esta matriz, el empleo delAMG-PCG es recomendable si se tiene un campo de velocidades tanto uniforme como circular.

Problema 6. El campo escalar u (x, y) = 20xy (1− x) (1− y), que en adelante llamaremos solu-ción polinómica, es solución en el dominio [0, 1]× [0, 1] de la ecuación de Poisson con condicionesde contorno Dirichlet homogéneas,

∂2u

∂x2+∂2u

∂y2= −40 [x (1− x) + y (1− y)] .

En adelante restringimos nuestra atención a los sistemas de orden mayor que 500, para los queel comportamiento se estabiliza. En la gura 3.1.1 se comprueba que el error queda siempre pordebajo de la tolerancia especicada, tanto para el laplaciano como para la matriz S del SMS. Paraesta última, el error relativo es un orden de magnitud inferior que la tolerancia, mientras que parael laplaciano discreto es varios órdenes menor. Por otra parte, se observa que el error es, por logeneral, mayor en redes no uniformes.

En cuanto a las iteraciones del gradiente conjugado, mencionamos que cada una de ellas equivalea un ciclo V. Es decir, el número de iteraciones equivale al de ciclos V. La gura 3.1.2 muestra ladiferencia más relevante entre usar el AMG-PCG con el laplaciano o con la matriz S del SMS. Así,para esta última se produce un mayor crecimiento del número de iteraciones al incrementar el ordendel sistema, siendo en todos los casos dicho crecimiento todavía mayor en las redes no uniformesfrente a las uniformes. Para el laplaciano discreto utilizando redes uniformes es interesante notaralgo que ya sabíamos, y es que el número de ciclos V apenas crece al aumentar el tamaño delsistema, esto es, al renar la malla. Este comportamiento óptimo no se observa para los otros casosestudiados. Sin embargo, para la situación más desfavorable, en que se tiene la matriz S del SMS

sobre una red no uniforme, el número de ciclos V aumenta con O(h−

12

), crecimiento que se puede

considerar aceptable.

2Algebraic Multigrid Preconditioned Conjugate Gradient.

CAPÍTULO 3. RESULTADOS NUMÉRICOS 47

Figura 3.1.1: Error relativo frente al orden de la matriz de coecientes para la solución polinómica


Figura 3.1.2: Número de iteraciones frente al orden de la matriz de coecientes para la soluciónpolinómica


Problema 7. El campo escalar u (x, y) = sinh xsinh 1

sinh ysinh 1

(1− sinh x

sinh 1

) (1− sinh y

sinh 1

), que en adelante

llamaremos solución hiperbólica, es solución en el dominio [0, 1]× [0, 1] de la ecuación de Poissoncon condiciones de contorno Dirichlet homogéneas,

∂2u

∂x2+∂2u

∂y2=

(sinhx

sinh 1− 2

sinh2 1

(sinh2 x+ cosh2 x

))(1− sinh y

sinh 1

)sinh y

sinh 1+

+

(sinh y

sinh 1− 2

sinh2 1

(sinh2 y + cosh2 y

))(1− sinhx

sinh 1

)sinhx

sinh 1.

Para la solución hiperbólica, los resultados se muestran en las guras 3.1.3 y 3.1.4. No merecencomentarios adicionales por ser análogos a los que se tienen para la solución polinómica. Lo que esimportante destacar es que el comportamiento descrito se repite para soluciones de tal complejidadque nos hace pensar que pueda ser extrapolable para otros términos fuente.


Figura 3.1.3: Error relativo frente al orden de la matriz de coecientes para la solución hiperbólica


Figura 3.1.4: Número de iteraciones frente al orden de la matriz de coecientes para la soluciónhiperbólica


3.2. SMS con campo de velocidades uniforme. Comparación

de los precondicionadores por bloques ideal y diagonal

con ~b = [2, 3]

Se tiene ahora el problema del SMS (1.2.56)-(1.2.57), derivado de (1.2.36)-(1.2.37) con uncampo de velocidades constante. En concreto, ~b = [2, 3], con coeciente de difusión ε = 10−8 (Elcorrecto funcionamiento de la técnica de estabilización SMS para este caso particular se compruebaen García-Archilla [18]). Los experimentos numéricos que se muestran emplean el precondicionadordiagonal y el ideal, con matriz de masa y matriz identidad como aproximación del complemento deSchur. El precondicionador ideal programado utiliza internamente tres gradientes conjugados conTOLCG =

√TOLMINRES , tolerancia para la que se obtiene un mejor comportamiento del error.

Un hecho que muestra la importancia que tiene el precondicionamiento de los métodos iterativos esque, para sistemas de orden elevado y utilizando MINRES sin precondicionar, se obtienen erroresrelativos del orden de la unidad.

A continuación, se muestran los resultados para una red uniforme con una tolerancia de 10−6,que son representativos de los obtenidos para 10−3, 10−8 y 10−9, con redes uniformes y no unifor-mes. Estos últimos se pueden consultar en el anexo correspondiente.

En la gura 3.2.1 se observa que solo el precondicionador diagonal con matriz de masa consiguereducir el error relativo por debajo de la tolerancia dada por el usuario. Para otros valores de dichatolerancia se repite este comportamiento. El precondicionador ideal da lugar a unos errores de unoy dos órdenes de magnitud mayor, especialmente el que utiliza la matriz identidad.

Figura 3.2.1: Comportamiento del error relativo frente al orden de la matriz de coecientes y elnúmero de ciclos V (eciencia). TOL = 10−6.

Por otra parte, la gura 3.2.2 muestra que el método MINRES con el precondicionador idealefectúa en torno a 10 veces menos iteraciones que utilizando el precondicionador diagonal. Esinteresante notar cómo, para sistemas de más de 20000 ecuaciones, el método MINRES convergeen una sola iteración cuando se utiliza la matriz identidad. Sin embargo, esto se consigue con unnúmero de ciclos V del mismo orden que el que realiza el precondicionador diagonal con matriz demasa, pero proporcionando un error relativo varios órdenes de magnitud mayor. Además, resulta


evidente que la implementación del precondicionador diagonal es bastante más sencilla que la delideal. Por tanto, este experimento sugiere que el método SMS con campo de velocidades constantedebe ser precondicionado con el precondicionador diagonal con matriz de masa que proponenElman, Silvester y Wathen para el problema de Stokes en [13].

Figura 3.2.2: Coste computacional medido en iteraciones de MINRES y en ciclos V frente al ordende la matriz de coecientes. TOL = 10−6.


3.3. SMS con campo de velocidades circular. Comparación

con ~b =[2y(1− x2

),−2x

(1− y2

)]de los precondiciona-

dores por bloques ideal y diagonal

Los resultados experimentales con ε = 10−4 (este caso particular es tratado en García-Archilla[18]) muestran que el precondicionador que proporciona errores que se ajustan a la toleranciadepende de esta última. Así, considerando redes uniformes, para valores de la tolerancia compren-didos entre 10−3 y 10−6, conviene recurrir al precondicionador diagonal con matriz identidad paraaproximar el complemento de Schur, como muestran las gura 3.3.1 y 3.3.2. Además, este precon-dicionador realiza siempre un menor número de ciclos V que el ideal. Para tolerancias menoresque 10−6, el precondicionador diagonal sigue siendo menos costoso, pero el error obtenido es entreuno y dos órdenes de magnitud mayor que la tolerancia, como muestra la gura 3.3.3. Además,para una tolerancia de 10−9, el comportamiento del error se hace oscilatorio. Por tanto, se ponede maniesto que, para reducir el error por debajo de la tolerancia, es necesario recurrir a unprecondicionador con un coste computacional excesivo, como muestran los grácos de eciencia.






Por otra parte, el número de iteraciones del método MINRES es en torno a 10 veces menorcuando se utiliza el precondicionador ideal. Sin embargo, el número de ciclos V, que es el verdaderoestimador del coste computacional, se multiplica aproximadamente por la misma cantidad, comomuestra la gura 3.3.4. Es decir, los resultados experimentales revelan que el precondicionadorideal es unas 10 veces más costoso que el precondicionador diagonal.


Es curioso notar cómo, para una tolerancia de 10−3, el precondicionador ideal con matrizidentidad llega a multiplicar el número de ciclos V por 10−3 respecto al precondicionador diagonal,como se observa en la gura 3.3.5.

Para redes no uniformes los resultados concuerdan con los obtenidos en redes uniformes, aunqueel error presenta un comportamiento marcadamente oscilatorio. Las guras se pueden consultar enel anexo correspondiente.

Por tanto, concluimos que, para campo circular, se debe aproximar en todos los casos el com-plemento de Schur por la matriz identidad. Esto ya supone una diferencia considerable respecto alcaso anterior, en el que se tenía un campo de velocidades constante en el dominio y la aproximacióndel complemento debía llevarse a cabo con la matriz de masa. Por otra parte, los errores aceptablesse consiguen, bien con el precondicionador diagonal, bien con el ideal, en función de la toleranciaespecicada.




3.4. Aproximación exacta del complemento de Schur, Q = C

Es evidente que la diferencia entre los resultados obtenidos se debe a la estructura del campode velocidades. Así, para un campo de velocidades constante, el precondicionador diagonal conmatriz de masa es la mejor opción para el método MINRES. Sin embargo, cuando se tiene uncampo de velocidades circular, más complejo, está elección no es tan clara. De hecho, aproximarel complemento de Schur por la matriz identidad parece siempre preferible.

Recordemos que en los dos precondicionadores empleados realizamos dos aproximaciones. Porun lado, sustituimos la acción de la inversa de la matriz S por un ciclo V, o bien por un gradienteconjugado precondicionado con ciclo V. Y por otro suponemos que el complemento de Schur separece, bien a la matriz identidad, bien a la matriz de masa de la discretización. Dado que enla construcción de ambos operadores, S y C, interviene el campo de velocidades, no es posibledeterminar a priori qué aproximación es la que estropea el comportamiento del precondicionador.Suponemos que es solo una de ellas, aunque bien podrían ser las dos. No obstante, la fundamen-tación teórica ampliamente documentada del método multigrid algebraico nos lleva a sospecharque el mal funcionamiento que pueda exhibir el precondicionador es debido exclusivamente a laaproximación del complemento de Schur. En efecto, los resultados experimentales muestran que,cuando la matriz Q se toma idéntica a C = AS−1At y los sistemas asociados se resuelven pormedio de la barra invertida de MATLAB, el método MINRES precondicionado reduce en todoslos casos el error por debajo de la tolerancia. A modo de ejemplo, véase la gura 3.4.1 para elcampo de velocidades no circular, y 3.4.2 para el campo de velocidades circular, ambas para reduniforme y tolerancia 10−6. En ambos casos se conrma que, aunque el precondicionador idealreduce en mayor medida el número de iteraciones de MINRES, el precondicionador diagonal esmenos costoso, entre dos y tres veces menos. En el anexo correspondiente se adjuntan los resultanpara campo circular y no circular, en red uniforme y no uniforme, y para las tolerancias 10−3, 10−6

y 10−9.Este resultado tiene una doble lectura. El aspecto negativo es que las aproximaciones de C

utilizadas tienen una validez condicionada por el campo de velocidades especíco del problema bajoestudio. La contrapartida positiva es que nos permite armar que el método multigrid algebraicoes un buen precondicionador para la matriz S del SMS, ya sea el campo de velocidades constanteo circular. Llegamos a esta conclusión porque, siendo el método multigrid algebraico la únicaaproximación existente en el precondicionador, los resultados se acercan bastante a los ideales.En primer lugar, el error sigue perfectamente a la tolerancia. Y en segundo lugar, el número deiteraciones del método MINRES con precondicionador ideal se encuentra próximo a las dos quepredice la teoría.


Figura 3.4.1: Error relativo y coste computacional para el campo de velocidades no circular en reduniforme con TOL = 10−6 y complemento de Schur exacto.

Figura 3.4.2: Error relativo y coste computacional para el campo de velocidades circular en reduniforme con TOL = 10−6 y complemento de Schur exacto.


Capítulo 4

Conclusiones

A la vista de los resultados numéricos obtenidos, se extraen las siguientes conclusiones:

El método AMG-PCG exhibe un buen comportamiento en la resolución de sistemas linealesque involucran a la matriz simétrica S del SMS. Es decir, el método AMG es un buenprecondicionador para dicha matriz, aunque es indudablemente mejor para el laplacianodiscreto. Esto se comprueba de manera directa para un campo de velocidades uniforme en3.1, y de manera indirecta para un campo de velocidades circular en 3.4.

El precondicionador ideal por bloques que utiliza el gradiente conjugado internamente esmaniestamente menos eciente que el precondicionador diagonal debido al elevado númerode ciclos V que requiere. Resulta engañoso el hecho de que el MINRES con el precondicionadorideal realice considerablemente menos iteraciones, puesto que lo hace a costa de un númerode ciclos V prohibitivo.

Para un campo de velocidades uniforme, el precondicionador diagonal con matriz de masamantiene siempre el error por debajo de la tolerancia especicada, tanto para redes uniformescomo no uniformes. Los otros tres precondicionadores exhiben serias dicultades para cumplirdicha especicación, por lo que se desaconseja su empleo en estas circunstancias.

Para un campo de velocidades circular, no existe un precondicionador que presente en todaslas tolerancias las características que se le exigen, a saber, reducido número de ciclos V yerror por debajo del especicado. Sin embargo, lo que sí se observa es que, en cada situación,el precondicionador que utiliza la matriz identidad es el que consigue mantener el error pordebajo de la tolerancia. El precondicionador por bloques sigue siendo demasiado ineciente,aunque a partir de tolerancias menores que 10−6 es el que consigue ajustarse mejor a latolerancia cuando se utiliza con la matriz identidad.

La razón de este comportamiento, que impide obtener una conclusión determinante, es que,para el campo de velocidades circular, la matriz de masa y la identidad no aproximan bien elcomplemento de Schur. Esto se comprueba en 3.4, donde la acción de Q−1 se sustituye porla resolución del sistema lineal asociado mediante la barra invertida de MATLAB, igualandoQ al complemento de Schur calculado de forma exacta. En este caso, el error relativo sigue ala tolerancia especicada.

De lo anterior se deduce que la pobre aproximación del complemento de Schur es la únicaresponsable del comportamiento indeseable del error relativo. Por tanto, como ya anunciamos,el método AMG es también un buen precondicionador para la matriz S del SMS cuando estase construye a partir de un campo circular de velocidades.

61

62 CAPÍTULO 4. CONCLUSIONES

Los hechos anteriores dejan varias cuestiones abiertas para trabajos posteriores, especialmentepor requerir unos conocimientos en cuestiones matemáticas que sobrepasan ampliamente los quecubre el plan de estudios de una carrera de ingeniería industrial:

Diseño de un precondicionador que aproxime de manera satisfactoria al complemento deSchur cuando se tiene un campo de velocidades genérico. En primera aproximación parecelógico que el procedimiento requerido para ello debe tener algún tipo de dependencia con laestructura del campo de velocidades, la cual no se ha tenido en cuenta en el presente trabajo.

Probar el método MINRES precondicionado de esta forma en problemas sobre dominiostridimensionales, que constituyen el campo de aplicación donde maniestan ventajas losmétodos iterativos de resolución frente a los métodos directos.

Anexos

63

Anexo A

Implementación en MATLAB

La implementación en MATLAB del precondicionador para el método SMS consta de los si-guientes archivos:

pminres.m es el método MINRES precondicionado particularizado para el método SMS.

amg_grids_setup.m (IFISS ) contiene una función llamada desde pminres. Recibe como en-tradas la matriz de coecientes del sistema, el método de interpolación (en este trabajosiempre es Stüben direct), y los tamaños máximo y mínimo de la matriz de coecientes en elnivel más basto. Devuelve una estructura que contiene la información relativa a cada nivel (lamatriz de coecientes y los operadores de interpolación y restricción), el número de niveles yel orden de la matriz en el nivel más basto.

amg_smoother_params.m (IFISS ) contiene una función llamada desde pminres, y generauna estructura con los parámetros de suavizado del método multigrid algebraico. Tiene comoentradas la estructura generada en amg_grids_setup, el tipo de suavizado (en este trabajosiempre se emplea PGS ) y el número de ciclos de suavizado (siempre dos).

amg_smoother_setup.m (IFISS ) genera los datos de suavizado para el método multigridalgebraico. Contiene una función que se ejecuta desde pminres, y que recibe como entradasla estructura con los parámetros de suavizado y la de los niveles de la red.

preconditioner.m implementa el precondicionador propiamente dicho para el método SMS.Es llamado desde minres de MATLAB.

amg_v_cycle.m (IFISS ) contiene la función que realiza un ciclo V del método multigridalgebraico. Recibe como entradas el vector de términos independientes, la estructura con losniveles y los datos de suavizado. Devuelve una estimación del vector solución, por lo que sepuede considerar una aproximación de la acción de la inversa del sistema.

amg_smoother.m (IFISS ) contiene la función encargada de realizar el suavizado. Es llamadainternamente por amg_v_cycle.

65

66 ANEXO A. IMPLEMENTACIÓN EN MATLAB

A.1. Método MINRES precondicionado para el SMS

1 function [ so l , PCG1, PCG2, PCG3, flag , i t e r , vcyc le , l e v e l , orden ] = pminres (S , A,F , Q, rho , TOL_MINRES, maxiter_MINRES , interpolat ion_method , smoother_method ,smoother_iter , nmax , nmin , cg , TOL_CG, maxiter_CG13 , maxiter_CG2)

23 %PMINRES es e l método MINRES precondic ionado para e l problema de Stokes y e l SMS4 %5 %OUTPUT6 % so l Vector so luc ión de l s i s tema l i n e a l [ S , A' ; A, 0 ]∗ s o l = F7 %PCG1 Estructura con informe de r e su l t a do s de l método AMG−PCG para i n v e r t i r S8 %PCG2 Estructura con informe de r e su l t a do s de l método AMG−PCG para i n v e r t i r Q9 %PCG3 Estructura con informe de r e su l t a do s de l método AMG−PCG para i n v e r t i r S10 % f l a g Aviso generado por e l método MINRES11 % Para más información consu l t a r l a ayuda para minres12 % i t e r Número de i t e r a c i on e s necesar io para convergencia13 % vcy l e Número de c i c l o s V r ea l i z a d o s14 % Medida de l co s t e computacional15 % l e v e l Número de n i v e l e s generados en e l método mu l t i g r i d a l g e b r a i c o16 % orden Orden de l s i s tema f i n a l que se r e su e l v e por un método d i r e c t o17 % ( barra i n v e r t i d a de Matlab ) en e l c i c l o V18 %19 %INPUT20 % S Bloque (1 , 1) . Se precondic iona con mu l t i g r i d a l g e b r a i c o21 %A Bloque (2 , 1) . Matriz r ec tangu la r22 %F Vector de términos independ ien tes23 %Q Precondicionador para e l complemento de Schur , C = A∗ inv (S)∗A'24 % rho Parámetro que in troduce una correcc ión en e l precondic ionador d iagona l :25 % − rho = 0 => Precondicionador d iagona l por b l oque s26 % − rho = 1 => Precondicionador por b l oques27 %TOL_MINRES Tolerancia de l res iduo r e l a t i v o para e l método MINRES28 % Condición de parada de l método i t e r a t i v o29 %maxiter_MINRES Número máximo de i t e r a c i on e s para e l método MINRES30 % Condición de parada de l método i t e r a t i v o31 %32 % Parámetros de l método mu l t i g r i d a l g e b r a i c o33 % interpo lat ion_method Método de in t e r po l a c i ón34 % smoother_method Método de suav izado35 % smoother_iter Número de i t e r a c i on e s para e l método de suav izado36 % nmax Tamaño máximo de l s is tema l i n e a l que se r e su e l v e usando un método37 % di r e c t o ( back s l a sh de Matlab ) en e l ú l t imo n i v e l d e l c i c l o V38 % nmin Tamaño mínimo de l s is tema l i n e a l que se r e su e l v e usando un método39 % di r e c t o ( back s l a sh de Matlab ) en e l ú l t imo n i v e l d e l c i c l o V40 %41 % Gradiente conjugado precondic ionado42 % cg Gradiente conjugado precondic ionado para cada b loque43 % − cg = 0 => No se u t i l i z a PCG44 % − cg = 1 => Se u t i l i z a PCG45 %TOL_CG Tolerancia de l res iduo r e l a t i v o para e l g rad i en t e conjugado46 % Condición de parada de l método i t e r a t i v o47 % maxiter_CG13 Número máximo de i t e r a c i on e s para e l g rad i en t e conjugado48 % asociado a l a matriz S49 % Condición de parada de l método i t e r a t i v o50 %maxiter_CG2 Número máximo de i t e r a c i on e s para e l g rad i en t e conjugado51 % asociado a l complemento de Schur52 % Condición de parada de l método i t e r a t i v o5354 %Con l a s v a r i a b l e s pcg1 , pcg2 y pcg3 se ob t ienen e l número de i t e r a c i on e s y e l55 % informe de convergencia en l a i t e r a c i on cont de l método MINRES56 global pcg1 pcg2 pcg3 cont ;5758 % Se comprueba que l a s dimensiones de l a s matr ices y l o s v e c t o r e s in t roduc ido s59 % son l a s adecuadas60 [ n , na ] = s ize (S) ;61 [m, ma] = s ize (A) ;62 [ l , l a ] = s ize (Q) ;6364 i f ( l a ~= l )

ANEXO A. IMPLEMENTACIÓN EN MATLAB 67

65 error ( ' Matrix Q must be square . ' ) ;66 end

67 i f ( na ~= n)68 error ( ' Matrix S must be square . ' ) ;69 end

70 i f (n ~= ma) | | (m ~= l ) | | ( na ~= ma) | | (m ~= la )71 error ( ' Matrix S must be square . ' ) ;72 end

73 i f ~ i s e qua l ( s ize (F) , [ n+m, 1 ] )74 error ( [ ' Right hand s i d e must be a column vec to r o f ' . . .75 ' l ength %d to match the c o e f f i c i e n t matrix . ' ] , n+m) ;76 end

7778 % Se comprueba que e l número de parámetros in t roduc ido s es e l cor rec to .79 %De lo con t rar io se asignan va l o r e s razonab l e s a l o s mismos80 i f nargin < 481 error ( 'Not enough input arguments . ' ) ;82 end

83 i f nargin < 5 | | isempty ( rho )84 rho = 0 ;85 end

86 i f nargin < 6 | | isempty (TOL_MINRES)87 TOL_MINRES = 10^−6;88 end

89 i f nargin < 7 | | isempty (maxiter_MINRES)90 maxiter_MINRES = m + n ;91 end

92 i f nargin < 8 | | isempty ( interpolat ion_method )93 interpolat ion_method = 1 ;94 end

95 i f nargin < 9 | | isempty ( smoother_method )96 smoother_method = 'PGS ' ;97 end

98 i f nargin < 10 | | isempty ( smoother_iter )99 smoother_iter = 2 ;100 end

101 i f nargin < 11 | | isempty (nmax)102 nmax = 400 ;103 end

104 i f nargin < 12 | | isempty (nmin )105 nmin = 80 ;106 end

107 i f nargin < 13 | | isempty ( cg )108 cg = 0 ;109 end

110 i f nargin < 14 | | isempty (TOL_CG)111 TOL_CG = 10^−3;112 end

113 i f nargin < 15 | | isempty (maxiter_CG13 )114 maxiter_CG13 = n ;115 end

116 i f nargin < 16 | | isempty (maxiter_CG2)117 maxiter_CG2 = m;118 end

119120 i f cg ~= 0 | | cg ~= 1121 cg = 0 ;122 end

123124 % Se separa en dos e l v ec to r de términos independ ien tes125 f = F( 1 : n , 1) ;126 g = F( ( n+1) : ( n+m) , 1) ;127128 % Se preparan l o s n i v e l e s d e l mu l t i g r i d a l g e b r a i c o129 [ amg_grid , l e v e l , orden ] = amg_grids_setup (S , . . .130 interpolat ion_method , nmax , nmin ) ;131 smoother_params = amg_smoother_params ( amg_grid , . . .132 smoother_method , smoother_iter ) ;133 amg_smoother = amg_smoother_setup ( amg_grid , smoother_params ) ;


134135 % Se par te de l a so luc ión i n i c i a l nula y se i n i c i a e l contador de i t e r a c i on e s de l136 % método MINRES137 x0 = zeros (n+m, 1) ;138 cont = 1 ;139140 % Se l lama a l método MINRES implementado en MATLAB141 [ so l , flag , r e l r e s , i t e r ] = minres ( [ S , A' ; A, sparse ( 1 :m, 1 :m, 0) ] , . . .142 [ f ; g ] , TOL_MINRES, maxiter_MINRES , ' p r e c ond i t i on e r ' , [ ] , . . .143 x0 , S , A, Q, rho , amg_grid , amg_smoother , cg , TOL_CG, . . .144 maxiter_CG13 , maxiter_CG2) ;145146 PCG1 = pcg1 ;147 PCG2 = pcg2 ;148 PCG3 = pcg3 ;149150 % Se ca l c u l a e l número de c i c l o s V r ea l i z a do s151 % Si no se u t i l i z a n g rad i en t e s conjugados intermedios , se r e a l i z a uno o dos c i c l o s152 %V por i t e r a c i ón de MINRES, dependiendo de s i se emplea e l precondic ionador i d e a l153 % o e l d iagona l154 i f cg == 0 %No se u t i l i z ó e l g rad i en t e conjugado155 i f rho == 0156 vcyc l e = i t e r ;157 else

158 vcyc l e = 2∗ i t e r ;159 end

160 % Si se u t i l i z a n g rad i en t e s conjugados intermedios , se r e a l i z a un c i c l o V por cada161 % i t e r a c i ón de l g rad i en t e conjugado con l a matriz S162 e l s e i f cg == 1 % Se u t i l i z ó e l g rad i en t e conjugado163 vcyc l e = sum(PCG1. i t e r ) + sum(PCG3. i t e r ) ;164 end

165166 clear global pcg1 pcg2 pcg3 cont ;167168 end

ANEXO A. IMPLEMENTACIÓN EN MATLAB 69

A.2. Precondicionador general para el método SMS

1 function [ z ] = pr e cond i t i on e r (F , S , A, Q, rho , amg_grid , amg_smoother , cg , TOLcg ,maxiter_CG13 , maxiter_CG2)

23 %PRECONDITIONER es e l precondic ionador para e l problema de Stokes y e l SMS45 global pcg1 pcg2 pcg3 cont ;67 n = s ize (S , 1) ;8 m = s ize (A, 1) ;9 f = F( 1 : n , 1) ;10 g = F( ( n+1) : ( n+m) , 1) ;11 x0 = zeros (n , 1) ;12 y0 = zeros (m, 1) ;1314 %No se u t i l i z a n g rad i en t e s conjugados intermedios15 i f cg == 016 % Se estima l a acción de l a inver sa de S mediante un c i c l o V17 V1 = amg_v_cycle ( f , amg_grid , amg_smoother ) ;18 pcg1 . f lag ( cont ) = 0 ;19 pcg1 . i t e r ( cont ) = 0 ;20 V2 = diag (Q) . \ ( g−rho∗A∗V1) ;21 pcg2 . f lag ( cont ) = 0 ;22 pcg2 . i t e r ( cont ) = 0 ;23 % Se ca l c u l a e l término co r r e c t i v o V324 i f rho == 025 % Precondicionador d iagona l de IFFIS :26 V3 = zeros (n , 1) ;27 pcg3 . f lag ( cont ) = 0 ;28 pcg3 . i t e r ( cont ) = 0 ;29 else

30 % Precondicionador i d e a l s i rho = 1:31 V3 = amg_v_cycle ( rho∗A'∗V2 , amg_grid , amg_smoother ) ;32 pcg3 . f lag ( cont ) = 0 ;33 pcg3 . i t e r ( cont ) = 0 ;34 end

35 % Se u t i l i z a n g rad i en t e s conjugados intermedios36 e l s e i f cg == 137 [V1 , f l ag1 , r e l r e s 1 , i t e r 1 ] = pcg (S , f , TOLcg , maxiter_CG13 , @amg_v_cycle , [ ] ,

x0 , amg_grid , amg_smoother ) ;38 pcg1 . f lag ( cont ) = f l a g 1 ;39 pcg1 . i t e r ( cont ) = i t e r 1 ;40 [V2 , f l ag2 , r e l r e s 2 , i t e r 2 ] = pcg (Q, g−rho∗A∗V1 , TOLcg , maxiter_CG2 , [ ] , [ ] , y0 )

;41 pcg2 . f lag ( cont ) = f l a g 2 ;42 pcg2 . i t e r ( cont ) = i t e r 2 ;43 i f rho == 044 % Precondicionador d iagona l :45 V3 = zeros (n , 1) ;46 pcg3 . f lag ( cont ) = 0 ;47 pcg3 . i t e r ( cont ) = 0 ;48 else

49 % Precondicionador i d e a l s i rho = 1:50 [V3 , f l ag3 , r e l r e s 3 , i t e r 3 ] = pcg (S , rho∗A'∗V2 , TOLcg , maxiter_CG13 ,

@amg_v_cycle , [ ] , x0 , amg_grid , amg_smoother ) ;51 pcg3 . f lag ( cont ) = f l a g 3 ;52 pcg3 . i t e r ( cont ) = i t e r 3 ;53 end

54 cont = cont + 1 ;55 end

5657 z = [V1 − V3 ; V2 ] ;5859 end


A.3. Modicaciones en amg_grids_setup.m de IFISS

En primer lugar, se modica la denición de la función original,

function [ grid_data ] = amg_grids_setup (A, i_method , max_levels ) ;

por

function [ grid_data , l e v e l , orden ] = amg_grids_setup (A, i_method , nmax , nmin )

Y la condición de parada del bucle principal,

while ( l e v e l <= max_levels+1) & (n_C ~= 1)

se cambia por

while ( numel ( grid_data ( l e v e l −1) .A) > nmax^2) && (n_C ~= 1)

Por último, al nal de la función se añaden las siguientes líneas de código,

l e v e l = l e v e l − 1 ;orden = s ize ( grid_data ( l e v e l ) .A, 1) ;

i f ( numel ( grid_data ( l e v e l ) .A) <= nmin^2)grid_data = grid_data ( 1 : l e v e l −1) ;l e v e l = l e v e l − 1 ;fpr intf ( ' \ nRes t r i c c i ón nmin provoca que e l orden de l a matr iz menos f i n a sea

mayor que nmax ' ) ;fpr intf ( ' \n%i g r id l e v e l s cons t ruc ted . \ n ' , l e v e l )

else

fprintf ( ' %i g r id l e v e l s cons t ruc ted . \ n ' , l e v e l )end

De esta forma se consigue que el sistema lineal que nalmente se resuelve mediante la barrainvertida de MATLAB tenga un orden comprendido entre nmın y nmax. El número de nivelesconstruidos depende, por tanto, del tamaño del sistema original, n0, y cumple aproximadamente

l ≈ 1 +ln

n0nf

d ln 2 , donde d es la dimensión del problema, y nf es el orden del sistema nal que seresuelve.

Anexo B

Resultados numéricos adicionales

B.1. Método SMS con campo de velocidades uniforme. Com-

paración de los precondicionadores por bloques ideal y

diagonal con ~b = [2, 3]

B.1.1. Red uniforme

Figura B.1.1: Comportamiento del error relativo frente al orden de la matriz de coecientes y elnúmero de ciclos V (eciencia). TOL = 10−3.

71

72 ANEXO B. RESULTADOS NUMÉRICOS ADICIONALES

Figura B.1.2: Coste computacional medido en iteraciones de MINRES y en ciclos V frente al ordende la matriz de coecientes. TOL = 10−3.


ANEXO B. RESULTADOS NUMÉRICOS ADICIONALES 73





B.1.2. Red no uniforme














B.2. Método SMS con campo de velocidades circular. Com-

paración de los precondicionadores por bloques ideal y

diagonal con ~b =[2y(1− x2

),−2x

(1− y2

)]B.2.1. Red uniforme



















B.3. Campo de velocidades no circular. Aproximación exacta

del complemento de Schur, Q = C

B.3.1. Red uniforme

Figura B.3.1: Error relativo y coste computacional para el campo de velocidades no circular en reduniforme con TOL = 10−3.


Figura B.3.2: Error relativo y coste computacional para el campo de velocidades no circular en reduniforme con TOL = 10−9.


Figura B.3.3: Error relativo y coste computacional para el campo de velocidades no circular en redno uniforme con TOL = 10−3.





B.4. Campo de velocidades circular. Aproximación exacta

del complemento de Schur, Q = C

B.4.1. Red uniforme

Figura B.4.1: Error relativo y coste computacional para el campo de velocidades circular en reduniforme con TOL = 10−3 y complemento de Schur exacto.


Figura B.4.2: Error relativo y coste computacional para el campo de velocidades circular en reduniforme con TOL = 10−9 y complemento de Schur exacto.


Figura B.4.3: Error relativo y coste computacional para el campo de velocidades circular en red nouniforme con TOL = 10−3 y complemento de Schur exacto.




Bibliografía

[1] T. M. APOSTOL. Análisis matemático. Reverté, Barcelona, 2001.

[2] M. BENZI, G. H. GOLUBT, and J. LIESEN. Numerical solution of saddle point problems.Acta Numer., 14:1137, 2005.

[3] F. BREZZI, D. MARINI, and A. RUSSO. Applications of the pseudo residual-free bubbles tothe stabilization of convection-diusion problems. Computer Methods in Applied Mechanicsand Engineering, 166(1-2):5163, 1998.

[4] R. L. BURDEN and J. D. FAIRES. Numerical Analysis. Brooks/Cole, Cengage Learning,Boston, MA, 2011.

[5] Z. CASTILLO and J. P. SUÁREZ. Evaluating block preconditioners in the solution of saddlepoint systems. Revista de la Facultad de Ingenieria, 25(4):715, 2010.

[6] P. E. CERUZZI. A History of Modern Computing. MIT Press, London, Eng.; Cambridge,Mass., 2003.

[7] KE CHEN. Matrix Preconditioning Techniques and Applications, volume 19. CambridgeUniversity Press, Cambridge, 2005.

[8] I. CHRISTIE, D. F. GRIFFITHS, A. R. MITCHELL, and O. C. ZIENKIEWICZ. Finiteelement methods for second order dierential equations with signicant rst derivatives. Int.J. Numer. Meth. Eng., 10(6):13891396, 1976.

[9] P. G. CIARLET. The Finite Element Method for Elliptic Problems. North-Holland, Amster-dam, 1987.

[10] D. P. DIVINCENZO. Quantum computation. Science, 270(5234):255261, 1995.

[11] I. S. DUFF, A. M. ERISMAN, and J. K. REID. Direct Methods for Sparse Matrices. ClarendonPress, Oxford, 1992.

[12] A. EKERT and R. JOZSA. Quantum computation and shor's factoring algorithm. Reviewsof Modern Physics, 68(3):733753, 1996.

[13] H. C. ELMAN, D. J. SILVESTER, and A. J. WATHEN. Finite Elements and Fast IterativeSolvers: with Applications in Incompressible Fluid Dynamics. Oxford University, Oxford, 2005.Howard C. Elman, David J. Silvester, Andrew J. Wathen.

[14] H. C. ELMAN, A. RAMAGE, and D. J. SILVESTER. Algorithm 866: Iss, a matlab toolboxfor modelling incompressible ow. ACM Transactions on Mathematical Software, 33(2), 2007.

[15] K. ERIKSSON. Computational Dierential Equations. Cambridge University Press, 1996.

[16] L. C. EVANS. Partial dierential equations, volume 19. American Mathematical Society,Providence, R.I., 2002.

[17] C. A. FELIPPA. A historical outline of matrix structural analysis: A play in three acts.Computers and Structures, 79(14):13131324, 2001.

91

92 BIBLIOGRAFÍA

[18] B. GARCÍA-ARCHILLA. Shishkin mesh simulation: A new stabilization technique forconvection-diusion problems. Computer Methods in Applied Mechanics and Engineering,256:116, 2013.

[19] K. K. GUPTA and J. L. MEEK. A brief history of the beginning of the nite element method.International Journal for Numerical Methods in Engineering, 39(22):37613774, 1996.

[20] T. J. R. HUGHES. The Finite Element Method: Linear Static and Dynamic Finite ElementAnalysis. Dover Publications, 2000.

[21] T. J. R. HUGHES and A. BROOKS. Multi-dimensional upwind scheme with no crosswinddiusion. American Society of Mechanical Engineers, Applied Mechanics Division, AMD, 34,1979.

[22] L. B. KISH. End of moore's law: Thermal (noise) death of integration in micro and nanoelectronics. Physics Letters, Section A: General, Atomic and Solid State Physics, 305(3-4):144149, 2002.

[23] M. LUNDSTROM. Applied physics: Moore's law forever? Science, 299(5604):210211, 2003.

[24] R. LÖHNER. Applied Computational Fluid Dynamics Techniques: an Introduction Based onFinite Element Methods. Wiley, Chichester; New York, 2001.

[25] J. J. H. MILLER, E. O'RIORDAN, and G. I. SHISHKIN. Fitted numerical methods forsingular perturbation problems: error estimates in the maximum norm for linear problems inone and two dimensions. World Scientic, Singapore; River Edge, NJ, 1996.

[26] C. B. MOLER. Numerical Computing with MATLAB. Siam, Philadelphia, 2010.

[27] G. E. MOORE. Cramming more components onto integrated circuits. Proceedings of theIEEE, 86(1):8285, 1998.

[28] K. W. MORTON. Numerical Solution of Convection-Diusion Problems, volume 12. Chapmanand Hall, London etc., 1996.

[29] C. C. PAIGE and M. A. SAUNDERS. Solution of sparse indenite systems of linear equations.SIAM J. Numer. Anal., 12(4):617629, 1975.

[30] F. H. PEREIRA, S. L. LOPES VERARDI, and S. I. NABETA. A fast algebraic multigridpreconditioned conjugate gradient solver. Appl. Math. Comput., 179(1):344351, 2006.

[31] A. QUARTERONI and A. VALLI. Numerical Approximation of Partial Dierential Equations,volume 23. Springer-Verlag, Berlin, 1994.

[32] J. N. REDDY. An Introduction to Nonlinear Finite Element Analysis. Oxford UniversityPress, Oxford, 2004.

[33] A. BARRERO RIPOLL and M. PÉREZ-SABORID SÁNCHEZ-PASTOR. Fundamentos yaplicaciones de la mecánica de uidos. McGraw-Hill Interamericana, Madrid, 2005.

[34] STEVEN ROMAN. Advanced Linear Algebra, volume 135. Springer, 2008.

[35] H.-G. ROOS, M. STYNES, and L. TOBISKA. Numerical Methods for Singularly PerturbedDierential Equations: Convection-Diusion and Flow Problems, volume 24. Springer-Verlag,Berlin etc., 1996.

[36] Y. SAAD. Iterative Methods for Sparse Linear Systems. Siam, Philadelphia, 2 edition, 2003.

[37] R. R. SCHALLER. Moore's law: past, present, and future. IEEE Spectrum, 34(6):5255, 57,1997.

[38] Y. SHAPIRA. Matrix-Based Multigrid, volume 2. Springer-Verlag, 2008.

BIBLIOGRAFÍA 93

[39] A. STEANE. Quantum computing. Reports on Progress in Physics, 61(2):117173, 1998.

[40] G. STRANG. Introduction to Applied Mathematics. Wellesley-Cambridge Press, Wellesley,Mass., 1986.

[41] K. STÜBEN. A review of algebraic multigrid. J. Comput. Appl. Math., 128(1-2):281309,2001.

[42] H. K. VERSTEEG and W. MALALASEKERA. An Introduction to Computational FluidDynamics: the Finite Volume Method. Pearson-Prentice Hall, Harlow England etc., 2007.

Documents

PROYECTO FIN DE CARRERA - bibing.us.esbibing.us.es/proyectos/abreproy/5414/fichero/Memoria.pdf · deduce la ecuación de convección-difusión no estacionaria en forma integral, @u