alu, palu y formas cuadráticas

Factorizacion PA=LU

Prof. I. HuertaFacultad de Matematicas

UC

ihuerta@mat.puc.cl

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

• 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 Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

• 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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

• 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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

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

Factorizacion A=LU Tabulacion de Datos

−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

Factorizacion A=LU Tabulacion de Datos

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 Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

• 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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

• 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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Tabulacion de Datos

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Factorizacion PA=LU Aplicaciones

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

Matrices Diagonales Matrices

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

Matrices Diagonales Matrices

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

Matrices Diagonales Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Matrices Triangulares superiores Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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

Propiedades A = LU Matrices

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 Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

• 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

Formas Cuadraticas Matrices

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 Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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 Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

y por lo tanto~xT

(A + AT

2

)~x = ~xT A ~x

87

Formas Cuadraticas Matrices

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 Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

de donde

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

2

93

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

~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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

simetrıa de A.

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

105

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

=

√

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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

Formas Cuadraticas Matrices

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