Jlkjl

Tema 3 Resolución de Sistemas de Ecuaciones Lineales
Índice

1. Introducción 2. Método de Gauss 2.1 2.2 2.3 2.4 Resolución de sistemas triangulares Triangulación por el método de Gauss Variante Gauss-Jordan Comentarios al método de Gauss

3. Inestabilidad del Método de Gauss y Estrategias de Pivote 3.1 Pivote parcial 3.2 Pivote total 4. Condicionamiento de sistemas de ecuaciones lineales 5.Otros métodos directos 5.1 Factorización LU 5.2 Método de Cholesky 6. Métodos iterativos usuales 6.1 Método de Jacobi 6.2 Método de Gauss-Seidel 6.3 Método de relajación

1

1.

Introducción

ciones lineales con n incógnitas:

El objetivo de este tema es la resolución de un sistema de n ecuaa11 x1 + a12 x2 + · · · + a1n xn = b1 , a21 x1 + a22 x2 + · · · + a2n xn = b2 , ... an1 x1 + an2x2 + · · · + ann xn = bn ,       

donde son conocidos la matriz de coecientes
a11 a12 · · · a1n  a21 a22 · · · a2n  A= . . .. . .  . . . . . . an1 an2 · · · ann      

y el vector de términos independientes
 b1  b2    b= .  .   . bn 

En notación matricial, el sistema de ecuaciones lineales se escribe:
Ax = b.

y se puede resolver por dos tipos de métodos:Métodos directos: son métodos que, en un número nito de operaciones, obtienen la solución exacta.

Métodos iterativos: son métodos que generan una sucesión de aproximaciones {x(m) } que converge a la solución del sistema: x = A−1 b. Recordemos que el Método de Cramer para la resolución de un sistema de n con n incógnitas x1 , . . . , xn consiste en calcular las incógnitas mediante la fórmulaxi = det Ai , det A i = 1, . . . , n,

2

siendo A la matriz de coecientes y Ai la matriz que resulta de sustituir la columna i-ésima de la matriz de coecientes por el vector de términos independientes. Teniendo en cuenta que el coste de un proceso de cálculo se puede estimar mediante el número total de operaciones aritméticas necesarias, entonces el coste de un determinante de orden n esn!n − 1 y, por tanto, el coste del Método de Cramer es (n + 1)n! − 1. A continuación aparece una tabla con el tiempo estimado para resolver con el método de Cramer un sistema de orden n, para distintos valores de n, con una máquina que realice unas 106 operaciones por segundo:
n Coste del Método de Cramer Tiempo (106 oper/s) 5 ≈ 3600 3,6 milisegundos 10 ≈ 4 × 108 6 minutos 39 segundos 20 ≈ 1,02 ×1021 32,4 millones de años

Algunos costes del método de Cramer

Por último, recordemos algunas deniciones sobre matrices
An×n = (aij ) se dice

si verica
AT = A−1 AT = A

Ortogonal Simétrica Diagonal Tridiagonal Triangular superior Hessenberg superior (Semi)Denida positiva (Estrictamente)Diagonalmente dominante

si i = j entonces aij = 0 si |i − j| > 1 entonces aij = 0 si i > jentonces aij = 0 si i > j + 1 entonces aij = 0
xt Ax(≥) > 0, ∀ x = 0 |aij |(k

tal que

|aik | = m´x |ark | a
k≤r≤n

y se

permuta con la ecuación

k. 1,00010... 0,99990
p.p.

0,0001 1 1 1 1 2

exacta

−→

Efectuando un cambio de la
1 1 2 0,0001 1 1 ∼ 1 1 2 0 1 1 −→ 0 1 1 1 . .

Pero

0,0001 1 1 0,0001 0,0001 0,0002

−→

p.p.

Pivote parcial con escalado:
(1)Igual que el pivote parcial, reescalando las
(2) (n)

ecuaciones antes del pivotaje para que

m´x |aij | = m´x |a2j | = · · · = m´x |anj |. a a a

8

3.2.

Pivote total

Se toma (i, j) tal que
|aij | = m´x |a(k) |, a rs
k≤r≤n k≤s≤n

(k)

y se permutan las ecuaciones i y k , y las incógnitas j y k .
4. Condicionamiento de Sistemas de Ecuaciones Lineales

Para entender elconcepto de condicionamiento, consideremos el siguiente ejemplo de R.S. Wilson: Se trata del sistema de ecuaciones lineales cuya matriz ampliada y solución exacta son:
 10  7   8 7 7 8 7 5 6 5 6 10 9 5 9 10   32 23  sol.exacta   −→   33  31  1 1  , 1  1

mientras que si se produce una pequeña variación en los términos independentes (datos) se produce una gran modicación en la...