MA 590  Homework 5

MA 590 
Homework 5
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
1 (10 points) Consider the Landweber iteration, where
x
(k+1) = x
(k) + ωG
T
(y − Gx
(k)
) (1)
for k = 0, 1, . . . . To ensure convergence, the parameter ω must be selected so that
0 < ω <
2
λmax(GTG)
=
2
σ
2
1
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
f
(k)
i = 1 − (1 − ωσ2
i
)
k
. (2)
(a) Use the SVD of G to verify that (1) is satisfied when the Landweber iterate x
(k)
is given by
x
(k) =
min(
X
m,n)
i=1
f
(k)
i
u
T
i y
σi
vi
with the filter factors f
(k)
i 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/σ2
1
?)
2 (20 points) The Landweber iteration in (1), as described in Problem 1, converges under the
condition that 0 < ω < 2/σ2
1
, 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 G
TG.
(See Appendix A in the Aster et al. 2019 text for a useful linear algebra review.)
(a) Diagonalize the matrix A = G
TG, and use the diagonalization to show that, for the kth
power of A,
A
k = PΛkP
−1
.
Assume that the eigenvalues of A are sorted so that λ1 ≥ λ2 ≥ · · · ≥ λn ≥ 0.
(b) Take an arbitrary vector x in R
n
, and write it in terms of the eigenvectors of A as
x = α1v1 + · · · + αnvn.
Then show that for k ≥ 1,
A
kx = α1λ
k
1v1 + · · · + αnλ
k
nvn.
(c) Starting with a random vector x
(0), and assuming α1 6= 0, show that
lim
k→∞
||A
kx
(0)||2
||Ak−1x(0)||2
= λ1.
(d) The above leads to an iterative algorithm for estimating σ1 =
√
λ1. Start with a random
vector x
(0). In each iteration, let
x
(k+1) =
G
T
(Gx
(k)
)
||x(k)
||2
and let
ρk+1 =
q
||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