GDI_AMAT_18_Ejercicios_Practica2

233 days ago by etlopez18

Resolución Numérica de Sistemas de Ecuaciones

Ejercicios

En los ejercicios siguientes, $DNI$ es la suma de los números de DNI de los miembros del grupo, $a$ la última cifra de dicho número,  y $dni=DNI/2.9^{ln(DNI)}$.

 

1. Resolver mediante el método de Gauss (con pivote) el sistema. Comprueba el error cometido (sustituye la solución en el sistema y calcula los errores cometidos en cada ecuación).

$$\left.\begin{array}{r} 2x-(3+dni)y+100z=1  \\ x-10y+0.00002 z=0  \\ 3x-100y+0.00003z=0 \end{array}\right\}$$


 

 2. Aplicar cinco pasos del método de Gauss-Seidel al sistema:

$$\left.\begin{array}{r} (12+dni)x-y+z=1  \\ 5x+4y-2z=2  \\ -2x+y-6 z=3 \end{array}\right\}$$

  Discutir si podemos asegurar la convergencia.


3. Aplicar cuatro pasos del método de Newton para, partiendo de $(0,0,0)$, aproximar un cero del sistema:

$$\left.\begin{array}{r} (12+dni)x-y^3-exp(z)=1  \\ -sin(x)+(10+a) y-2z=2\\ -2x-\cos(y)+16\sin(z)=3  \end{array}\right\}$$

Si quieres representar las ecuaciones y los puntos, deberás usar las versiones 3d de parametric_plot y points.


 


 
       

4. Difuminando y perfilando una imagen

Vamos a ver un ejemplo de cómo se puede aplicar el método iterativo de Gauss-Seidel. Concretamente, veremos cómo funciona (de modo básico) un modelo de difuminado y perfilado. Estos modelos se aplican por ejemplo a imágenes de satélite para eliminar los efectos de difusión de la atmósfera, al análisis de imágenes por ordenador, para retocar fotografías, etc.

Cada imagen viene cargada en una matriz (por simplicidad asumiremos que está en blanco y negro). Vamos a necesitar algunas funciones que nos pasen los datos de la matriz a un vector y viceversa. Para ello, basta ejecutar la siguiente línea.

def matrix_to_vector(A): n,m=A.dimensions(); v=vector(RDF,n*m) for i in range(0,n): for j in range(0,m): v[m*i+j]=A[i,j]; return v; def vector_to_matrix(v): n=sqrt(v.degree()); A=matrix(RDF,n); for i in range(0,n): for j in range(0,n): A[i,j]=v[n*i+j]; return A; 
       

Para pasar la matriz a un vector, numeramos las celdas comenzando por la primera fila:

 

$$\left(\begin{array}{rrr}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}\right)\to(1,2,3,4,5,6,7,8,9)$$

 

Definimos la matriz en la que tenemos la imagen. Cuando creamos la matriz estará a cero (color negro). Vamos a poner algunas posiciones a uno (blanco).

n=5; A=matrix(RDF,n) A[1,1:4]=Matrix([1,1,1]) A[3,1:4]=Matrix([1,1,1]) A[2,1]=1 show(plot(A),figsize=4) 
       

Creamos la matriz de difuminado (está libremente basado en el difuminado gaussiano). Para ello cada posición pasa a tomar "un poco del color de los vecinos". Estamos considerando cuatro vecinos (arriba, abajo, derecha e izquierda). Si A(i,j) es el color del punto (i,j), después de la transformación será: $$A(i,j)\to (1-4d) A(i,j)+d\,A(i-1,j)+d\,A(i+1,j)+d\,A(i,j-1)+d\,A(i,j+1)$$

Esto puede hacerse escribiendo la matriz $A$ en forma de vector y multiplicando el vector por cierta matriz (dada por la expresión anterior). Guardaremos en $N$ la matriz por la que hay que multiplicar (matriz de difuminado).

N=matrix(RDF,n*n); d=1/10; for i in range(0,n-1): for j in range(0,n): N[i+j*n,i+1+j*n]=d; # vecino a la derecha (i+1,j) N[i+1+j*n,i+j*n]=d; # vecino a la izquierda (i-1,j) N[i*n+j,(i+1)*n+j]=d; # vecino superior (i,j+1) N[(i+1)*n+j,i*n+j]=d; # vecino inferior (i,j-1) for i in range(0,n*n): N[i,i]=1-4*d; # posición original (i,j) 
       

Para difuminar la imagen, escribimos la matriz como vector y multiplicamos ese vector por la matriz de difuminado.

Av=matrix_to_vector(A);Av # Necesitamos considerar la imagen como un vector b=N*Av # Multiplicamos la imagen Av por la matriz N show(plot(vector_to_matrix(b)), figsize=4) # Para dibujar necesitamos volver a pasar a la forma de matriz 
       

Y podemos hacer el proceso inverso resolviendo el sistema $Nx=b$, para lo cual Gauss-Seidel es un método apropiado (a cada paso se perfila un poco más la imagen). Véamoslo en el ejemplo.

Construimos las matrices de Gauss-Seidel

U=matrix(RDF,n*n); for i in range(0,n*n): for j in range(i+1,n*n): U[i,j]=N[i,j]; DL=N-U; 
       

Y aplicamos el método

x0=vector(RDF,n*n) m=3 # Número de iteraciones del método M0=Matrix(RDF,m+1,n*n) # Aquí guardamos los pasos para pintarlo después M0[0,:]=x0; # guardamos la condición inicial for i in range(1,m+1): x0=(DL).solve_right(-U*x0+b) M0[i,:]=x0; # guardamos el vector en la fila i 
       

A continuación mostramos los pasos de Gauss-Seidel. Se puede observar que con 3 iteraciones prácticamente estamos en la matriz original. Esto no depende del número de puntos de la imagen, por lo que para matrices muy grandes este método es mucho más rápido que la eliminación gaussiana o que los métodos LU.

c0=plot(vector_to_matrix(vector(M0.row(0))), figsize=2.5) c1=plot(vector_to_matrix(vector(M0.row(1))), figsize=2.5) c2=plot(vector_to_matrix(vector(M0.row(2))), figsize=2.5) c3=plot(vector_to_matrix(vector(M0.row(3))), figsize=2.5) html.table([["Iteración 0", "Iteración 1","Iteración 2", "Iteración 3"],[c0,c1,c2,c3]], header=True) 
       
/home/sage1516/sage-7.0/local/lib/python2.7/site-packages/sage/misc/html\
.py:82: DeprecationWarning: use table() instead of html.table()
See http://trac.sagemath.org/18292 for details.
  output = method(*args, **kwds)
/home/sage1516/sage-7.0/local/lib/python2.7/site-packages/sage/misc/deco\
rators.py:471: DeprecationWarning: the filename and linkmode arguments
are deprecated, use save() to save
See http://trac.sagemath.org/17234 for details.
  return func(*args, **kwds)
Iteración 0 Iteración 1 Iteración 2 Iteración 3
/home/sage1516/sage-7.0/local/lib/python2.7/site-packages/sage/misc/html.py:82: DeprecationWarning: use table() instead of html.table()
See http://trac.sagemath.org/18292 for details.
  output = method(*args, **kwds)
/home/sage1516/sage-7.0/local/lib/python2.7/site-packages/sage/misc/decorators.py:471: DeprecationWarning: the filename and linkmode arguments are deprecated, use save() to save
See http://trac.sagemath.org/17234 for details.
  return func(*args, **kwds)
Iteración 0 Iteración 1 Iteración 2 Iteración 3

Problema. Se tiene la siguiente matriz $M$, resultado de aplicar la matriz $N$ sobre cierta imagen.


M=matrix(RDF,[[0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0],[0.0, 0.0, 0.1, 0.7, 0.1, 0.0, 0.0],[0.0, 0.1, 0.2, 0.8, 0.2, 0.1, 0.0],[0.1, 0.7, 0.8, 1.0, 0.8, 0.7, 0.1],[0.0, 0.1, 0.2, 0.8, 0.2, 0.1, 0.0],[0.0, 0.0, 0.1, 0.7, 0.1, 0.0, 0.0],[0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0]]) n=7 N=matrix(RDF,n*n); d=1/10; for i in range(0,n-1): for j in range(0,n): N[i+j*n,i+1+j*n]=d; # vecino a la derecha (i+1,j) N[i+1+j*n,i+j*n]=d; # vecino a la izquierda (i-1,j) N[i*n+j,(i+1)*n+j]=d; # vecino superior (i,j+1) N[(i+1)*n+j,i*n+j]=d; # vecino inferior (i,j-1) for i in range(0,n*n): N[i,i]=1-4*d; # posición original (i,j) 
       
show(plot(M), figsize=5,axes=False) 
       

Comparar las imágenes resultantes tras aplicar 3 pasos del método de Jacobi y tres pasos del método de Gauss-Seidel.