Métodos Numéricos para MatricesLas operaciones con matrices aparecen en distintos problemas de la física. Aunque el ejemplo

más conocido es el estudio de pequeñas oscilaciones en sistemas de muchos cuerpos, también se

utilizan en resolución de circuitos eléctricos y son fundamentales en mecánica cuántica.

Supongamos que queremos estudiar el espcro de vibraciones de una molécula con n grados de

libertad. La primer aproximación consiste en investigar las oscilaciones armónicas del sistema, ex-

pandiendo la energía potencial hasta el segundo orden en las coordenadas generalizadas alrededor

de las posiciones de equilibrio:

U (q1, q2, . . . , qn) ≈1

2

∑

j,k

Ajkqjqk

donde qi son las coordenadas generalizadas y Ajk son parámetros del potencial que usualmente

pueden obtenerse a partir de un cálculo de química cuántica. La energía cinética puede escribirse

en términos de las velocidades generalizadas q̇

T (q̇1, q̇2, . . . , q̇n) ≈1

2

∑

j,k

Mjkq̇j q̇k.

Aplicando la ec. de Lagrange:∂L

∂qj

−d

dt

∂L

∂q̇j

= 0

con L = T − U tenemos:n∑

j=1

(Ajkqj + Mjkq̈j) = 0

con k = 1, 2, . . . , n. Realizando el reemplazo qj = xjeiωt obtenemos el siguiente sistema de

ecuaciones homogéneon∑

j=1

(Ajk − Mjkω2)xj = 0

que tiene solución no trivial si

det[A− Mω2] = 0.

Este es un ejemplo sencillo en el cual es necesario calcular el determinante de una matriz, y poder

resolver un sistema de ecuaciones lineales.

En general, podemos dividir los métodos numéricos para matrices en dos grandes áreas:

• Resolución de sistemas lineales.

1

• Diagonalización de matrices.

El cálculo de la matriz inversa A−1de una matriz de n × n puede reducirse a la resolución de n

sistemas de ecuaciones lineales. Por otra parte, el cálculo del determinante de una matriz puede

realizarse a través de la descomposición en determinantes menores a lo largo de la columna j

det[A] =n∑

i=1

(−1)i+jAij det[Rij]

donde Rij es la matriz de orden (n−1)×(n−1) que se obtiene removiendo la fila i y la columna j

de la matriz A. Este es un ejemplo de algoritmo recursivo, en el cual, para calcular el determinante

de orden n es necesario conocer el determinante de orden n − 1. Este es un ejercicio interesante

de programación, aunque, como veremos, no es la mejor forma de calcular el determinante.

En el cálculo numérico con matrices, es de fundamental importancia reconocer el costo com-

putacional de cada operación a realizar. Usualmente, dada una matriz de tamaño n×n, el costo de

estas operaciones se mide en términos de la dimensión n de la matriz. La mayoría de los métodos

que veremos son de orden n3. Entonces, por ejemplo, la diferencia en el número de operaciones

entre utilizar una matriz de 10 × 10 y una de 12 × 12 es de: 123 − 103 = 1728 − 1000 = 728

operaciones. Es decir que un aumento pequeño en el tamaño de la matriz implica un incremento

de alrededor del 70% en el número típico de operaciones!!!!

I. SISTEMAS DE ECUACIONES LINEALES

Definiremos el sistema de ecuaciones lineales de la siguiente manera:

Ai1x1 + Ai2x2 + Ai3x3 + . . . + Ainxn = bi

para i = 1, 2, . . . , n. Definiendo el vector de incógnitas x = (x1, x2, . . . , xn) como una matriz de

n × 1, el sistema se puede escribir como

Ax = b.

Por ejemplo,

1 2 3

−3 1 5

2 4 −1

x1

x2

x3

=

3

−2

1

.

Antes de continuar, es conveniente definir las matrices triangulares superiores U tales que Uij = 0

para i > j y las matrices triangulares inferiores L con Lij = 0 para i < j.

2

A. El método de Gauss

Sabemos que existen diversas operaciones elementales que se pueden realizar en estos sistemas

de ecuaciones:

• Se pueden intercambiar el orden de dos ecuaciones

• Se puede reemplazar una ecuación por una combinación lineal de esta ecuación y otra.

• Se pueden intercambiar las incógnitas.

Estas operaciones no alteran la solución. Cada una de estas operaciones implica realizar determi-

nados cambios en la matriz Ay en b. Por otra parte, es claro que la resolución de un sistema de

ecuaciones en los cuales A es una matriz triangular superior o inferior es muy sencilla. En efecto,

si tenemos

1 2 3

0 7 14

0 0 −7

x1

x2

x3

=

3

7

−7

entonces x3 = 1, y sustituyendo

x2 =1

7(7 − 14 × 1) = −1

y

x3 = 3 − 2 × (−1) − 3 × 1 = 2,

es decir x = (2,−1, 1).

El método de Gauss consiste en realizar np operaciones elementales sobre la matriz A de modo

tal que se pueda obtener una forma triangular superior o inferior de dicha matriz, procediendo a

resolver este último problema mediante sustituciones. El método de Gauss-Jordan para obtener

la inversa de una matriz va aún más allá y requiere que después de realizadas las operaciones

elementales, la matriz original A quede transformada en la identidad.

Cuál sería el algoritmo para realizar el método de Gauss? Para fijar ideas, pensaremos en una

matriz de 3 × 3:

A11 A12 A13

A21 A22 A23

A31 A32 A33

3

Primero, multiplicamos la primer fila y el término independiente b1por −Ai1/A11

A21/A11×

A11 A12 A13

A21 A22 A23

A31 A32 A33

→

A21 A12A21/A11 A13A21/A11

A21 A22 A23

A31 A32 A33

y la sumamos a todas las filas con i > 1,

A(1) =

1 A(1)12 A

(1)13

0 A(1)22 A

(1)23

0 A(1)32 A

(1)33

.

De esta manera, eliminamos los coeficientes de A de la primer columna, excepto claro el A11.

De la misma manera, ahora multiplicamos la segunda fila y el término independiente b(1)2 por

−A(1)i2 /A

(1)22 y la sumamos a todas las filas con i > 2.

En el ejemplo anterior

A |b =

1 2 3

−3 1 5

2 4 −1

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

3

−2

1

f1 × 3 + f2

→

f2

1 2 3

0 7 14

2 4 −1

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

3

7

1

f1 × (−2) + f3

→

f

1 2 3

0 7 14

0 0 −7

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

3

7

−7

es decir que

A(1)∣

∣

∣b(1) =

1 2 3

0 7 14

0 0 −7

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

3

7

−7

.

En el caso general, si después de np operaciones elementales, obtenemos A(np) ≡ U, entonces las

soluciones son

xi =1

Uii

b(np)i −

n∑

j=i+1

Uijxj

.

Pivoting

El ejemplo anterior es bastante sencillo. Sin embargo, podría ocurrir que en algun paso, el

elemento diagonal que se utiliza como denominador Aii sea cero (a este elemento se lo llama

pivote). Más aún, podría ocurrir que el pivote no sea cero, y así y todo el método de Gauss sea

inestable frente a errores de redondeo. En todos los casos en los cuales el pivote es un número

pequeño, puede haber problemas.

4

Ejemplo: Un ejemplo claro son las matrices de Hilbert, definidas como

Hij =1

i + j − 1

Estas matrices contienen números fraccionarios que no pueden representarse exactamente en la

aritmética binaria. Por ejemplo, para la matriz de Hilbert de 6 × 6, el sistema

H6×6x = b

con bT = (6, 5, 4, 3, 2, 1) tiene como solución

x = (174,−5880, 45360,−131040, 157500,−66528)

y sin embargo, una rutina numérica obtiene un error de 1×10−4 para dicha solución. Es importante

observar que estos sistemas contienen una combinación letal desde el punto de vista numérico:

numeros fraccionarios no representables en binario, y números extremadamente grandes.

En estos casos, es conveniente elegir el pivote como el máximo valor entre los elementos de

una columna. En el ejemplo, elegiríamos−3 como el pivote. Esto significa intercambiar la primer

y segunda filas (esto es, las ecuaciones) de la matriz A.

B. Descomposición LU

Vimos antes que el método de Gauss se basaba en una serie de operaciones elementales. Cada

una de estas operaciones puede pensarse como el producto de ciertas matrices R y la matriz A.

Por ejemplo, la matriz

R13 =

0 0 1

0 1 0

1 0 0

intercambia las filas 1 y 3 de A. En efecto

R13A =

0 0 1

0 1 0

1 0 0

1 2 3

−3 1 5

2 4 −1

=

2 4 −1

−3 1 5

1 2 3

.

Entonces, la matriz triangular superior A(np)que se obtiene al final de este procedimiento, puede

verse como

UA(np) = R(1)R(2)R(3) . . .R(np)A = RA

5

es decir que A = R−1U. Es posible probar que R es una matriz triangula inferior y que la inversa

de una matriz triangular inferior es otra matriz triangular inferior.

Por otra parte, puede darse el caso en que uno tenga que resolver una serie de sistemas de

ecuaciones, en los cuales sólo cambia el vector b; como por ejemplo cuando uno calcula la inversa

de una matriz. Entonces es útil tener una descomposición de la matriz A que nos permita resolver

el problema eficientemente. Esta es la denominada descomposición LU en la cual la matriz Ase

escribe como un producto de una matriz triangular inferior y una superior. Si tenemos

Ax = b

y A = LU entonces

Ax = LUx = b.

Llamando

Ux = y

tendremos que resolver el sistema

Ly = b.

Para obtener los coeficientes de la descomposición, se utiliza el siguiente algoritmo:

1. Se eligen Lii = 1, para i = 1, 2, . . . , n.

2. Para cada j,

Uij = Aij −i−1∑

k=1

LikUkj

Lij =1

Ujj

Aij −j−1∑

k=1

LikUkj

Por ejemplo, si

A =

4 2 3

−3 1 4

2 4 5

entonces L11 = 1, L22 = 1, L33 = 1 y para j = 1

U11 = 4

L21 =1

4(−3) = −

3

4

L31 =1

4(2) =

1

2

6

para j = 2

U12 = 2

U22 = 1 − L21U12 = 1 − (−3

4) × 2 =

5

2

L32 =2

5(4 − L31U12) =

2

5

(

4 −1

2× 2

)

=6

5

etc. Tenemos que

A =

1 0 0

−34

1 0

12

65

1

4 2 3

0 52

254

0 0 −4

Observemos también que

det[A] = det[L] det[U]

y el algoritmo siempre deja det[L] = 1,con lo cual el determinante de Aes simplemente el pro-

ducto de los elementos de la diagonal de U.

Puede ser posible todavía que algún elemento de la diagonal de U sea nulo, con lo cual es

necesario hacer pivoting.

Ejemplo: Calcular la descomposición LU de la matriz

B =

1 2 6

4 8 −1

−2 3 5

(Hint: intercambiar las filas 2 y 3).

Si la matriz no tiene descomposición LU, entonces es una matriz singular.

Con la descomposición LU de la matriz, es posible entonces calcular los valores de y y la

solución x a nuestro problema, dado que en ambos casos las matrices son triangulares

y1 =b1

L11

yi =1

Lii

bi −i−1∑

j=1

Lijyj

y

x1 =yn

Unn

xi =1

Uii

yi −n∑

j=i+1

Uijxj

.

7

Cualquiera de ambos métodos es de orden n3, aunque el método de la descomposición LU es un

factor 3 más rápido.

C. Búsqueda de ceros en una funcion de varias variables

Supongamos que buscamos los ceros de una función de varias variables

f(x) = 0

donde f = (f1, f2, . . . , fn) y x = (x1, x2, . . . , xn). Si la solución de la ecuación es x0, podemos

expandir en desarrollo de Taylor alrededor de ese punto

f(x0) ≈ f(x) + ∆x · ∇f(x) + . . .

que es lo mismo que

f(x0) ≈ f(x) + A(x)∆x = 0

donde ∆x = x − x0 y

Aij(x) =∂fi

∂xj

de tal manera que obtenemos el método de Newton para búsqueda de ceros en el caso multidimen-

sional

x0 ≈ x − A−1(x)f(x)

y donde se hace necesario calcular la inversa de la matriz de derivadas A.

II. DIAGONALIZACIÓN DE MATRICES

El problema de diagonalización de matrices aparece en numerosos problemas de la física. Dada

una matriz A de n × n, el problema de autovalores consiste en encontrar λ y x tales que

Ax = λx,

donde x es el autovector correspondiente al autovalor λ. Los valores de λ se obtienen resolviendo

la ecuación secular

det[A − λ1] = 0

donde 1 es la matriz identidad. Para una matriz de n × n, existen en general n autovalores.

8

Uno de los casos más importantes en física corresponde al problema de autovalores de una

matriz hermítica. La matriz A es hermítica si

A = A†

donde A† es la matriz traspuesta conjugada de A. El problema de autovalores de una matriz

hermítica tiene las siguientes propiedades

1. Los autovalores de una matriz hermítica son reales.

2. Los autovectores forman una base ortonormal.

3. Una matriz hermítica puede transformarse en una matriz diagonal a través de transforma-

ciones de similaridad con matrices unitarias.

Más aún, el problema de autovalores de una matriz de n × n hermítica compleja puede trans-

formarse en un problema de autovalores para una matriz simétrica real de 2n × 2n. En efecto,

si

A = B + iC

entonces B es una matriz real simétrica y C es una matriz real antisimétrica. El problema de

autovalores es:

(B + iC) (y + iz) = λ (y + iz)

que puede escribirse como

B −C

C B

y

z

= λ

y

z

.

Éste es un problema de autovalores para una matriz real simétrica.

A. Matrices Tridiagonales

El caso más sencillo de diagonalización corresponde a matrices tridiagonales de la forma

a1 b1 0 . . . 0

b1 a2 b2 . . . 0

0 b2 a3 . . . 0...

...... . . . bn−1

0 0 0 bn−1 an

9

Estas matrices tienen propiedades que hacen que el cálculo de autovalores y autovectores sea más

sencillo. En primer lugar, el determinante de la matriz tridiagonal det[A−λ1] es equivalente a la

ecuación polinomial pn(λ) = 0, que puede obtenerse mediante la recursión

p0(λ) = 1

p1(λ) = a1 − λ

pi(λ) = (ai − λ)pi−1(λ) − b2i−1pi−2(λ)

En principio, se podría usar una rutina de búsqueda de ceros para obtener las raíces de pn(λ). Sin

embargo, este polinomio tiene las siguientes propiedades

1. Todas las raíces de pn(λ) = 0 se encuentran en el intervalo [−‖A‖ , ‖A‖] donde ‖A‖ está

definido como

‖A‖ = max

n∑

j=1

|Aij|

.

2. El número de raices de pn(λ) = 0 con λ > λ0 esta dado por el número de acuerdos de los

signos de pj(λ0) y pj−1(λ0) para j = 1, 2, . . . , n. Si por ejemplo, pj(λ0) = 0, se le asigna el

signo del polinomio precedente pj−1(λ0).

Es evidente que utilizando estas dos propiedades, es posible diseñar un algoritmo numérico que

encuentre los autovalores utilizando el método de bisección. Una vez obtenidos los autovalores,

el problema de obtener los autovectores se reduce a resolver un sistema de ecuaciones para cada

autovalor obtenido.

B. El método QR

En este método, la matriz A a diagonalizar se descompone en un producto de una matriz uni-

taria Q y una matriz triangular superior R,

A = QR.

Si construimos la matriz

A′ = RQ,

como QQ† = 1, entonces R = Q†A y

A′ = Q†AQ,

10

es decir, A′es una transformación unitaria de A. Esta transformación preserva los autovalores. Se

puede probar que luego de una serie de estas transformaciones, la matriz original A se transforma

en una matriz triangular superior cuya contiene los autovalores de A. Entonces, comenzando con

A(0) = A, y definiendo

A(k) = QkRk

tendremos

A(k+1) = Q†kA

(k)Qk.

En el caso general, estas transformaciones dan un algoritmo de orden n3. Sin embargo, en el caso

de matrices tridiagonales, el algoritmo es de orden n. Más aún, es posible construir la transforma-

ción a partir de matrices de rotación P(p, q):

P(p, q) =

1. . .

c . . . s... 1

...

−s . . . s. . .

1

tales que c2 + s2 = 1, Ppp(p, q) = Ppp(p, q) = c y Ppq(p, q) = −s, Pqp(p, q) = s. En efecto, se

pueden elegir c y s de modo tal que al aplicar la transformación

A′ = PT(p, q)AP(p, q)

se obtenga que A′pq = 0. Para ello, el ángulo de rotación es tal que

cot 2φ =c2 − s2

2sc=

aqq − app

2apq

.

Se puede probar que la rotación en angulos menores que π/4 es la más estable.

Volviendo a la transformación Q, se la puede construir como una serie de rotaciones que elim-

inen los elementos de las sub y supra diagonales:

Q†k = Pk(1, 2)Pk(2, 3) . . .Pk(n − 1, n).

11

C. Transformación a una matriz tridiagonal

Hemos visto que resulta más o menos sencillo obtener los autovalores y autovectores de una

matriz tridiagonal. En esta sección describiremos el método de Householder para transformar una

matriz real y simétrica a la forma tridiagonal. Para ello definimos la matriz de Householder como

P = 1 − 2wwT

donde w es un vector real con |w|2 = 1. La matriz P es ortogonal, pues

P2 =(

1 − 2wwT) (

1 − 2wwT)

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

Supongamos entonces que escribimos

P = 1 − 2uuT

|u|2

y elijamos u = x + |x| e1 donde x es el primer vector columna de la matriz A a transformar, y

e1 = (1, 0, 0, . . . , 0). Notemos que

|u|2 = 2 |x|2 + 2 |x| e1x = 2 |x|2 + 2 |x| x1

Entonces

Px =

(

1 − 2uuT

|u|2

)

x

= x − 2u (x + |x| e1)

Tx

|x + |x| e1|2

= x − 2u(

|x|2 + |x| x1

)

2 |x|2 + 2 |x| x1

= x − u = − |x| e1

Esto nos muestra que la aplicación de P así definido transforma la columna x en una columna con

ceros en todos los elementos excepto el primero. Entonces, si elegimos como primer vector x a

los últimos n − 1 elementos de la primer columna de la matriz A, x = (A21, A31, . . . , An1) :

P1A =

1 0 0 0

0

0 Pn−11

0

A11 A12 . . . A1n

A21. . .

...

A11

=

A11 A12 . . . A1n

k. . .

...

0

12

donde k = − |(A21, A31, . . . , An1)| . La transformación ortogonal completa será

A(2) = P1AP1 =

A11 k . . . 0

k. . .

...

0

.

En el siguiente paso, construimos:

P2 =

1 0 0 0

0 1 0 0

0 0 Pn−12

0 0

donde x ahora contiene los n − 2 elementos de la segunda columna de A(2). El procedimiento

entonces garantiza que al final de n − 2 transformaciones, la matriz A(n−2) será tridiagonal.

Una forma más sencilla de aplicar este procedimiento es definir

p = 2Au

|u|2

entonces

AP = A

(

1 − 2uuT

|u|2

)

= A − puT

y

A′ = PAP = A− quT − uqT

donde

q = p −uT p

|u|2u.

a. Ejemplo La transformación de Householder para

A =

4 2 2 1

2 −3 1 1

2 1 3 1

1 1 1 2

es

A′ =

4 −3 0 0

−3 2 3.162277 0

0 3.162277 −1.4 0.2

0 0 0.2 1.4

13

b. Ejemplo Dada

A =

2 −1 −1

−1 2 −1

−1 −1 2

mostrar que p3(λ) = −(−4 + λ)(−1 + λ)2. Probar calculando el determinante de A − λ1 y con

la recursión anterior.

14