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

You are not logged in.

#76 2016-06-17 15:29:33

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

Re: Polynomial Root Finding

bobbym wrote:

This one does not converge to the fixed point, it falls in a limit cycle and oscillates between 1.92 and 0.54.

Maybe I should choose a different starting point

Last edited by Agnishom (2016-06-17 15:31:28)

'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

#77 2016-06-17 15:30:50

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

Re: Polynomial Root Finding

We have not discussed how to know beforehand, we are just seeing how they are created.

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

#78 2016-06-17 15:32:00

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

Re: Polynomial Root Finding

Okay.

I guess I know how to draw cobwebs. I have done them for a guy on Brilliant.

'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

#79 2016-06-17 15:37:17

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

Re: Polynomial Root Finding

The general method when you have an iteration:

If the absolute value of the derivative of g(x) is less than 1  for the point in question, then there will be convergence to that 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

#80 2016-06-17 15:39:57

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

Re: Polynomial Root Finding

Yeah! because if that is so, it means that it is a contraction mapping, which means it must converge to the fixed point. Right?

'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

#81 2016-06-17 15:42:59

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

Re: Polynomial Root Finding

I do not even know what a contraction mapping is.

The important thing is that now you know how to tell whether the iteration you have will converge. of course, sometimes it will be easier to just run the calculation and see because the derivative may be difficult to compute.

You have code for a cobweb?

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

#82 2016-06-17 15:44:42

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

Re: Polynomial Root Finding

How can you not know that?

I can make one on Geogebra

'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

#83 2016-06-17 15:45:46

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

Re: Polynomial Root Finding

I am a bumpkin remember.

I have a couple for M.

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

#84 2016-06-17 15:48:51

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

Re: Polynomial Root Finding

'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

#85 2016-06-17 15:49:45

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

Re: Polynomial Root Finding

ClearAll[CobwebPlot]
Options[CobwebPlot] = Join[{CobStyle -> Automatic}, Options[Graphics]];
CobwebPlot[f_, start_?NumericQ, n_, xrange : {xmin_, xmax_},
opts : OptionsPattern[]] :=
Module[{cob, x, g1, coor}, cob = NestList[f, N[start], n];
coor = Partition[Riffle[cob, cob], 2, 1];
coor[[1, 2]] = 0;
cobstyle = OptionValue[CobwebPlot, CobStyle];
cobstyle = If[cobstyle === Automatic, Red, cobstyle];
g1 = Graphics[{cobstyle, Line[coor]}];
Show[{Plot[{x, f[x]}, {x, xmin, xmax},
PlotStyle -> {{Thick, Black}, Black}], g1},
FilterRules[{opts}, Options[Graphics]]]]

This is the cobweb for the Fibonacci polynomial.

CobwebPlot[20/(10 + 2 # + #^2) &, 1, 40, {0, 4},
PlotRange -> {{0, 3.5}, {0, 3}}, Frame -> True, Axes -> False,
CobStyle -> Directive[Dashed, Red], PlotRangePadding -> None]

With a cobweb, you have a graphical means of testing convergence.

here is the cobweb for one iteration that does not converge:

CobwebPlot[(20 - 2 #^2 - #^3)/10 &, 1, 40, {0, 4},
PlotRange -> {{0, 3.5}, {0, 3}}, Frame -> True, Axes -> False,
CobStyle -> Directive[Dashed, Red], PlotRangePadding -> None]

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

#86 2016-06-17 16:18:12

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

Re: Polynomial Root Finding

Okay, I am eating now..

'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

#87 2016-06-17 16:19:03

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

Re: Polynomial Root Finding

Remember to watch out for the topo boys, do the calculation before using the test for convergence.

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

#88 2016-06-17 16:23:19

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

Re: Polynomial Root Finding

What calculations?

I think you mean Analysis boys

Last edited by Agnishom (2016-06-17 16:24:14)

'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

#89 2016-06-17 16:27:28

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

Re: Polynomial Root Finding

They are just miniature topo boys. If you do the calculations

Out[28]= {0, 0.3333333333333333, 0.241105637657362, \
0.241073360838539, 0.241073360510646, 0.24107336051065, \
0.24107336051065, 0.24107336051065, 0.2410733605106, 0.2410733605106, \
0.241073360511, 0.241073360511, 0.241073360511, 0.24107336051, \
0.24107336051, 0.24107336051, 0.2410733605, 0.2410733605, \
0.241073361, 0.241073361, 0.241073361}

that is like throwing a whole bushel of raw garlic on a vampire. They will be repulsed by those calculations and head somewhere else. If you quote the test first they will jump on it like hungry wolves, pointing out where you violated this axiom or that condition.

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

#90 2016-06-17 16:29:59

Member
Registered: 2016-04-16
Posts: 1,086

Re: Polynomial Root Finding

``````iteration 	x	sqrt(20/x-9)-1
1	1.5	1.081665999
2	1.290833	1.548307481
3	1.41957024	1.255830441
4	1.33770034	1.439473622
5	1.388586981	1.324463563
6	1.356525272	1.396570746
7	1.376548009	1.351403267
8	1.363975638	1.379709749
9	1.371842693	1.361976084
10	1.366909389	1.373088232
11	1.36999881	1.366126122
12	1.368062466	1.370488451
13	1.369275458	1.367755235
14	1.368515347	1.369467784
15	1.368991565	1.368394775
16	1.36869317	1.369067085
17	1.368880127	1.368645842
18	1.368762985	1.368909777
19	1.368836381	1.368744406
20	1.368790393	1.368848021
21	1.368819207	1.3687831
22	1.368801153	1.368823777
23	1.368812465	1.36879829
24	1.368805378	1.368814259
25	1.368809818	1.368804254
26	1.368807036	1.368810523
27	1.368808779	1.368806595
28	1.368807687	1.368809056
29	1.368808371	1.368807514
30	1.368807943	1.36880848
31	1.368808211	1.368807875
32	1.368808043	1.368808254
33	1.368808148	1.368808016
34	1.368808082	1.368808165
35	1.368808124	1.368808072
36	1.368808098	1.36880813
37	1.368808114	1.368808094
38	1.368808104	1.368808117
39	1.36880811	1.368808102
40	1.368808106	1.368808111
41	1.368808109	1.368808106
42	1.368808107	1.368808109
43	1.368808108	1.368808107
44	1.368808108	1.368808108
45	1.368808108	1.368808107
46	1.368808108	1.368808108``````

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#91 2016-06-17 16:39:21

Member
Registered: 2016-04-16
Posts: 1,086

Re: Polynomial Root Finding

Agnishom wrote:
bobbym wrote:

This one does not converge to the fixed point, it falls in a limit cycle and oscillates between 1.92 and 0.54.

Maybe I should choose a different starting point

I used the same equation with amoderation factor of 0.5 to get the result

``````iteration	x	(20-2x^2-x^3)/10
1.5	1.2125
1	1.35625	1.382646655
2	1.369448328	1.368097461
3	1.368772894	1.368847181
4	1.368810037	1.368805967
5	1.368808002	1.368808225
6	1.368808114	1.368808101
7	1.368808108	1.368808108
8	1.368808108	1.368808108
9	1.368808108	1.368808108
10	1.368808108	1.368808108 ``````

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#92 2016-06-17 16:44:31

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

Re: Polynomial Root Finding

Let's do 4)

'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

#93 2016-06-17 16:59:24

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

Re: Polynomial Root Finding

That one seems to oscillate above and below the root. There are many, many different ways to do them but when choosing one you naturally consider complexity, convergence rate and numerical stability.

Compute as many digits as you can

Do not use M, Sage, Maxima, Maple  any other CAS or Wolfram Alpha.

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

#94 2016-06-17 17:48:47

Member
Registered: 2016-04-16
Posts: 1,086

Re: Polynomial Root Finding

1.423025E-05 from excel sheet using conjugate surds. did not try further.

Last edited by thickhead (2016-06-17 17:59:22)

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#95 2016-06-17 17:51:34

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

Re: Polynomial Root Finding

These algorithms are non-terminating. How do you define "complexity" in such a case?

'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

#96 2016-06-17 18:00:34

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

Re: Polynomial Root Finding

How many machine instructions it takes for each computation. We will see later that stability is probably at least if not more important.

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

#97 2016-06-17 18:15:09

Member
Registered: 2016-04-16
Posts: 1,086

Re: Polynomial Root Finding

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#98 2016-06-17 18:29:42

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

Re: Polynomial Root Finding

Hi;

We will wait for Agnishom to do the computation before doing more.

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

#99 2016-06-17 23:51:19

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

Re: Polynomial Root Finding

bobbym wrote:

That one seems to oscillate above and below the root. There are many, many different ways to do them but when choosing one you naturally consider complexity, convergence rate and numerical stability.

Compute as many digits as you can

Do not use M, Sage, Maxima, Maple  any other CAS or Wolfram Alpha.

May I use specialized libraries for handling large precision floats?

'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

#100 2016-06-18 02:35:58

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

Re: Polynomial Root Finding

Nope, that would defeat the purpose of the question, Try to use the simplest language you can.

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