Algebra lineal y Sus aplicaciones cuarta edicién Gilbert Strang Massachusetts Institute of Technology Revisi6n técnica: Edmundo Palacios Pastrana Universidad Iberoamericana UTN - FRCU Dpto. Biblioteca ‘Algebra lineal y sus aplicaciones HAN RAARE E 11736 THOMSON —+*—___. Australia + Brasil » Canada + Espafia « Estados Unidos « México * Reino Unido SingapurPreakdente de Thomson Learning \beroamarioa: Javier Arellano Gulérrez Director editorial tberoamérica: José Tomas Pérez Bonila Gerente editorial y de producelén: Ulla Moreno Olvera Editor de doserrolto: Podro de la Garza Rosales COPYRIGHT © 2007 por Intemational Tomson Editores, S.A. 60 C.V,, una division de Thomson Leaming, inc. ‘Thomson Leaming™ es une marca registrada usadia bajo permiso. Impreso en México Printed in Mexico 123.4.0908 07 06 Para mayor informacién ccontdctencs ent Corporativo Santa Fe ‘Av. Santa Fo, aim. 508, pico 12, (Col, Cruz Manea, Sants Fe CP. 05849, Delegacién Cusiimalpa México, 0. F. Pade visiter nuestro sito on bitpu/wwwthomson.com.rmx México y América Central THOMSON —+ Aigebra tineal y aus splicactones, 4a. 4. Giver Strang Coordinador de manutactura: larael Robles Martinez Editora de produceién: ‘Abril Voga Orozco Diseto de portada: Grupo Insigne O.TA., S.A, de CY. DERECHOS RESERVADOS. ‘Queda prohibida la reproduccion © transmision total 0 parcial del texto de la presente cbra bajo ualesquiera formas, slectrénica ‘9 mecdiica, incluyendo fotocopiado, ‘imacenamiento on algin sistema do recuperacién de informacion, 0 ‘grabado aln al coneetimionto previo Y Por eserto del ecto, Divieién beroamertcana ‘Huge vilagémez Composicién tipogrifies: Juan Castro (TROGAS) Lectores ortotipogriticos: David Garcia Vazquez Felipe Martinez Martinez Traducido del loro Linear Algebra and its Appfcations, 4th. publcado ‘en inglés por Brooks Cole, © 2006 ISBN 0-09-010567-6 ‘Datos para catalogacién biblogrifica: ‘Strang, Gilbert. Algebra fineal y ‘us aplicaciones, 4a. 6d. (SBN 070-696-600-4 Contenido: 1. Maticas y ellminacién gsussiana, 2. Espacios vectoralee, 2. Orogonallded. 4. Determinantes. 5. Valores carscteristicos y vectores caracterticos. 6. Matrices positives defnidas. . Céloulos con matrices. 8, Programacién lineal y teora de juegos. ‘Thomson Laaming. Corporative Santa Fo ‘Av. Santa Fe, nd. 805, piso 12 Cot Cruz Manca, Santa Fe (C-P 05349, Delegacién Cusjimaipa Maxico, OF Tol. (52-55) 1500 6000 Fax (62-58) 1500 6019 ‘edtor@ thomsoaleaming.com.me £1 Caribe ‘Thomson Leaming Metro Oftes Park'3 Suite 201 St. 1 Lota Guaynabo, Puerte Roo Zp Code: 00968-1705, Toh. (707) G41 N12 Fox (787) 641 1119 ‘Cone Sur Buenos Alres, Argentina thomson@ thomeonleaming.com ar ‘28018 Mada Espana ‘ol. 4 (0) 91 446 3350, Fax 34 (0) 91 445 6218 lentes @ paraninio.esOB abla te contenido... UNIVER ICA HACIONAL NCHAL 293 Ing. PEREVAA Sis sceecion DEL URUGUAY ENTRE RIGS = AEP ARGENTINA ——.- Votap as. Gee Se re6” HE Capitulo 1 MATRICES Y ELIMINACIGN GAUSSIANA = 1 1.1. Introducci6n 1 1.2 Geometria de las ecuaciones lineales 3 1.3 Un ejemplo de eliminacién gaussiana 11 1.4 Notacién matricial y multiplicacién de matrices 19 1.5. Factores triangulares e intercambios de renglones 32 1.6 Inversas y traspuestas 45 1.7. Matrices especiales y aplicaciones 58 Ejercicios de repaso 65 HE Capitulo 2 ESPACIOS VECTORIALES 69 2.1 Espacios y subespacios vectoriales 69 2.2 Cémo resolver Ax =OyAx=b 77 2.3. Independencia lineal, base y dimensién 92 2.4 Los cuatro subespacios fundamentales 102 2.5 Gréficas y redes 114 2.6 Transformaciones lineales 125 Ejercicios de repaso. 137 EE Capitulo 3 ORTOGONALIDAD 141 3.1 Vectores y subespacios ortogonales 141 3.2 Cosenos y proyecciones sobre rectas 152 3.3. Proyecciones y mfnimos cuadrados 160 3.4 Bases ortogonales y Gram-Schmidt 174 3.5 La transformada discreta de Fourier 188 Ejercicios de repaso 198 EE Capitulo 4 DETERMINANTES 201 4.1 Introduccién 201 4.2, Propiedades del determinante 203 4.3. Formulas para el determinante 210 4.4 Aplicaciones de los determinantes 220 Ejercicios de repaso 230iv * Tabla de contenido ME Capitulo 5 VALORES CARACTERISTICOS Y VECTORES CARACTERISTICOS 233 5.1 Introduccién 233 5.2 Diagonalizacion de una matriz 245 5.3 Ecuaciones en diferencias y potencias AX 254 5.4 Ecuaciones diferenciales ye’ 266 5.5 Matrices complejas 280 5.6 Transformaciones de semejanza 293 Ejercicios de repaso 307 ME Capitulo 6 MATRICES POSITIVAS DEFINIDAS 311 6.1 Minimos, méximos y puntos silla 311 6.2 Pruebas para comprobar si una matriz es positiva definida 318 6.3 Descomposicién del valor singular 331 6.4 Principios minimales 339 6.5 El método del elemento finito 346 EE Capitulo 7 CALCULOS CON MATRICES 351 7A Introduccién 351 7.2, Norma de una matriz y némero de condicién 352 7.3, Célculo de valores caracteristicos 359 7.4 Métodos iterativos para Ax = b 367 HE Capitulo 8 PROGRAMACION LINEAL Y TEORIA DE JUEGOS 377 8.1 Desigualdades lineales 377 8.2 El método simplex 382 8.3 El problema dual 392 8.4 Modelos de redes 401 8.5 Teorfa de juegos 408 ME Apéndice A INTERSECCION, SUMAY PRODUCTO DE ESPACIOS © 415 ME Apéndice8 + LAFORMADE JORDAN 422 Soluciones a ejercicios seleccionados 428 Factorizaciones matriciales 474 Glosario: Un diccionario de digebra lineal 476 Cédigos de ensefanza MATLAB 481 Indice 482 Algebra lineal en pocas palabras 488Prefacio.. La revisiOn de este libro de texto ha sido un desafio especial por una razén bastante agra- dable. Mucha gente ha lefdo este libro, ensefiado a partir de 1 e ificlusive 1o ha querido. Quizé el espirita del libro no cambie jamés. Este texto fue escrito como ayuda para que nuestra ensefianza del Algebra lineal mantenga la importancia crucial de este tema, que si- gue creciendo. Ciertamente, un paso era posible y aconsejable: aadir nuevos problemas. Tantos afios de ensefianza requirieron cientos de reactivos de examen nuevos (especialmente con inte- rrogantes que impliquen el uso de la red). Considero que el lector aprobaré la amplia gama de problemas. Los reactivos siguen siendo una mezcla de explicacién y cdlculo: los dos métodos complementarios para aprender este hermoso tema. Personalmente considero que mucha més gente necesita algebra lineal que célculo. {Isaac Newton podria no estar de acuerdo! Sin embargo, 1 no estd ensefiando mateméticas en el siglo 204 (y quiz4 no fue un gran profesor, aunque le otorgaremos el beneficio de 1a duda). Ciertamente, las leyes de la Fisica se expresan bien mediante ecuaciones diferencia- les. Newton requirié del célculo, lo cual esté bien, Pero el alcance de la ciencia, la ingenie- ra y la administracién (asf como de la vida) actualmente es mucho més grande, y el dlgebra lineal se ha desplazado a un sitio nodal. Podrfa decir algo més, ya que muchas universidades atin no ajustan el equilibrio hacia el Algebra lineal. Al trabajar con lineas curvas y superficies curvas, el primer paso siempre es linealizar. Sustituir la curva por su recta tangente, ajustar la superficie por un plano y entonces el problema se vuelve lineal. El poder de este tema se hace evidente cuando se tienen 10 variables, 0 1000, en vez de dos. ‘Quizé el lector piense que estoy exagerando cuando uso la palabra “hermoso” para un. curso bésico de mateméticas. En absoluto. Este curso empieza con dos vectores v y w que apuntan en direcciones distintas. El paso clave es tomar sus combinaciones lineales. Se mi!- tiplica para obtener 3u y 4w, y se suma para obtener una combinacién particular 3u + 4w. Este nuevo vector esté en el mismo plano que v y w. Cuando se toman todas las combina- ciones, se est enando todo el plano. Si v y w se dibujan en esta pégina, sus combinacio- nes cv + dw Henan la pagina (y més all4), pero no salen de la pagina. En el lenguaje de las ecuaciones lineales, cu + dw = b puede resolverse exactamen- te cuando el vector b estd en el mismo plano que v y w. Matrices Se avanzar4 un poco més para convertir combinaciones de vectores tridimensionales al Algebra lineal. Si los vectores son v = (1,2, 3) y w = (1, 3, 4), se escriben en una matriz columna: ane nuePracio Para encontrar combinaciones de estas columnas, la matriz se “multipliea” por un vector fd 1 1p. ¥ 1 Combinaciones linealescv + dw |2 3 (4 =c|2] +a 3]. 3 4 Estas combinaciones llenan un espacio vectorial, denominado espacio columna de la ma- ttiz. (Para estas dos columnas, dicho espacio es un plano.) Para decidir si b = (2, 5. 7) es- td en ese plano, se cuenta con tres componentes para lograrlo. Asf, hay que resolver tres ecuaciones: fa 2, c+ d=2 23 (il = |5] significa 2¢+3¢ =5 34 7 Be + 4d ‘Se deja que el lector las resuelva. El vector b = (2, 5, 7) no esté en el plano de vy w. Si el 7 se cambia por cualquier otro némero, entonces b no esté en el plano; de hecho, no ninguna combinacién de v y w, por lo que las tres ecuaciones no tienen solucién. ‘Ahora es posible describir la primera parte del libro, sobre ecuaciones lineales Ax = b. La matriz A tiene n columnas y m renglones. El digebra lineal se desplaza de manera continua hacia n vectores en el espacio m-dimensional. Siguen buscéndose combinaciones de las columnas (en el espacio columna). Siguen obteniéndose m ecuaciones para producir (una por cada renglén). Estas ecuaciones pueden o no tener una solucién. Siempre tienen una solucién por minimos cuadrados. La interacci6n de las columnas y los renglones constituye el nticleo del élgebra lineal, Noes totalmente fécil comprenderlo, aunque tampoco es tan dificil. A continuacién se enu- ‘meran cuatro de los conceptos més importantes: 1. Elespacto columna (todas las combinaciones de las columnas). 2, El espacto renglén (todas las combinaciones de los renglones). 3. El rango (el ntimero de columnas independientes) (0 renglones). 4. Eliminacién (la forma idénea para encontrar el rango de una matriz). YY aqui me detengo para permitirle iniciar el curso. Paginas web Quizé sea titil mencionar las paginas de la red conectadas con este libro. Recibimos muchos mensajes con sugerencias y palabras de aliento, por lo que espero que el lector utilice todo con libertad. Puede acceder directamente a Attp://web.rmit.ediu/18.06, que se ac- tualiza constantemente para el curso que se imparte cada semestre. Algebra lineal también esté en el sitio del MIT OpenCourseWare http://ocw.mit.edu, donde 18.06 se volvié excep- ional al incluir videos de las conferencias (que, por supuesto, usted no tiene que ver...) ‘A ccontinuacién se menciona una parte del material disponible en la red: 1. Programa de conferencias y tareas y exAmenes actuales con soluciones. 2. Los objetivos del curso, asf como preguntas conceptuales. 3. Demos interactivos Java (ahora ya se cuenta con audio para los valores caracteristi- 08). 4, Cédigos de ensefianza del Algebra lineal y problemas MATLAB. 5. Videos de todo el curso (tal y como se ensefia.en un aula real). La pégina del curso se ha convertido en un vinculo valioso para la clase y un recurso para los estudiantes. Estoy bastante optimista sobre el potencial de las gréficas sonoras. El an-Prefacio. vii cho de banda para la voz en off es bajo, y FlashPlayer estd disponible de manera gratuita. Esto ofrece un repaso répido (con experimentos activos), y es posible bajar todas las con- ferencias. Espero que los profesores y estudiantes de todo el mundo encuentren titiles es- tas paginas web. Mi objetivo es hacer este libro lo més til posible con todo el material del curso que puedo proporcionar. Nota importante: La administracién de estas paginas Web y de otras mencionadas dentro del libro no esté a cargo de Thomson Learning Iberoamérica, por lo que la editorial no es responsable de las modificaciones en el contenido y los cambios en las politicas y formas de acceso que pudieran ocurrir. Le recomendamos visitar frecuentemente estos sitios a fin de estar al tanto de cualquier actualizacién. Complementos Este libro cuenta con complementos para el profesor, los cuales estn en inglés y s6lo se proporcionan a los docentes que adopten la presente obra como texto para sus cursos. Pa- ra mayor informacién, favor de comunicarse con las oficinas de nuestros representantes 0 a los siguientes correos electrénicos: Thomson México y Centroamérica clientes @thomsonlearning.com.mx. ‘Thomson América de! Sur cliente @thomsonlearning.com Thomson Caribe [email protected] Estructura del curso Los dos problemas fundamentales son Ax = b y Ax = Ax para matrices cuadradas A. El primer problema Ax = b tiene una solucién cuando las columnas de A son independientes. El segundo problema Ax = Ax es para vectores caracteristicos independientes. Una parte crucial de este curso es aprender el significado de “independencia Considero que !a mayorfa de nosotros aprendemos primero a partir de ejemplos. Pue- de ver que 112 af 2 |] no tiene columnas independientes. 13 4 La columna 1 més la columna 2 es igual a la columna 3. Un teorema maravilloso del dige- bra establece que los tres renglones tampoco son independientes. El tercer renglén debe estar en el mismo plano que los dos primeros renglones. Con alguna combinacién de los renglones | y 2 se obtiene el renglén 3. Quizé el lector pueda encontrar répidamente esta. combinacién (yo no pude). Al final nuve que usar eliminacién para descubrir que la com- binacién correcta utiliza 2 veces el renglén 2, menos el renglén 1. La.eliminacién es la forma simple y natural para entender una matriz al producir bastan- tes elementos iguales a cero. Por tanto, el curso empieza aqui. ;Pero no se quede demasiado aqui! El lector debe proceder de combinaciones de los renglones a independencia de los. renglones a la “dimensi6n del espacio renglén”. Este es el objetivo clave, abordar todos los espacios de los vectores: el espacio renglén, el espacio columna y el espacio nulo. ‘Otro objetivo es comprender la manera en que actiia la matriz. Cuando A se multipli- ca por x se obtiene el auevo vector Ax. Todo el espacio de vectores se mueve; es “transfor- mado” por A. Transformaciones especiales se obtienen de matrices particulares, y aquéllas son las primeras piedras del lgebra lineal: matrices diagonales, matrices ortogonales, ma- trices triangulares, matrices simétricas.vil ayia 1 Maices.y eliminacion goussiana Los valores caracteristicos de estas matrices también son importantes. Considero que Jas matrices de 2 por 2 constituyen ejemplos contundentes de la informacién que pueden proporcionar los valores caracteristicos 2. Las secciones 5.1 y 5.2 ameritan una lectura cui- dadosa para ver la manera en que Ax = Ax es de utilidad. Ahf se presenta un caso en que matrices pequefias permiten la obtencién de muchfsimo conocimiento, En forma global, la belleza del Algebra lineal puede apreciarse de varias maneras: 1. Visualizacién, Combinaci6n de vectores. Espacios de vectores. Rotacién, reflexién y proyeccién de vectores. Vectores perpendiculares. Cuatro subespacios fundamentals. 2. Abstraccién. Independencia de vectores. Base y dimensién de un espacio vectorial. ‘Transformaciones lineales. Descomposicién del valor singular y la mejor base. 3. Céleulo. Eliminacién para producir elementos cero. Gram-Schmidt para producir vectores ortogonales. Valores caracteristicos para resolver ecuaciones diferenciales y en di- ferencias. 4, Aplicaciones. Solucién por minimos cuadrados cuando Ax = 6 tiene demasiadas ecuaciones. Ecuaciones en diferencias que aproximan ecuaciones diferenciales. Matrices de probabilidad de Markov (jla base para Google!). Vectores caracterfsticos ortogonales como ejes principales (y més... .). Para continuar con estas aplicaciones, se mencionan los libros publicados por Welles- ley-Cambridge Press. Todos aparentan ser de algebra, aplicados al procesamiento de seiia~ les, a ecuaciones diferenciales parciales y a célculos cientificos (e inclusive GPS: Sistema de Posicionamiento Global). Si el lector consulta la pagina http:/www.wellesleycambride. ‘com, vers parte de la raz6n por la que el Algebra lineal es tan utilizada. Después de este prefacio, el libro hablaré por sf mismo. De inmediato observaré el es- piritu. El énfasis se pone en la comprensi6n: intento explicar, mds que deducir. Este ¢s un libro sobre matemsticas verdaderas, no un ejercicio interminable. En clase, constantemen- te trabajo con ejemplos para ensefiar lo que necesitan los estudiantes. Agradecimientos Disfruté la redaccién de este libro, y ciertamente espero que el lector disfrute leyéndolo. ‘Mucho de este placer proviene por haber trabajado con amigos. Recibf una ayuda mara- villosa de Brett Conley, Cordula Robinson y Erin Maneri, quienes crearon los archivos IST X y trazaron todas las figuras. Sin el apoyo constante de Brett nunca hubiera podido terminar esta nueva edicién. Steven Lee y Cleve Moler me proporcionaron ayuda previa con los cédigos de ense- fianza. Ellos siguieron los pasos descritos en el libro: MATLAB, Maple y Mathematica son ms répidos para matrices grandes. Todos pueden utilizarse (de manera opcional) en este ‘curso. Hubiera podido afiadir “Factorizaci6n” a la lista anterior, como una quinta avenida para la comprensién de las matrices: [L.U,P] = lu(A) para ecuaciones lineales [Q.R] = ar(A) para hacer ortogonales a las columnas [S.€] = eig(A) para encontrar vectores caracteristicos y valores caracteristicos. Al dar las gracias, nunca me olvido de la primera dedicatoria de este libro, hace afios. ‘Aquélla fue una oportunidad especial para agradecer a mis padres por haberme proporcio- nado tantos presentes generosos. Su ejemplo es una inspiracién en mi vida. Y también agradezco al lector, esperando que le agrade este libro. Gilbert Strang044-738 M atric egy" aces eliminacién gaussiana Ez 1.1 INTRODUCCION Este libro empieza con el problema central del algebra lineal: la solucién de ecuaciones li- neales. El caso més importante, y el més sencillo, es cuando el atimero de incégnitas es igual al ntimero de ecuaciones. Se tienen n ecuaciones en n incdgnitas, empezando conn = 2: Dos ecuaciones Ix + 2y = 3 Dos ineégnitas ar + Sy = 6 Las inc6gnitas son x y y. Para resolver estas ecuaciones requiero, describir dos métodos e! de eliminacién y el de determinantes. Ciertamente, x y y estén determinadas por los nuime- ros 1, 2, 3, 4,5, 6. La cuesti6n es c6mo utilizar estos seis ntimeros para resolver el sistema. a 1. Eliminacién De la segunda ecuacién, réstese 4 veces la primera ecuacién. Asf se eli- mina x de la segunda ecuaci6n, y queda una ecuacién para y: (ecuacién 2) — 4(ecuacién 1) =3y = 2) De inmediato se sabe que y = 2. Luego, x se conoce a partir de la primera ecuacién, le+2y=3: als @ Con sustitucién hacia atrés 1x +2(2)=3 se obtiene Procediendo cuidadosamente, se comprueba que x y y también resuelven la segunda ecuaci6n. Esto debe funcionar, como es el caso: 4 veces (x = —1) mas 5 veces (y = 2) es igual a6. 2. Determinantes La solucién y = 2 depende completamente de los seis niimeros en las ecuaciones. Debe haber una f6rmula para y (y también para x). Se trata de una “razén. de determinantes”, que espero, el lector me permita escribir directamente: @Captulo 1 Matices y elminacin gaussiana Lo anterior puede parecer algo misterioso, a menos que el lector ya conozca algo sobre de~ terminantes de 2 por 2. Estos determinantes proporcionan la misma respuesta y = 2, pro- veniente de la misma razén de ~6 a3. Si nos quedamos con los determinantes (lo cual no pensamos hacer), hay una férmula semejante para calcular la otra inc6gnita, x. -L. 6) 32 —_ 6 5|_ 3:5=2:6° 3 12 : 45 ‘A continuaci6n se compararin ambos métodos, pensando en futuros problemas reales en los que n es mucho més grande (n = 1000 es un tamaiio bastante moderado en célculos cientificos). Lo cierto es que el uso directo de la férmula de los determinantes para 1000 ecuaciones puede ser un desastre total, ya que el millén de némeros a la izquierda se utiliza- rfa correcta pero ineficazmente, Esta formula se encontraré en el capitulo 4 (regla de Cramer), aunque en el capitulo 1 se presenta un método aceptable para resolver 1000 ecuaciones. Este método aceptable es la eliminacién gaussiana. Se trata del algoritmo que suele aplicarse de manera constante para resolver grandes sistemas de ecuaciones. A partir de los ‘ejemplos en un libro de texto (n = 3 se aproxima al {mite superior de la paciencia del au- tor y del lector), quizé el lector no puede apreciar mucha diferencia, En las ecuaciones (2) y (4) se siguieron esencialmente los mismos pasos para encontrar y = 2. Ciertamente, x se ‘conocié mas répido por la sustitucién hacia atrés en la ecuaci6n (3) que la raz6n en (5). Pa- ran més grande, no hay caso. Gana la eliminacién (e incluso este método es el mejor para calcular determinantes). La idea de eliminaci6n es engafiosamente simple: el lector la dominaré luego de unos ccuantos ejemplos. Constituye la base de la mitad de este libro, simplificando una matriz. de ‘modo que sea posible comprendetia, Junto con la mecénica del algoritmo, en este capitulo es necesario explicar cuatro aspectos més profundos. Estos son: 1. Las ecuaciones lineales evan a la geometria de planos. No es facil visualizar un pla- ‘no nueve-dimensional en un espacio de diez dimensiones. Es més dificil ver diez de es- tos planos, que se cortan en la solucién de diez ecuaciones, aunque de alguna manera esto es casi posible. Nuestro ejemplo tiene dos rectas en la figura 1.1, que se encuen- tran en el punto (x, y) = (—1, 2). El Algebra lineal mueve esta imagen hacia diez di- mensiones, donde la intuiciéa debe imaginar la geometrfa (y la obtiene correctamente) 2. Pasamos a la notacién matricial al escribir las n inc6gnitas como un vector x y las n ecuaciones como Ax = b. Multiplicamos A por “matrices de eliminacién” con la fina- lidad de obtener una matriz triangular superior U. Con lo anterior, A se factoriza en L veces U, donde L es triangular inferior. 4x + 5y =6 4x +8y =6 4x + By = 12 Una solucién (x,y) =(- 1,2) Paralelas: no hay solucién —_Recta completa de soluciones Figura 1.1 El ejemplo tiene una solucién. Los casos singulares no tienen solucién, o tie- nen demasiadas soluciones.1.2 Geometria de tas ecuacioneslinesles 3 Accontinuacién se escribirén A y sus factores para nuestro ejemplo, y se explicarén en su debido momento: 45 4 1}lo -3 Primero es necesario presentar las matrices, los vectores y las reglas de la multiplica- cién. Toda matriz tiene una fraspuesta AT. Esta matriz, tiene una inversa A~*. 3. En la mayor parte de los casos, la eliminaciGn se realiza sin dificultades. La matrz tie- ne una inversa, y el sistema Ax = b tiene una solucién. En casos excepcionales e! mé- todo falla; ya sea que las ecuaciones se escribieron en orden equivocado, lo cual se arregla fécilmente al intercambiarlas, o las ecuaciones no tienen una solucién tnica. El caso singular aparece si 8 se sustituye por 5 en nuestro ejemplo: Caso singular lx + 2y = 3 Dos rectas paralelas 4x + By = 6. Factorizacién, ani 3)-[: al [3 3] eves o. © Mm La eliminacién resta simplemente 4 veces la primera ecuacién de la segunda. Sin em- argo, jobserve el resultado! (ecuacién 2) ~ 4(ecuacién 1) Este caso singular no tiene solucién. Otros casos singulares tienen una infinidad de soluciones. (Cambie 6 a 12 en el ejemplo, y la eliminacién produciré 0 = 0. Ast, ¥ puede asumir cualquier valor.) Cuando la eliminacién falla, se quiere encontrar toda solucién posible. 4, Se requiere una estimaci6n aproximada del niimero de pasos de eliminacién necesa- rios para resolver un sistema de tamaiio n. El costo de cémputo a menudo determina la precisiéa det modelo. Cien ecuaciones requieren alrededor de 300 000 pasos (mul- tiplicaciones y restas). La computadora es capaz de hacer estos pasos répidamente, pe- 10 no es asf para el caso de varios billones de pasos. Y después de un millén de pasos, elerror por redondeo puede ser significativo. (Algunos problemas son sensibles; otros no.) Sin entrar en todos los detalles, pretendemos considerar grandes sistemas que se presentan en la préctica, asf como la manera en que se resuelven realmente. El resultado final de este capftulo, es un algoritmo de eliminacién que es casi lo més eficaz posible. Se trata del algoritmo que suele usarse en una nuimerosa variedad de aplica- ciones. ¥ al mismo tiempo, comprenderlo en térmainos de matrices —la matriz de coeficien- tes A, las matrices E y P para la eliminaci6n ¢ intercambio de renglones, respectivamente, y los factores finales L y U—es un fundamento esencial de la teorfa. Espero que el lector disfrute este libro y su curso. 1.2. GEOMETRIA DE LAS ECUACIONES LINEALES La forma de comprender este tema es mediante un ejemplo. Se empieza con dos ecuacio- nes extremadamente simples, reconociendo que el lector puede resolverias sin necesidad de llevar un curso de flgebra lineal. No obstante, espero que le dé una oportunidad a Gauss: de -y=l xty=s. Este sistema puede abordarse por renglones 0 por columnas. Queremos abordarlo en am- ‘bas formas.Capitulo t (Mavices y elminecién gaussiana El primer método se centra en las ecuaciones por separado (los renglones). Es el més conocido, y en dos dimensiones se hace répidamente. La ecuacién 2x —y = ta por una linea recta en el plano x-y. La recta pasa por los puntos x = l,y = Lyx y = 0(y también por (2, 3) y todos los puntos intermedios). La segunda ecuacién, x + y = 5, produce una segunda recta (véase la figura 1.2). Su pendiente es dy/dx = —1 y cor- taa la primera recta en la solucién. El punto de interseccién pertenece a ambas rectas. Se trata de la nica solucién de las dos ecuaciones. El punto x = 2 y y = 3 se encontrar pronto por “eliminacién”. = 2(columna 1) al 9) = 43 (columns 2) Se(4s2) (<1, (2,1) = columna 1 a) Las rectas se cortan en 6) Las columnas se combinan con 2 y 3 z=2y=3 Figura 1.2 Representaci6n por renglén (dos rectas) y representacién por columna (se combinan columnas). El segundo método considera las columnas del sistema lineal. Las dos ecuaciones por separado en realidad son una ecuacién vectorial: =1) ft off El problema consiste en encontrar la combinacién de los vectores columna en el miembro izquierdo que produce el vector del miembro derecho. Los vectores (2, 1) y (—1, 1) se re- resentan con las Ifneas gruesas en la figura 1.2b. Las incdgnitas son los nimeros x y y que ‘multiplican a los vectores columna. Toda la idea puede verse en esa figura, donde 2 veces la columna 1 se suma a3 veces la columna 2. Geométricamente, asf se obtiene un famoso pa- ralelogramo. Algebraicamente, se obtiene el vector correcto (1, 5), en el miembro derecho de las ecuaciones, La representaci6n por columnas confirma que x = 2 y y = 3. Puede dedicarse mAs tiempo a este ejemplo, aunque se prefiere pasar al caso en que n= 3. Tres ecuaciones siguen siendo manipulables, y presentan mucha mayor variedad: Forma de columna «ff e+ vt we 5 ‘Tres planos 4u — 6y =-2 a Wut Ty +2w= 9. De nuevo, es posible estudiar los renglones las columnas, de modo que se empieza con los renglones. Cada ecuacién describe un plano en tres dimensiones. El primer plano es 2u + v + w =5, y se muestra en la figura 1.3. Contiene a los puntos ($ , 0, 0) y (0, 5,0) y (0, 0, 5). Es determinado por cualesquiera tres de sus puntos, suponiendo que no son colineales. Al cambiar 5 a 10, el plano 2u + v + w = 10 debe ser paralelo al anterior. Contie- ne a (5, 0, 0) y (0, 10, 0), y (0, 0, 10) que esté dos veces més lejos del origen, que es elO1l 1.2 Geometva de las ecuaciones inaalts 5 I wo o " Jos dos primeros planos Figura 1.3 La representacién por renglén: tres planos que se cortan, provenientes de tres ecuaciones lineales. punto central u = 0, v = 0, w = 0. Al cambiar el miembro derecho, el plano paralelo se mueve a sf mismo, y el plano 2u + v + w = 0 pasa por el origen. El segundo plano es 4u ~ 6v = ~2. Se traz6 verticalmente porque w puede asumir cualquier valor. El coeficiente de w es cero, aunque sigue siendo un plano en el espacio tridimensional, (La ecuacién 4u = 3, 0 incluso el caso extremo u = 0, sigue describien- do un plano.) En la figura se muestra la interseccién del segundo plano con el primero. Esta interseccién es una recta. En tres dimensiones, una recta requiere dos ecuaciones; en n dimensiones requiere n — 1. Finalmente, el tercer plano corta a la recta en un punto. El plano (no esté dibujado) representa la tercera ecuacién, —2u + 7v + 2w = 9, y corta ala recta en u = 1,v = I, w = 2. Este punto de interseccién triple (1, 1, 2) resuelve el sistema lineal. {.Cémo se extiende hasta n dimensiones esta representaci6n por renglones? Las n ecua- ciones contienen n incégnitas. La primera ecuacién sigue determinando un “plano”, que ya no es un plano bidimensional en el espacio tridimensional; de alguna manera, su “dimen- sign” es n — 1. Debe ser plano y extremadamente delgado en un espacio n-dimensional, aunque nos parezca s6lido. Siel tiempo es la cuarta dimensién, entonces el plano s = O corta al espacio tetradimen- sional y produce el universo tridimensional en que vivimos (o més bien, el universo como eran t = 0). Otro plano es z = 0, que también es tridimensional; se trata del plano normal X-y que se considera todo el tiempo. ;Estos espacios tridimensionales se cortan! Comparten. el plano normal x-y en t = 0. Si se desciende a dos dimensiones, el siguiente plano deja una recta. Por tiltimo, un cuarto plano deja un solo punto, Se trata de! punto de interseccién de 4 planos en 4 dimensiones, y resuelve las 4 ecuaciones subyacentes. Si continuamos con este ejemplo proveniente de la relatividad, estaremos en proble- mas. La cuestiGn es que el élgebra lineal es capaz de operar con cualquier mtimero de ecua- ciones. La primera ecuacién produce un plano (n ~ 1) dimensional en n dimensiones. ElCaputo 1 Matrices y eiminacién gaussiana segundo plano lo corta (esperamos) un conjunto més pequefio de ““dimensién n — 2”, Su- poniendo que todo va bien, todo plano nuevo (toda ecuacién nueva) reduce Ia dimensién en una unidad. Al final, cuando se hayan tomado en cuenta todos los 7 planos, la dimen- sién de la interseccién es cero. Se trata de un punto, que pertenece a todos los planos, y sus coordenadas satisfacen a todas las n ecuaciones. jEsta, es la solucién! Vectores columna y combinaciones [ineales Ahora volvemos a las columnas. Esta vez la ecuacién vectorial (la misma ecuaci6n que (1)) z Y 1 s Forma decolumna u} 4/ + |-6/ +w /o| = |-2] =o. @ +2. 7 2 9 Estos son vectores columna tridimensionales. El vector b se identifica con el punto cuyas coordenadas son 5, -2, 9. Todo punto en el espacio tridimensional se hace corresponder con un vector, y viceversa. Esta, era la idea de Descartes, quien transforms la geometria en. Algebra al trabajar con las coordenadas del punto. Es posible escribir el vector en una co lumna, 0 sus componentes pueden enumerarse como b = (5, —2, 9), 0 incluso puede re- presentarse geométricamente mediante una flecha a partir de su origen. Pueden elegirse la flecha, o el punto © los tres nuimeros. En seis dimensiones, quiz es mAs conveniente ele- ‘gir los seis niimeros, Cuando los componentes se enumeran horizontalmente, suele utilizarse paréntesis y comas, y cuando el vector colummna se indica verticalmente se usan llaves (sin comas). Lo que realmente importa es la suma de vectores y la multiplicacién por un escalar (un ni- mero). En Ja figura 1.4a se muestra una suma vectorial, componente por componente: me SE [3] = combinant 5 Ele 2 (columna 3) LI-E} columnas 1+ 2 LI 4) Los vectores se suman a ) Se suman las columnas 1 +2 + (3+ 3) Jo largo de los ejes Figura 1.4 La representacién por columna: la combinacién lineal de las columnas es igual a b.DA HACIONAL cope 1,2. Geometria de las ecvaciones lineales. 1 man oEe EL UnUaUAY «iis, AA REININA En la figura de la'aéieha' hay una’ mildiplicacion por 2 (y si el vector hubiese sido multi- plicado por -2, entonces el vector hubiera invertido su direccién): aman od “ff ‘También en la figura de la derecha se observa una de las ideas centrales del élgebra, Utiliza las dos operaciones bésicas: los vectores se multiplican por niimeros y luego se su- ‘man. El resultado se denomina combinacién lineal, y esta combinacién resuelve nuestra come [3] [4] ff -H La ecuaci6n (2) requirié multiplicadores u,v, w, que producen el miembro derecho b. Estos ngmeros son u = 1, v = 1, w = 2. Y proporcionan la combinacién correcta de las colum- nas. También proporcionaron el punto (1, 1, 2) en la representacién por renglén (donde se cortan los tres planos). ‘Nuestro verdadero objetivo es ir més allé de dos o tres dimensiones, hasta n dimensio- nes. Con n ecuaciones en n incOgnitas, en la representacién por rengl6n hay n planos. En Ja representacién por columna hay n vectores, més un vector b en el miembro derecho. La ecuacién pide una combinacién lineal de las n columnas que sea igual a b. Para ciertas ecuaciones esto ¢s imposible. Paradéjicamente, la mejor manera de entender el caso bue- ‘no €s estudiando el caso malo. Por consiguiente, consideraremos la geometria, justo cuan- do falla, en el caso singular. Representacién por renglén: interseccién de planos Representaci6n por columna: combinacién de columnas El caso singular ‘Suponga que nuevamente estamos en tres dimensiones, y que tres planos en la representa- cién por renglén no se cortan. {Qué puede estar mal? Una posibilidad es que dos planos pueden ser paralelos. Las ecuaciones 2u + v + w = Sy 4u + 2v + 2w = 11 son inconsis- tentes, y planos paralelos no dan solucién (en la figura 1.5a se muestra una vista del extre- mo). En dos dimensiones, la nica posibilidad de falla la constituyen las rectas paralelas. Sin embargo, tres planos en tres dimensiones pueden estar en problemas sin ser paralelos. La dificultad més frecuente se muestra en la figura 1.5b. A partir de la vista del ex- tremo, los planos forman un trigngulo. Cada par de planos se corta en una recta, y estas, RAAN dos planos no hay recta de todos los planos paralelos interseccién interseccién son paralelos a) 8) °) d) Figura 1.5 Casos singulares: no hay solucién para a), 6), 0 d), una infinidad de solucio- nies para c).Capitulo 1 Mavices y eliinacion gaussian rectas son paralelas. El tercer plano no es paralelo a los otros planos, pero es paralelo a su inea de intersecci6n. Esto corresponde a un sistema singular con b = (2, 5, 6): utu+ w=2 No hay soluciones, como en la figura l.5b = 2u +3w a5 @) Buty + dw =6. ‘Sumados, los dos primeros miembros izquierdos son iguales al tercero. En el miembro de- echo falla eso: 2 + 5 # 6.Laecuaci6n 1 menos la ecuaci6n 2 menos la ecuacién 3.¢s la afirmacién imposible 0 = 1. Asi, las ecuaciones son inconsistentes, como la eliminacién gaussiana descubre sisteméticamente. Ow sistema singular, préximo a éste, tiene una infinidad de soluciones. Una vez que el 6 en la Gltima ecuacién se vuelve 7, las tres ecuaciones se combinan para dar 0 = 0. Asf, Ja tercera ecuacién es la suma de las dos primeras. En ese caso, los tres planos tienen toda una recta en comtin (véase la figura 1.5c). Al cambiar los miembros derechos, los planos de la figura 1.56 se moverdn en sentido paralelo a s{ mismos, y para b = (2, 5, 7), repeati- namente la figura es diferente. El plano inferior se movi6 para encontrar a los otros, y hay ‘una recta de soluciones. El problema 1.5c sigue siendo singular, pero ahora adolece de de- masiadas soluciones, en vez de tenet unas cuantas. El caso extremo lo constituyen tres planos paralelos. Para la mayor parte de miembros derechos no hay solucién (véase la figura 1.5d). Para miembros derechos especiales (jco- mob = (0, 0, 0)!), hay todo un plano de soluciones, ya que los tres planos paralelos se mue- ven para convertirse en el mismo. {Qué ocurre con la representacién por columna cuando el sistema es singular? Debe estar mal, aunque la pregunta es c6mo. En el miembro izquierdo de las ecuaciones sigue ha- biendo tres columnas, y se intenta combinarlas para obtener b. Se queda con la ecuacién (3): Caso singular: representacién por columna F] | E] u}2] + ]o| +w |3| =o ) ‘Tres columnas en el mismo plano 2 0 3 Facil de resolver s6lo para en ese plano 3 1 4. Para b = (2, 5, 7) era posible esto; para b = (2, 5, 6) no lo era. La raz6n de esto es que es- tas tres columnas estén en un plano. Entonces cualquier combinacién también estd en el plano (que pasa por el origen). Si el vector b no esté en ese plano, ninguna solucién es po- sible (véase la figura 1.6). Este es por mucho el evento més probable; un sistema singular 3 columnas \ 3 columnas en un plano b no est en el plano a) no hay solucién >) infinidad de soluciones Figura 1.6 Casos singulares: b fuera o dentro de! plano con todas las tres columnas.1.2. Gaometta de is ecvacioneslneales 9 en general no tiene soluci6n. Sin embargo, hay una posibilidad de que b esré en el plano de las columnas. En ese caso hay demasiadas soluciones; las tres colurnnas pueden com- binarse en una infinidad de formas para producir b. Esa representacién por columna de a figura 1.66 corresponde a la representaci6n por renglén de la figura 1.5c. {Cémo se puede saber que las tres columnas estén en el mismo plano? Una respuesta consiste en encontrar una combinacién de las columnas cuya suma sea cero. Después de al- gunos célculos, esta combinaci6n es u = 3, v = —1, w = —2. Tres veces la columna 1 es igual a dos veces la columna 2 més dos veces la columna 3. La columna 1 esté en el plano de las columnas 2 y 3. S6lo dos columnas son independientes. El vector 6 = (2, 5, 7) esté en ese plano de las columnas: es 1a columna 1 més la co- jumna 3, de modo que (1, 0, 1) es una solucién. Es posible sumar cualquier muiltiplo de la combinacién (3, —1, -2) que produzca b = 0. Ast, hay toda una recta de soluciones, co- mo se sabe a partir de la representacién por renglén. La verdad es que se sabfa que las columnas deben combinarse para obtener cero, ya que eso ocurrfa con los renglones. Este hecho pertenece a las mateméticas, no a los célcu- los, y sigue siendo verdadero en la dimensin n. Si los n planos no tienen ningtin punto en comin, 0 comparten una infinidad de puntos, entonces las n columnas estén en el mismo plano. Si Ia representacién por renglén falla, entonces también falla la representacién por co- lumna. Esto hace la diferencia entre el capitulo 1 y el capftulo 2. En el capftulo 1 se estudia el problema mds importante: el caso no singular, donde hay una solucién que es necesario ‘encontrar. En el capitulo 2 se estudia el caso general, donde puede haber muchas soluciones ‘© ninguna. En ninguno de estos dos casos es posible continuar sin tener una notacién (nota- cién matricial), y un algoritmo (eliminacién) idéneos. Después de los siguientes ejercicios se abordaré la eliminacién. Conjunto de problemas 1.2 1. Para las ecuaciones x + y = 4, 2x — 2y = 4, trace Ia representacién por renglén (dos rectas que se cortan), y la cepresentacién por columna (combinacién de dos columnas igual al vector columna (4, 4) en el miembro derecho). 2, Resuelva lo siguiente para encontrar una combinacién de las columnas que sea igual a b: unv-wab Sistema triangular vtwb w= by 3. (Recomendado) Describa la intersecci6n de los tres planos u + u + w+z=6yut w+z=4yut w= 2 (todos en el espacio tetradimensional). {Es una recta, un pun- to.0 un conjunto vacfo? {Cudl es la interseccién si se incluye el cuarto plano u = —17 Encuentre una cuarta ecuacién que deje Ja situacién sin solucién, Trace las tres rectas siguientes, y decida si las ecuaciones son de fécil soluci6n: x+2y=2 Sistema de3por2 x — y ye {Qué ocurre si todos los miembros izquierdos son cero? {Hay alguna opcién diferen- te de cero de miembros derechos que permita que las tres rectas se cortan en el mismo punto? 5, Encuentre dos puntos en la recta de interseccién de los tres planos t = 0 y x+y+z+1= 1 enel espacio de 4 dimensiones. =oyCaplnd 1 Matrices y eieinacin gaussiana 6. Cuando b = (2, 5, 7), encuentre una solucién (u, v, w) de la ecuacién (4) distinta de Ja solucién (1, 0, 1), mencionada en el texto. 7. Proporcione dos miembros derechos mAs, aparte de b = (2, 5, 7) para los cuales la ecuacién (4) pueda resolverse. Proporcione dos miembros derechos ms, aparte de b = (2,5, 6) para los cuales la ecuacién (4) no pueda resolverse. 8. Explique por qué el sistema ut vt w=2 w+ 2v + 3w =1 v+2w=0 ¢s singular, encontrando una combinacién de las tres ecuaciones que produzca 0 = 1 {Qué valor debe sustituirse en el dltimo cero del miembro derecho para que las ecua- ciones tengan soluciones, y cudl es una de las soluciones? 9, La representaci6n por columna del ejercicio anterior (sistema singular) es dd ‘Demuestre que las tres columnas de la izquierda estén en el mismo plano, expresando la tereera columna como una combinacién de las dos primeras. {Cudles son las solu- ciones (u, v, w) si b es el vector cero (0, 0, 0)? 10. (Recomendado) {Bajo qué condicién sobre y,, yz, y3 los puntos (0, y,), (1s ¥a)s (2s Ys) estén en una Kinea recta? 11. Es cierto que la solucién de las siguientes ecuaciones es x = y = 0. ,Para qué valores de a hay toda una recta de soluciones? ax +2y 2x + ay 12, Empezando con x + 4y = 7, encuentre la ecuacién de la recta paralela que pasa por x = 0,y = 0. Encuentre la ecuaci6n de otra recta que corta a la primera en x = 3, y = 1. Los problemas 13 a 15 son un repaso de las representaciones por renglén y por columna. 13. Trace las dos representaciones en dos planos para las ecuaciones x —2y = 14. Para dos ecuaciones lineales en tres incégnitas x, y, z, la representaci6n por renglén muestra (2.0 3) (rectas 0 planos) en un espacio (bi o tri) dimensional. La representa- ci6n por columna es en un espacio (bi o tri) dimensional. Las soluciones normalmen- teestinenun___. x+y = 6. 15. Para cuatro ecuaciones lineales en dos incégnitas x y y, la representaci6n por renglén muestra cuatro La representacién por columna est4 en un espacio di- mensional. Las ecuaciones no tienen solucién, a menos que el vector del miembro de- recho sea una combinacién de __. 16. Encuentre un punto con z en la recta de interseccién de los planos x + y + 3z = 6yx—y +z= 4. Encuentre el punto con z = Oy un tercer punto a la mitad entre los dos puntos anteriores.1.3. Un ejemplo de eliinscién gaussiane " 17. La primera de las siguientes ecuaciones més la segunda es igual a la tercera: xt yte xt2yt 253 Qe +3y +22 Los dos primeros planos se encuentran a lo largo de una recta. El tercer plano contie~ ‘ne a esta recta, ya que si x, y, z satisfacen las dos primeras ecuaciones, entonces tam- bién ____. Las ecuaciones tienen una infinidad de soluciones (toda la recta L). En- cuentre las tres soluciones. 18. Mueva el tercer plano en el problema 17 hasta un plano paralelo 2x + 3y + 2z = 9. Ahora, las tres ecuaciones no tienen soluci6n; ,por qué? Los dos primeros planos se encuentran a lo largo de la recta L, pero el tercero no esa recta. 19. Enel problema 17, las colurmnas son (1, 1, 2) y (1, 2,3)y (1, 1, 2). Este es un “caso sin- gular” porque la tercera columna es __. Encuentre dos combinaciones de las colum- nas que proporcionen 6 = (2, 3, 5). Esto s6lo es posible para b = (4,6, ¢) sic =__. 20. Normalmente, 4 “planos” en el espacio tetradimensional se cortan en un Nor- malmente, 4 vectores columna en el espacio de 4 dimensiones pueden combinarse pa- ra producir b. ,Qué combinacién de (1, 0,0, 0), (1, 1,0, 0), (1, 1, 1,0), (1, 1, 1, 1) pro duce b = (3,3, 3, 2)? {Cuéles son las 4 ecuaciones que esti resolviendo para x, y, z,?, 21. Cuando la ecuacién 1 se suma a la ecuacién 2, ,cusl de las siguientes opciones cam- bia: los planos en la representaci6n por rengl6n, la representacién por colurnna, la ma- triz de coeficientes, la solucién? Si (a, b) es un milltiplo de (c, d) con abcd # 0, demuestre que (a, c) es un miltiplo de (6, d). Esto es sorprendentemente importante: denominela pregunta de desafio, Primero puede usar mimeros para ver c6mo estén relacionados a, b, c y d. La pregunta leva a: Si A [i ‘] tiene renglones dependientes, entonces tiene columias dependientes. 23. Enestas ecuaciones, la tercera colunna (que multiplica a w) es la misma que el miem- bro derecho b. La forma en columna de las ecuaciones, ,qué solucién para (u,v, w) proporciona de inmediato? 6u + 7v + Bw =8 4u + 5u + 9w =9 2u —2v + Tw =7. 1.3 UN EJEMPLO DE ELIMINACION GAUSSIANA La forma de entender la eliminacién es por medio de un ejemplo. Se empieza en tres di- mensiones: ut ut w= 5 Sistema original 4u — 6 =-2 a + Tut 2w= 9. El problema consiste en encontrar los valores inc6gnitos de u, v, y w, de modo que se aplicaré eliminacién gaussiana. (Gauss es reconocido como el més grande de los matemé- ticos, aunque no ciertamente debido a este invento, que quizé le lev6 10 minutos. IrSnica- mente, és el concepto més frecuentemente utilizado que leva su nombre.) El método em-12 Capito 1 Matvces y eiminacién gaussiana pieza por restar miiltiplos de la primera ecuacién a las otras ecuaciones. El objetivo es eliminar u de las dos tltimas ecuaciones. Para lograt este objetivo se requiere lo siguien- te: 4) restar 2 veces la primera ecuacién de la segunda ) restar -1 vez la primera ecuacién de la tercera. mrt vt we 5 Sistema equivalente —8v — 2w = -12 @ Bu+3w= 14, El coeficiente 2 es el primer pivote. La eliminacién consiste en dividir constantemente €] primer pivote entre los niimeros que estén abajo de él, con la finalidad de encontrar los mul- tiplicadores idéneos. El pivote de la segunda etapa de la eliminacién es -8. Ahora se ignora la primera ecuacién. Un miltiplo de la segunda ecuacién se restaré de las ecuaciones que quedan (en este caso s6lo queda la tercera) con la finalidad de eliminar v. La segunda ecuacién se su- maa Ia tercera 0, en otras palabras, ) se resta I vez la segunda ecuaciGn de la tercera. Ahora el proceso de eliminacién est completo, por lo menos en la direccién “hacia ade- Jante”: wt vt we 5 Sistema triangular —8y — 2w = -12 ) w= 2. Este sistema se resuelve hacia atras, de abajo arriba. La tiltima ecuaci6n da w = 2. Al sustituir en la segunda ecuacién, se encuentra v = 1. Luego, la primera ecuaci6n da u = 1. Este proceso se denomina sustitucién hacia atrds. Para repetir: con la eliminacién hacia adelante se obtuvieron los pivotes 2, —8, 1. En este método se restan miltiplos de cada rengién de los renglones de abajo para llegar al sis- tema “triangular” (3), que se resuelve en orden inverso. Luego, cada nuevo valor calcula- do se sustituye en las ecuaciones restantes. Observacién Una forma aceptable de escribir los pasos de la eliminacién hacia adelante es incluir el miembro derecho como una columna adicional. No es necesario copiar u y v y wy = en cada paso, por lo que se trabaja con lo mfnimo indispensable: 2 1 1 5 2s a) 4 ~6 0 -2}+]0 -8 -2 -12}+]o0 -8 -2 -12 2072°2~«9 o 8 3 14 o o 1 2 Al final se llega al sistema triangular, que ya est4 listo para la sustitucién hacia atrés. Qui- 2 el lector prefiera esta disposicién, que garantiza que las operaciones en el miembro quierdo de la ecuacién también se realizan en el miembro derecho, ya que ambos miem- bros estan juntos abt. En un problema més grande, la eliminaci6n hacia adelante requiere més esfuerzo. Se usan miltiplos de la primera ecuacién para producir ceros abajo del primer pivote. Luego, la segunda columnna se limpia abajo del segundo pivote. El paso hacia adelante se finaliza ‘cuando el sistema es triangular; la ecuacién n s6lo contiene a la ultima incégnita multipli- ‘cada por el tiltimo pivote.Ejemplo 2 13 tag. FES Set URUGUAY La sustituci6n hacia’ atrés-produce la'sbludver tdhipfeta en orden opuesto: se empieza con la Ultima incégnita, luego se resuelve de la siguiente hasta la tltima, terminando con la primera. Por definiciGn, los pivotes no pueden ser cero. Es necesario dividir entre ellos. La falla de la eliminacién zEn qué circunstancias es posible que falle el proceso? Algo debe estar mal en el caso singular, y algo puede estar mal en el caso no singular. Esto podria parecer algo prematu- 10; después de todo, apenas se ha logrado tener funcionando al algoritmo. Sin embargo, la posibilidad de fala ilumina al método en sf. La respuesta es: con un conjunto completo de n pivotes, s6lo hay una solucién. El sis- tema es no singular, y se resuelve por eliminacién hacia adelante y sustituciGn hacia atrés. Pero si en una posicién pivote aparece un cero, es necesario detener la eliminacién, ya sea ‘temporal o permanentemente. El sistema puede o no ser singular. ‘Si el primer coeficiente es cero, en la esquina superior izquierda, la eliminaci6n de u de las otras ecuaciones es imposible. Lo mismo es cierto en toda etapa intermedia. Obser- ‘ve que en una posicién pivote puede aparecer un cero, aun si el coeficiente original en ese sitio no era cero. En términos generales, no se sabe si aparecerd un cero sino hasta que se intenta, al realizar en verdad el proceso de eliminacién. En muchos casos este problema puede restablecerse, por lo que la eliminacién puedé continuar. Un sistema asf sigue siendo no singular; es s6lo el algoritmo lo que requiere re- paraci6n. En otros casos es inevitable la falla. Estos sistemas incurables son singulares; no tienen solucién o tienen una infinidad de éstas, por lo que no es posible encontrar un con- junto completo de pivotes. No singular (restablecido al intercambiar las ecuaciones 2 y 3) ut vt wa ut vt wa utvt wa 2Qu + 2v + Sw 4u + 6v + Bw — awe 2u + 4w Qu + 4w = 3w EI sistema es triangular, y puede resolverse con sustitucién hacia atrés. ‘Singular (caso incurable) ut vt we utut ws Qu +2v+Sw = — 3w = _ 4u + 4u + Bw = dw =_ No existe ningiin intercambio de ecuaciones que pueda evitar el cero en la segunda posi- cién pivote. Las ecuaciones mismas pueden ser 0 no faciles de resolver. Si las dos tltimas ecuaciones son 3w = 6 y 4w = 7, no hay soluci6n. Si ocurre que estas dos ecuaciones son consistentes, como con 3w = 6 y 4w = 8, entonces este caso singular tiene una infinidad de soluciones. Se sabe que w = 2, pero la primera ecuaci6n no puede decidir ambas u y v. En la seccién 1.5 se abordarén los intercambios de renglén cuando el sistema es no singular. Asf, los intercambios producen un conjunto completo de pivotes. En el capitulo 2 se estudia el caso singular. El 3w atin puede eliminar a 4w, por lo que el segundo pivote es 3. (No habré un tercer pivote). Por ahora se confia en que todos los n elementos pivote son diferentes de cero, sin cambiar el orden de las ecuaciones. Este es el mejor caso, que seré continuado.4 Capito 1 Matrices y elrinacén gaussiana El costo de la eliminacién La otra pregunta es muy préctica. ,Cudntas operaciones aritméticas requiere la elimina. ccidn para n ecuaciones en n incégnitas? Si n es grande, una computadora puede realizar el proceso de eliminacién. Debido a que se conocen todos los pasos, debe ser posible po- der pronosticar el nimero de operaciones. Por el momento se ignoraréin los miembros derechos de las ecuaciones, y s6lo se con- tarin las operaciones a la izquierda. Estas operaciones son de dos clases. Se divide entre el pivote para encontrar qué milltiplo (por ejemplo £) de la ecuacién pivote debe restarse. Una vvez que se realiza esta sustraccién, continuamente se encuentra una combinacién “multipli- car-restar”; los términos de la ecuacién pivote se multiplican por ¢, y luego se restan de otra ecuacién, Suponga que cada divisi6n, y cada multiplicacién-sustraccién se denomina una ope- racién. En la columna 1, se requieren n operaciones por cada cero que se obtiene: una pa- ra encontrar el miltiplo £, y la otra para encontrar los nuevos elementos a lo largo del rengl6n. Abajo del primer renglén hay n ~ 1 renglones, de modo que la primera etapa de la eliminaci6n requiere n(n ~ 1) = n? ~ n operaciones. (Otra forma de llegar an? — nes ésta: es necesario cambiar todos los n* elementos, excepto los n en el primer renglén). Las eta- pas posteriores son més répidas porque las ecuaciones son més cortas. ‘Cuando la eliminaci6n se realiza con k ecuaciones, para limpiar la columna que esti aba- _jo del pivote se requieren s6lo i? — k operaciones, por el mismo razonamiento que se aplicé en la primera etapa, cuando k era igual a n. Al reunir todo lo anterior, se encuentra que el ni- ‘mero total de operaciones es la sumatoria de — k sobre todos los valores k desde I hasta n: n(n + 1Qn +1) _ n(n ty 6 2 Miembro izquierdo 1? + +++ +n®) —(1+-++ +n) = 3 Estas férmulas son normales para encontrar las sumatorias de los n primeros mimeros y los n primeros cuadrados. Al sustituirn = 1 yn = 2yn = 100en la formula } (n° —7), lacli- minaci6n hacia adelante puede no requerir ningéin paso, requerir dos pasos o requerir alre- dedor de un millén de pasos: Sin no es grande en absoluto, una buena estimacién para el niimero de operaciones es 4n>. Si el tamafio se duplica, y pocos de los coeficientes son cero, entonces el costo se multipli- ca por 8 La sustitucién hacia atrés es considerablemente més répida. La ultima incégnita se en- cuentra en s6lo una operacién (una divisi6n entre el titimo pivote). Para encontrar la ante- pentltima incégnita se requieren dos operaciones, y asf sucesivamente. Entonces, el total para la sustitucién hacia atrés es 1+ 2 +--+. La eliminaci6n hacia adelante también acta sobre el miembro derecho (restando los mismos miltiplos que en la izquierda con la finalidad de preservar las ecuaciones correc- tas). Empieza con 7 — 1 sustracciones de la primera ecuaci6n. Junto con el miembro dere- cho es responsable de n* operaciones: mucho menos que las 7°/3 a la izquierda. El total para la eliminaci6n hacia adelante y la sustitucién hacia atrés es Miembro derecho [(n = 1) + (n —2) +--+ +1] +[1+24-+- +n] Hace 30 afios, casi cualquier matemético hubiera conjeturado que un sistema general de orden n no podia resolverse con mucho menos que n?/3 multiplicaciones. (Incluso ha- 2