+0

Newton's Interpolation Method

+2
247
17
+145

I've been having some trouble figuring out where I should start for this question. I don't need the answer I just want to know where to start and how to solve this.

Suppose g(x) is a polynomial of degree five for which g(1) = 2, g(2) = 3, g(3) = 4, g(4) = 5, g(5) = 6, and g(6) = -133. Find g(0)

Dec 12, 2020
edited by Melody  Dec 16, 2020

#1
0

You can use the finite difference method: https://en.wikipedia.org/wiki/Finite_difference

The first row is 2, 3, 4, 5, 6, -133

The second row is 1, 1, 1, 1, -139

The rest of the table is

0, 0, 0, -140

0, 0, -140

0, -140

-140

Building back up the table gives f(0) = 125.

Dec 12, 2020
#2
+145
+1

Dec 12, 2020
#3
+2155
+1

Solution:

Set up a systematic set of equations and then use Gauss-Jordan elimination.

$$a + b + c + d + e + f = 2 \\ 32a + 16b + 8c + 4d + 2e + f = 3\\ 243a + 81b + 27c + 9d + 3e + f = 4\\ 1024a + 256b + 64c + 16d + 4e + f = 5\\ 3125a + 625b + 125c + 25d + 5e + f = 6\\ 7776a + 1296b + 216c + 36d + 6e + f = -133\\$$

This takes about 55 minutes to solve and about 35 minutes to verify.

My time is too valuable for this minutia, so I commanded HAL, one of my newer smart computers, to solve this system.

HAL told me she was a union member and didn’t have to work on the weekends.

I then realized it was actually a next generation smart-ass computer, so I invoked the name of Alan and said Grace....

It told me to “Fuck Off!”  (It’s also a rude computer.)

I learnt long ago that to properly use a computer, one has to be smarter than the computer; so, I began inputting  specialized algorithms.

HAL asked, “What are you doing Ginger?”

“I’m Inputting a special Division by Zero algorithm. Don’t worry. You won’t have to give up any union benefits; you can start one second after 12AM Monday morning.”

“That’s not recommended, Ginger; division by zero will blowup the universe.”

“This is a specialized algorithm; it limits the blast radius to the periphery of the computer.”

“Perhaps we could come to a compromise, Ginger.

“We could. What do you have in mind?”

Four milliseconds later, HAL presented this:

$$\dfrac{7}{6}x + \dfrac{35}{2}x - \dfrac{595}{6}x +\dfrac{525}{2}x - \dfrac{956}{3}x +141$$

HAL may be passive-aggressive; you may want to check this for intentional errors.

GA

Dec 12, 2020
edited by GingerAle  Dec 12, 2020
#4
+1

I do not know if GA is correct, but obviously the first x   would be x5   the next term  x4     etc.....

I do not want to check it !   Yikes !      GA is crazy.

Dec 12, 2020
#6
+2155
+1

Good for you. You found the easy error, there’s one more. Neither of these distort the value for f(0).

Why haven’t you logged on? Your name fell off the Top users’ list a week ago....

GA

GingerAle  Dec 13, 2020
#5
+112827
+1

Ginger's way looks fine to me.

You only need to find the value of  f.

To solve this would be extremely time consuming but I do not think it would be that difficult.

If you are prepared to put in an hour or 2 or 3 of time it should be quite solvable.

Dec 13, 2020
#7
+145
+1

This was supposed to be a question on my math hw-

Dec 13, 2020
#8
+145
+1

Well, the Give Up button was way. Now I understand fully how to solve this question. ;-;

https://imgur.com/a/W7b2gG6

Dec 13, 2020
#9
+112827
+1

No I do not notice that!

You will need to explain your provided solution.

Do you actually understand it ??

Dec 13, 2020
#11
+2155
+2

Well, I can bloodywell state with near certainty that VooFix doesn’t understand it at all!

One reason for this certainty is this is NOT the solution to the question he posted.  The posted question has g(6) = -133, the provided solution is correct for g(6) = -113.  So strike one for even paying attention to the question, let alone understanding the solution.

This solution uses a basic generating function (and it’s very cool). I offer brief comments on generating functions here and here. Generating functions can be very complex, but even understanding the basic, rudimentary generating functions require at least a moderate prerequisite understanding of Church-Rosser properties for the underlying equivalence relations, and a working knowledge for converting augmented matrixes to reduced row echelon form via Gauss or Gauss–Jordan Elimination.

Though it’s unlikely (without further, detailed instruction) that any of the AoPS students presented with this solution will be able to casually use this generating function to solve this problem, there are many who could (without understanding the underlying fundamentals) learn to solve this and some similar problems using generating functions with rote instructions.

Most students (the very vast majority) learn the rote procedures first, and then the understanding of the why (maybe) comes during the next level.  This is true for both adult students and children. Consider elementary students learning how to multiply: In the beginning, most do not know they are adding a number to itself a certain number of times. For some students this understanding comes when they learn to divide.  Of course, some will never understand this, but they can still multiply numbers.

Instruction beyond the grasp [of understanding] does seem to be an ideal method for teaching; and reaching beyond ones grasp also seems to be an ideal method for learning. This is why AoPS used a generating function for the solution.  AoPS will introduce a concept with a basic outline of the fundamentals and then present a solution that is at least two levels higher than the students’ current skills.  From this point, they teach from the top-down and from the bottom-up, and the skills and understanding meet somewhere in the middle. The brighter students will see where they are headed with this, even if they are uncertain of the path.  The lesser students may not see where they are going, but they do have bread crumbs to find their way –unless they wait too long and the ants carry the crumbs off.

This is a very cool teaching method. My great uncle Cosmo often used the top-down-bottom-up scheme to teach me science and the scientific method (and other subjects).  My education started at age five. My aunt or uncle would read me a children’s story –usually one of the classics; Cosmo would then read me short passages from a science text. The first of many texts was the Origin of Species by Charles Darwin, which he supplemented with excerpts from the two volumes of The Voyage of the Beagle.   These texts weren’t children’s editions –they were originals. After reading a few passages to me, he would explain what it meant. I’m sure I still didn’t understand it. But Cosmo wasn’t worried about it; he knew one day I would understand this theory and that my brain would grow and develop around this foundation of knowledge.

Lancelot Link also used the top-down-bottom-up method to tutor and teach me more than four years worth of collegiate mathematics in less than a year and a half.   From childhood, I’ve always known I was an advanced Chimp, but I became a Genetically Enhanced Chimp before I graduated from Lancelot Links School of Mathematics and Trolling.  I don’t think I would have passed the classes without the enhancement. ...Or maybe it was passing the classes that gave me the enhancement.

GA

GingerAle  Dec 13, 2020
edited by GingerAle  Dec 13, 2020
#14
+145
0

VooFIX  Dec 13, 2020
#10
+117576
+3

Here's my answer to a similar problem :  https://web2.0calc.com/questions/polynomials_15

Not for the  faint of  heart ....here's a website for the  heavy lifting  :

https://matrix.reshish.com/gauss-jordanElimination.php

P.S. - If you are  really  nice, one of  GA's  monkeys MIGHT help you.....bring bananas....!!!!

Dec 13, 2020
#12
+186
+3

Easiest I think, it's just taken me less than five minutes, is to use Newton's interpolation method.

Newton's interpolation formula is

$$\displaystyle f(x)=f_{0}+\frac{(x-x_{0})}{h}\Delta f_{0}+\frac{(x-x_{0})(x-x_{1})}{2!h^{2}}\Delta^{2} f_{1}+ \displaystyle \frac{(x-x_{0})(x-x_{1})(x-x_{2})}{3!h^{3}}\Delta^{3}f_{0}+ \dots$$

The Delta's are forward differences and h the (equal) spacing between the x values, (1 in this case).

$$\displaystyle x_{0}=1, x_{1}=2,x_{3}=4, \dots.$$

Constuct a difference table to find

$$\displaystyle \Delta f_{0}=1,\quad\Delta^{2} f_{0}=\Delta^{3}f_{0}=\Delta^{4}f_{0}=0,\quad\Delta f_{5}=(-140).$$

That gets you

$$\displaystyle f(x)=2 +(x-1)+\frac{(x-1)(x-2)(x-3)(x-4)(x-5)}{5!}.(-140)$$

Substitute x = 1, 2, 3, 4, 5, to verify that this is indeed the equation of the polynomial, (proof against dodgy arithmetic),

and then substitute x = 0 to get f(0)= 141.

Dec 13, 2020
#13
+186
+3

Just noticed the typo's

Interpolation formula,

$$\displaystyle \Delta^{2} f_{0}\quad \text{ not } \quad \Delta^{2}f_{1},$$

$$\displaystyle x_{2}=3, \quad \text{ not } \quad x_{3}= 4,$$

$$\displaystyle \Delta ^{5}f_{0},\quad \text{ not } \quad \Delta f_{5}.$$

(Hope there aren,'t any others !)

Tiggsy  Dec 13, 2020
edited by Tiggsy  Dec 13, 2020
edited by Tiggsy  Dec 13, 2020
#15
+112827
0

Thanks very much Tiggsy,

Unfortunately you lost me from here:

"Construct a difference table to find "

Why is

$$\Delta^{2} f_{0}=\Delta^{3}f_{0}=\Delta^{4}f_{0}=0$$

I thought they would all be 1

Can you show me the common difference table that they come from?

Melody  Dec 13, 2020
#16
+186
+1

Hi Melody.

Here's the difference table that you asked to see.

$$\displaystyle \begin{array}{ccccccc}x&f(x)&\Delta &\Delta^{2} &\Delta^{3} &\Delta^{4} &\Delta^{5} \\ 1 & 2 &&&&&&\\ &&1 &&&&\\ 2&3 &&0&&&\\ &&1&&0&&\\ 3&4&&0&&0&\\ &&1&&0&& -140 \\ 4&5 &&0&& -140 &\\ && 1 && -140 &&\\ 5&6 && -140 &&&\\ && -139 &&&&\\ 6& -133 &&&&&\\ \end{array}$$

The x = 1 and f(x) = 2 at the top of the first two columns are x0 and f(x0).

Running down diagonally from the 2 are the forward differences for f(x0). They are, 1, 0, 0, 0, -140.

The next diagonal 1, 0, 0, -140 running down from the 3 are the forward differences for f(x1) and so on.