12.4. LEAST SQUARES 317
That which is desired is obtained. So assume n > 1. By induction, there exists Q′2 an(m−1)× (n−1) unitary matrix such that Q′2A1 = R′, R′i j = 0 if i > j. Then(
1 0
0 Q′2
)Q1A =
(a bT
0 R′
)= R
Since the product of unitary matrices is unitary, there exists Q unitary such that Q∗A = Rand so A = QR. ■
12.4 Least SquaresA common problem in experimental work is to find a straight line which approximates aswell as possible a collection of points in the plane {(xi,yi)}p
i=1. The usual way of dealingwith these problems is by the method of least squares and it turns out that all these sorts ofapproximation problems can be reduced to Ax= b where the problem is to find the best xfor solving this equation even when there is no solution.
Lemma 12.4.1 Let V and W be finite dimensional inner product spaces and let A : V →Wbe linear. For each y ∈W there exists x ∈V such that
|Ax− y| ≤ |Ax1− y|
for all x1 ∈ V. Also, x ∈ V is a solution to this minimization problem if and only if x is asolution to the equation, A∗Ax = A∗y.
Proof: By Theorem 12.1.7 on Page 310 there exists a point, Ax0, in the finite dimen-sional subspace, A(V ) , of W such that for all x ∈V, |Ax− y|2 ≥ |Ax0− y|2 . Also, from thistheorem, this happens if and only if Ax0− y is perpendicular to every Ax ∈ A(V ) . There-fore, the solution is characterized by (Ax0− y,Ax) = 0 for all x ∈ V which is the same assaying (A∗Ax0−A∗y,x) = 0 for all x ∈V. In other words the solution is obtained by solvingA∗Ax0 = A∗y for x0. ■
Consider the problem of finding the least squares regression line in statistics. Supposeyou have given points in the plane, {(xi,yi)}n
i=1 and you would like to find constants mand b such that the line y = mx+ b goes through all these points. Of course this will beimpossible in general. Therefore, try to find m,b such that you do the best you can to solvethe system
y1...
yn
=
x1 1...
...xn 1
(
mb
)
which is of the form y = Ax. In other words try to make
∣∣∣∣∣∣∣∣A(
mb
)−
y1...
yn
∣∣∣∣∣∣∣∣2
as small
as possible. According to what was just shown, it is desired to solve the following for mand b.
A∗A
(mb
)= A∗
y1...
yn
.