How to change the tolerance to get 8 significant numbers in the point fix method ( matlab)

Question

So we have a fixed point function and were asked to choose an epsilon ( tolerance) that would give us an approximation of the root with 8 significant numbers.

The root is 1 so we would like a result that gives us 1,234567 ( 8 significant numbers)

My question is how am i supposed to guess that ? I know we have the formula :

$\Delta x\leq 0.5\quad X \quad 10^-m $ (exponent -m) But i am not sure what plays the role of $\Delta x$ here i think it's $errel$ but i am not sure.

Also when i check the output in the console it's always an answer with 5 significant numbers no matter what i change the epsilon to so i am a bit confused.

Thanks for your help.

The function

function [x] = pointfixe(g, x0, N, epsilon)

x(1)=x0;

x1=g(x0);

e_n=abs(x1-x0);
errel=e_n/abs(x1);

nbiterations=1;
while (errel > epsilon) & (nbiterations <N)
          x0=x1;
          x1=g(x0);
          e_n_1=e_n;
          e_n=abs(x1-x0);
          errel=e_n/abs(x1);
          nbiterations=nbiterations+1;
          x(nbiterations)=x1;
          disp(x);
end
end

My script

clear;close all;clc;

g1 = @(x) -0.25* (x^3 - 3*x^2  - 2);
x0 = 1.5;

epsilon = 1e-7;

N=50;

pointfixe(g1, x0, N, epsilon);

A part of the console imput to show you an example about what i mean by 5 significant numbers

Edit from this output how can i analyze if the number of significant numbers is 8, how can i judge which epsilon will give me 8 significant numbers

New edit

Answer 1

You are considering the functional iteration $$x_{n+1} = g(x_n)$$ where $$g(x) = \frac{1}{4}(x^3 - 3 x^2 - 2)$$ and $x_0 = \frac{3}{2}$. You seek to recover the fixed point $x=1$ with a relative error which is less than $\tau = 10^{-8}/2$. We begin by considering the interval $I = [\frac{1}{2}, \frac{3}{2}]$ which contains $x_0$ and is centered around $x=1$. We have $$g'(x) = \frac{1}{4} (3x^2 - 6x) = \frac{3}{4} x (x-2).$$ A short calculations show that $|g'(x)| \leq \frac{3}{4}$ for $x \in I$. This shows that convergence sets in immediately and that we may choose $L=\frac{3}{4}$. You can now deploy the bound suggested by @PierreCarre, i.e., $$ |x-x_n| \leq \frac{L}{1-L} |x_n - x_{n-1}| = \frac{\frac{3}{4}}{\frac{1}{4}}|x_n - x_{n-1}| = 3|x_n - x_{n-1}|.$$ Since the target value is $x=1$ this observation allows you to bound the relative error. You need to iterate until $|x_n-x_{n-1}| \leq \tau$. As @PierreCarre correctly points out this analysis hinges on the choice of the function $g$.

Algorithms which attempts to detect convergence by monitoring $x_n - x_{n-1}$ can always be defeated by a sufficiently complicated function. Detail are presented in this answer to a question related to the termination of Newton's method.

Answer 2

Keep in mind that no criteria will be independent of the particular function $g$. When you estimate the error by computing the difference between consecutive iterates (the abs(x1-x0) in your code), this is not an actual upper bound. What you can prove from the fixed point theorem (if the conditions hold) is that

$$ \underbrace{|x_n - z|}_{\textrm{error}}\leq \frac{L}{1-L} |x_n - x_{n-1}|. $$

So you see that the difference $|x_n-x_{n-1}|$ is only an upper bound for the error if $L$ (the contractivity constant) is $\leq \frac 12$.

For instance, if $L=0.99$, you have that $L/(1-L) = 99$, so the actual error can be two orders of magnitude larger than the difference $|x_n-x_{n-1}|$.

That being said, since you are able to "sort of" estimate the error in each iteration, if you want to get $d$ significant digits, just iterate until the relative error is less than $0.5 \times 10^{-d}$.

note: Depending on the authors, the number of significant digits can be defined in terms of the relative error (I think this is more useful) or the absolute error.