Description

1 (10 points) 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 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)
(a) 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).
(b) Implement the Landweber iteration and apply it to the Phillips’ test problem (using the‘Regularization Tools’ function phillips.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 ?)
(a) 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.
(b) 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 .
(c) Starting with a random vector x(0), and assuming α1 6= 0, show that
.
√
(d) 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