Polynomial Regression

Introduction
This article describes polynomial curve fitting by the least squares method.

Two approaches are presented

1. by use of linear algebra
2. by differential calculus

method 1. provides the best fitting polynomial , degree 0..7, for a set of points.
The graphics program Graphics-Explorer uses this method.

method 2. is limited to straight lines, so a polynomial of degree one or linear regression.

Method 1: Polynomial Regression
Look at the picture right:

you see the points (x₁,y₁)....(x₅,y₅).
Requested is the best fitting polynomial of degree 2 through these points.

"Best fitting" means :
the sum of the squares of the deviations must be minimal.
Dotted lines show the deviation for each point.

Given are the points (x₁,y₁) , (x₂,y₂)...(x_n , y_n)

Requested:
a polynomial, degree m, y = c₀ + c₁x + c₂x² + ... + c_mx^m
through these points with minimal deviations.

If the polynomial exactly crosses all points, if m+1 = n, than:

y₁ = c₀ + c₁x₁ + c₂x₁² + ... + c_mx₁^m
y₂ = c₀ + c₁x₂ + c₂x₂² + ... + c_mx₂^m
.............
.............
y_n = c₀ + c₁x_n + c₂x_n² + ... + c_mx_n^m

written as matrix:

­ y1 ­ y2 ... ... yn

=

­ 1 x1 1 x1 2 ... x1 m ­ 1 x2 1 x2 2 ... x2 m .. .. .. .. .. .. .. .. .. .. 1 xn 1 xn 2 ... xn m

­ c0 ­ c1 .. .. cm



or shorter: y = M . c

If the polynomial does not exactly cross the points, there will be a difference vector:

y - M . c

The norm of this difference vector is the sum of all squared deviations.

So we look for the values of c , making || y - M . c || minimal.

This will be the case if the difference vector is perpendicular to the column space of M.
The inner product equals zero in this case.

(M c )^t ( y - M c) = 0

(c^t M^t) (y - M c = 0

c^t ( M^t ( y - M c)) = 0

c^t ( M^t y - M^t M c ) = 0

so:
M^t y - M^t M c = 0

c = (M^t M)^-1 M^t y

Remarks
1.
M^t means the matrix M, reflected in the main diagonal.

If

M = 

­	2	0	3	­
	1	5	8

than

M t

=

­ 2 1 ­ 0 5 3 8

2.
rule: ( A B)^t = B^tA^t

3.
The inner product of two vectors a and b can be written as a^t.b

Example
Find the least-squares line through
points (0,1) (1,3) (2,4) en (3,4)

M

=

­ 1 0 ­ 1 1 1 2 1 3



M ^t = 

­	1	1	1	1	­
	0	1	2	3



M ^t M = 

­	4	6	­
	6	14



(M ^t M) ⁻¹ = 0 . 1 

­	7	−3	­
	−3	2



c = 0 . 

1  ­ 7 −3 ­ −3 2   ­ 1 1 1 1 ­ 0 1 2 3         ­ 1 ­ 3 4 4

=

­ 1.5 ­ 1

The line therefore is y = 1.5 + x

Method 2: Linear Regression
Look at the picture right:
Given are points (x_i, y_i)...where i = 1,2,...,n
Requested is the line y = b + ax with minimal deviation to these points.

Again, the result is measured as the sum of the squares
of the difference d_i of the point i and the line.

deviation = d₁² + d₂² + ..... + d_n²

in case of n points.

For a point i we observe

d_i = y_i - (ax_i + b)

Before continuing we give some definitions and calculus rules

Definition

sum:
S x_i = x₁+ x₂ + .... + x_n

average:


x

 = 

Σ xi

n

Rules

S (x_i + y_i) = S x_i + S y_i

and , if c is a constant:

S cx_i = c S x_i
and
S c = n c

from the avarage we know:


Σ

xi

 = n 

x

example:

Σ

x   y

 = n 

x

 

y

 = 

y

 

Σ

xi

The formulas for the regression line y = b + ax
Let f(a,b) be the function of the sum of the squared deviations of points 1..n:

f (a , b)

 = 

Σ	(yi − (a xi + b)) 2

First, the derivative of f(a,b) to a is calculated, where b is held constant

f '_a(a,b) = 2 

Σ	(yi − (a xi + b)) · −xi

second, the derivative of f(a,b) to b is calculated where a is held constant:

f '_b(a,b) = 2 

Σ	(yi − (a xi + b)) · −1

For the minimum of f(a,b) both derivatives must be 0.
This yields the following set of equations:

Σ	(xi yi − a xi 2 − b xi)

 = 0 ...................1)


Σ	(yi − a xi − b)

 = 0 ....................2)

Continuing with ....2)

Σ

yi

 − a 

Σ

xi

 − b n = 0


Σ yi

n

 − 

a  Σ xi

n

 − b = 0

b = 

y

 − a 

x

................3)

and using this result in ........1)

Σ	(xi yi − a xi 2 − ( y  − a  x ) xi)

 = 0


Σ	(xi yi − a xi 2 −  y  xi + a  x  xi)

 = 0


Σ

xi yi

 − a 

Σ

xi 2

 − 

y

 

Σ

xi

 + a 

x

 

Σ

xi

 = 0


Σ

xi yi

 − a (

Σ

xi 2

 − 

x

 

Σ

xi

) − 

y

 

Σ

xi

 = 0
a (

Σ

xi 2

 − 

x

 

Σ

xi

) = 

Σ

xi yi

 − 

y

 

Σ

xi


a = 

Σ xi yi  −  y   Σ xi

Σ xi 2  −  x   Σ xi

By now, the formulas for a and b are found.
By substituting the a value into ........3) the value of b can be calculated.
However, the formula for a may be written more elegantly.
Nominator and denominator are worked on separately.

1. nominator

Σ

xi yi

 − 

y

 

Σ

xi

=


Σ	(xi yi −  y  xi −  x   y  +  x   y )

=


Σ	(xi yi −  y  xi −  x  yi +  x   y )

=


Σ	(xi −  x )

 · (y_i − 

y

)

2. denominator

Σ

xi 2

 − 

x

 

Σ

xi

=


Σ	(xi 2 −  x  xi)

=


Σ	(xi 2 − 2  x  xi +  x  xi)

=


Σ	(xi 2 − 2  x  xi + ( x ) 2)

=


Σ	(xi −  x ) 2

summary:

a = 

Σ (xi −  x )  · (yi −  y )

Σ (xi −  x ) 2



b = 

y

 − a 

x

Note
The above formulas for a and b may be derived as well by using linear algebra instead of differential calculus.
In the case of linear regression so m = 1 and c =[b,a] .......{line has equation y = b + ax..}
we depart with:

y

=

­ y1 ­ y2 ... yn





M

=

­ 1 x1 ­ 1 x2 ... ... 1 xn



M^t =

­	1	1	...	1	­
	x1	x2	...	xn

remembering

M^tMc = M^ty

­ 1 1 ... 1 ­ x1 x2 ... xn      ·    ­ 1 x1 ­ 1 x2 ... ... 1 xn         ­ b ­ a

=

­ 1 1 ... 1 ­ x1 x2 ... xn      ·    ­ y1 ­ y2 ... yn





­	n	Σ xi	­
	Σ xi	Σ xi 2

 · 

­	b	­
	a

 = 

­	Σ yi	­
	Σ xi yi





­	b n + a  Σ xi	­
	b  Σ xi  + a  Σ xi 2

 = 

­	Σ yi	­
	Σ xi yi

The next set of equations has to be solved:

b n + a 

Σ

xi

 = 

Σ

yi


b 

Σ

xi

 + a 

Σ

xi 2

 = 

Σ

xi yi

or

Σ

xi yi

 − a 

Σ

xi 2

 − b 

Σ

xi

 = 0


Σ

yi

 − a 

Σ

xi

 − b n = 0

or

Σ	(xi yi − a xi 2 − b xi)

 = 0


Σ	(yi − a xi − b)

 = 0

which matches .......1) and ..........2) before.

---

OneStat