1
$\begingroup$

I'm working on a university project studying numerical analysis and have hit a small snag. I have several theorems that deal with convergence of iterative procedures with respect to the absolute error at step $n$, i.e. $\epsilon_n = |x_n - x|$, where $x$ is the value being approximated by $x_n$.

My issue is that when I have written the programs to implement these methods I have used the error approximation of $\delta_n = |x_n - x_{n-1}|$. Testing has shown that these methods still converge, but I don't know how $\epsilon_n$ and $\delta_n$ have any connection to each other, and thus why $\delta_n$ is a valid error measure.

I've looked through several books without finding the answer and I want to be fairly rigorous with my perturbing choices in my project. In particular I an working with Newton's Method as one of those being used, and I can know that $\epsilon_n \le \epsilon_{n-1}$.

$\endgroup$

1 Answer 1

0
$\begingroup$

In general, there is no relation between the absolute value of the error $\epsilon_n$ and the number $\delta_n$!

For example consider a function $f : \mathbb{R} \rightarrow \mathbb{R}$ which far away from the desired root is positive and decays as $x \rightarrow \exp(-\lambda x)$, where $\lambda >0$. If the user has picked an initial guess far from the root and inside the bad region, then Newton's method will essentially reduce to $x_{n+1} = x_n + \frac{1}{\lambda}$. If $\lambda$ is sufficiently large, then your routine will signal convergence, despite the fact that you are moving away from the root! A good routine should also monitor the residual, i.e the absolute value of $f(x_n)$, but this will not save you in this case, as $f(x_n) \rightarrow 0$.

If you want a truly robust code, then you should strive to maintain a bracket, i.e. an interval $[a,b]$ for which you are certain that $f(a)$ and $f(b)$ have different signs. You should look into hybrid methods such as merger between the secant method and the bisection method.

If you can decisively say that you are close to a root, then you can approximate the error as $x - x_{n} \approx \frac{f'(x_n)}{f(x_n)}$. This estimate is however worthless unless you are close to a root, so look for a bracket.

$\endgroup$
1
  • $\begingroup$ Thanks for that, that helps a lot. $\endgroup$
    – user163911
    Feb 2, 2016 at 10:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .