Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#151 2016-06-19 04:06:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

It sure does!

happy-jump-happy-animation-animated-smiley-emoticon-000360-large.gif

I feel just like my teachers.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#152 2016-06-19 04:08:33

ElainaVW
Member
Registered: 2013-04-29
Posts: 580

Re: Polynomial Root Finding

You aren't going to finish with that awful Colonel story?

Offline

#153 2016-06-19 04:10:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

smiley_14.gif

You can bet a whole lot of bananas I am!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#154 2016-06-19 14:19:33

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

nestList :: (Double -> Double -> Double) -> Double -> Double -> [Double]
nestList f x n = (x : (nestList f (f x (n+1.0)) (n+1.0)) )

f :: Double -> Double -> Double
f x n = (1.0 - 8.0*x*n)/n
*Main> take 21 $ nestList f 0.11778303565638346 0
[0.11778303565638346,5.7735714748932354e-2,3.811428200854117e-2,2.8419077265003995e-2,2.2647381879968037e-2,1.8820944960255704e-2,1.6099106984621026e-2,1.4064286980174654e-2,1.248570415860277e-2,1.1225477842288951e-2,1.0196177261688389e-2,9.339672815583799e-3,8.615950808662945e-3,7.995470453773365e-3,7.464807798384503e-3,6.948204279590642e-3,6.914365763274866e-3,3.508603305565781e-3,2.748672911102931e-2,-0.16726225394086605,1.3880980315269285]

Last edited by Agnishom (2016-06-19 14:21:59)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#155 2016-06-19 14:25:01

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

So your answer for a[20] was?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#156 2016-06-19 15:13:58

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

1.3880980315269285

The error amplifies with each step


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#157 2016-06-19 15:48:25

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

Correct a mundo.

The correct answer to 30 digits is 0.00531798937699268677949682431548, notice that a[19] does not even have the right sign!

What do you think went wrong?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#158 2016-06-19 16:07:40

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

That multiplication by 8 and the subtraction.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#159 2016-06-19 16:09:19

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

The effect is called smearing. The subtraction had little effect.

So is that the end? Nope, there is a nice workaround. It will seem like magic!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#160 2016-06-19 23:48:08

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

Why does smearing happen?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#161 2016-06-19 23:52:36

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

Why does smearing happen?

It happens all the time.

Anytime a multiplication occurs 101 * .123456 = 12.4690, actual answer 12.469006. We lost 2 digits, they were smeared out.

Anytime you have a number n, unless you are dealing with integers you have a small error called little e. You do not really have n but instead n + e. Everytime you do a calculation the little e is either no trouble because it remains small or...

Here is what happened.

1st iteration) 8 (n + e) = 8n + 8e. For the sake of brevity I will just chart the e.
2nd iteration) 8 (n + 8 e) = 64e
3rd iteration) 8 (n + 64 e) = 512e
3th iteration) 8 (n + 512 e) = 4096e etc.

The small e is now 4000 times larger than it was and that is only the third iteration! You lost about 18 - 20 digits doing that calculation and since you only had about 16 to start your final answer does not have a single correct digit.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#162 2016-06-20 02:43:11

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

Oh I see!

What can we do about this?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#163 2016-06-20 03:12:22

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

Run the recursion in a different way!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#164 2016-06-20 03:26:10

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

There is a different way?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#165 2016-06-20 03:27:21

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

If multiplying by some constant is unstable when that constant is greater than 1 than dividing by it must be stable.

We can run the recurrence backwards, first you solve for a[n-1].

Now we have the 8 on the bottom as a divisor. The error is going to work for us! What does this difference equation say. Well it runs from the higher numbers downwards ( backwards direction ). We need to start from say a[50] then we would get a[49], a[48], a[47]... all the way down to a[20].

Only one problem, how do we know what a[50] is?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#166 2016-06-20 03:31:06

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

Something like 1 or 0 or Infinity?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#167 2016-06-20 03:33:58

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

Right! Start with anything at all, try a[50]=1241. At each step the system which is now an error divider will pick up almost 1 digit per iteration. By the time you get to a[20] you should have about 25 correct digits! Try it.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#168 2016-06-20 03:36:57

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

And if I work all the way down to a[0], would it converge to log(9/8)?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#169 2016-06-20 03:38:16

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

That I would doubt, get a[20], which is the point.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#170 2016-06-20 03:40:06

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

That is strange. I have never seen anything like this before


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#171 2016-06-20 03:43:38

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

Numerical analysis, it is fantaaastic!

What did you get?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#172 2016-06-20 03:58:52

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,838
Website

Re: Polynomial Root Finding

You'll have to wait. I have a computer issue.


Does the sequence of a converge as n goes towards infty?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#173 2016-06-20 04:02:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

I do not understand the question

I am getting .005317989376992687 with all digits correct.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#174 2016-06-20 08:42:18

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Polynomial Root Finding

Hmm, out Intro to NA professor mentioned that trick with the example of the integral

It's quite brilliant.

Also, yes, if you ran it to a[0], you would get an approximation of ln(9/8). This is also, I think, the only value of a[0] for which the sequence a[n] converges.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#175 2016-06-20 09:06:46

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Polynomial Root Finding

Thanks, I will try that for a[0]. I think the idea is credited to Wilkinson.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB