2
$\begingroup$

It is obvious that for any given $f(x)$ there exists $g(x)$ such that $f(x)=0 \Leftrightarrow g(x)=x$. We could use this fact to solve any root finding problem using fixed point iteration method, only if $g(x)$ promises convergence of the fixed point iteration method.

So I was wondering if there exists an algorithm that takes $f(x)$ and returns appropriate $g(x)$ and $x_0$ such that $x_{i+1}=g(x_i)$ converges to a root of $f(x)$.

$\endgroup$

1 Answer 1

4
$\begingroup$

You do not specify your class of $f$, and most importantly, do not specify where the convergence should hold, for which $x_0$.

In general, the answer on your question is Newton's method: $g(x)=x-f(x)/f'(x)$. The iterates usually converge when $x_0$ is sufficiently close to the root, and if $f'(x)\neq 0$ at the root $x$. Finding an algorithm with global convergence is another matter, and the answer strongly depends on the class of functions $f$ you consider. There are even results on non-existence of globally convergent iterative methods satisfying some natural conditions for the class of rational functions (C. McMullen).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.