MA 590  Homework 5

Original price was: \$35.00.Current price is: \$30.00.

Category:
Rate this product

MA 590
Homework 5
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 =

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