Significance of (average) damping in fixed point iteration for square roots

Question

Fixed point iteration means that we apply a function $f$ repeatedly to itself and see if we can find an $x_n$ such that $f(x_n) = x_n$ or is at least close enough.

Let's say we want to use fixed point iteration to find the square root of some number $A$. We know we are looking for an $x$ such that $x^2 = A$ or equivalently $x = \frac{A}{x}$.

Then define our function to be:

$$f(x) = \frac{A}{x}$$

Let $A=2$, to find the square root of 2. Start with an initial guess of $x_0=1$. Then:

$$f(x_0)=\frac{2}{1}=2$$

And we continue to use $x_1=2$, again applying the function:

$$f(x_1)=\frac{2}{2}=1$$

And we are back at $x_2=1$ again. So the fixed point iteration will be stuck in a loop, oscillating around the number we want to find.

Now I read if we modify $f(x)$ and add $x$ on both sides we get:

$$f(x) = \frac{1}{2}(\frac{A}{x} + x)$$

Using this function, we will converge. This technique is called average damping.

What I wonder:

• Is there any special reason why we actually want to take the average of $x$ and $\frac{A}{x}$? I also tried to add $2x$ on both sides and ended up with $f(x)=\frac{1}{3}(\frac{A}{x}+2x)$ which also converges, but slower.
• Why does changing the function to return the average actually make sure that the oscillation is stopped and the iteration gets "unstuck"? I mean, I can't see a reason why just taking the average actually results in the correct answer at all. What's the reason this damping makes the function converge?

Answer 1

The equation $x=f(x)$ is equivalent to $x=(1-\alpha)f(x)+\alpha\,x\equiv g_\alpha(x)$ for any $\alpha\in\Bbb R$. If $\bar x$ is the solution, we try to choose $\alpha$ such that $|g_\alpha'(\bar x)|$ is as small as possible. In general, this needs some knowledge about $\bar x$.

When $f(x)=A/x$, $\bar x=\sqrt A$ and $$ g_\alpha'(\bar x)=-(1-\alpha)\frac{A}{A}+\alpha=-1+2\,\alpha. $$ $|g_\alpha'(\bar x)|$is minimum when $\alpha=1/2$.

Answer 2

I am adding this answer just to break down the explanation of the accepted answer a little bit more, since apparently the person asking it in the first place could not follow it entirely.

What @Julián Aguirre showed is that the damped fixed point method consists in constructing a different function of the unknown $g(x)$ that, by construction, has the same fixed point (solution) as the original function $f(x)$.

The particular way in which one constructs the function is, as stated above, like this:

$g(x) = (1-\alpha)f(x) + \alpha x $

with $\alpha$ a real number. This definition suggests using the name $g_{\alpha}$ instead of $g$, so that the particular value of $\alpha$ chosen identifies the function you are using.

But, why would you prefer function $g_{\alpha}$ to the original $f(x)$? Well @Julián Aguirre also showed that you can pick the value $\alpha$ to produce a function that has a minimal rate of variation around the solution (i.e., $|g_{\alpha}(\bar{x})'|$ is minimal among all the functions defined like above). Note that, in particular, the rate of variation of $g_{\alpha}$ is smaller than that of $f$ around $\bar{x}$, since $f = g_0$ (for $\alpha = 0$ you recover $f$).

And why is having minimal rate of change an advantage? Well, suppose you are given an initial guess for $\bar{x}$, $x_0$, that is not too far from the correct value, say $x_0 = \bar{x} + \epsilon$.

Then, applying the fixed point iteration you will get $x_1 = g_{\alpha}(\bar{x} + \epsilon) \approx g_{\alpha}(\bar{x}) + g_{\alpha}'(\bar{x})\epsilon = \bar{x} + g_{\alpha}'(\bar{x})\epsilon $

Where I am using the first-order Taylor series in the approximation above. Note that the smaller $|g_{\alpha}'(\bar{x})|$, the smaller the error in $|\bar{x} - x_1| \approx |g_{\alpha}'(\bar{x})\epsilon|$, making it obvious why you would want this rate to be small around the solution.