3
$\begingroup$

I'm asked to find if the fixed-point iteration

$$x_{k+1} = g(x_k)$$

converges for the fixed points of the function $$g(x) = x^2 + \frac{3}{16}$$ which I found to be $\frac{1}{4}$ and $\frac{3}{4}$.

In this short video by Wen Shen,

https://www.youtube.com/watch?v=3_PKDDnxgCo

it's explained how to find these fixed-points and to see if a fixed-point iteration converges. My doubt is related to find if a fixed point iteration converges for a certain fixed point.

At more or less half of the video, she comes up with the following relation for the error

$$e_{k+1} = |g'(\alpha)| e_k$$

where $\alpha \in (x_k, r)$, by the mean value theorem, and because $g$ is continuous and differentiable.

If $|g'(\alpha)| < 1$, then the fixed-point iteration converges.

I think I agree with this last statement, but when she tries to see if the fixed point iteration converges for a certain root of a certain function, she simply finds the derivative of that function and plugs in it the root.

I don't understand why this is equivalent to $$e_{k+1} = |g'(\alpha)| e_k$$

Can someone fire up some light on my brain? (lol, can I say this?)

$\endgroup$
  • $\begingroup$ $g(1/4) = (1/16) + (3/16) = 1/4$, so although $1/4$ is a fixed-point of $g$, it is not a root of $g$. The roots of $g$ are $\pm \frac{\sqrt{3}}{4}\mathbf{i}.$ $\endgroup$ – John Hughes Apr 8 '16 at 14:52
  • $\begingroup$ @JohnHughes Yes, I wrote roots but I meant "for the fixed points of $g$"...I modified by question. $\endgroup$ – nbro Apr 8 '16 at 14:55
  • $\begingroup$ One "sheds light on a problem", is the closest I can come to "fire up some light on my brain". $\endgroup$ – Patrick Stevens Apr 8 '16 at 15:05
2
$\begingroup$

We can do this in a different way using the Contraction Mapping Theorem.

$$d(g(x), g(y)) = d(x^2, y^2) = d(x, y) \times |x+y|$$ so if we can ensure that there is $r$ such that $|x + y| \leq r < 1$, and if we can ensure that $g$ applied to $[-r, r]$ produces a set which lies within $[-r, r]$, then in fact $g$ is a contraction mapping on $[-r, r]$.

Therefore, as long as there's a fixed point of $g$ inside $[-r, r]$ with $0 < r < \frac{1}{2}$, the iteration will converge when started anywhere in $[-r, r]$ to that (necessarily unique) fixed point. (Indeed, $g$ restricts to a function $[-r, r] \to [-r, r]$ if $\frac{1}{4}$ lies in the interval.)

So starting the iteration off from any $x \in (-\frac{1}{2}, \frac{1}{2})$ will produce something which converges to $\frac{1}{4}$. (We say nothing about how the iteration behaves from other starting points.)

$\endgroup$
2
$\begingroup$

The point behind the derivative is that locally a function looks linear and the derivative is the multiplier. Symbolically: $$f(x) \approx f(x_0) + f'(x_0)(x-x_0)$$ for $x$ near $x_0$. The statement "looks like" can be made more precise with the Mean Value Theorem.

Now, try iterating a function of the form $g(x) = a + m(x-a)$. You'll find that it converges to its fixed point of $x=a$ when $|m|<1$.

We can prove this since $$|g(x)-a| = |a+m(x-a) - a| = |m|\cdot |x-a|$$ so that $$|g^n(x)-a| = |m|^n |x-a|.$$

This is why we say the fixed point $x_0$ is attractive if $|f'(x_0)|<1$ and repulsive if $|f'(x_0)|>1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.