Calculating Square Roots - Matrix Algorithm


by danago
Tags: algorithm, matrix, roots, square
danago
danago is offline
#1
Feb23-07, 11:39 PM
PF Gold
P: 1,132
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.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Integral
Integral is offline
#2
Feb24-07, 12:02 AM
Mentor
Integral's Avatar
P: 7,292
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.
danago
danago is offline
#3
Feb24-07, 12:09 AM
PF Gold
P: 1,132
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 :)

tim_lou
tim_lou is offline
#4
Feb24-07, 01:40 AM
P: 689

Calculating Square Roots - Matrix Algorithm


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.
danago
danago is offline
#5
Feb24-07, 02:19 AM
PF Gold
P: 1,132
Quote Quote by tim_lou View Post
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'?
danago
danago is offline
#6
Feb24-07, 02:26 AM
PF Gold
P: 1,132
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
tim_lou
tim_lou is offline
#7
Feb24-07, 11:31 AM
P: 689
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....
Hurkyl
Hurkyl is offline
#8
Feb24-07, 02:56 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
The analysis is a lot easier in the case of multiplying by a matrix.

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]


Register to reply

Related Discussions
Derivatives of square roots Calculus 11
square roots and fractions Precalculus Mathematics Homework 7
Square roots Introductory Physics Homework 7
square roots Brain Teasers 12
Square Roots General Math 6