Problem 3: Least Squares Approximation (6 points) 3.1 (3/6) Solve linear

Question
Problem 3: Least Squares Approximation (6 points)

3.1 (3/6) Solve linear systems based on QR factorization We can use QR factorization to solve

a linear system Ar = b, where A has independent columns, and be col (A) (i.e., the system has

unique solution). Suppose that the QR factorization of A = QR, where Q is orthonormal (i.e.,

Q¹Q = I), and R is square and upper triangular. If we substitute A = QR into the linear system,

we have

QRx=b⇒ Q¹Q R = Q¹b⇒ Ra=Q¹b.

=I

This implies that to solve the linear system, we can take three steps:

Factorize A into Q and R

• Compute bo = Q¹b

• Solve Ra= bo by back-substitution (remember R is upper-triangular)

Algorithm 4 Back substitution (æ = backSubstitute (R, bq))

Input: R, bq

1: x = 0

2: for i in range(n-1,-1,-1) do

3: x[i] = [bqli] - [j+1R[i, j]æ[j]] /R[i,i]

4: end for

5: return a

(22)

▷ Solve Rz = bq

▷ is initialized as an all-zero vector

▷n is the number of rows of R

The back substitution algorithm is summarized in Algorithm 4 (We have implemented a similar

thing for HW1). The entire process of solving the linear system is summarized in Algorithm 5.

Please implement mySolver (A,b), and test your solver on the linear system provided in the Colab

file.

Input: A, b

1: Q, R = QR(A)

2: bq = Q¹b

3: a = backSubstitute (R, bq)

4: return a

Algorithm 5 Linear system solver based on QR factorization (x = mySolver (A, b), depending on

two functions: QR, backSubstitute)

▷ Solve Arb

Suppose that your solver returns a solution . To check if you have solved the given linear

system correctly, please compare with the true z we provide in the Colab file and report the

10

Question image 1