Solved–HOMEWORK 03– Solution

Description

Problem 00 First of all, carefully reread Chapter 4 and read Chapter 5 in Eldén.

Problem 01 Let A 2 Rm£m be a symmetric matrix. As you have already learned in MAT 22A or MAT 67, an eigenvector of A is a nonzero vector x 2 Cm such that Ax ˘ ‚x for some ‚ 2 C, the corresponding eigenvalue. Here C denotes the complex numbers; i.e. all numbers p

of the form z ˘ a ¯ b i where a and b are real numbers and i ˘ ¡1 is the square root of ¡1. Also, you will also need to know that

z ˘ a ¡b i is the complex conjugate of z and if z1 and z2 are any two complex numbers we have z1 z2 ˘ z1 z2. In the following problem, you may assume that all of the eigenvalues of A are distinct.

(a) Prove that all of the eigenvalues of A are real.

[Hint: If ‚ is a (complex) eigenvalue of A with eigenvector x, then it’s complex conjugate ‚ is also an eigenvalue of A with eigenvector x.]

(b) Prove that if x1 and x2 are eigenvectors corresponding to distinct eigenvalues, then x1 and x2 are orthogonal.

Problem 02 Let
21 13

A˘4† 05,

0 †

where † is a small positive number (e.g., 10¡8) so that †2 can be ignored numerically.

(a) Compute the reduced QR factorization A ˘ QbRb using the classical Gram-Schmidt algorithm by hand.

(b) Compute the reduced QR factorization A ˘ QbRb using the modified Gram-Schmidt algorithm by hand.

(c) Compute the full QR factorization A ˘ QR using the Householder triangularization by hand.

(d) Check the quality of these results by computing the Frobenius norm of kQbTQb¡ IkF for the results obtained by the CGS and MGS algorithms and kQTQ ¡IkF for the result obtained by the Householder triangularization.

Problem 03 Let E 2 Rm£m that extracts the “even part” of an m-vector: Ex ˘ (x ¯ Fx)/2, where F 2 Rm£m flips x ˘ [x1, . . . , xm ]T to

x ˘ [xm , . . . , x1]T.

(a) Is E an orthogonal projector, an oblique projector, or not a projector at all?

(b) What are its entries?

Problem 04 Take m ˘ 50, n ˘ 12. Using MATLAB’s linspace, define t to be the m-vector corresponding to linearly spaced grid points from 0 to 1. Using MATLAB’s vander and fliplr, define A to be the m £n matrix associated with least squares fitting on this grid by a polynomial of order n ¡ 1. Take b to be the function cos(4t) evaluated on the grid. Now, calculate and print (to 16 digit precision) the least squares coefficient vector x by the following three methods.

(a) Solving the normal equation explicitly computing (AT A)¡1.

(b) Using the MATLAB implementation CGS.m of the classical Gram-Schmidt algorithm CGS, which can be downloaded from CANVAS.

(c) Using the MATLAB implementation MGS.m of the modified Gram-Schmidt algorithm MGS, which can be downloaded from CANVAS.

(d) QR factorization using MATLAB’s qr, which is based on the Householder triangularization.

(e) x ˘ A\b in MATLAB, which is also based on QR factorization.

(f) The calculations above will produce five lists of twelve coefficients. In each list, use the “\textcolor{color}{words}” func-tion in LaTeX

© 2018 Professor E. G. Puckett – 1 – Revision 3.01 Wed 11th May, 2016 at 19:43
MAT 167–001 HOMEWORK 03 SPRING QUARTER 2018

\textcolor{red}{This sentence will be in red.} ! This sentence will be in red.

to highlight the digits that appear to be incorrect; i.e., affected by rounding error.

• Comment on the differences you observe.

• Do the normal equations exhibit instability?

Although, explanations for what you observe are welcome, you are not required to explain your observations.

© 2018 Professor E. G. Puckett – 2 – Revision 3.01 Wed 11th May, 2016 at 19:43