Math 191 Wilkening
Spring 2023
Homework 5
due Sat, March 4, 2:00 PM
(Upload your solutions to Gradescope)
Problems 1–8 below are devoted to the simplest and most important application of least squares: Fitting a straight line to data. A line y = C +Dt has n = 2 parameters C and D. We are given m > 2 measurements bi at m different times ti. The equations Ax = b (usually unsolvable) and AT Ax = AT b (solvable) are
1 t1 b1
1 t2C b2 T m tiC bi Ax=::D=:, AAxˆ=tt2 D=bt.
iiii 1 tm bm
The column space R(A) is a 2-dimensional plane in Rm. The vector b is in this column space if and only if the m points (ti, bi) actually lie on a straight line. In that case only, Ax = b is solvable: the line is C + Dt. Always b is projected to the closest p in R(A).
The best line (the least squares fit) passes through the points (ti,pi). The error vector (residual) r = b − Ax has components bi − pi. And r is orthogonal to p in Rm.
There are two important ways to draw this least squares regression problem. One way shows the best line y = C + Dt and the errors ri (vertical deviations of the data from the line). The second way is in Rm = m-dimensional space. There we see the data vector b, its projection p onto R(A), and the error vector r = b − p. This is a right triangle with ∥p∥2 + ∥r∥2 = ∥b∥2.
The problems below>use four data points b = (0, 8, 8, 20) at t = (0, 1, 3, 4) to bring out the key
bz . W- 20.
-* >* $i* AA by
I residual)
17****$ 5>)
CS Help, Email: tutorcs@163.com
1. (3 points) (II.2.12, page 136, Strang.) With b = (0, 8, 8, 20) at t = (0, 1, 3, 4), set up and solve
the normal equations AT Ax = AT b. For the best straight line in Figure II.3a, find its four heights pi
and four residual errors ri. What is half the minimum squared error, 1 ∥r∥2 = 1 r12 + r2 + r32 + r42? 22
2. (2 points) (II.2.13, page 137, Strang.) With b = (0, 8, 8, 20) at t = (0, 1, 3, 4), write down the four equations Ax = b (unsolvable). Change the measurements to p = 1, 5, 13, 17 and find an exact solution to Ax = p, where x = (C, D).
3. (2 points) (II.2.14, page 137, Strang.) Check that r = b − p = (−1, 3, −5, 3) is orthogonal to both columns of A. What is the shortest distance ∥r∥ from b to the column space (range) of A?
4. (2 points) (II.2.15, page 137, Strang.) Write down f = 12 ∥b − Ax∥2 as a sum of four squares. The last one is 21(20 − C − 4D)2. Set ∂f/∂C = 0 and ∂f/∂D = 0 to obtain the normal equations ATAx = ATb.
5. (2 points) (II.2.22, page 137, Strang.) The averages of the ti and bi are t ̄ = 2 and ̄b = 9. Verify that C + Dt ̄ = ̄b. Explain!
(a) Verify that the best-fit line passes through the center point (t, b) = (2, 9).
(b) Explain why C + Dt ̄ = ̄b comes from the first equation in AT Ax = AT b.
6. (2 points) (II.2.18, page 137, Strang.) Find the closest line y = Dt, through the origin, to the same four points. An exact fit would solve bi = Dti for 1 ≤ i ≤ 4. Find the 4×1 matrix and solve AT Ax = AT b for x = (D). Redraw Figure II.3a showing the best line y = Dt.
7. (3 points) (II.2.20, page 137, Strang.) For the closest parabola y = C + Dt + Et2 to the same four points, write down the unsolvable equations Ax = b in three unknowns x = (C,D,E). Set up the three normal equations AT Ax = AT b (solution not required). In Figure II.3a you are now fitting a parabola to 4 points—what is happening in Figure II.3b?
Code Help
8. (4 points) (II.2.21, page 137, Strang.) For the closest cubic y = C + Dt + Et2 + F t3 to the same four points, write down the four equations Ax = b. Solve them by Gaussian elimination. In Figure II.3a this cubic now goes exactly through the points. What are p and r?
9. Let a, u, v and w denote vectors in Rm with components ai, ui, vi and wi, and let e1 ∈ Rm have 1 i=1
components (e1)i = 0 i ̸= 1 . Recall from lecture 16 that there are two Householder reflections H=I−2uuT thatmapatoamultipleofe1,namely
u= w , w=a+s∥a∥e1, (s=±1). ∥w∥
(The two Householder reflections are obtained by setting s = 1 or s = −1.) Show that
Then show that 2uuT = τvvT with
wT a = ∥a∥2 + s∥a∥a1, wT w = 2wT a,
Ha = −s∥a∥e1.
v= w, τ=1+sa1. w1 ∥a∥
(3 points)
1 a1≥0 Usuallywechooses= −1 a1 <0 sothatsa1 =|a1|.
−16 2 10. LetA= 2 −1 andb=−1.
(a) (3points)Findτ1 ∈R,τ2 ∈R,v1 ∈R3,v2 ∈R3 andR∈R2×2 suchthattheHouseholder
transformations H1 = I − τ1v1v1T and H2 = I − τ2v2v2T reduce A to upper triangular form, T R
so the least-squares solution is x = R y
Q A=H2H1A= 0 =R0.
Here R is 2×2 while R0 is 3×2. Choose the signs s1 and s2 in H1 and H2 in the usual way (as stated in the last line of problem 9 and also in lecture 16, where we used more complicated notation to handle the construction of H1, H2, . . . , Hn consecutively.)
(b) (2 points) Find the least-squares solution x of Ax = b and compute the minimum value of ∥r∥ = ∥b − Ax∥. Note that
∥r∥ = ∥QT r∥ = ∥QT (b − Ax)∥ = ∥y − R0x∥, y = QT b = H2H1b,
and the minimum value of ∥r∥ is |y3|.
程序代写 CS代考 加微信: cstutorcs