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 ₁ 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) ^uT_i k (k)

x

with the filter factors defined in (2).

• Implement the Landweber iteration and apply it to the Phillips test problem (using theRegularization Tools function m) with n = 64 and noiseless data. Verify that x⁽¹⁰⁾ 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 ₁ is the largest singular value of G (or, equivalently, ₁ = ||G||₂). 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 ₁ is the square root of the largest eigenvalue of the matrix G^TG. (See Appendix A in the Aster et al. 2019 text for a useful linear algebra review.)

• Diagonalize the matrix A = G^TG, and use the diagonalization to show that, for the kth power of A,

Ak = PkP1.

Assume that the eigenvalues of A are sorted so that _{1 2 n} 0.

• Take an arbitrary vector x in Rⁿ, and write it in terms of the eigenvectors of A as

x = ₁v₁ + + _nv_n.

Then show that for k 1,

A.

• Starting with a random vector x⁽⁰⁾, and assuming ₁ 6= 0, show that

.

• The above leads to an iterative algorithm for estimating ₁ = ₁. Start with a random

vector x⁽⁰⁾. 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 ₁. Write your own implementation of this algorithm, and test it using the matrix G from Problem 1. Compare your results to those obtained using MATLABs 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.