Upload
jose-duartte
View
224
Download
0
Embed Size (px)
Citation preview
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
1/57
Caṕıtulo 3
Sistemas de Ecuaciones Lineales
Sistemas de ecuaciones lineales se utilizan en muchos problemas de ingenierı́a y de las ciencias,
ası́ como en aplicaciones de las matemáticas a las ciencias sociales y al estudio cuantitativo de
problemas de administración y economı́a.
En este caṕıtulo se examinan métodos iterativos y métodos directos para resolver sistemas
de ecuaciones lineales
a11x1 + a12x2 + · · · + a1nxn = b1a21x1 + a22x2 + · · · + a2nxn = b2
...
an1x1 + an2x2 + · · · + annxn = bn .
(3.1)
Este sistema puede ser expresado en la forma matricial como
Ax = b, (3.2)
donde A = (aij)n×n ∈ M (n × n,R) , b = (b1 , b2 , . . . , bn)T ∈ Rn y x = (x1 , x2 , . . . , xn)T ∈Rn es la incógnita.
En la siguiente sección estudiaremos algunos métodos directos para resolver sistemas de
ecuaciones lineales, posteriormente abordaremos algunos métodos iterativos .
3.1 Normas matriciales
Para estudiar algunos métodos iterativos que nos permitan resolver sistemas de ecuacioneslineales, necesitamos de algunos conceptos básicos de Álgebra Lineal.
3.1.1 Normas vectoriales
Sea V un espacio vectorial de dimensión finita.
Definición 3.1 Una norma en V es una funci´ on || || : V −→ R que satisface
N1) x 0 para todo x ∈ V ,
96
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
2/57
Sergio Plaza 97
N2) ax = |a| x para todo x ∈ V y todo a ∈R ,N3) x + y x + y para todo x, y ∈ V (desigualdad triangular).
Ejemplo 44 En Rn podemos definir las siguientes normas
1. (x1, x2, . . . , xn) 2 = (n
i=1 x2i )
1/2 (norma euclideana )
2. (x1, x2, . . . , xn) ∞ = max { |xi| : 1 i n }
3. (x1, x2, . . . , xn) 1 =n
i=1|xi|
4. ||(x1, x2, . . . , xn)|| p = (n
i=1 |xi| p)1/p (norma p ).
Ejemplo 45 Denotemos por V = M (n
× n,R) el espacio vectorial real de las matrices de
orden n × n con entradas reales. Definimos las siguientes normas en V
1. ||A||2 =
traza(AAT )
2. ||A||F =n
i,j=1 a2ij
1/2=n
i=1
nj=1 a
2ij
1/2(norma de Fröbenius)
3. ||A||α,β = sup{||Ax||β : x ∈ Rn , con xα = 1} , donde || ||β y || ||β , denotannormas cualesquiera norma sobre Rn . Esta norma es llamada norma subordinada a las
norma en Rn .
Notemos que también se tiene
Aα,β = sup Axβxα : x ∈Rn, xα = 0 .La verificación que lo anterior define una norma sobre el espacio vectorial M (n × n,R)no es dif́ıcil, por ejemplo N1 es inmediata, para verificar N2, usamos la propiedad sigu-
iente del supremo de conjuntos en R , sup (λA) = λ sup(A) , para todo λ 0, donde
λA = {λx : x ∈ A} . Finalmente, para verificar N3, usamos la propiedad sup (A + B) sup(A) + sup(B) , donde A + B = { x + y : x ∈ A, y ∈ B } .
Observación.
1. Si A ∈ M (n × n,R) es no singular, esto es, det(A) = 0 , entonces
inf {||Ax|| : ||x|| = 1} = 1||A−1|| .
2. ||A||2 =√
λmax , donde λmax es el mayor valor propio de AAT .
3. Si A ∈ M (n × n,R) es no singular, entonces
||A−1||2 = 1inf {||Ax||2 : ||x||2 = 1} =
1√ λmin
,
donde λmin es el menor valor propio de AAT .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
3/57
Sergio Plaza 98
4. ||A||2 = ||AT ||2 .
5. A 00 B 2
= max{||A||2, ||B||2} .
Teorema 3.1 Para A ∈ M (n × n,R) y x ∈Rn , se tiene que Ax A x .
Demostración. Desde la definicíon de norma matricial se tiene que ||A|| ||Ax||||x|| , paratodo x ∈ Rn , con x = 0, de donde ||Ax|| ||A|| ||x|| , y como esta última desigualdad valetrivialmente para x = 0 , el resultado se sigue.
Ejemplo 46 Si en Rn elegimos la || ||∞ , entonces la norma matricial subordinada viene dadapor
||A||∞ = sup {Ax∞ : x∞ = 1}
= max
nj=1
|a1j |,n
j=1
|a2j |, . . . ,n
j=1
|aij|, . . . ,n
j=1
|anj| .
Ejemplo 47 Si en Rn elegimos la || ||1 , entonces la norma matricial subordinada viene dadapor
||A||1 = sup {Ax1 : x1 = 1}
= max
n
i=1|ai1|,
n
i=1|ai2|, . . . ,
n
i=1|aij|, . . . ,
n
i=1|ain|
.
Una de las normas más usadas en Algebra Lineal es la norma de Fr¨ obenius la cual es dada
por
||A||F = n
i=1
mj=1
a2ij
1/2 , A ∈ M (m × n,R)
y también las p –normas ( p 1 ), las cuales son dadas por
||A|| p = sup ||Ax|| p
||x|| p : x = 0
.
Teorema 3.2 Para cualquier norma matricial subordinada se tiene
1. I = 1.
2. AB A · B .
Demostración. Del teorema (3.1) para todo x ∈Rn se tiene que
||ABx|| ||A| | · | |Bx|| ||A| | · | |B||||x|| ,
de donde el resultado se sigue.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
4/57
Sergio Plaza 99
Ejemplo 48 No toda norma matricial es subordinada a alguna norma en Rn . Para verlo,
usamos la parte 2 del teorema anterior.
Definamos la norma matricial
||A||∆ = maxi,j=1,...,n
|ai,j| .
Afirmamos que esta es una norma matricial (se deja al lector la verificaci ón) y no es subor-
dinada a ninguna norma en M (n × n,R) .En efecto, tomemos las matrices
A = B =
1 1
0 1
.
Tenemos ||
A||∆ =
||B
||∆ = 1 y como
AB =
1 2
0 1
se tiene que ||AB||∆ = 2 > ||A||∆||B||∆ = 1 .
Teorema 3.3 Para las normas matriciales definidas anteriormente valen las siguientes rela-
ciones. Sea A ∈ M (n × n,R) , entonces
1. ||A||2 ||A||F √
n ||A||22.
||A
||∆
||A
||2 n
||A
||∆
3. 1√ n ||A||∞ ||A||2 √ n ||A||∞
4. 1√ n ||A||1 ||A||2 √ n ||A||1 .
Teorema 3.4 Sea A ∈ M (n × n,R) , con A < 1 , entonces I −A es una matriz que tiene inversa, la cual viene dada por (I − A)−1 =
∞k=0
Ak , donde A0 = I . Adem´ as, se tiene que (I − A)−1 11 − A .
Demostración. Es sólo cálculo y se deja a cargo del lector.
Teorema 3.5 Sean A, B ∈ M (n × n,R) tales que I − AB < 1 entonces A y B tienen inversas, las cuales son dadas por A−1 = B
∞k=0 (I − AB)k
y B−1 =
∞k=0 (I − AB)k
A ,
respectivamente,.
Demostración. Directa desde el teorema anterior.
Definición 3.2 Sea A ∈ M (n × n,R) , decimos que λ ∈ C es un valor propio de A si la matriz A − λ I no es invertible, en otras palabras, λ es soluci´ on de la ecuaci´ on polinomial
pA (λ) = det(A − λ I ) = 0,
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
5/57
Sergio Plaza 100
donde p (λ) es el polinomio caracterı́stico de A . Se define el espectro de A como el conjunto
de sus valores propios, es decir,
σ(A) = {λ ∈C : λ valor propio de A} .
Observación. El polinomio caracterı́stico de A , p(λ) , tiene grado menor o igual a n .
Definición 3.3 Sea A ∈ M (n × n,R) , definimos el radio espectral de A por
ρ (A) = max { |λ| : λ ∈ σ(A)} .
Observación. Geométricamente ρ (A) es el menor radio tal que el ćırculo centrado en el origen
en el plano complejo con radio ρ(A) contiene todos los valores propios de A .
Observación. Si λ = a + ib ∈C , su valor absoluto o norma es dado por | λ | = √ a2 + b2 .
Teorema 3.6 Se tiene ρ (A) = inf A , donde el ı́nfimo es tomado sobre todas las normas matriciales definidas sobre el espacio vectorial M (n × n,R) .
Observación. Desde la definición de las norma matriciales || ||∞ y || ||1 vemos que calcularlaspara una matriz dada es fácil. Para lo norma || ||2 el cálculo no es tan sencillo, pero tenemosel siguiente resultado.
Teorema 3.7 Sea A ∈ M (n × n,R) . Entonces
||A||2 = max |λ| : λ ∈ σ(AT A)
1/2,
en otras palabras, ||A||2 es la ráız cuadrada del mayor valor propio de la matriz AT A .
Corolario 3.1 Si A ∈ M (n × n,R) es simétrica, entonces
||A||2 = max{|λ| : λ ∈ σ(A)} .
3.2 Número de condición
Consideremos el sistema Ax = b , donde A es una matriz invertible, por lo tanto tenemos que
xT = A−1b es la solución exacta.
Caso 1: Se perturba A−1 para obtener una nueva matriz B , la solución x = A−1b resultaperturbada y se obtiene un vector xA = Bb que deberı́a ser una solución aproximada al sistema
original. Una pregunta natural ¿es que ocurre con E (xA) = xT − xA ? Tenemos
xT − xA = xT − Bb = xT − BAxT = (I − BA) xT I − BA xT
de donde obtenemos que
E (xA) = xT − xA I − BA xT
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
6/57
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
7/57
Sergio Plaza 102
A−1 = ε−2
1 −1 − ε
−1 + ε 1
,
obtenemos que A∞ = 2 + ε,A−1∞ = ε−2 (2 + ε) , por lo tanto
κ (A) = (2 + ε)2
ε2
4
ε.
Observe que si ε < 0.0001, entonces k (A) 40.000.
Ejemplo 50 Consideremos la matriz
A =
1 1
1 1.00000001
Tenemos
A−1 =
1.0 × 108 −1.0 × 108−1.0 × 108 1.0 × 108
Luego, ||A||1 = ||A||2 ≈ ||A||∞ = 2 , ||A−1||1 = ||A−1||∞ ≈ ||A−1||2 ≈ 2 × 108 , luegoκ1(A) = κ∞(A) ≈ 4 × 108 .
Observación. Si κ (A) es demasiado grande diremos que A está mal condicionada .
Ejemplo 51 Consideremos la matriz
A =
1 −1 −1 · · · −10 1 −1 · · · −1...
......
. . . ...
0 0 0 · · · −10 0 0 · · · 1
.
La matriz A tiene sólo unos en su diagonal, y sobre ella tiene sólo menos unos. Tenemos que
det(A) = 1, pero κ∞(A) = n2n−1 , esta matriz está mal condicionada.
Si resolvemos Ax = b numéricamente no obtenemos una solución exacta, xT , si no una
solución aproximada xA . Una pregunta natural al resolver numéricamente el sistema es ¿quétan cerca esta AxA de b ?
Para responder dicha interrogante definamos r = b − AxA como el vector residual y e =xT − xA como el vector de error .
Observación. Tenemos que
1. Ae = r.
2. xA es solución exacta de AxA = bA = b − r .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
8/57
Sergio Plaza 103
¿Qué relación existe entre xT −xAxT y b−bA
b = rb ?
Teorema 3.8 Para toda matriz invertible A ∈
M (n×
n,R) , se tiene que
1
κ (A)
b − bA b
xT − xA xT κ (A)
b − bA b , (3.6)
es decir,1
κ (A)
r b
e xT κ (A)
r b . (3.7)
Observación. Si tenemos una matriz B escrita en la forma
B = A(I + E )
donde I denota la matriz identidad y E es una matriz de error, entonces se tienen las siguientescotas para el error relativo
||xT − xA||||xT ||
κ(A)
1 − κ(A) ||AE ||||A||AE ||||A|| (3.8)
si ||AE || < 1 y||xT − xA||
||xT || ||E ||
1 − ||E || (3.9)
si ||E || < 1 .Observación. Sea A ∈ M (n × n,R) . Denotemos por λmax y λmin , respectivamente, elmáximo y el mı́nimo de los valores propios de AAT . Entonces κ2(A) = λmaxλmin .Ejemplo 52 Determine ||A||2 , ||A−1||2 y κ2(A) , donde
A =
3√ 3
− 1√ 3
0
√ 8√ 3
Tenemos que
AT = 3√
30
− 1√ 3
√ 8√ 3
Luego
AAT − λI =
10
3 − λ −
√ 8
3
−√
8
3
8
3 − λ
.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
9/57
Sergio Plaza 104
Por lo tanto, det(AAT − λI) = λ2 − 6λ + 8 , de donde los valores propios de AAT son λ = 2y λ = 4 , es decir, λmin = 2 y λmax = 4. Luego
||A||2 =
λmax = 2 y ||A−1||2 = 1√ λmin
= 1√
2,
y se tiene que κ2(A) = 2√ 2
=√
2 .
3.3 Solucíon de sistemas de ecuaciones lineales: métodos
directos
En esta parte estudiaremos métodos directos, es decir, algebraicos, para resolver sistemas de
ecuaciones lineales. Herramienta fundamental aqúı es el Álgebra Lineal.
3.3.1 Conceptos básicos
La idea es reducir un sistema de ecuaciones lineales a otro que sea m ás sencillo de resolver.
Definición 3.5 Sean A, B ∈ M (n × n,R) . Decimos que dos sistemas de ecuaciones lineales Ax = b y Bx = d son equivalentes si poseen exactamente las mismas soluciones.
Por lo tanto si podemos reducir un sistema de ecuaciones lineales Ax = b a un sistema
equivalente y más simple Bx = d , podemos resolver este último, y obtenemos de ese modo las
soluciones del sistema original.
Definición 3.6 Sea A ∈ M (n × n,R) . Llamaremos operaciones elementales por filas sobre Aa cada una de las siguientes operaciones
1. Intercambio de la fila i con la fila j , denotamos esta operaci´ on por F i ↔ F j .2. Reemplazar la fila i, F i , por un m´ ultiplo no nulo λF i de la fila i , denotamos esta
operaci´ on por F i → λF i3. Reemplazar la fila i , F i , por la suma de la fila i m´ as un m´ ultiplo no nulo λF j de la fila
j , i = j , denotamos esta operaci´ on por F i → F i + λF j
Definición 3.7 Decimos que una matriz A es una matriz elemental si ella se obtiene a partir de la matriz identidad a trav́es de una ´ unica operaci´ on elemental. Una matriz elemental ser´ a
denotada por E .
Ejemplo 53 1.
1 0 00 1 0
0 0 1
F 3 ↔ F 2
1 0 00 0 1
0 1 0
.
2.
1 0 00 1 0
0 0 1
F 2 → rF 2
1 0 00 r 0
0 0 1
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
10/57
Sergio Plaza 105
3.
1 0 0
0 1 0
0 0 1
F 3 → F 3 + rF 2
1 0 0
0 1 0
0 r 1
Observación. Si a una matriz A se le aplican una serie de operaciones elementales
E 1, E 2, . . . , E k denotaremos el resultado por E kE k−1 · · · E 2E 1A .Además, si E kE k−1 · · · E 2E 1A = I , se tiene que A posee inversa y E kE k−1 · · · E 2E 1 = A−1 .El teorema siguiente resume las condiciones para que una matriz tenga inversa.
Teorema 3.9 Sea A ∈ M (n × n,R) entonces son equivalentes
1. A tiene inversa.
2. det(A)
= 0.
3. Las filas de A forman una base de Rn .
4. Las columnas de A forman una base de Rn .
5. La transformaci´ on lineal T : Rn −→ Rn dada por T (x) = Ax , asociada a la matriz A ,es inyectiva,
6. La transformaci´ on T : Rn −→ Rn dada por T (x) = Ax , asociada a la matriz A , es sobreyectiva
7. El sistema Ax = 0 , donde x ∈Rn posee soluci´ on ´ unica x = 0 .8. Para cada b
∈Rn existe un ´ unico vector x
∈Rn tal que Ax = b .
9. A es producto de matrices elementales.
10. Todos los valores propios de A son distinto de cero.
3.4 Factorización de matrices
En esta sección estudiaremos las condiciones necesarias para que una matriz A ∈ M (n × n,R)tenga una factorización de la forma LU donde L, U ∈ M (n×n,R) , con L una matriz triangularinferior y U una matriz triangular superior.
Observe que si A
∈ M (n
×n,R) tiene una factorización de la forma LU como arriba, entonces
el sistema de ecuaciones lineales Ax = b , con x, b ∈Rn , puede resolverse de una manera mássencilla, para ello consideramos el cambio de variable U x = z , y resolvemos primero el sistema
Lz = b primero y enseguida resolvemos el sistema U x = z , obteniendo aśı la solución del
sistema original, es decir,
Ax = b ⇐⇒ L U x z
= b ⇐⇒
Lz = b
U x = z .
Supongamos que A ∈ M (n × n,R) tiene una descomposición de la forma LU como arriba,con
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
11/57
Sergio Plaza 106
L =
l11 0 0 · · · 0l21 l22 0 · · · 0
......
... . . .
...
ln1 ln2 · · · lnn−1 lnn
y U = u11 u12 · · · u1n−1 u1n
0 u22 · · · u2n−1 u2n...
......
. . . ...
0 0 0 · · · unn
(3.10)
De esta descomposición tenemos
det(A) = det(L) det(U ) =
ni=1
lii
ni=1
uii
(3.11)
ası́, det(A) = 0 si y sólo si lii = 0 y uii = 0 para todo i = 1, . . . , n .Para simplificar la notación, escribamos
L = (F 1 F 2 . . . F n)T
y U = (C 1C 2 · · · C n) ,
donde F i = (li1 li2 · · · lii 0 · · · 0) y C i = (u1i u2i · · · uii 0 · · · 0)T , son las filas de L ylas columnas de U , respectivamente.
Ahora, al desarrollar la multiplicación A = LU ,
a11 a21 · · · a1na21 a22 · · · a2n
......
. . . ...
an1 an2 · · · ann
=
F 1F 2
...
F n
(C 1C 2 · · · C n) =
F 1C 1 F 1C 2 · · · F 1C nF 2C 1 F 2C 2 · · · F 2C n
......
. . . ...
F nC 1 F nC 2 · · · F nC n
donde F iC j es considerado como el producto de las matrices F i = (li1 li2 · · · lii 0 · · · 0) yC i = (u1i u2i · · · uii 0 · · · 0)T . Tenemos entonces
a11 = F 1C 1 = l11u11a12 = F 1C 2 = l11u12
......
...
a1n = F 1C n = l11u1n
(3.12)
de aqúı, vemos que si fijamos l11 = 0 , podemos resolver las ecuaciones anteriores para u1i ,i = 1, . . . , n . Enseguida, para la segunda fila de A tenemos
a21 = F 2C 1 = l21u11a22 = F 2C 2 = l21u12 + l22u22
......
...
a2n = F 2C n = l21u1n + l22u2n
(3.13)
como u11 ya lo conocemos desde las ecuaciones (3.12), podemos encontrar el valor l21 , conocido
este valor, fijando un valor no cero para l22 , y dado que conocemos los valores u1i para
i = 2, . . . , n , podemos encontrar los valores de u2i para i = 2, . . . , n . Siguiendo este método
vemos que es posible obtener la descomposición de A en la forma LU . Note que tambíen
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
12/57
Sergio Plaza 107
podemos comparar las columnas de A con aquellas obtenidas desde el producto LU y proceder
a resolver las ecuaciones resultantes. El problema es ahora saber bajo que condiciones dada
una matriz A ella puede descomponerse en la forma LU , es decir, siempre y cuando podamos
hacer las elecciones anteriores.
Ejemplo 54 Sea A =
10 −3 61 8 −2
−2 4 −9
. Encontremos una descomposición LU para A .
Escribamos 10 −3 61 8 −2
−2 4 −9
=
l11 0 0l21 l22 0
l31 l32 l33
u11 u12 u130 u22 u23
0 0 u33
desarrollando, obtenemos que
l11u11 = 10
l11u12 = −3l11u13 = 6
de aqúı fijando un valor no cero para l11 , digamos l11 = 2 , obtenemos que u11 = 5 , u12 = −32 ,y u13 = 3 . Enseguida tenemos las ecuaciones
l21u11 = 1
l21u12 + l22u22 = 8
l21u13 + l22u23 = −2
como u11 = 5 se tiene que l21 = 15 . Ahora fijamos el valor de l22 = 1 y obtenemos los valores
u22 = 8310 , y u23 = −135 . Finalmente, para la última fila de A , nos queda
l31u11 = −2l31u12 + l32u22 = 4
l31u13 + l32u23 + l33u33 = −2
como u11 = 5 de la primera ecuacíon l31 = − 25 , reemplazando los valores de l31 = −25 ,u12 = −32 y u22 = 8310 en la segunda ecuación encontramos que l32 = 3483 . Ahora, reemplazandolos valores ya obtenidos en la tercera ecuación obtenemos que l33u33 = − 1694415 , para encontrar elvalor de u33 podemos fijar el valor de l33 , digamos l33 = − 1415 , y obtenemos que u33 = 1604 .Tenenmos aśı una descomposición LU para la matriz A , es decir,
10 −3 61 8 −2
−2 4 −9
=
2 0 0
1
5 1 0
−35
34
83 − 1
415
5 −32
3
0 83
10 −13
5
0 0 1604
.
No siempre es posible encontrar una descomposición de la forma LU para una matriz A
dada, esto se muestra en el siguiente ejemplo.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
13/57
Sergio Plaza 108
Ejemplo 55 La matriz A =
0 1
1 1
no tiene descomposición de la forma LU . Notemos
que det(A)
= 0 .
Para verlo supongamos que podemos escribir A = LU , donde
L =
l11 0
l21 l22
y U =
u11 u12
0 u22
.
Tenemos entonces que
0 1
1 1
=
l11 0
l21 l22
u11 u12
0 u22
de donde l11u11 = 0 , por lo tanto
l11 = 0 (∗) o u11 = 0 (∗∗).
Como l11u12 = 1 , no es posible que (*) sea verdadero, es decir, debemos tener que l11 = 0 ,en consecuencia se debe tener que u11 = 0 , pero además se tiene que u12 = 0 . Ahoram, comol21u11 = 1 , llegamos a una contradiccíon. Luego tal descomposición para A no puede existir.
En el algoritmo que vimos para buscar la descomposición de una matriz A en la forma LU ,
en los sucesivos paso fue necesario fijar valores no cero para los coeficientes lii de L , de modo apoder resolver las ecuaciones resultantes. También, si procedemos con el algoritmo a comparar
las columnas de la matriz producto LU con las columnas de A , vemos que será necesario fijar
en paso sucesivos valores no cero para los coeficientes uii de U , de modo a poder resolver las
ecuaciones resultantes. Como es evidente existe una manera simple de hacer esto, por ejemplo
si en el primer algoritmo fijamos los valores lii = 1 para i = 1, . . . , n , decimos que tenemos una
descomposici´ on LU de Doolitle para A , y si en el segundo algoritmo fijamos los valores uii = 1
para i = 1, . . . , n , decimos que tenemos una descomposici´ on LU de Crout para A , finalmente
si fijamos U = LT (transpuesta de L) se tiene que lii = uii , y decimos que tenemos una
descomposici´ on LU de Cholesky para A . Note que para la existencia de descomposición de
Cholesky es necesario que A sea simétrica, pues si A = LLT entonces AT = A , esto significa
que es una condición necesario, pero una no es una condición suficiente.
Sobre la existencia de descomposición LU para una matriz A veremos a continuación algunos
teoremas. Primero recordemos que si
A =
a11 a21 · · · a1na21 a22 · · · a2n
......
. . . ...
an1 an2 · · · ann
n×n
entonces los menores principales de A son las submatrices Ak , k = 1, . . . , n , definidas por
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
14/57
Sergio Plaza 109
A1 = (a11)1×1 , A2 = a11 a21
a21 a22
2×2
, . . . , Ak =
a11 a21 · · · a1ka21 a22 · · · a2k
......
. . . ...
ak1 ak2 · · · akk
k×k
,
. . . , An = A .
Teorema 3.10 Si los n menores principales de una matriz A tienen determinante distinto
de cero, entonces A tiene una descomposici´ on LU .
Para tener descomposición de Cholesky, recordemos algunos conceptos y resultados.
Definición 3.8 Sea A ∈
M (n ×
n,R) . Decimos que A es definida positiva si
Ax, x
> 0
para todo x ∈Rn , con x = 0 .
Ejemplo 56 La matriz
A =
2 −1 0−1 2 −1
0 −1 2
es definida positiva. En efecto considere x = (x y z)T , tenemos
x, Ax = (x, y, z)2 −1 0
−1 2 −10 −1 2
xyz = 2x2 − 2xy + 2y2 − 2yz + 2z2.
Luego,
x, Ax = 2x2 − 2xy + 2y2 − 2yz + 2z2= x2 + (x − y)2 + (y − z)2 + z2 > 0,
para todo (x, y, z) = (0, 0, 0) .
Teorema 3.11 Si A ∈ M (n × n,R) es definida positiva entonces todos sus valores propios son reales y positivos.
Observación. Si A ∈ M (n × n, R) entonces podemos descomponer A de manera únicacomo la suma de una matriz simétrica, A0 =
12
A + AT
, y una matriz antisimétrica, A1 =
12
A − AT . Desde la definicíon de matriz positiva definida se tiene que Ax, x = A0x, x ,
por lo cual sólo necesitamos considerar matrices simétricas.
Teorema 3.12 Sea A ∈ M (n × n,R) , entonces A es positiva definida si y s´ olo si todos los menores principales de A tiene determinante positivo.
Teorema 3.13 Sea A ∈ M (n × n,R) , entonces A simétrica y positiva definida si y s´ olo si A tiene una descomposici´ on de Cholesky.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
15/57
Sergio Plaza 110
Ejemplo 57 La matriz
A = 2 −1 0−1 2 −1
0 −1 2
es definida positiva, pues se tiene que det (A1) = 2 > 0, det (A2) = det
2 −1−1 2
= 3 > 0
y det(A3) = det(A) = 4 > 0 . Luego tiene descomposición de Cholesky.
Ahora, para encontrar la descomposición de Cholesky para esta matriz procedemos como
sigue.
2 −1 0
−1 2
−1
0 −1 2 = l11 0 0
l21 l22 0
l31 l32 l33
l11 l21 l310 l22 l320 0 l33
Luego, l211 = 2 , es decir, l11 =
√ 2 ; −1 = l11l21 , de donde l21 = −
√ 22 ; 0 = l11l31 , de
donde l31 = 0 ; l221 + l222 = 2 , de donde l22 =
√ 5√ 2
; l21l31 + l22l32 = −1 , de donde l32 = −√ 2√ 5
;
l231 + l232 + l
233 = 2 , de donde l33 =
2√ 2√ 5
.
Por lo tanto
2 −1 0
−1 2 −10
−1 2
=
√ 2 0 0
−√ 22
√ 5√ 2
0
0
−
√ 2√ 5
2√ 2√ 5
√ 2 −
√ 22 0
0√ 5√ 2
−√ 2√ 5
0 0 2√ 2√ 5
.
3.5 Método de eliminación gaussiana
En esta sección estudiaremos el método de eliminación gaussiana para resolver sistemas de
ecuaciones lineales
a11 a21 · · · a1na21 a22 · · · a2n
......
. . . ...
an1 an2 · · ·
ann
x1x2...
xn
=
b1b2...
bn
.
Colocamos primero esta información en la forma
A b
=
a11 a12 · · · a1n b1a21 a22 · · · a2n b2
......
. . . ...
...
an1 an2 · · · ann bn
F 1F 2
...
F n
esto es, consideramos la matriz aumentada del sistema. En la notación anterior, los śımbolos
F i denotan las filas de la nueva matriz.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
16/57
Sergio Plaza 111
Si a11 = 0 , el primer paso de la eliminación gaussiana consiste en realizar las operacioneselementales
(F j − mj1F 1) → F j , donde mj1 = aj1a11
, j = 2, 3, . . . ,n. (3.14)
Estas operaciones transforman el sistema en otro en el cual todos los componentes de la
primera columna situada bajo la diagonal son cero.
Podemos ver desde otro punto de vista el sistema de operaciones. Esto lo logramos si-
multáneamente al multiplicar por la izquierda la matriz original A por la matriz
M (1) =
1 0 · · · 0
−m21 1 · · · 0...
... . . .
...
−mn1 0 · · · 1
(3.15)
Esta matriz recibe el nombre de primera matriz gaussiana de transformaci ón. El producto
de M (1) con la matriz A(1) = A lo denotamos por A(2) y el producto de M (1) con la matriz
b(1) = b lo denotamos por b(2) , con lo cual obtenemos
A(2)x = M (1)Ax = M (1)b = b(2) (3.16)
De manera análoga podemos construir la matriz M (2) , en la cual si a(2)22 = 0 los elemen-
tos situados bajo de la diagonal en la segunda columna con los elementos negativos de los
multiplicadores
mj2 =a(2)j2
a(2)22
, j = 3, 4, . . . , n (3.17)
Ası́ obtenemos
A(3)x = M (2)A(2)x = M (2)M (1)Ax = M (2)M (1)b = b(3) (3.18)
En general, con A(k)x = b(k) ya formada, multiplicamos por la k–ésima matriz de transfor-
mación gaussiana
M (k) =
1 0 · · · · · · 00 1
. . . 1 . . .
...
0... −mk+1 k . . .
......
... 0 0
0 · · · 0 −mn k 0 0 1
para obtener
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
17/57
Sergio Plaza 112
A(k+1)x = M (k)A(k)x = M (k)
· · ·M (1)Ax = M (k)b(k) = b(k+1) = M (k)
· · · M (1)b (3.19)
Este proceso termina con la formación de un sistema A(n)x = b(n) , donde A(n) es una matriz
triangular superior
A(n) =
a(1)11 a
(1)12 · · · a(1)1n
0 a(2)22 . . . a
(2)2n
......
. . .
. . .
...
a(n−1)n−1 n
0 · · · 0 a(n)nn
dada por
A(n) = M (n−1)M (n−2)M (n−3) · · · M (1)A. (3.20)
El proceso que hemos realizado sólo forma la mitad de la factorización matricial A = LU ,
donde con U denotamos la matriz triangular superior A(n) . Si queremos determinar la matriz
triangular inferior L , primero debemos recordar la multiplicación de A(k)x = b(k) mediante la
transformación gaussiana M (k) con que obtuvimos
A(k+1)x = M (k)A(k)x = M (k)b(k) = b(k+1)
para poder revertir los efectos de esta transformación debemos considerar primero la matriz
L(k) = M (k)−1 , la cual esta dada por
L(k) =
M (k)−1
=
1 0 · · · · · · · · · 00 1
...... 1
...... 0
. . . ...
... mk+1 k. . .
......
... 0 . . . 0
0 · · · 0 mn k 0 0 1
.
Por lo tanto si denotamos
L = L(1)L(2) · · · L(n−1)
obtenemos
LU = L(1)L(2) · · · L(n−1)M (n−1)M (n−2)M (n−3) · · · M (1) = A.
Con lo cual obtenemos el siguiente resultado.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
18/57
Sergio Plaza 113
Teorema 3.14 Si podemos efectuar la eliminaci´ on gaussiana en el sistema lineal Ax = b sin
intercambio de filas, entonces podemos factorizar la matriz A como el producto de una matriz
triangular inferior L y una matriz triangular superior U , donde
U =
a(1)11 a
(1)12 · · · a(1)1n
0 a(2)22
. . . ...
......
. . . a(n−1)n−1 n
0 · · · 0 a(n)nn
y L =
1 0 · · · 0m21 1
......
......
. . . 0
mn1 · · · mn n−1 1
.
Ejemplo 58 Consideremos el siguiente sistema lineal
x + y + 3w = 4
2x + y − z + w = 13x − y − z + w = −3−x + 2y + 3z − w = 4
Si realizamos las siguientes operaciones elementales F 2 → (F E 2 − 2F 1) , F 3 → (F 3 − 3F 1) ,F 4 → (F 4 − (−1) F 1) , F 3 → (F 3 − 4F 2) , F 4 → (F 4 − (−3) F 2) con lo que obtenemos el sis-tema triangular
x + y + 3w = 4
−y − z − 5w = −73z + 13w = 13
−13w = −13Por lo tanto la factorización LU está dada por
A =
1 1 0 3
2 1 −1 13 −1 −1 2
−1 2 3 −1
=
1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1
L
1 1 0 3
0 −1 −1 −50 0 3 13
0 0 0 −13
U
= LU.
Esta factorización nos permite resolver fácilmente todo sistema que posee como matriz aso-
ciada la matriz A . Aśı, por ejemplo, para resolver el sistema
Ax = LU x =
1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1
1 1 0 3
0 −1 −1 −50 0 3 13
0 0 0 −13
x
y
z
w
=
8
7
14
−7
primero realizaremos la sustitución y = U x . Luego resolvemos Ly = b , es decir,
LU x = Ly =
1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1
y1y2y3y4
=
8
7
14
−7
.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
19/57
Sergio Plaza 114
Este sistema se resuelve para y mediante un simple proceso de susbtitución hacia adelante,
con lo cual obtenemos
y =
y1y2y3y4
=
8
−926
−26
.
Por ultimo resolvemos U x = y , es decir, resolvemos el sistema por un proceso de susbtituci ón
hacia atrás
U x =
1 1 0 3
0 −1 −1 −50 0 3 13
0 0 0 −13
x
y
z
w
=
8
−926
−26
el cual tiene por solución
x =
x
y
z
w
=
3
−10
2
.
que es la solución buscada.
3.6 Eliminación gaussiana con pivoteo
Al resolver un sistema lineal Ax = b , a veces es necesario intercambiar las ecuaciones, ya sea
porque la elimninación gaussiana no puede efectuarse o porque las soluciones que se obtienen
no corresponden a as soluciones exactas del sistema. Este proceso es llamado pivoteo y nos
lleva a la descomposición P A = LU del sistema. Aśı el sistema se transforma en LU x = P b
y resolvemos entonces los sistemas
U x = z
Lz = P b
donde P es una matriz de permutaci´ on , es decir, es una matriz obtenida a partir de la matriz
identidad intercambiando algunas de sus filas. Más precisamente.
Definición 3.9 Una matriz de permutaci´ on P ∈ M (n × n,R) es una matriz obtenida desde la matriz identidad por permutaci´ on de sus filas.
Observación. Las matrices de permutación poseen dos propiedades de gran utilidad que se
relacionan con la eliminación gaussiana. La primera de ellas es que al multiplicar por la izquierda
una A por una matriz de permutación P , es decir, al realizar el producto P A se permutan las
filas de A . La segunda propiedad establece que si P es una matriz de permutación, entonces
P −1 = P T .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
20/57
Sergio Plaza 115
Si A ∈ M (n × n,R) es una matriz invertible entonces podemos resolver el sistema linealAx = b vı́a eliminación gaussiana, sin excluir el intercambio de filas. Si conociéramos los inter-
cambios que se requieren para resolver el sistema mediante eliminación gaussiana, podŕıamos
arreglar las ecuaciones originales de manera que nos garantice que no se requieren intercambios
de filas. Por lo tanto, existe un arreglo de ecuaciones en el sistema que nos permite resolver el
sistema con eliminación gaussiana sin intercambio de filas. Con lo que podemos concluir que
si A ∈ M (n × n,R) es una matriz invertible entonces existe una matriz de permutación P para la cual podemos resolver el sistema P Ax = P b , sin hacer intercambios de filas. Pero
podemos factorizar la matriz P A en P A = LU , donde L es una triangular inferior y U
triangular superior, y P es una matriz de permutación. Dado que P −1 = P T obtenemos queA =
P T L
U . Sin embargo, la matriz P T L no es triangular inferior, salvo que P = I .
Supongamos que tenemos el sistema
a11 a12
· · · a1n
a21 a22 · · · a2n...
... . . .
...
an1 an2 · · · ann
x1x2...
xn
=
b1b2...
bn
(3.21)
Se define la escala de cada fila como
si = max{|ai1|, |ai2|, . . . , |ain|} , 1 i n . (3.22)
Elección de la fila pivote. Elegimos como fila povote la fila para la cual se tiene que
|ai01|si0
(3.23)
es el mayor.
Intercambiamos en A la fila 1 con la fila i0 , esto es, realizamos la operacíon elemental
F 1 ↔ F i0 . Esto nos produce la primera permutación. Procedemos ahora a producir cerosbajo la primera columna de la matriz permutada, tal como se hizo en la eliminaci ón gaussiana.
Denotamos el ı́ndice que hemos elegido por p1 , este se convierte en la primera componente de
la permutación.
Más especificamente, comenzamos por fijar
p = ( p1 p2 . . . pn) = (1 2 . . . n) (3.24)
como la permutación antes de comenzar el pivoteo. Aśı la primera permutacíon que hemos
hecho es
1 2 . . . i0 . . . n
i0 2 . . . 1 . . . n
.
Para fijar las ideas, comenzamos con la permutación ( p1 p2 . . . pn) = (1 2 . . . n) . Primero
seleccionamos un ı́ndice j para el cual se tiene
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
21/57
Sergio Plaza 116
|a pjj |s pj
, 2 j n (3.25)
es el mayor, y se intercambia p1 con pj en la permutación p . Procedemos a la elmincación
gaussiana, restando
a pi1a p11
× F p1
a las filas pi , 2 i n .
En general, supongamos que tenemos que producir ceros en la columna k . Impeccionamos
los números
|a pik|s pi
, k i n (3.26)
y buscamos el mayor de ellos. Si j es el ı́ndice del primer cuociente más grande, intercambiamos
pk con pj en la permutación p y las filas F pk con la fila F pj en la matriz que tenemos en
esta etapa de la eliminación gaussiana–pivoteo. Enseguida producimos ceros en la columna pkbajo el elemento a pkk , para ellos restamos
a pika pkk
× F pk
de la fila F pi , k + 1 i n , y continuamos el proceso hasta obtener una matriz triangular
superior.
Veamos con un ejemplo especı́fico como podemos ir guardando toda la información del proceso
que vamos realizando en cada etapa del proceso de eliminacíon gaussiana–pivoteo
Ejemplo 59 Resolver el sistema de ecuaciones lineales
2 3 −61 −6 8
3 −2 1
xy
z
=
11
1
Solución. Primero calculemos la escala de las filas. Tenemos
s1 = max{|2|, |3|, | − 6|} = 6s2 = max{|1|, | − 6|, |8|} = 8s3 = max{|3|, | − 2|, |1|} = 3
permutación inicial p = (1 2 3) . Denotemos por s el vector de la escala de las filas, es decir,
s = (6 8 3) .
Elección de la primera fila pivote:
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
22/57
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
23/57
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
24/57
Sergio Plaza 119
Ahora es fácil verificar que P A = LU .
Ejemplo 60 Consideremos la matriz
A =
0 0 −1 11 1 −1 21 1 0 3
1 2 −1 3
puesto que a11 = 0 la matriz no posee una factorización LU . Pero si realizamos el intercambio
de filas F 1 ↔ F 2 , seguido de F 3 → (F 3 − F 1) y de F 4 → (F 4 − F 1) obtenemos
1 1 −1 20 0 −1 10 0 1 10 1 0 1
.
Realizando las operaciones elementales F 2 ↔ F 4 y F 4 → (F 4 + F 3) , obtenemos
U =
1 1 −1 20 1 0 1
0 0 1 1
0 0 0 2
.
La matriz de permutación asociada al cambio de filas F 1 ↔ F 2 seguida del intercambio defilas F 2
↔ F 4 es
P =
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
.
La eliminación gaussiana en P A se puede realizar sin intercambio de filas usando las opera-
ciones F 2 → (F 2 − F 1) , F 3 → (F 3 − F 1) y (F 4 + F 3) → F 4 , esto produce la factorización LU de P A
P A = 1 1 −1 21 2 −1 31 1 0 3
0 0 −1 2
= 1 0 0 0
1 1 0 01 0 1 0
0 0 −1 1
1 1 −1 20 1 0 10 0 1 1
0 0 0 2
= LU.
Al multiplicar por P −1 = P T obtenemos la factorización
A =
P T L
U =
0 0 −1 11 0 0 0
1 0 1 0
1 1 0 0
1 1 −1 20 1 0 1
0 0 1 1
0 0 0 2
.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
25/57
Sergio Plaza 120
3.7 Matrices especiales
En esta sección nos ocuparemos de clases de matrices en las cuales podemos realizar la elimi-
nación gaussiana sin intercambio de filas.
Decimos que una matriz A ∈ M (n × n,R) es diagonal dominante si
|aii| >n
j = 1
j = i
|aij |
para todo i = 1, 2, . . . , n .
Ejemplo 61 Consideremos las matrices
A = 7 2 03 5 −1
0 5 −6
y B = 6 4 −34 −2 0−3 0 1
.La matriz A es diagonal dominante y la matriz B no es diagonal dominante, pues por
ejemplo |6| 0, para todo i = 1, 2, . . . , n .
3. max1 k, j n |akj | max1 i n |aii| .
4. (aij )2 < aii ajj , para todo i = j
Teorema 3.17 Una matriz simétrica A es definida positiva si y s´ olo si la eliminaci´ on gaus-
siana sin intercambio de filas puede efectuarse en el sistema Ax = b con todos los elementos
pivotes positivos. Adem´ as, en este caso los c´ alculos son estables respecto al crecimiento de los errores de redondeo.
Corolario 3.2 Una matriz simétrica A es definida positiva si y s´ olo si A puede factorizarse
en la forma LDLT , donde L es una matriz triangular inferior con unos en su diagonal y D
es una matriz diagonal con elementos positivos a lo largo de la diagonal.
Corolario 3.3 Una matriz simétrica A es definida positiva si y s´ olo si A puede factorizarse
de la forma LLT , donde L es una matriz triangular inferior con elementos distintos de cero
en su diagonal.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
26/57
Sergio Plaza 121
Corolario 3.4 Sea A ∈ M (n × n,R) una matriz simétrica a la cual puede aplicarse la elim-inaci´ on gaussiana sin intercambio de filas. Entonces, A puede factorizarse en LDLT , donde
L es una matriz triangular inferior con unos en su diagonal y donde D es una matriz diagonal
con a(1)11 , . . . , a(n)nn en su diagonal.
Ejemplo 62 La matriz
A =
4 −1 1−1 4.25 2.75
1 2.75 3.5
es definida positiva. La factorización LDLT de la matriz A es
A =
1 0 0
−0.25 1 00.25 0.75 1
4 0 0
0 4 0
0 0 1
1 −0.25 0.250 1 0.75
0 0 1
mientras que su descomposición de Cholesky es
A =
2 0 0−0.5 2 0
0.5 1.5 1
2 −0.5 0.50 2 1.5
0 0 1
.
Definición 3.10 Una matriz A ∈ M (n × n,R) es llamada matriz banda si existen enteros p y q con 1 < p, q < n , tales que aij = 0 siempre que i + p j o j + q i . El ancho de la
banda de este tipo de matrices esta dado por w = p + q − 1 .
Ejemplo 63 La matriz A = 1 2 02 1 2
0 1 1
es una matriz de banda con p = q = 2 y conancho de banda 3.
Definición 3.11 Una matriz A ∈ M (n × n,R) se denomina tridiagonal si es una matriz de banda con p = q = 2 .
Observación. Los algoritmos de factorización pueden simplificarse considerablemente en el
caso de las matrices de banda.
Para ilustrar lo anterior, supongamos que podemos factorizar una matriz tridiagonal A en
las matrices triangulares L y U . Ya que A tiene sólo 3n−2 elementos distintos de cero, habráapenas 3n − 2 condiciones aplicables para determinar los elementos de L y U , naturalmentea condición de que tambíen se obtengan los elementos cero de A . Supongamos que podemos
encontrar las matrices de la forma
L =
l11 0 · · · · · · 0l21 l22
. . . ...
...
0 . . .
. . . . . .
......
... . . .
. . . 0
0 · · · 0 ln n−1 lnn
y U =
1 u12 0 · · · 00 1
. . . ...
......
. . . . . .
. . . 0...
... . . .
. . . un−1 n0 · · · · · · 0 1
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
27/57
Sergio Plaza 122
De la multiplicación que incluye A = LU , obtenemos
a11 = l11;ai i−1 = li i−1 para cada i = 2, 3, . . . , n;aii = li i−1ui−1 i + lii para cada i = 2, 3, . . . , n;ai i+1 = liiui i+1 para cada i = 1, 2, 3, . . . , n − 1;
3.8 Solucíon de sistemas de ecuaciones lineales: métodos
iterativos
En general, puede resultar muy engorroso encontrar la solución exacta a un sistema de ecua-
ciones lineales, y por otra parte, a veces nos basta con tener buenas aproximaciones a dicha
solución. Para obtener estas últimas usamos métodos iterativos de punto fijo, que en este caso
particular resultan ser más analizar su convergencia.
Teorema 3.18 Consideremos un método iterativo
x(k+1) = Gx(k) + c (3.27)
donde G ∈ M (n×n,R) , x, c ∈Rn . Entonces el método iterativo es convergente, para cualquier condici´ on inicial x(0) elegida arbitrariamente si y s´ olo si ρ(G) < 1 . Adem´ as, si existe una
norma | || en M (n × n, R) , en la cual se tiene ||G|| < 1 , entonces el método iterativoconverge cualesquiera que sea la condici´ on inicial x(0) ∈ Rn dada. Si tomamos x(k) como una aproximaci´ on al punto fijo xT del método iterativo (3.27), entonces valen las desigualdades
siguientes, x(k) − x ρ(G)k1 − ρ(G)
x(1) − x(0) . (3.28)y x(k) − x λk
1 − λx(1) − x(0) , (3.29)
donde λ = ||G|| .
Observación. Si el método iterativo x(k+1) = Gx(k) + c es convergente y tiene por ĺımite a
x ∈ Rn , entonces
x = limk→∞x(k+1) = G limk→∞x(k) + c = Gx + c,
de donde x = (I − G)−1c .
Regresemos al problema inicial de resolver el sistema de ecuaciones lineales
Ax = b,
donde A = (aij ) ∈ M (n × n,R) , b = (b1 , b2 , . . . , bn)T ∈ Rn y x = (x1 , x2 , . . . , xn)T ∈ Rnes la incógnita.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
28/57
Sergio Plaza 123
Consideremos una matriz Q ∈ M (n × n,R) , la cual suponemos tiene inversa. Tenemos queAx = b es equivalente a escribir 0 = −Ax + b , sumando a ambos miembros de esta últimaigualdad el término Qx , no queda la ecuacíon Qx = Qx
−Ax + b , multiplicando esta ecuación
por la izquierda por Q−1 obtenemos x = (I − Q−1A)x + Q−1b , lo que nos sugiere proponerel siguiente método iterativo para resolver la ecuación original Ax = b ,
x(k+1) = (I − Q−1A)x(k) + Q−1b, (3.30)
donde x(0) ∈ Rn es arbitrario. Sobre la convergencia del método propuesto, tenemos el siguientecorolario.
Corolario 3.5 La f´ ormula de iteraci´ on x(k+1) =
I − Q−1Ax(k) + Q−1b define una sucesi´ on que converge a la soluci´ on de Ax = b , para cualquier condici´ on inicial x(0) ∈ Rn si y s´ olosi ρ I − Q
−1A < 1 . Adem´ as, si existe una norma | || en M (n × n, R) , en la cual se tiene ||I − Q−1A|| < 1 , entonces el método iterativo converge cualesquiera que sea la condici´ on inicial x(0) ∈ Rn dada.
Observación La fórmula de iteración
x(k+1) =
I − Q−1Ax(k) + Q−1bdefine un método iterativo de punto fijo. En efecto, consideremos la función F : Rn −→ Rndefinida por F (x) =
I − Q−1Ax + Q−1b . Observemos que si x es un punto fijo de F
entonces x es una solución de la ecuación Ax = b . Además, si x =
I − Q−1Ax + Q−1bentonces se tiene que
x(k) − x =
I − Q−1A
x(k−1) − x
,
por lo tanto x(k) − x I − Q−1A x(k−1) − x ,de donde, iterando esta desigualdad obtenemosx(k) − x I − Q−1Ak x(0) − x ,luego si
I − Q−1A < 1 , se tiene de inmediato que limk→∞ x(k) − x = 0 para cualquierx(0) ∈ Rn dado.
Observación. La condiciónI − Q−1A < 1 implica que las matrices Q−1A y A tienen
inversas.
Teorema 3.19 Si I − Q−1A < 1 para alguna norma matricial subordinada en M (n ×
n,R) , entonces el método iterativo x(k+1) =
I − Q−1Ax(k) + Q−1b es convergente a una soluci´ on de Ax = b , para cualquier vector inicial x(0) ∈ Rn . Adem´ as, si λ =
I − Q−1A <1 , podemos usar el criterio de parada
x(k) − x(k−1) < ε y se tiene que x(k) − x λ
1 − λx(k) − x(k−1) · · · λk
1 − λx(1) − x(0) .
, es decir, x(k) − x λk1 − λ
x(1) − x(0) . (3.31)
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
29/57
Sergio Plaza 124
También vale la desigualdad siguiente
x(k) − x ρ(I − Q−1A)k
1 − ρ(I − Q−1A) x(1) − x(0) . (3.32)Observación. Desde la definicíon de radio espectral de una matriz, se tiene que ρ(A) < 1
implica que existe una norma matricial || || en M (n×n,R) , tal que ||A|| < 1 . Por otra parte, si||A|| < 1 para alguna norma matricial en M (n×n,R) entonces se tiene que ρ(A) < 1. Notemosque si existe una norma matricial || || en M (n × n,R) , tal que ||A|| 1 no necesariamente setiene que ρ(A) 1 .
Observación. Si M 1 y M 2 son dos métodos iterativos convergentes para resolver un sistema
de ecuaciones lineales Ax = b , digamos M 1 : x(k+1) = G1x(k) + c1 y M 2 : x(k+1) =
G2x(k) + c2 . Si ρ(G1)) ρ(G2) , entonces M 1 converge más rápido que M 2 a la solución de la
ecuación. Además, si existe una norma || · || en M (n × n,R
) tal que ||G1||
||G2|| , entoncesM 1 converge más rápido que M 2 a la solución de la ecuación.
3.9 Método de Richardson
Para este método tomamos QR = I , luego el método iterativo x(k+1) =
I − Q−1Ax(k) +
Q−1b se transforma en
x(k+1) = (I − A)
T Rx(k) + b, (3.33)
el cual converge si y sólo si ρ(T R) = ρ(I − A) < 1 .
Si existe una norma matricial · para la cual se tiene que T R = ||I − A|| < 1 , entoncesel método iterativo de Richardson es convergente.
Ejemplo 64 Resolver el sistema de ecuaciones lineales usando el método de Richardson.
1 1213
1
3 1 1
2
12
13 1
x
yz =
1118
11
18
1118
Solución. Tenemos
T R = I − A = 1 0 00 1 0
0 0 1
−
1 1213
13 1
12
12
13 1
=
0 −12 −13
−13 0 −12
−12 −13 0
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
30/57
Sergio Plaza 125
Llamando x(j) = (xj yj zj)T , nos queda
x(k+1) = T Rx(k) + b =
0
−12
−13
− 13 0 −12
− 12 −13 0
xkyk
zk
+
1118
1118
1118
se tiene ||T R||∞ = 56 < , luego el método iterativo de Richardson para este sistema converge.
3.10 Método de Jacobi
En este caso tomamos
QJ = diag (A) =
a11 · · · 0... . . . ...0 · · · ann
donde los elementos fuera de la diagonal en QJ son todos iguales a 0. Notemos que det(QJ ) =
a11a22 · · · ann , luego det(QJ ) = 0 si y sólo si aii = 0 para todo i = 1, . . . , n , es decir, QJ tiene inversa si y sólo si aii = 0 para todo i = 1, . . . , n .
Como antes, colocando esta matriz QJ = diag(A) en la fórmula iterativa definida por
x(k+1) =
I − diag(A)−1A
T J x(k) + diag(A)−1b , (3.34)
obtenemos un método iterativo convergente si y sólo si ρ(T J ) = ρ(I − diag(A)−1A) < 1 . Siexiste una norma matricial · para la cual se tiene que T J = ||I − diag(A)−1A|| < 1 ,entonces el método iterativo de Jacobi es convergente.
Examinemos un poco más la fórmula iterativa del método de Jacobi. Tenemos, en este caso,
que un elemento genérico de Q−1A es de la forma aijaii y todos los elementos de la diagonal deQ−1A son iguales a 1. Luego, tomando la norma ∞ en M (n × n,R) tenemos que
I − diag(A)−1A∞ = max1in
nj=1 ,j=i
|aij ||aii|
.
Recordemos que una matriz A es diagonal dominante si
|aii| >n
j=1 , j=i|aij | , 1 i n,
es decir,n
j=1 , j=i
aijaii
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
31/57
Sergio Plaza 126
3.11 Método de Gauss–Seidel
En esta caso, consideremos la matriz Q como la matriz triangular obtenida considerando la
parte triangular inferior de la matriz A incluyendo su diagonal, es decir,
QG-S =
a11 0 · · · 0a21 a22 · · · 0
......
. . . ...
an1 an2 · · · ann
Se tiene que det(QG-S) = a11a22 · · · ann . Luego, det(QG-S) = 0 si y sólo si aii = 0 ( i =1, . . . , n ). Usando la matriz QG-S, obtenemos el método iterativo
x(k+1) = I − Q−1
G-SA
T G-S
x(k) + Q−1G-S
b . (3.35)
Teorema 3.21 Sea A ∈ M (n × n, R) . Entonces el método iterativo de Gauss–Seidel es convergente si y s´ olo si ρ(T G-S ) = ρ(I − Q−1G-S A) < 1 , donde QG-S es la matriz triangular inferior definida arriba a partir de A .
Como en el caso del método iterativo de Jacobi, tenemos el siguiente teorema.
Teorema 3.22 Si A ∈ M (n × n,R) es una matriz es diagonal dominante entonces el métodode Gauss–Seidel converge para cualquier elecci´ on inicial x(0) .
Ejemplo 65 Considere el sistema de ecuaciones lineales
4 2 12 5 2
1 2 6
xy
z
=
54
7
Explicitaremos los métodos iterativos de Jacobi y Gauss–Seidel para este sistema. Estudi-
aremos la convergencia de ellos sin iterar. Finalmente, sabiendo que la solución exacta del
sistema es (xT , yT , zT ) = (1, 0, 1) y usando el punto de partida (1, 1, 1) nos podemos pregun-
tar ¿Cuál de ellos converge más rápido?, para las comparaciones usaremos la norma ∞ enM (n
×n,R) .
Primero que nada tenemos que los métodos iterativos de Jacobi y Gauss–Seidel convergen,
pues la matriz asociada al sistema es diagonal dominante.
Explicitaremos el método de Jacobi. En este caso tenemos
QJ =
4 0 00 5 0
0 0 6
por lo tanto
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
32/57
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
33/57
Sergio Plaza 128
Como ||T G-S||∞ = max{|−14 | + |−14 |, | 210 | + |−310 |, | 2120 | + | 17120} = max{ 34 , 510 , 19120} = 0.75 < 1 .Luego, el método de Gauss–Seidel converge para cualquier condición inicial x(0) ∈ Rn dada.
Notemos que cómo ||T G-S||∞
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
34/57
Sergio Plaza 129
3.13 Otra forma de expresar los métodos iterativos para
sistemas lineales
Sea
A =
a11 · · · a1n...
. . . ...
an1 · · · ann
podemos escribir A en la forma
A =
a11 · · · a1n
... . . .
...
an1 · · ·
ann
=
a11 0 · · · 00 a22 · · · 0...
... . . .
...
0 · · · 0 ann
D
−
0 0 · · · 0−a21 0 · · · 0
... . . .
......
−an1 · · · −ann−1 0
C L
−
0 −a12 · · · −a1n0 0
. . . ...
0 0 · · · −an−1n0 0 · · · 0
C U
Notemos primero que Ax = b si y sólo si (D − C L − C U )x = b si y sólo si Dx = (C L +C U )x + b .
Veamos como quedan los métodos anteriores con esta notación.
Método de Jacobi. Si det(D) = 0 , entonces como (D − C L − C U )x = b se sigue quex = D−1(C L + C U )
T j
x + D−1b C J
(3.39)
luego el método de Jacobi se puede escribir como
x(k+1) = D−1(C L + C U ) T j
x(k) + D−1b C J
Método de Gauss–Seidel. Este se puede escribir como
(D
−C L)x
(k+1) = C U x(k) + b (3.40)
de donde, si det(D − C L) = 0 nos queda
x(k+1) = (D − C L)−1C U T G-S
x(k) + (D − C L)−1 C G-S
b
Resumen. Supongamos que la matriz A se escribe en la forma A = D − C L − C U , dondeD = diag(A) , C L es el negativo de la parte triangular inferior estricta de A y C U es el
negativo de la parte triangular superior estricta de A . Entonces podemos rescribir los métodos
iterativos vistos antes como sigue:
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
35/57
Sergio Plaza 130
Richardson
Q = I G = I − A
x(k+1) = (I − A)x(k) + b
Jacobi
Q = D
G = D−1(C L + C U )
Dx(k+1) = (C L + C U )x(k) + b
Gauss-Seidel Q = D − C LG = (D − C L)−1C U
(D − C L)x(k+1) = C U x(k) + bSOR
Q = ω−1(D − ωC L)G = (D − ωC L)−1(ωC U + (1 − ω)D)
(D − ωC L)x(k+1) = ω(C U x(k) + b) + (1 − ω)Dx(k)
ω = 1
α , 0 < ω
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
36/57
Sergio Plaza 131
Solución. Tenemos el sistema de ecuaciones lineales
1
3
1
4
1
4
1
5
x1
x2
= 7
12
0.45
.
a) El vector b̂ =
0.58
0.45
es una perturbación del vector b =
7
12
0.45
. Sean xT la
solución exacta del sistema Ax = b y xA la solución exacta del sistema Ax = b̂ . Se tiene
entonces que xA es una aproximación a xT . Para simplificar los cálculos trabajaremos con la
norma subordinada || · ||∞ . Como b̂ es una perturbación de b , tenemos la fórmula
E R(xA) = ||xT − xA||∞
||xT ||∞ ||A||∞||A−1||∞ ||b − b̂||∞||b||∞ .
Ahora,
b − b̂ =
3.33333333 × 10−30
.
Recordemos que si A =
a11 a12a21 a22
, entonces
A−1 = 1
det(A)
a22 −a12−a21 a11
En nuestro caso, det
13 1414
15
= 1240 . Luego,
A−1 = 11240
15 −14
−14 13
= 240
15 −14
−14 13
= 48 −60−60 80
.
De esto, tenemos
||A
||∞ = max
1
3
+ 1
4
, 1
4
+ 1
5 = max 7
12
, 9
20 = 7
12
||A−1||∞ = max{|48| + | − 60|, | − 60| + |80|} = 140
||b||∞ = max
7
12, 0.45
=
7
12
||b̂||∞ = max{0.58, 0.45} = 0.58
||b − b̂||∞ = max{3.33333333 × 10−3, 0} = 3.33333333 × 10−3 .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
37/57
Sergio Plaza 132
Reemplazando nos queda
E R(xA) 7
12 140 3.3333333
×10
−3
712
= 0.4666666662 ,
esto es, E R(xA) 0.4666666662 .
b) Consideremos ahora la matriz perturbada
 =
0.33 0.25
0.25 0.20
.
Podemos escribir  en la forma  = A(I + E ) , donde I es la matriz identidad 2 × 2 y E es la matriz de error, esto es, .E =  − A . Como  = A(I + E ), se tiene que  − A = AE .Luego,
AE = Â − A =
0.33 0.25
0.25 0.20
− 13 14
14
15
= −3.33333333 × 10−3 0
0 0
,
de donde ||AE ||∞ = 3.33333333 × 10−3 .Veamos si podemos usar la fórmula
||xT − xA||||xT ||
k(A)
1 − k(A) ||AE ||||A||· ||AE ||||A|| ,
para ello debemos verificar que
||AE || < 1||A−1|| .
Como ||A||∞ = 140 y ||AE ||∞ = 3.33333333 × 10−3 , se cumple que
||AE ||∞ < 1140
= 7.14285714 × 10−3 ,
y podemos aplicar la fórmula anterior. Reemplazando nos queda
||xT − xA||∞||xT ||∞
81.66666667
1 − 81.66666667 × 3.33333333×10−30.5833333333× 3.3333333 × 10
−3
0.5833333333
= 81.66666667
1 − 81.66666667 × 5.7142857 × 10−3 × 5.7142857 × 10−3
= 0.466666667
0.5333333349 = 0.8749999945
Luego E R(xA) 0.8749999945 .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
38/57
Sergio Plaza 133
Problema 3.2 Dada la matriz
A = 2 −1 −1
−1 1 1−1 1 3
se tiene que A−1 = 1 1 0
1 5/2 −1/20 −1/2 1/2
(a) Obtenga la descomposición de Cholesky de A . Utilice lo anterior para resolver el sistema
Ax = b para el vector b = (1, 1, 2)T .
(b) Estime a priori la magnitud del error relativo si la matriz A se perturba quedando
finalmente
à =
2 −0.99 −0.98−1 1 0.99
−1 1.02 2.99
Solución.
(a) Tenemos que
A =
2 −1 −1−1 1 1
−1 1 3
es simétrica. Ahora, A1 = [2] , luego det(A1) = 2 > 0 , A2 =
2 −1−1 1
y det(A2) =
1 > 0 , A3 = A = 2 −1 −1
−1 1 1−1 1 3 y det(A3) = 2 > 0 . Por lo tanto A es positiva
definida, y consecuentemente tiene descomposición de Cholesky.
Para obtener la descompsición de Cholesky de A escribamos
2 −1 −1−1 1 1
−1 1 3
=
ℓ11 0 0ℓ21 ℓ22 0
ℓ31 ℓ32 ℓ33
ℓ11 ℓ21 ℓ310 ℓ22 ℓ32
0 0 ℓ33
De aquı́, ℓ211 = 2 , de donde ℓ11 =√
2 ; ℓ11ℓ21 = −1 , de donde ℓ21 = −√ 22 , ℓ11ℓ31 = −1 ;
ℓ31 = −√ 22 ; ℓ
221 + ℓ
222 = 1 , de donde ℓ22 =
√ 22 ; ℓ21ℓ31 + ℓ22ℓ32 = 1 , de donde ℓ32 =
√ 22 ;
finalmente ℓ231 + ℓ232 + ℓ233 = 3 , de donde ℓ33 = √ 2 . Por lo tanto, 2 −1 −1−1 1 1
−1 1 3
=
√ 2 0 0
−√ 22
√ 22 0
−√ 22
√ 22
√ 2
√ 2 −
√ 22 −
√ 22
0√ 22
√ 22
0 0√
2
Ahora, resolver el sistema Ax = b , con bT = (1, 1, 2) es equivalente a resolver los
sistemas Ly = b
LT x = y
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
39/57
Sergio Plaza 134
El sistema Ly = b
√
2 0 0
−
√ 2
2
√ 2
2
0
−√ 22 √ 22 √ 2
α
β
γ =
1
1
2
De aquı́√
2 α = 1 , de donde α =√ 22 ; −
√ 22 α +
√ 22 β = 1 , reemplazando y despejando
nos da que β = 32√
2 ; finalmente −√ 22 α +
√ 22 β +
√ 2γ = 2 , reemplazando y despejando
nos da que γ =√ 22 . Debemos resolver ahora el sistema L
T x = y , es decir,
√ 2 −
√ 22 −
√ 22
0√ 22
√ 22
0 0√
2
xy
z
=
√ 22
3√ 2
2√ 22
de donde z = 12 , y = 52 , x = 2 .
(b) Sean xT y xA las soluciones exactas de los sistemas Ax = b y Ãx = b , respectivamente,
es decir, xT = A−1b . Entonces
E (xA = ||xA − xT || = ||xA − A−1b||= ||xA − A−1 ÃxA|| = ||(I − A−1 Ã)xA|| ||I − A−1 Ã|| ||xA||
de donde
E R(xA) = ||xA − xT ||
||xA||
||I −
A−1 Ã||
.
Para simplificar los cálculos usamos la norma subordinada || ||∞ . Ahora, tenemos
A−1 =
1 1 0
1 5
2
−12
0 −1
2
1
2
à =
2 −0.99 −0.98
−1 1 0.99
−1 1.02 2.99
luego,
A−1 Ã =
1 0.01 0.010 1.0 0
0 0.01 1.0
Además, como
I =
1 0 00 1 0
0 0 1
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
40/57
Sergio Plaza 135
se tiene que
I − A−1 Ã = 0 −0.01 −0.010 0 00 −0.01 0
luego, ||I −A−1 Ã||∞ = max{0.02, 0, 0.01} = 0.02 , de donde ||xA−xT ||∞||xA||∞ ||I −A−1 Ã||∞ =0.02 .
Otra solución. Escribimos à de la forma à = A(I + E ) . Entonces se tiene las f́ormulas
1.
E R(xA) = ||xT − xA||
||xT || ||E ||
1 − ||E ||si
||E
|| < 1 .
2.
E R(xA) = ||xT − xA||
||xT || k(A)
1 − k(A) ||AE ||||A||||AE ||||A||
si ||AE || < 1||A−1|| .
Usemos por ejemplo la primera de ellas. Debemos calcular la matriz E . De la ecuación
à = A(I + E ) se tiene que A−1 à = I + E , de donde, A−1 à − I = E . Realizando loscálculos, obtenemos que
E = 0 0.01 0.01
0 0 00 0.01 0
Por simplicidad de los cálculos, usaremos la norma subordinada || ||∞ . Luego, ||E ||∞ =0.02 < 1 , por lo tanto, reemplazando nos queda,
||xT − xA||||xT ||
||E ||1 − ||E || =
0.02
1 − 0.02 = 0.02
0.98 = 0.0204016...
Ahora usamos la segunda de las f órmulas. Tenemos que calcular k(A) = ||A|| ||A−1|| .Sabemos que
A =
2 −1 −1−1 1 1−1 1 3
luego ||A||∞ = 5y
A−1 =
1 1 0
1 5
2
−12
0 −1
2
1
2
luego ||A−1||∞ = 4 ,
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
41/57
Sergio Plaza 136
de donde k∞(A) = 5 × 4 = 20 . Para aplicar la fórmula debemos verificar que ||AE ||∞ <1
||A−1||∞ . Tenemos que
AE = 0 0.01 0.010 0.005 0.01
0 0.005 0
luego, ||AE ||∞ = 0.02 y ||A−1||∞ = 4 , de aquı́ se tiene que 1||A−1||∞ = 14 = 0.25 yes claro entonces que se satisface la condición ||AE ||∞ < 1||A−1||∞ . Reemplazando losvalores obtenidos, nos queda
||xT − xA||∞||xT ||∞
20
1 − 20 · 0.025· 0.02
5 =
20 × 0.0041 − 20 × 0.004
=
0.08
1 − 0.08 = 0.08
0.92 = 0.08695652...
esto es,||xT − xA||∞
||xT ||∞ 0.08695652...
Problema 3.3 Sean
A =
1 −1 −1 −10 1 −1 −10 0 1 −10 0 0 1
y b =
5.00
1.02
1.04
1.10
(a) Calcule una solución aproximada xA del sistema Ax = b , primero aproximando cada
entrada del vector b al entero más próximo, obteniendo un vector b̃ y luego resolviendo
el sistema Ax = b̃ .
(b) Calcule ||r||∞ y k∞(A) , donde r es el vector residual, es decir r = b − AxA y k∞(A)el número de condicionamiento de la matriz A.
(c) Estime una cota para el error relativo de la solución aproximada, respecto a la solución
exacta (no calcule esta última explı́citamente).
Solución.
(a) El vector perturbado es (5 1 1 1)T . Luego la solución del sistema perturbado es
1 −1 −1 −10 1 −1 −10 0 1 −10 0 0 1
x
y
z
w
=
5
1
1
1
de donde (x, y, z, w) = (12, 4, 2, 1) = xA
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
42/57
Sergio Plaza 137
(b) Tenemos ||b||∞ = ||̃b||∞ = 5 . Por otra parte,
r = b − AxA =
5.001.02
1.04
1.10
−
1 −1 −1 −10 1 −1 −10 0 1 −10 0 0 1
124
2
1
=
5.00
1.02
1.04
1.10
−
5
1
1
1
=
0
0.02
0.04
0.10
Luego, ||r||∞ = 0.10 .Para encontrar la inversa de la matriz A basta resolver el sistema
1 −1 −1 −10 1 −1 −10 0 1 −10 0 0 1
a11 a12 a13 a14a21 a22 a23 a24a31 a32 a33 a34a41 a42 a43 a44
=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
de donde
A−1 =
1 1 2 4
0 1 1 2
0 0 1 1
0 0 0 1
Luego, ||A−1||∞ = 8 . Tenemos que ||A||∞ = 4 , luego k∞(A) = ||A||∞||A−1||∞ = 4×8 =32 .
(c) Usamos la fórmula1
k(A)
||r||||b||
||xT − xA||||xT || k(A)
||r||||b||
Reemplazando los datos nos queda
1
32 × 0.10
5
||xT − xA||||xT || 32 ×
0.10
5
es decir,
0.625 × 10−3 ||x
T −x
A||||xT || 0.64 .
Problema 3.4 Encuentre una descomposición del tipo LU para la matriz A siguiente
A =
4 3 2 1
3 4 3 2
2 3 4 3
1 2 3 4
Use la descomposión anterior para solucionar el sistema Ax = (1 1 − 1 − 1)T .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
43/57
Sergio Plaza 138
Solución. La descomposición de Doolittle de A es dada por
A = L · U =
1 0 0 034 1 0 0
12
67 1 0
14
57
56 1
·
4 3 2 1
0 7432
54
0 0 127107
0 0 0 53
Ahora resolver el sistemas Ax = b es equivalente a resolver los sistemas Ly = b y U x = y.
Tenemos que b = (1 1 − 1 − 1)T . Llamando y = (y1 y2 y3 y4)T , de la forma del sistemaLy = b, obtenemos que y1 = 1 , y2 =
14 , y3 = −127 , y y4 = 0. Ahora al resolver el sistema
U x = b obtenemos x4 = 0 , x3 = −1 , x2 = 1 y x1 = 0 .
Problema 3.5 Considere el sistema de ecuaciones lineales Ax = b , donde
A =
2 −3 8 14 0 1 −10
16 4 −2 10 7 −1 5
y b =
1
1
1
1
a) Usando aritmética exacta y el método de eliminación gaussiana con pivoteo resuelva el
sistema de ecuaciones lineales Ax = b .
b) Denote por B a la matriz P A obtenida en el item anterior Demuestre que el método
iterativo de Jacobi aplicado a la matriz B es convergente. Usando como punto inicial
(0.0377,0.21819,0.20545,-0.06439) y la máxima capacidad de su calculadora, realice itera-
ciones con el método de Jacobi para obtener una solución aproximada del sistema Bx = b .Use como criterio de parada (xn+1, yn+1, zn+1, wn+1) − (xn, yn, zn, wn) 10−5 .
Solución. a) Tenemos que
A =
2 −3 8 14 0 1 −10
16 4 −2 10 7 −1 5
y b =
1
1
1
1
.
Escribiendo la matrix ampliada del sistema, nos queda
A =
2 −3 8 1 14 0 1 −10 116 4 −2 1 10 7 −1 5 1
,de donde
s =
8
10
16
7
y P =
1
2
3
4
.
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
44/57
Sergio Plaza 139
Luego
m1 = max28 , 410 , 1616 , 0 = 1 = m31por lo tanto debemos intercambiar la fila 1 con la fila 3. Realizando este intercambio de filas y
la eliminación gaussiana, nos queda
16 4 −2 1 14 0 1 −10 12 −3 8 1 10 7 −1 5 1
F 2 − 14F 1→
F 3 − 18F 1
16 4 −2 1 10 −1 3/2 −41/4 3/40 −7/2 33/4 7/8 7/80 7 −1 5 1
de donde
L1 = 1
1/41/8
0
, s1 = 16
108
7
, P 1 = 3
21
4
Para la elección del segundo pivote tenemos
m2 = max
1
10,
7
16,
7
7
= 1 = m42
por lo tanto debemos intercambiar la fila 2 con la fila 4
16 4
−2 1 1
0 7 −1 5 10 −7/2 33/4 7/8 7/80 −1 3/2 −41/4 3/4
F 3
− −12
F 2
→
F 4 − −17 F 2
16 4
−2 1 1
0 7 −1 5 10 0 31/4 27/8 11/8
0 0 19/14 −227/28 25/28
luego,
L11 =
1
0
1/8
1/4
, L2 =
0
1
−1/2−1/7
, P 2 =
3
4
1
2
, S 2 =
16
7
8
10
Para la elección del tercer pivote tenemos que
m3 = max
31
32,
19
140
=
31
32 = m33
y obtenemos
16 4 −2 10 7 −1 5 10 0 31/4 27/8 11/8
0 0 19/14 −227/28 25/8
→
F 4 − 38217F 3
16 4 −2 1 10 7 −1 5 10 0 31/4 27/8 11/8
0 0 0 −4395/434 283/434
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
45/57
Sergio Plaza 140
luego,
L3 =
00
1
38/217
Por lo tanto
P A = LU =
1 0 0 0
0 1 0 0
1/8 −1/2 1 01/4 −1/7 38/217 1
16 4 −2 10 7 −1 50 0 31/4 27/8
0 0 0 −4395/434
(3.41)
donde
P =
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
.
Por lo tanto
P A =
16 4 −2 10 7 −1 52 −3 8 14 0 1 −10
Resolviendo la ecuación se obtiene que
w = − 2834395
, z = 301
1465, y =
959
4395, x = 331/8790 (3.42)
Ahora, como
B = P A =
16 4 −2 10 7 −1 52 −3 8 14 0 1 −10
tenemos que la matriz B es diagonal dominante, por lo tanto el método de Jacobi converge.
Por otra parte, la matriz de Jacobi es dada por
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
46/57
Sergio Plaza 141
J = I − Q−1B
= I 4 −
1/16 0 0 00 1/7 0 0
0 0 1/8 0
0 0 0 −1/10
16 4 −2 10 7 −1 52 −3 8 14 0 1 −10
=
0 −1/4 1/8 −1/160 0 1/7 −5/7
−1/4 3/8 0 −1/82/5 0 1/10 0
Para determinar si el método de Jacobi converge determinaremos los valores propios de J .
Tenemos
det(J − λI 4) = det
−λ −1/4 1/8 −1/160 −λ 1/7 −5/7
−1/4 3/8 −λ −1/82/5 0 1/10 −λ
= λ4 + 171120 λ2 − 2194480 λ + 332240 (3.43)
de donde se tiene que los valores propios son
λ1,2 = −0.2483754458 ± 0.3442140503iλ3,4 = −0.2483754458 ± 0.1416897424i (3.44)
Por lo tanto, se tiene que el radio espectral es ρ = 0.4244686967
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
47/57
Sergio Plaza 142
2. Resolver Anx = bn en forma exacta. Denote por x̄n la solución exacta y cálcule el error
relativo de la aproximación x̃ = (1, 0)T .
3. Lo razonablemente esperado es que x̄n converja a x̃ cuando n tiende a infinito. Para este
ejemplo, ¿ se tiene dicha afirmación?. Calcule K ∞(An) y explique el resultado obtenido.
Solución. Para cada n ∈N , un resultado para una solución de Anx = bn es x̃ = (1, 0) .
1. El vector residual asociado a esta solución es
rn = Anx̃ − bn .
Tenemos
rn =
1 2
2 4 + 1n2
1
0
−
1
2 − 1n2
=
1
2
−
1
2 − 1n2
=
01
n2
Ahora, la solución exacta del sistema es
1 2
2 4 + 1n2
x
y
=
1
2 − 1n2
esto del par de ecuaciones lineales
x + 2y = 1
2x +
4 +
1
n2
y = 2 − 1
n2 .
De la primera ecuación obtenemos x = 1 − 2y , reemplazando en la segunda ecuación nosqueda
2 − 4y + 4y + 1
n2 y = 2 − 1
n2 ,
es decir, 1
n2y = − 1
n2 , de donde y = −1 , por lo tanto x = 3 . Note que la solución es
exactamente la misma para cada n ∈N , es decir, la solución no depende de n ∈N .Por lo tanto la solución dada no es razonablemente confiable, pues no se aproxima en
nada a la solución exacta xT = (3, −1) del sistema Anx = bn .
2. Ya calculamos la solución exacta xn de Anx = bn , la cual es xn = (3, −1) = xT paratodo n ∈ N .
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
48/57
Sergio Plaza 143
Usando la norma || · ||∞ para simplificar los cálculos.
E R
(x̃) = ||xT − x̃||∞
||xT ||∞
= ||(3, −1) − (1, 0)||∞
||(3, −1)||∞
= ||(2, −1)||∞
||(3, −1)||∞
= max{|2|, | − 1|}
max{|3|, | − 1|}
= 2
3 .
3. No, pues xn = (3, −1) = xT es un vector constante y no se aproxima (obviamente) ax̃ = (1, 0) .
Para calcular k∞(An) , tenemos
||An||∞ = max{|1| + |2|, |2| +4 + 1
n2} = 6 + 1
n2
Ahora, det(An) = 4 + 1
n2 − 4 = 1
n2 . Luego
A−1n = 11n2
4 + 1
n2
−2
−2 1
= n2
4 +
1
n2 −2
−2 1
=
4n2 + 1 −2n2
−2n2 n2
y ||A−1
n ||∞ = max{|14n2
+ 1| + | − 2n2
| + |n2
|} = max{6n2
+ 1, 3n2
} = 6n2
+ 1 . Por lotanto
k∞(An) =
6 + 1
n2
(6n2 + 1)
= 36n2 + 6 + 6 + 1
n2
= 36n2 + 12 + 1
n2−−−→n→∞ ∞,
8/19/2019 Sistemas Lineales Con Ejercicios Resueltos
49/57
Sergio Plaza 144
lo cual significa que la matriz An está muy mal condicionada para valores grandes de n (es
numéricamente no invertible para n grande), lo cual explica la mala aproximación x̃ de xn para
n grande.
3.15 Ejercicios Propuestos
Problema 3.1 Para resolver un sistema de ecuaciones lineales Ax = b , donde x, b ∈R2 , sepropone el siguiente método iterativo
x(k+1) = Bx(k) + b , k 0
donde
B =
λ c
0 −λ
, λ, c ∈R
1. ¿Para qué valores de λ y c el método iterativo propuesto es convergente?
2. Sea x̃ el punto fijo de la iteración. Calcule ||x̃ − x(k)||∞ y ||x(k+1) − x(k)||∞ cuandok −→ ∞ ¿Es la convergencia la punto fijo independiente de c ? Justificque.
Problema 3.2 Dado un método iterativo para resolver un sistema de ecuaciones lineales
x(k+1) = Bx(k) + c ,
Si det(B) = 0 ¿Puede el método propuesto ser convergente?
Problema 3.3 Si un método iterativo de punto fijo xn+1 = Axn , donde A ∈ M(n × n,R)tiene un punto fijo x̄ = 0 . Pruebe que ||A|| 1 para cualquier norma ssubordinada enM(n × n,R) .Problema 3.4 Dada una matri