Least Squares Fit

Straight Line Least Squares Fit Michael O. Duffy 28 Oct 2009

Assume that you have n points: (x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )

(1)

The points are distributed randomly in such a way that you can’t draw a single straight line that passes through all the points. You’d like to know the ”best” equation for a line to approximate the data you have: y = mx + b

(2)

where m is the slope and b is the y-intercept. Substituting the n points into the equation for the line gives n equations with two unknowns: the slope and y-intercept: y1 = mx1 + b y2 = mx2 + b .. .

(3)

yn = mxn + b We can rewrite this in terms of a matrix equation: 

x1  x2   ..  . xn

  1  y1       y2 1 m =  ..   b .    1 yn

    

(4)

   

Remember that multiplying two matricies Amn and Bnp together means adding the products of each element in a row of Amn in succession, multiplying it by the value in the corresponding column in Bnp :

1

2

Cmp =

n X

Ami Bip

(5)

i=1

We’ll assume that the coefficients of the ”best” line are those that minimize the sum of squares of the errors between the data point yi and mxi + b, the value predicted by the line at the point xi . For now, we’ll take it on faith that we can calculate those ”best” coefficients by pre-multiplying both sides by the transpose of the matrix:   x1 1  y1         y2 . . . x n  x2 1 m x1 x2 . . . xn =   .. .. ... 1  . 1 1 ... 1   b .    xn 1 yn 

 x1 x2 1 1

    

(6)

   

I can multiply these matricies and reduce them to a 2x2 matrix equation, with the product of a 2x2 matrix and a 2x1 vector of unknowns equal to a 2x1 right-hand side vector: c = y˜ A˜

(7)

 Pn Pn 2 (x ) (x ) i i i=1 i=1 A = Pn n i=1 (xi )

(8)

  m c˜ = b

(9)

where

and

and

y˜ =

Pn  (xi yi ) Pi=1 n i=1 (yi )

(10)

Now I can calculate the solution by multiplying both sides of the matrix equation by the inverse of A: A−1 A˜ c = A−1 y˜

(11)

The product of A−1 A is the identity matrix: A−1 A = I

(12)

3 where 

1 0 I= 0 1

 (13)

Since the product I c˜ = c˜, we have an expression for the vector of unknown coefficients: c˜ = A−1 y˜

(14)

I can write out the expression for A−1 using determinants:

det(A) = n

n n X X (xi )2 − ( (xi ))2 i=1

(15)

i=1

We can write out the inverse of A explicitly:  A−1 =

−

 Pn (x ) − i i=1 Pn n 2 i=1 (xi ) i=1 (xi ) det(A)

Pn

(16)

We can check this result by multiplying the matrix by its inverse and seeing if we get the identity matrix back:  A−1 A =

−

  Pn Pn Pn (xi )2 − i=1 (xi ) Pn i=1 (xi2) Pi=1 n (xi ) n (xi ) i=1 (xi ) Pn i=1 Pni=1 2 2 n i=1 (xi ) − ( i=1 (xi ))

Pnn

(17)

Performing the multiplication gives the desired result:   Pn P 0 P n i=1 (xi )2 − ( ni=1 (xi ))2 Pn 0 n i=1 (xi )2 − ( ni=1 (xi ))2 Pn P A−1 A = n i=1 (xi )2 − ( ni=1 (xi ))2

(18)

Solving for the coefficients:  c˜ =

−

 Pn  Pn − (xi yi ) Pn i=1 (xi2) Pi=1 n i=1 (xi ) i=1 (xi ) i=1 (yi ) det(A)

Pnn

(19)

Simplifying:  Pn P Pn (xi yi ) − ( ni=1 (x i ))( i=1 (yP i )) Pn n i=1P P −( i=1 (xi ))( ni=1 (xi yi )) + ( ni=1 (xi )2 )( ni=1 (yi )) det(A)

 c˜ =

(20)

4 Define the following symbols:

SX = SY

=

SXX = SXY

=

n X i=1 n X i=1 n X i=1 n X

(xi )

(21)

(yi )

(22)

(xi )2

(23)

(xi yi )

(24)

i=1

Now we can write the final expressions for the slope and y-intercept of the ”best” line:

det(A) = nSXX − SX 2 nSXY − (SX)(SY ) m = nSXX − SX 2 (SXX)(SY ) − (SX)(SXY ) b = nSXX − SX 2

(25) (26) (27)