讲解MAT 128B、Programming留学生讲解、辅导Matlab编程语言、讲解Matlab设计 讲解留学生Processing|解析
- 首页 >> 其他 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.
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.