Some questions about variations of fixed point method

Question

I'm doing some excercises in Fixed Point Iteration methods with Matlab. I have to find roots for $f(x)=e^x -x -1.9\cos x$ by using $x_{n+1}=g(x_n)$. I know how to choose $g(x)$ such that I can find both roots. The following part of the exercise is as follows:

In general we can rewrite $f(x)=0$ to $x=g(x)$ with $g(x)=x+cf(x)$, where $c\neq 0$ is a constant.

I am given the function $f(x)=e^x-x-1.9\cos x$ , and I have to determine values for $x_0$ and $c$ such that the sequences obtained for $x_{n+1}=g(x_n)$ both converge quickly, to roots $x_{r1}$ and $x_{r_2}$.

I'm told that this can be obtained by picking a point $x_0$ close to the zero and setting $g'(x_0)=0$ by an appropriate choice of $c$. My question is, what is this all about? What should I do?

Then, another part says

Increase the order of convergence of the fixed point method $x_{n+1}=x_n+cf(x_n)$ by changing $c$ each iteration instead of using a constant value.

How can I do that? What do they mean?

Answer 1

A central tenet in calculus is that we can understand the local behavior of a function near a point by examining the linear approximation of the function at that point. Thus, let's begin by exploring the behavior of iteration near fixed points of linear functions.

To this end, consider the function $\ell(x) = x_f + m(x-x_f)$. This clearly has a fixed point at $x_f$. Now, suppose that we iterate this function starting from some point $x_0$. Note that $$\ell(\ell(x_0)) = x_f + m((x_f + m(x_0-x_f)) - x_f) = x_f + m^2 (x_0 - x_f).$$

More generally, $$\ell^p(x_0) = x_f + m^p (x_0 - x_f).$$

As a result, we see quite easily that the orbit of $x_0$ tends towards $x_f$ iff $|m|<1$. Furthermore, the smaller the value of $m$, the faster the convergence. The convergence is fastest (instantaneous, in fact) when $m=0$.

Now, let's consider the iteration of a differentiable function $g$ near a fixed point $x_f$, thus $g(x_f)=x_f$. Suppose we iterate $g$ starting from some point $x_0$ near $x_f$. By analogy with the linear example we just examined, we might expect $x_f$ to be attractive if the slope of $g$ is less than $1$ in absolute value at the point $x_f$. More precisely, we need $|g'(x_f)|<1$.

Now, in your example, you have a given function $f(x)=e^x-x-1.9\cos(x)$ and you'll generate $g_c$ by setting $g_c(x)=x+c\,f(x)$. Since you have a computational tool in your hands, I suggest that you examine the graph of $g_c$ together with the graph of $y=x$ to help you choose a good value of $c$. For example, here's the graph of $y=g_{-1/2}(x)$ together with the graph of $y=x$.

The points of intersection correspond to the roots of $f$. It appears that one such point is around $0.7$ or so and that iteration of $g_{-1/2}$ starting near there should converge to that fixed point. It does appear, though, that you could pick a value of $c$ that is better than $-1/2$. Note that it is important to plot the graph in it's correct aspect ratio to get a good feel for the magnitude of the derivative.

Finally, if you start with a good $c$ value, then refinement should not be necessary. I guess the idea, though, is choose $c$ at the $i^{\text{th}}$ step so that $g_c'(x_i)=0$. Since $x_i$ is close to $x_f$, we'd then expect $g_c'(x_f)$ to be close to zero.