MCI_Sistemas_2024

Vista previa del material en texto

Sistemas de Ecuaciones Lineales
MÉTODOS COMPUTACIONALES EN
INGENIERÍA I
Sistemas de ecuaciones lineales
Facultad de Ingeniería
Universidad Nacional del Comahue
web page: http://pedco.uncoma.edu.ar/
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Sistemas de Ecuaciones Lineales
Introducción
Los sistemas de ecuaciones lineales se utilizan en muchos
problemas de ingeniería, ciencias y en aplicaciones
matemáticas en otras áreas.
Se trabajará con métodos directos e iterativos que
resuelvan el sistema lineal
E1 : a11x1 + a12x2 + · · ·+ a1nxn = b1
E2 : a21x1 + a22x2 + · · ·+ a2nxn = b2
...
En : an1x1 + an2x2 + · · ·+ annxn = bn
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Directos
Operaciones fundamentales
Utilizamos tres operaciones para simplificar los sistemas lineales
1 La ecuación Ei puede multiplicarse por una constante λ 6= 0 y la
ecuación resultante se emplea en lugar de Ei
(λEi )→ (Ei )
2 La ecuación Ej puede multiplicarse por cualquier constante λ y sumarse
a la ecuación Ei , utilizando la ecuación resultante en vez de Ei .
(Ei + λEj )→ (Ei )
3 El orden de las ecuaciones Ei y Ej pueden intercambiarse.
(Ei )↔ (Ei )
Con estas operaciones podemos transformar un sistema lineal en otro que
puede resolverse más fácilmente con las mismas soluciones.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Ejemplo
Eliminación gaussiana con sustitución hacia atrás
Se resuelven las siguientes cuatro ecuaciones para x1, x2, x3 y x4:
E1 : x1 + x2 + 3x4 = 4
E2 : 2x1 + x2 − x3 + x4 = 1
E3 : 3x1 − x2 − x3 + 2x4 = −3
E4 : −x1 + 2x2 + 3x3 − x4 = 4
Utilizamos la ecuación E1 para eliminar la incógnita x1 en E2, E3 y E4, al
efectuar (E2 − 2E1)→ (E2), (E3 − 3E1)→ (E3) y (E4 + E1)→ (E4)
resultando
E1 : x1 + x2 + 3x4 = 4
E2 : −x2 − x3 − 5x4 = −7
E3 : −4x2 − x3 − 7x4 = −15
E4 : 3x2 + 3x3 + 2x4 = 8
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Ejemplo
Eliminación gaussiana con sustitución hacia atrás
En el sistema nuevo, usamos E2 para eliminar x2 en E3 y E4, al efectuar
(E3 − 4E2)→ (E3), (E4 + 3E2)→ (E4) resultando
E1 : x1 + x2 + 3x4 = 4
E2 : −x2 − x3 − 5x4 = −7
E3 : 3x3 + 13x4 = 13
E4 : −13x4 = −13
El sistema presenta una forma triangular (o reducida) y puede
resolverse mediante el proceso de sustitución hacia atrás:
De E4 tenemos x4 = 1, E3 puede resolverse para x3 y dar
x3 =
1
3
(13− 13x4) =
1
3
(13− 13) = 0 ⇒ x3 = 0
Continuando el proceso E2 y E1 nos dan x2 = 2 y x1 = −1
x2 = −(−7+5x4+x3)−(−7+5+0) = 2 y x1 = 4−3x4−x2 = 4−3−2 = −1
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Notación
Dado un sistema lineal general de n ecuaciones con n incógnitas
a11x1 + a12x2 + · · ·+ a1nxn = b1
a21x1 + a22x2 + · · ·+ a2nxn = b2
...
...
an1x1 + an2x2 + · · ·+ annxn =n
podemos representarlos mediante una matriz de A de n × n y un vector
b de n × 1
A =

a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann
 b =

b1
b2
...
bn

FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Notación
Combinando estas matrices podemos formar la matriz aumentada
[A|b] =

a11 a12 · · · a1n
... b1
a21 a22 · · · a2n
... b2
...
...
. . .
...
...
...
an1 an2 · · · ann
... bn

donde con la línea punteada vertical se separan los coeficientes de las
incógnitas de los valores situados en el lado derecho de las
ecuaciones.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
En el proceso general de eliminación gaussiana aplicado al sistema
lineal general o a su equivalente la matriz aumentada de coeficientes
[A|b], el primer paso será renombrar el sistema como:
à = [A|b] =

a11 a12 · · · a1n
... a1,n+1
a21 a22 · · · a2n
... a2,n+1
...
...
. . .
...
...
...
an1 an2 · · · ann
... an,n+1

donde A denota a la matriz formada por los coeficientes y los
elementos de la (n + 1)-ésima columna son los valores de b; es decir,
ai,n+1 = bi para toda i = 1, 2, · · · , n.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
Siempre que a11 6= 0, las operaciones correspondientes a Ej se
efectúan por cada j = 2, 3, · · · , n para eliminar el coeficiente de x1 en
cada uno de estos renglones
(Ej −
aj1
a11
E1)→ (Ej )
Aunque se espera que los elementos de los renglones 2 a n cambien
utilizaremos la misma notación aij para el elemento de la i-ésima fila y
j-ésima columna.
Aplicamos un procedimiento secuencial cuando i = 2, 3, · · · , n − 1 y
realizamos la operación para Ej para toda j = i + 1, i + 2, · · · , n a
condición de que aii 6= 0.
(Ej −
aji
aii
E1)→ (Ej )
De esta forma se anula el coeficiente de xi en cada fila debajo del
i-ésimo para todos los valores de i = 1, 2, · · · , n − 1.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
La matriz resultante tiene la forma
˜̃A =

a11 a12 · · · a1n−1 a1n
... a1,n+1
0 a22 · · · a2n−1 a2n
... a2,n+1
...
...
. . .
...
...
...
...
0 0 · · · 0 ann
... an,n+1

donde, salvo en el primer renglón no se espera que los valores de aij
concuerden con los de la matriz original Ã.
La matriz ˜̃A representa un sistema lineal con el mismo conjunto
solución que el sistema original.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
Dado que el nuevo sistema lineal es triangular
a11x1 + a12x2 + · · ·+ a1nxn = a1,n+1
a22x2 + · · ·+ a2nxn = a2,n+1
...
...
annxn = an,n+1
podemos efectuar la sustitución hacia atrás, al resolver la n-ésima
ecuación para xn obtenemos
xn =
an,n+1
an,n
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
Al resolver la (n − 1)-ésima ecuación para xn−1 y al utilizar la incógnita
xn obtenemos
xn−1 =
an−1,n+1 − an−1,nxn
an−1,n−1
Al continuar este proceso, obtenemos para cada
i = n − 1, n − 2, · · · , 2, 1
xi =
ai,n+1 − ai,nxn − ai,n−1xn−1 − · · · − ai,i+1xi+1
aii
=
ai,n+1 −
∑n
j=i+1 aijxj
aii
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
El procedimiento de eliminación gaussiana puede escribirse con
mayor precisión formando una sucesión de matrices aumentadas
Ã(1), Ã(2), · · · , Ã(n)
donde Ã(1) es la matriz aumentada inicial y Ã(k) para cada
k = 2, 3, · · · , n tiene los elementos a(k)ij donde
a(k)ij =

a(k−1)ij , para i = 1, 2, · · · , k − 1 y j = 1, 2, · · · , n + 1
0, para i = k , k + 1, · · · , n y j = 1, 2, · · · , k − 1
a(k−1)ij −
a(k−1)i,k−1
a(k−1)k−1,k−1
a(k−1)k−1,j , para i = k , k + 1, · · · , n y j = k , k + 1, · · · , n + 1
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
Por lo tanto, se obtiene el sistema lineal equivalente por el cual la
variable xk−1 se eliminó en las ecuaciones Ek ,Ek+1, · · · ,En
Ã(k) =

a(1)11 a
(1)
12 a
(1)
13 · · · a
(1)
1,k−1 a
(1)
1k · · · a
(1)
1n
... a(1)1,n+1
0 a(2)22 a
(2)
23 · · · a
(2)
2,k−1 a
(2)
2k · · · a
(2)
2n
... a(2)2,n+1
...
...
...
...
...
...
...
...
...
...
0 0 0 0 a(k−1)k−1,k−1 a
(k−1)
k−1,k · · · a
(k−1)
k−1,n
... a(k−1)k−1,n+1
0 0 0 0 0 a(k)kk · · · a
(k)
kn
... a(k)k,n+1
0 0 0 0 0 a(k)nk · ·· a
(k)
nn
... a(k)n,n+1

FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Presentación del método
El procedimiento fallará si uno de los siguientes elementos son cero
a(1)11 , a
(2)
22 , a
(3)
33 , · · · , a
(n−1)
n−1,n−1, a
(n)
nn
porque en ese caso, el siguiente paso(
Ei −
a(k)ik
a(k)kk
Ek
)
→ Ei
no puede efecturarse (lo cual ocurre si uno de a(1)11 , · · · , a
(n−1)
n−1,n−1 es
cero) o si no es posible realizar la sustitución hacia atrás (en este caso
a(n)nn = 0).
Lo anterior no necesariamente significa que el sistema no tiene
solución, sino que debe modificarse el método para obtenerla.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Ejemplo
Considere el sistema lineal
E1 : x1 − x2 + 2x3 − x4 = −8
E2 : 2x1 − 2x2 + 3x3 − 3x4 = −20
E3 : x1 + x2 + x3 = −2
E4 : x1 − x2 + 4x3 + 3x4 = 4
La matriz aumentada es
à = Ã(1) =

1 −1 2 −1
... −8
2 −2 3 −3
... −20
1 1 1 0
... −2
1 −1 4 3
... 4

FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Ejemplo
Al efectuar las operaciones
(E2 − 2E1)→ (E2) (E3 − E1)→ (E3) (E4 − E1)→ (E4)
Obtenemos
Ã(2) =

1 −1 2 −1
... −8
0 0 −1 −1
... −4
0 2 −1 1
... 6
0 0 2 4
... 12

Dado que a(2)22 denominado elemento pivote es cero, no podemos
continuar el procedimiento en su forma actual.
Pero la operación (Ei )↔ (Ej ) es permitida, por lo cual buscamos los
elementos a(2)32 y a
(2)
42 en el primer elemento no nulo.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Ejemplo
Puesto que a(2)32 6= 0, efectuamos la operación (E2)↔ (E3) para
obtener una nueva matriz
Ã(2)′ =

1 −1 2 −1
... −8
0 2 −1 1
... 6
0 0 −1 −1
... −4
0 0 2 4
... 12

Como ya se eliminó x2 de E3 y de E4, Ã(3) = Ã(2)′ y continuaremos los
cálculos con la operación (E4 + 2E3)↔ (E4), que nos da
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Ejemplo
Ã(4) =

1 −1 2 −1
... −8
0 2 −1 1
... 6
0 0 −1 −1
... −4
0 0 0 2
... 4

Finalmente, aplicamos la sustitución hacia atrás
x4 =
4
2
= 2, x3 =
[−4− (−1)x4]
−1 = 2
x2 =
[6− x4 − (−1)x3]
2
= 3, x1 =
[−8− (−1)x4 − 2x3 − (−1)x2]
1
= −7
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Observaciones
En el ejemplo anterior se explica que se realiza si el pivote a(k)kk = 0
para alguna k = 1, 2, · · · , n − 1.
La k -ésima columna de Ã(k−1) proveniente del k -ésimo renglón se
analiza en busca del primer elemento no nulo.
Si a(k)pk 6= 0 para alguna p, con k + 1 ≤ p ≤ n, entonces efectuamos la
operación (Ek )↔ (Ep) para obtener Ã(k−1)′ .
Después continuamos con el procedimiento para formar Ã(k), y así
sucesivamente.
Si a(k)pk = 0 para cada p, el sistema lineal no tiene solución única y el
procedimiento se interrumpe.
Finalmente, si a(n)nn = 0, el sistema lineal no tiene solución única y el
procedimiento vuelve a interrumpirse.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Pseudocódigo
En el pseudocódigo a continuación, se resume la
eliminación gaussiana con sustitución hacia atrás.
En el mismo se incorpora el pivoteo cuando uno de los
pivotes a(k)kk es nulo, intercambiando el k -ésimo renglón
con el p-ésimo renglón, donde p es el entero más pequeño
con valor más grande que k en donde a(k)pk no es cero.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Pseudocódigo
Resolver el sistema lineal de n × n
E1 : a11x1 + a12x2 + · · ·+ a1nxn = b1
E2 : a21x1 + a22x2 + · · ·+ a2nxn = b2
...
En : an1x1 + an2x2 + · · ·+ annxn = bn
ENTRADA: número de incógnitas y ecuaciones n, matriz aumentada A = aij donde
1 ≤ i ≤ n y 1 ≤ j ≤ n + 1
SALIDA: solución x1, x2, · · · , xn o mensaje de que el sistema lineal no tiene solución
única
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Pseudocódigo
Paso 1: Para i = 1, · · · , n − 1 haga pasos 2 a 4
Paso 2: Sea p el entero más pequeño con i ≤ p ≤ n y api 6= 0
Si no puede encontrarse un entero p
entonces SALIDA(no existe solución única) PARAR
Paso 3: Si p 6= i entonces realice (Ep)↔ (Ei )
Paso 4: Para j = i + 1, · · · , n haga pasos 5 y 6
Paso 5: Tome mji = aji/aii
Paso 6: Realice (Ej −mji Ei )↔ (Ej )
Paso 7: Si ann = 0 entonces SALIDA(no existe solución única)PARAR
Paso 8: Tome xn = an,n+1/ann (comience la sustitución hacia atrás)
Paso 9: Para i = n − 1, · · · , 1 tome
xi =
ai,n+1 −
∑n
j=i+1 aij xj
aii
Paso 10: SALIDA (x1, · · · , xn) (algoritmo finalizado con éxito) PARAR
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
Tanto el tiempo necesario para determinar los cálculos como el
subsecuente error de redondeo dependen de la cantidad de
operaciones que deban efectuarse.
En términos generales, el tiempo que tardamos en realizar una
multiplicación o una división en una computadora es similar, pero
mucho más largo que el que tardamos en efecturar una suma o una
resta.
No obstante, las diferencias reales en tiempo de ejecución dependen
del sistema de cálculo que estamos utilizando.
Para realizar el conteo de operaciones de un método trabajaremos en
forma general, en este caso con un sistema de n ecuaciones con n
incógnitas.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
En el pseudocódigo, no se efectúan operaciones
aritméticas antes de los pasos 5 y 6.
El paso 5, requiere efectuar (n − i) divisiones.
La sustitución de la ecuación Ej por (Ej −mjiEi) en el paso
6 requiere de multiplicar mji por cada término de Ei , lo cuál
nos da un total de (n − i)(n − i + 1) multiplicaciones.
Los términos de la ecuación resultante se restan al término
correspondiente de Ej efectuando (n − i)(n − i + 1) restas.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
Para cada i = 1, 2, · · · , n − 1 las operaciones necesarias en los pasos
5 y 6 son las siguientes:
Multiplicaciones y Divisiones:
(n − i) + (n − i)(n − i + 1) = (n − i)(n − i + 2)
Sumas y Restas:
(n − i)(n − i + 1)
El número total de operaciones que requieren estos pasos se obtiene
sumando los conteos de operaciones para cada i .
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
Utilizando las siguientes fórmulas
m∑
j=1
1 = m,
m∑
j=1
j =
m(m + 1)
2
,
m∑
j=1
j2 =
m(m + 1)(2m + 1)
6
y además, teniendo en cuenta que los conteos de operaciones
realizados son para i fija general, como i toma valores entre 1 y n − 1
se obtiene
Multiplicaciones y Divisiones:
n−1∑
i=1
(n − i)(n − i + 2) =
n−1∑
i=1
(n2 − 2ni + i2 + 2n − 2i)
= (n2 + 2n)
n−1∑
i=1
1− 2(n + 1)
n−1∑
i=1
i +
n−1∑
i=1
i2
=
2n3 + 3n2 − 5n
6
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
Sumas y Restas:
n−1∑
i=1
(n − i)(n − i + 1) =
n−1∑
i=1
(n2 − 2ni + i2 + n − i)
= (n2 + n)
n−1∑
i=1
1− (2n + 1)
n−1∑
i=1
i +
n−1∑
i=1
i2
=
n3 − n
3
Hasta aquí, se ha contabilizado la cantidad de operaciones
correspondientesa la eliminación gaussiana.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
Los pasos 8 y 9, corresponden a la sustitución hacia atrás.
El paso 8 requiere una división.
El paso 9 requiere (n − i) multiplicaciones y (n − i − 1) sumas en cada
término de la suma y después una resta y una división.
La cantidad total de sumas y divisiones de los pasos 8 y 9 es la
siguiente:
Multiplicaciones y Divisiones:
1 +
n−1∑
i=1
((n − i) + 1) = n
2 + n
2
Sumas y Restas:
n−1∑
i=1
((n − i − 1) + 1) = n
2 − n
2
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Conteo de Operaciones
Por lo tanto, el número total de operaciones aritméticas del
pseudocódigo será:
Multiplicaciones y Divisiones:
2n3 + 3n2 − 5n
6
+
n2 + n
2
=
n3
3
+ n2 − n
3
Sumas y Restas:
n3 − n
3
+
n2 − n
2
=
n3
3
+
n2
2
− 5n
6
Con n grande, el número total de multiplicaciones y divisiones es
aproximadamente igual a n3/3, al igual que el número total de sumas y
restas.
Así, la cantidad total de cálculos y tiempo necesarios aumentan con n
en proporción a n3.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Estrategias de Pivoteo
Cuando uno de los elementos del pivote a(k)kk es nulo, se requiere
intercambio de renglones, (Ek )↔ (Ep), donde p es el menor entero
mayor que k con a(k)pk 6= 0.
Si se requiere reducir el error de redondeo, pueden realizarse
intercambio de renglones aún cuando los elementos del pivote no sean
cero.
Si a(k)kk es de magnitud pequeña en comparación con a
(k)
jk , el
multiplicador mjk tendrá una magnitud mucho mayor que 1:
mjk =
a(k)jk
a(k)kk
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Eliminación gaussiana con sustitución hacia atrás
Estrategias de Pivoteo
Los errores de redondeo introducidos en el cálculo de uno
de los términos de a(k)kl se multiplicarán por mjk cuando se
calcule a(k)jl , lo cual puede incrementar el error inicial.
De igual forma, cuando se realiza la sustitución hacia atrás
con xk y un valor pequeño de a
(k)
kk , cualquier error del
numerador puede aumentar extraordinariamente por la
división entre a(k)kk :
xk =
a(k)k ,n+1 −
∑n
j=k+1 a
(k)
kj
a(k)kk
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Estrategias de Pivoteo
Ejemplo
Dado el siguiente sistema lineal con solución exacta x1 = 10.00 y
x2 = 1.000; realizar la eliminación gaussiana con redondeo a cuatro cifras.
E1 : 0.003000x1 + 59.14x2 = 59.17
E2 : 5.291x1 − 6.130x2 = 46.78
El primer elemento del pivote es un número pequeño a(1)11 = 0.003000 y
su multiplicador asociado
m21 =
5.291
0.003000
= 1763.66⇒ se redondea a 1764
Al realizar (E2 −m21E1)→ (E2) y el redondeo adecuado, obtenemos
0.003000x1 + 59.14x2 ≈ 59.17
−104300x2 ≈ 104400
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Estrategias de Pivoteo
Ejemplo
Observar que los valores exactos sin redondeo a cuatro cifras son
0.003000x1 + 59.14x2 = 59.17
−104309x2 = 104309.376
La disparidad de las magnitudes de m21a13 y a23 ha ocasionado el error
de redondeo, pero este todavía no se ha propagado.
La sustitución hacia atrás produce x2 ≈ 1.001 que es una aproximación
cercana al valor real x2 = 1.000.
Debido al pivote pequeño a11 = 0.003000
x1 ≈
59.17− (59.14)(1.001)
(0.003000)
= −10.00
x1 contiene el pequeño error de 0.001 multiplicado por 59.140.003000 ≈ 20000,
Lo cual arruina la aproximación al valor real de x1 = 10.00.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Estrategias de Pivoteo
Pivoteo Parcial
En el ejemplo anterior, se observaron los problemas que pueden surgir
cuando el elemento pivote a(k)kk es pequeño en comparación con los
elementos a(k)ij para k ≤ i ≤ n y k ≤ j ≤ n.
Para evitar este problema empleamos el pivote seleccionando un
elemento mayor a(k)pq como pivote e intercambiando los renglones
k -ésimo y p-ésimo y, en caso necesario, intercambiando después las
columnas k -ésima y q-ésima.
La estrategia más sencilla es conocida como pivoteo parcial y
consiste en escoger el elemento en la misma columna que esta debajo
de la diagonal y que tiene el máximo valor absoluto: se busca la más
pequeña p ≥ k tal que
|a(k)pq | = máx
k≤i≤n
|a(k)ik |
y luego se efectua el intercambio (Ek )→ (Ep)
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Pivoteo Parcial
Ejemplo
Reconsideremos el sistema
E1 : 0.003000x1 + 59.14x2 = 59.17
E2 : 5.291x1 − 6.130x2 = 46.78
Con el procedimiento que se describió primero se obtiene
máx{|a(1)11 |, |a
(1)
21 |} = máx{|0.003000|, |5.291|} = |5.291| = |a
(1)
21 |
Efectuamos la operación (E2)→ (E1) para obtener el sistema
E1 : 5.291x1 − 6.130x2 = 46.78
E2 : 0.003000x1 + 59.14x2 = 59.17
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Pivoteo Parcial
Ejemplo
El multiplicador para este sistema es
m21 =
a(1)21
a(1)11
= 0.0005670
La operación (E2 −m21E1)→ (E2) reduce el sistema
5.291x1 − 6.130x2 ≈ 46.78
59.14x2 ≈ 59.14
Las respuestas de cuatro dígitos que surgen de la sustitución hacia
atrás son los valores correctos x1 = 10.00 y x2 = 1.000.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Estrategias de Pivoteo
Pivoteo Total
Otra estrategia posible de pivoteo es el pivoteo total o
completo.
Este pivoteo en el k -ésimo paso busca todos los
elementos aij , para i = k , k + 1, · · · ,n y j = k , k + 1, · · · ,n
con el fin de localizar el de mayor magnitud.
Los intercambios de renglones y columnas se realizan
para poner este elemento en la posición de pivote.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Tipos especiales de matrices
Matriz estrictamente diagonal dominante
Se dice que la matriz A de n × n es estrictamente diagonal
dominante cuando para toda i = 1, 2, · · · , n
|aii | >
n∑
j=1,j 6=i
|aij |
Ejemplos:
Dada A = [7, 2, 0; 3, 5,−1; 0, 5,−6] es estrictamente diagonal
dominante porque |7| > |2|+ |0|, |5| > |3|+ | − 1| y
| − 6| > |0|+ |5|.
La matriz B = [6, 4,−3; 4,−2, 0;−3, 0, 1] no es e.d.d ya que en el
primer renglón se tiene |6| < |4|+ | − 3| = 7.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Tipos especiales de matrices
Matriz de Banda
Teorema: Una matriz estrictamente diagonal dominante es no singular.
Más aún, se podrá realizar la eliminación gaussiana sin intercambios
de renglones ni columnas y los cálculos serán estables respecto al
crecimiento de los errores de redondeo.
Una matriz de n× n recibe el nombre de matriz de banda si existen los
enteros p y q con 1 < p, q < n, que tienen la propiedad de que aij = 0
siempre que i + p ≤ j o j + q ≤ i . El ancho de banda se define como
w = p + q − 1.
Las matrices tridiagonales se presentan cuando el ancho de banda
es 3, es decir p = q = 2.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Vectorial
Para medir la distancia entre dos vectores y poder definir el error entre
dos soluciones: aproximada y exacta o la que se tenga de referencia se
utilizará el concepto de norma vectorial.
Una norma vectorial en Rn es una función ||.|| : Rn → R con las
siguientes propiedades:
(i) ||x || ≥ 0 para todo x ∈ Rn
(ii) ||x || = 0 si y sólo si x = 0
(iii) ||αx || = |α|||x || para todo α ∈ R y x ∈ Rn
(iv) ||x + y || ≤ ||x ||+ ||y || para todo x , y ∈ Rn
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Vectorial
Las normas euclidea l2 e infinita l∞ del vector x = (x1, x2, · · · , xn)t
están definidas por
||x ||2 =
[
n∑
i=1
x2i
]1/2
y ||x ||∞ = máx1≤i≤n
|xi |
Ejemplo: Dado x = (−1, 1,−2)t en R3 tiene las normas
||x ||2 =
√
(−1)2 + (1)2 + (−2)2 =
√
6 y ||x ||∞ = máx{|−1|, |1|, |−2|} = 2
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Vectorial
Como la norma de un vector nos da una medida de la distancia entre
un vector arbitrario y el vector cero, podemos definir la distancia entre
dos vectores como la norma de la diferencia de los mismos.
Si x = (x1, x2, · · · , xn)t e y = (y1, y2, · · · , yn)t son vectores de Rn, las
distancias l2 y l∞ entre x e y están definidas por
||x − y ||2 =
[
n∑
i=1
(xi − yi )2
]1/2
||x − y ||∞ = máx
1≤i≤n
|xi − yi |
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Vectorial
Ejemplo: Si dado un sistema de 3× 3 con solución exacta
x = (1, 1, 1)t y solución aproximada mediante eliminación gaussiana
x̃ = (1.2001, 0.99991, 0.92538)t , las mediciones que se obtienen son
||x−x̃ ||2 = [(1−1.2001)2+(1−0.99991)2+(1−0.92538)2]1/2 = 0.21356
||x − x̃ ||∞ = máx{|1− 1.2001|, |1− 0.99991|, |1− 0.92538|} = 0.2001
Aunque las componentes x̃2 y x̃3 son buenas aproximaciones de x2 y
x3, la componente x̃1 es una aproximación deficiente de x1 y |x1 − x̃1|
domina las normas.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Vectorial
Se dice que una sucesión {x (k)}nk=1 de vectores en Rn
converge a x respecto a la norma ||.|| si dado cualquier
ε > 0, existe un entero N(ε) tal que
||x (k) − x || < ε, para todo k ≥ N(ε).
Se puede probar que las normas son equivalentes, salvo
una constante. Por lo tanto, a los fines prácticos pueden
utilizarse cualquiera de ellas.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Matricial
Una norma matricial sobre el conjunto de todas las matrices de n × n
es una función de valor real ||.|| definida en este conjunto y que
satisface para todas las matrices A y B de n × n y todos los números
reales α:
(i) ||A|| ≥ 0
(ii) ||A|| = 0 si y sólo si A es la matriz nula
(iii) ||αA|| = |α|||A||
(iv) ||A + B|| ≤ ||A||+ ||B||
(v) ||AB|| ≤ ||A||||B||
La distancia entre las matrices A y B de n × n respecto a esta norma
matricial es ||A− B||.
La norma matricial que consideraremos es la norma matricial infinita,
dada A = aij de n × n se tiene que
||A||∞ = máx
1≤i≤n
n∑
j=1
|aij |
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Normas de vectores y matrices
Norma Matricial
Ejemplo: Si A = [1, 2,−1; 0, 3,−1; 5,−1, 1] entonces
3∑
j=1
|a1j | = |1|+ |2|+ | − 1| = 4
3∑
j=1
|a2j | = |0|+ |3|+ | − 1| = 4
3∑
j=1
|a3j | = |5|+ | − 1|+ |1| = 7
Luego:
||A||∞ = máx{4, 4, 7} = 7
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Los métodos iterativos en general no se utilizan para
resolver sistemas de pequeña dimensión ya que el tiempo
necesario para conseguir una exatitud satisfactoria rebasa
el que requieren los métodos directos como el de la
eliminación gaussiana.
En sistemas grandes con un alto porcentaje de elementos
cero, son eficientes tanto en almacenamiento como en el
tiempo de cómputo frente a los métodos directos.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Un método iterativo con el cual se resuelve el sistema lineal Ax = b
comienza con una aproximación inicial x (0) a la solución x y genera una
sucesión de vectores {x (k)}∞k=0 que converge a x .
Los métodos iterativos convierten el sistema Ax = b en otro equivalente
de la forma x = Tx + c para alguna matriz fija T y un vector c.
Luego de seleccionado el vector inicial x (0) la sucesión de vectores de
la solución aproximada se genera calculando para k = 1, 2, 3, · · ·
x (k) = Tx (k−1) + c
Observar la similitud con la iteración de punto fijo.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Método de Jacobi
Ejemplo
Dado el siguiente sistema lineal con solución única x = (1, 2,−1, 1)t
E1 : 10x1 − x2 + 2x3 = 6
E2 : −x1 + 11x2 − x3 + 3x4 = 25
E3 : 2x1 − x2 + 10x3 − x4 = −11
E4 : 3x2 − x3 + 8x4 = 15
Para convertir Ax = b en la forma x = Tx + c, resolvemos la ecuación Ei para xi
con cada i = 1, 2, 3, 4 y así obtenemos
x1 =
1
10
x2 −
1
5
x3 +
3
5
x2 =
1
11
x1 +
1
11
x3 −
3
11
x4 +
25
11
x3 = −
1
5
x1 +
1
10
x2 +
1
10
x4 −
11
10
x4 = −
3
8
x2 +
1
8
x3 +
15
8
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos de Jacobi
Ejemplo
Si queremos escribirlo como x = Tx + c, utilizamos
T =

0 110 −
1
5 0
1
11 0
1
11 −
3
11
− 15
1
10 0 −
11
10
0 − 38
1
8 0
 y c =

3
5
25
11
− 1110
15
8

Tomando x (0) = (0, 0, 0, 0)t , encontramos x (1) calculando
x (1)1 =
1
10
x (0)2 −
1
5
x (0)3 +
3
5
x (1)2 =
1
11
x (0)1 +
1
11
x (0)3 −
3
11
x (0)4 +
25
11
x (1)3 = −
1
5
x (0)1 +
1
10
x (0)2 +
1
10
x (0)4 −
11
10
x (1)4 = −
3
8
x (0)2 +
1
8
x (0)3 +
15
8
El proceso continúa similarmente para encontrar las siguientes iteraciones.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Jacobi
Un criterio de parada podría ser el cálculo del error relativo ya sea en
un número máximo de iteraciones o con una tolerancia definida.
||x (n) − x (n−1)||∞
||x (n)||∞
< TOL
Formalmente, el Método iterativo de Jacobi consiste en resolver la
i-ésima ecuación en Ax = b para xi a fin de obtener (siempre que
aii 6= 0)
xi =
n∑
j=1,j 6=i
(
−aijxj
aii
)
+
bi
aii
, para i = 1, 2, · · · , n
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Jacobi
Además, generar cada x (k)i a partir de los componentes de x
(k−1)
cuando k ≥ 1 por medio de
x (k)i =
∑n
j=1,j 6=i
(
−aijx (k−1)j
)
+ bi
aii
, para i = 1, 2, · · · , n
El método se escribe en la forma x (k) = Tx (k−1) + c separando A en
sus partes diagonales y fuera de la diagonal, es decir A = D − L− U,
luego si
A =

a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann

FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Jacobi
A = D − L− U
=

a11 0 · · · 0
0 a22 · · · 0
...
...
. . .
...
0 0 · · · ann
−

0 0 · · · 0
−a21 0 · · · 0
...
...
. . .
...
−an1 −an2 · · · 0
−

0 −a12 · · · −a1n
0 0 · · · −a2n
...
...
. . .
...
0 0 · · · 0

Se transforma la ecuación Ax = b o (D − L− U)x = b en
Dx = (L + U)x + b
x = D−1(L + U)x + D−1b siempre que exista la inversa
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Jacobi
Esto da origen a la forma matricial del método iterativo de Jacobi:
x (k) = D−1(L + U)x (k−1) + D−1b con k = 1, 2, · · ·
Luego tendremos la forma de punto fijo
x (k) = Tjx (k−1) + cj
Donde
Tj = D−1(L + U) y cj = D−1b
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Método iterativo de Jacobi
Pseudocódigo
Resolver Ax = b dada una aproximación inicial x (0)
ENTRADA: número de incógnitas y ecuaciones n, elementos aij donde 1 ≤ i, j ≤ n,
elementos XOi donde 1 ≤ i ≤ n, tolerancia TOL, número máximo de iteraciones N
SALIDA: solución aproximada x1, x2, · · · , xn o mensaje
Paso 1: Tomar k = 1
Paso 2: Mientras (k ≤ N) haga pasos 3-6
Paso 3: Para i = 1, · · · , n
xi =
−
∑n
j=1,j 6=i (−aij XOj ) + bi
aii
Paso 4: Si ||x − XO|| < TOL entonces SALIDA(x1, · · · , xn) PARAR (éxito)
Paso 5: Tome k = k + 1
Paso 6: Para i = 1, · · · , n tome XOi = xi
Paso 7: SALIDA(Se supero el número máximo de iteraciones) PARAR (sin éxito)
FAIN-UNCOMA
MÉTODOS COMPUTACIONALESEN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Jacobi
El paso 3 del pseudocódigo requiere que aii 6= 0 para cada
i = 1, 2, · · · , n.
Si uno de los elementos aii es nulo y si el sistema es no singular,
pueden reordenarse las ecuaciones de modo que ningún aii sea cero.
Para acelerar la convergencia, se pueden arreglar las ecuaciones de
modo que aii sea lo más grande posible.
Otro posible criterio de parada en el paso 4 consiste en iterar hasta
que
||x (k) − x (k−1)||
||x (k)||
< TOL
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Gauss-Seidel
Analizando el método de Jacobi, se puede realizar una mejora.
Al calcular x (k)i se utilizan las componentes de x
(k−1), pero para i > 1
ya se calcularon x (k)1 , · · · , x
(k)
i−1 y probablemente sean mejores
aproximaciones de las soluciones reales x1, · · · , xi−1 que
x (k−1)1 , · · · , x
(k−1)
i−1 .
Esto es
x (k)i =
−
∑i−1
j=1 (aijx
(k)
j )−
∑n
j=i+1(aijx
(k−1)
j ) + bi
aii
, para i = 1, 2, · · · , n
Esta modificación se conoce como el Método iterativo de
Gauss-Seidel.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Método de Gauss-Seidel
Ejemplo
Dado el sistema del ejemplo anterior y trabajando sobre las ecuaciones
ya calculadas para Jacobi
x (k)1 =
1
10
x (k−1)2 −
1
5
x (k−1)3 +
3
5
x (k)2 =
1
11
x (k)1 +
1
11
x (k−1)3 −
3
11
x (k−1)4 +
25
11
x (k)3 = −
1
5
x (k)1 +
1
10
x (k)2 +
1
10
x (k−1)4 −
11
10
x (k)4 = −
3
8
x (k)2 +
1
8
x (k)3 +
15
8
El proceso continua de manera similar.
Comparando ambos métodos en este ejemplo el método de Jacobi requirió más
del doble de iteraciones que el método de Gauss-Seidel para alcanzar el mismo
grado de exactitud.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Método de Gauss-Seidel
Ejemplo
Para expresar la forma matricial del método iterativo de
Gauss-Seidel, se multiplica a ambos lados de la ecuación para x (k)i por
aii y se reunen todos los k -ésimos términos de iteración obteniendo
para cada i = 1, 2, · · · , n:
ai1x
(k)
1 + ai2x
(k)
2 + · · ·+ aiix
(k)
i = −ai,i+1x
(k−1)
i+1 − · · · − ainx
(k−1)
n + bi
Al escribir todas las n ecuaciones obtenemos
a11x
(k)
1 = −a12x
(k−1)
2 − a13x
(k−1)
3 − · · · − a1nx
(k−1)
n + b1
a21x
(k)
1 + a22x
(k)
2 = −a23x
(k−1)
3 − · · · − a2nx
(k−1)
n + b2
an1x
(k)
1 + an2x
(k)
2 + · · · + annx
(k)
n = bn
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Método de Jacobi
Con las definiciones de D, L y U se deduce que
(D−L)x (k) = Ux (k−1) +b o bien x (k) = (D−L)−1Ux (k−1) +(D−L)−1b
Luego tendremos la forma de punto fijo
x (k) = Tgx (k−1) + cg
Donde
Tg = (D − L)−1U y cg = (D − L)−1b
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Pseudocódigo
Método iterativo de Gauss-Seidel
Resolver Ax = b dada una aproximación inicial x (0)
ENTRADA: número de incógnitas y ecuaciones n, elementos aij donde 1 ≤ i, j ≤ n,
elementos XOi donde 1 ≤ i ≤ n, tolerancia TOL, número máximo de iteraciones N
SALIDA: solución aproximada x1, x2, · · · , xn o mensaje
Paso 1: Tomar k = 1
Paso 2: Mientras (k ≤ N) haga pasos 3-6
Paso 3: Para i = 1, · · · , n
xi =
−
∑i−1
j=1 (aij xj )−
∑n
j=i+1(aij XOj ) + bi
aii
Paso 4: Si ||x − XO|| < TOL entonces SALIDA(x1, · · · , xn) PARAR (éxito)
Paso 5: Tome k = k + 1
Paso 6: Para i = 1, · · · , n tome XOi = xi
Paso 7: SALIDA(Se supero el número máximo de iteraciones) PARAR (sin éxito)
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Radio Espectral
El radio espectral ρ(A) de una matriz A está definido por
ρ(A) = máx |λ| donde λ es un autovalor de A
Teorema: Para cualquier x (0) ∈ Rn, la sucesión {x (k)}∞k=0 definida por
x (k) = Tx (k−1) + c, para cada k ≥ 1,
converge a la solución única de x = Tx + c si y sólo si ρ(T ) < 1.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Radio Espectral
Corolario: Si ||T || < 1 para toda norma matricial natural y si c es un
vector cualquiera, entonces la sucesión {x (k)}∞k=0 definida por
x (k) = Tx (k−1) + c converge, para cualquier x (0) ∈ Rn, a un vector
x ∈ Rn, y las siguientes cotas de error son válidas:
||x − x (k)|| ≤ ||T ||k ||x (0) − x ||
||x − x (k)|| ≤ ||T ||
k
1− ||T || ||x
(1) − x (0)||
Teorema: Si A es estrictamente diagonal dominante, entonces con
cualquier elección de x (0), tanto el método de Jacobi como el de
Gauss-Seidel dan sucesiones {x (k)}∞k=0 que convergen a la solución
única de Ax = b.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Sistemas de Ecuaciones Lineales
Métodos Iterativos
Radio Espectral
Del Corolario anterior, se infiere una relación entre la rapidez de
convergencia y el radio espectral de la matriz de iteración T .
Puede probarse que
||x (k) − x || ≈ ρ(T )k ||x (0) − x ||
Por lo tanto, conviene seleccionar el método iterativo con mínimo
ρ(T ) < 1 para un sistema particular Ax = b.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
	Sistemas de Ecuaciones Lineales