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

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?
• "Average damping" is in fact equivalent to Newton's method applied to the problem $x^2 = A$, and therefore gives the best convergence.
– user856
Apr 30, 2019 at 9:48

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.

• Thanks, I just corrected it. Jan 22, 2020 at 17:55

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$$.

• Thank you Professor for your answer. I see that this is a somewhat beyond my current capabilities as I don't have the knowledge yet to fully understand. I appreciate your answer and I hope I can come to it one day with improved skills. Cheers!
– BMBM
May 2, 2019 at 21:08