• Support PF! Buy your school textbooks, materials and every day products Here!

Calculating Square Roots - Matrix Algorithm

  • Thread starter danago
  • Start date
  • #1
danago
Gold Member
1,122
4
Hi. I only just recently found out about an algorithm for calculating the square roots of a number.

Lets say i want to evaluate [tex]\sqrt {n}[/tex]. I can make an approximation by inspection, and say [tex]\sqrt n \approx \frac{a}{b}[/tex]. Now, using this approximation, i can write:

[tex]
\left[ {\begin{array}{*{20}c}
1 & n \\
1 & 1 \\
\end{array}} \right]\left[ {\begin{array}{*{20}c}
a \\
b \\
\end{array}} \right] = \left[ {\begin{array}{*{20}c}
{a + bn} \\
{a + b} \\
\end{array}} \right]
[/tex]

Treating the resultant matrix as a fraction ([tex]
\frac{{a + bn}}{{a + b}}
[/tex]
), i have a better approximation of [tex]\sqrt {n}[/tex]. If i keep repeating this method with the new approximation, over and over again, i get a more accurate answer. So the next step would be:

[tex]
\left[ {\begin{array}{*{20}c}
1 & n \\
1 & 1 \\
\end{array}} \right]\left[ {\begin{array}{*{20}c}
{a + bn} \\
{a + b} \\
\end{array}} \right] = \left[ {\begin{array}{*{20}c}
{a + an + 2bn} \\
{2a + b + bn} \\
\end{array}} \right]
[/tex]

And [tex]
\frac{{a + an + 2bn}}{{2a + b + bn}}[/tex] would be an even better approximation to [tex]\sqrt {n}[/tex].

Even if the starting approximation is way off, if alot of iterations are complete, the answer will still be accurate.


Im just wondering, why does this method work? Is there a name for this method, or anywhere i can look to find more information?

Thanks,
Dan.
 

Answers and Replies

  • #2
Integral
Staff Emeritus
Science Advisor
Gold Member
7,198
55
That sure seems like a complex method.

A Newton's method root finder yields a very simple iterative method:

[tex] x_{n+1} = \frac 1 2 (x_n + \frac A {x_n}) [/tex]

So A is the number you are computing the root of and [itex] x_0 [/itex] is your inital guess, it doesn't have to be very good. Compute [itex] x_1 [/itex] with the formula, continue.

This procedure converges quadratically.
 
  • #3
danago
Gold Member
1,122
4
Hmm that method does seem good. Im still interested in the matrix method though. Im not interested in it as a way to actually calculate square roots, but as a mathematical phenomenon. Just curious as to why it works.

Ofcouse im still always going to resort to my calculator to evaluate them :)
 
  • #4
682
1
well, you are essentially taking an initial value of x, and then iterate through
[tex]x_{i+1}=\frac{x_{i}+n}{x_{i}+1}[/tex]
so, let
[tex]f(x)=\frac{x+n}{x+1}[/tex]
the fix point of f
[tex]f(x)=x[/tex]
is sqrt(n)

you can check derivatives and find out when this fix point is asymptotically stable.
 
  • #5
danago
Gold Member
1,122
4
well, you are essentially taking an initial value of x, and then iterate through
[tex]x_{i+1}=\frac{x_{i}+n}{x_{i}+1}[/tex]
so, let
[tex]f(x)=\frac{x+n}{x+1}[/tex]
the fix point of f
[tex]f(x)=x[/tex]
is sqrt(n)

you can check derivatives and find out when this fix point is asymptotically stable.
Yep, i understand that i am essentially iterating through [tex]x_{i+1}=\frac{x_{i}+n}{x_{i}+1}[/tex], but what do you mean when you say 'fix point'?
 
  • #6
danago
Gold Member
1,122
4
Just researched it on wikipedia, and now understand what a fixed point is.

[tex]
\begin{array}{l}
f(x) = \frac{{x + n}}{{x + 1}} \\
\frac{{x + n}}{{x + 1}} = x \\
x^2 + x = x + n \\
x^2 = n \\
x = \sqrt n \\
\end{array}
[/tex]

That pretty much exactly answers my question. Thanks very much for that
 
  • #7
682
1
hehe, if you want to dig deep. Do you know why this works for All n?

well, the reason, is, the absolute value of f'(x) at the fixed point is less than 1 for all n except n=0. there is a theorem that says (from my difference equation book)

if x* is a fix point for f and f is continuously differentiable at x* then
(1) if |f'(x*)| < 1, then x* is asymptotically stable.
(2) if |f'(x*)| > 1, then x* is unstable.

so that in your case, x* is asymptotically stable.

what if |f'(x*)|=0? then you need to do a lot more tests... if you want to know more. go to the library and pick up a difference equation book....
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
18
The analysis is a lot easier in the case of multiplying by a matrix. :smile:

The eigenvalues of the matrix

[tex]
\left[ {\begin{array}{*{20}c}
1 & n \\
1 & 1 \\
\end{array}} \right]
[/tex]

are

[tex]1 \pm \frac{\sqrt{n}}{2}[/tex]

If you take (almost) any vector and repeatedly multiply by the matrix A, the result will approach the eigenspace associated to the largest eigenvalue in magnitude. Here, that's [itex]1 + \sqrt{n} / 2[/itex].


Given the rest of the discussion, I expect that the eigenspace associated to the eigenvalue [itex]1 + \sqrt{n} / 2[/itex] is the set of all:

[tex]
a
\left[ {\begin{array}{c}
\sqrt{n} \\ 1
\end{array}} \right]
[/tex]

In fact, I would go so far as to expect A to factor as:

[tex]

\left[ {\begin{array}{cc}
1 & n \\
1 & 1 \\
\end{array}} \right]
=
\left[ {\begin{array}{cc}
\sqrt{n} & -\sqrt{n} \\
1 & 1 \\
\end{array}} \right]
\left[ {\begin{array}{cc}
1 + \frac{\sqrt{n}}{2} & 0 \\
0 & 1 - \frac{\sqrt{n}}{2} \\
\end{array}} \right]

\left[ {\begin{array}{cc}
\sqrt{n} & -\sqrt{n} \\
1 & 1 \\
\end{array}} \right]^{-1}

[/tex]
 
Last edited:

Related Threads on Calculating Square Roots - Matrix Algorithm

Replies
11
Views
3K
Replies
28
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
4
Views
331
  • Last Post
Replies
17
Views
4K
  • Last Post
Replies
20
Views
4K
Replies
4
Views
658
Replies
4
Views
3K
  • Last Post
Replies
4
Views
11K
Top