From a previous problem, it is given that the function $f(x) = e^{2x} - 2x - 1$ has a zero of multiplicity two in zero.
Using that information, I am trying to resolve the following problem:
Using the Newton method, calculate the root (zero) with a precision of $0.00001$ with $p_0 = 1$.
To do this, I have a function in Mathematica in which the function $f(x)$, the initial point $a$, the tolerance and the number of iterations.
From the given data I would believe that:
- $f(x) = e^{2x} - 2x - 1$
- The $a = p_0 = 1$
- Tolerance: $10^{-5}$ (from the precision)
- Number of iterations: ? (Not sure how to determine this)
Would that be correct and how do I calculate the number of iterations?
The Newton step is $$ N(x)=x-\frac{f(x)}{f'(x)}=x-\frac{e^{2x}-1-2x}{2(e^{2x}-1)} $$ By the extended mean value theorem we can simplify the fraction by replacing it with derivatives, using that $f(0)=f'(0)=0$, there are middle points $0<\xi_1<\xi_1<x$ with $$ \frac{f(x)}{xf'(x)} =\frac{f'(\xi_1)}{f'(\xi_1)+\xi_1f''(\xi_1)} =\frac{f''(\xi_2)}{2f''(\xi_2)+\xi_2f'''(\xi_2)} =\frac12(1+O(\xi_2))=\frac12(1+O(x)) $$ the last for $x\approx 0$ and thus $\xi_2\approx 0$.
Now insert the concrete functions to get $f'(x)=2(e^{2x}-1)$, $f''(x)=4e^{2x}$, $f'''(x)=8e^{2x}$ so that $$ \frac{f(x)}{xf'(x)}=\frac{1}{2+2\xi_2}\le\frac12 $$ It follows that for $x\in [0,1]$ $$ N(x)=x\frac{1+2\xi_2}{2(1+\xi_2)}\le\frac{x}{2}\left(1+\frac x{1+x}\right) $$ Starting with $x_0=1$ we get the sequence of upper bounds $\bar x_0=x_0=1$, $\bar x_{k+1}=\frac{x_k}2\frac{1+2x_k}{1+x_k}$, which again have upper bound in simpler fractions like $$ \bar x_2=\frac34, ~~ \bar x_3=\frac38\cdot\frac{14}{11}\le\frac12, ~~ \bar x_4\le \frac13 $$ and from that point onward $$ \bar x_{4+k}\le\frac13\left(\frac58\right)^k $$ To get that upper bound smaller than $10^{-5}$ we need $$ \ln3+k(\ln8-\ln5)>5\ln10\iff k> 22.15794.. $$ so $k\ge 23$ or $27$ iteration steps. In practice it is likely that the target accuracy is reached one or three steps earlier. For instance, going one step further in above scheme gives $\bar x_{5+k}\le\frac14(\frac35)^k$ which results in the estimate of 25 iteration steps.