How to choose a sensible tolerance equivalent to 10 significant digits.

By using a function called FixedPoint to compute 10 iterations for g(x) and h(x).

function [x, flag] = FixedPoint(g, x0, tol, nmax)
x(1) = x0; flag = 1;
for n = 1:nmax
  x(n+1) = g(x(n));
  if ( abs(x(n+1)-x(n)) <= tol*max(abs(x(n)), abs(x(n+1))))
flag = 0;
break end
end
x = x(:);

g = @(x) 1/(x^2 - 1);
[x, flag] = FixedPoint(g, 1.5, 1e-10, 10)

h = @(x) 1 + x/(x^2 + x + 1);
[x, flag] = FixedPoint(h, 1.5, 1e-10, 10)

I'm confused of what number to choose for tolerance to give 10 significant digits. I tried 1e-10.

[John D'Errico]

See how when I edited your post to make the code readable, how much it helps?

Please, when you post code like this, all you need do is select it, then click on the "{} Code} button.

[John D'Errico]

Also, you will find it necessary to use the ./, .*, and .^ operators much of the time. I would strongly suggest learning how to use them, when, and why.

These operators are used whenever you will do element-wise operations on a matrix or vector.

g = @(x) 1./(x.^2 - 1);
h = @(x) 1 + x./(x.^2 + x + 1);

Answer 1

[John D'Errico]

So you want 10 SIGNIFICANT digits. Wanting to meet a tolerance is good.

But what happens if the algorithm has not converged in 10 iterations? After all, you specified nmax=10 iterations. What happens if the algorithm is divergent for some set of starting values, or even for all starting values?

Under those conditions, can you rationally expect the tolerance to necessarily be met?

Essentially this fixed point iteration requires two things for that tolerance to have a chance.

1. It must be convergent.
2. Even if it is convergent, it must have converged by the iteration limit you have posed, and 10 iterations is not a big number here.

So think about these issues. Then look at the actual sequence the fixed point scheme took. Think about what you see. Did the function g converge? Should it have converged in that number of iterations? Why did it do what it did? I assume you have learned the circumstances that will allow a fixed point scheme like this to converge. Have they been met for g?

Then look at the iterations taken for h. What is different about h and g in the vicinity of the starting point?

When in doubt (and even when no doubt exists) follow John's rule: PLOT EVERYTHING. Then think about what you see.

ezplot(g),hold on, ezplot(@(x) x)
axis equal

ezplot(h),hold on, ezplot(@(x) x)
axis equal

[XIN JIN]

g(x) diverges and h(x) converges. Still don't know how to get 10 s.d.. 10 iterations and 1.5 as starting point are stated in the question, so I used them.

[XIN JIN]

After seeing the graph, I still can't see what tolerance to choose to give 10 significant digits.

[John D'Errico]

I don't think you seriously read what I said above, even though you seem to recognize that g is not convergent here.

Ok, for the function h, did it converge to the desired tolerance, in roughly 9 iterations? Did the function h show a nice smooth convergence to the desired solution? What property does the function h have in that region? (Hint: what is the derivative of h near the solution? If necessary, plot it!)

How about g? LOOK at what comes out for g.

[x, flag] = FixedPoint(g, 1.5, 1e-10, 10)
x =
                       1.5
                       0.8
         -2.77777777777778
         0.148897058823529
         -1.02267300215983
          21.8054620118945
       0.00210757850569503
         -1.00000444190689
          112564.018591266
      7.89224977794335e-11
                        -1

flag =
     1

Is the iteration converging for g? What property does g have in that vicinity? (Again, think about the derivative of g.)

syms x
gprime = diff(1/(x^2 - 1))
subs(gprime,1.5)
ans =
-48/25

The test that matters here is...

abs(-48/25) > 1
ans =
     1

Why must any tolerance exist at all that will give you what you want for g? Maybe the Rolling Stones may have been singing about the function g when they sang: "You can't always get what you want..."

(I'll check back in later, but what you need to consider is whether any tolerance at all has a meaning on a divergent sequence.)

[XIN JIN]

g'(x)=-2x/((x^2-1)^2),g'(x)<0, so it diverges. Any tolerance won't have an effect on g? After running what I wrote for g, i got

[John D'Errico]

Ok, so do you think that has converged? I think you miss the scientific notation there - that tiny little factor of 1e5 in front of the vector, multiplying every element. Using a large font does not prove anything, only that you need to think about what it is that is happening.

Perhaps you need to do some reading about the format used to display numbers.

help format

NO TOLERANCE WILL MAKE A DIVERGENT SEQUENCE CONVERGE. PERIOD. How many times can I say this?

Changing the tolerance has NO impact on the sequence. Only when the iterations stop.

The sequence for g is divergent. It generates what is essentially arbitrary numerical garbage, a sequence of values that are not convergent to the solution.

As for your statement about g'(x) being negative, that does NOT make it diverge.

The important factor for convergence is that abs(g'(x)) must not exceed 1 in that region.

I think you need to do some reading about fixed point iteration, convergence of that scheme, and about the format command in MATLAB.