Numerical Computing :: Project Eight

Description

The purpose of this homework is to see the relationship between the condition number and the numerical error when solving linear least-squares problems.

First, implement the following methods for least-squares, which you’ll use in the next exercise.

1. Method of Normal Equations (uses the Cholesky factorization)

2. Method based on the Thin QR factorization

Next, load the given matrix (download from Canvas) into memory. Call the matrix A,

A = a1 · · · an ,

(1)

where a_i ∈ R^m is the ith column of A. Define the matrices A₁, . . . , A_n as:

Ak = a1 · · · ak , k = 1, . . . , n.

(2)

That is, A_k contains the first k columns of the matrix A (that you loaded into memory).

Now, generate the error data that you’ll analyze. For k from k_min = 40 to k_max = 65:

1. Report the size, rank, and condition number of A_k.

2. Generate 100 random vectors b_i ∈ R^m. For each b_i,

1. 1. Use the built-in equation solver (numpy.linalg.lstsq) to com-pute the least-squares minimizers given A_k and b_i. Call this vector x_true, because we’re just gonna trust the software on this one.

1. 2. Use your Normal Equation solver to compute the least-squares minimizer, x_NE. Compute the relative error with x_true.

1. 3. Use your QR solver to compute the least-squares minimizer, x_QR. Compute the relative error with x_true.

3. For each of QR and Normal Equations, compute the average error over all the b_i.

Make two plots on a semilogy scale:

• the average error versus k (how many columns in the matrix) for both QR and the Normal Equations,

• the condition number of A_k versus k.

Now tell me what’s going on. More specifically:

1. What is the relationship between the error using QR versus the Normal Equations?

2. What is the relationship between the errors and the condition number of A_k?

3. Suppose your matrix A is ill-conditioned. Which method is more fa-vorable?

2