Fixed-point-iteration method converges but error increases

Question

I apologise beforehand for the possible errors in my post, I am an undergraduate student in Greece and I am translating Greek terminology in to english sort of on the go. Also excuse me if this questions sounds trivial but I am a beginner in this subject.

I am a physics student and taking a numerical analysis (calculus?) course and our professor gave us this problem after having recently done the Picard method else known as $x=g(x)$ method as he taught it to us (I am not asking anyone to do my homework for me, I just have a question of mathematical nature and I don't know if it's my own misunderstanding or an actual problem):

We have the function $f(x)=e^{2x}-3x-1$ and we need to find its roots with said method, how we do this and the starting points we choose are left to our own discretion.

Looking for the root $x=0$ specifically I solved for $x$ as such:

$$x=\frac 13e^{2x}-\frac 13=g(x)$$

and started iterations and according to the professor we should stop iterations when the value

$$\epsilon_n=\left|\frac{x_{n+1}-x_n}{x_{n+1}}\right| < 0.01$$

for this specific problem.

Although the method should converge this way (this can be proven) I see that the value $\epsilon_n$ actually increases with each iteration and slowly converges at the value $\epsilon_n=0.5$.

My question being: is this correct? i.e. Is this supposed to happen, or is it a misunderstanding/miscalculation of my own in this problem?

Again very sorry if this sounds trivial or like I'm just assigning my homework to smarter people since this isn't really what I'm trying to do here.

Answer 1

You get linear convergence with factor about $g'(0)=\frac23$ towards zero, so that $g(x)\approx \frac23x$ for $x\approx 0$, leading to $x_n\approx(\frac23)^nx_0$. Then $$ \frac{x_{n+1}-x_n}{x_{n+1}}\approx\frac{\frac23-1}{\frac23}=-\frac12 $$ so that your observed result is not surprising. The relative error will always converge towards $0.5$.

The question now is when to switch to the absolute error and determine for sufficient "numerical convergence". One intuitive variant to organically slide from relative to absolute error would be to include the scale of the initial value in the denominator, as in $$ ϵ_n=\frac{|x_{n+1}-x_n|}{|x_0|+|x_{n+1}|}. $$

The original method will finish after 50 or so steps because of floating point errors. The difference exp(2*x)-1 will be zero for about x<1e-16. You can continue the original scheme indefinitely by using the expm1(2*x) function contained in most math libraries, as that will return the relatively exact result for $e^{2x}-1\simeq 2x$ for $x\approx 0$.

Answer 2

$\epsilon_n$ is an expression for the approximate relative error: if $x_{n+1}$ is close to $L$ then $\frac{|x_{n+1}-x_n|}{|x_{n+1}|}$ is presumably close to $\frac{|x_n-L|}{|L|}$. Controlling relative error is usually more desirable than controlling absolute error.

However, a problem arises with this way of measuring the error when $L=0$ because then the denominator shrinks. As a result, if you have a method converging linearly to zero, such as fixed point iteration $x_{n+1}=g(x_n)$ with $g'(0) \neq 0$, $\epsilon_n$ will fail to go to zero even though the numerator is converging nicely.