代做MAT 128B、Programming留学生代做、代写Matlab编程语言、代做Matlab设计

日期：2019-03-10 09:00

MAT 128B, Winter 2019

Programming Project 3

(due by Wednesday, March 13, 11:59 pm)

General Instructions

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 format.

You can use the Matlab command “format long e” to switch to that format from Matlab’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 presented

in class. The inputs of this function should be a function that computes matrix-vector

products x = A u 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

ρ := kA u λ uk2,

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 +1ne vT. (1)

Here, Q ∈ Rn×n

is a sparse matrix, i.e., only very few of its entries qij are nonzero, v ∈ Rn,and∈ Rn

(2)

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 ∈ R, computes the matrix-vector

product x = A u by exploiting the formula,

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 matrixvector

product x = A u where

(3)

and 0 < α ≤ 1 is a parameter. Your routine should exploit the formula

x = Aα u = α Q u +α vT u + (1  α) eT une,

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

i if i = j,

1 if |i j| = 1,

0 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

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

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

(α)

100 = 0.273386197776496 . . . .

Print out your computed values of x

(α)

333, x

(α)

7333, x

(α)

11333, and x

(α)

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.