Least Squares Line

We want to find a straight line that fits the given set of points best in a sense of least squares approximation. If a line is not perpendicular to the x-axis, it can be represented either explicitly as y=kx+c or implicitly as y-kx-c=0. Assume this line is used to approximate the given set of points p_i (i=1,2,¼,n). Then, the squared error with respect to p_i=(x_i,y_i) is (y_i-kx_i- c)². Accordingly, the total squared error is given by

f = å (yi-kxi-c)2.

We now want to optimize k and c such that f is minimized. This is equivalent to solving the following system of linear equations:

¶f ¶k =2 å (yi-kxi-c)xi=0

¶f ¶c =2 å (yi-kxi-c)=0

Alternatively, we may represent the above equations as

a00k+a01c=b0

a10k+a11c=b1

where,

a00= å xi2,     a01= å xi,    b0= å xiyi

a10= å xi,    a11=n,    b1= å yi

Since it is assumed that the line is not perpendicular to the x-axis, we have

ê ê ê a00 a01 a10 a11 ê ê ê ¹ 0.

Therefore,

k= ê ê ê b0 a01 b1 a11 ê ê ê ê ê ê a00 a01 a10 a11 ê ê ê ,   c= ê ê ê a00 b0 a10 b1 ê ê ê ê ê ê a00 a01 a10 a11 ê ê ê .

We now consider how to find the projection point of p_i on the line y=kx+c. Let

f=(x-xi)2+(kx+c-yi)2.

We want to find x such that the distance between p_i and (x,y), which is on y=kx+c, is minimized. This is equivalent to solving

df dx =2(x-xi)+2(kx+c-yi)k=0.

Therefore,

x= xi+(yi-c)k 1+k2 .

Finally, if the line is perpendicular to the x-axis, we may represent it as x=[`k] y + [`c]. Accordingly, we can solve the following linear system of equations to obtain optimized [`k] and [`c]:

_ a   00  _ k   + _ a   01  _ c   = _ b   0

_ a   10  _ k   + _ a   11  _ c   = _ b   1

where,

_ a   00  = å yi2,     _ a   01  = å yi,    _ b   0  = å xiyi

_ a   10  = å yi,    _ a   11  =n,    _ b   1  = å xi

In applications, we actually compare two determinants

ê ê ê a00 a01 a10 a11 ê ê ê    and    ê ê ê ê ê ê _ a   00  _ a   01  _ a   10  _ a   11  ê ê ê ê ê ê

and choose the method that yields the larger absolute value. This approach will guarantee the numerical stability.