Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
#76 2016-06-17 15:29:33
Re: Polynomial Root Finding
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
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
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
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
Re: Polynomial Root Finding
Please post them
'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
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
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
- thickhead
- 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
- thickhead
- Member
- Registered: 2016-04-16
- Posts: 1,086
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
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
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
- thickhead
- 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
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.
Please do the computation.
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
- thickhead
- 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
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.
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