代写 MTH 451: Homework 6

MTH 451: Homework 6
1 Problem Statements
1. (40 points) Let A ∈ R
m×m be symmetric and positive definite.
(a) Show that the eigenvalues of A are all positive real numbers.
(b) Show that there exists a matrix M ∈ R
m×m such that A = MTM. Recall that A is unitarily
diagonalizable (say A = U
T DU). Find M in terms of U and D.
(c) Given b ∈ R
m, show that there is a unique x ∈ R
m such that Ax = b.
(d) Let M ∈ R
m×m. Show that A = MTM is positive semidefinite.
(e) Let M ∈ R
m×m and µ > 0. Show that A = MTM + µI is positive definite with λi ≥ µ for all
eigenvalues λi of A.
2. (40 points) Steepest/Gradient Descent Algorithm. Let A ∈ R
m×m be symmetric and positive
definite. Let b ∈ R
m and set f(x) = 1
2
x
T Ax − x
T
b. Let x
(0) ∈ R
m and define a sequence as follows:
Given some x
(k) ∈ R
m, let l(t) = x
(k) − tr(k)
, where r
(k) = ∇f(x
(k)
). Set αk = argmint∈R f(l(t)) and
x
(k+1) = x
(k) − αkr
(k)
(i.e., x
(k+1) = l(αk) minimizes f over the line l(t)).
(a) Compute the gradient ∇f(x).
(b) Compute the Hessian ∇2f(x).
(c) Compute αk in terms of r
(k)
.
(d) Show that the αk satisfies the bounds
1
λ1
≤ αk ≤
1
λm
,
where λ1 is the largest eigenvalue of A and λm is the smallest.
(e) If A = µI with µ > 0, show that this algorithm will produce the exact solution x in one iteration
from any initial guess.
(f) Show that there exists a C > 0 (independent of k) such that kr
(k+1)k2 ≤ Ckr
(k)k2.
3. (20 points) The convergence of the Steepest Descent Algorithm is heavily dependent on the condition
number κ(A).
(a) Create a MATLAB function for the Steepest Descent Algorithm above that takes an input of A
and b and returns x
(k) and k such that kAx(k) − bk2 < 10−10. Use x
(0) = 0 for the initial guess.
The signature for this function should be [x,k] = steepestDescent(A,b).
(b) Create a MATLAB script to produce a scatter plot of at least N = 100 random symmetric positive
definite matrices A ∈ R
m×m with m ≥ 1000. Sample A as using the following lines:
D = (Lmax-Lmin)*rand(m,1) + Lmin;
A = (1/m)*sprandn(m,m,1/m);
A = sparse(1:m,1:m,D) + A’*A;
1