![Page 1: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/1.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Resolución numérica de sistemas de ecuaciones.
Introducción
![Page 2: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/2.jpg)
SISTEMAS. INTRODUCCIÓN· 1
Índice
Motivación Objetivos Condiciones de existencia de solución Perspectiva numérica Clasificación de los métodos de resolución
![Page 3: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/3.jpg)
SISTEMAS. INTRODUCCIÓN · 2
Motivación La cercha de la figura se carga con una fuerza uniforme repartida sobre el cordón superior El planteamiento del problema conduce a un sistema lineal de ecuaciones de dimensión n=50 y en el que la matriz tiene la siguiente estructura Al resolver el sistema, obtenemos la deformada de la estructura
![Page 4: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/4.jpg)
SISTEMAS. INTRODUCCIÓN · 3
Puerto de Mataró
![Page 5: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/5.jpg)
SISTEMAS. INTRODUCCIÓN · 4
Puerto de Mataró
![Page 6: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/6.jpg)
En general, utilizando elementos finitos, tenemos que resolver sistemas lineales grandes y vacíos.
Muchas veces, la matriz es simétrica definida positiva. Por ejemplo: matriz de masa: matriz de rigidez (conductividad):
SISTEMAS. INTRODUCCIÓN · 5
![Page 7: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/7.jpg)
SISTEMAS. INTRODUCCIÓN · 6
Objetivos
La formulación de problemas de ingeniería a menudo conduce a sistemas lineales de ecuaciones. Estos sistemas pueden llegar a tener millones de grados de libertad. El objetivo de este tema es desarrollar estrategias numéricas que permitan resolver sistemas de ecuaciones grandes de una manera eficiente.
![Page 8: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/8.jpg)
SISTEMAS(1). MÉTODOS DIRECTOS ·
Existencia y unicidad de soluciones
Consideremos una matriz cuadrada Las siguientes condiciones son equivalentes:
1. Para cualquier el sistema tiene solución
2. Si tiene solución, ésta es única
3. Para cualquier ,
4. Las columnas (filas) de la matriz son linealmente independientes
5. Existe una matriz cuadrada (matriz inversa) tal que
6. La matriz tiene determinante no nulo
![Page 9: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/9.jpg)
SISTEMAS. INTRODUCCIÓN · 7
Perspectiva numérica
Las condiciones de existencia y unicidad no son útiles desde el punto de vista numérico Determinantes
El cálculo de un determinante es muy costoso. Además, es difícil decidir si es cero o no
Matriz inversa
El cálculo directo de la matriz inversa es muy costoso. Para calcularla se tienen que resolver n sistemas de ecuaciones de dimensión n: donde es la i-ésima columna de la matriz inversa y es el i-ésimo vector de la base canónica.
![Page 10: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/10.jpg)
SISTEMAS. INTRODUCCIÓN · 8
De hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para resolver un sistema de dimensión n con este método es
TC = (n+1)2n! – 1 Desde el punto de vista numérico buscaremos algoritmos eficientes en diferentes aspectos:
Número de operaciones necesarias (tiempo CPU) Necesidades de almacenamiento (memoria) Rango de aplicabilidad (sobre qué tipo de matrices se
pueden aplicar)
n TC
5 4319
10 4x108
100 10158 3x10142 años !!! 100 Mflops
![Page 11: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/11.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Clasificación de los métodos de resolución
![Page 12: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/12.jpg)
Clasificación de los métodos de resolución
1. Sistemas con solución inmediata - matrices diagonales - matrices triangulares
2. Métodos directos - método de Gauss - métodos de factorización - Crout, LU, Cholesky
3. Métodos iterativos - métodos estacionarios - Jacobi, Gauss-Seidel - métodos no estacionarios - Gradiente, gradiente conjugado, GMRES…
SISTEMAS. INTRODUCCIÓN · 9
![Page 13: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/13.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Sistemas con solución inmediata
![Page 14: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/14.jpg)
SISTEMAS CON SOLUCIÓN INMEDIATA· 1
Sistemas con solución inmediata
Sistemas con matriz diagonal Resolvemos . Coste computacional: n operaciones Sistema con matriz triangular superior (U)
Método de sustitución hacia atrás (backward substitution). Coste computacional: n2 operaciones
Sistema con matriz triangular inferior (L)
Método de sustitución hacia delante (forward substitution). Coste computacional: n2 operaciones
![Page 15: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/15.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Métodos directos
![Page 16: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/16.jpg)
Métodos directos
Mediante operaciones de fila o columna transformamos el sistema en uno de solución inmediata. La solución “exacta” (salvo errores de redondeo) se obtiene en un número finito de pasos. Métodos de eliminación (Gauss)
Coste computacional: eliminación + sustitución hacia atrás (2/3)n3 operaciones
SISTEMAS. MÉTODOS DIRECTOS · 1
A U
![Page 17: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/17.jpg)
Métodos de descomposición Métodos de Crout o de factorización LU Descomponemos la matriz del sistema en un producto de matrices triangulares:
SISTEMAS. MÉTODOS DIRECTOS · 2
triangular inferior
triangular superior
A U
L
![Page 18: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/18.jpg)
SISTEMAS. MÉTODOS DIRECTOS · 3
Entonces podemos resolver el sistema haciendo dos sustituciones Coste computacional: (2/3)n3 operaciones
calculamos con una sustitución hacia adelante
calculamos con una sustitución hacia atrás
La ventaja de este método respecto del de Gauss es que, una vez factorizada la matriz, puede utilizarse la descomposición para resolver varios sistemas, sin necesidad de conocer a priori los términos independientes. De este modo, para resolver cada sistema adicional sólo se tienen que hacer dos sustituciones (2n2 operaciones).
![Page 19: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/19.jpg)
SISTEMAS. MÉTODOS DIRECTOS · 4
Aplicabilidad de los métodos de Gauss, Crout, LU
Teorema: si A es invertible y se puede factorizar como A = LU, donde L tiene la diagonal unitaria, entonces la factorización es única
Teorema: si A es invertible existe una matriz de permutación P tal que PA=LU
Con pivotamiento total, siempre es posible hacer una factorización LU (o Gauss) de una matriz regular
Teorema: la condición necesaria y suficiente para que una matriz regular A se pueda descomponer como A = LU es que todos los menores principales tengan determinante no nulo
![Page 20: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/20.jpg)
Pivotamiento total Utilizando un pivotamiento total, llegamos a calcular una descomposición de la matriz de la forma: PAQ = LU donde: • P tiene en cuenta las permutaciones de filas • Q tiene en cuenta las permutaciones de columnas
Ejemplo: comando Matlab [L,U,P,Q]=lu(A) En este caso, obtenemos:
y tenemos que resolver dos sistemas triangulares
para calcular SISTEMAS. MÉTODOS DIRECTOS · 5
![Page 21: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/21.jpg)
• Método de Cholesky
• Método de Cholesky generalizado
SISTEMAS. MÉTODOS DIRECTOS · 6
A LT
L
Aplicabilidad: matrices simétricas y definidas positivas. Coste computaciónal: al aprovechar las características de la matriz, se realizan aproximadamente la mitad de operaciones que con el de Crout
TChol ≈ (1/3)n3
A LT
L D
Aplicabilidad: matrices simétricas.
![Page 22: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/22.jpg)
Skyline
SISTEMAS. MÉTODOS DIRECTOS · 7
0 10 20 30 40 50 60 70 80
0
10
20
30
40
50
60
70
80
nz = 1445
![Page 23: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/23.jpg)
Skyline storage
SISTEMAS. MÉTODOS DIRECTOS · 8
• Dimension n ~ 4000 • Band half-width s = 1737
• Assuming symmetry (only triangular matrix is stored) • Skyline storage ~ 106 coefficients • Band storage ~ 7 106 coefficients
![Page 24: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/24.jpg)
SISTEMAS. MÉTODOS DIRECTOS · 9
Llenado en métodos de factorización Al factorizar una matriz pueden aparecer coeficientes no
nulos donde inicialmente había ceros Se mantiene el skyline de la matriz
![Page 25: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/25.jpg)
SISTEMAS. MÉTODOS DIRECTOS · 10
• Estructura de barras 2D • 50 grados de libertad
![Page 26: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/26.jpg)
SISTEMAS. MÉTODOS DIRECTOS · 11
• Estructura de barras 3D • 111 grados de libertad
![Page 27: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/27.jpg)
Reordenación • Para reducir el fenómeno de llenado cuando se calculan las
factorizaciones de matrices, se pueden utilizar técnicas de reordenación.
• Existen muchos algoritmos de reordenación. • En Matlab, por ejemplo, encontramos el método “reverse
Cuthill-McKee ordering” (comando symrcm(A) )
SISTEMAS. MÉTODOS DIRECTOS · 12
A (nz=964)
LT (nz=1583)
A (nz=964)
LT (nz=4235)
![Page 28: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/28.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Métodos iterativos
![Page 29: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/29.jpg)
Métodos iterativos
• Idea: dada una aproximación inicial de la solución , calculamos nuevas aproximaciones que convergen a la solución del sistema
• La aproximación se calcula a partir de las anteriores, utilizando operaciones con vectores o productos matriz por vector
• Notación: • residuo • solución
SISTEMAS. MÉTODOS ITERATIVOS · 1
![Page 30: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/30.jpg)
• Métodos iterativos estacionarios
(que es un caso particular con , ) Ejemplos: Jacobi, Gauss-Seidel
• Métodos iterativos no estacionarios
Ejemplos: Gradiente, gradiente conjugado, GMRES
SISTEMAS. MÉTODOS ITERATIVOS · 2
Métodos iterativos
![Page 31: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/31.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Métodos iterativos estacionarios
![Page 32: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/32.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 3
• Método de Jacobi
• Método de Gauss-Seidel
Métodos clásicos
![Page 33: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/33.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 4
Métodos clásicos
Si consideramos la descomposición aditiva
se puede mostrar que podemos escribir los métodos de Jacobi y de Gauss-Seidel en la forma con
C = DA método de Jacobi C = LA+DA método de Gauss-Seidel
Por construcción, son métodos consistentes y la convergencia está asegurada si
![Page 34: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/34.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 4b
Consistencia
• Definición: • Un esquema iterativo es consistente si y
sólo si x* es el único punto fijo. 1. Es punto fijo: 2. Es el único punto fijo: consideremos tal que
, entonces
El sistema tiene solución única, , si y sólo si es regular
Para esquemas de la forma
1. x* es punto fijo por construcción 2. es el único punto fijo por ser C regular
![Page 35: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/35.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 5
Condiciones de convergencia El método de Jacobi es convergente si • A es diagonalmente dominante
El método de Gauss-Seidel es convergente si • A es diagonalmente dominante, o • A es simétrica y definida positiva
Observaciones: Los métodos vistos también se pueden aplicar por bloques
Gauss-Seidel por bloques:
![Page 36: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/36.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 6
Convergencia Definición: Un esquema iterativo es convergente si y sólo si el error en la iteración k, , cumple
para cualquier .
Análisis de convergencia Se asume consistencia del esquema El error cumple El esquema es convergente si
o, equivalentemente, si
< radio espectral
Condición necesaria y suficiente
![Page 37: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/37.jpg)
Criterios de convergencia Consideremos el comando Matlab:
[x,flag,relres,iter,resvec] = pcg (A,b,tol,maxit,M1,M2,x0) En general se puede demostrar que
Hay dos posibles criterios para terminar el proceso iterativo: Control del residuo
criterio significativo sólo para matrices con razonablemente pequeño (criterio utilizado en Matlab)
Control del incremento
criterio significativo sólo si SISTEMAS. MÉTODOS ITERATIVOS · 7
![Page 38: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/38.jpg)
Laboratori de Càlcul Numèric (LaCàN) Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Spain) http://www-lacan.upc.es
Métodos iterativos no estacionarios
![Page 39: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/39.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 8
Métodos iterativos no estacionarios El esquema cambia con las iteraciones Para empezar, consideremos una matriz A simétrica y
definida positiva. • Entonces, es solución del sistema si y sólo si
es el mínimo del funcional cuadrático:
A definida positiva
A singular
A definida negativa
A indefinida
![Page 40: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/40.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 9
Máximo descenso
• Idea: avanzar en la dirección de máxima pendiente
• La dirección del gradiente es la de máximo crecimiento de la función y, dado que se quiere resolver un problema de minimización, la dirección de avance será
• Esquema iterativo:
• se determina resolviendo un problema de minimización unidimensional
![Page 41: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/41.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 10 Figuras de “The Conjugate Gradient Method Without the Agonizing Pain”, J.R. Shewchuk
Máximo descenso: representación gráfica
![Page 42: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/42.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 11
Superficie definida por el funcional φ(x) y sus curvas de nivel con los vectores gradiente
![Page 43: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/43.jpg)
• Iteraciones del método de máximo descenso
Sólo se tiene en cuenta el comportamiento local de la función Se repiten direcciones de avance El comportamiento del método depende del condicionamiento
de la matriz (para matrices SDP, del cociente entre el mayor y el menor autovalor)
SISTEMAS. MÉTODOS ITERATIVOS · 12
![Page 44: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/44.jpg)
• Se puede mostrar que para el método de gradientes tenemos la siguiente cota de error:
donde y, como A es simétrica definida positiva,
• Cuanto mayor es , más lenta es la convergencia del método.
SISTEMAS. MÉTODOS ITERATIVOS · 13
![Page 45: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/45.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 14
Gradientes conjugados
• Idea: no repetir direcciones de avance
• Esquema iterativo: se determina resolviendo un problema de minimización
en la dirección de avance
Las direcciones de avance en cada iteración se escogen A-conjugadas y se definen como
con
![Page 46: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/46.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 15
Gradientes conjugados: algoritmo
Operaciones: • 2 matriz x vector • 3 productos escalares • 2 (escalar x vector) + vector
![Page 47: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/47.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 16
Gradientes conjugados: propiedades
Convergencia en n iteraciones como máximo
![Page 48: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/48.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 17
Gradientes conjugados: algoritmo mejorado
Operaciones: • 1 matriz x vector • 2 productos escalares • 3 (escalar x vector) + vector
![Page 49: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/49.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 18
• Iteraciones de gradientes conjugados
Converge en como máximo n iteraciones, siendo n la dimensión del sistema
Aunque en sentido estricto es un método directo (se llega a la solución en un número finito de pasos), se utiliza como iterativo porque normalmente converge mucho antes de n iteraciones.
![Page 50: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/50.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 19
Precondicionamiento
• La convergencia de un método iterativo depende del número de condición de la matriz del sistema, que para matrices SDP se define como
• Idea: reducir el número de condición de la matriz del sistema
• Se considera una matriz (precondicionador) tal que sea fácilmente inversible
y se resuelve el sistema equivalente
![Page 51: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/51.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 19b
• Con esta estructura se pierde la simetría de la matriz, de manera que para precondicionar gradientes conjugados se utiliza otra estrategia. Se resuelve un sistema
con
Si es una matriz SDP, su raíz cuadrada es la única matriz SDP que verifica .
Si diagonaliza como , se define
En la práctica el algoritmo se simplifica para evitar el cálculo de P1/2.
![Page 52: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/52.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 20
Gradientes conjugados precondicionado
Se tiene que resolver un sistema con matriz P
![Page 53: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/53.jpg)
SISTEMAS. MÉTODOS ITERATIVOS · 21
GMRES Método iterativo para matrices regulares cualesquiera. En cada iteración xk minimiza la norma euclídea del residuo
en x0+Kk:
– donde el k-ésimo espacio de Krylov se define como
• Observación: Kk⊂ Rn es de dimensión k, de manera que en la iteración n se calcula la minimización del error en Rn proporciona la solución x* (es decir, se obtiene la solución en n iteraciones como máximo)
Para resolver el problema de minimización se hacen varias reformulaciones.
Otros métodos: MINRES, BiCGStab, CGS (Matlab)
![Page 54: Resolución numérica de sistemas ... - · PDF fileDe hecho, métodos clásicos como el de Cramer tampoco sirven para resolver sistemas grandes. El número total de operaciones para](https://reader031.vdocumento.com/reader031/viewer/2022030400/5a7259027f8b9aa2538d7f50/html5/thumbnails/54.jpg)
Precondicionamiento
• Caracterizar un buen precondicionador es difícil.
• No existen reglas generales y se tiene que escoger en función de las características del problema.
• Algunas estrategias convencionales: • C = D (diagonal de A) precondicionador de Jacobi • C = LA + DA (parte triangular inferior de A) precondicionador
de Gauss-Seidel • C = ILU(A) (factorización incompleta de A)
• Otras técnicas utilizadas en práctica: multigrid, descomposición de dominios…
SISTEMAS. MÉTODOS ITERATIVOS · 22