闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

DDA 3005 — Numerical Methods

Final Exam – Sample

Fall Semester 2022-23

Exercise 1 (Power Method): (20 points)

We consider the problem of computing eigenvalues and eigenvectors of the following matrix:

A = 1

「0

Let λ 1 > λ2 > λ3 denote the three eigenvalues of A. Furthermore, let v 1 , v2 , v3 be the three eigenvectors corresponding to λ 1 , λ2 , λ3 with ∥v1 ∥2 = ∥v2 ∥2 = ∥v3 ∥2 = 1, respectively.

a) Compute all eigen-pairs (vi, λi) of A for i = 1, 2, 3.

b) Set x0 = (1, −1, 1)⊤ as initial point and perform two steps of the normalized power method without shifting. Will this sequence converge to v 1 ? Explain your answer!

c) Set x0 = (1, −1, 1)⊤ . State a necessary and sufficient condition on the choice of the shift σ ∈ R such that the inverse iteration with shift σ converges to v3 .

Exercise 2 (Eigenvalues of a Rank-1 Matrix): ( 15 points)

Let A ∈ Rn×n be a real, symmetric, and positive semidefinite matrix with rank one.

a) Show that A = uu⊤ for some nonzero real vector u ∈ Rn .

b) Show that ∥u∥2 is an eigenvalue of A.

c) What are the other eigenvalues of A?

d) If the power iteration is applied to A with initial point x0 ∈ Rn satisfying u⊤x0 0, how many iterations are required for it to converge exactly to the eigenvector corresponding to the dominant eigenvalue? Explain your answer!

Exercise 3 (Newton’s Method):

Consider the following nonlinear equation in R:

f(x) := x2 − 1.

(20 points)

Our goal is to find the root x∗ = 1 using Newton’s method.

a) Formulate Newton’s iteration as a fixed point iteration xk+1 = g(xk) and give an explicit formula for g .

b) Choose the initial point x0 = 2 and perform one step of Newton’s method.

c) Prove g(t) ≥ 1 for all t > 0 and |g\ (t)| < for all t ≥ 1. Use these two results to show that Newton’s method starting from any x0 > 0 will converge to x∗ = 1.

d) How fast does Newton’s method converge to x∗ = 1 if the initial point x0 satisfies x0 > 0? I.e., what type/rate of convergence do you expect?

Exercise 4 (QR Algorithm): (10 points)

Let the 2 × 2 matrix

A = [3(0) 1(2)]

be given. Perform one step of the QR algorithm (without shift).

Exercise 5 (Singular Value Decomposition): (20 points)

In this problem, we consider the SVD decomposition of a matrix A ∈ Rn×n given its low-rank structure A = BC⊤, where B , C ∈ Rn×k are two known full rank matrices with n > k .

a) Design an algorithm to compute the SVD of A based on the given matrices B and C , i.e., without forming the matrix A explicitly.

– Your algorithm can use QR factorizations and SVDs (of matrices different from A).

– Suppose we only consider the computational costs of the involved matrix decompositions (QR factorizations, SVDs, etc.). Is your algorithm more efficient compared to applying the SVD directly to A? Explain your answer!