Waste less time on Facebook — follow Brilliant.
×

Square Root Algorithm

Fix a number \(\alpha \in \mathbb{R}^+\). Choose \(x_1 > \sqrt{\alpha}\) and define:

\(x_{n+1} = \frac{1}{2}(x_n +\frac{\alpha}{x_n})\)

We will prove that the sequence of all \(x_n\):

(1) Is bounded below

(2)\(\displaystyle \lim_{n \to \infty} x_n = \sqrt{\alpha}\)

(3) Is monotone decreasing

Proof:

(1) We will show that \(x_n > \sqrt{\alpha}\) \(\forall\) \(n \in \mathbb{N}\).

Using induction, we establish a base case as \(n=1\), which is trivial as this is given:

\(x_1 > \sqrt{\alpha}\)

Now, suppose the statement is true for \(n= k-1\):

\(x_{k-1} > \sqrt{\alpha}\)

\(\Rightarrow\) \(x_{k-1} - \sqrt{\alpha} > 0\)

\(\Rightarrow\) \((x_{k-1} - \sqrt{\alpha})^2 > 0\)

\(\Rightarrow\) \(x_{k-1}^2 -2\sqrt{\alpha}x_{k-1} + \alpha > 0\)

\(\Rightarrow\) \(x_{k-1}^2 + \alpha > 2\sqrt{\alpha}x_{k-1}\)

\(\Rightarrow\) \(x_{k-1} +\frac{\alpha}{x_{k-1}} > 2\sqrt{\alpha}\)

\(\Rightarrow\) \(\frac{1}{2} (x_{k-1} + \frac{\alpha}{x_{k-1}}) > \sqrt{\alpha}\)

\(\Rightarrow\) \(x_k > \sqrt{\alpha}\)

Then we may conclude that the statement is true for \(n=1\) and if it is true for some \(n=k-1\) then it is true for \(n=k\). The proof follows by induction.

This proves (1).

(2) Proceeding to take the limit:

\(\displaystyle \lim_{n \to \infty} x_{n+1} = \displaystyle \lim_{n \to \infty} \frac{1}{2}(x_n + \frac{\alpha}{x_n})\)

Now, if this limit exists then it must be true that:

\(\displaystyle \lim_{n \to \infty} x_n = \displaystyle \lim_{n \to \infty} x_{n+1}\)

Let this limit be represented as \(L\). Then we have:

\(L = \frac{1}{2}(L+ \frac{\alpha}{L})\)

\(\Rightarrow\) \(2L^2 = L^2 + \alpha\)

\(\Rightarrow\) \(L = \sqrt{\alpha}\)

Then the sequence is bounded below with \(\displaystyle \lim_{n \to \infty} x_n =\sqrt{\alpha}\)

This proves (2).

(3) Using induction, we establish a base case as \(n=1\):

\(\Rightarrow\) \(x_1 > \frac{1}{2} (x_1 + \frac{\alpha}{x_1})\)

Now we need to actually prove this. Start with:

\(x_1 > \sqrt{\alpha}\)

\(\Rightarrow\) \(\frac{1}{2}x_1^2 > \frac{1}{2} \alpha\)

\(\Rightarrow\) \(x_1^2 - \frac{1}{2}x_1^2 > \frac{1}{2} \alpha\)

\(\Rightarrow\) \(x_1^2 > \frac{1}{2} (x_1^2 +\alpha)\)

\(\Rightarrow\) \(x_1>\frac{1}{2}(x_1 +\frac{\alpha}{x_1})\)

\(\Rightarrow\) \(x_1>x_2\)

The base case clearly holds. Now the inductive case \(n=k\):

In (1) we proved that \(x_n > \sqrt{\alpha}\) \(\forall\) \(n \in \mathbb{N}\). Begin with:

\(x_k > \sqrt{\alpha}\)

\(\Rightarrow\) \(\frac{1}{2} x_k^2 > \frac{\alpha}{2}\)

\(\Rightarrow\) \( x_k^2 > \frac{1}{2}x_k^2 + \frac{\alpha}{2}\)

\(\Rightarrow\) \(x_k > \frac{1}{2}(x_k + \frac{\alpha}{x_k})\)

\(\Rightarrow\) \(x_k > x_{k+1}\)

The proof again follows by induction. This proves (3).

We have shown that the sequence is monotone decreasing and bounded below with a limit at infinity that exists. It follows that the sequence converges.

QED

Note the utility of this sequence. If we let alpha equal any real number, we now have an algorithm that will approximate the square root of alpha, with accuracy increasing as \(n\) increases. The proof above is my own, but the sequence itself is not original. I thought this was interesting.

Note by Ethan Robinett
2 years, 5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

To prove (2), you made the assumption that the limit exists. It is not necessarily valid to assume that the limit exists, and then show that the limit is a certain value.

You can actually show that the limit exists using (1) and (3). Note that (3) doesn't use (2). That is often the approach taken for this question. Calvin Lin Staff · 2 years, 5 months ago

Log in to reply

@Calvin Lin I was thinking about this. I read that in order to show that a sequence converges, if it is monotone decreasing, then you must show that it is bounded below, which was done above without (2). So I'm not sure if (2) really needs to be in the proof at all. However, we could have just as easily shown that the sequence is bounded by zero, but the sequence clearly doesn't converge to zero. If (1) and (3) can be used to show that the limit exists, then would (2) be more appropriately placed at the end? Ethan Robinett · 2 years, 5 months ago

Log in to reply

@Ethan Robinett The standard approach is to

  • Show that the sequence is monotonically decreasing.
  • Show that the sequence is bounded below.
  • Hence conclude that the limit exists.
  • Then conclude that the limit is \( \sqrt{\alpha} \).

The order of the first 2 steps is interchangeable.
Note that bounded below follows directly from AM-GM. Calvin Lin Staff · 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...