Programacion Cuadratica

Cap´ ıtulo 2

Programaci´n cuadr´tica o a
2.1.
2.1.1.

Preliminares de ´lgebra lineal a
Determinantes de matrices

El concepto del determinante est´ relacionado con el ´rea de un paralelogramo definido por dos a a vectores y el volumen de un paralelep´ ıpedo definido por tres vectores. Ver la Figura 2.1 El determinante de una matriz 2 ⇥ 2 es det(A) = (A)1,1 (A)2,2 (A)1,2 (A)2,1 y eldeterminante de una matriz 3 ⇥ 3 det(A) =(A)1,1 (A)2,2 (A)3,3 + (A)1,2 (A)2,3 (A)3,1 + (A)1,3 (A)2,1 (A)3,2 (A)1,3 (A)2,2 (A)3,1 (A)1,1 (A)2,3 (A)3,2 (A)1,2 (A)2,1 (A)3,3 .

La conocida como regla de Sarrus es un truco mnemot´cnico para recordar esta f´rmula. Dicha regla e o

x3

a3

x2 a1

a2 x1

a2 x1 a1

x2

Figura 2.1: En el panel de la izquierda aparece un paralelogramo con lados a1y a2 . El determinante de una matriz cuyas columnas son los vectores a1 y a2 es el ´rea de la superficie sombreada. El determinante a de una matriz 3 ⇥ 3 se interpreta geom´tricamente como el volumen del paralelepipedo determinado por e las tres columnas de la matriz como el que se muestra en el panel de la derecha. 17

´ ´ CAP´ ITULO 2. PROGRAMACION CUADRATICA consiste en a˜adir las dosprimeras columnas a la derecha de la matriz. El producto de los elementos de n las diagonales que forman de arriba–izquierda a abajo–derecha se suman y el producto de los elementos en la diagonales que se forman de arriba–derecha a abajo–izquierda se restan. (A)1,1 (A)2,1 (A)3,1 (A)1,2 (A)2,2 (A)3,2 (A)1,3 (A)2,3 (A)3,3 (A)1,1 (A)2,1 (A)3,1 (A)1,2 (A)2,2 (A)3,2

Para matrices de mayor tama˜o existeuna generalizaci´n de este concepto y m´todos de c´lculos que n o e a se recogen en la Secci´n 2.B. El c´lculo de los determinantes est´ implementado en todos los programas o a a de c´lculo num´rico. a e Ejemplo 2.1. Calculemos el determinante 1 4 2 0 1 1 2 1 3 = 1 · 0 · 3 + 4 · ( 1) · 1 + 1 · 2 · 1 1 · ( 1) · 1 4·2·3 2·0·1= 23

2.1.2.

Inversa de una matriz

Una matriz A de tama˜o n ⇥ n sedice que es invertible si existe una matriz A 1 del mismo tama˜o n n tal que A A 1 = A 1 A = I. A la matriz A 1 se le denomina inversa de A.  a b Una matriz A = de tama˜o 2 ⇥ 2 es invertible si ad bc 6= 0 y su inversa es n c d  1 d b A 1= c a ad bc El procedimiento para el c´lculo de inversas de tama˜o mayor que dos es recogido en la secci´n 2.A. a n o  1 2 Ejemplo 2.2. La inversa de la matriz esA = es 5 8   1 8 2 4 1 1 A = = 5 1 5/2 1/2 1·8 5·2

2.1.3.

Autovalores

Sea A una matriz cuadrada m ⇥ m. Un escalar 2 R se dice autovalor o valor propio de la matriz A si verifica que det(A I) = 0. Un vector x 2 Rm no nulo se dice autovector o vector propio de A asociado a un autovalor 2 R si Ax = x. Teorema 2.1. Sea A una matriz de tama˜o m ⇥ m y n 1. es un autovalor de A; Im )x = 0tiene soluci´n no trivial; o Im . 2. (A 2 R. Son equivalentes:

3. No es invertible la matriz A

Sea A una matriz de tama˜o m ⇥ m. La funci´n pA ( ) = det(A n o Im ) es un polinomio de grado m. Al polinomio pA ( ) se le llama polinomio caracter´ ıstico de A. A la ecuaci´n det(A o Im ) = 0 se le llama ecuaci´n caracter´ o ıstica de A. Para calcular autovalores y autovectores se emplean usualmenteprogramas de c´lculo num´rico. Para a e algunos casos sencillos se pueden encontrar por el procedimiento de la secci´n 2.C. o 18

Optimizaci´n matem´tica o a

2.1.4.

Matrices sim´tricas e

Sea A una matriz m ⇥ m, se dice sim´trica si AT = A. e  7 2 Ejemplo 2.3. La matriz es sim´trica. e 2 8 Ejemplo 2.4. La matriz 2 4 6 2 6 4 1 0 2 0 2 5 1 2 1 3 3 0 5 7 7 3 5 0

es sim´trica. e2.1.5.

Matrices ortogonales

Si escribimos los vectores de un sistema ortonormal de Rm por columna formamos una matriz que se denomina ortogonal. Una matriz A se dice ortogonal si es cuadrada y AT A = I. Teorema 2.2. Sea A un matriz cuadrada m ⇥ m. Entonces, A es ortogonal si, y s´lo si, sus columnas o forman un sistema ortonormal de Rm . Obs´rvese que la matriz sea ortogonal implica que sus...