Finding Line of Best Fit with Matrices

Date: 06/30/2004 at 14:24:33
From: Dominic
Subject: Line of best fit using linear algebra

Hello, Dr. Math -

I've recently been trying to recollect all that I've learned in my 
Linear Algebra classs.  I remember my teacher showing us a way to find
a line of best fit using matrices.  I believe you need at least two
matrices, but I don't remember much else.  Can you refresh my memory?

Date: 07/02/2004 at 08:42:36
From: Doctor Fenton
Subject: Re: Line of best fit using linear algebra

Hi Dominic,

Thanks for writing to Dr. Math.  In trying to fit a line y = mx + b to 
a set of data points, (x(1),y(1)),(x(2),y(2)),...,(x(n),y(n)), you are 
trying to solve an overdetermined linear system

   y(1) = m x(1) + b
   y(2) = m x(2) + b
    :       :
   y(n) = m x(n) + b

which can be written as a matrix equation

   [ x(1) 1 ]         [ y(1) ]
   [ x(2) 1 ] [ m ]   [ y(2) ]
   [  :   : ] [ b ] = [   :  ]
   [ x(n) 1 ]         [ y(n) ]   ,

or  

     A X = B ,

where A is the n x 2 matrix whose kth row is [ x(k) 1 ], X is the
2 x 1 matrix [ m ] ,  and B is the column vector of y's.
             [ b ]

You can show that the minimum norm of ||AX - B|| occurs when X 
satisfies the "normal equations"

    A^tAX = A^tB ,

where A^t is the transpose of A.  This gives the system of two 
equations in two unknowns

    [  n                n        ]          [  n           ]
    [ ---              ---       ]          [ ---          ]
    [ \                \         ]          [ \            ]
    [ /   x(k)^2       /   x(k)  ]          [ /   x(k)y(k) ]
    [ ---              ---       ]          [ ---          ]
    [ k=1              k=1       ] [ m ]    [ k=1          ]
    [                            ] [ b ]  = [              ]
    [  n                         ]          [  n           ]
    [ ---                        ]          [ ---          ]
    [ \                          ]          [ \            ]
    [ /   x(k)           n       ]          [ /    y(k)    ]
    [ ---                        ]          [ ---          ]
    [ k=1                        ]          [ k=1          ]

which can be easily solved with Cramer's Rule, for example, to give 
the formulas for m and b in the least squares fit of the line to the
data points.

If you have any questions, please write back and I will try to explain
further.

- Doctor Fenton, The Math Forum
  http://mathforum.org/dr.math/