General Instructions
MAT 128B, Winter 2019 Programming Project 3 (due by Wednesday, March 13, 11:59 pm)
• You are required to submit each of your programming projects via file upload to Canvas. Note that the due dates set in Canvas are hard deadlines. Submissions outside of Canvas or after the deadline will not be accepted.
• Produce a single file for each Matlab function that you are asked to write and a single driver file for each of the problems that you are asked to test your programs on. The driver files should display all the quantities you are asked to print out. We will run these these driver files to check your programs. Submit a complete set of your Matlab files as a single zip file. When you prepare your zip file, please make sure that you zip just the Matlab files, rather than a folder containing these files.
For this current project, you should submit a zip file of a total of 9 Matlab files: 4 files for the functions POWER ITER, AMULT, AMULT WWW, and AMULT WWW ALPHA and 5 driver files for Problems 1–5.
• Write a short report that includes a discussion of the convergence speed of power iteration and explanations of runs for which power iteration did not produce an approximate dominant eigenvalue.
• When you are asked to print out numerical results, print numbers in 16-digit floating-point for- mat. You can use the Matlab command “format long e” to switch to that format from Mat- lab’s default. For example, the number 10π would be printed out as 3.141592653589793e+01 in 16-digit floating-point format.
• For each programming project, upload two files: a zip file of a complete set of Matlab files that lets us run your programs and a pdf file of your report.
The goal of this programming project is to implement and run power iteration for computing an approximate eigenvalue and a corresponding approximate eigenvector of any matrix A ∈ Rn×n.
• Write a Matlab function POWER ITER that implements the version of power iteration pre- sented in class. The inputs of this function should be a function that computes matrix-vector products x = Au with the matrix A, an initial vector x0, a convergence tolerance TOL, and a safeguard N0 against infinite loops. The outputs should be the approximate eigenvalue λ and approximate eigenvector u produced by power iteration, the corresponding eigenvalue residual norm
ρ := ∥A u − λ u∥2,
and the number j of iterations that the algorithm needed to produce the approximations λ and u.
• Write a Matlab function AMULT for computing matrix-vector products x = A u for a given matrix A. This function should have u and A as inputs and x as output.
• Matrices A ∈ Rn×n that arise in the context of search engines usually have the form
A = Q + 1 e vT . (1)
n
Here, Q ∈ Rn×n is a sparse matrix, i.e., only very few of its entries qij are nonzero, v ∈ Rn,
and
1
1 e:= . ∈R
.
1
is the vector of all 1’s. For large n, Matlab can still compute matrix-vector products with the
sparse matrix Q, but it is usually not possible to actually form and store the matrix A. Write a Matlab function AMULT WWW that for any u ∈ Rn, computes the matrix-vector
n
(2)
product x = A u by exploiting the formula
x = A u = Q u + vT u e,
n
which readily follows from (1). This function should have u, Q, and v as inputs and x as
output.
• Write a Matlab function AMULT WWW ALPHA that for any u ∈ Rn, computes the matrix-
vector product x = A u where
Aα :=α Q+nev +(1−α) nee (3)
1T1T
and 0 < α ≤ 1 is a parameter. Your routine should exploit the formula
x = Aα u = α Q u + α vT u + (1 − α) eT u e, n
which readily follows from (3). This function should have u, Q, v, and α as inputs and x as output.
Use your functions to solve the following 5 problems.
Problem 1: Run POWER ITER with AMULT as the function that computes x = A u, initial
vector x0 = e from (2), TOL = 10−12, and N0 = 10000 on the matrix A = aij ∈ R20×20,
where
√ i
aij = −1 0
ifi=j, if|i−j|=1, otherwise,
i,j=1,2,...,20.
Print out λ, u, ρ, and the iteration count j. Compare the approximate eigenvalue λ with the eigenvalues of A generated by means of the Matlab command “eig(A)”. Does λ approximate the dominant eigenvalue of A?
Problem 2: Run POWER ITER with AMULT as the function that computes x = A u, initial vector x0 = e from (2), TOL = 10−12, and N0 = 10000 on the matrix
1−s 1 −1 A=−2 2−s 2
−1 3 1−s
for the four cases s = 0, 1, 1.9, 1.98. For each case, print out λ, u, ρ, and the iteration count j. Compare the approximate eigenvalue λ with the eigenvalues of A generated by means of the Matlab command “eig(A)”. Does λ approximate the dominant eigenvalue of A?
Rerun POWER ITER with initial vector
1 x 0 = 0
1
for the four cases s = 0, 1, 1.9, 1.98. For each case, print out λ, u, ρ, and the iteration count j.
Does λ approximate the dominant eigenvalue of A?
Problem 3: Use your function AMULT WWW to compute the vector x = A e, where e is the vector (2) and A is the matrix (1) with Q and v provided in the Matlab file “large_example.mat”. The Matlab command “load(’large_example.mat’)” will load the matrix Q and the vector v into Matlab. To check the correctness of your routine, compare your computed value of x100 with the exact value
x100 = 0.145160232678231 . . . . Print out your computed values of
x333 , x7333 , x11333 , and x15333 .
Use your function AMULT WWW ALPHA to compute the vector x(α) = Aα e, where Aα is the matrix (3) and α = 0.85. To check the correctness of your routine, compare your computed value of x100 with the exact value
x(α) =0.273386197776496... . 100
Print out your computed values of
x(α), x(α) , x(α) , and x(α) .
333 7333 11333 15333
For all your runs of POWER ITER in the following Problems 4 and 5, use x0 = e from (2) as initial vector, convergence tolerance TOL = 10−9, and safeguard N0 = 1000.
Problem 4: Run POWER ITER with AMULT WWW as the function that computes x = A u on the matrix A given in (1) with Q and v provided in “large_example.mat”. Print out λ, ρ, and the iteration count j.
Run POWER ITER with AMULT WWW ALPHA as the function that computes x = Aα u on the matrix Aα given in (3) with Q and v provided in “large_example.mat” and α = 0.85. Print out λ, ρ, and the iteration count j.
Problem 5: Run POWER ITER with AMULT WWW as the function that computes x = A u on the matrix A given in (1) with Q and v provided in “larger_example.mat”. Print out λ, ρ, and the iteration count j.
Run POWER ITER with AMULT WWW ALPHA as the function that computes x = Aα u on the matrix Aα given in (3) with Q and v provided in “larger_example.mat” and α = 0.85. Print out λ, ρ, and the iteration count j.