0
$\begingroup$

So when I run newton method for certain values in matlab it gives the following result. Question is how do you tell this is linear or quadratic? Book says Notice how the convergence rate actually looks linear for the first 20 iterations and then converges quadratically? How?

Problem description:

The following illustrates the possible effect of a poor ini- tial approximation with Newton's method, yet the eventual characteristic quadratic convergence. Here Newton's method is used to compute a root of $$x^3 + 4x^2 - 10 = 0\text{ with }p_0 = -100.$$

>> Newton_wCR(-100,10^(-8),1000,'Ex2','Ex2Prime',xt)

**i ------approximation--------------- convergence rate(not sure what this column called)**

 0 -100.0000000000000000
 1 -67.1229452054794540  ------------ 0.6756574735718571
 2 -45.2106915629508280 ------------ 0.6800578556444912
 3 -30.6110303374327980------------ 0.6865405829580693
 4 -20.8903135326827250 ------------0.6960020747237687
 5 -14.4275998450253840------------ 0.7096133071622610
 6 -10.1439728120448680------------ 0.7287612751243944
 7 -7.3216506641581773 ------------0.7547769215046272
 8 -5.4823476696099007 ------------0.7882665754466991
 9 -4.3043281697322326------------ 0.8279655150465651
10 -3.5648242613362786------------ 0.8695658665971102
11 -3.0994781840095929------------ 0.9056103540867716
12 -2.7643039450246527 ------------0.9249280749908025
13 -2.0756744750764016 ------------0.8332428121722965
14 -2.5401125042410282------------ 1.1349755654997482
15 -3.1421077624340263 ------------1.1541465967380635
16 -2.8006794352317459------------ 0.9242505567184756
17 -2.2742377750642446------------ 0.8736310362342069
18 -2.6754008707963317------------ 1.1102257580083743
19 4.7255390285480541 ------------0.8316297903540348
20 2.9616670020385882------------ 0.4750863630203516
21 1.9405440180104074------------ 0.3603737627577821
22 1.4793327062840065------------ 0.1983311582167616
23 1.3711198338928769------------ 0.0516185931343018
24 1.3652469470192556------------ 0.0028750630379588
25 1.3652300135546727------------ 0.0000083015856297
26 1.3652300134140969------------ 0.0000000000000000

ans =

1.3652
$\endgroup$
  • $\begingroup$ You really haven't supplied sufficient information about the problem or even what the program is outputting. Please edit your question to provide more information. In general, the quadratic convergence of Newton's method is asymptotic as the iterates approach a solution, and convergence may be very slow until the iterates are close enough to the solution. $\endgroup$ – Brian Borchers Oct 11 '16 at 5:01
  • $\begingroup$ @BrianBorchers I have updated but all I need is how by looking at the numbers say this is linear or quad? $\endgroup$ – Square-root Oct 11 '16 at 5:18
1
$\begingroup$

Here is a plot of the error as a function of the number of iterations, on a logarithmic scale.

enter image description here

The convergence is indeed linear (constant slope), then slows down because of the quasi-root and finally quadratic (i.e. the number of correct digits grows exponentially) when it finds the attraction basin of the real root.

$\endgroup$
1
$\begingroup$

If $p_*=1.3652300134140968457608068289816660783311647...$ is the exact solution, then your last column shows something like $$ \frac{|p_{k+1}-p_*|}{|p_k-p_*|} $$ which would be constant under linear convergence.

What you can observe from your table is that far from the solution the convergence is indeed linear, which conforms with theory that states that the contraction factor there should be close to $1-\frac1{\deg f}(=\frac23)$. Then the iteration enters a stage of seemingly chaotic jumps around the local maximum at $(x,y)=(-2.65,-0.54)$ to then make a long jump to the positive axis and finally end up in a basin of quadratic convergence around the real root.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.