Métodos Numéricos

DEPARTAMENTO DE CIENCIAS EXACTAS

ASIGNATURA: Metodos Numericos

NRC: 1668

TEORIA DEL SEGUNDO PARCIAL

TEMA: Factorizacion de matrices e interpolacion

PROFESOR: Dr. Medina

ALUMNOS:

Asimbaya Israel

FECHA DE ENTREGA: 07 de julio del 2015

SANGOLQUI-ECUADOR

ABRIL 15 - AGOSTO 15

1

Indice

1. Sistemas lineales y repaso Algebra lineal 31.1. Sistemas lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2. Repaso de conceptos de Algebra lineal . . . . . . . . . . . . . . . 3

2. Resolucion de Sistemas de Ecuaciones Lineales por Metodo deGauss 5

3. Resolucion de Sistemas Lineales por Gauss Jordan 6

4. Factorizacion LU 7

5. Tratamiento de imagenes con uso de SVD 9

6. Descomposicion de matrices SVD 11

7. Interpolacion 137.1. Interpolacion de Lagrange . . . . . . . . . . . . . . . . . . . . . . 147.2. Interpolacion de Newton . . . . . . . . . . . . . . . . . . . . . . . 15

2

Metodos Numericos NRC: 1668 Israel Asimbaya

1. Sistemas lineales y repaso Algebra lineal

1.1. Sistemas lineales

Se presentan problemas matematicos los cuales pueden ser resueltos pormedio de un sistema lineal de tipo Ax = b el mismo que puede tener unacantidad igual de ecuaciones como de variables, ademas de esto, el algebra linealpermite la resolucion de sistemas lineales, por metodos de obtencion de susvalores y vectores propios. Dentro de las tecnicas para resolver sistemas linealesencontramos dos:

Metodos directos Los cuales se emplean siguiendo un numero finito deoperaciones para la obtencion de una solucion. [?]

Metodos iterativos Los cuales usan una relacion de recurencia para obteneruna sucesion infinita, logrando asi una estimacion la misma que convergecon la solucion que se busca.[?]

En el empleo de resolucion de sistemas lineales implica el uso de determinan-tes por medio de ecuaciones de tipo Ax = b. Es aplicable pero no optimo porel numero de operaciones necesarias la metodologa de Gauss y Gauss Jordanestudiadas previamente. Existen otros tipos de factorizacion como

LUQue implica la descomposicion matricial en otras dos nuevas matrices,una triangular superior y otra triangular inferior, Tambien se considerauna matriz de permutacion que se determina al desarrollar el ejercicio.

SVDEste tipo de resoluciones implica el desarollo y obtencion de valores singu-lares y vectores propios de una matriz. Permite un amplio rango de datos,ya las matrices operadas no son necesariamente pequenas, ademas quepermite obtener mejores calculos dado el condicionamiento de matricesque permite reducir el error en el momento de obtencion de resultados.SV D tambien es el principio de compresion de imagenes, lo que permitetrabajar con imagenes de forma matricial y numerica en matlab.

QRPara la resolucion de este metodo se emplea la formulacion de una matrizortonormal.

Todos estos metodos de resolucion lineal seran detallados a continuacion.

1.2. Repaso de conceptos de Algebra lineal

Los conceptos completos pueden encontrarse en libros de Algrebra linealincluso en el libro gua usado de Sanchez [?], a continuacion un breve resumende los conceptos mas importantes para el estudio posterior de sistemas lineales.

Ingeniera Mecatronica 3


1. Matrices

Se denota como Mmxn(R) donde m hace referencia al numero de las filasy n a las columnas existentes en el espacio vectorial de la matriz, loselementos de la matriz pueden ser R o C

2. Tipos de matrices

AT Matriz transpuestaDonde la matriz original Amxn se convierte en A

Tnxm.

A Matriz conjugadaEsta matriz al tener valores imaginarios, estos cambian de signo paracconvertirse en la matriz conjugada.

A+ Matriz adjuntaTambien conocida como la matriz transpuesta de la matriz conjugadadonde A+ = (A)T .

Matriz HermticaDonde A = A+ y A = AT entonces A = AA+

Matriz Simetrica A = AT

Matriz Antisimetrica A = ATMatriz Unitaria A1 = A+

Matriz Ortogonal Si AT = A+

Matriz Normal Si A+A = AA+

3. Matriz inversaSe dice que una matriz tiene inversa si

A1 existe

detA 6= 0El sistema lineal Ax = b, tiene una unica solucion x = 0

Para cualquier vector b, el sistema lineal Ax=b tiene solicion unica.

Las filas y las columnas son linealmente independientes.

El rango de la matriz A es n (no existen filas nulas en la matriz)

4. Matrices diagonal dominante o estrictamente dominante

Diagonal dominanteSe cumple si el elemento de la diagonal principal es mayor o igual ala sumatoria de los elementos de la fila perteneciente al elemento dela diagonal.

Diagonal estrictamente dominante

5. Valores y Vectores Propios



Espectro de A: es el conjunto de todos los valores propios o autova-lores de A

Radio espectral: (A) =max |i|Elemento propio: es la pareja de el autovalor y el vector propio

2. Resolucion de Sistemas de Ecuaciones Linea-les por Metodo de Gauss

El metodo de Gauss implica utlizar los coeficientes de las ecuaciones linealesordenadas de tal forma que se obtenga una matriz U el que contiene dichoscoeficientes y b que contiene los valores a la que esta igualada la ecuacion. Seemplea la siguiente formula en orden de resolver los sistemas.

Ux = b.

U =

a11 a12 . . a1n0 a22 a23 . a2n0 0 a33 . a3n. . . . .0 0 0 0 ann

b =

b11b21b31.bn1

Resolucion del sistema de una matriz A2x2(

a11 a120 a22

) b =

(b11b21

)Para encontrar los valores de x

x2 =b2a22

.

x1 =b1 a12x2

a11.

Resolucion del sistema de una matriz A2x2 a11 a12 a130 a22 a230 0 a33

b = b11b21

b31

Los valores de x seran

x3 =b3a33

.

x2 =b2 a23x3

a22.

x1 =b1 a23x3 a13x2

a11.



Estas operaciones se realizaran consecuentemente segun el numero de incognitasempezando desde el ultimo valor encontrado en la ultima fila de la matriz A yb.

Caracteristicas del Metodo de Gauss

La matriz A es una matriz triangular superior formada a partir de opera-ciones elementales y reduccion de filas y columnas.

En el caso de existir ceros en la diagonal principal es necesario realizar uncambio de las filas, mas no de las columnas dado a que estas contienen lasdiverentes variables .

La reduccion bajo la diagonal va a alterar los valores tanto de la matrizA como la batriz b

Para el metodo de resolucion de Gauss Jordan, Existe una diferencia signi-ficativa dado a que el metodo de resolucion por Guass implica una matrizresultante por reduccion de filas de tipo triangular superior, el metodo deGauss Jordan trabaja con una matriz identidad.

3. Resolucion de Sistemas Lineales por GaussJordan

Para una matriz Aa11 a12 . . a1na21 a22 a23 . a2na31 a32 a33 . a3n. . . . .an1 an2 an3 . ann

Reduccion por filas y columnas

a11 0 . . 00 a22 . . 00 0 a33 . 0. . . . .0 0 0 0 ann

Donde la matriz resultante solo tiene valores en la diagonal principal o en sudefecto es una matriz identidad.

Ux = b.a11 0 . . 00 a22 . . 00 0 a33 . 0. . . . .0 0 0 0 ann

x11x21x31.xn1

=

b11b21b31.bn1

Para la definicion de los valores de las variables de x comienza desde la fila

del final hacia arriba de la siguiente manera:

xn =bn1ann

.



4. Factorizacion LU

Se conoce a la factorizacion LU como un proceso resumido similar a la eli-minacion Gaussiana que consiste en reducir una matriz en triangular superiore inferior para obtener de esta forma una similitud entre una matriz nueva P omatriz de permutacion, con la matriz original, de la siguiente forma:

A = LU.

PA = LU.

Donde P es una matriz de permutacion que descifraremos a continuacion.Para un sistema lineal

Ax = b.

Donde se necesita definir el valor de la variable x tenemos:{Ly = PbUx = y

Donde Ly = Pb resultara en una matriz triangular inferior y Ux = y sera unamatriz triangular superior, la misma que contendra los valores buscandos de x.

Ejemplo

A =

4 3 12 4 51 2 6

Encontramos la matriz triangular superior de la sifuiente forma:

A =

4 3 12 4 51 2 6

Para lograr la matriz superior se aplican operaciones elementales una a la vez alas filas por lo cual se desarrollan las sifuientes:

F2 +1

2F1.

F3 14F1.

obteniendo:

A =

4 3 10 5

292

0 55

254

Realizando otra operacion elemental:

F3 +1

2F2.



Resultando:

U =

4 3 10 52

92

0 0 172

Obtenemos la primera matriz resultante en este caso U que es una matriz

triangular superior. Por otro lado la matriz triangular inferior vendra a sercompuesta por las operaciones elementales que han sido aplicadas a la matrizoriginal de este modo:

L =

1 0 012

1 014 12 1

Si observamos bien, la matriz L sera compuesta inicialmente por una matrizcuadrada identidad, del mismo numero de filas de la matriz original, en la cual,sus ceros debajo de la diagonal princial han sido sustituidos por los coeficientesde las operaciones elementales realizadas a la matriz original.Una forma de comprobar las operaciones es operar la matriz LU de tal formaque la matriz resultante sea A 1 0 01

21 0

14 12 1

4 3 10 5

292

0 0 172

= 4 3 12 4 5

1 2 6

Al realizar estas operaciones vemos que no se implemento la matriz de permu-taciones pero la misma sera usada si se requiere cambiar las filas de una matriz,si la matriz no lo requiere se emplea el metodo de Crout

Metodo de Crout

a11 a12 a13a21 a22 a23a31 a32 a33

= L11 0 0L21 L22 0

L31 L32 L33

1 U12 U130 1 U23

0 0 1

Donde:

a11 = L11.

a12 = L11U12 U12.a13 = L11U13 U13.

Ahora analizaremos cuando se debe implementar el uso de una matriz de per-mutacion.



Tenemos:

A =

1 2 64 8 12 3 5

F2 4F1F3 + 2F1

=

1 2 60 0 250 7 17

F3 F2

=

1 2 60 7 170 0 25

Como pudimos obsrvar se realizo un cambio de filas el cual no responde a unaoperacion elemental la cual pueda ser sustituida en la matriz L por lo cual seopta por el uso de la matriz de permutacion. 1 0 00 1 0

0 0 1

F2 F3 = 1 0 00 0 1

0 1 0

Esta matriz identidad permutada puede ser operada de tal modo que solucioneel cambio de filar y columnas. 1 0 00 0 1

0 1 0

1 2 60 0 25

0 7 17

= 1 2 60 7 17

0 0 25

Donde: 1 0 00 0 1

0 1 0

1 2 64 8 12 3 5

= LUPA = LU. 1 2 64 8 1

2 3 5

v (Reducidoporfilas) 1 2 60 7 17

0 0 25

= 1 0 02 1 0

4 0 1

1 2 60 7 17

0 0 25

Como se ve en la matriz L debajo de la matriz principal, el los numeros re-emplazados por las operaciones basicas se coloco un 0 que indica que no serealizo ninguna operacion.

5. Tratamiento de imagenes con uso de SVD

En matlab las imagenes pueden ser tratadas como una matriz finita de pun-tos dado a que cada seccion de la imagen representa a un pixel, la imagen estratada de tal manera que puede ser comprimida y asi reducida su calidad oaumentada segun se requiera, tambien cambiar la saturacion del color o hacerablanca y negra. Tratamiento de imagenes, implementacion Matlab

1. Lectura de la imagen



A=imread(nombre,extension,extension)

Es importante que la imagen que se requiera ser tratada sea una imagenen escala de grises, en el caso de ser una imagen a color, se requiere separarla matriz segun el color en tres matrices distintas.

2. Muestra de imagen

imagesc(A);

colormap(gray);

3. Conversion de matriz en formato numerico

A=double(A)

4. Tamano de la matriz

[maO,naO]=size(A)

En este punto del tratamiento de la imagen, si el script no corre o presentao un error, la imagen que es operada no se encuentra en escala de grises,por lo que se require cambiar de imagen.

5. Incorporacion de la imagen en el sistema SV D

[U,S,V]=svd(A)

La matriz S contiene los autovalores o valores singulares de la matrizcompuesta por los elementos de la imagen. Para tratar la imagen se empleael siguiente codigo

A1=U(:,1:4)*S(1:4,:4)*V(:,1:4)

En este caso el numero 4 implica el numero de autovalores seleccionados,este numero puede aumentar y consigo aumentar la calidad de la imagen.



6. Descomposicion de matrices SVD

Su sigla se debe a su nombre en ingles (Singular Value Descomposition) y elobjetivo general es descomponer a una matriz en tres matrices diferentes, dosde ellas son ortogonales y una es una matriz diagonal a trozos, lo que quieredecir que se formaran matrices diagonales por bloques.

Al descomponer la matriz tenemos:

A = USV T

El uso de estas matrices es para identificar el mal condicionamiento que puedantener ciertas matrices.Tambien se la usa para la compresion de imagenes.Donde:

U Matriz compuesta de conjunto de vectores ortogonales

S Matriz diagonal por bloques

V Matriz compuesta de autovectores de la matriz

Debemos recordar que en una matriz, las pequenas perturbaciones a la entradageneran pequenas perturbaciones a la salida.

La descomposicion SVD baja el condicionamiento de la matriz, as pues, de-bemos recordar que al aplicar la descomposicion SVD a una matriz, no estamosresolviendo el mismo problema, sino un problema similar o muy cercano al ori-ginal.

Ejemplo

A =

[1 1 00 0 1

]

1. ATA 1 1 01 1 00 0 1

2. Valores y vectores propios A I = x 1 1 01 1 0

0 0 1

= ( 2)(1 )Valores propios: [

2 1 0]



Vectores propios:

1 = 0;

1 1 00 0 00 0 1

= 11

0

2 = 2;

1 1 00 0 00 0 1

= 11

0

3 = 1;

0 1 01 0 00 0 0

= 00

1

3. Normalizar

12

0 12

12

0 12

0 1 0

4. Ordenar los valores propios

Para la matriz S se ordenan los valores propios de mayor a menor, con surespectiva raz cuadrada.

S =

2 10

5. Calculamos la matriz U

Para calcular U se usa la ecuacion Un =11Av1. Donde:

n es la raz cuadrada de los valores propios.

vn es el vector propio.

A es nuestra matriz.



La combinacion lineal de estos tres vectores columna forman la matriz U queen nuestro caso es:

U =

[1 00 1

]

Ahora con nuestra tres matrices obtenemos la descomposicion SVD que que-da de la siguiente forma:

A = USV T[

1 00 1

] [ 2 0 0

0 1 0

] 12 12 00 0 1 1

212

0

Es importante mencionar que en esta descomposicion abarcamos los temas detruncamiento de matrices y de pseudo inversa de una matriz.

Primero, el truncamiento es cuando tenemos una matriz de dimenciones nxm yse decide eliminar una fila o columna, segun convenga, pero esta eliminacion sepermite cuando la fila o la columna es nula, esto quiere decir, que sus elementosson ceros o son valores muy bajos. Este truncamiento nos ayuda a reducirel ruido en la matriz, lo que ocaciona el mal acondicionamiento de la misma.

Segundo, la pseudo inversa es un termino que indica que podemos encontrarla inversa de una matriz no cuadrada mediante la descomposicion SVD, y laecuacion quedara as: A1 = V S1UT

7. Interpolacion

La interpolacion es de utilidad al momento de hallar una funcion Pn(x) que pasepor los puntos dados y as describir el comportamiento de los puntos dados.Ademas busca la curva que minimiza el error.

En muchos casos experimentales o de analisis de datos, se hace uso de variasmediciones, pero se desconoce la funcion que rige tales mediciones puesto quetienen una tendencia indefinida. Vemos estos casos en la medicion deltiempo de enfriamiento o calentamiento de un material o la evolucion de preciosde cierto producto en el mercado.

Los metodos mas usados son:

Metodo de Lagrange

Metodo de Newton

Metodo de Spline



7.1. Interpolacion de Lagrange

La interpolacion actua tomando todos valores o puntos de funcion, los cualesse acomoden de tal manera que se ajusten a una nueva funcion o un nuevomodelo matematico. Es importante mecionar que la interpolacion no es unaaproximacion. La interpolacion busca una curva que mejor se ajustea los puntos de modo que se minimice el error

La interpolacion de lagrange se da a partir de la siguiente forma:

f(x) = Pn(x) + En(x) (1)

Como ya fue estudiado la interpolacion de Lagrange tiene una gran similitudcon el el Polinomio de Taylor.Para el calculo del polinomio interpolador:

Pn(x) =

nk=0

f(xk)Lnk(x) (2)

Como podemos ver en el polinomio existe un valor de n el cual hace referenciaal grado del polinomio, que se obtiene a partir del numero de datos reducino enuno, n = k 1, es decir el grado del polinomio sera un grado inferior al numerode datos.

Ln, k(x) =

nj=0j 6=k(x xj)nj=0j 6=k(xk xj)

(3)

Ejemplo

x f(x)0 1

0.6 0.82531.2 0.3626

Figura 1: Grafica de los punto en Matlab

Los puntos graficados son imperceptibles, en la siguiente imagen se senalanpara su identificacion



Pn(x) =

nk=0

f(xk)Lnk(x) P2(x) =

2k=0

f(xk)Lnk(x)

Pn(x) =

2k=0

f(x0)L2, 0(x) + f(x1)L2, 1(x) + f(x2)L2, 2(x)

P2(x) =

2k=0

f(xk)Lnk(x)

P2(x) = f(x0)L2, 0(x) + f(x1)L2, 1(x) + f(x2)L2, 2(x)P2(x) = 1L2, 0(x) + 0,82L2, 1(x) + 0,3626L2, 2(x)

Ln, k(x) =

nj=0j 6=k(x xj)nj=0j 6=k(xk xj)

L2, 0(x) =(x x1)(x x2)(x0 x1)(x0 x2

L2, 0(x) =(x 0,6)(x 1,2)(0 0,6)(0 1,2 =

x2 1,2x 0,6x+ 0,720,72

L2, 1(x) =(x x0)(x x2)(x1 x0)(x1 x2 =

x2 1,2x0,36

L2, 1(x) =(x 0)(x 1,2)

(0,6 0)(0,6 1,2)L2, 2(x) =

(x x0)(x x1)(x2 x0)(x2 x1)

L2, 2(x) =(x 0)(x 0,6)

1,6 0)(1,6 0,6) =x2 0,6x

1,6

P2(x) =x2 1,8x+ 0,72x 2,29

0,72

7.2. Interpolacion de Newton

A diferencia de la interpolacion de Lagrange, permite calcular polinomios deun grado elevado n 3 con mayor facilidad, tanto de manera analtica comonumerica. Esto es de gran utilidad puesto que dependiendo de la distri-bucion de los datos, el polinomio debera ser mas elevado.

Polinomio interpolador de Newton.- Supongamos que x0, x1, . . . , xN sonN+1 numeros distintos en [a, b]. Entonces, existe un unico polinomio PN (x) degrado menor o igual a N tal que:

f(x) = PN (x) + EN (x)

donde el polinomio interpolador PN (x) tiene la forma:

PN (x) = a0 + a1(x x0) + . . .+ aN (x x0)(x x1)(x x2) (x xN1)Siendo ak = f [x0, x1, . . . , xN ] y

EN (x) =(x x0)(x x1) . . . (x xN )fN+1(c)

(N + 1)!



con c [a, b]

Diferencias Divididas.- Se las define como:

f [xk] = f(xk)

f [xk1, xk] =f [xk] f [xk1]xk xk1

f [xk2, xk1xk] =f [xk1, xk] f [xk2, xk1]

xk xk2...

......

f [xkj , xkj+1, . . . , xk] =f [xkj+1, . . . , xk] f [xkj , . . . , xk1]

x k xkjEjemploSean los x y sus respectivos f(x) encuentre el Polinomio de Newton.

x f(x)1 32 03 154 48

La forma del polinomio de grado PN1 sera:

P3(x) = a0 + a1(x x0) + a2(x x0)(x x1) + a3(x x0)(x x1)(x x2)

Y los coeficientes del polinomio se hallan de la siguiente manera:

xk f [xk] f [xk1, xk] f [xk2, xk1, xk] f [xk3, xk2, xk1, xk]x0 = 1 3x1 = 2 0 3x2 = 3 15 15 6x3 = 4 48 33 9 1

Ahora se reemplaza los coeficientes y los valores de x en el polinomio:

P3(x) = 3 + 3(x 1) + 6(x 1)(x 2) + (x 1)(x 2)(x 3)


Documents

Métodos Numéricos