alu, palu y formas cuadráticas

Factorizacion PA=LU

Prof. I. HuertaFacultad de Matematicas

UC

[email protected]

Septiembre 2008

Factorizacion PA=LU Aplicaciones

Factorizaciones(Dividir para Conquistar)

• La estrategia consiste en expresar una operacion complicada como lacomposicion de varias sencillas.• Esto permite revertir una operacion complicada revirtiendo una sucesion

de operaciones sencillas• En matrices, la estrategia consiste en expresar una matriz A como el

producto de matrices sencillas.• Por ejemplo, para la composicion A = BC tenemos

1


A~x = ~b⇔ B C~x︸︷︷︸ = ~b⇔{

B~y = ~bC~x = ~y

~y

Entonces, para resolver A~x = ~b, donde A = BC, se hace lo siguiente

• Resuelva B~y = ~b

• Resuelva C~x = ~y

En general, si tenemos la factorizacion

A = A1 A2 · · · Ak

entonces para resolver A~x = ~b, se resuelven sucesivos sistemas de ecuaciones

• ~x0 = ~b

2


• Para i = 1, 2, . . . , k, resuelva Ai~xi = ~xi−1

• ~x = ~xk

Si A es invertible, entonces resolver A~x = ~b es equivalente a calcular~x = A−1~b SIN TENER LA INVERSA de A.

3

Factorizacion A=LU Tabulacion de Datos

Al final del semestre habremos visto las factorizaciones

• A es el producto de matrices elementales para A invertible.• PA = LU ( Factorizacion PALU para matrices generales)• A = LDLT (Cholesky sin raız cuadrada para simetricas)• A = RTR (Cholesky con raız cuadrada para A simetrica positiva definida)• A = QR (Factorizacion QR para matrices generales)• A = V DV −1 (Diagonalizacion)• A = V DV T (diagonalizacion ortogonal para A simetrica)• A = V ΣU (descomposicion de valores singulares para A matriz general

de m× n)

4


Factorizacion A=LU

Sea A de m× n. La factorizacion A = LU

• se obtiene al llevar la matriz A a la forma escalonada U

usando exclusivamente la operacion elemental fila: sumar un multiplode una fila a otra.

• la matriz escalonada U de m × n obtenida no tiene los pivotes iguales a1 en general.

• La factorizacion A = LU expresa a cada fila de A como combinacionlineal de las filas de U .

5


• la matriz L de m×m es triangular inferior con 1’s en la diagonal

L =

1 0 0 · · · 0

l2,1 1 0 · · · 0l3,1 l3,2 1 · · · 0

... . . .lm,1 lm,2 lm,3 · · · 1

• A = LU no siempre puede realizarse pues en ciertos casos hay

intercambios de filas forzados, en cuyo caso se obtiene la factorizacionPA = LU .

• La ecuacion A = LU expresa a la fila i de A como combinacion lineal delas filas de U con coeficientes en la fila i de L.

6


Hay dos maneras de ver la factorizacion PA = LU .

i) Matricial: interpretando a la eliminacion de gauss como multiplicacionespor matrices elementales

ii) Vectorial: interpretando las filas de A como combinaciones lineales de lasfilas de U .

7


Ejemplo 1.

A =

? ? ? ? · · ·? ? ? ? · · ·? ? ? ? · · ·

E2,1(−l2,1)−→

? ? ? ? · · ·0 ? ? ? · · ·? ? ? ? · · ·

E3,1(−l3,1)−→

? ? ? ? · · ·0 ? ? ? · · ·0 ? ? ? · · ·

E3,2(−l3,2)−→

? ? ? ? · · ·0 ? ? ? · · ·0 0 ? ? · · ·

= U

Matricialmente

E3,2(−l3,2) E3,1(−l3,1) E2,1(−l2,1) A = U 1 0 00 1 00 −l3,2 1

1 0 00 1 0−l3,1 0 1

1 0 0−l2,1 1 0

0 0 1

A = U

8


Entonces

A = (E2,1(−l2,1))−1 (E3,1(−l3,1))−1(E3,2(−l3,2))−1 U

A =

1 0 0−l2,1 1 0

0 0 1

−1 1 0 00 1 0−l3,1 0 1

−1 1 0 00 1 00 −l3,2 1

−1

U

Por lo tanto

A = E2,1(l2,1) E3,1(l3,1) E3,2(l3,2)︸︷︷︸ U = LU

L

A =

1 0 0l2,1 1 00 0 1

1 0 00 1 0

l3,1 0 1

1 0 00 1 00 l3,2 1

U = LU

9


Pero

L =

1 0 0

l2,1 1 0

0 0 1

1 0 0

0 1 0

l3,1 0 1

1 0 0

0 1 0

0 l3,2 1

=

1 0 0

l2,1 1 0

0 0 1

1 0 0

0 1 0

l3,1 l3,2 1

=

1 0 0

l2,1 1 0

l3,1 l3,2 1

Es decir,

A =

1 0 0l2,1 1 0l3,1 l3,2 1

U

La matriz L tiene los multiplicadores usados en la eliminacion deguass. La matriz U es la escalonada sin 1’s en la diagonal.

10


Ejemplo 2. Llevamos la matriz

A =

1 1 1 1 1−1 −1 1 −2 0

2 2 −2 2 1

a una forma escalonada U usando solamente la operacion elemental desumar un multiplo de una fila a otra.

A =

1 1 1 1 1−1 −1 1 −2 0

2 2 −2 2 1

l2,1=−1,l3,1=2,−→

1 1 1 1 10 0 2 −1 10 0 −4 0 −1

l3,2=−2,−→ U =

1 1 1 1 10 0 2 −1 10 0 0 −2 1

11


La relacion entre las filas Ai de A y las filas Uj de U es la siguiente

U1 = A1 = A1

U2 = A2 −l2,1U1 = A2 +U1

U3 = A3 −l3,1U1 −l3,2U2 = A3 −2U1 +2U2

Despejando cada una de las filas Ai en terminos de la filas Uj obtenemos

A1 = U1 = U1

A2 = l2,1U1 +U2 = −U1 +U2

A3 = l3,1U1 +l3,2U2 +U3 = 2U1 −2U2 +U3

Estas relaciones de combinaciones lineales se escriben convenientemente enforma matricial A1

A2

A3

=

U1

l2,1U1 + U2

l3,1U1 + l3,2U2 + U3

=

1 0 0l2,1 1 0l3,1 l3,2 1

U1

U2

U3

12


Es decir A1

A2

A3

︸︷︷︸

A

=

1 0 0−1 1 0

2 −2 1

︸︷︷︸

L

U1

U2

U3

︸︷︷︸

U

o equivalentemente 1 1 1 1 1−1 −1 1 −2 0

2 2 −2 2 1

︸︷︷︸

A

=

1 0 0−1 1 0

2 −2 1

︸︷︷︸

L

1 1 1 1 10 0 2 −1 10 0 0 −2 1

︸︷︷︸

U

13


Generalizacion

Note que

• Para obtener la fila Uj se le resta a la fila Aj multiplos de las filas Ui coni < j

• El multiplicador li,j dice por cuanto hay que multiplicar la fila j de modoque al restarla a la fila i se hace un cero bajo el pivote j.

En general se tiene entonces que

U1 = A1

U2 = A2 − l2,1U1

U3 = A3 − l3,1U1 − l3,2U2...

Um = Am − lm,1U1 − lm,2U2 − · · · − lm,m−1Um−1

14


Expresando las filas Ai de A como combinacion lineal de las filas Uj de Use tiene

A1 = U1

A2 = l2,1U1 + U2

A3 = l3,1U1 + l3,2U2 + U3...

Am = lm,1U1 + lm,2U2 + · · · + lm,m−1Un−1 + Um

Estas relaciones de combinaciones lineales se escriben convenientementemediante la factorizacion

A1

A2

A3...

Am

︸︷︷︸

A

=

1 0 0 · · · 0 0

l2,1 1 0 · · · 0 0l3,1 l3,2 1 · · · 0 0

. . .lm,1 lm,2 lm,3 · · · lm,m−1 1

︸︷︷︸

L

U1

U2

U3...

Um

︸︷︷︸

U

15


Tabulacion de datos

Para efectos de mantener en forma organizada los resultados intermediosy multiplicadores en el proceso de eliminacion gaussiana hacemos lo siguiente

• Trabajamos con una sola matriz de trabajo de m× n.

• Esta matriz inicialmente tiene el valor de A.

• Se procede con la eliminacion tal como siempre pero se guarda el valordel multiplicador li,k en el elemento que se anula al restar li,k veces lafila k a la fila i

• Es decir, se guarda implıcitamente el valor cero de U y explıcitamente elmultiplicador li,k que hace el cero.

• Las posiciones en la matriz de trabajo que corresponden a multiplicadoresse marcan (en estas notas los multiplicadores van en negrita)

16


• La tabla final que se obtiene al terminar el proceso tiene los multiplicadoresli,k que definen a L y a la escalonada U .

• Los ceros que se realizan en el proceso de eliminacion estan implıcitos en latabla y estan ubicados en los lugares donde se guardan los multiplicadores.

• Los unos de la diagonal de L se suponen implıcitos

17


Ejemplo 3. Donde se hace un cero anotamos en negrita elmultiplicador correspondiente.

El valor del multiplicador li,j es

li,j =Elemento que se anula

Pivote

2 1 2 3 4−2 −1 −5 −4 −34 2 7 9 94 2 −2 2 10

l2,1=−2/2=−1

l3,1=4/2=2

l4,1=4/2=2−→

2 1 2 3 4-1 0 −3 −1 12 0 3 3 12 0 −6 −4 2

18


l3,2=3/(−3)=−1

l4,2=(−6)/(−3)=2−→

2 1 2 3 4-1 0 −3 −1 12 0 -1 2 22 0 2 −2 0

l4,3=(−2)/2=−1

−→

2 1 2 3 4-1 0 −3 −1 12 0 -1 2 22 0 2 -1 2

Los multiplicadores en negrita definen la parte triangular inferior deL. Si reemplazamos los multiplicadores por ceros obtenemos U .

A = LU, L =

1 0 0 0−1 1 0 0

2 −1 1 02 2 −1 1

U =

2 1 2 3 40 0 −3 −1 10 0 0 2 20 0 0 0 2

19


Ejemplo 4. Calculamos una factorizacion A = LU para

A =

−2 1 1 −3 −2−4 2 −1 −3 −12 −1 1 1 16 −3 5 1 2

20


−2 1 1 −3 −2

−4 2 −1 −3 −1

2 −1 1 1 1

6 −3 5 1 2

l2,1=(−4)/(−2)=2,

l3,1=2/(−2)=−1

l4,1=6/(−2)=−3

−→

-2 1 1 −3 −2

2 0 −3 3 3

-1 0 2 −2 −1

-3 0 8 −8 −4

l3,2=2/(−3)=−2/3

l4,2=−8/3

−→

-2 1 1 −3 −2

2 0 -3 3 3

-1 0 -2/3 0 1

-3 0 -8/3 0 4

l4,3=4/1=4−→

-2 1 1 −3 −2

2 0 -3 3 3

-1 0 -2/3 0 1

-3 0 -8/3 0 4

21


A = LU, L =

1 0 0 02 1 0 0−1 −2/3 1 0−3 −8/3 4 1

U =

−2 1 1 −3 −2

0 0 −3 3 30 0 0 0 10 0 0 0 0

22

Factorizacion PA=LU Tabulacion de Datos

Ejemplo 5. Calculamos A = LU para A =

2 −4 24 −6 7−6 10 −12

2 −4 24 −6 7−6 10 −12

l2,1=2

l3,1=−3−→

2 −4 22 2 3-3 −2 −6

l3,2=−1−→

2 −4 22 2 3-3 -1 −3

Por lo tanto A = LU con

L =

1 0 02 1 0−3 −1 1

U =

2 −4 20 2 30 0 −3

23


Factorizacion PA=LU

La factorizacion PA = LU es la que se obtiene al llevar la matriz A a suforma escalonada U realizando exclusivamente las operaciones elementalesfila:

i) Restar un multiplo de un fila a otra

ii) intercambiar dos filas

• La operacion elemental fila de reemplazar la fila i por un mutiplo de simisma no se puede realizar.

• La matriz PA es la matriz A con las filas intercambias

• La matriz P es una matriz de permutacion y es la matriz identidad consus filas intercambiadas

24


• Por ejemplo

PA =

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

A1

A2

A3

A4

=

A4

A3

A1

A2

• Al intercambiar filas a medida que se realiza la eliminacion de Gauss se

calcula la factorizacion LU a la matriz A con su filas intercambiadas. Esdecir PA = LU .

Ejemplo 6. En este ejemplo calculamos la factorizacion PA = LU de

A =

2 −2 1 13 −3 1 1−2 2 −1 11 1 1 1

25


y mostramos lo que pasa cuando se intercambian filas.

• Como siempre guardamos (en negrita) el multiplicador li,k en elelemento que se anula al realizar la operacion elemental fila

• Cuando se intercambias filas

? anotamos el intercambio y? se intercambian las filas, incluyendo los multiplicadores ya

calculados.

2 −2 1 13 −3 1 1−2 2 −1 11 1 1 1

−→

2 −2 1 1

3/2 0 −1/2 −1/2-1 0 0 2

1/2 2 1/2 1/2

26


P4,2−→

2 −2 1 1

1/2 2 1/2 1/2-1 0 0 2

3/2 0 −1/2 −1/2

P4,3−→

2 −2 1 1

1/2 2 1/2 1/23/2 0 −1/2 −1/2-1 0 0 2

27


Note que

• La matriz que factorizamos es realmente

PA =

A1

A4

A2

A3

=

1 0 0 00 0 0 10 1 0 00 0 1 0

A1

A2

A3

A4

• Entonces,

P =

1 0 0 0

0 0 0 1

0 1 0 0

0 0 1 0

, L =

1 0 0 0

1/2 1 0 03/2 0 1 0−1 0 0 1

, U =

2 −2 1 1

0 2 1/2 1/2

0 0 −1/2 −1/2

0 0 0 2

28


• La matriz P se obtiene de la matriz identidad intercambiandoprimero las filas 2 y 4 y luego las filas 3 y 4,

P = P4,3P4,2I4 = P4,3P4,2

.

29


Generalizacion

Suponga que

• en la eliminacion se intercambian las filas 1 con ii, 2 con i2, etc....

• Se define k = ik en caso que la fila k no se intercambie con ninguna fila.

Entonces,

Si A es la matriz que se obtiene de A intercambiando las filasde modo que estas queden en el orden final que se obtieneen la eliminacion de Gauss, entonces al realizar el proceso deeliminacion de gauss en A no se requiere intercambiar filas

30


Si P = Pm,im−1 · · ·P2,i2P1,i1 entonces A = PA es la matriz quese obtiene de A intercambiando las filas 1 con i1, fila 2 coni2 etc... en ese mismo orden.

Por lo tanto

para la matriz A = PA se puede realizar la eliminacion de Gausssin intercambio de filas

es decir A = PA = LU .

31


Teorema 1. Sea A matriz de m× n. Entonces existen:

• P matriz m×m de permutacion.• L matriz de m×m triangular inferior con 1’s en la diagonal• U matriz de m× n escalonada (sin 1’s en los pivotes)

tal quePA = LU

Ademas se tiene que

P = Pm−1,im−1 · · ·P2,i2P1,i1 es el producto de las matrices depermutacion elementales que se realizan en la eliminacion degauss. Puesto que P = PIm, P es la matriz identidad con lasfilas intercambiadas con los mismos intercambio de filas que serealizan en el proceso de eliminacion de gauss de A.

32


Tabulacion de datos en PA = LU

• La tabulacion de calculos es una extension del metodo para A = LU queconsidera el intercambio de filas.

• Se procede con la eliminacion tal como siempre.

• Se anotan los multiplicadores li,k en el lugar donde se hace el cero alrestar li,k veces la fila k a la fila i.

• En caso que se intercambie la fila la fila k con la ik en algun puntode la eliminacion, se intercambian las filas completas, incluyendo losmultiplicadores.

33


Ejemplo 7. Calculamos la factorizacion PA = LU de

A =

2 −1 3 14 −2 1 03 1 1 11 −3 0 −1

Tenemos

2 −1 3 14 −2 1 03 1 1 11 −3 0 −1

−→

2 −1 3 12 0 −5 −2

3/2 5/2 −7/2 −1/21/2 −5/2 −3/2 −3/2

34


P3,2−→

2 −1 3 1

3/2 5/2 −7/2 −1/22 0 −5 −2

1/2 −5/2 −3/2 −3/2

−→

2 −1 3 1

3/2 5/2 −7/2 −1/22 0 −5 −2

1/2 -1 −5 −2

−→

2 −1 3 1

3/2 5/2 −7/2 −1/22 0 −5 −2

1/2 -1 1 0

35


Por lo tanto PA = LU con

P = P3,2 =

1 0 0 00 0 1 00 1 0 00 0 0 1

L =

1 0 0 0

3/2 1 0 02 0 1 0

1/2 −1 1 1

U =

2 −1 3 10 5/2 −7/2 −1/20 0 −5 −20 0 0 0

36


Numero de Operaciones

Sean A,B,C, L, U, P ∈ Mn×n, ~x, ~y,~b ∈ Rn, donde L es triangular inferiorcon 1’s en su diagonal, U es triangular superior y P matriz de permutacion.

~x · ~y∑n

i=1 xiyi Nops = 2n~y = A~x yi = Ai · ~x, i = 1, 2, . . . , n Nops = 2n2

C = AB ci = Abi, i = 1, 2, . . . , n Nops = 2n3

Res. L~y = ~byi ← bi −

∑i−1j=1 li,jyj

i = 1, 2, . . . , nNops = (n− 1)n

Res. U~x = ~yxi ← (yi −

∑nj=i+1 ui,jxj)/ui,i

i = n, n− 1, . . . , 2, 1Nops = n2

Calc. PA = LU

∑n−1k=1(2(n− k)2 + (n− k)) =2/3n3 − 1/2n2 − 1/6n

Nops = O(23n

3)

37


Aplicaciones PA=LU

I Solucion de Ax = b

Note que

Ax = b =⇒ (PA)x = Pb =⇒ (LU)x = Pb

=⇒ L Ux︸︷︷︸ = Pby

=⇒ Ly = PbUx = y

i) Se calcula la factorizacion PA = LUii) Se resuelve Ly = Pbiii) Se resuelve Ux = y

38


II Calcular A−1b

Para calcular A−1b se resuelve Ax = b por el metodo anterior.

NUNCA se calcula A−1, a menos que se quiera ver los elementos de ella

Note que

? el numero de operaciones que toma resolver Ly = Pb, Ux = y es 2n2,que es el mismo numero de operaciones que toma calcular el productoA−1b.

? el calculo de A−1 es mucho mas caro que calcular la factorizacionPA = LU (ademas de realizar las operaciones sobre A, hay que realizarlas operaciones sobre la matriz identidad)

39


III Resolver AX = B

Para resolver AX = B hay que resolver A~xi = ~bi, i = 1, 2, . . . , n

i) Calcula la factorizacion PA = LUii) Para k = 1, 2, ..., n se resuelven∗ Ly = Pbk∗ Uxk = y

iii) X = [x1x2 · · ·xn]

Un caso especial importante es el calculo de X = A−1, que es la solucionde AX = I. El algoritmo se puede optimizar evitando las operaciones porcero al resolver los sistemas Ly = Pek, k = 1, 2, . . . , n.

40


IV Resolver ATx = b

Note que PA = LU implica que ATPT = UTLT .

Pero,

PT P = (PT1,i1· · ·PT

n−1,in−1) (Pn−1,in−1 · · ·P1,i1)

= (P1,i1 · · ·Pn−1,in−1) (Pn−1,in−1 · · ·P1,i1)

= (P1,i1 · · ·Pn−2,in−2) (Pn−2,in−2 · · ·P1,i1)...

= P1,i1P1,i1

= I

(Aquı ocupamos que Pi,jPi,j = I)

Por lo tanto P−1 = PT .

41


Entonces AT = UTLTP implica que

ATx = b =⇒ UTLTPx = b

=⇒ UTy = b, LTPx = y

=⇒ UTy = b, LTz = yPx = z

=⇒ UTy = b, LTz = y, x = PTz

El metodo para resolver ATx = b es entonces

i) Calcular la factorizacion PA = LU .ii) Resolver UTy = b (sistema triangular inferior)iii) Resolver LTz = y (sistema triangular superior)iv) Calcular x = PTz

42


Ejemplo 8. Para la matriz

A =

2 1 1−2 −2 04 3 −2

determine

a) La solucion de Ax = b donde b = [1,−1, 1]T

b) La solucion de ATx = b donde b = [1,−1, 1]T

c) Solo la tercera columna de A−1

d) Solo la segunda fila de A−1

e) Solo el elemento (1,1) de A−1.

43


Solucion:

2 1 1−2 −2 04 3 −2

−→ 2 1 1

-1 −1 12 1 −4

−→ 2 1 1

-1 −1 12 -1 −3

Entonces A = LU

P = I, L =

1 0 0−1 1 02 −1 1

U =

2 1 10 −1 10 0 −3

44


a) La solucion de Ly = Pb es y = [1, 0,−1]T .La solucion de Ux = y esx = [1/6, 1/3, 1/3]T .Entonces la solucion de Ax = b es x = [1/6, 1/3, 1/3]T

b) La solucion de UTy = b es y = [1/2, 3/2, 1/3]T .La solucion de LTz = yes z = [5/3, 11/6, 1/3]T .Entonces la solucion de AT b = b es x = PTz =[5/3, 11/6, 1/3]T .

c) La tercera columna de A−1 es la solucion de Ax = e3 = [0, 0, 1]T .

Como la solucion de Ly = Pe3 es y = [0, 0, 1]T y la solucion de Ux = yes x = [1/3,−1/3,−1/3]T tenemos que la tercera columna de A−1 esx = x = [1/3,−1/3,−1/3]T

45


d) Como (AT )−1 = (A−1)T tenemos que la segunda fila de A−1 es .... latranspuesta de la segunda columna de (AT )−1,que es igual a .... latranspuesta de la solucion de ATx = e2 = [0, 1, 0]T

La solucion de UTy = e2 es y = [0,−1,−1/3]T .

La solucion de LTz = y es z = [−2/3,−4/3,−1/3]T .

Entonces la segunda fila de A−1 es [−2/3,−4/3,−1/3].

46

Matrices Especiales Matrices

e) Primero observamos que A1,1 = eT1Ae1 por lo tanto el elemento (1,1) de

B = A−1 es ...b1,1 = eT

1A−1e1.

Pero A = PTLU y entonces A−1 = U−1L−1P .En este caso P = I,por lo que A−1 = U−1L−1. Entonces debemos evaluar la expresionb1,1 = eT

1 U−1L−1e1Pero

b1,1 = eT1 U−1L−1e1

= ((U−1)Te1)T (L−1e1)

= xT · y, donde UTx = e1, Ly = e1

La solucion de UTx = e1 es x = [1/2, 1/2, 1/3]T .La solucion de Ly = e1 esy = [1, 1,−1]T .El elemento (1,1) de A−1 es entonces el producto puntoentre x e y, que es igual a b1,1 = 2/3.

47

Matrices Diagonales Matrices

Matrices Diagonales

Las siguientes matrices son diagonales:

A = diag(1, 2, 3, 4) =

1 0 0 00 2 0 00 0 3 00 0 0 4

B = diag(−1, 2, 0) =

−1 0 00 2 00 0 0

Definicion 1. La matriz A de n × n se dice diagonal si Ai,j = 0 parai 6= j, es decir, los elementos fuera de la diagonal son iguales a cero.

La matriz D = diag(d1, d2, . . . , dn) denota a la matriz diagonal conDi,i = di.

Las matriz identidad y la matriz nula de n× n son matrices diagonales.

Las siguientes propiedades son muy sencillas de verificar y sudemostracion queda propuesto como ejercicio.

48


Propiedades

Proposicion 1. Sean D = diag(d1, d2, . . . , dn), F = diag(f1, f2, . . . , fn) y αescalar entonces:

1.- D + F , αF son diagonales.

2.- DA es la matriz que se obtiene multiplicando la fila i de A por di,i = 1, . . . , n. (1)

3.- AD es la matriz que se obtiene multiplicando la columna i de A pordi, i = 1, . . . , n.(2)

4.- DF = FD = diag(d1f1, d2f2, . . . , dmfn)

5.- D tiene inversa sii di 6= 0 para todo i y D−1 = diag(1/d1, 1/d2, . . . , 1/dn)

49


DA es la matriz que se obtiene multiplicando la fila i de A por di

d1 0 · · · 0 · · · 00 d2 · · · 0 · · · 0... ... . . . ... ... ...0 0 · · · di · · · 0... ... ... ... . . . ...0 0 · · · 0 · · · dn

~A1

~A2...~Ai...~An

=

d1~A1

d2~A2...

di~Ai...

dn~An

(1)

50


AD es la matriz que se obtiene multiplicando la columna i de A por di

[~a1 ~a2 · · · ~ai · · · ~an

]

d1 0 · · · 0 · · · 0

0 d2 · · · 0 · · · 0... ... . . . ... ... ...0 0 · · · di · · · 0... ... ... ... . . . ...0 0 · · · 0 · · · dn

=[

d1~a1 d2~a2 · · · di~ai · · · dn~an

]

(2)

51

Matrices Triangulares superiores Matrices

Matrices Triangulares superiores

Las siguientes matrices son triangulares superiores

A =

−4 4 −20 −1 −40 0 −2

B =

2 −1 2 −10 −2 −4 40 0 −2 −10 0 0 −3

Definicion 2. La matriz A de n×n se dice triangular superior si Ai,j = 0para i > j.

Toda matriz diagonal es tambien triangular superior

52


Propiedades

Proposicion 2. Sean U , V son matrices triangulares superiores de n×ny α escalar, entonces:

1.- U + V , αU son triangulares superiores

2.- UV es triangular superior. Si U y V tienen unos en la diagonalentonces UV tambien tiene unos en la diagonal.

3.- U tiene inversa si y solo si Ui,i 6= 0, i = 1, . . . , n.

4.- U−1 es triangular superior (cuando existe). Si U tiene unos en ladiagonal entonces U−1 tambien tiene unos en la diagonal.

53


Demostracion:

1.- La demostracion es trivial.

2.- Si U , V son triangulares superiores entonces (UV )i,j es el productopunto de la fila i de U con la columna j de V :

(UV )i,j = (0, . . . , 0, ui,i, ui,i+1, . . . , ui,n)

v1,j

v2,j...

vj,j

0...0

= 0 si i > j

y por lo tanto UV es triangular superior.

54


Si U , V tienen unos en la diagonal entonces

(UV )i,j = (0, . . . , 0, 1, ui,i+1, . . . , ui,n)

v1,j

v2,j...10...0

= 1 si i = j

y por lo tanto UV tiene unos en la diagonal.

3.- Usamos la siguiente propiedad: A tiene inversa sii la escalonada de Atiene n pivotes distintos de cero.

Si ui,i 6= 0 i = 1, . . . , n entonces U ya esta en forma escalonada y tienesus n pivotes distintos de cero, que son los elementos de la diagonal deU , y por lo tanto U tiene inversa.

55


Si ui,i = 0 para algun i, entonces la escalonada de U tendrıa por lo menosuna fila nula y por lo tanto no habrıan n pivotes distintos de cero y porlo tanto U no tendrıa inversa.

4.- Si U es triangular superior y la diagonal de U tiene todos sus elementosno nulos

entonces la matriz ampliada [U |I] se puede llevar a la forma [I|X]multiplicando la fila i por 1/ui,i, i = 1, . . . , n y luego sumando multiplosde filas i a filas j con i > j

por lo tanto la matriz X = U−1 resulta triangular superior.

Si U tiene unos en la diagonal entonces solo es necesario restar multiplosde filas i a filas j con i > j y por lo tanto X tiene tambien unos en ladiagonal.

56


Por ejemplo,

1 4 −2 1 0 00 −1 −4 0 1 00 0 1 0 0 1

−→

1 4 0 1 0 20 −1 0 0 1 40 0 1 0 0 1

−→

1 0 0 1 4 180 1 0 0 −1 −40 0 1 0 0 1

por lo tanto

1 4 −20 −1 −40 0 1

−1

=

1 4 180 −1 −40 0 1

.

57


Tambien,

1 −1 2 −1 1 0 0 0

0 1 −4 4 0 1 0 0

0 0 1 −1 0 0 1 0

0 0 0 1 0 0 0 1

−→

1 −1 2 −1 1 0 0 0

0 1 −4 4 0 1 0 0

0 0 1 −1 0 0 1 0

0 0 0 1 0 0 0 1

−→

1 −1 2 0 1 0 0 1

0 1 −4 0 0 1 0 −4

0 0 1 0 0 0 1 1

0 0 0 1 0 0 0 1

−→

1 −1 0 0 1 0 −2 −1

0 1 0 0 0 1 4 0

0 0 1 0 0 0 1 1

0 0 0 1 0 0 0 1

−→

1 0 0 0 1 1 2 −1

0 1 0 0 0 1 4 0

0 0 1 0 0 0 1 1

0 0 0 1 0 0 0 1

.

58

Matrices Triangulares inferiores Matrices

Por lo tanto 1 −1 2 −10 1 −4 40 0 1 −10 0 0 1

−1

=

1 1 2 −10 1 4 00 0 1 10 0 0 1

.

Contrariamente a lo que muchos alumnos creen, la inversa de unatriangular con unos en la diagonal NO se obtiene cambiandole el signo alos elementos fuera de la diagonal.

59


Triangulares inferiores

Las siguientes matrices son triangulares inferiores:

A =

2 0 0 00 2 0 0−2 1 −4 0

0 3 4 1

B =

5 0 0−2 −2 0−4 −2 3

Definicion 3. La matriz A de n × n se dice triangular inferior si Ai,j = 0para i < j, es decir, cuando AT es triangular superior.

Toda matriz diagonal es triangular inferior y triangular superior.

A es triangular superior (inferior) ⇔ AT es triangular inferior (superior)

60


Propiedades

Proposicion 3. Sean L, M son matrices triangulares inferior de n× n,entonces:

1.- L+M , αL son triangulares inferiores

2.- LM es triangular inferior. Si L y M tienen unos en la diagonalentonces LM tambien tiene unos en la diagonal.

3.- L tiene inversa si y solo si li,i 6= 0, i = 1, . . . , n.

4.- L−1 es triangular inferior (cuando existe). Si L tiene unos en ladiagonal entonces L−1 tambien tiene unos en la diagonal.

61

Propiedades A = LU Matrices

Demostracion:

Las propiedades para matrices triangulares inferiores se pueden deducir delas propiedades de matrices triangulares superiores ocupando las propiedadesde transpuestas, inversas y productos de matrices.

Por ejemplo, L = (LT )T

y entonces L−1 = ((LT )T )−1 = ((LT )−1)T .

Por lo tanto, L triangular inferior implica U = LT triangular superior ypor lo tanto (LT )−1 es triangular superior

y entonces L−1 = ((LT )−1)T es triangular inferior.

Las demostraciones restantes quedan propuestas como ejercicio.

62


Submatrices Principales

Las submatrices principales principales de 1× 1, 2× 2, 3× 3 de

A =

−1 2 3 −2

3 1 −1 00 1 2 −3

−1 0 0 1

de 4 × 4

sonA1 =

[−1

]A2 =

[−1 2

3 1

]A3 =

−1 2 33 1 −10 1 2

Definicion 4. La submatriz principal Ak de una matriz A de n × n esla matriz k × k, k = 1, 2, . . . , n con

(Ak)i,j = Ai,j 1 ≤ i ≤ k, 1 ≤ j ≤ k

Ak se obtiene de A eliminando las filas y columnas k + 1, k + 2, . . . , n.

63


Note que en la factorizacion

A =

2 1 0 1−2 −2 2 −24 3 −1 24 3 −4 2

=

1 0 0 0−1 1 0 02 −1 1 02 −1 −2 1

2 1 0 10 −1 2 −10 0 1 −10 0 0 −3

= LU

A1 = [2] = [1][2] = L1U1,

A2 =

[2 1−2 −2

]=

[1 0−1 1

] [2 10 −1

]= L2U2

A3 =

2 1 0−2 −2 24 3 −1

=

1 0 0−1 1 02 −1 1

2 1 0

0 −1 20 0 1

= L3U3

En el producto LU , debido a los ceros sobre la diagonal de L, al eliminarlas filas y columnas k + 1, k + 2, . . . , n de L y de U se obtiene Ak, es decirAk = LkUk.

64


Otra manera de ver:

Al hacer ceros bajo el pivote k−1 se factoriza en el ”camino” a la submatrizprincipal Ak y se tiene Ak = Lk Uk.

65


Proposicion 4. Si A = LU entonces Ak = Lk Uk, donde Ak, Lk, Uk sonlas submatrices principales de A, L y U respectivamente

Demostracion: Es consecuencia de las observaciones anteriores

Teorema 2. (Pivoteos Forzados) Sea A matriz invertible de n× n.

1.- Si cada submatriz principal Ak, k = 1, 2, . . . , n es invertible entoncesA se puede factorizar A = LU (sin intercambio de filas)

2.- Si cada submatriz principal Ai , i = 1, 2, . . . , k − 1 tiene inversa y sepivotea sin intercambio de filas hasta el pivote k− 1 y la submatrizprincipal Ak no tiene inversa, entonces en el pivoteo k-esimo esnecesario realizar un intercambio forzado de filas.

66


Demostracion:1.- Si A1 tiene inversa entonces a1,1 6= 0 y entonces se puede hacer ceros

bajo el elemento 1, 1 sin intercambio de filas.

Como A2 es invertible la matriz resultante del primer pivoteo debe tenerun elemento no nulo en la posicion 2,2.

Entonces se puede pivotear en 2,2 sin intercambio de filas y hacer cerosbajo 2,2 en la segunda columna.

Como A3 es invertible la matriz resultante del segundo pivoteo debe tenerun elemento no nulo en la posicion 3,3.

Entonces se puede pivotear en 3,3 sin intercambio de filas y hacer cerosbajo 3,3 en la tercera columna.

etc...

Por induccion se demuestra que se puede proceder con la eliminacion degauss sin intercambio de filas quedando el pivote k-esimo en el elementok, k.

67


2.- Si cada submatriz principal Ai , i = 1, 2, . . . , k − 1 tiene inversa entoncesse puede realizar la eliminacion de gauss en A sin intercambio de filashasta el pivote k − 1.

Si la submatriz principal Ak no tiene inversa entonces su escalonada tieneuna fila nula, y por lo tanto la matriz C que resulta despues del pivoteok − 1 tiene el elemento k, k igual a cero

Como A es invertible, la columna k-esima de C debe tener algun elementono cero bajo el elemento k, k

(Pues si no, el pivote k quedarıa en la columna k + 1 o superior, por loque la escalonada de A tendrıa una fila nula, lo que contradice que Atiene inversa).

Entonces para pivotear en el elemento k,k es necesario un intercambioforzado de filas.

68


Ejemplo 9. Construya una matriz A de 4 × 4 tal en la factorizacionPA = LU se requiera un intercambio de filas forzado para el tercerpivote.

Solucion: Construimos una matriz A de 4 × 4 invertible que tengasubmatrices principales A1, A2 invertibles, pero A3 no invertible:

A =

1 1 2 21 2 2 22 3 4 51 −1 0 0

→

1 1 2 21 1 0 02 1 0 11 −2 −2 −2

→

1 1 2 21 1 0 02 1 0 11 −2 −2 −2

→

1 1 2 21 1 0 01 −2 −2 −22 1 0 1

→

1 1 2 21 1 0 01 −2 −2 −22 1 0 1

69


Entonces PA = LU , donde P = P3,4

L =

1 0 0 01 1 0 01 −2 1 02 1 0 1

U =

1 1 2 20 1 0 00 0 −2 −20 0 0 1

70


Teorema 3. Si A es invertible entonces la factorizacion A = LU esunica (cuando existe con P = I). Es decir, si es A invertible, A =L1U1 = L2U2 donde Li son triangulares inferiores con 1’s en la diagonaly Ui triangulares superiores, entonces L1 = L2, U1 = U2.

Demostracion: Si A es invertible entonces U1, U2 tienen inversas (sontriangulares con elementos en la diagonal no nulos).

Entonces, de A = L1U1 = L2U2 obtenemos L−12 L1 = U2U

−11 .

Como L1, L2 son triangulares inferiores con 1’s en la diagonal, L−12 L1 es

triangular inferior con 1’s en la diagonal

Como U1, U2 son triangulares superiores y U1 es invertible se tiene queU2U

−11 es triangular superior.

Entonces C = L−12 L1 = U2U

−11 es a la vez triangular inferior con 1’s en

la diagonal y triangular superior.

71


Por lo tanto C = I, es decir L−12 L1 = U2U

−11 = I, de donde L1 = L2,

U1 = U2.

72

A = LU Matrices

Factorizacion A = LDLT para A simetrica

Estudiamos la factorizacion A = LU para matrices simetricas:

73

A = LU Matrices

Para esta matriz tenemos entonces

L =

1 0 0 0

−2 1 0 0

3 −1 1 0

−1 3 2 1

D =

2 0 0 0

0 −1 0 0

0 0 3 0

0 0 0 2

U =

2 −4 6 −2

0 −1 1 −3

0 0 3 6

0 0 0 2

Note que U = DLT , D = diag(U)

U =

2 −4 6 −20 −1 1 −30 0 3 60 0 0 2

=

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

1 −2 3 −10 1 −1 30 0 1 20 0 0 1

= DLT

74

A = LU Matrices

Proposicion 5. Si A es simetrica de n × n y al pivotear en a1,1 se

transforma A en C =[a1,1 ∗0 B

]donde B es de n− 1× n− 1 entonces

B es simetrica.

Demostracion:

ci,j = ai,j −ai,1

a1,1a1,j 2 ≤ i, j ≤ n

cj,i = aj,i −aj,1

a1,1a1,i 2 ≤ i, j ≤ n

Como ai,j = aj,i , a1,j = aj,1, a1,i = ai,1 se tiene que ci,j = cj,i para2 ≤ i, j ≤ n, y por lo tanto BT = B. Esta ultima proposicion implica que lacolumna k de L transpuesta multiplicada por uk,k es igual a las fila k de U .

Matricialmente esto se escribe:

75

A = LU Matrices

Proposicion 6. Factorizacion de Cholesky A = LDLT (sin raızcuadrada) Si A es simetrica y cada submatriz principal de A esinvertible entonces A = LU con

U = DLT ,

donde D = diag(U). Es decir,A = LDLT .

Demostracion: Si A = LU entoncesAT = UTLT

= (DD−1U)TLT

= (D−1U)TDLT pues DT = D

= L1U1,

donde L1 = (D−1U)T , es triangular inferior con 1’s en la diagonal y U1 = DLT

es triangular superior.

76

Formas Cuadraticas Matrices

Como A es simetrica, AT = A y por lo tanto A = LU = L1U1. Puestoque la factorizacion A = LU es unica para matrices invertibles se tieneU = U1 = DLT .2

77


Formas Cuadraticas

Definicion 5. Si

A es de n× n y ~x = (x1, x2, . . . , xn)T ∈ Rn

decimos queF (~x) = ~xT A ~x

es una forma cuadratica en las variables x1, x2, . . . , xn.

Note que• F (~x) es escalar, es decir F : Rn → R.

~xT︸︷︷︸ A︸︷︷︸ ~x︸︷︷︸ = F (~x)1×n n×n n×1 1×1

• F (~0) = ~0T A ~0 = ~0T ~0 = 0

78


Un problema fundamental asociado a una forma cuadratica F (x) = ~xT A ~xes su clasificacion de acuerdo a si su signo es constante o no:

• A Definida Positiva

~xT A ~x > 0 para ~x 6= ~0

Es decir, F tiene un mınimo estricto en ~x = ~0.

• A Semi Definida Positiva

~xT A ~x ≥ 0 para ~x ∈ Rn

Es decir, F tiene un mınimo (no estricto) en ~x = ~0.

79


• A Definida Negativa

~xT A ~x < 0 para ~x 6= ~0

Es decir, F tiene un maximo estricto en ~x = ~0.

• A Semi Definida Negativa

~xT A ~x ≤ 0 para ~x ∈ Rn

Es decir, F tiene un maximo (no estricto) en ~x = ~0.

• A Indefinida

Existen ~x, ~y ∈ Rn tales que ~xT A ~x > 0, ~yT A ~y < 0

Es decir, F cambia de signo en torno a ~x = ~0 y F no tiene ni maximo nimınimo en ~x = ~0.

80


Las competencias mınimas que deben tener para esta seccion son:

• Dada una funcion F (~x) determinar si esta es una forma cuadratica.

• Si F (~x) es una forma cuadratica expresarla en la forma F (~x) = ~xTA~xdonde A es simetrica

• Calcular la factorizacion de Cholesky con y sin raız cuadrada de unamatriz simetrica definida positiva

• Expresar a una forma cuadratica como la suma ponderada de cuadrados

• Clasificar a una forma cuadratica.

• Saber demostrar propiedades basicas de matrices definidas positivas.

81


Formas Cuadraticas: A de 2× 2

Sea A de 2× 2

~xTA~x =[x1

x2

]T [a1,1 a1,2

a2,1 a2,2

] [x1

x2

]=

[x1 x2

] [ a1,1 x1 + a1,2 x2

a2,1 x1 + a2,2 x2

]= x1(a1,1 x1 + a1,2 x2) + x2(a2,1 x1 + a2,2 x2)

= a1,1 x21 + a1,2 x1x2 + a2,1 x2x1 + a2,2 x

22

= a1,1 x21 + (a1,2 + a2,1) x1x2 + a2,2 x

22

Observe que x1x2 aparece dos veces: a1,2x1x2 + a2,1x2x1 = (a1,2 + a2,1)x1x2

82


Para cualquier matriz B = (bi,j) de 2× 2 tal que

b1,1 = a1,1, b2,2 = a2,2, b1,2 + b2,1 = a1,2 + a2,1

se tiene que~xT B~x = ~xT A ~x.

En particular para

B =A + AT

2=

[a1,1 a1,2

a2,1 a2,2

]+[

a1,1 a2,1

a1,2 a2,2

]2

=

a1,1a1,2+a2,1

2

a2,1+a1,22 a2,2

tenemos

~xT B ~x = b1,1 x21 + (b1,2 + b2,1) x1x2 + b2,2 x

22

= a1,1 x21 + (a1,2 + a2,1) x1x2 + a2,2 x

22

= ~xT A ~x

83


Ejemplo 10.

x21 + 3x1x2 − 2x2

2 =[x1

x2

]T 1 3

0 −2

[ x1

x2

]= ~xT A1 ~x

=[x1

x2

]T 1 0

3 −2

[ x1

x2

]= ~xT A2 ~x

=[x1

x2

]T 1 1

2 −2

[ x1

x2

]= ~xT A2 ~x

=[x1

x2

]T 1 3/2

3/2 −2

[ x1

x2

]= ~xT B ~x

Note que en todos los casosAi+AT

i2 = B y B es simetrica.

84


Formas Cuadraticas: A de 3× 3

~xTA~x =

x1

x2

x3

T a1,1 a1,2 a1,3

a2,1 a2,2 a2,3

a3,1 a3,2 a3,3

x1

x2

x3

=

[x1 x2 x3

] a1,1 x1 + a1,2 x2 + a1,3 x3

a2,1 x1 + a2,2 x2 + a2,3 x3

a3,1 x1 + a3,2 x2 + a3,3 x3

= a1,1 x

21 + a1,2 x1x2 + a1,3x1x3 +

a2,1 x2x1 + a2,2 x22 + a2,3x2x3 +

a3,1 x3x1 + a3,2 x3x2 + a3,3x23

= a1,1 x21 + (a1,2 + a2,1) x1x2 + (a1,3 + a3,1)x1x3 +

a2,2x22 + (a3,2 + a2,3) x2x3 + a3,3x

23

Observe que xixj aparece dos veces: ai,jxixj + aj,ixjxi = (ai,j + aj,i)xixj

85


Para cualquier matriz B = (bi,j) de 3× 3 tal que

bi,i = ai,i, bi,j + bj,i = ai,j + aj,i (para i 6= j)

se tiene que~xT B~x = ~xT A ~x.

En particular para B = A+AT

2 tenemos

B =A+AT

2=

a1,1 a1,2 a1,3

a2,1 a2,2 a2,3

a3,1 a3,2 a3,3

+

a1,1 a2,1 a3,1

a1,2 a2,2 a3,2

a1,3 a2,3 a3,3

2 b1,1 b1,2 b1,3

b2,1 b2,2 b2,3

b3,1 b3,2 b3,3

=

a1,1a1,2+a2,1

2

a1,3+a3,1

2a2,1+a1,2

2 a2,2a2,3+a3,2

2a3,1+a1,3

2

a3,2+a2,3

2 a3,3

86


y por lo tanto~xT

(A + AT

2

)~x = ~xT A ~x

87


Ejemplo 11.

x21 + 3x1x2 − 2x1x3 + x2

2 + x2x3 + 2x23 =

=

x1

x2

x3

T 1 3 −20 1 10 0 2

x1

x2

x3

= ~xT A1 ~x

=

x1

x2

x3

T 1 2 −31 1 21 −1 2

x1

x2

x3

= ~xT A2 ~x

=

x1

x2

x3

T 1 3/2 −13/2 1 1/2−1 1/2 2

x1

x2

x3

= ~xT B ~x

Note que en todos los casosAi+AT

i2 = B y B es simetrica.

88


Formas Cuadraticas: A de n× n

~xTA~x =

x1

x2...xn

T

a1,1 a1,2 · · · a1,n

a2,1 a2,2 · · · a2,n... . . . ...

an,1 an,2 · · · an,n

x1

x2...xn

=

n∑i=1

xi(n∑

j=1

ai,jxj)

=n∑

i=1

n∑j=1

ai,jxixj

=n∑

i=1

ai,ix2i +

n∑i=1

∑j>i

(ai,j + aj,i)xixj

89


Note ademas que ~xTA~x es de 1× 1 y por lo tanto

~xTA~x = (~xTA~x)T

= ~xTAT (~xT )T

= ~xTAT~x

entonces ~xTA~x =~xTA~x+ ~xTAT~x

2

=~xT (A~x+AT~x)

2

=~xT (A+AT )~x

2

= ~xTA+AT

2~x

90


La siguiente formula es una generalizacion de la identidad

xy =(x + y)2 − x2 − y2

2para x, y ∈ R

Ella expresa el producto en terminos de cuadrados.

Lema 1. (Formula Polar) Si B es simetrica entonces

~xT B~y =(~x + ~y)T B(~x + ~y)− ~xT B~x− ~yT B~y

2

para ~x, ~y ∈ Rn.

Como caso particular, para B = I, como ~xT~x = ||~x||2, se obtiene

~x · ~y =||~x + ~y||2 − ||~x||2 − ||~y||2

2para ~x, ~y ∈ Rn,

91


Demostracion:

(~x+ ~y)TB(~x+ ~y) = (~x+ ~y)T (B~x+B~y)

= (~xT + ~yT )(B~x+B~y)

= ~xT (B~x+B~y) + ~yT (B~x+B~y)

= ~xTB~x+ ~xTB~y + ~yTB~x+ ~yTB~y

Pero ~xTB~y es de 1× 1 y BT = B, por lo tanto

~xT B~y = (~xT B~y)T = ~yT BT ~x = ~yT B~x.

Entonces,

(~x + ~y)T B(~x + ~y) = ~xT B~x + 2~xT B~y + ~yT B~y

92


de donde

~xT B~y =(~x + ~y)T B(~x + ~y)− ~xT B~x− ~yT B~y

2

93


Proposicion 7. Sea A de n× n entonces

1.- ~xTA~x =∑n

i=1

∑nj=1 ai,jxixj

2.- ~xTA~x = ~xT A+AT

2 ~x

3.- Existe una unica matriz simetrica B tal que

F (~x) = ~xT A~x = ~xT B~x para todo ~x ∈ Rn

y B = A+AT

2

Demostracion: Solo resta demostrar la unicidad de B en 3). Supongamosque existen matrices simetricas B,C tales que

(?) ~xT B~x = ~xT C~x

94


para todo ~x ∈ Rn Debemos demostrar que B = C. Por la formula polartenemos que para ~x, ~y ∈ Rn

~xTB~y =(~x+ ~y)TB(~x+ ~y)− ~xTB~x− ~yTB~y

2

=(~x+ ~y)TC(~x+ ~y)− ~xTC~x− ~yTC~y

2por (?)

= ~xTC~y (por formula polar)

Entonces ~xTB~y = ~xTC~y para todo ~x, ~y ∈ Rn. En particular, para los vectorescanonicos ~x = ei, ~y = ej tenemos

bi,j = eTi Bej = eT

i Cej = ci,j.

Por lo tanto B = C. De ahora en adelante identificamos a una formacuadratica F (~x) con la unica matriz simetrica B tal que F (~x) = ~xTB~x,~x ∈ Rn.

95


Ejemplo 12. Escriba la forma cuadratica siguiente como F (~x) = ~xTB~x,donde B es simetrica.

F (x1, x2, x3, x4) = 2x21 + 3x1x2 + x1x4 + x2

2 − 2x3x4 + 4x24

Solucion:

F (~x) =[

x1 x2 x3 x4]

2 3/2 0 1/23/2 1 0 0

0 0 0 −11/2 0 −1 4

x1

x2

x3

x4

B =

2 3/2 0 1/2

3/2 1 0 00 0 0 −1

1/2 0 −1 4

96


Recordemos que las formas cuadraticas se clasifican de acuerdo alcomportamiento de su signo.

A se dice:

1.- definida positiva si ~xTA~x > 0 para ~x 6= ~0.

2.- semi definida positiva si ~xTA~x ≥ 0 para ~x ∈ Rn.

3.- definida negativa si ~xTA~x < 0 para ~x 6= ~0.

4.- semi definida negativa si ~xTA~x ≤ 0 para ~x ∈ Rn.

5.- indefinida si existen ~x, ~y ∈ Rn tales que ~xTA~x < 0, ~yTA~y > 0.

97


Clasificacion de Formas Cuadraticas

Proposicion 8.

• A es negativa definida sii −A es positiva definida

• A es semi negativa definida sii −A es semi positiva definida

Demostracion: La proposicion es el resultado inmediato de la identidad

~xT (−A)~x = −~xT A~x

98


Note que si D = diag(d1, d2, . . . , dn) es una matriz diagonal entonces

~xTD~x =

x1

x2...xn

T

d1 0 · · · 00 d2 · · · 0... . . . ...0 0 · · · dn

x1

x2...xn

=

n∑i=1

di x2i

Por ejemplo, si di > 0, i = 1, 2, . . . , n entonces

~xT D~x =n∑

i=1

di x2i > 0 si ~x 6= ~0

y la matriz D serıa positiva definida. Ademas, si ~xTD~x > 0 para todo

99


~x ∈ Rn, se tendrıa necesariamente con

~x = ei = (0, . . . , 1, . . . , 0)(un 1 en el elemento i-esimo)

que

0 < ~xT D~x = eTi Dei =

n∑i=1

di x2i = di

Entonces D es positiva definida sii di > 0, i = 1, 2, . . . , n El mismo argumentodemuestra la siguiente proposicion

100


Proposicion 9. Sea D = diag(d1, d2, . . . , dn) matriz diagonal. Entonces

1.- D es definida positiva sii di > 0, i = 1, 2, . . . , n

2.- D es semi definida positiva sii di ≥ 0, i = 1, 2, . . . , n

3.- D es definida negativa sii di < 0, i = 1, 2, . . . , n

4.- D es semi definida negativa sii di ≤ 0, i = 1, 2, . . . , n

5.- D es indefinida sii existen i, j tales que di < 0 y dj > 0

101


Ejemplo 13. D =

2 0 00 3 00 0 1

es (simetrica) positiva definida pues

x1

x2

x3

T 2 0 00 3 00 0 1

x1

x2

x3

= 2x21+3x2

2+x23 > 0 si ~x = (x1, x2, x3)T 6= ~0

Similarmente, −2 0 00 −4 00 0 −3

es definida negativa,

−2 0 00 4 00 0 0

es indefinida

102


Proposicion 10. Sea A simetrica definida positiva, entonces

1.- A tiene inversa

2.- Cada submatriz principal Ak de k × k de A es simetrica definidapositiva

3.- Cada submatriz de A que se obtiene eliminando las mismas filas ycolumnas de A es simetrica definida positiva.

4.- Cada submatriz principal Ak de A tiene inversa

Demostracion:

1.- Si A no tuviera inversa, existirıa ~x 6= ~0 tal que A~x = ~0, por lo que~xTA~x = 0 con ~x 6== 0, y entonces A no serıa definida positiva. Por lotanto A definida positiva implica A tiene inversa.

103


2.- Es obvio que A simetrica implica Ak simetrica. Sea ~xk ∈ Rk 6= ~0, debemosdemostrar que ~xT

kAk~x > 0. Sea ~x = [~xTk , 0, . . . , 0]T ∈ Rn (completamos

~xk con ceros para obtener un vector ~x en Rn. Entonces ~x 6= ~0 , peroxk+1 = xk+2 = · · · = xn = 0. Por lo tanto

0 < ~xT A~x =n∑

i=1

n∑j=1

ai,jxixj =k∑

i=1

k∑j=1

ai,jxixj = ~xTk Ak~xk

Por lo tanto Ak es simetrica definida positiva

3.- Al poner un vector ~x con algunas componentes iguales a cero se obtieneque la submatriz C que se obtiene de A eliminando las mismas columnasy filas donde las componentes de vx son cero cumple

~xTk C~xk = ~xA~x > 0 si vxk 6= ~0

Entonces C es positiva definida. La simetrıa de C es inmediata de la

104


simetrıa de A.

4.- Como la submatriz Ak es simetrica positiva definida , por la parte 1) deesta proposicion Ak tiene inversa

105


Teorema 4. Sea A de n× n. Son equivalentes

1.- A es simetrica definida positiva

2.- (factorizacion de Cholesky sin raız cuadrada) Existen

• L triangular inferior con 1’s en la diagonal,• D = diag(d1, d2, . . . , dn) matriz diagonal con di > 0, i = 1, 2, . . . , n tal

que

A = LDLT

3.- (factorizacion de Cholesky con raız cuadrada) Existe R triangularsuperior invertible tal que

A = RT R

106


Demostracion: 1) implica 2) Si A es simetrica positiva definida, entoncescada submatriz principal Ak de A es invertible y por lo tanto se puede realizareliminacion de gauss sin intercambio forzado de filas y A = LU Como A essimetrica, se tiene U = DLT , y entonces A = LDLT . Falta demostrar que ladiagonal de D es positiva. En general, para ~x 6= ~0, realizando la substitucion~y = LT~x obtenemos

0 < ~xTA~x = ~xT (LDLT )~x

= (LT~x)T D (LT~x)

= ~yTD~y =n∑

i=1

diy2i

Eligiendo ~y = ei, es decir para ~x = (LT )−1ei 6= ~0 tenemos

0 < ~xT A~x = eTi Dei = di

Entonces la diagonal de D es positiva, y por lo tanto 1) implica 2)

107


2) implica 3) Supongamos que A = LDLT con di > 0. Definimos√D =

diag(√d1,√d2, . . . ,

√dn), Entonces

√D√D = D, y podemos escribir

A = LDLT

= L√D√DLT

= (L√D)((L(

√D)T )T

= (L√D)((L(

√D))T

= RT R

donde R = (L(√D)T . Como L es triangular inferior y

√D es diagonal y ellas

tienen inversas, R = (L(√D)T es triangular superior y tiene inversa.

108


3) implica 1) Si A = RTR, donde R es triangular superior invertible, entoncesAT = (RTR)T = RT (RT )T = RTR = A, por lo que A es simetrica. Ademas,si ~x 6= ~0

~xT A~x = ~xT RTR~x

= (R~x)T (R~x)

= ~yT~y = ||~y||2 > 0 si ~y = R~x 6= ~0.

Pero R invertible, ~x 6= ~0 implican ~y = R~x 6= 0. Entonces 3) implica 1)

109


La equivalencia entre 1) y 2) nos dice que

Para A es simetrica:A es positiva definida sii al realizar eliminacion degauss en A sin intercambios de filas se obtienenpivotes positivos

Como A es negativa definida sii −A es positiva definida obtenemos tambien

Para A es simetrica:A es negativa definida sii al realizar eliminacion degauss en A sin intercambios de filas se obtienenpivotes negativos

110


Ejemplo 14. SeaF (x1, x2, x3, x4) = 2x1

2 − 8x1 x2 + 8x1 x3 − 4x1 x4 + 10x22

−20x2 x3 + 16x2 x4 + 11x32 − 12x3 x4 + 17x4

2

• Clasifique a la forma cuadratica F (~x).• Si es factible, determine las factorizaciones de cholesky con y sin

raız cuadrada de la matriz simetrica que la representa.• Escriba la forma cuadratica como la suma ponderada de cuadrados

e indique el cambio de variables que diagonaliza esta formacuadratica.

Solucion: La forma cuadratica puede escribirse como F (~x) = ~xTB~x, Bsimetrica:

B =

2 −4 4 −2−4 10 −10 8

4 −10 11 −6−2 8 −6 17

111


Procedemos con la eliminacion de gauss sin intercambio de filas.

2 −4 4 −2−4 10 −10 8

4 −10 11 −6−2 8 −6 17

→

2 −4 4 −2-2 2 −2 42 −2 3 −2-1 4 −2 15

→

2 −4 4 −2-2 2 −2 42 -1 1 2-1 2 2 7

→

2 −4 4 −2-2 2 −2 42 -1 1 2-1 2 2 3

Como B es simetrica y al realizar eliminacion de gauss sin intercambio defilas y escalamientos de filas se obtienen pivotes positivos, B es positiva

112


definida. La factorizacion de Cholesky sin raız cuadrada es A = LDLT donde

D =

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

, L =

1 0 0 0−2 1 0 0

2 −1 1 0−1 2 2 1

La factorizacion de Cholesky con raız cuadrada de B es A = RTR donde

R =√DLT

=

√

2 0 0 0

0√

2 0 00 0 1 0

0 0 0√

3

1 −2 2 −10 1 −1 20 0 1 20 0 0 1

113


=

√

2 −2√

2 2√

2 −√

2

0√

2 −√

2 2√

20 0 1 2

0 0 0√

3

El cambio de variables que diagonaliza la forma cuadratica, es ~y = LT~x

y1

y2

y3

y4

=

1 −2 2 −10 1 −1 20 0 1 20 0 0 1

x1

x2

x3

x4

=

x1 − 2 x2 + 2 x3 − x4

x2 − x3 + 2 x4

x3 + 2 x4

x4

114


Con la substitucion ~y = LT~x obtenemos

~xTB~x = ~xTLDLT~x = (LT~x)TD(LT~x)

= ~yTD~y

= 2 y21 + 2 y2

2 + y23 + 3 y2

4

= 2 (x1 − 2x2 + 2x3 − x4)2 + 2 (x2 − x3 + 2x4)2 + (x3 + 2x4)2 + 3x24

115


Ejemplo 15. Sea

F (x1, x2, x3) = x21 − 2x1x2 + 3x1x3 + 3x2

2 − x2x3 + 2x23

• Si es factible, determine las factorizaciones de cholesky con y sinraız cuadrada de la matriz simetrica que representa a la formacuadratica.• Escriba la forma cuadratica como la suma ponderada de cuadrados

e indique el cambio de variables que diagonaliza esta formacuadratica.• Clasifique a la forma cuadratica F (~x).

Solucion:

F (~x) = ~xT B~x donde B =

1 −1 3/2−1 3 −1/23/2 −1/2 2

116


Procedemos a realizar eliminacion de gauss sin intercambio de filas.

B =

1 −1 3/2−1 3 −1/23/2 −1/2 2

→

1 −1 3/2-1 2 1

3/2 1 −1/4

→

1 −1 3/2-1 2 1

3/2 1/2 −3/4

Entonces la factorizacion de Cholesky de B es B = LDLT , donde

D =

1 0 00 2 00 0 −3/4

L =

1 0 0−1 1 03/2 1/2 1

117


Por lo tanto

~xTB~x = ~xTLDLT~x = (LT~x)TD(LT~x)

= ~yTD~y

= y21 + 2y2

2 −34y23

donde ~y = LT~x.

Es decir, y1

y2

y3

=

1 −1 3/20 1 1/20 0 1

x1

x2

x3

⇐⇒ y1 = x1 − x2 + 3/2 x3

y2 = x2 + 1/2 x3

y3 = x3

118


Entonces

~xTB~x = y21 + 2 y2

2 −34y23

= (x1 − x2 +32x3)2 + 2 (x2 +

12x3)2 − 3

4x2

3

Como la diagonal de D = diag(1, 2,−3/4) tiene elementos de distinto signo,la forma cuadratica es indefinida.

Por ejemplo, con y3 = 1, y2 = 0, y1 = 0, o equivalentemente, x3 = 1,x2 = −1/2, x1 = −2 tenemos F (−2,−1/2, 1) = −3/4 < 0. En cambio, concon y3 = 0, y2 = 1, y1 = 0, o equivalentemente, x3 = 0, x2 = 1, x1 = −1tenemos F (−1, 1, 0) = 2 > 0. La matriz B no tiene factorizacion real decholesky con raız cuadrada pues los elementos de la diagonal de D no sonpositivos.

119


Note que la tecnica que hemos utilizado para clasificar una formacuadratica ha sido realizar un cambio de variables o substitucion y reducir elproblema a la clasificacion de una forma cuadratica diagonal. Este procesorecibe el nombre de diagonalizacion de una forma cuadratica.

El siguiente teorema aclara la tecnica de reduccion de la clasificacion deuna forma cuadratica a la de otra, posiblemente mas sencilla de determinar.

120


Teorema 5. Sean B, V matrices de n × n. Si V es matriz invertible,entonces

• B es simetrica sii V TBV es simetrica

• B es simetrica definida positiva sii V T B V es simetrica definidapositiva

• B es simetrica definida negativa sii V T B V es simetrica definidanegativa

• B es simetrica semi definida negativa sii V T B V es simetrica semidefinida negativa

• B es simetrica indefinida sii V T B V es simetrica indefinida

Es decir, si V es invertible,

121


B y V TBV definen a formas cuadraticas del mismo tipo, cuando unade ellas es simetrica.

Para clasificar a una matriz simetrica B se busca una matriz V invertibletal que clasificar a V TBV sea mas simple de realizar.

Demostracion: Simetrıa:

Si B es simetrica, C = V TBV , entonces

CT = (V T BV )T = V T BT V = V T BV = C

y por lo tanto C es simetrica.

Si V es invertible, entonces B = (V −1)TCV −1 = WTCW , y por el loya demostrado, intercambiando los roles de B,C, tenemos que C simetricaimplica B simetrica. Entonces B es simetrica sii C = V TBV es simetrica.

122


Misma Clasificacion: Es el resultado inmediato de aplicar la substitucion~y = V ~x:

~xT C~x = ~xT (V T BV )~x = (V ~x)T B(V ~x) = ~yT B~y

Note que V invertible implica que ~x 6= ~0 sii ~y = V ~x 6= 0. 2.

123


Ejemplo 16. Demuestre que A es simetrica definida positiva sii A−1 essimetrica positiva definida

Solucion: Sea A simetrica definida positiva. Como (A−1)T = (AT )−1 = A−1

tenemos que A−1 es simetrica. Ademas para ~x 6= ~0 tenemos

~xT A−1~x = ~xT A−1AA−1~x = (A−1~x)T A(A−1~x) = ~yT A~y

donde ~y = A−10~x = V ~x, con V = A−1 es invertible.

Entonces A y A−1 tienen la misma clasificacion. Note que A−1 = V TAVy por el teorema anterior, A definida positiva implica A−1 definida positiva.

Hemos demostrado que A simetrica definida positiva implica A−1

simetrica definida positiva.

Poe este ultimo resultado, tomando a A como A−1, obtenemos queA−1 simetrica definida positiva implica (A−1)−1 = A es simetrica definidapositiva.

124


Ejemplo 17. Demuestre que

• ATA es simetrica semi definida positiva

• ATA es simetrica definida positiva sii Ker(A) = {~0} (sii las columnasde A son li.)

Solucion:

Sea B = ATA. Entonces, BT = (ATA)T ) = AT (AT )T ) = ATA = B, porlo que ATA es simetrica.

Ademas

(?) ~xT AT A ~x = (A~x)T (A~x) = ||Ax||2 ≥ 0

Por lo tanto ATA es simetrica semi positiva definida.

125


Ahora si Ker(A) = {~0} entonces A~x 6= ~0 para ~x 6= ~0. Entonces por(?) tenemos que ~xT ATA ~x > 0 cuando ~x 6= ~0. Hemos demostrado queKer(A) = {~0} implica que ATA es simetrica definida positiva.

Ahora, si ATA es definida positiva, entonces 0 < ~xT ATA ~x = ||A~x||2 ypor lo tanto A~x 6= ~0 cuando ~x 6= ~0. Es decir, Ker(A) = {~0}.

Hemos demostrado que ATA es definida positiva implica que Ker(A) ={~0}.

126


Ejemplo 18. Demuestre que toda matriz simetrica definida positivatiene diagonal principal positiva, pero existen matrices simetricas condiagonal positiva que no son definidas positivas.

Solucion:

Si A es definida positiva entonces ~xTA~x > 0 para ~x 6= ~0.

Tomando ~x = ei obtenemos que ai,i = eTi Aei > 0.

Entonces la diagonal principal de A es positiva.

Construimos una matriz de 2× 2 simetrica con A = LU , con la diagonalde U no es positiva, pero la diagonal de A es positiva. Esto es facil:

A =[

1 22 1

]→[

1 20 −3

]Entonces los pivotes no son todos positivos y A es indefinida, pero ladiagonal de A es positiva.

127


Note que NO toda matriz simetrica A se puede factorizar como A =LDLT . Ejemplo:

A =[

0 11 0

]Esto sucede cuando A tiene submatrices principales no invertibles.

En este ejemplo A1 = (a1,1) no es invertible, por lo que es necesario unintercambio forzado de filas.

La matriz A de este ejemplo es indefinida.

Las matrices semi positivas o negativas definidas tienen submatricesprincipales no invertibles.

El metodo visto, tal como esta no se puede usar para clasificar matricessimetricas que tengan submatrices principales no invertibles

La factorizacion de cholesky como esta permite clasificar a matricesdefinidas positivas o negativas.

128


Permitiendo el ”pivoteo por la diagonal” se puede adaptar el metodo a laclasificacion de matrices que tengan submatrices principales no invertibles.

Este metodo no lo vemos en este curso.

Desde el punto de vista numerico, la factorizacion de cholesky se puedecalcular en forma numericamente estable, es decir, el redondeo en lasoperaciones aritmeticas de punto flotante no tiene mayor impacto en laprecision relativa de los resultados.

129

alu, palu y formas cuadráticas

Documents