代写MTH 451、代做Python，c/c++编程

日期：2023-08-03 07:56

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