0
$\begingroup$

I am not sure if I understand the following problem correctly nor if I am on the right path. Here it is, with my idea for a proof:

Consider the fixed point iteration method $x_{k+1}=g(x_k)$, $k= 0,1,...$ for solving the nonlinear equation $f(x) = 0$. Consider choosing an iteration function of the form:

$g(x) =x−af(x)−b(f(x))^2−c(f(x))^3$ where a, b and c are parameters to be determined. Find expressions for the parameters a, b and c such that the iteration method is of fourth order.

Idea: If $r$ is a root such that $f(r)=0$ then $g'(r)=0$, $g''(r)=0$, $g'''(r)=0$ but $g^{IV}(r)\neq 0$. As such, $g'(r) =1−af'(r)−2b(f(r))f'(r)−3c(f(r))^2f'(r)=0$ which means $a=\frac{1}{f'(r)}$.

Is this the right approach to find a? Where can I take it next? Thanks and regards,

$\endgroup$
0
3
$\begingroup$

The basic fixed-point iteration to find roots of $f$ has the form $$ g(x)=x-a(x)f(x)\implies g'(r)=1-a(r)f'(r). $$ So to get $g'(r)=0$, one needs $a(r)=1/f'(r)$. As $r$ is unknown, one can only set $a(x)=1/f'(x)+b(x)f(x)$ to get the correct value at $x=r$ while retaining the freedom to further adapt the formula. In consequence $$ g(x)=x-\frac{f(x)}{f'(x)}-b(x)f(x)^2\\ g'(x)=\frac{f(x)f''(x)}{f'(x)^2}-b'(x)f(x)^2-2b(x)f'(x)f(x) $$ This has a double root at $x=r$ if $$ \frac{f''(r)}{f'(r)^2}-2b(r)f'(r)=0 \implies b(x)=\frac{f''(x)}{2f'(x)^3}+c(x)f(x). $$ Now do a similar computation to determine the form of $c(x)$.


One could alternatively start with a formula with known 4th convergence order, $$ \tilde g(x)=x+p\frac{(1/f)^{(p-1)}}{(1/f)^{(p)}},~~~p=4-1=3, $$ treat the fraction as a division of Taylor series in $f(x)$ or $s=f(x)/f'(x)$ and carry it out to get a truncated Taylor series expansion for the quotient.


Another related approach is to directly employ the Taylor expansion of $f$, we want $f(g(x))=O(f(x)^4)$. So \begin{align} f(g(x))&=f(x)-f'(x)(af+bf^2+cf^3)+\tfrac12f''(x)(af+bf^2+cf^3)^2-\tfrac16f'''(x)(af+bf^2+cf^3)^3+O(f(x)^4) \\ &=(1-af'(x))f(x)+(-bf'(x)+\tfrac12a^2f''(x))f(x)^2 \\&\quad+(-cf'(x)+abf''(x)-\tfrac16a^3f'''(x))f(x)^3+O(f(x)^4) \end{align} also gives easy-to-solve equations if one wants the coefficients to be zero.

$\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.