Why does the fixed point method rely on the derivative of the root for convergence or divergence?

659 Views Asked by At

I'm currently studying the fixed point iterative method, and I am confused as to how the derivative of g(x) at a point between a guess and a root can tell us if the method will converge or diverge for this point. For example, for

$f(x) = e^x - 10x = 0$,

$x = g(x)$, where $g(x) = (1/10)e^x$.

When you rearrange it with the root solutions, you will get

$x_{i+1} − x_{r} = {\dfrac{dg}{dx}}(ξ) (x_{i} − x_{r})$,

where $x_{i+1}$ and $x_{i}$ are the guesses of the root, $x_{r}$ is the root, and the mean value theorem is used, with $ξ$ being a value inbetween $x_{i}$ and $x_{r}$.

I understand mathematically, the ${\dfrac{dg}{dx}}(ξ)$ term has to be below 1 for convergence to occur, but I do not understand the intuition behind it.

Does this mean the fixed point method only works for roots where the derivative near a point is relatively flat?

1

There are 1 best solutions below

0
On

A visual interpretation of the derivative is that we graph the function on the $xy$-plane, then "zoom in" near one point until the curve looks almost like a straight line. The derivative is the slope of this line which the curve looks like. So for simpler intuition, what happens if a piece of the function's graph actually is a straight line segment?

Suppose $g(x) = mx+b$, with $m \neq 1$. The unique point where $g(x)=x$ is $x_r = \frac{b}{1-m}$.

But if we ignore the simple algebraic solution and just try iteration from some guess, we'll have some sequence $(x_i)$ where $x_{i+1} = g(x_i)$. Is this sequence converging to, or getting farther from, the value $x_r$?

$$ \begin{align*} x_{i+1} - x_r &= g(x_i) - x_r \\ &= mx_i + b - x_r \\ &= m(x_i - x_r) + m x_r + b - x_r \\ &= m(x_i - x_r) + (m-1) x_r + b \\ x_{i+1} - x_r &= m(x_i - x_r) \end{align*} $$

So the absolute value of the error in the sequence decreases if $|m|<1$, or increases if $|m|>1$.

Intuitively then, once the sequence is "close enough" to the correct point that the derivative is a "good enough" description of the overall behavior of the iterative algorithm, it will converge if $|g'(x_r)| < 1$, since the derivative approximates a linear slope in a neighborhood of the point. If $|g'(x_r)| > 1$, the sequence can't converge unless it happens to land on $x_N = x_r$ exactly, since for a point $x$ close to $x_r$, the iteration will send the next point farther from $x_r$. If the derivative doesn't exist, or if $g'(x_r) = \pm 1$, we need to look for other means of analyzing things.

Getting away from intuition to precise statements, using the mean value theorem's value $\xi$ is part of a way of proving something general about actual values which aren't "arbitrarily close to $x_r$" (since no such values really exist in ordinary real analysis).