# Polynomial Regression from data points

I'm trying to achieve polynomial regression using data points and spreadsheets, and I'm looking for shortcuts, I'm not interested in using the curve fit function

I found this cool pattern and want to simplify it.

I can do it for the 1st and 2nd order (ax + b), (ax² + bx + c) and 3rd order (ax^3 + bx^2 + cx + d), but beyond that I gets really long and tedious.

What I'm doing:

### 1st order: (sorry if this is too simple)

x   y   A  B  C
1   10
2   13
3   16
4   19
5   22


1)Subtracting y(n) from y(n+1) and storing in a column A we get:

x   y   A  B  C
1   10  -
2   13  3
3   16  3
4   19  3
5   22  3


2) A is constant, so it's the first therm, the scalar a in ax + b. multiplying 3 by x and storing in B I get:

x   y   A   B  C
1   10      3
2   13  3   6
3   16  3   9
4   19  3   12
5   22  3   15


3) subtracting B from y and storing in C I get:

x   y   A   B   C
1   10      3   7
2   13  3   6   7
3   16  3   9   7
4   19  3   12  7
5   22  3   15  7


4) 7is the constant b in ax + b and I'm done, y = 3x + 7

### 2nd Order

x   y   A   B   C ...
1   65
2   153
3   263
4   395
5   549


Doing the same process again until I get constant values:

1) Subtract y(n) from y(n+1) and store it in A and then Subtract A(n) from A(n-1) and storing in B

x   y   A   B   C ...
1   65
2   153 88
3   263 110 22
4   395 132 22
5   549 154 22


2) Since the B column is constant and this is a Power 2, I divide 22 by 2 and get 11, the first modifier a in ax^2 + bx + c. I then calculate the current prediction with ax^2, store in C, and subract it from y(the error) and store in D and I'll get:

x   y   A   B   C   D  E  F  G
1   65          11  54
2   153 88      44  109
3   263 110 22  99  164
4   395 132 22  176 219
5   549 154 22  275 274


3) Repeat the step 1, this time subtracting D(n) from D(n+1) and store in E. I get:

x   y   A   B   C   D   E
1   65          11  54
2   153 88      44  109 55
3   263 110 22  99  164 55
4   395 132 22  176 219 55
5   549 154 22  275 274 55


4) 55 is the second modifer b in ax^2 + bx + c, no need to divde since this is no powered. So I caculate the updated function with C + 55x and store in F and compute the error and store in G I get:

x   y   A   B   C   D   E   F   G
1   65          11  54      66  -1
2   153 88      44  109 55  154 -1
3   263 110 22  99  164 55  264 -1
4   395 132 22  176 219 55  396 -1
5   549 154 22  275 274 55  550 -1


5) Since G is constant this is the last therm in the function, -1 is the cin ax^2 + bx + c and the function is y = 11x^2 + 55x -1

## Finally...

So, as you can see this is scalable to nth root, you just just have to divide the current constant to all values prior to it(3th order the 1st term is divided by 3 and 2, the second by 2 and the 4th order the 1st term is divided by 4, 3 and 2 and the second by 3 and 2, and so on...), but is rather labor intense way. What I'm looking for is a way to simplify this process.

Any tips?

Also, this work for data that comes from non-functions, but the end part where all cells in the columns are constant sometimes doesn't and you have to average them.

And sorry for the lack of syntax, I'm have no math background.

Here's the spreadsheet with the 4th order regression. in case my explanation is subpar. Notify me if this is down.

I wouldn't call this a regression method because I'm not sure it can be made to produce reasonable results to give an approximate formula: in all of these examples, there is an exact formula, and you find it.

Anyway, this is known as the "method of finite differences" and you can look up some other sources to learn more.

Here's one thing that can speed this up. Suppose you're at the step where you have taken the differences up to the $k$-th level and gotten a constant:

x   y   A   B
1   65
2   153 88
3   263 110 22
4   395 132 22
5   549 154 22


The values at the top of the columns ($65$, $88$, and $22$) can then be used to directly write down the polynomial: $$65 + 88 \cdot \frac{(x-1)}{1!} + 22\cdot \frac{(x-1)(x-2)}{2!}.$$ This pattern generalizes: if you have values $a_0, a_1, \dots, a_k$ at the top of your columns, and the last column is constant, then the formula is $$a_0 + a_1 \cdot \frac{(x-1)}{1!} + a_2 \cdot \frac{(x-1)(x-2)}{2!} + \cdots + a_k \cdot \frac{(x-1)(x-2)(\cdots)(x-k)}{k!}.$$

• That's pretty cool. I just found out about the Tailor Series, that comes from that right? – f.rodrigues May 8 '17 at 4:02
• Taylor series are related but not quite the same idea. If you replace "taking differences" with "taking the derivative" and $\frac{(x-1)(x-2)(\dotsb)(x-k)}{k!}$ with $\frac{x^k}{k!}$, what you get is the Taylor series. What we're doing here is called a Newton series. – Misha Lavrov May 8 '17 at 4:17