2-sistemas de ecuaciones lineales
DESCRIPTION
Curso de Cálculo Numérico, Capítulo 2TRANSCRIPT
-
Universidad de MontevideoFacultad de Ingeniera
Curso Terico deCLCULO NUMRICO
Tema: SISTEMAS LINEALES
Objetivos de aprendizaje Conocer la mecnica del mtodo de Gauss y cmo y porqu se hace pivotaje. Comprender cmo el mtodo de Gauss puede interpretarse como una descomposicin
triangular. Conocer varios mtodos de descomposicin triangular, cundo son aplicables y qu
ventajas tienen. Comprender el concepto de sistema mal condicionado y su relacin con el nmero de
condicin. Conocer los efectos del mal condicionamiento en la sensibilidad de la solucin a errores en
los datos y en la relacin entre residuo y error.
Germn BRESCIANO
-
2 SISTEMAS DE ECUACIONES LINEALES............................................................................... 2-12.1 INTRODUCCIN...........................................................................................................................2-12.2 GENERALIDADES ........................................................................................................................2-22.3 MTODOS DIRECTOS...................................................................................................................2-3
2.3.1 Sistemas con matriz triangular superior .......................................................................... 2-32.3.2 Mtodo de Gauss .............................................................................................................. 2-3
2.3.2.2 Pivoteo .........................................................................................................................................2-52.3.3 Mtodos de descomposicin triangular............................................................................ 2-6
2.3.3.2 Mtodo de Crout...........................................................................................................................2-82.3.3.3 Mtodo de Doolitle.......................................................................................................................2-92.3.3.4 Mtodo de Cholesky.....................................................................................................................2-92.3.3.5 Aplicacin a matrices tridiagonales............................................................................................2-10
2.3.4 Anlisis de error ............................................................................................................. 2-112.3.4.1 Sistemas mal condicionados.......................................................................................................2-112.3.4.2 Normas de vectores y matrices...................................................................................................2-122.3.4.3 Anlisis de perturbaciones..........................................................................................................2-132.3.4.4 Errores de redondeo ...................................................................................................................2-13
2.3.5 Mejora de la solucin y estimacin del nmero de condicin........................................ 2-142.3.6 Clculo de determinantes ............................................................................................... 2-15
2.4 MTODOS ITERATIVOS .............................................................................................................2-152.4.1 Mtodo de Jacobi ........................................................................................................... 2-152.4.2 Mtodo de Gauss Seidel ................................................................................................. 2-172.4.3 Convergencia.................................................................................................................. 2-17
-
Sistemas de ecuaciones lineales 2-1
2 Sistemas de ecuaciones lineales
2.1 IntroduccinLa necesidad de resolver sistemas de ecuaciones lineales se presenta en los ms diversoscampos de ingeniera, desde transmisin de calor hasta circuitos de corriente alterna.En lo que sigue veremos cmo resolver sistemas de ecuaciones lineales de n ecuaciones con nincgnitas, con coeficientes reales, aunque casi todo lo que veremos se aplica tambin asistemas con coeficientes complejos.Estos sistemas suelen representarse en la forma Ax = b donde A es una matriz real de nxn y bes un vector de Rn.Supondremos que A es no singular, en cuyo caso el sistema es compatible y determinado, esdecir, tiene solucin y es nica.Si bien tericamente este sistema puede resolverse calculando x = A-1b , para ello es necesariocalcular la matriz inversa de A, lo cual implica mucho ms esfuerzo de clculo1 que resolver elsistema por otros mtodos.Algo similar ocurre con el mtodo de Cramer, que implica gran esfuerzo para calcular losdeterminantes involucrados, lo que lo hace muy poco prctico.
EjemploSe tiene una placa de 2cm por 2cm de 1cm de espesor cuyas superficies superior e inferiorestn trmicamente aisladas.Dos bordes opuestos se mantienen a 50C y los otros dos a 0C y 100C respectivamente.Se quiere calcular el perfil de temperatura en el interior de la placa, para lo cual se considerauna retcula de puntos separados 0.5cm como se muestra en la Figura 2-1.
Figura 2-1 Perfil de temperatura en una placa
1 del orden se n2(n!) operaciones aritmticas
100C
100C
50C50C 50C
50C50C 50C
0C
0C
0C u1 u2 u3
u4 u5 u6
u7 u8 u9 100C
-
Sistemas de ecuaciones lineales 2-2
Su u(x,y) representa la temperatura en cada punto, se verifica que 022
2
2
=
+
yu
x
u
Aproximando las derivadas por diferencias finitas, se llega al siguiente sistema lineal:
=+
=+
=+
=+
=+
=+
=+
=+
=
1504504504
10040404
1504504504
986
9875
874
9653
86542
7541
632
5321
421
uuu
uuuu
uuu
uuuu
uuuuu
uuuu
uuu
uuuu
uuu
2.2 GeneralidadesPor lo general se aplica alguno de los mtodos de resolucin que veremos sin evaluarpreviamente el determinante; en muchas ocasiones el determinante y la inversa de la matrizson un subproducto de los clculos efectuados.Los algoritmos se evalan en funcin de su eficacia, teniendo en cuenta tres caractersticasfundamentales:
1. Nmero de operaciones necesarias. Se tienen en cuenta las operaciones elementalesentre nmeros en punto flotante (flops): +, -, / *, que es un buen indicador del tiempo deCPU.
2. Necesidades de memoria, los diferentes mtodos requieren almacenar las matrices dedistinta forma en la computadora y esto cambia las necesidades de memoria.
3. Rango de aplicabilidad: no todos los mtodos sirven para cualquier matriz no singular;adems, en funcin del mtodo y de las propiedades de la matriz, la precisin de losresultados puede verse afectada dramticamente.
Los tres criterios deben ser tenidos igualmente en cuenta ya que, por ejemplo, de nada sirve unmtodo rpido y preciso si no alcanza la memoria disponible.
Las matrices ms comunes en ingeniera pueden clasificarse en dos categoras:
1. Matrices llenas pero no muy grandes. Que poseen pocos elementos nulos y que el nmerode ecuaciones es de unos cientos. Estas matrices aparecen en problemas estadsticos,fsicos y de ingeniera.
2. Matrices vacas y muy grandes. En oposicin al caso anterior, tienen pocos elementos nonulos y adems estn situados con una cierta regularidad. En la mayora de estos casos elnmero de ecuaciones supera los miles. Estas matrices son comunes en la resolucin deecuaciones diferenciales de problemas de ingeniera.
En general los mtodos directos se emplean con las primeras, mientras que los mtodositerativos se aplican a las segundas.
En todo lo que veremos se supone que los elementos de A y b son reales, pero casi todo esvlido si fueran complejos. Adems en ese caso se puede replantear el problema como elsiguiente sistema de coeficientes reales de 2n ecuaciones:
-
Sistemas de ecuaciones lineales 2-3
=
dc
z
yCDDC
donde C y D son matrices reales de nxn, y c, d, y y z son vectores de Rn tales que:
D C A i+=d c b i+=z y x i+=
2.3 Mtodos directosLos mtodos directos de resolucin de sistemas de ecuaciones lineales son aquellos quepermiten obtener la solucin con un nmero finito de operaciones, que depende del tamao dela matriz.Adems, si se pudiera emplear una aritmtica exacta, con los mtodos directos se obtendra lasolucin exacta del sistema.
2.3.1 Sistemas con matriz triangular superiorSi la matriz A es triangular superior, es decir
==
nn
nnnn
nn
nn
u
uu
uuu
uuuu
00000
0
,11,1
21,222
11,11211
L
L
MMOMM
L
L
UA
la solucin de la ltima ecuacin es trivial, xn = bn /unn.Una vez conocido xn, la penltima ecuacin se resuelve fcilmente despejando xn-1.Conocidos ahora xn y xn-1, se pasa a la ecuacin anterior y as sucesivamente.Se obtiene el algoritmo de sustitucin hacia atrs:
2-1 nnnn ubx /=
2-2 121/1
, ,, n-n-iuxubx iin
ijjijii =
=
+=
Por supuesto la solucin existe pues siendo U no singular, todos los trminos de su diagonalson no nulos.El determinante puede calcularse multiplicando los trminos de la diagonal.El nmero de operaciones es n2 .
2.3.2 Mtodo de GaussEn el mtodo de eliminacin de Gauss el problema original, Ax = b, se transforma, medianteadecuadas combinaciones lineales de las ecuaciones, en un sistema de la forma Ux = y dondeU es una matriz triangular superior. Este nuevo sistema equivalente al original se resuelveusando el algoritmo de sustitucin hacia atrs ya visto (2-1 y 2-2).Durante la transformacin del sistema original al equivalente con matriz triangular, lasoperaciones (que slo dependen de la matriz A) se realizan sobre la matriz y al mismo tiemposobre el trmino independiente.
-
Sistemas de ecuaciones lineales 2-4
El algoritmo de este mtodo puede escribirse:
2-3 )1()1(
= kkk
kik
ika
al
2-4 )1()1()( = kkjikk
ijk
ij alaa
+=
+=
=
,...,nkj,...,nki
,...,nk
11
11
2-5 )1()1()( = kkikk
ik
i blbb
donde los trminos de superndice (0) son iguales a los originales del sistema de ecuaciones.Obsrvese que los elementos subdiagonales de A(n-1) sern nulos.A cada uno de los trminos que aparecen en la diagonal de la matriz anterior se le denominapivote 2 , los cuales deben ser no nulos para que 2-3 pueda evaluarse.El nmero de operaciones necesarias en esta fase de eliminacin es de (4n3+3n2-7n)/6.Si se tienen en cuenta las n2 operaciones correspondientes a la fase de sustitucin hacia atrs,el nmero total de operaciones elementales para el mtodo de Gauss es (4n3+9n2-7n)/6
EjemploConsideremos en sistema
=
138
15
311413124
3
2
1
x
x
x
Como vamos a modificar simultneamente la matriz y el trmino independiente, usaremos lamatriz ampliada
133118413
15124
para eliminar los elementos subdiagonales de la primera columna, a segunda fila le sumamosla primera por y a la tercera fila le sumamos la primera por obteniendo
25.975.25.0025.1975.45.20
15124
para eliminar el elemento subdiagonal de la segunda columna, a la tercera fila le sumamos lasegunda por (0.5/2.5) obteniendo
40.580.10025.1975.45.20
15124
que se resuelve por sustitucin hacia atrs dando x1=2, x2=-2 y x3=3
2 Ntese que los pivotes no coinciden con los trminos originales de la diagonal de A; es decir, 0)1( kk
kkk aa
-
Sistemas de ecuaciones lineales 2-5
2.3.2.2 PivoteoSe ha supuesto que los pivotes sean distintos de cero. Si durante el proceso de eliminacin seobtiene un pivote nulo, por ejemplo el )1( kkka , se debe buscar en la parte inferior de la columnak-sima un coeficiente no nulo, es decir de entre los )1( kika i=k+1,,n se toma uno que seadistinto de cero. Se intercambia entonces la fila k (y su trmino independiente) con la fila i (y sutrmino independiente) que se haya escogido. Si dicho coeficiente no nulo no existiera, lamatriz sera singular.Esta permutacin de filas es til tambin cuando el pivote es pequeo aunque no nulo. Valorespequeos del pivote pueden producir grandes errores de redondeo, ya que siempre se dividepor el valor del pivote. Por consiguiente, para reducir los errores de redondeo conviene escogerel pivote mximo en valor absoluto. Para ello, hay dos tcnicas:
1. En el k-simo sistema se toma como pivote el coeficiente mayor en valor absoluto de lacolumna k situado por debajo de la fila k inclusive. Para ello se permutan las filas k y la delal pivote escogido y sus trminos independientes. Esta tcnica se denomina mtodo deGauss con pivoteo parcial.
2. En el k-simo sistema, se toma como pivote el coeficiente mayor en valor absoluto de lasubmatriz de orden n-k definida por los coeficientes que quedan por debajo de la fila k y ala derecha de la columna k. Para ello, se permutan la fila k (y el trmino independienteasociado) y la columna k con las del pivote escogido. Al final del proceso deben ponerse enel orden inicial las componentes del vector solucin, puesto que su posicin ha sidomodificada al realizar las permutaciones de columnas. Esta tcnica es el mtodo de Gausscon pivoteo total.
Estas dos estrategias producen mtodos numricamente estables. El mtodo de Gauss sinpivoteo no es necesariamente estable. En la prctica el pivoteo total no suele hacerse pues lamejora obtenida no compensa la mayor complejidad.A continuacin se presenta el algoritmo del mtodo de Gauss con pivoteo parcial
for j=1:n-1[pivote, fila_pivote]=max(abs(A(j:n,j)); % Busca la fila pivotefila_pivote=fila_pivote+j-1;if abs(pivote)< 10*eps
Msgbox(Matriz singular); % Matriz singularReturn;
endif fila_pivote(j)~=j
Aux=A(j,:); % Intercambia las filasA(j,:)=A(fila_pivote,:);A(fila_pivote,:)=Aux;temp=b(j); % y los trminos independientesb(j)=b(fila_pivote);b(fila_pivote)=temp;
end
for i=j+1:n % almacena los multiplicadores enA(i,j)=A(i,j)/A(j,j); % los lugares de A que se anularnA(i,j+1:n)=A(i,j+1:n)-A(i,j)*A(j,j+1:n); % transforma las filasb(i)=b(i)-A(i,,j)*b(j); % y trminos independientes
endend
x(n)=b(n)/A(n,n); % Comienza sustitucin hacia atrsfor j=n-1:-1:1
x(j)=(b(j)-sum(x(j+1:n).*A(j,j+1:n)))/A(j,j);end
-
Sistemas de ecuaciones lineales 2-6
2.3.3 Mtodos de descomposicin triangularSi analizamos el mtodo de Gauss sin pivoteo desde un punto de vista matricial, podemos verque con este algoritmo obtenemos una matriz triangular superior U a partir de A mediante
U = A(n-1) = GA = G(n-1)G(n-2) G(1)A , siendo
=
+
1000
01000010000010
00001
,1
)(
LL
MOMMMM
LL
LL
LL
MMMMOM
LL
nk
kk
k
l
lG ,
o sea que descompusimos A como A = LU donde U es triangular superior y
( ) ( ) ( )
===
1...01
0010001
1,21
2,11,1
211)1(1)2(1)1(1
nnnn
nn
n
lllll
l
L
MMOMM
L
L
L GGGGL es triangular inferior.
EjemploDel ejemplo anterior podemos verificar que:
=
80.10075.45.20124
12.025.00175.0001
311413124
En caso de usar pivoteo parcial, LU ser una permutacin de las filas de A, es decir PA = LU ,siendo P es una matriz de permutacin.
Obsrvese que cualquier algoritmo que permita descomponer A como PA = LU siendo P unamatriz de permutacin, L triangular inferior y U triangular superior, permite transformar elproblema Ax = b en
=
=
yUxPbLy
resolviendo Ly = Pb por sustitucin hacia delante para obtener y, y luego Ux = y por sustitucinhacia atrs para obtener x.Estos algoritmos de descomposicin triangular no son ms que variantes del mtodo deGauss en las que se reordenan las operaciones, por lo que sus caractersticas (existencia desoluciones, necesidad de pivoteo, etc.) son las mismas.La diferencia ms importante es que en el mtodo de Gauss las operaciones sobre el trminoindependiente se hacen simultneamente con la fase de eliminacin, mientras que en losmtodos de descomposicin primero se hace la descomposicin y luego se opera sobre eltrmino independiente para obtener y (que no es ms que el b modificado que se obtiene en lafase de eliminacin). Luego en ambos casos se pasa a la fase de sustitucin hacia atrs.
-
Sistemas de ecuaciones lineales 2-7
Esto hace que los mtodos de descomposicin sean adecuados para resolver sucesivamentevarios problemas con la misma matriz y diferentes trminos independientes, pues una vezhecha la descomposicin basta con repetir las fases de sustitucin hacia adelante y atrs paracada trmino independiente3.
Veremos mtodos sin pivoteo. Supondremos que A puede descomponerse como A=LU con Ltriangular inferior y U triangular superior, es decir
njiulan
kkjikij ,...,1,
1==
=
con
>=>=
jkuikl
kj
ik
00
por tanto si i = j +==
==
iiii
i
kkiik
i
kkjikii ululula
1
11
2-6
=
=
1
1
i
kkiikiiiiii ulaul
si i > j entonces +==
==
jjij
j
kkjik
j
kkjikij ululula
1
11
2-7jj
j
kkjikij
iju
ulal
=
=
1
1
y si i < j +==
==
ijii
i
kkjik
i
kkjikij ululula
1
11
2-8ii
i
kkjikij
ij l
ulau
=
=
1
1
Obsrvese que estas ecuaciones se pueden resolver directamente si se alterna la eleccin deelementos diagonales de L y de U que verifiquen 2-6, el clculo de las columnas de L segn2-7 de las filas de U segn 2-8.
Por supuesto, si para algn i el segundo miembro de 2-6 se anula, algn elemento diagonal deL o U deber ser nulo y el algoritmo no podr terminarse. En esos casos ser necesariorealizar pivoteo, lo cual complica bastante las cosas y no lo veremos.
3 esto es especialmente til para el mtodo de mejora de la solucin que se ve en 2.3.5
-
Sistemas de ecuaciones lineales 2-8
2.3.3.2 Mtodo de CroutEs el caso particular en el que los elementos diagonales de U se hacen valer 1.En este caso el algoritmo del mtodo puede escribirse como:
L(:,1)=A(:,1); % Primera columna de LU(1,:)=A(1,:)/L(1,1); % Primer fila de U
for j=2:nU(j,j)=1;for i=j:n
L(i,j)=A(i,j)-sum(L(i,1:j-1).*U(1:j-1,j)) ; %Calcula col. Lendfor i=j+1:n
U(j,i)=(A(i,j)-sum(L(j,1:j-1).*U(1:j-1,i)))/L(j,j); %Calc. fila Uend
end
y(1)=b(1)/L(1,1); %Comienza sustitucin hacia adelantefor i=2:n y(i)=(b(i)-sum(L(i,1:i-1).*y(1:i-1)))/L(i,i);end
x(n) = y(n)/U(n,n); %Comienza sustitucin hacia atrsfor i=n-1:-1:1 x(i)=(y(i)-sum(U(i,i+1:n).*x(i+1:n)));end
Ntese que cada elemento de A slo se usa para calcular4 un elemento de L o de U y no sevuelve a usar, por lo que podran almacenarse los elementos calculados en las mismasvariables que contenan los elementos de A. Esta tcnica reduce a la mitad la memorianecesaria.La cantidad de operaciones del mtodo de Crout es (4n3-3n2-n)/6 en la fase de descomposiciny 2n2-n en la fase de sustitucin, totalizando la misma cantidad que el mtodo de Gauss,
EjemploConsideremos el caso
=
=
21112
122321213
bA y
se obtiene la descomposicin
=
=
100110
3/23/11
13/4203/71003
UL y
y en la fase de sustitucin
=
=
213
234
xy y
4Basta con realizar las sumas con variables de doble precisin para minimizar los errores de redondeo, aunque luego elresultado se almacene en variables de simple precisin.
-
Sistemas de ecuaciones lineales 2-9
2.3.3.3 Mtodo de DoolitleEs muy similar al de Crout. En este caso son los elementos diagonales de L que se hacen valer1, dando exactamente el mismo resultado que la escalerizacin por el mtodo de Gauss.Este es el mtodo usado por Matlab en la funcin [L, U, P]=lu(A) , que realiza la descompsicinPA=LU siendo P una matriz de permutacin que corresponde al pivotaje.Usando esta funcin se puede resolver el sistema Ax=b mediante:
[L,U,P]=lu(A) % descompone Ay=L\(P*b) % resuelve sistema Lx=U\y % resuelve sistema U
2.3.3.4 Mtodo de CholeskyEn muchas aplicaciones se presentan sistemas en los que la matriz A es simtrica y definidapositiva. En estas condiciones puede demostrarse que A se puede descomponer como A= LLT.El mtodo de Cholesky resuelve este caso. Sabiendo que U = LT las ecuaciones quedan:
2-9 11
1
2,n,jlal
j
kjkjjjj ==
=
2-10,n,ji
,n,jl
llal
jj
j
kjkikij
ij+=
==
=
11
1
1
Y podemos escribir el siguiente algoritmo:
L(1,1)=sqrt(A(1,1));L(2:n,1)=A(2:n,1)/L(1,1); % Primera fila de L
for j=2:nL(j,j)=sqrt(A(j,j)- sum(L(j,1:j-1)^2); % Elemento diagonalfor i=j+1:n
L(i,j)=(A(i,j)-sum(L(i,1:j-1).*L(j,1:j-1))/L(j,j); %Calc. fila Lend
end
y(1)=b(1)/L(1,1); %Comienza sustitucin hacia adelantefor i=2:n y(i)=(b(i)-sum(L(i,1:i-1).*y(1:i-1)))/L(i,i);end
x(n) = y(n)/L(n,n); %Comienza sustitucin hacia atrsfor i=n-1:-1:1 x(i)=(y(i)-sum(L(i+1:n,i).*x(i+1:n)))/L(i,i);end
Ntese que adems de las ventajas del mtodo de Crout, en el de Cholesky se puedealmacenar slo media matriz A y en la misma memoria almacenar la L.La cantidad de operaciones del mtodo de Cholesky es (2n3+3n2-5n)/6 ms n races cuadradasen la fase de descomposicin y 2n2 operaciones en la fase de sustitucin.
EjemploSi aplicamos este mtodo al sistema del ejemplo de transmisin de calor,
-
Sistemas de ecuaciones lineales 2-10
=
=
1505050
10000
1505050
410100000141010000
014001000100410100
010141010001014001000100410000010141000001014
bA y
Se obtiene
=
8284.16014.00146.05430.00000008315.15679.01716.05418.00000009249.10519.01555.05176.00000008417.15833.00092.05175.00000008457.15546.0138.05164.00000009319.10345.01291.05.00000009322.15164.0000000009365.15.0000000002
L
=
=
8571.670000.501429.324286.710000.505714.288471.670000.501429.32
0744.1247673.504829.325489.845350.181678.102582.862749.320000.25
xy y
2.3.3.5 Aplicacin a matrices tridiagonalesLas matrices tridiagonales son en las que los nicos elementos no nulos son los de la diagonalprincipal y sus dos diagonales adyacentes. Son bastante frecuentes en sistemas lineales queaparecen en ciertos problemas de Ingeniera.Como los elementos alejados de la diagonal son nulos, las frmulas 2-6, 2-7 y 2-8 sesimplifican pues las sumatorias tienen slo uno o ningn sumando no nulo, quedando:
iiiiiiiiii ulaul ,11, =
-
Sistemas de ecuaciones lineales 2-11
101,1
1,1,
-
Sistemas de ecuaciones lineales 2-12
Esto se debe a que el problema es mal condicionado pues la matriz A es casi singular ycualquier vector que satisfaga una de las ecuaciones dar muy bajo residuo en la otra (que escasi un mltiplo de la anterior).Adicionalmente los problemas mal condicionados usualmente implican que se obtendrnelementos pivotes cercanos a cero por resta de nmeros casi iguales, lo cual produce erroresrelativos por redondeo muy importantes. Si bien esto puede postergarse mediante pivoteo, serinevitable que el ltimo elemento pivote sea cercano a cero y su error de redondeo sepropagar en la sustitucin hacia atrs.Es ms, el mtodo de Gauss con pivoteo dar casi siempre bajos residuos, ya que la matriz Utiene elementos diagonales (con la posible excepcin del ltimo) con valor absolutorelativamente grande (ya que para eso se hace el pivoteo), y al obtener x1, x2,,xn-1 porsustitucin hacia atrs, las ecuaciones correspondientes se satisfarn con un bajo residuo sinimportar lo exacto que sea xn.
2.3.4.2 Normas de vectores y matricesPara comparar el tamao de los errores y los residuos usaremos normas.En espacios vectoriales una norma es una funcin RE : tal que:
yx,yxyxxxx
0x0xx,0x
++=
==,
En espacios de matrices se pide tambin que la norma cumpla BA,BAAB .Si una norma de matrices y una de vectores cumplen que xA,xAAx , se diceque son consistentes.Para toda norma de vectores existe al menos una norma de matrices consistente con ella, asaber
Axx
AxA
10 ===
xxmaxmax
Tres casos muy usados de normas de vectores son:
=
=
n
iix
11x
=
=
n
iix
1
22
x (Norma Eucldea)
iimax xx =
y sus correspondientes normas matriciales son:
=
=
n
iijj
amax1
1A
12=A siendo 1 el mximo valor propio de ATA (Norma espectral)
=
=
n
jiji
amax1
A
-
Sistemas de ecuaciones lineales 2-13
2.3.4.3 Anlisis de perturbaciones5Trataremos de estimar el efecto que tiene una perturbacin en A o en b sobre el error de x.
Perturbacin en b:( ) ( ) ==+=+ bAxbxAbbx)A(x 1
2-11 bAx 1
por otro lado = xbbx
2-12b
x1
Combinando 2-11 y 2-12 se obtiene
2-13bb
Abb
AAx
x 1 =
)(
donde 1AAA )( es el nmero de condicin de A.El nmero de condicin de una matriz es siempre mayor o igual a la unidad. Si el nmero decondicin es grande se dice que el problema es mal condicionado.
Perturbacin en A:En forma similar se demuestra que si =++ bx)A)(x(A
2-14AA(A)
xx
x
+
Las desigualdades 2-13 y 2-14 nos dicen que para problemas mal condicionados, pequeoserrores en la matriz o el trmino independiente pueden causar grandes errores en la solucin,mientras que para problemas bien condicionados nos asegura buena precisin.
2.3.4.4 Errores de redondeoLas desigualdades 2-13 y 2-14 slo sirven para acotar la parte del error de la solucin debida aerrores en los valores de A o b, pero aunque A y b no tengan errores, debido a los errores deredondeo generados durante las operaciones aritmticas, o a errores de truncacin del mtodo,la solucin obtenida, x*, tendr error.Se define el residuo de x* como r=b-Ax*
===== rAxxAx*)-A(xAx*-AxAx*-br 1 )(2-15 rAx 1
y, combinando 2-15 y 2-12,
2-16br
Abr
AAx
x 1 )(=
Obsrvese que el error (x) que aparece en 2-16 es el error total de la solucin e incluyeerrores de cualquier fuente (errores de datos, redondeo, truncacin, fallos, etc.)La experiencia muestra que para mtodos directos y si no hay errores en A y b, en general
maqnbr
5 Este anlisis es vlido para cualquier par de normas vectorial y matricial consistentes, pero suele usarse la norma 1 o
la norma infinito por ser fciles de evaluar.
-
Sistemas de ecuaciones lineales 2-14
2-17 )(Ax
x maqn
6
La desigualdades 2-16 y 2-17 nos dicen que un residuo pequeo o un psilon de mquinapequeo no necesariamente implica que el error en la solucin sea pequeo para problemasmal condicionados, pero s para problemas bien condicionados.
El problema es que para calcular el nmero de condicin habra que invertir la matriz delsistema, lo cual tiene mucho costo de clculo. Ms adelante veremos cmo estimar el nmerode condicin.
2.3.5 Mejora de la solucin y estimacin del nmero de condicinVeremos una forma de estimar el nmero de condicin y de paso mejorar la solucin calculada.Una vez obtenida una solucin calculada x* podemos evaluar el residuo r=b-Ax* (esto debehacerse con aritmtica de alta precisin para evitar errores por resta de nmeros casi iguales) ya continuacin calcular el error resolviendo Ax=-r, lo cual no es muy costoso pues ya tenemosla descomposicin triangular de A y slo hay que hacer las sustituciones hacia adelante y haciaatrs.Una vez obtenido x podemos mejorar la solucin mediante x(2)=x*-x y adems estimar elnmero de condicin a partir de 2-16 segn
2-18 )2()( xx
r
bA
EjemploSe tiene el sistema
=
58.222.528.5
32.211.285.198.077.653.211.206.123.4
x
Usando aritmtica de tres dgitos con truncacin, se obtiene x*=(0.991, 0.997, 1.00)T.Si calculamos Ax* y el residuo con aritmtica de 6 cifras obtenemos
=
0103.000246.00349.0
59032.222246.524511.5
* rAx
donde expresamos r con 3 dgitos.Si ahora resolvemos Ax=-r del mismo modo que antes, obtenemos
==
=
00.1
00.1
999.0
*
00000757.0
00300.0
00822.0)2( xxxx y
y podemos estimar el nmero de condicin usando 2-18 .
24.100.1
00822.00349.0
28.5)( )2( == xx
r
bA
Con lo cual confirmamos que este problema es bien condicionado7.
6 Este resultado es aproximado y slo sirve para estimar el orden de magnitud del nmero de condicin.
7 El nmero de condicin verdadero es 17.6, algo mayor que el estimado.
-
Sistemas de ecuaciones lineales 2-15
2.3.6 Clculo de determinantesUn resultado adicional que se obtiene a partir de cualquiera de estos mtodos con muy bajoesfuerzo es el clculo del determinante de la matriz A.Si PA=LU entonces det(P).det(A)=det(L).det(U), lo cual permite calcular el determinante de A
como:
= ==
n
iii
n
iii ludet
11)(A
siendo el signo negativo si la cantidad de permutaciones de P es impar y positivo si es par.
2.4 Mtodos IterativosEstos mtodos parten de una primera solucin aproximada a la que se le hacen sucesivasmejoras hasta obtener una solucin con la precisin deseada.Suelen aplicarse a sistemas con matrices grandes y vacas, pues como estos mtodos nomodifican la matriz sino que trabajan siempre con la matriz original, aprovechan su condicinde vaca para almacenar slo los elementos no nulos y operar slo con ellosSe basan en convertir el problema Ax=b en uno equivalente de la forma x=f(x)=Tx+c tal que lafuncin f sea contractiva8.Partiendo de una aproximacin inicial x(0) se define la sucesin {x(k)} / x(k+1)=Tx(k)+c, queconverge al punto fijo de f , x* / f(x*)=x* y por tanto es solucin del problema.
2.4.1 Mtodo de JacobiSupongamos que los elementos diagonales de A son no nulos (o reordenemos las ecuacionespara que lo sean). Podemos despejar de cada ecuacin la variable correspondiente obteniendoel sistema equivalente
nia
xab
xii
n
ijj
jiji
i ,...,2,11
=
=
=
El mtodo de Jacobi consiste en calcular la sucesin de aproximaciones definida por
2-19 nia
xab
xii
n
ijj
kjiji
ki ,...,2,1
1
)(
)1(=
=
=
+
partiendo de una aproximacin inicial x(0) , que usualmente se toma como el vector nulo.Este mtodo tambin se llama de desplazamientos simultneos, pues los nuevos valorescalculados de cada componente de x desplazan a los anteriores todos simultneamente alterminar una iteracin.El error puede estimarse por la norma de la diferencia entre una aproximacin y la anterior.El algoritmo puede escribirse como sigue.
x(:)=zeros(n,1); % aproximacin inicialiter=1;error=tol+1;
while(error>tol & iter
-
Sistemas de ecuaciones lineales 2-16
error=norm(xnuevo(:)-x(:),inf); % estima erroriter=iter+1;x(:)=xnuevo(:); % desplazamiento
end
EjemploSe tiene el sistema
=+
=++
=+
1525272
1126
321
321
321
xxx
xxx
xxx
la iteracin de Jacobi queda
++=
+=
+=
+
+
+
)(2
)(1
)1(3
)(3
)(1
)1(2
)(3
)(2
)1(1
4000.02000.0200.02857.02857.07143.01667.03333.08333.1
kkk
kkk
kkk
xxx
xxx
xxx
Empezando con el vector nulo como aproximacin inicial se obtienen las aproximaciones quese muestran en Tabla 1
Iteracin 0 1 2 3 4 5x1 0 1.833 2.038 2.085 2.004 1.994x2 0 0.714 1.181 1.053 1.001 0.990x3 0 0.200 0.852 1.080 1.038 1.001
Tabla 1 Iteraciones por el mtodo de Jacobi
-
Sistemas de ecuaciones lineales 2-17
2.4.2 Mtodo de Gauss SeidelEn el mtodo de Jacobi nos abstenemos de usar los nuevos valores de cada componentehasta completar el clculo de todas ellas. Sin embargo parece razonable pensar que losnuevos valores sean ms exactos que los viejos y deberan usarse lo antes posible.Usando en 2-19 las componentes ya calculadas obtenemos el mtodo de Gauss Seidel
2-20 nia
xaxabx
ii
n
ij
kjij
i
j
kjiji
ki ,...,2,1
1
)(1
1
)1(
)1(=
=
+=
=
+
+
Este mtodo usualmente converge ms rpido que el de Jacobi.El algoritmo se puede escribir:
x(:)=zeros(n,1); % aproximacin inicialiter=1;error=tol+1;
while(error>tol & iter
-
Sistemas de ecuaciones lineales 2-18
con TGS = (L+D)-1U y cGS = (L+D)-1bPara que la funcin de la iteracin sea contractiva basta que la norma de la matriz Tcorrespondiente sea menor que uno.Si A es diagonalmente dominante por filas,
1
ii
ijij
iij ii
ijiJij
ijiia
a
maxa
amaxaa T
lo cual demuestra que el mtodo de Jacobi converge si A es diagonalmente dominante porfilas.
En el caso de Gauss Seidel, xTyy GS= /
y = (L+D)-1Ux -(L+D)y = Ux -Dy = Ux+Ly
sea = i
yi y/
+=
=
+=
=+=
=
+++==
n
ijij
i
jij
n
ijjij
i
jjij
n
ijjij
i
jjijiiiii aaxayaxayayaa
1
1
11
1
11
1
1xyy
ii
i
jij
iii
n
ijij
ii
iii
a
a
sya
a
rdondes
rsr
=+=
==
+
1
11
1xyyxy
Si A es diagonalmente dominante por filas, entonces
11
11
10