Gauss con pivoteo

1. TEMA 8 F. MATEM
¶
ATICOS.
TEMA 8
Sistemas de Ecuaciones Lineales: M¶etodo de Gauss.
1. Sistemas de ecuaciones lineales. Generalidades
Uno de los problemas centrales del ¶algebra lineal es la resoluci¶on de ecuaciones lineales simult¶aneas.
De¯nici¶on 1Un sistema de ecuaciones lineales, en concreto de m ecuaciones con n inc¶ognitas, es un
conjunto de m igualdades que se pueden escribir en la forma:
8
>
>
>
<
>
>
>
:
a11x1+a12x2+¢ ¢ ¢+a1nxn=b1
a21x1+a22x2+¢ ¢ ¢+a2nxn=b2
.
.
.
.
.
.
.
.
.
.
.
.
am1x1+am2x2+¢ ¢ ¢+amnxn=bm
(1)
Los n¶umerosaij2Rparai= 1;2;¢ ¢ ¢; m;j= 1;2;¢ ¢ ¢; nreciben el nombre de coe¯cientes y los
bi2Rparai= 1;2;¢ ¢ ¢; m;t¶erminos independientes
1
. Por ¶ultimo,x1; x2;¢ ¢ ¢; xnson las inc¶ognitas
del sistema.
En el caso particular de queb1=b2=¢ ¢ ¢=bm= 0 el sistema se denominahomog¶eneo.
De¯nici¶on 2Lamatriz del sistemadado (omatriz ampliada) es el conjunto formado por losm£
(n+ 1)n¶umeros que se obtiene al escribir los coe¯cientes y los t¶erminos independientes, ordenadamente
por ¯las y columnas, en la forma:
0
B
B
B
@
a11a12¢ ¢ ¢a1nb1
a21a22¢ ¢ ¢a2nb2
.
.
.
.
.
.
.
.
.
.
.
.
am1am2¢ ¢ ¢amnbm
1
C
C
C
A
Si quitamos la ¶ultima columna de los t¶erminos independientes, la matriz que nos queda recibe el
nombre dematriz de los coe¯cientesdel sistema.
Al ser m¶as c¶omodo trabajaremos solamente con la matriz del sistema, en lugar de hacerlo con todo
el sistema, pues con ello simpli¯ca ¶mos el proceso de resoluci¶on.
2. Soluci¶on de un sistema de ecuaciones. Sistemas equivalentes
De¯nici¶on 3Diremos que un conjunto de n n¶umeros ordenados(®1; ®2; ;¢ ¢ ¢; ®n)es una soluci¶on del
sistema (1) si satisfacen todas las ecuaciones del sistema.
De¯nici¶on 4Diremos que dos sistemas de ecuaciones sonequivalentessi tienen las mismas solu-
ciones.
1
En el caso de seraij2C, [1] puede transformarse en un sistema de coe¯cientes y t¶erminos independientes reales con
doble n¶umero de ecuaciones que el sistema inicial
I.T.I. MEC
¶
ANICA Curso 2006/07 1 FUNDAMENTOS MAT
¶
EMATICOS

2. TEMA 8 F. MATEM
¶
ATICOS.
Obs¶ervese que no necesariamente han de tener el mismo n¶umero de ecuaciones.
Es f¶acil comprobar que las siguientes transformaciones, que denominaremoselementales, efectuadas
sobre la matriz de un sistema nos conducen a otro sistema equivalente:
1.Fij: Intercambiar el orden de las ¯las i, j (equivale a cambiar el orden de dichas ecuaciones).
2.Fi(®) : Multiplicar la ¯la i por el escalar®6= 0 (equivalente a multiplicar la ecuaci¶on i-¶esima por
el escalar®no nulo).
3.Fij(®) : Sumar a la ¯la i la ¯la j multiplicada por el escalar®(equivalente a sumar a la ecuaci¶on
i-¶esima un m¶ultiplo de la ecuaci¶on j-¶esima).
Clasi¯caci¶on de un sistema de ecuaciones lineales
Atendiendo a la existencia o no de soluciones, los sistemas lineales se clasi¯can en:
Compatibles:si tienen al menos una soluci¶on.
Incompatibles:si no tienen soluci¶on.
A su vez los sistemas de ecuaciones lineales compatibles se clasi¯can, en funci¶on del n¶umero de
soluciones, en:
Determinados:si tienen una ¶unica soluci¶on.
Indeterminados:si tienen m¶as de una, en cuyo caso tendr¶an in¯nitas soluciones.
Notemos que los sistemas homog¶eneos tienen siempre, al menos, la soluci¶on (0;0;¢ ¢ ¢;0) que recibe
el nombre de soluci¶on trivial, por ello siempre son compatibles.
3. M¶etodo de eliminaci¶on de Gauss
Es un m¶etodo directo que nos da la soluci¶on exacta, si existe, en un n¶umero ¯nito de pasos u opera-
ciones.
Pretendemos resolver un sistema de ecuaciones lineales dado mediante su transformaci¶on en otro
sistema equivalente que se resuelva f¶acilmente. Dichos sistemas tienen una forma concreta.
De¯nici¶on 5Un sistema de ecuaciones lineales se denominaescalonado(oreducido) si la matriz
del sistema veri¯ca que:
1.Todos los elementos por debajo de losaiiparai= 1;2;¢ ¢ ¢; nson nulos.
2.El primer elemento no nulo de cada ¯la, llamadopivote, est¶a a la derecha del primer elemento
diferente de cero (pivote) de la ¯la anterior.
3.Cualquier ¯la formada ¶unicamente por ceros est¶a bajo todas las ¯las con elementos diferentes de
cero.
Para conseguir nuestro objetivo utilizaremos elm¶etodo de eliminaci¶on de Gaussque consiste en,
utilizando transformaciones elementales sobre la matriz del sistema, pasar de un sistema de ecuaciones
a otro equivalente que sea escalonado. Los sucesivos pasos de este proceso son:
I.T.I. MEC
¶
ANICA Curso 2006/07 2 FUNDAMENTOS MAT
¶
EMATICOS

3. TEMA 8 F. MATEM
¶
ATICOS.
3.1 Aplicaci¶on del m¶etodo de Gauss a la resoluci¶on de un sistema de ecuaciones lineales con o sin
par¶ametros
1.Localizamos en la primera columna no nula, de la matriz del sistema, el primer elemento no nulo
a.
2. Intercambiamos la primera ¯la con la ¯la en la que se encuentraa.
3.Multiplicamos la primera ¯la pora
¡1
.
4.Sumando m¶ultiplos adecuados de la primera ¯la a las dem¶as, anulamos todos los elementos de la
primera columna no nula menos el primero.
5.Repetimos el proceso, con la matriz que resulta de eliminar la primera ¯la y la primera columna,
hasta conseguir un sistema escalonado.
En algunos casos podemos ahorrarnos c¶alculos no siguiendo a rajatabla los pasos del proceso explicado.
Por ejemplo, si en la primera columna no nula hay ununoconviene, en el primer paso, tomaracomo
dicho elemento, pues as¶³ nos ahorraremos el paso tercero. Esto nos permite a¯rmar que dado un sistema,
el sistema escalonado obtenido a partir de ¶el no es ¶unico, aunque si hay ciertas caracter¶³sticas que son
comunes a todos ellos, a saber:
-El n¶umero de ¯las no nulas (n¶umero de ecuaciones independientes que tiene el sistema) que coincide
con el n¶umero de pivotes.
-El pivote de cada ¯la est¶a situado siempre en la misma columna.
Finalmente, una vez obtenido el sistema escalonado, lo resolvemos por sustituci¶on regresiva.
3.1. Aplicaci¶on del m¶etodo de Gauss a la resoluci¶on de un sistema de ecua-
ciones lineales con o sin par¶ametros
Estudiamos la eliminaci¶on gaussiana como un m¶etodo para la manipulaci¶on de sistemas de ecuaciones
con el ¯n de obtener un sistema escalonado cuya resoluci¶on fuese m¶as c¶omoda.
Nuestro objetivo ahora, es dar criterios generales que nos faciliten la resoluci¶on del sistema escalonado
obtenido y, en consecuencia, del sistema inicialmente planteado (1).
Para ello dividimos las inc¶ognitas de nuestro sistemax1; x2;¢ ¢ ¢xnen dos grupos, aquellas que corre-
sponden a columnas con pivotes, que llamaremosinc¶ognitas b¶asicasy las restantes, correspondientes
a las columnas sin pivotes, que llamaremosinc¶ognitas libres. Al n¶umero de inc¶ognitas libres se le
denomina n¶umero degrados de libertaddel sistema.
En el sistema escalonado puede ocurrir entonces lo siguiente:
1.Aparece una ¯la al menos, en la matriz del sistema, que tiene todos los elementos nulos salvo el
¶ultimo (es decir hay alguna ecuaci¶on de la forma 0 =bconb6= 0 ). En dicho caso el sistema
escalonado y por tanto el inicial (1) es incompatible.
2.En caso contrario el sistema (1) es compatible.
a)Si el n¶umero de pivotes coincide con el de inc¶ognitas, es decir, no hay inc¶ognitas libres, el
sistema tiene soluci¶on ¶unica. La soluci¶on se obtiene por sustituci¶on regresiva empezando por
la ¶ultima ecuaci¶on hasta llegar a la primera (determinado).
b)Si el n¶umero de pivotes es menor que el de inc¶ognitas, es decir, hay inc¶ognitas libres, el sistema
tiene in¯nitas soluciones (indeterminado). En este caso las soluciones se obtienen dando valores
arbitrarios a las inc¶ognitas libres y poniendo las inc¶ognitas b¶asicas, por sustituci¶on regresiva,
en funci¶on de dichos valores arbitrarios.
I.T.I. MEC
¶
ANICA Curso 2006/07 3 FUNDAMENTOS MAT
¶
EMATICOS

4. TEMA 8 F. MATEM
¶
ATICOS.
A veces aparecen sistemas de ecuaciones en los cuales ciertos coe¯cientes o t¶erminos independientes no
tienen un valor ¯jo predeterminado, sino que son par¶ametros, y se nos pide estudiar el sistema para todos
los valores posibles de dichos par¶ametros (discutir el sistema). Pues bien, en dichos casos, aplicamos
tambi¶en la t¶ecnica de eliminaci¶on gaussiana para clasi¯car estos sistemas atendiendo a los distintos
valores de los par¶ametros.
M¶etodo de Gauss con pivoteo parcial y total
Cuando un proceso matem¶atico no est¶a de¯nido para un valor particular de un par¶ametro, es muy
posible que el proceso funcione num¶ericamente mal cerca de ese valor. El siguiente ejemplo ilustra las
consecuencias de operar con un pivote peque~no.
Ejemplo. Por eliminaci¶on gaussiana y trabajando con dos y cuatro cifras respectivamente, resolver el
sistema de ecuaciones: ½
0;0001x+y= 1
x+y= 2
Este ejemplo prueba que la aparici¶on de un pivote peque~no puede ser el anuncio de un desastre com-
putacional. Por ello debemos modi¯car el m¶etodo de eliminaci¶on de Gauss para evitar pivotes peque~nos
intercambiando las ¯las y las columnas de la matrizA. Concretamente:
Eliminaci¶on gaussiana con pivoteo total. Si en la etapa r-¶esima del proceso de eliminaci¶on el
pivotearres demasiado peque~no, elegimos el elementoapq=maxfjaijj= i; j¸rgcomo nuevo pivote.
Para ello intercambiamos las ¯lasrypy las columnasryqde forma que situamos el elementoapq
en la posici¶on (r,r). Obviamente hemos tomadoi; j¸rpara no perturbar los ceros que ya ten¶³amos.
Posteriormente continuamos la eliminaci¶on con el nuevo pivote.
Eliminaci¶on gaussiana con pivote parcial. En este caso la alternativa consiste en buscar sola-
mente en la r-¶esima columna; es decir, tomar
apr=maxfjairj= i¸rgcomo nuevo pivote. Para ello intercambiamos las ¯lasryp, continuando
posteriormente el proceso de eliminaci¶on.
En la pr¶actica, el m¶etodo de Gauss con pivoteo total puede consumir mucho tiempo, computacional-
mente hablando, pues para hallar el m¶aximo en cada paso hay que buscar entre (m¡r+ 1)¢(n¡r+ 1)
elementos.
En el otro caso, adem¶as del ahorro de tiempo, las inc¶ognitas de nuestro sistema no cambian de orden
en el sistema reducido. Por ello, en general, es su¯ciente utilizar un pivoteo parcial.
4. Factorizaci¶on L.U de una matriz
Teorema 1 (Descomposici¶on L.U)Toda matrizA2Mm£n(K), siempre que no sea necesario re-
alizar un intercambio de ¯las, se puede descomponer en la formaA=L:UconL2Mm(K) triangular
inferior con unos en la diagonal yU2Mm£n(K) triangular superior.
Para el casom < n, supuesto que ¶unicamente utilicemos la transformaci¶onFij(®), ser¶³a:
0
B
@
a11¢ ¢ ¢a1m¢ ¢ ¢a1n
.
.
.
.
.
.
.
.
.
.
.
.
am1¢ ¢ ¢amm¢ ¢ ¢amn
1
C
A=
0
B
B
B
@
1 0 ¢ ¢ ¢0
l211¢ ¢ ¢0
.
.
.
.
.
.
.
.
.
.
.
.
lm1lm2¢ ¢ ¢1
1
C
C
C
A
:
0
B
B
B
@
p11u12¢ ¢ ¢u1m¢ ¢ ¢u1n
0p22¢ ¢ ¢u2m¢ ¢ ¢u2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ¢ ¢ ¢pmm¢ ¢ ¢umn
1
C
C
C
A
I.T.I. MEC
¶
ANICA Curso 2006/07 4 FUNDAMENTOS MAT
¶
EMATICOS

5. TEMA 8 F. MATEM
¶
ATICOS.
Donde:
La matrizUes la matriz escalonada resultado de aplicar a la matrizAlas trasformaciones elemen-
tales por ¯las del tipoFij(®) .
los elementospijde la diagonal deU, son los pivotes de la matrizA.
El elementolij; i > jde la matrizLes exactamente el valor®cambiado de signo que aparece en
la transformaci¶on elementalFij(®) que se aplic¶o aApara obtener la matrizU.
Ejercicios
1.Resolver, cuando sea posible, los sistemas:
a)
8
<
:
x1+x2+x3= 0
¡2x1+3x2¡x3=¡4
3x1¡2x2+x3= 2
b)
8
>
>
<
>
>
:
x1+x2¡x3+x4+x5= 2
x1¡2x2 +x4 = 5
¡x1 +x3 +2x5= 3
3x2+x3¡2x4 =¡1
c)
8
<
:
x1+x2+2x3= 0
3x1¡x2¡2x3= 0
¡x1¡2x2+x3= 0
d)
8
>
>
<
>
>
:
x1+x2¡x3¡2x4+3x5= 0
¡x1+2x2+2x3+3x4¡2x5= 0
2x1¡x2¡x3+x4+x5= 0
2x1+2x2¡2x3¡x4¡2x5= 0
e)
8
>
>
<
>
>
:
x1+2x2¡3x3= 0
¡2x1 ¡x3=¡3
¡x1+x2 = 0
¡2x2+4x3= 4
2.Utilizando el m¶etodo de Gauss, estudiar los sistemas seg¶un los par¶ametros y resolverlos cuando sea
posible:
a)
8
<
:
mx1 ¡x2+x3= 2x1
x1+2mx2¡mx3=x2
x1+mx2¡x3= 0
b)
8
<
:
x1+ax2+x3= a+ 2
x1+x2+ax3=¡2a¡2
ax1+x2+x3= a
c)
8
<
:
2x1+x2= a
4x1+2x2= 1 +b
5x1+3x2= 2
d)
8
<
:
x1+ax2+a
2
x3= 1
x1+ax2+abx3= a
bx1+ax2+a
2
bx3=a
2
b
e)
8
<
:
(a+ 1)x1 +x2 +x3= 1
x1+(a+ 1)x2 +x3=b
x1 +x2+(a+ 1)x3=b
2
3.Dado los siguientes sistemas estudiarlos seg¶un los diferentes valores de los par¶ametros:
a)
8
<
:
(1 +a)x+y+z= 3 +b
¡ax +y+z= b
x +ay+z= 0
b)
8
<
:
(1 +a)x+y¡z= 1 +b
(2 +a)x¡y+ 3z=¡1
3x+ay+ 2z= 1¡b
c)
8
<
:
(3u¡4)x+ 2(u¡1)y+ (3u¡4)z= 1
ux+uy+uz= (u¡1)
2
2(u¡1)x+ 2(u¡1)y+ (3u¡4)z=u¡1
d)
8
<
:
(1 +a)x+y +z= 1 +b
¡2x +2y +z=¡2
ax (4¡a)y+3z= 1 +b
e)
8
>
>
<
>
>
:
(1 +a)x+y+z= 3 +b
¡ax +y+z= b
x ¡2y+z= ¡4
x +ay+z= 0
I.T.I. MEC
¶
ANICA Curso 2006/07 5 FUNDAMENTOS MAT
¶
EMATICOS

6. TEMA 8 F. MATEM
¶
ATICOS.
4. Una industria utiliza tres m¶aquinas en la elaboraci¶on de cuatro productos diferentes. Las m¶aquinas
se utilizan a pleno rendimiento 8 horas al d¶³a. El n¶umero de horas que cada m¶aquina necesita para
elaborar una unidad de cada producto es:
Producto 1 Producto 2 Producto 3 Producto 4
M¶aquina 1 1 2 1 2
M¶aquina 2 2 0 1 1
M¶aquina 3 1 2 3 0
>Cu¶al es el n¶umero de unidades de cada producto que elaborar¶a la industria en un d¶³a?
5.Tres productosX; YyZ, tienen los siguientes porcentajes deF e,ZnyCu:
Fe Zn Cu
X50 30 20
Y40 30 30
Z30 70 0
>Cu¶anto de cada producto debe combinarse para obtener un nuevo producto que contenga 44 % de
F e, 38 % deZny 18 % deCu?
6.Consideremos la siguiente red de calles de una direcci¶on:
¾ ¾ ¾ ¾
- - - -
?
6
?
?
6
?
?
6
?
400 x6 x7 450
500 x1 x2 600
350 600 400
x3 x4 x5
300 200 100
F E D
A B C
Los n¶umeros indican la cantidad de coches/hora que pasan por ese punto. Las variablesx1; x2; : : : ; x7,
representan el n¶umero de coches/hora que pasan de la intersecci¶onAa laB, de laBa laC, etc.
Suponiendo que en las calles est¶a prohibido aparcar, >qu¶e valores tomar¶an las variablesx1; x2; : : : ; x7
en los siguientes casos?
a)Hay obras en la calle deDaEy por tanto queremos que en ese tramo el tr¶a¯co sea m¶³nimo.
b)An¶alogamente, hay obras en la calle deDaF.
7.En una red telef¶onica como la de la ¯gura las centralesA; B;yCse encargan de distribuir las
llamadas a la centralD. Los n¶umeros que aparecen en la ¯gura son las llamadas/hora que entran
o salen de las centralesA; B; CyD.
I.T.I. MEC
¶
ANICA Curso 2006/07 6 FUNDAMENTOS MAT
¶
EMATICOS

7. TEMA 8 F. MATEM
¶
ATICOS.
-
?
-
?
¡
¡
¡
¡
¡
¡µ
@
@
@
@
@
@R
¡
¡
¡
¡
¡
¡ª
@
@
@
@
@
@R
@
@
@
@
@
@
@
@
@
@
@
@R
@
@
@
@
@
@R
C D
A B
x5
x4
x3
x1 x2
®
150 850
250
a)Hallar el valor de®que hace que sea posible la distribuci¶on de llamadas.
b)Para dicho valor de®, hallar el n¶umero de llamadas por cada tramo, si por una aver¶³a en la
l¶³nea, se quiere que en el tramoBDel tr¶ansito sea m¶³nimo.
8.Hallar la factorizaci¶onL¢Ude las siguientes matrices:
A=
0
@
1 2 0
0 1 0
2 1¡1
1
A B=
0
@
6 1 4
0¡1 0
2 0 2
1
A C=
0
@
1 1 0 0
0 1 1 0
1 0 0 1
1
A
9.Calcular cuando sea posible, por el m¶etodo de Gauss-Jordan, la inversa de las matrices del ejercicio
anterior.
10.Resolver mediante factorizaci¶onLUel sistema
8
<
:
2x+y+z= 1
3x¡y+ 4z= 0
x+y+z=¡2
11.Dado el sistema de ecuaciones
8
<
:
ax+by+z= 1
x+aby+z=b
x+by+az= 1
. Se pide:
a)Discutirlo seg¶un los valores deayb.
b)Paraa= 2 yb= 1, hallarA
¡1
por el m¶etodo de Gauss-Jordan dondeAes la matriz de los
coe¯cientes.
c)>Para qu¶e valores deaybadmite descomposici¶onLUla matriz de los coe¯cientes ? Calcular
dicha descomposici¶on para dichos valores.
12.Resolver utilizando el m¶etodo de factorizaci¶onLUlos sistemas:
a)
8
<
:
4x¡2y¡2z= 0
¡2x+2y = 1
¡2x +9z= 0
b)
8
>
>
<
>
>
:
x¡y+z = 4
¡x+2y¡z+2t=¡3
x¡y+5z+2t= 16
2y+2z+6t= 8
I.T.I. MEC
¶
ANICA Curso 2006/07 7 FUNDAMENTOS MAT
¶
EMATICOS