0

Consider $F(x)=x-f(x)f'(x)$ where for some $r$ $f(r)=0, 0\neq f'(r)$. Find a perciese condition of $f$ such that $x_{k+1}=F(x_k)$ converge to the fixed-point $r$ at least cubically if started near $r$.

I want somehow to show $|g(x)-g(y)|<L|x-y|$ for any $x,y$ in the domin of $g$. So, $$|g(x)-g(y)|=|x-y-(f'(x)f(x)+f'(y)f(y))|$$

I am lookinf for a specific of $f$ condition that guarntess $|x-y-(f'(x)f(x)+f'(y)f(y))|<L|x-y|^3$ with $L<1$, how can I come up with a spicif formula for this condition, thanks in advance for any help.

Best,

Ahmed
  • 1,486
  • 2
    Intuitively, Newton's method converges quadratically because the Taylor expansion about $x$ gives $0=f(x_n)+f'(x_n)(x_{n+1}-x_n)+\mathcal O(x_{n+1}-x_n)^2$. Under what conditions would you expect the last term to actually be $\mathcal O(x_{n+1}-x_n)^3$? – Simply Beautiful Art Sep 25 '20 at 17:38

1 Answers1

2

You have at some stage transcribed the Newton method incompletely. It should be $F(x)=x-f(x)/f'(x)$, then also the remark about $f'(r)\ne 0$ makes sense.

There are two ways to get to the convergence behavior. One is to Taylor expand $F(x)$ around $x=r$. This requires to compute the derivatives of $F$. The first non-zero derivative determines the order of convergence. \begin{align} F'(x)&=\frac{f(x)f''(x)}{f'(x)^2},& \implies F'(r)&=0, \\ F''(x)&=\frac{ff'''+f'f''}{f'^2}-2\frac{ff''^2}{f'^3},&\implies F''(r)&=\frac{f''(r)}{f'(r)} \end{align}

The second way is to consider the evolution of the function values, that is, to compute the Taylor expansion of $f(x+s)$ with $s=-f(x)/f'(x)$ \begin{align} f(x+s)&=f(x)+f'(x)s+\frac12f''(x)s^2+\frac16f'''(x)s^3+...\\ &=\frac{f''(x)^2}{2f'(x)^2}f(x)^2+\frac{f'''(x)}{6f'(x)^3}f(x)^3+... \end{align} This in general gives $f(F(x))=O(f(x)^2)$, now check how you could ensure that $f(F(x))=O(f(x)^3)$.

Lutz Lehmann
  • 126,666
  • Thanks for your effor but $F(x)=x-f(x)f'(x)$ – Ahmed Sep 28 '20 at 03:15
  • 1
    This is so obviously wrong that it is easy to correct. If the transcription error is not with you, then it is with the one assembling the task sheet. – Lutz Lehmann Sep 28 '20 at 07:07
  • It is NOT wrong. – Ahmed Sep 29 '20 at 01:09
  • Theorem: Assume that the iterations $x_{k+1} = g(x_k)$ converge to a fixed point $z$. Furthermore, assume that $q$ is the first positive integer for which $g^{(q)}(z) \neq 0$ and if $q = 1$ then $|g(z)| < 1$. Then the sequence ${x_k}$ converges to z with order $q$. (It is assumed that $g \in C^q(G)$, where $G$ contains z. – Ahmed Sep 29 '20 at 01:11
  • Yes, this is the first way. If $f''(r)\ne 0$, then the Newton method is of second order. – Lutz Lehmann Sep 29 '20 at 04:22