Description
- Implement LU factorization.
Your function should have the signature mylu(A,pivot), and return a Python list [L,U,P,Q] where
A Matrix to factorize
pivot 0 – no pivoting, 1 – partial pivoting, 2 – complete pivoting.
L,U L and U as defined by the LU algorithm.
P Permutation matrix as defined for partial and complete pivoting. Q Permutation matrix as defined for complete pivoting.
The algorithm should satisfy
| pivot = 0 | A =LU |
| pivot = 1 | PA =LU |
| pivot = 2 | PAQ=LU |
- Implement Jacobi’s iterations to find the eigenvalues and eigenvectors of a symmetric matrix.
Your function should have the signature myeig(A), and return a Python list [D,V] where
A Matrix to diagonalize.
D Diagonal matrix with SORTED eigenvalues (largest to smallest) on the diagonal. V Matrix of eigenvectors.
The matrices V and D should satisfy V DV T = A. You may assume that the entries of A are real (i.e., ai,j ∈ R).
- Download the file npy from the moodle site and use the load function of numpy to load the file into an ndarray variable named ’dists’. The file contains the pairwise distances between 312 cities, specifically, dists is a matrix of size 312 × 312, with
dists(i,j) = kxi − xjk
where xi,xj ∈ R2 are the coordinates in the plane of cities i and j respectively, and k·k is the Euclidean norm.
- Let X ∈ R312×2 be a matrix whose ith row is xi. Find an expression for XXT in terms of the matrix dists.
- The coordinates x1,…,x312 cannot be recovered uniquely from XXT . Explain why.
- The coordinates of the first 5 cities are
Find x1,…,x312, and write them as a 312 × 2 ndarray into a .npy file named ’cities coor.npy’, using the save function of numpy. In addition, write the coordinates of the first 10 cities to the PDF file.
- Implement Gradient Descent iterations ~xk+1 = ~xk − a ∇f(~xk) for a general function f(x) : Rn → R. Your function should have the signature myGD(f,gradf,x0,a,tol,maxiter), and return a Python list [y, iter] where
gradf Function handle to ∇f(x) x0 Initial vector to start the iterations from
- Step size
tol Tolerance
maxiter Maximal number of iterations
y Final approximation of the vector that minimizes f iter Number of iterations until convergence
where the tolerance tol is an upper bound on kxi+1−xik to be used as the stopping criteria. Use myGD to minimize the Rosenbrock function f(x,y) = (1 − x)2 + 100(y − x2)2 with tol = 10−6, the parameter a = 0.001 and the starting point x0 = (2,2). How many iterations did you need in order to achieve the approximation?
- In this question we would like to compress an image using the SVD decomposition.
- Download the file png from the moodle site.
- Read the image into an ndarray variable in Python named ’bwmandril’ using the imread function of matplotlib
- Display the image using the imshow function of matplotlib library, with the flag cmap=’gray’ (you should see a gray-scale image of a mandrill monkey displayed on the screen now).
Answer the following questions:
- Plot the singular values of the decomposition and decide according to their graph howmany singular values are needed.
- Create a function which gives a rank-k approximation of the image. Your function should have the signature Krank(A,k), and return a Python list [Uk, Sk, Vk] where
A A matrix of size m × n k The rank of the approximation
Uk m × k matrix
Sk k × k matrix of the singular values
Vk n × k matrix
The rank-k approximation of A should be Ak = Uk · Sk · VkT
- Use the Krank function to reconstruct an approximation of the image using just k singular values (the number k is for you to decide upon). Add your approximated image to the PDF file (use the matplotlib command imsave, NO Print Screens).
