Why linear convergence in this example?

Question

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

Answer 1

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

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.

Answer 2

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.