How do I derive the condition for the function $A(x)$ so that this Newton type method converges

Question

Say I modify Newtons method by introducing the function $A(x)$ s.t.

$$p_{ n + 1} = p_n - A(p_n) \frac{f(p_n)}{f'(p_n)}$$

If $x = a$ is a simple root of $f$ and $f$ is sufficiently differentiable, what conditions do I have put on $A(x)$ so that this method converges for an sufficiently accurate initial value $p_0$.

Can I somehow derive a condition on $A(x)$ that would ensure this method has quadratic convergence like Newtons method? I've also read that applying fixed point theorem is a good way to start, but I have not been able to make any progress using this. I'd appreciate if someone could post a solution to this problem, as I have no idea.

Answer 1

Let $\epsilon_n:=p_n-a$ so$$\epsilon_{n+1}:=\epsilon_n-A(a+\epsilon_n)\frac{f(A+\epsilon_n)}{f^\prime(A+\epsilon_n)}.$$Taylor-approximating $f$ (if it's nice enough we can),$$\begin{align}\epsilon_{n+1}&=\epsilon_n\left[1-(A(a)+\epsilon_nA^\prime(a))\frac{1+\epsilon_nf^{\prime\prime}(A)/(2f^\prime(A))}{1+\epsilon_nf^{\prime\prime}(A)/(f^\prime(A))}\right]+o(\epsilon_n)\\&=\epsilon_n\left[1-A(a)\right]+o(\epsilon_n).\end{align}$$This tells us:

• A sufficiently accurate seed converges if $|1-A(a)|<1$ (the case $|1-A(a)|=1$ is trickier);
• We get quadratic convergence or better iff $A(a)=1$.

It's obvious now why Newton's method uses $A(x)=1$, but you could also e.g. have $A(x)=1+g(x)f(x)$. Then we'd have$$p_{n+1}=p_n-\frac{f(p_n)}{f^\prime(p_n)}-\frac{f^2(p_n)g(p_n)}{f^\prime(p_n)}.$$For quadratic convergence we need the extra term to be $O(\epsilon_n^2)=O(f(p_n)^2)$ (or $o$), i.e. $g(p_n)\in O(f^\prime(p_n))=O(1)$ (or $o$).