MA590- Homework 5 Solved

Your assignment should be well-organized, typed (or neatly written and scanned) and saved as a .pdf for submission on Canvas. You must show all of your work to receive full credit. For problems requiring the use of MATLAB code, remember to also submit your .m-files on Canvas as a part of your completed assignment. Your code should be appropriately commented to receive full credit.

Problems
) Consider the Landweber iteration, where

                                                                                       x(k+1) = x(k) + ωGT(y − Gx(k))                                                  (1)

for k = 0,1,.... To ensure convergence, the parameter ω must be selected so that

2
0 < ω < 

λmax(GTG)

where σ1 is the largest singular value of G. It can be shown that the kth iterate of the Landweber iteration is exactly the same as the SVD solution with filter factors

                                                                                            .                                                       (2)

Use the SVD of G to verify that (1) is satisfied when the Landweber iterate x(k) is given by
min(m,n) uTi k (k)

x

with the filter factors defined in (2).

Implement the Landweber iteration and apply it to the Phillips’ test problem (using the‘Regularization Tools’ function m) with n = 64 and noiseless data. Verify that x(10) from the Landweber iteration matches the SVD solution with filter factors given by (2) for different choices of ω. (Try, e.g., ω = 1... does this give a good solution? How about if you choose ω slightly smaller than 2?)
2 (20 points) The Landweber iteration in (1), as described in Problem 1, converges under the condition that 0 , where σ1 is the largest singular value of G (or, equivalently, σ1 = ||G||2). As a practical matter we typically cannot compute the full SVD of G. However, it is possible to rapidly estimate this quantity using an iterative method that we will derive in this exercise. Recall that σ1 is the square root of the largest eigenvalue of the matrix GTG. (See Appendix A in the Aster et al. 2019 text for a useful linear algebra review.)

Diagonalize the matrix A = GTG, and use the diagonalization to show that, for the kth power of A,
Ak = PΛkP−1.

Assume that the eigenvalues of A are sorted so that λ1 ≥ λ2 ≥ ··· ≥ λn ≥ 0.

Take an arbitrary vector x in Rn, and write it in terms of the eigenvectors of A as
x = α1v1 + ··· + αnvn.

Then show that for k ≥ 1,

A.

Starting with a random vector x(0), and assuming α1 6= 0, show that
.

√

The above leads to an iterative algorithm for estimating σ1 = λ1. Start with a random
 

vector x(0). In each iteration, let GT(Gx(k)) x(k+1) =

||x(k)||2

and let

 

q ρk+1 = ||x(k+1)||2.

The sequence ρk converges to σ1. Write your own implementation of this algorithm, and test it using the matrix G from Problem 1. Compare your results to those obtained using MATLAB’s normest function. Discuss your findings.

Note: For any of the above problems for which you use MATLAB to help you solve, you must submit your code/.m-files as part of your work. Your code must run in order to receive full credit. If you include any plots, make sure that each has a title, axis labels, and readable font size, and include the final version of your plots as well as the code used to generate them.

2