11.5. LEAST SQUARES 283
Lemma 11.5.1 Let V andW 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 11.2.4 on Page 276 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, fromthis theorem, this happens if and only if Ax0 − y is perpendicular to every Ax ∈ A (V ) .Therefore, the solution is characterized by (Ax0 − y,Ax) = 0 for all x ∈ V which is thesame as saying (A∗Ax0 −A∗y, x) = 0 for all x ∈ V. In other words the solution is obtainedby solving A∗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)}ni=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
(m
b
)
which is of the form y = Ax. In other words try to make
∣∣∣∣∣∣∣∣A(m
b
)−
y1...
yn
∣∣∣∣∣∣∣∣2
as small
as possible. According to what was just shown, it is desired to solve the following for m andb.
A∗A
(m
b
)= A∗
y1...
yn
.
Since A∗ = AT in this case,( ∑ni=1 x
2i
∑ni=1 xi∑n
i=1 xi n
)(m
b
)=
( ∑ni=1 xiyi∑ni=1 yi
)Solving this system of equations for m and b,
m =− (∑n
i=1 xi) (∑n
i=1 yi) + (∑n
i=1 xiyi)n
(∑n
i=1 x2i )n− (
∑ni=1 xi)
2
and
b =− (∑n
i=1 xi)∑n
i=1 xiyi + (∑n
i=1 yi)∑n
i=1 x2i
(∑n
i=1 x2i )n− (
∑ni=1 xi)
2 .
One could clearly do a least squares fit for curves of the form y = ax2 + bx + c in thesame way. In this case you solve as well as possible for a, b, and c the system
x21 x1 1...
......
x2n xn 1
a
b
c
=
y1...
yn
using the same techniques.