cap 3 - laecya · con la descomposicion-lu es simple resolver un sistema de ecuaciones lineales en...

23
Cap 3: Cap 3: Álgebra lineal Álgebra lineal Prof: J. Solano Universidad Nacional de Ingeniería Facultad de Ciencias Maestría en Ciencia de la Computación Cálculo Numérico 1 IF321

Upload: others

Post on 20-Aug-2020

5 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Cap 3: Cap 3: Álgebra lineal Álgebra lineal

Prof: J. Solano

Universidad Nacional de IngenieríaFacultad de Ciencias

Maestría en Ciencia de la Computación

Cálculo Numérico 1IF321

Page 2: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

INTRODUCCIONINTRODUCCION

2

Aqui trabjaremos con operaciones basicas con matrices, tales como solucion de ecuaciones lineales, calculo de inversa de matriz, su determinante, etc.

Detalles importantes de programacion tales como manejo de asignacion de memoria para matrices, introduccion al concepto de clases, templates.

Trabajaremos principlamente con matrices simetricas o hermitianas.

En aras de la simplicidad, echemos un vistazo a una matriz (4x4) A y una matriz identidad correspondiente I.

La inversa de una matriz es definida por

Una propiedad de las matrices simetricas y hermitianas es que tienen autovalores reales

Page 3: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Propiedades de matricesPropiedades de matrices

3

Page 4: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamaño fijoDeclaracion de vectores y matrices de tamaño fijo

4

Page 5: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamanho fijoDeclaracion de vectores y matrices de tamanho fijo

5

Page 6: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamaño fijoDeclaracion de vectores y matrices de tamaño fijo

6

Page 7: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamaño dinámicoDeclaracion de vectores y matrices de tamaño dinámico

7

Page 8: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamanhoDeclaracion de vectores y matrices de tamanhodinámicodinámico

8

Page 9: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamañoDeclaracion de vectores y matrices de tamañodinámicodinámico

9

Page 10: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamanhoDeclaracion de vectores y matrices de tamanhodinámicodinámico

10

Page 11: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Declaracion de vectores y matrices de tamañoDeclaracion de vectores y matrices de tamañodinámicodinámico

11

Page 12: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-LU de una matrizDescomposicion-LU de una matriz

12

Una matriz mxn se dice que tiene descomposicion-LU si existen matrices L y U con las siguientes propiedades:

- L es una matriz triangular inferior mxn con todas los elementos en la diagonal siendo 1

- U es una matriz m×n en alguna forma escalonada

- A = LU

Ventajas de la descomposicion:

Suponga que queremos resolver el sistema mxn, Ax = b

Si podemos hallar una descomposicion-LU para A, entonces para resolver AX=b es suficiente resolver los sistemas (Ax=b equivale a LUx=b)

Ly = b

Ux = y

Entonces el sistema Ly = b puede ser resuelto por el método de sustitución hacia adelante y el sistema Ux = y puede ser resuelto por el método de sustitución hacia atrás.

Para ilustrar esto, le damos algunos ejemplos

Page 13: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-LU de una matrizDescomposicion-LU de una matriz

1313

Considere el sistema Ax = b, donde

x1 + 2 x

2 = 2

3 x1 + 6 x

2 – x

3 = 8

x1 + 2 x

2 + x

3 = 0

Es facil chequear que A=LU, donde

Para resolver Ax=b, primero resolvemos Ly = b por sustitucion hacia adelante

para obtener

Ahora resolvemos Ux = y por sustitucion hacia atras:

obteniendose x1= 6, x

2= -2, x

3= -2

Page 14: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-LU de una matrizDescomposicion-LU de una matriz

1414

Sea matriz A4x4

tq A=BC

Comenzamos con la primera columna

Que determina los elementos c11

, b21

, b31

, b41

. Ahora para la segunda columna

Aqui los valores desconocidos son c12

, c22

, b32

y b42

, que pueden ser evaluados por A y por el resultado anterior

Page 15: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-LU: algoritmo de CroutDescomposicion-LU: algoritmo de Crout

15

Podemos generalizar este procedimiento en tres ecuaciones

Para cada columna (j) calculemos el primer elemento c1j por: c

1j = a

1j

Luego calculamos todos los elementos cij , i = 2, …, j-1

Ahora calculamos los elementos de la diagonal cjj,

Finalmente calculamos los elementos bij , i > j.

En el caso que es cero o cercano a cero, lo que lleva a perdida de precision, hay que usar un metodo de pivoteo (intercambiano filas) en torno al mayor elemento de la columna

Page 16: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Solucion de sistema de ecuaciones linealesSolucion de sistema de ecuaciones lineales

1616

Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales

En forma matricial: Ax = w

Usando la descomposicion-LU: Ax = BCx = w

Se puede calcular esta ecuacion en dos pasos: By = w ; Cx = y

Para nuestro ejemplo 4-d

esto toma la forma:

y

Page 17: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Inversa de una matriz y determinanteInversa de una matriz y determinante

17

Def. basica de determinante:

la suma es sobre todas las permutaciones p de los indices 1,2,...,n, que dan n! terminos.

Igual, para caclular la inversa de A hay que calcular el cofactor de c/elemento aij, que es un

(j-1) determinante. Esto significa el calculo de n2 determinantes. DEMASIADO!!!

Una matriz A con descomposicion-LU: det{A} = det{B} x det{C) = det{C}

ya que los elementos diagonales de B son 1.

Entonces el determinante de A es:

La inversa es algo mas complicada. Formalmente, dado A=BC: A-1 = C-1 B-1

La razon es que la inversa de una matriz triangular superior (inferior) tambien es una matriz triangular superior (inferior)

Page 18: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Inversa de una matriz y determinanteInversa de una matriz y determinante

18

Si llamamos D a la inversa de B, se pueden determinar los elementos de la matriz de la ec

que lleva al algoritmo general

que es valido para i > j. La diagonal es 1 y los elementos del triangulo superior son cero. Resolvemos la ecuacion columna por columna (incrementando j).

Page 19: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Inversa de una matriz y determinanteInversa de una matriz y determinante

19

Similarmente definimos una ecuacion que da la inversa de C (la llamamos E)

con la ecuacion general (para i<= j)

Page 20: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Solucion de sistema de ecuaciones linealesSolucion de sistema de ecuaciones lineales

20

Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales

En forma matricial: A x = w

A-1 A x = A-1 w

I x = A-1 w

x = A-1 w

Tambien se puede resolver usando las librerias de Matlab

Page 21: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-QR de una matrizDescomposicion-QR de una matriz

2121

Descomposición QR (factorización QR) de una matriz es una descomposición de una matriz A en un producto A = QR de una matriz ortogonal Q y una matriz triangular superior R. La descomposición QR se usa a menudo para resolver el problema de mínimos cuadrados lineales. y es la base para el algoritmo QR (eigenvalues).

Factorización QR de una matriz.

Dada una matriz A (no necesariamente cuadrada), con columnas linealmente independientes, encontraremos matrices Q, R tales que:

(i) A = QR.

(ii) Las columnas de Q son ortonormales.

(iii) Q es del mismo tamaño que A.

(iv) R es triangular superior invertible.

Page 22: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-QR de una matrizDescomposicion-QR de una matriz

22

La forma de hacerlo es aplicar el proceso de Gram-Schmidt a las columnas de A.

Ejemplo. Tomemos

Las columnas son

Aplicando

Gram-Schmidt

Page 23: Cap 3 - LAECyA · Con la descomposicion-LU es simple resolver un sistema de ecuaciones lineales En forma matricial: A x = w A-1 A x = A-1 w I x = A-1 w x = A-1 w Tambien se puede

Mëtodos Numéricos - MCC613

Descomposicion-QR de una matrizDescomposicion-QR de una matriz

23

Ahora tenemos