Optimizacin
Tarea #1 Recuerde que: Las tareas deben realizarse de manera INDIVIDUAL. Esto quiere decir que aunque es vlido discutir los problemas con sus compaeros, la solucin debe ser de su completa autora. En particular est prohibido resolver problemas en grupo, y por supuesto copiar la solucin y/o procedimiento desarrollado por otro estudiante, u obtener soluciones del internet u otros medios. Cualquier transgresin a esta regla se considerar FRAUDE y se reportar sin excepciones. Las tareas deben entregarse antes de la fecha y hora lmites sealadas para su entrega. NO se recibirn tareas tarde. La calicacin de las tareas se har de manera selectiva de acuerdo a criterio del profesor. 1. Considere el sistema de m ecuaciones en n incginitas (con m n) Ax = b. Una solucin bsica del sistema de ecuaciones se dene como una solucin en la cual a lo sumo m variables son diferentes de cero (estas se llaman variables bsicas). Para el caso: 0 0 2 3 3 1 2 4 1 2 3 2 4 4 , b = A= 0 3 0 0 1 0 1 0 1 1 1 8 1 0 a) Halle todas las soluciones de este sistema de ecuaciones. b) Encuentre todas las soluciones bsicas del sistema. 2. Una matriz B es similar a una matriz A (denotado por B A) si existe una matriz invertible P tal que B = P1 AP. Demuestre que: (a) Si B A, entonces A B. (b) Si B C y A C entonces A B (c) Matrices similares tienen los mismos valores propios. (d) Matrices similares pueden tener vectores propios diferentes (Ayuda: construya un contraejemplo con matrices 2 2). 3. a) Halle la matriz P = aaT /aT a que proyecta cualquier vector sobre la linea a travs T de a = 2 1 2 . b) Cul es el nico valor propio de P diferente de cero y cul es el vector propio correspondiente? c) Resuelva uk+1 = Puk comenzando en u0 = 9 9 0
T
Entrega: Agosto 31 de 2009, 2 p.m.
4. Suponga que se conoce la matriz inversa de una matriz A0 Rmm . Se desea calcular la inversa de una nueva matriz: A1 = A0 + XRY donde X, YT Rmr , R Rrr . Una forma de calcular esta inversa es utilizar la frmula de Sherman-Morrison-Woodbury: A1 = A1 A1 X(YA1 X + R1 )1 YA1 1 0 0 0 0 (2) (1)
Note que dada A1 , esta frmula requiere el clculo de la inversa de matrices de tamao 0 r, mientras que en el clculo directo se requiere invertir una matriz de tamao m. Ya que el costo de la inversin de una matriz es proporcional aproximadamente al cubo de su tamao, este clculo es mucho ms eciente para r < m. a) Verique que el lado derecho de (2) es efectivamente A1 (Ayuda: pre-multiplique 1 y pos-multiplique (2) por A1 dado en (1). b) Usando MATLAB, halle los valores propios 1 , 2 , 3 , 4 y los vectores propios correspondientes u1 , u2 , u3 , u4 de la siguiente matriz: 10 4 2 0 4 10 0 2 B= 2 0 10 4 0 2 4 10 c) Usando la descomposicin espectral B = 4 i ui uT , aplique cuatro veces la fri i=1 mula de Sherman-Morrison-Woodbury para calcular (a mano) la inversa de la matriz I + B (note que en este caso R = 1). Verique su resultado usando MATLAB 1 5. Sea Q Rnn una matriz positiva denida. a) Demuestre que x, y Q1 = xT Q1 y es un producto interno en Rn . b) Sean v1 , v2 , . . . , vn las columnas de Q. Demuestre que vi , vj donde qij es la entrada i, j de Q. 6. a) Demuestre que los vectores propios de una matriz A con valores propios diferentes son linealmente independientes. b) Demuestre que los vectores propios de una matriz simtrica A con valores propios diferentes son ortogonales.
Q1
= qij
7. Demuestre que para una matriz simtrica A
n
tr(A) =
i=1
donde tr(A) representa el operador traza, el cual suma los elementos de la diagonal de A. Ayuda: Primero demuestre que tr(CD) = tr(DC).
Para una introduccin al uso de matlab, abra MATLAB ,escriba "helpwin", y vaya a "Begin here", o haga click aqu.
1
8. (a) Halle el rango y los cuatro valores propios para las matrices de unos y de tablero de ajedrez: 1 1 A= 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 C= 0 1 1 0 1 0 0 1 0 1 1 0 1 0
Cules son los vectores propios correspondientes a los valores propios diferentes de cero? (b) Halle el rango y los valores propios para las matrices de unos y de tablero de ajedrez de tamao n n. Cuntos valores propios diferentes a cero hay en este caso? (c) Si A es la matriz de unos de tamao 4 4, halle los valores propios y el determinante de A I. 9. Sea f (w) una funcin escalar de un vector w de dimensin n. El gradiente de f (w) con respecto a w est denido como: w f (w) = (a) Sea 1 f (w) = wT Aw + bT w + c 2 donde A es una matriz simtrica de n n, b es un vector de n 1 y c es un escalar. Muestre que: w f (w) = Aw + b (b) La matriz Hessiana est denida como: H=
T 2 f (w) 2 w1 2 f (w) w2 w1 2 f (w) w1 w2 2 f (w) 2 w2 f (w) w1 f (w) w2
. . .
f (w) wn
... ... .. . ...
w f (w))
2 f (w) = w
2 f (w) w1 wn 2 f (w) w2 wn
. . .
2 f (w) wn w1
. . .
. . .
2 f (w) 2 wn
2 f (w) wn w2
Para f (w) denida anterioremente demuestre que: H=
2 w f (w)
=A
10. Considere la funcin cuadrtica f (x) = xT Ai x. (a) Utilice las funciones contour y mesh de MATLAB para gracar la funcin f y sus curvas de contorno en el rango [1, 1]2 , para las siguientes matrices: 3 2 , 2 3 2 3 , 3 2 3 9,5 0,5 , 0,5 9,5 9,5 0,5 0,5 9,5
A1 =
A2 =
A3 =
A4 =
(b) Halle los valores propios y vectores propios para las matrices A1 , A2 , A3 , A4 . Cmo se relacionan estos valores con las grcas que usted obtuvo?.
