13.3. LEAST SQUARE APPROXIMATION 313

Solving this system of equations for m and b,

m =−(∑n

i=1 xi)(∑ni=1 yi)+(∑n

i=1 xiyi)n(∑

ni=1 x2

i

)n− (∑n

i=1 xi)2

and

b =−(∑n

i=1 xi)∑ni=1 xiyi +(∑n

i=1 yi)∑ni=1 x2

i(∑

ni=1 x2

i

)n− (∑n

i=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 want to solve as well as possible for a,b, and c the system

x21 x1 1...

......

x2n xn 1

 a

bc

=

y1...

yn

and one would use the same technique as above. Many other similar problems are impor-tant, including many in higher dimensions and they are all solved the same way.

13.3.2 The Fredholm AlternativeThe next major result is called the Fredholm alternative. It comes from Theorem 13.3.3and Lemma 13.3.5.

Theorem 13.3.8 Let A be an m× n matrix. Then there exists x ∈ Fn such that Ax = y ifand only if whenever A∗z = 0 it follows that z ·y = 0.

Proof: First suppose that for some x ∈ Fn, Ax = y. Then letting A∗z = 0 and usingLemma 13.3.5

y · z = Ax · z = x ·A∗z = x ·0 = 0.

This proves half the theorem.To do the other half, suppose that whenever, A∗z = 0 it follows that z ·y = 0. It is

necessary to show there exists x ∈ Fn such that y = Ax. From Theorem 13.3.3 there existsx minimizing |y−Ax|2 which therefore satisfies

(y−Ax) ·Aw = 0 (13.11)

for all w ∈ Fn. Therefore, for all w ∈ Fn,

A∗ (y−Ax) ·w = 0

which shows that A∗ (y−Ax) = 0. (Why?) Therefore, by assumption,

(y−Ax) ·y = 0.

Now by 13.11 with w = x,

(y−Ax) · (y−Ax) = (y−Ax) ·y−(y−Ax) ·Ax = 0

showing that y = Ax. ■The following corollary is also called the Fredholm alternative.