3 Métodos directos de resolución de sistemas linealespersonal.us.es/doubova/cn1/Tema3CNI.pdf · Antes de hacer una descripción general del método de Gauss (que es bastante engorroso

3 Versión: 2 de abril de 2018

Métodos directos de resolución desistemas lineales

3.1 Introducción

Una ecuación lineal (sistema de orden 1) es de la forma:

ax = b,

donde a y b son números reales dados y x es la incógnita a determinar.Un sistema de ecuaciones lineales es un conjunto de ecuaciones lineales que comparten las mismas incógnitas.Un sistema de ecuaciones de orden 2 es de la forma:{

ax+ by = cdx+ ey = f,

donde a, b, c, d, e, f son números dados y x e y son las incógnitas.

Cuando hay más de 3 o 4 ecuaciones y/o incógnitas, se suele utilizar una notación con subíndices para designartanto las incógnitas como los coeficientes. Así, un sistema lineal de m ecuaciones con n incógnitas se representa,de forma general:

a11x1 + a12x2 + . . . + a1nxn = b1a21x1 + a22x2 + . . . + a2nxn = b2

. . .am1x1 + am2x2 + . . . + amnxn = bm

(3.1)

donde aij y bj son números reales dados y xi son las incógnitas.Este sistema se puede escribir de forma equivalente utilizando notación matricial, que es, en general, más fácilde escribir:

a11 a12 . . . a1na21 a22 . . . a2n...

.... . .

...am1 am2 . . . amn

x1x2...xn

=

b1b2...bm

,Llamando A a la matriz m×n de los coeficientes del sistema, x al vector columna de longitud n de las incógnitasy b al vector columna de longitud m del segundo miembro, el sistema de ecuaciones anterior se puede finalmenteescribir en la forma más resumida:

Ax = b. (3.2)

Una solución del sistema (3.1) es un conjunto de n valores (ordenados) tales que, al sustituir las incógnitas porestos valores, las ecuaciones se convierten en identidades. Colocando estos valores en forma de vector columna,x de longitud n, se tiene, obviamente, una solución del sistema escrito en forma matricial (3.2). Por ello se suelehablar de vector solución, tanto de (3.1) como de (3.2).

1

3. Métodos directos de resolución de sistemas lineales 2

Los sistemas lineales no siempre tienen solución. En relación con el número de soluciones de un sistema linealde ecuaciones, sólo pueden darse los tres casos siguientes:

1. No tener ninguna solución: se dice que el sistema es incompatible.

2. Tener una única solución: el sistema es compatible determinado.

3. Tener infinitas soluciones: el sistema es compatible indeterminado.

Ejemplo 3.1

• El siguiente sistema es incompatible (no tiene solución):{x1 + x2 = 1x1 + x2 = 2.

• El siguiente sistema tiene una única solución:{x1 − x2 = 0x1 + x2 = 2

(x1x2

)=

(11

).

• El siguiente sistema tiene infinitas soluciones:{x1 + x2 = 12x1 + 2x2 = 2

(x1x2

)=

(α

1− α

), ∀α ∈ R.

En el caso particular en que un sistema lineal tiene el mismo número de ecuaciones que de incógnitas, la matrizdel sistema es cuadrada,

a11 a12 . . . a1na21 a22 . . . a2n...

.... . .

...an1 an2 . . . ann

x1x2...xn

=

b1b2...bn

. (3.3)

Se recuerda que una matriz cuadrada es regular si su determinante, det(A), es distinto de cero, lo cual esequivalente a la existencia de la matriz inversa A−1.

Proposición 3.2 El sistema de ecuaciones lineales Ax = b, con A matriz cuadrada de orden n de coeficientes

reales posee una única solución para todo b ∈ Rn si y sólo si la matriz A es regular.

Demostración: Si A es regular, entonces existe la inversa A−1, luego la solución es única y viene dada por

Ax = b ⇔ A−1Ax = A−1b ⇔ x = A−1b.

Recíprocamente, supongamos que para todo b ∈ Rn existe una única solución de Ax = b. Sean {e1, . . . , en} losvectores de la base canónica de Rn y consideramos n sistemas lineales de la forma

Ack = ek, k = 1, . . . , n.

Por hipótesis, existe una única solución ck para cada k = 1, . . . , n. Sea C una matriz, cuyas columnas estánformadas por los ck, es decir C = [c1|c2| · · · |cn]. Entonces,

AC = [Ac1|Ac2| · · · |Acn] = [e1|e2| · · · |en] = I ⇔ AC = I ⇔ C = A−1,

es decir A es regular.�

En lo que sigue, vamos a suponer que A es una matriz cuadrada regular de coeficientes reales.

Anna Doubova - Dpto. EDAN - U. de Sevilla Cálculo Numérico I - Grado en Matemáticas


Los métodos de reducción, sustitución e igualación que se estudian en la enseñanza secundaria están diseñadosprincipalmente para sistemas de pocas ecuaciones e incógnitas (2 ó 3). Por otra parte, la conocida regla deCramer proporciona fórmulas para las soluciones de sistemas compatibles determinados: si en (3.3), la matriz Aes tal que det(A) 6= 0, entonces el sistema posee una única solución, que es el vector columna x de componentes:

xi =det(Ai)

det(A), i = 1, . . . , n,

donde Ai es la matriz obtenida a partir de A reemplazando su i-ésima columna por el vector b.

En la práctica, es necesario resolver sistemas lineales con un número elevado de ecuaciones e incógnitas y laresolución de tales sistemas por la regla de Cramer es inviable, incluso para un ordenador, a causa de la enormecantidad de operaciones que exige: aproximadamente 2(n+1)! si se usa la regla recursiva de Laplace para calcularlos determinantes (ver [4]). Como es habitual, por operación queremos decir una suma, una resta, un productoo una división. Por ejemplo, con un ordenador capaz de realizar 109 operaciones por segundo, se necesitarían entorno a 12 horas para resolver un sistema de dimensión n = 15 (aprox. 4× 1013 operaciones) por este método,y en torno a 3240 años para un sistema de dimensión n = 20 (aprox. 1020 operaciones).

Más adecuados para la resolución de sistemas lineales son dos familias de métodos alternativos: los llamadosmétodos directos que dan la solución del sistema en un número finito de pasos, o los métodos iterativosque requieren (en principio) un número infinito de pasos. Los métodos iterativos se analizarán en la asignatura«Cálculo Numérico II». En este curso, vamos a estudiar los métodos directos. Dichos métodos están basadosen la construcción de un sistema equivalente al dado, es decir, con la misma solución (ver la Sección 3.3),pero que sea más fácil de resolver, concretamente que tenga una matriz triangular (ver la Sección 3.2). Estosmétodos, en general, requieren del orden de 2n3/3 operaciones para resolver el sistema lineal (3.3), es deciraprox. 2250 operaciones para n = 15 y 5300 para n = 20.Observemos que la elección entre métodos directos e iterativos puede depender de varios factores: en primerlugar de la eficiencia teórica del algoritmo, pero también del tipo particular de la matriz, la memoria de alma-cenamiento requerido y, finalmente del la estructura del ordenador (véase [4]).

A continuación presentamos el procedimiento para resolver sistemas lineales con matriz triangular.

3.2 Resolución de sistemas triangulares

Cuando la matriz del sistema lineal (3.3) es triangular inferior (resp. superior) dicho sistema se puede resolverfácilmente, ya que las incógnitas se pueden ir despejando de una en una y sustituyendo en las demás ecuaciones,como se muestra en el siguiente ejemplo de dimensión 3: a11 0 0

a21 a22 0a31 a32 a33

x1x2x3

=

b1b2b3

,que se escribe en forma desarrollada: a11x1 = b1

a21x1 + a22x2 = b2a31x1 + a32x2 + a33x3 = b3 .

Este sistema tendrá solución única si y sólo si det(A) 6= 0, y puesto que, en este caso, det(A) = a11 · a22 · a33, elsistema tiene solución si y sólo si aii 6= 0 para todo i = 1, 2, 3.Suponiendo, pues, que éste es el caso, una simple inspección del sistema muestra que se pueden calcular lasincógnitas de forma sucesiva, comenzando por x1: x1 = b1/a11 ,

x2 = (b2 − a21x1)/a22 ,x3 = (b3 − a31x1 − a32x2)/a33 .



Ejemplo 3.3 Resolución de un sistema triangular inferior 4x = 8x + 2y = 6−x + y − 2z = 12.

1. En la primera ecuación sólo aparece la incógnita x y por lo tanto se puede resolver independientemente:

4x = 8 ⇔ x = 2.

2. Una vez resuelta la primera ecuación, ya se sabe que, necesariamente, tiene que ser x = 2. Se puedeahora sustituir su valor en la segunda ecuación, en la que quedará y como única incógnita:

x+ 2y = 6 ⇔ 2y = 6− x = 6− 2 = 4 ⇔ y = 2.

3. Conocidas x = 2 e y = 2, se sustituyen en la tercera ecuación:

−2z = 12 + x− y = 12 + 2− 2 = 12 ⇔ z = −6.

4. Resumiendo, la única solución del sistema es

x = 2, y = 2, z = −6.

Este procedimiento se denomina algoritmo de bajada, ya que las incógnitas se van obteniendo por recurrencia,desde arriba hacia abajo.En general, un sistema de dimensión n× n con matriz triangular inferior

a11 0 . . . 0a21 a22 . . . 0...

.... . .

...an1 an2 . . . ann

x1x2...xn

=

b1b2...bn

.que tiene todos sus elementos diagonales no nulos, es decir aii 6= 0, i = 1, 2, . . . , n, el proceso anterior siemprepuede llevarse a cabo, y se puede describir de forma general como sigue:

Algoritmo 3.4 (de bajada)n = dimensión de APara cada i = 1, 2 . . . , n

xi =1

aii

bi − i−1∑j=1

aij xj

Fin

Se observa que para calcular cada xi, i = 1, 2, . . . n se necesitan: 1 divisióni− 1 productosi− 2 + 1 = i− 1 sumas

Sumando para i = 1, 2, . . . n, obtenemos que para la resolución de un sistema triangular inferior hacen falta:n∑i=1

1 + 2

n∑i=1

(i− 1) =

n∑i=1

1 + 2

n∑i=1

i− 2

n∑i=1

1 = 2n(n+ 1)

2− n = n2 + n− n = n2 operaciones.



Para un sistema lineal con matriz triangular superiora11 a12 . . . a1n0 a22 . . . a2n...

.... . .

...0 0 . . . ann

x1x2...xn

=

b1b2...bn

,se puede utilizar un procedimiento análogo, pero comenzando desde abajo hacia arriba, por lo cual se denominaalgoritmo de subida:

Algoritmo 3.5 (de subida)n = dimensión de APara cada i = n, . . . , 2, 1

xi =1

aii

bi − n∑j=i+1

aij xj

Fin

Haciendo el recuento de operaciones de manera análoga al algoritmo de bajada, se puede comprobar que laresolución del sistema lineal con la matriz triangular superior de dimensión n por algoritmo de subida requieren2 operaciones.

Ejemplo 3.6 Resolución de un sistema triangular superior x + 3y + z = 6y + z = 1

2z = −2⇒

xx = 6− 3y − z = 6− 6 + 1 = 1y = 1− z = 1− (−1) = 2z = −1

⇒

xyz

=

12−1

3.3 Sistemas equivalentes

Dos sistemas se dicen equivalentes si tienen las mismas soluciones. Determinadas operaciones pueden trans-formar un sistema en otro equivalente, por ejemplo:

1. Cambiar el orden de las ecuaciones de un sistema.

2. Multiplicar los dos miembros de una de las ecuaciones por el mismo número (distinto de cero).

3. Suprimir una ecuación que sea combinación lineal de las demás1.

4. Sustituir una ecuación por una combinación lineal de ella misma y alguna/s otra/s.

El método siguiente hace uso de estas propiedades para transformar un sistema dado en otro equivalente dematriz triangular superior que, como se ha visto, es «fácil» de resolver.

1Una combinación lineal de dos ecuaciones es otra ecuación obtenida multiplicando cada una de ellas por un número y luegosumándolas.



3.4 Método de Gauss

El método de Gauss el el método más sencillo de resolución de sistemas de ecuaciones lineales. Consta de dospartes bien diferenciadas:

1. Transformación del sistema lineal en otro equivalente (es decir con la misma solución) en el que la matrizsea triangular superior. Para ello se realizan dos operaciones elementales:

1.(a) Sumar a una ecuación otra multiplicándola por un número: en cada etapa del método se trata de«sustituir» por cero uno de los coeficientes por debajo de la diagonal. Para ello, y mediante lastransformaciones elementales, se sustituye la ecuación correspondiente por otra que haga el sistemaequivalente y que tenga nulo dicho coeficiente.

1.(b) Intercambiar dos ecuaciones.

2. Resolución del sistema triangular por el algoritmo de subida.

Si sólo usamos la opción 1.(a) hablaremos del método de Gauss sin pivote; y con pivote parcial si tambiénrealizamos las operaciones 1.(b), cuando la elección de las filas que se conmutan sea muy particular. Otraposibilidad es intercambiar columnas, que corresponde a reordenar las incógnitas. En este caso se habla delmétodo de Gauss con pivote total.

Desde el punto de vista práctico, es más fácil llevar las transformaciones sobre la forma matricial del sistema.Para ello se procede como sigue:

1. Se escribe el sistema en su forma matricial, Ax = b, donde A es una matriz, x es el vector de las incógnitasy b es el vector de los términos independientes.

2. Se construye la matriz ampliada correspondiente, que es una matriz que denotamos [A|b] que se formaañadiendo el vector b como última columna de la matriz A.

3. Se aplican operaciones elementales con las ecuaciones del sistema a las filas de la matriz ampliada.

3.4.1 Primeros ejemplos

Antes de hacer una descripción general del método de Gauss (que es bastante engorroso de escribir), vamosa presentar un ejemplo en un caso particular. Usaremos una notación abreviada para indicar las operacionesefectuadas. Por ejemplo:

F2 → −2F1 + F2

indica que se sustituye la segunda fila de la matriz ampliada (F2) por la suma de la primera fila multiplicadapor −2 más la segunda (−2F1 + F2).



Ejemplo 3.7 Resolución por el método de Gauss x − y − 2z = −12x − 3y + 4z = 45x − y + 3z = 16

1. Se comienza escribir el sistema de forma matricial Ax = b: 1 −1 −22 −3 45 −1 3

xyz

=

−14

16

⇒ [A|b] =

1 −1 −2 −12 −3 4 45 −1 3 16

2. A continuación se procede a aplicar las transformaciones adecuadas para anular el elemento a21 de la

matriz: se sustituye la segunda fila por la suma de la primera multiplicada por −2 más la segunda: 1 −1 −2 −12 −3 4 45 −1 3 16

−→F2 → −2F1 + F2

1 −1 −2 −10 −1 8 65 −1 3 16

3. Para anular el elemento a31 se sustituye la tercera fila por ella misma más la primera multiplicada por−5: 1 −1 −2 −1

0 −1 8 65 −1 3 16

−→F3 → −5F1 + F3

1 −1 −2 −10 −1 8 60 4 13 21

4. Una vez anulados todos los elementos sub-diagonales de la primera columna se pasa a hacer lo mismo

con la segunda. Es preciso a partir de ahora no utilizar la primera fila en las transformaciones, ya queeso modificaría los ceros ya conseguidos en la primera columna. Para anular el elemento a32 se sustituyela tercera fila por ella misma más la segunda multiplicada por 4: 1 −1 −2 −1

0 −1 8 60 4 13 21

−→F3 → 4F2 + F3

1 −1 −2 −10 −1 8 60 0 45 45

5. Con esto el sistema ya está en forma triangular, ya que todos los elementos por debajo de la diagonal

principal son nulos. Se resuelve, pues, despejando las incógnitas mediante el algoritmo de subida:

x − y − 2z = −1− y + 8z = 6

45z = 45⇒

xx = y + 2z − 1 = 2 + 2− 1 = 3y = 8z − 6 = 8− 6 = 2z = 1

⇒

xyz

=

321

El procedimiento anterior puede llevarse a cabo siempre y cuando el elemento diagonal de la columna sobrela que se está actuando no valga cero, ya que en este caso no es posible convertir en ceros los elementos dedicha columna que están por debajo de él. Lo que hay que hacer en este caso es permutar la fila del elementonulo con otra de más abajo que no tenga cero en esa columna. Intercambiar dos filas de la matriz ampliada esequivalente a intercambiar la posición de dos ecuaciones del sistema, y esto no cambia la solución. El siguienteejemplo muestra ese caso. La notación

Fi ↔ Fj

indica que se intercambian la fila i con la fila j.



Ejemplo 3.8 Resolución por el método de Gauss 2x − y + 3z = 64x − 2y + 6z = 9x − y + z = 3

1. Se comienza por trasformar en ceros los elementos sub-diagonales de la primera columna: 2 −1 3 64 −2 6 91 −1 1 3

−→F2 → 2F1 − F2

F3 → −0.5F1 + F3

2 −1 3 60 0 0 30 −0.5 −0.5 0

2. Para hacer las transformaciones necesarias en la segunda columna, se necesitaría que a22 fuera distinto

de cero. Como no lo es, se permutan las filas 2 y 3: 2 −1 3 60 0 0 30 −0.5 −0.5 0

−→F2 ↔ F3

2 −1 3 60 −0.5 −0.5 00 0 0 3

3. El sistema ya está en forma triangular, luego no es necesario seguir aplicando transformaciones: 2x − y + 3z = 6

− 0.5y − 0.5z = 00z = 3

4. La última ecuación de este sistema es 0 · z = 3, lo que es imposible. En consecuencia, el sistema no tienesolución: es incompatible.

Ejemplo 3.9 Resolución por el método de Gauss x − 3y + z = 4x − 2y + 3z = 6

2x − 6y + 2z = 8 1 −3 1 41 −2 3 62 −6 2 8

−→F2 → −F1 + F2

1 −3 1 40 1 2 22 −6 2 8

−→F3 → −2F1 + F3

1 −3 1 40 1 2 20 0 0 0

El sistema ya está en forma triangular, por lo que no es necesario continuar el procedimiento. La últimaecuación es 0 · z = 0 lo que significa que z puede tomar cualquier valor: z = α para cualquier α ∈ R. Lasegunda ecuación es y + 2z = 2, de donde se deduce qye y = 2− 2z = 2− 2α.Por último, de la primera ecuación se deduce x = 4− z + 3y = 4− α+ 3(2− 2α) = 10− 7α.

Así pues, el sistema tiene infinitas soluciones (una para cada valor de α), que son de la forma:

x = 10− 7α, y = 2− 2α, z = α, α ∈ R.

En este último ejemplo se muestra un caso de sistema que resulta indeterminado, ya que aparece una ecuaciónde la forma 0 · z = 0: esta ecuación se cumple siempre, es decir, para cualquier valor de z.



Ejemplo 3.10 Resolución por el método de Gauss 3x2 + 2x3 = 125x1 − 6x2 + 2x3 = −1−4x1 + 2x2 + x3 = 3

1. Se comienza por escribir el sistema de forma matricial Ax = b: 0 3 25 −6 2−4 2 1

x1x2x3

=

12−1

3

⇒ [A|b] =

0 3 2 125 −6 2 −1−4 2 1 3

2. Se intercambian la primera fila con la segunda y se comienza por trasformar en ceros los elementos

sub-diagonales de la primera columna:

0 3 2 125 −6 2 −1−4 2 1 3

−→F1 ↔ F2

5 −6 2 −10 3 2 12−4 2 1 3

−→F3 →

4

5F1 + F3

5 −6 2 −10 3 2 12

0 −14

5

13

5

11

5

3. Se anulan los elementos por debajo de a22:

5 −6 2 −10 3 2 12

0 −14

5

13

5

11

5

−→F3 →

14

15F2 + F3

5 −6 2 −10 3 2 12

0 067

15

67

5

4. El sistema ya está en forma triangular, luego no es necesario seguir aplicando transformaciones. Se

resuelve, pues, despejando las incógnitas mediante el algoritmo de subida:

5x1 − 6x2 + 2x3 = −1

3x2 + 2x3 = 1267

15x3 =

67

5

⇒

xx1 =

1

5(−1 + 12− 6) = 1

x2 =1

3(12− 6) = 2

x3 = 3

⇒

x1x2x3

=

123



Ejemplo 3.11 Resolución por el método de Gauss0 2 0 12 2 3 24 −3 0 16 1 −6 −5

x1x2x3x4

=

0−2−7

6

1. Se intercambian la primera fila con la segunda:

0 2 0 1 02 2 3 2 −24 −3 0 1 −76 1 −6 −5 6

−→F1 ↔ F2

2 2 3 2 −20 2 0 1 04 −3 0 1 −76 1 −6 −5 6

2. Se transforman en ceros los elementos sub-diagonales de la primera columna:

2 2 3 2 −20 2 0 1 04 −3 0 1 −76 1 −6 −5 6

−→F3 → −2F1 + F3

F4 → −3F1 + F4

2 2 3 2 −20 2 0 1 00 −7 −6 −3 −30 −5 −15 −11 12


2 2 3 2 −20 2 0 1 00 −7 −6 −3 −30 −5 −15 −11 12

−→F3 → 7/2F2 + F3

F4 → 5/2F2 + F4

2 2 3 2 −20 2 0 1 00 0 −6 1/2 −30 0 −15 −17/2 12


2 2 3 2 −20 2 0 1 00 0 −6 1/2 −30 0 −15 −17/2 12

−→F4 → −15/6F3 + F4

2 2 3 2 −20 2 0 1 00 0 −6 1/2 −30 0 0 −39/4 39/2

5. El sistema ya está en forma triangular, luego no es necesario seguir aplicando transformaciones. Se

resuelve, pues, despejando las incógnitas mediante el algoritmo de subida:

x

x1 =1

2(−2− 2x4 − 3x3 − 2x2) =

1

2(−2−+4− 1− 2) = −1

2

x2 =1

2(−x4) = 1

x3 = −1

6(−3− 1

2x4) = −1

6(−3 + 1) =

1

3x4 = −2

⇒

x1x2x3x4

=

−1/2

1−1/3

−3

Desde el punto de vista teórico y con vistas a formalizar el método de Gauss, observemos que podemos realizarlos pasos de una etapa a la siguiente mediante multiplicaciones por «matrices de paso», como muestran losejemplos que siguen.



Ejemplo 3.12 Resolución del sistema del Ejemplo 3.10 usando «matrices de paso» 0 3 25 −6 2−4 2 1

x1x2x3

=

12−1

3

Etapa 1: Sean A1 = A, b1 = b

[A1|b1] =

0 3 2 125 −6 2 −1−4 2 1 3

(a) Intercambio de filas en A1 y b1: F1 ↔ F2

P1A1 ≡

0 1 01 0 00 0 1

0 3 25 −6 2−4 2 1

=

5 −6 20 3 2−4 2 1

P1b1 ≡

0 1 01 0 00 0 1

12−1

3

=

−1123

(b) Anulación en la primera columna de P1A1 y P1b1 : F3 →

4

5F1 + F3

A2 := E1P1A1 ≡

1 0 00 1 045 0 1

5 −6 20 3 2−4 2 1

=

5 −6 20 3 20 − 14

5135

b2 := E1P1b1 ≡

1 0 00 1 045 0 1

−1123

=

−112

11/5

Etapa 2: Tenemos A2 y b2

(a) No hay que intercambiar filas: P2 = I, P2A2 = A2, P2b2 = b2.

(b) Anulación en la segunda columna de P2A2 y P2b2 : F3 →14

15F2 + F3

A3 := E2P2A2 ≡

1 0 00 1 00 14

15 1

5 −6 20 3 20 − 14

5135

=

5 −6 20 3 20 0 67

15

b3 := E2P2b2 ≡

1 0 00 1 00 14/15 1

−112

11/15

=

−112

67/5

A3 es una matriz triangular superior. Se resuelve el sistema resultante A3x = b3 mediante elalgoritmo de subida como en el Ejemplo 3.10.

Observaciones: Después de haber aplicado el método, resulta que

A3 = E2P2E1P1A1 = E2P2E1P1A ⇔ A3 = MA, M = E2P2E1P1.

En particular, el método de Gauss permite calcular el determinante de la matriz A:

det(A3) = det(E2) det(P2) det(E1) det(P1) det(A) = 1 · (1) · (1) · (−1) · det(A) = −det(A)

⇒ det(A) = − det(A3) = −5 · 3 · 67

15= −67



Ejemplo 3.13 Resolución del sistema del Ejemplo 3.11 usando «matrices de paso»0 2 0 12 2 3 24 −3 0 16 1 −6 −5

x1x2x3x4

=

0−2−7

6

Etapa 1: Sean A1 = A, b1 = b

(a) Intercambio de filas en A1 y b1: F1 ↔ F2

P1A1 ≡

0 1 0 01 0 0 00 0 1 00 0 0 1

0 2 0 12 2 3 24 −3 0 16 1 −6 −5

=

2 2 3 20 2 0 14 −3 0 16 1 −6 −5

P1b1 ≡

0 1 0 01 0 0 00 0 1 00 0 0 1

0−2−7

6

=

−2

0−7

6

(b) Anulación en la primera columna de P1A1 y P1b1 : F3 → −2F1 + F3 y F4 → −3F1 + F4

A2 := E1P1A1 ≡

1 0 0 00 1 0 0−2 0 1 0−3 0 0 1

2 2 3 20 2 0 14 −3 0 16 1 −6 −5

=

2 2 3 20 2 0 10 −7 −6 −30 −5 −15 −11

b2 := E1P1b1 ≡

1 0 0 00 1 0 0−2 0 1 0−3 0 0 1

−2

0−7−6

=

−2

0−312



(b) Anulación en la segunda columna de P2A2 y P2b2 : F3 → 7/2F2 + F3 y F4 → 5/2F2 + F3

A3 := E2P2A2 ≡

1 0 0 00 1 0 00 7/2 1 00 5/2 0 1

2 2 3 20 2 0 10 −7 −6 −30 −5 −15 −11

=

2 2 3 20 2 0 10 0 −6 1/20 0 −15 −17/2

b3 := E2P2b2 ≡ (−2, 0,−3, 12)t



(b) Anulación en la tercera columna de P3A3 y P3b3 : F4 → −15/6F3 + F4

A4 := E3P3A3 ≡

1 0 0 00 1 0 00 0 1 00 0 −15/6 1

2 2 3 20 2 0 10 0 −6 1/20 0 −15 −17/2

=

2 2 3 20 2 0 10 0 −6 1/20 0 0 −39/4

b4 := E3P3b3 ≡ (−2, 0,−3, 39/2)t

A4 es una matriz triangular superior. Se resuelve el sistema resultante A4x = b4 mediante elalgoritmo de subida como en el Ejemplo 3.11 .

Observación: Tenemos A4 = MA, siendo M = E3P3E2P2E1P1.



3.4.2 Matrices de permutación y «matrices de paso»

Se observa que las matrices P1, P2 y P3 que han aparecido en los ejemplos de la sección anterior son casosparticulares de matrices de permutación de las filas i y j:

P ij =

1 i) j)

. . .1

0 · · · · · · · · · 1... 1

......

. . ....

... 1...

1 · · · · · · · · · 01

. . .1

i)

j)

Dada una matriz A, se puede comprobar que la matriz P ijA es una matriz idéntica a A salvo que la filas i y jestán permutadas entre sí. Además,

det(P ij) =

{1 si i = j−1 si i 6= j

y (P ij)−1 = P ij .

En particular, la matriz P1 del Ejemplo 3.13 es P ij para i = 1 y j = 2, es decir

P1 = P 12 =

1) 2)0 1 0 01 0 0 00 0 1 00 0 0 1

1)

2)

Las matrices E1, E2 y E3 son casos particulares de «matrices de paso» del tipo

Ek =

11

. . .1

`k+1,k 1...

. . .`nk 1

.

Estas matrices son invertibles, pues det(Ek) = 1.En particular, la matriz E1 del Ejemplo 3.13, es la matiz Ek para k = 1:

E1 =

1 0 0 00 1 0 0−2 0 1 0−3 0 0 1

, P1A1 =

2 2 3 20 2 0 14 −3 0 16 1 −6 −5

, E1(P1A1) =

2 2 3 20 2 0 10 −7 −6 −30 −5 −15 −11

Se observa que `21 = 0, `31 = −2 y `41 = −3 son los números por los que hay que multiplicar la primera fila deP1A1 para que después de haberle sumado la correspondiente fila (dos, tres o cuatro) se obtengan ceros en laprimera columna por debajo del primer elemento.De manera general, en cada Ek el elemento ìk, i = k+1, k+2, . . . , n es el número por el que hay que multiplicar,en el paso k, la fila i-ésima para que al sumarle k-ésima, el elemento que ocupa la fila i y la columna k tome elvalor cero.



3.4.3 Estudio general del método de Gauss

Sea A = (aij) matriz cuadrada de orden n regular, es decir con det(A) 6= 0 (después veremos el caso en el quedet(A) = 0).

Etapa 1: Pongamos A1 = A, b1 = b. Vamos a generar A2 y b2 como sigue.

(a) Intercambio de filas.

• Si a11 = 0, como det(A) 6= 0, existe un índice i ∈ {2, . . . , n} tal que ai1 6= 0 (ver la Sección 3.4.4para sus posibles elecciones). Este elemento no nulo se denomina primer pivote.Intercambiamos la fila i del pivote ai1 con la primera fila, lo que equivale a multiplicar la matrizA1 por la izquierda por la matriz de permutación P1 ≡ P 1i definida en la sección anterior.

De la matriz A1 pasamos a tener, la matriz P1A1, cuyos elementos vamos a detonar por (α1ij)

ni,j=1,

con α111 = ai1 6= 0, y de b1 obtenemos P1b1, lo que esquemáticamente escribimos:

(A1|b1) −→ (P1A1|P1b1), P1A1 =

α111 α1

12 . . . α11n

α121 α1

22 . . . α12n

......

. . ....

α1n1 α1

n2 . . . α1nn

, det(P1) = −1.

• Si a11 6= 0, P1 = I, det(P1) = 1.

(b) Anulación en la primera columna de P1A1 por debajo de α111 = ai1 6= 0. Como hemos visto, esto

equivale a multiplicar P1A1 por la izquierda por E1:

(P1A1|P1b1) −→ (A2|b2) = (E1P1A1|E1P1b1), E1 =

1 0 . . . 0

−α121

α111

1 . . . 0

......

. . ....

−α1n1

α111

0 . . . 1

, det(E1) = 1.

Así obtenemos la matriz A2, cuya primera fila coincide con la de A1, y cuyos otros elementos vamosa denotar por a2ij :

A2 = E1P1A1 =

α111 α1

12 . . . α11n

0 a222 . . . a22n

......

. . ....

0 a2n2 . . . a2nn

Se observa que det(A2) = det(E1) det(P1) det(A1) = ±det(A1) = ±det(A) 6= 0 y que por otra parte,

det(A2) = α111 · det

a222 . . . a22n...

. . ....

a2n2 . . . a2nn

6= 0,

ya que α111 6= 0. Luego la submatriz que aparece en el determinante de A2 es regular.



Etapa k: Dados Ak = Ek−1Pk−1 · · ·E1P1A1 y bk = Ek−1Pk−1 · · ·E1P1b1, siendo Ak de la forma

Ak =

α111 α1

12 . . . α11,k−1 α1

1k . . . α11n

0 α222 . . . α2

1,k−1 α21k . . . α2

1n

......

. . ....

.... . .

...

0 0 . . . αk−1k−1,k−1 αk−1k−1,k . . . αk−1k−1,n

0 0 . . . 0 akkk . . . akkn

......

......

.... . .

...

0 0 . . . 0 aknk . . . aknn

, con det

akkk . . . akkn

.... . .

...

aknk . . . aknn

6= 0

Vamos a generar Ak+1 y bk+1 como sigue.

(a) Intercambio de filas.

• Si akkk = 0, existe un índice i ∈ {k + 1, . . . , n} tal que akik 6= 0, es el k-ésimo pivote.Intercambiamos la fila i del pivote akik con la k-ésima fila de Ak, lo que equivale a multiplicar lamatriz Ak por la izquierda por la matriz de permutación Pk ≡ P ik.De la matriz Ak pasamos a la matriz PkAk, cuyos elementos vamos a detonar por (αkij)

ni,j=1, con

αkkk = akik 6= 0, lo que esquemáticamente escribimos (Ak|bk) −→ (PkAk|Pkbk), siendo

PkAk =

α111 α1

12 . . . α11,k−1 α1

1,k α11,k+1 . . . α1

1n

0 α222 . . . α2

1,k−1 α21k α2

1,k+1 . . . α21n

......

. . ....

......

. . ....

0 0 . . . αk−1k−1,k−1 αk−1k−1,k αk−1k−1,k+1 . . . αk−1k−1,n

0 0 . . . 0 αkkk αkk,k+1 . . . αkkn

0 0 . . . 0 αkk+1,k αkk+1,k+1 . . . αkk+1,n

......

......

......

. . ....

0 0 . . . 0 αknk αkn,k+1 . . . αrnn

• Si akkk 6= 0, Pk = I, det(Pk) = 1.

(b) Anulación en la k-ésima columna de PkAk por debajo de αkkk = akik 6= 0 equivale a multiplicar PkAkpor la izquierda por Ek:

(PkAk|Pkbk) −→ (Ak+1|bk+1) = (EkPkAk|EkPkbk), Ek =

1. . . 0

11

−αkk+1,k

αkkk1

0...

. . .

−αkn,kαkkk

1

Así, obtenemos la matriz Ak+1 = EkPkAk de la forma



Ak+1 =

α111 α1

12 . . . α11,k−1 α1

1,k α11,k+1 . . . α1

1n

0 α222 . . . α2

1,k−1 α21k α2

1,k+1 . . . α21n

......

. . ....

......

......

0 0 . . . αk−1k−1,k−1 αk−1k−1,k αk−1k−1,k+1 . . . αk−1k−1,n

0 0 . . . 0 αkkk αkk,k+1 . . . αkkn

0 0 . . . 0 0 ak+1k+1,k+1 . . . ak+1

k+1,n

......

......

......

. . ....

0 0 . . . 0 0 ak+1n,k+1 . . . ak+1

nn

Como det(Ek) = 0 y det(Pk) = ±1, tenemos det(Ak+1) = det(Ek) det(Pk) det(Ak) = ±det(A1) =±det(A) 6= 0. Por otra parte,

det(Ak+1) = α111α

222 . . . α

kkk det

ak+1k+1,k+1 . . . ak+1

k+1,n

.... . .

...

ak+1n,k+1 . . . ak+1

nn

6= 0.

Luego la submatriz que aparece en el determinante de Ak+1 es regular.

Etapa n− 1: Si este proceso se lleva a cabo en n− 1 pasos, se obtiene que la matriz

An = En−1Pn−1 · · ·E1P1A1 = MA, con M = En−1Pn−1 · · ·E1P1

es triangular superior. La matriz M es invertible, ya que

det(M) =

{1 si γ es par−1 si γ es impar,

donde γ es el número de matrices de permutación distintas de la identidad.

En consecuencia,

Ax = b ⇔ MAx = Mb,

siendo MA matriz triangular superior.

Veamos que el método de Gauss es aplicable a matrices arbitrarias.

Teorema 3.14

Sea A una matriz de orden n (regular o no). Entonces existe una matriz regular M de orden n tal que lamatriz MA es triangular superior.

Demostración: El resultado ya está demostrado si A es regular. Observemos que sólo hemos usado quedet(A) 6= 0 para asegurar que, en cada etapa k del método, la existencia de algún akik 6= 0 con i ∈ {k, k+1, . . . , n}.En el caso de que todos estos elementos fueran nulos, la matriz Ak ya tendría la forma de Ak+1. Por tanto,bastaría tomar Pk = Ek = I y continuar el proceso.

�

Para resolver el sistema lineal Ax = b, con A = aij y bi, i, j = 1, . . . , n dados, el algoritmo de Gauss sin pivoteconsiste en lo siguiente:



Algoritmo 3.15 (de Gauss sin pivote - pseudocódigo)para resolver un sistema lineal Ax = b, n = dimensión de A

1. Tomar A1 = A, b1 = b, es decir a1ij = aij .

2. Dados Ak, bk, akij

Para k = 1, 2, . . . , n− 1

Para i = k + 1, k + 2, . . . , n

αik =akikakkk

Para j = k + 1, k + 2, . . . , nak+1ij = akij − αikakkj

Finbk+1 = bk − αikbi

Fin

Fin

Para i = n, n− 2, . . . , 1

xi =1

aii

bi − n∑j=i+1

aij xj

Fin

Se puede comprobar que el número de operaciones elementales efectuadas en el método de Gauss es del ordende 2n3/3. En la tabla que sigue se compara el número de operaciones necesarias para resolver un sistema linealde orden n usando el método de Gauss y la regla de Cramer:

n operaciones (Gauss) operaciones (Cramer)

10 805 399167999

100 681550 ∼ 10162

1000 668165500 ∼ 102573

3.4.4 Estrategia de elección del pivote

Hasta ahora hemos considerado como pivotes elementos cualesquiera siempre y cuando sean no nulos. Si enla etapa k-ésima en la descripción general del método de Gauss akkk 6= 0, pero es pequeño en relación a akikpara algún i, la división puede producir grandes errores de redondeo. En [2] se pueden encontrar ejemplos quemuestran este hecho. Por tanto, no es aconsejable elegir como pivotes números «muy pequeños». En la prácticase utiliza una de las estrategias siguientes al comienzo de la etapa k-ésima del método de Gauss:

Estrategia del pivote parcial o pivote máximo de columna: se toma como pivote el elemento de mayorvalor absoluto de entre los n− k últimos elementos de la columna k-ésima, es decir se elige akik, k ≤ i ≤ n,de la forma

|akik| = maxk≤p≤n

|akpk|.

A continuación, se intercambian las filas i y k. Este procedimiento suele ser suficiente para la mayoría desistemas lineales y es el que más se aplica en la práctica.

Estrategia del pivote total: se toma como pivote el elemento de mayor valor absoluto de la submatrizcorrespondiente a la matriz Ak, es decir en cada etapa k se elige el elemento akij que en valor absoluto esel mayor de entre los que están en la fila k o por debajo de ella y en la columna k o a la derecha de ella:



|akij | = maxk≤p,q≤n

|akpq|.

Si el pivote así elegido no está situado en la k-ésima columna, hay que efectuar un cambio de columnas,lo que equivale a multiplicar por la derecha la matriz Ak por una matriz P kj de permutación y significaque hay que cambiar el orden de las incógnitas, lo que habrá que tener en cuenta a la hora de escribir enel orden adecuado el resultado. Esta dificultad añadida hace que, en general, en el método de Gauss seutilice habitualmente la estrategia del pivote parcial.

3.5 Método de Gauss-Jordan

Se trata de una variante del método de Gauss que consiste en transformación del sistema lineal en otro equi-valente en el que la matriz del sistema sea diagonal. No es difícil adaptar la descripción general del método deGauss para conseguir una matriz diagonal en vez de la triangular superior (ver [2]). En cada etapa k, ademásse harían ceros los elementos extradiagonales en la columna k. Para ello harían falta n etapas, frente a n − 1etapas del método de Gauss.

Ejemplo 3.16 Resolución por el método de Gauss-Jordan2x1 + x2 − 3x3 = −1

−x1 + 3x2 + 2x3 = 12

3x1 + x2 − 3x3 = 0

1. Se comienza por trasformar en ceros los elementos sub-diagonales de la primera columna, como en elmétodo de Gauss:

2 1 −3 −1

−1 3 2 12

3 1 −3 0

−→

F2 → 12F1 + F2

F3 → − 32F1 + F3

2 1 −3 −1

0 7/2 1/2 23/2

0 −1/2 3/2 3/2

2. En la segunda columna, hay que anular los elementos por debajo de a22 y los encima de él:

2 1 −3 −1

0 7/2 1/2 23/2

0 −1/2 3/2 3/2

−→

F3 → 17F2 + F3

F1 → − 27F2 + F1

2 0 −22/7 −30/7

0 7/2 1/2 23/2

0 0 11/7 22/7

3. En la tercera columna, se anulan los elementos por encima de a33:

2 0 −22/7 −30/7

0 7/2 1/2 23/2

0 0 11/7 22/7

−→

F1 → 2F3 + F1

F2 → − 722

F3 + F2

2 0 0 2

0 7/2 0 21/2

0 0 11/7 22/7

4. El sistema ya está en la forma diagonal y las incógnitas se calculan despejando: x1 = 1, x2 = 3, x3 = 2.



Observaciones:

1. En el método de Gauss-Jordan, también se pueden aplicar las estrategias del pivote parcial o total.

2. Aunque el sistema que queda por resolver después de haber aplicado el método de Gauss-Jordan es mássencillo que en el método de Gauss (sólo hay que hacer divisiones para despejar las incógnitas), el númerode operaciones que hay que realizar es mayor que en el de Gauss y en general no compensa.

3. Si A no es regular, no se puede asegurar la obtención de una matriz diagonal, es decir aplicar el métodode Gauss-Jordan. En efecto, si todos los elementos a partir de k-ésimo son cero en una columna, no sepuede seguir el proceso.

3.5.1 Aplicación al cálculo de la inversa de una matriz

Como hemos dicho, el método de Gauss-Jordan no presenta ventajas sobre el método de Gauss para resolver unsistema lineal, en cambio puede tener interés en el cálculo de la inversa de una matriz. Se procede como sigue.Sea A−1 = [c1|c2| · · · |cn] la matriz inversa de A, cuyas columnas hemos llamado ci, i = 1, . . . , n. Hallar la inversade A equivale a calcular los n vectores-columna ci tales que

Aci = ei, i = 1, . . . , n,

siendo {e1, e2, . . . , en} los vectores de la base canónica de Rn. Así, calcular A−1 equivale a resolver n sistemaslineales, todos con la misma matriz A de coeficientes. Esto permite hacer una resolución conjunta de los nsistemas lineales por el método de Gauss-Jordan. Se escribe [A|I] y tras n + 1 etapas del método de Gauss-Jordan se llega a [I|C], siendo C = A−1.

Ejemplo 3.17 Usando el método de Gauss-Jordan, calcular la inversa de la matriz

A =

2 3

4 7

(3.4)

Se escribe la matriz [A|I] y se aplica el método de Gauss-Jordan hasta obtener una matriz de la forma [I|C].Entonces C = A−1.

[A|I] =

2 3 1 0

4 7 0 1

−→

F2 → −2F1 + F2

2 3 1 0

0 1 −2 1

−→

F1 → −3F2 + F1

2 0 7 −3

0 1 −2 1

2 0 7 −3

0 1 −2 1

−→

F1 →1

2F1

1 0 7/2 −3/2

0 1 −2 1

= [I|A−1] ⇒ A−1 =

7/2 −3/2

−2 1

.

Observemos que para calcular A−1 podíamos haber resuelto los n sistemas lineales (3.4) por el método deGauss, obteniendo así n sistemas con una matiz triangular superior. No obstante, el método de Gauss-Jordan elmás ventajoso en este caso: la diagonalización de la matriz es algo más laboriosa que la triangularización, peromerece la pena, pues la resolución de n sistemas triangulares es más larga que de n diagonales.



3.6 Método de factorización LU

Sea A una matriz cuadrada regular de orden n y b ∈ Rn y consideramos el sistema lineal

Ax = b.

El método LU

para resolver el sistema lineal Ax = b consta de dos etapas:

Factorización: Escribimos, si es posible, la matriz A como producto de dos matrices

A = LU

con L triangular inferior con unos en la diagonal principal y U una matriz triangular superior. Estadescomposición se llama factorización LU de A (L viene de «lower» en inglés y U de «upper»).

Resolución del sistema: Una vez obtenida la factorización A = LU , escribimos

Ax = b ⇔ LUx = b

Pongamos Ux = v y resolvemos el sistema lineal Lv = b por el algoritmo de bajada, obteniendo v.

Dado v, resolvemos el sistema lineal Ux = v por el algoritmo de subida, obteniendo x, la solucióndel sistema original.

La cuestión que tenemos que responder ahora es cuándo es posible obtener la factorización LU de una matriz.Se observa que si en el método de Gauss no es necesario intercambiar filas, ni tampoco aplicar la estrategia delpivote, tal factorización existe (ver el Ejemplo 3.18).En efecto, si A es regular y al aplicar el método de Gauss no es necesario intercambiar filas, porque en cadaetapa k, akkk 6= 0 para todo k, se tiene que

P1 = P2 = · · · = Pn−1 = I.

En este caso, hemos visto que en la etapa n− 1 del método de Gauss

An = (En−1 · · ·E1)A,

siendo An triangular superior y (En−1 · · ·E1) triangular inferior con diagonal de unos. Luego

A = (En−1 · · ·E1)−1An := LU,

con L = (En−1 · · ·E1)−1 triangular inferior con 1 en la diagonal y U = An triangular superior.

Aquí, hemos usado las siguientes propiedades de matrices triangulares, que son fáciles de comprobar:

Si A = (aij) y B = (bij), i, j = 1, . . . , n son matrices triangulares superiores (resp. inferiores), entoncesla matriz AB (el producto de A por B) es también triangular superior (resp. inferior) y los elementosdiagonales de la matriz AB son de la forma

(AB)ii = aiibii, ∀ i = 1, . . . , n.

Si A es triangular superior (resp. inferior) y aii 6= 0 para todo i, luego det(A) = a11 · a22 · · · ann 6= 0 yexiste A−1 que también es triangular superior (resp. inferior) y los elementos diagonales de A−1 son de laforma

(A−1)ii =1

aii∀ i.



Ejemplo 3.18 Resolver por el método LU el sistema lineal5 2 1

5 −6 2

−4 2 1

x1

x2

x3

=

12

−1

3

Factorización: Si aplicamos el método de Gauss sin intercambiar filas, obtendremos A = LU . En efecto,

sean A1 = A y P1 = I, luego

E1 =

1 0 0

−1 1 0

4/5 0 1

, A2 = E1A1 =

5 2 1

0 −8 1

0 18/5 9/5

Tenemos ahora P2 = I y

E2 =

1 0 0

0 1 0

0 9/20 1

, A3 = E2A2 =

5 2 1

0 −8 1

0 0 9/4

En consecuencia, A3 = E2A2 = E2E1A, luego

A = (E2E1)−1A3 = E−11 E−12 A3 =

1 0 0

1 1 0

−4/5 0 1

1 0 0

0 1 0

0 −9/20 1

5 2 1

0 −8 1

0 0 9/4

⇒

A =

1 0 0

1 1 0

−4/5 −9/20 1

5 2 1

0 −8 1

0 0 9/4

≡ LUResolución del sistema: Pongamos Ux = b y resolvemos Lv = b usando el algoritmo de bajada:

v1 = 12

v1 + v2 = −1

−4

5v1 − 9

20v2 + v3 = 3

⇒

yv1 = 12

v2 = −1− v1 = −1− 12 = −13

v3 = 3 +9

20(−13) +

4

5(12) =

27

4

⇒

v1

v2

v3

=

12

−1327

4

Resolvemos ahora Ux = v por el algoritmo de subida

5x1 + 2x2 + x3 = 12

− 8x2 + x3 = −13

9/4x3 = 27/4

⇒

xx1 = (12− 2x2 − x3)/5 = 1

x2 = (13 + x3)/8 = 2

x3 = 3

⇒

x1

x2

x3

=

1

2

3

Queda establecer cuándo no es necesario permutar filas al aplicar el método de Gauss (es decir tomar Pk = I,∀ k) para asegurar la descomposición LU de A. A continuación vamos a dar una condición suficiente para quese pueda llevar a cabo el método de Gauss sin permutar filas, es decir realizar la factorización LU.



3.6.1 Condición suficiente de existencia y unicidad de la factorización LU

Submatrices principales y menores principales

Sea A una matriz cuadrada de orden n. Se llaman submatrices principales de orden k, 1 ≤ k ≤ n de A alas matrices formadas por las primeras k filas y columnas de A.Los determinantes de estas matrices se denominan menores principales o determinantes principales:

∆k := det

a11 · · · a1k...

. . ....

ak1 · · · akk

, k = 1, . . . , n

Teorema 3.19 Factorización LUSea A una matriz cuadrada de orden n tal que todos los menores principales de orden k, ∆k, k = 1, . . . , n seanno nulos.Entonces existe una matriz L = (ìj) triangular inferior, con ìi = 1, i = 1, . . . , n y existe una matriz Utriangular superior tales que A = LU . Además, dicha factorización es única.

Demostración:

Existencia: Basta demostrar que bajo las hipótesis del teorema, al aplicar el método de Gauss no es necesariointercambiar filas, es decir akkk 6= 0 ∀ k.Vamos a razonar por inducción sobre la dimensión de la matriz.

Para k = 1, ∆1 = a11 6= 0, luego P1 = I.

Supongamos que ∆k 6= 0, ∀ k y que hemos podido elegir P1 = P2 = · · · = Pk−1 = I. Veamosque también podemos tomar Pk = I. En efecto, como P1 = P2 = · · · = Pk−1 = I, obtenemosAk = (Ek−1 · · ·E1)A, siendo Ek−1Ek−2 · · ·E1 una matriz triangular inferior con 1 en la diagonalprincipal.La igualdad Ak = (Ek−1 · · ·E1)A se escribe en forma matricial como sigue:

Ak =

a111 . . . a11k a11,k+1 . . . a11n...

. . ....

......

...

0 . . . akkk akk,k+1 . . . akkn

0 . . . akk+1,k akk+1,k+1 . . . akkn...

. . ....

.... . .

...

0 . . . aknk akn,k+1 . . . aknn

=

1 . . . 0 0 . . . 0...

. . ....

.... . .

...

`k1 . . . 1 0 . . . 0

`k+1,1 . . . `k+1,k 1 . . . 0...

. . ....

.... . .

...

`n1 . . . `nk `n,k+1 . . . 1

a11 . . . a1k a1,k+1 . . . a1n...

. . ....

.... . .

...

ak1 . . . akk ak,k+1 . . . akn

ak+1,1 . . . ak+1,k ak+1,k+1 . . . ak+1,n

.... . .

......

. . ....

an1 . . . ank an,k+1 . . . ann

Haciendo la multiplicación de matrices por bloques, el primer bloque queda:



a111 . . . a11k...

. . ....

0 . . . akkk

=

1 . . . 0...

. . ....

`k1 . . . 1

a11 . . . a1k...

. . ....

ak1 . . . akk

,de donde, tomando determinantes, tenemos

k∏i=1

aiii = 1 · det

a11 . . . a1k...

. . ....

ak1 . . . akk

= 1 ·∆k 6= 0 ⇒ aiii 6= 0, i = 1, 2 . . . k.

En particular, akkk 6= 0, luego podemos elegir akkk como pivote y, en consecuencia Pk = I.

Unicidad: Supongamos que existen L1 , L2 triangulares inferiores con (L1)ii = (L2)ii = 1, i = 1, . . . , n y U1 , U2

triangulares superiores tales queL1U1 = A = L2U2.

Como det(L1) = det(L2) = 1 y det(U1) = det(U2) = det(A) = ∆n 6= 0, entonces existen L−1i , U−1i ,i = 1, 2.

Por otra parte, L1U1 = L2U2, luego

L−12 L1U1U−11 = L−12 L2U2U

−11 ⇔ L−12 L1 = U2U

−11 ⇔ L−12 L1 = U2U

−11 = I,

pues L−12 L1 es triangular inferior con diagonal de unos y U2U−11 es triangular superior. Luego, necesaria-

mente L2 = L1 y U1 = U2. Esto termina la demostración.

�

Observación: La factorización LU de matrices invertibles es siempre posible. Si la condición del Teorema 3.19no se verifica, pero A es invertible, se puede comprobar (ver [2]) que se pueden efectuar permutaciones defilas para que los menores principales de matrices resultantes sean distintos de cero, es decir existe P tal quePA = LU (ver Ejemplo 3.20).

Ejemplo 3.20 Comprobar que la matriz A no cumple las condiciones del Teorema 3.19.Comprobar que permutando las filas de A, se puede obtener una matriz que cumple las condi-ciones del dicho teorema.

A =

1 −1 2

2 −2 3

−1 4 1

Tenemos ∆1 = 1, ∆2 =

∣∣∣∣∣∣ 1 −1

2 −2

∣∣∣∣∣∣ = −2 + 2 = 0, det(A) = 3. Por tanto al ser ∆2 = 0, no se cumplen las

hipótesis del Teorema 3.19 y, en consecuencia, no podemos asegurar la existencia de la factorización LU de A.Observemos que permutando la primera fila de A con la tercera, obtenemos PA que sí admite factorizaciónLU:

PA =

0 0 1

0 1 0

1 0 0

1 −1 2

2 −2 3

−1 4 1

=

−1 4 1

2 −2 3

1 −1 2

, ∆1 = −1, ∆2 = −6, ∆3 = −3



3.6.2 Caso particular: matrices con la diagonal dominante

Matriz con la diagonal estrictamente dominante

Sea A una matriz cuadrada de orden n. Se dice que A es de diagonal estrictamente dominante si

|aii| >n∑

j=1,i6=j

|aij |, i = 1, . . . , n.

Ejemplo 3.21La siguiente matriz es de diagonal estrictamente dominante:

A =

−4 −1 2

2 7 3

−3 4 10

,puesto que

| − 4| > | − 1|+ |2| = 3

|7| > |2|+ |3| = 5

|10| > | − 3|+ |4| = 7.

Teorema 3.22Sea A una matriz cuadrada de orden n de diagonal estrictamente dominante. Entonces A es regular. Además,existe una única factorización LU de A.

Demostración: Para probar que A es invertible (regular) veamos que la única solución del sistema linealhomogéneo Az = 0 es z = 0.Por reducción al absurdo, supongamos que A es singular, es decir existe z ∈ Rn, z 6= 0 tal que Az = 0.Sea p ∈ {1, 2, . . . , n} tal que

|zp| = max1≤i≤n

|zi| ⇒ |zi| ≤ |zp|, ∀ i = 1, 2, . . . , n.

Como z 6= 0, tenemos zp 6= 0 y el hecho que Az = 0 se escribe

n∑j=1

apjzj = 0, ∀ p = 1, 2, . . . , n ⇔ appzp +

n∑j=1,j 6=p

apjzj = 0, ⇒ appzp = −n∑

j=1,j 6=p

apjzj .

Luego, como|zj ||zp|≤ 1, se tiene

|app||zp| ≤n∑

j=1,j 6=p

|apj ||zj | ⇒ |app| ≤n∑

j=1,j 6=p

|apj ||zj ||zp|≤

n∑j=1,j 6=p

|apj |,

lo que está en contradicción con que A es de diagonal estrictamente dominante. Por tanto, z = 0 y A es regular.

Como A es de diagonal estrictamente dominante, entonces todas las submatrices principales son estrictamentediagonal dominantes y, por tanto regulares, es decir sus determinantes (que son menores principales) son distintosde cero. En consecuencia, gracias al Teorema 3.19 existe una única factorización LU de tal matriz.

�



3.6.3 Cálculo efectivo de la factorización LU

Los elementos del las matrices L y U pueden calcularse, directamente, a partir de los elementos de la matriz A.Para ello, basta considerar la igualdad A = LU , elemento a elemento, teniendo en cuenta que L es triangularinferior tal que ìi = 1 y que U es triangular superior.

Ejemplo 3.23 Calcular la factorización LU de la matriz

A =

2 −1 0

−1 2 −1

0 −1 2

Escribimos

LU =

1 0 0

`21 1 0

`31 `32 1

u11 u12 u13

0 u22 u23

0 0 u33

=

u11 u12 u13

`21u11 `21u12 + u22 `21u13 + u23

`31u11 `31u12 + `32u22 `31u13 + `32u23 + u33

Comparando lo obtenido con los elementos de A, vamos calculando las filas de U y las columnas de L:

A = LU ⇔

2 −1 0

−1 2 −1

0 −1 2

=

u11 u12 u13

`21u11 `21u12 + u22 `21u13 + u23

`31u11 `31u12 + `32u22 `31u13 + `32u23 + u33

u11 = 2, u12 = −1, u13 = 0

−1 = `21u11 ⇒ `21 = − 1

u11= −1

2

0 = `31u11 ⇒ `31 = 0

2 = `21u12 + u22 ⇒ u22 = 2− `21u12 = 2− (−1

2)(−1) = 2− 1

2=

3

2

−1 = `21u13 + u23 ⇒ u23 = −1

−1 = `31u12 + `32u22 ⇒ `32 =1

u22(−1− `31u12) = −2

3

2 = `31u13 + `32u23 + u22 ⇒ u33 = (2− `31u13 + `32u23) = 2− 2

3=

4

3

Por tanto,

A = LU =

1 0 0

−1/2 1 0

0 −2/3 1

2 −1 0

0 3/2 −1

0 0 4/3

.



Para una matriz de orden n, se razona de forma similar: se calculan los elementos de L y U directamente,elemento a elemento.

a11 a12 · · · a1,n−1 a1n

a21 a22 · · · a2,n−1 a2n

· · · · · · · · · · · · · · ·

an1 an2 · · · an,n−1 ann

=

1 0 · · · 0 0

`21 1 · · · 0 0

· · · · · · · · · · · · · · ·

`n1 `n2 · · · `n,n−1 1

u11 u12 · · · u1,n−1 u1n

0 u22 · · · u2,n−1 u2,n

· · · · · · · · · · · · · · ·

0 0 · · · 0 unn

Haciendo las multiplicaciones de las matrices de la derecha y comparando e igualando con las filas de A, vamosobteniendo las filas de U y las columnas de L.

Multiplicamos la 1a fila de L por las columnas de U obtenemos 1a fila de A:

u1j = a1j , j = 1, . . . , n

Multiplicamos todas las filas de L (salvo la 1a) por la 1a columna de U , obtenemos la 1a columna de A(salvo el 1er. elemento):

ai1 = ì1u11, i = 2, . . . , n ⇒ ì1 =ai1u11

, i = 2, . . . , n

Multiplicamos la 2a fila de L por las columnas de U (salvo la 1a), obtenemos la 2a fila de A (salvo el 1er.elemento):

a2j = `21u1j + u2j , j = 2, . . . , n ⇒ u2j = a2j − `21u1j , j = 2, . . . , n

Multiplicamos las filas de L (salvo las 2 primeras) por la 2a columna de U , obtenemos 2a columna de A:

ai2 = ì1u12 + ì2u22, i = 3, . . . , n ⇒ ì2 =1

u22(ai2 − ì1u12), i = 3, . . . , n

Supongamos conocidas (k − 1) primeras filas de U y las (k − 1) primeras columnas de L. Multiplicamosla ka fila de L por las columnas de U (salvo las (k − 1) primeras), obtenemos ka fila de A: teniendo encuenta que `kp = 0, para p = k + 1, . . . , n y `kk = 1

akj =

n∑p=1

`kpupj =

k−1∑p=1

`kpupj + 1 · ukj , j = k, . . . , n ⇒ ukj = akj −k−1∑p=1

`kpupj , j = k, . . . , n

Multiplicamos las filas de L (salvo las primeras k) por la columna k de U , obtenemos la ka columna deA: teniendo en cuenta que ukp = 0, para p = k + 1, . . . , n

aik =

n∑p=1

ìpupk =

k−1∑p=1

ìpupk + ìkukk, ⇒ ìk =1

ukk(aik −

k−1∑p=1

ìpupk), i = k + 1, . . . , n



Algoritmo 3.24 (de factorización LU)n = dimensión de APara cada k = 1, 2 . . . , n

ukj = akj −k−1∑p=1

`kpupj , j = k, k + 1, . . . , n

ìk =1

ukk(aik −

k−1∑p=1

ìpupk), i = k + 1, k + 2 . . . , n

Fin

Observaciones:

1. La factorización LU obtenida, se conoce también como factorización LU de Doolittle.

2. Si en el cálculo efectivo de la factorización LU de una matriz A obtenemos uii = 0 para algún i, entoncespodemos concluir que A no admite tal factorización.

3. Se puede comprobar, haciendo el recuento de operaciones de método LU (factorización LU junto con laresolución por subida y bajada de dos sistemas lineales) que, el número de operaciones es aproximadamentedel mismo orden que en el método de Gauss (que suele ser más conveniente para matrices cualesquiera).Cuando se quieren resolver varios sistemas lineales con la misma matriz, es mejor usar el método LU, paraobtener un considerable ahorro en el tiempo de cálculo.

4. Por otra parte, es posible demostrar que la factorización LU conserva la estructura de matrices «banda»,es decir si aij = 0 para |i− j| ≥ p, entonces ìj = 0 para i− j ≥ p y uij = 0 para j − i ≥ p. En particular,las matrices tridiagonales (p = 2) poseen esta propiedad, de hecho su factorización es particularmentesimple (ver los Ejemplos 3.23 y 3.26).



3.6.4 Factorización LU de Crout

Es posible también descomponer A en la forma A = LU , con L triangular inferior (con la diagonal general) yU triangular superior con la diagonal de unos. Dicha factoriazación se conoce como factorización LU de Crout.

Ejemplo 3.25 Calcular la factorización de Crout de la matriz

A =

1 −2 3

4 −6 0

−5 6 1

1 −2 3

4 −6 0

−5 6 1

=

`11 0 0

`21 `22 0

`31 `32 `33

1 u12 u13

0 1 u23

0 0 1

Multiplicando las matrices de la derecha y comparando con los elementos de A, obtenemos:

`11 = 1, `21 = 4, `31 = −5

−2 = `11u12 ⇒ u12 = − 2

`11= −2

3 = `11u13 ⇒ u13 =3

`11= 3

−6 = `21u12 + `22 ⇒ `22 = −6− `21u12 = −6 + 8 = 2

6 = `31u12 + `32 ⇒ `32 = 6− `31u12 = 6− (−5)(−2) = 6− 10 = −4

0 = `21u13 + `22u23 ⇒ u23 =1

`22(−`21u13) = −12

2= −6

1 = `31u13 + `32u23 + `33 ⇒ `33 = (1− `31u13 − `32u23) = 1 + 15− 24 = −8

A = LU =

1 0 0

4 2 0

−5 −4 −8

1 −2 3

0 1 −6

0 0 1

.

Observaciones:

1. Se observa que la factorización de Crout puede obtenerse también a partir de la factorización LU de Doo-little y recíprocamente. En efecto, dada A = LU , con uii 6= 0, i = 1, . . . , n, sea D = diag(u11, u22, . . . , unn)la matriz diagonal de los elementos uii, i = 1, . . . , n. Podemos escribir:

A = LU = LDD−1U ≡ LU , donde L = LD, U = D−1U, D = diag(u11, u22, . . . , unn)

Recíprocamente, dada A = LU , con ìi 6= 0, i = 1, . . . , n (los elementos diagonales de L), consideramosD = diag(`11, `22, . . . , `nn) la matriz diagonal de los elementos ìi, i = 1, . . . , n. Podemos escribir

A = LU = LD−1DU ≡ LU, donde L = LD−1, U = DU, D = diag(`11, `22, . . . , `nn)

2. Si A es simétrica y A = LU , entonces

A = At = (LU)t = U tLt ≡ LU ,

puesto que U t := L es triangular inferior con la diagonal general y Lt := U es triangular superior con ladiagonal de unos.



Ejemplo 3.26 Obtener la factorización de Crout de la matriz A. A partir de ella obtener lafactorización LU de Doolittle.

A =

a −1 0 0 0

−1 4/a −1 0 0

0 −1 a −1 0

0 0 −1 4/a −1

0 0 0 −1 a

, a ∈ R \ {0}

a −1 0 0 0

−1 4/a −1 0 0

0 −1 a −1 0

0 0 −1 4/a −1

0 0 0 −1 a

=

`11 0 0 0 0

`21 `22 0 0 0

0 `32 `33 0 0

0 0 `43 `44 0

0 0 0 `54 `55

1 u12 0 0 0

0 1 u23 0 0

0 0 1 u34 0

0 0 0 1 u45

0 0 0 0 1

Multiplicando las matrices de la derecha y comparando con los elementos de A, obtenemos:

`11 = a, `21 = −1

−1 = `11u12 ⇒ u12 = − 1

`11= −1/a

4/a = `21u12 + `22 ⇒ `22 = 4/a− `21u12 = 4/a− (−1)(−1/a) = 3/a

−1 = `22u23 ⇒ u23 = −a/3

a = `32u23 + `33 ⇒ `33 = a− a/3 = 2a/3

−1 = `33u34 ⇒ u34 = −3/(2a)

−1 = `43 ⇒ `43 = −1

4/a = `43u34 + `44 ⇒ `44 = −5/(2a)

−1 = `44u45 ⇒ `45 = −2a/5

`54 = −1, `55 = a

A = LU =

a 0 0 0 0

−1 3/a 0 0 0

0 −1 2a/3 0 0

0 0 −1 5/(2a) 0

0 0 0 −1 a

1 −1/a 0 0 0

0 1 −a/3 0 0

0 0 1 −3/(2a) 0

0 0 0 1 −2a/5

0 0 0 0 1

Como A es simétrica y A = LU , entonces

A = At = (LU)t = U tLt ≡ LU,

ya que U t := L es triangular inferior de diagonal de unos y Lt := U es triangular superior de diagonal general.



3.7 Método de Cholesky

Consideramos el sistema lineal

Ax = b,

donde A es una matriz simétrica y definida positiva (ver la Sección 3.7.1).

El método de Cholesky

para resolver el sistema lineal Ax = b con A matriz simétrica y definida positiva, consta de dos etapas:

Factorización: Escribimos la matriz A como producto de dos matrices

A = BBt, B triangular inferior

Esta descomposición se llama factorización de Cholesky de A.

Resolución del sistema: Una vez obtenida la factorización A = BBt, escribimos

Ax = b ⇔ BBtx = b

Pongamos Btx = v y resolvemos el sistema lineal Bv = b por el algoritmo de bajada, obteniendo v.

Dado v, resolvemos el sistema lineal Btx = v por el algoritmo de subida, obteniendo x, la solucióndel sistema original.

En lo que sigue, hablaremos de las matrices definidas positivas y justificaremos la existencia de la factorizaciónde Cholesky.

3.7.1 Matrices definidas y sus propiedades

Matriz definida positiva

Sea A una matriz cuadrada de orden n de coeficientes reales. Se dice que A es de definida positiva si

vtAv > 0 para todo v ∈ Rn \ {0} ⇔n∑i=1

n∑j=1

aijvivj > 0 ∀ v ∈ Rn \ {0} (3.5)

En efecto, la relación vtAv > 0 se escribe por componentes como sigue:

vtAv = (v1, . . . , vn)

a11 . . . a1n...

. . ....

an1 . . . ann

v1...

vn

= (v1, . . . , vn)

n∑j=1

a1jvj

...n∑j=1

anjvj

= v1

n∑j=1

a1jvj + · · ·+ vn

n∑j=1

anjvj =

n∑i=1

n∑j=1

aijvi vj



Ejemplo 3.27 Demostrar que la matriz A =

2 1

−1 2

es definida positiva

Sea v ∈ R2 \ {0}, tenemos

vtAv = (v1, v2)

2 1

−1 2

v1

v2

= (v1, v2)

2v1 + v2

−v1 + 2v2

= 2v21 + v1v2 − v1v2 + 2v22 = 2(v21 + v22) > 0

Proposición 3.28 (Propiedades de matrices definidas positivas)

1. Si A es definida positiva, entonces A es regular.

2. Si A es definida positiva, entonces todas las submatrices principales de orden k, Ak, k = 1, . . . , n sondefinidas positivas.

3. A es definida positiva y B es regular ⇐⇒ la matriz BABt es definida positiva

Demostración:

1. Como A es definida positiva, se tiene vtAv > 0 para todo v ∈ Rn\{0}. Luego Av 6= 0 para todo v ∈ Rn\{0}y, en consecuencia, A es regular.

2. Fijado k ≤ n, sea Ak la submatriz principal de orden k. Sea w ∈ Rk \ {0} (arbitrario), conw = (w1, . . . , wk)t. Tomamos v ∈ Rn \ {0} tal que v = (w1, . . . , wk, 0, . . . , 0)t. Usando que A es defi-nida, positiva podemos escribir:

0 < vtAv = wtAk w, ∀w ∈ Rk \ {0},

lo que implica que Ak es definida positiva.

3. =⇒ Supongamos que A es definida positiva y B es regular. Sea w ∈ Rn \ {0} vector arbitrario. EntoncesBtw 6= 0, pues B es regular. Como A es definida positiva, tomando en (3.5) v = Btw, podemos escribir:

0 < vtAv = (Btw)tABtw, ∀Btw ∈ Rn \ {0} ⇔ 0 < wtBABtw ∀w ∈ Rn \ {0},

lo que implica que la matriz BABt es definida positiva.

⇐= Supongamos que BABt es definida positiva. Veamos primero que B es regular. Por reducción alabsurdo, si B fuera singular, existe v 6= 0 tal que Btv = 0. Así,

0 = (Btv)tABtv = vt(BABt)v, v 6= 0,

lo que estaría en contradicción con que BABt es definida positiva, luego B es regular.Veamos ahora A es definida positiva. Sea v ∈ Rn \ {0}, entonces w = (B−1)tv 6= 0, pues B es regular.Usando que BABt es definida positiva, tenemos

vtAv = vtB−1BABt(B−1)tv = (vtB−1)BABt(B−1)tv = ((B−1)tv)tBABt(B−1)tv ≡ wtBABtw > 0,

lo que implica que A es definida positiva.�



3.7.2 Factorización de Cholesky

Teorema 3.29 Factorización de CholeskySea A una matriz cuadrada de orden n, simétrica y definida positiva. Entonces existe al menos una matriz Btriangular inferior tal que

A = BBt.

Además, se puede imponer que bii > 0, i = 1, . . . , n, en cuyo caso la factorización es única.

Demostración:

Existencia: Como A es definida positiva, según la Proposición 3.28 todas las submatrices principales sondefinidas positivas y, por tanto regulares, es decir ∆k 6= 0 ∀ k. En consecuencia, por el Teorema 3.19 existeuna única factorización LU de A: A = LU , siendo L una matriz triangular inferior de diagonal de unos yU una matriz triangular superior.

Como A es simétrica, se tiene At = A, luego teniendo en cuenta que A = LU y At = U tLt obtenemos

At = A ⇔ U tLt = LU ⇔ L−1U tLt(Lt)−1 = L−1LU(Lt)−1 ⇔ L−1U t = U(Lt)−1

Como L−1U t es una matriz triangular inferior y U(Lt)−1 es triangular superior y ambas coinciden, nece-sariamente tienen que ser una matriz diagonal, es decir

D := U(Lt)−1 = diag (u11, . . . , unn) ⇒ U = DLt ⇒ A = LU = LDLt (3.6)

Por ser A definida positiva, la matriz A = LDLt es definida positiva, luego según la Proposición 3.28, lamatriz D es definida positiva. Además, dii > 0, para todo i = 1, . . . , n, ya que

(ek)tDek =

n∑i,j=1

dijeki ekj = dkk > 0, ∀ k = 1, . . . , n,

donde ek es el k-ésimo vector de la base canónica de Rn.

Si denotamos por D1/2 = diag(√d11, . . . ,

√dnn), obtenemos

A = LDLt = LD1/2D1/2Lt = BBt con B = LD1/2

siendo B triangular inferior con bii =√dii.

Unicidad: En principio, la factorización no es única, ya que podemos tomar D1/2 = diag(−√d11, . . . ,−

√dnn).

Tomemos pues, bii =√dii > 0, ∀ i = 1, . . . , n.

Supongamos que existen B1 y B2 triangulares inferiores con los elementos positivos en la diagonal, es decirb1ii > 0 y b2ii > 0 ∀ i = 1, . . . , n tales que

A = B1B1t = B2B2

t

Sean D1 y D2 las matrices diagonales con los elementos de las diagonales de B1 y B2, respectivamente,es decir D1 = diag (b111, . . . , b

1nn) y D2 = diag (b211, . . . , b

2nn). Entonces, podemos escribir

A =

B1B1t = B1D1

−1D1B1t

B2B2t = B2D2

−1D2B2t

(3.7)

Las matrices B1D1−1 y B2D2

−1 son triangulares inferiores con 1 en la diagonal principal y las matricesD1B1

t y D2B2t son triangulares superiores. Gracias a la unicidad de la factorización LU de A, tenemos

de (3.7)



B1D1−1 = B2D2

−1 := L

D1B1t = D2B2

t := U

Los elementos diagonales en la segunda igualdad son (D1B1t)ii = (D2B2

t)ii, es decir (b1ii)2 = (b2ii)

2 paratodo i y, como b1ii > 0 y b2ii > 0, se tiene b1ii = b2ii. Por tanto, D1 = D2 ⇒ Bt1 = Bt2 ⇒ B1 = B2.

�

Observaciones:

1. El recíproco del Teorema 3.29 también es cierto. Más concretamente, si B es una matriz regular (nonecesariamente triangular inferior) tal que A = BBt, entonces A es simétrica y definida positiva. Enefecto, si A = BBt, se tiene

At = (BBt)t = (Bt)tBt = BBt = A ⇒ A es simétrica.

Para todo v ∈ Rn \ {0}, gracias a que B es regular, tenemos Btv 6= 0 y podemos escribir:

vtAv = vtBBtv = (Btv)t(Btv) =n∑i=1

(Btv)2i > 0 ⇒ A es definida positiva.

2. De la demostración del Teorema 3.29 se deduce un procedimiento para calcular la factorización de Choleskya partir de la factorización LU . En efecto, si A es simétrica y definida positiva tal que A = LU , entonces

A = BBt con B = LD1/2, D = diag (u11, . . . , unn)

3. También es posible obtener la factorización LU a partir de la de Cholesky. En efecto, si A = BBt, entonces

A = BBt = BD−1DBt ⇒ A = LU con L = BD−1, U = DBt, D = diag (b11, . . . , bnn)

4. Se puede comprobar que la factorización de Cholesky, igual que la factorizaciín LU conserva la estructura«banda» de la matriz (ver [2]).

Por último, mostramos una propiedad que usaremos en la práctica para comprobar si una matriz simétrica eso no definida positiva.

Criterio de Sylvester

Sea A una matriz simétrica. A es definida positiva ⇔ todos sus menores principales son positivos.

Demostración: Sea A simétrica.

=⇒ Supongamos que A es definida positiva. Veamos que todos sus menores principales son positivos, es decir∆k > 0, k = 1, . . . , n.

Usando la Proposición 3.28, se tiene que si A definida positiva, entonces todas las submatrices principales deorden k, Ak, k = 1, . . . , n son definidas positivas. La implicación quedará demostrada si probamos que todamatriz definida positiva tiene su determinante positivo (no se usará que A sea simétrica).En efecto, sea B definida positiva y consideramos la familia Bλ de matrices dada por

Bλ = λB + (1− λ)I, λ ∈ [0, 1].



Es fácil comprobar (usando la definición) que, para cada λ ∈ [0, 1], la matriz Bλ es definida positiva, y por tantoregular: det(Bλ) 6= 0.Consideramos ahora la función g : [0, 1] 7→ R, dada por g(λ) = det(Bλ). Es claro que la función g(λ) es unpolinomio en la variable λ y, por tanto es continua en el intervalo [0, 1]. Hemos visto antes que det(Bλ) 6= 0,luego g no se anula en [0, 1] (no cambia de signo). Observando que

g(0) = det(I) = 1 > 0,

podemos concluir que g(1) = det(B) > 0, que es lo que queríamos demostrar.

⇐= Supongamos ahora que ∆k = det(Ak) > 0, k = 1, . . . , n. Veamos que A es definida positiva.Se razona como sigue:

Como 0 < ∆k = det(Ak) 6= 0 para todo k y A es simétrica, existe una única factorización LU de A de laforma particular (3.6):

A = LDLt, D = diag (u11, . . . , unn)

Supongamos por un momento que hemos sido capaces de demostrar que ukk > 0 para todo k = 1, . . . , n.

Como L es regular y la matriz diagonal D es definida positiva (pues ukk > 0, k = 1, . . . , n), usandola Proposición 3.28 deducimos que LDLt es definida positiva, por tanto A es definida positiva, ya quecoincide con una matriz definida positiva.

Veamos ahora que ukk > 0 para todo k = 1, . . . , n. En efecto, como ∆k = det(Ak) > 0, k = 1, . . . , n,existe una única factorización LU de A:

a11 · · · a1k · · · a1n...

. . ....

......

ak1 · · · akk · · · akn...

......

. . ....

an1 · · · ank · · · ann

=

1...

. . .

`k1 · · · 1

......

.... . .

`n1 · · · `nk · · · 1

u11 · · · u1k · · · u1n. . .

......

...

ukk · · · ukn. . .

...

unn

Haciendo multiplicaciones por bloques, se verifica

0 < ∆k = det(Ak) = 1 · det(Uk) = u11 · · ·ukk, k = 1, . . . , n.

de donde razonando de forma recusiva sobre la dimensión de la matriz para k = 1, . . . , n, se compruebaque ukk > 0 para todo k = 1, . . . , n.

Esto termina la demostración.�



Ejemplo 3.30 Resolver por Cholesky el sistema lineal Ax = b con

A =

4 −1 0

−1 4 −1

0 −1 4

, b =

2

6

2

En primer lugar, vamos a comprobar que es posible realizar la factorización de Cholesky. Es claro que A essimétrica. Según el criterio de Sylvester A es definida positiva, pues

∆1 = a11 = 4 > 0, ∆2 = 16− 1 = 15 > 0, ∆3 = det(A) = 56 > 0.

Calculamos la factorización de Cholesky: A = BBt.4 −1 0

−1 4 −1

0 −1 4

=

b11 0 0

b21 b22 0

0 b32 b33

b11 b21 0

0 b22 b32

0 0 b33

Comparando la parte izquierda con la derecha de esta igualdad, obtenemos:

b211 = 4 ⇒ b11 = 2 b11b21 = −1 ⇒ b21 = −1

2

b221 + b222 = 4 ⇒ b222 = 4− 1

4=

15

4⇒ b22 =

√15

2b22b32 = −1 ⇒ b32 = − 1

b22= − 2√

15

b232 + b233 = 4 ⇒ b233 = 4− 4

15=

56

15⇒ b33 =

√56

15

A = BBt =

2 0 0

−1

2

√15

20

0 − 2√15

√56

15

2 −1

20

0

√15

2− 2√

15

0 0

√56

15

.

Pongamos Btx = v. Resolvemos Bv = b por el algoritmo de bajada2v1 = 2

−1

2v1 +

√15

2v2 = 6

− 2√15v2 +

√56

15v3 = 2

⇒

y

v1 = 1

v2 =2√15

(6 +

1

2

)=

13√15

v3 =

√15√56

(2 +

26

15

)=

√56

15

⇒

v1

v2

v3

=

1

13/√

15√

56/√

15

Resolvemos ahora Btx = v por el algoritmo de subida

2x1 −1

2x2 = 1

√15

2x2 −

2√15x3 =

13√15

√56√15x3 =

√56√15

⇒

xx1 =

1

2(1 + 1) = 1

x2 =2√15

( 13√15

+2√15

)= 2

x3 = 1

⇒

x1

x2

x3

=

1

2

1



Ejemplo 3.31 A partir de la factorización de Cholesky del Ejemplo 3.30 obtener la factorizaciónLU.Tenemos

A = BBt =

2 0 0

−1

2

√15

20

0 − 2√15

√56

15

2 −1

20

0

√15

2− 2√

15

0 0

√56

15

.

Escribimos A = BD−1DBt := LU , siendo

D =

2 0 0

0

√15

20

0 0

√56

15

, D−1 =

1

20 0

02√15

0

0 0

√15

56

L := BD−1

2 0 0

−1

2

√15

20

0 − 2√15

√56

15

1

20 0

02√15

0

0 0

√15

56

=

1 0 0

−1

41 0

0 − 4

151

U := DBt

2 0 0

0

√15

20

0 0

√56

15

2 −1

20

0

√15

2− 2√

15

0 0

√56

15

=

4 −1 0

015

4−1

0 056

15

3.7.3 Cálculo efectivo de la factorización de Cholesky

Se razona de forma similar al cálculo efectivo de la factorización LU (ver la Sección 3.6.3), escribiendo queA = BtB es de la forma:

a11 a12 · · · a1,n−1 a1n

a21 a22 · · · a2,n−1 a2n

· · · · · · · · · · · · · · ·

an1 a12 · · · an,n−1 ann

=

b11 0 · · · 0 0

b21 b22 · · · 0 0

· · · · · · · · · · · · · · ·

bn1 b12 · · · bn,n−1 bnn

b11 b21 · · · bn−1,1 bn1

0 b22 · · · bn−1,2 bn2

· · · · · · · · · · · · · · ·

0 0 · · · 0 bnn

Supongamos que bii > 0 ∀ i. Se multiplican las matrices de la derecha y se comparan elementos de A.

Multiplicamos la 1a fila de B por las columnas de Bt obtenemos 1a fila de A:

a1j = b11bj1, j = 1, . . . , n ⇒

b11 =

√a11

bj1 =a1jb11

, j = 2, . . . , n

Multiplicamos la 2a fila de B por las columnas de Bt (salvo la 1a), obtenemos la 2a fila de A (salvo el 1er.



elemento):

a2j = b21bj1 + b22bj2, j = 2, . . . , n ⇒

b22 =

√a22 − b221

bj2 =1

b22(a2j − b21bj1), j = 3, . . . , n

Supongamos conocidas (k − 1) primeras columnas de B. Multiplicamos la ka fila de B por las columnasde Bt (salvo las (k− 1) primeras), obtenemos ka fila de A (salvo los primeros (k− 1) elementos): teniendoen cuenta que bkp = 0, para p = k + 1, . . . , n

akj = bk1bj1 + bk2bj2 · · ·+ bkkbjk =

k∑p=1

bkpbjp =

k−1∑p=1

bkpbjp + bkkbjk, j = k, . . . , n

⇒

bkk =

√√√√akk −k−1∑p=1

b2kp

bjk =1

bkk(akj −

k−1∑p=1

bkpbjp), j = k + 1, . . . , n

Algoritmo 3.32 (de factorización de Cholesky)n = dimensión de APara cada k = 1, 2 . . . , n

bkk =

√√√√akk −k−1∑p=1

b2kp

bjk =1

bkk(akj −

k−1∑p=1

bkpbjp), j = k + 1, . . . , n

Fin

Se puede demostrar que el número de operaciones necesarias para llevar a cabo el método de Cholesky esaproximadamente la mitad que el en método de Gauss y, por tanto también la mitad que en el método LU.


Bibliografía

[1] R.L. Burden, J.D. Faires, Análisis Numérico, Grupo Editorial Iberoamérica, México, Madrid, 2011.

[2] J.A. Infante del Río, J.M. Rey Cabezas, Métodos Numéricos. Teoría, problemas y prácticas con MATLAB,Ediciones Pirámide, Madrid, 1999.

[3] J.H. Mathews, K.D. Fink, Métodos Numéricos con MATLAB, Prentice Hall, Madrid, 2000.

[4] A. Quarteroni, F. Saleri, Cálculo Científico con MATLAB y Octave, Springer, Milano, 2006.

38

Índice general

3. Métodos directos de resolución de sistemas lineales 13.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.2. Resolución de sistemas triangulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33.3. Sistemas equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.4. Método de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.4.1. Primeros ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.4.2. Matrices de permutación y «matrices de paso» . . . . . . . . . . . . . . . . . . . . . . . . 133.4.3. Estudio general del método de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4.4. Estrategia de elección del pivote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.5. Método de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.5.1. Aplicación al cálculo de la inversa de una matriz . . . . . . . . . . . . . . . . . . . . . . . 19

3.6. Método de factorización LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.6.1. Condición suficiente de existencia y unicidad de la factorización LU . . . . . . . . . . . . 223.6.2. Caso particular: matrices con la diagonal dominante . . . . . . . . . . . . . . . . . . . . . 243.6.3. Cálculo efectivo de la factorización LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.6.4. Factorización LU de Crout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.7. Método de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.7.1. Matrices definidas y sus propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.7.2. Factorización de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.7.3. Cálculo efectivo de la factorización de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . 36

Bibliografía 37

39

Documents

3 Métodos directos de resolución de sistemas linealespersonal.us.es/doubova/cn1/Tema3CNI.pdf · Antes de hacer una descripción general del método de Gauss (que es bastante engorroso