Calculating Square Roots - Matrix Algorithm

In summary, the conversation discusses two methods for calculating square roots: the matrix method and Newton's method. The matrix method involves iterating through a formula to get a more accurate approximation, while Newton's method is a simpler iterative method. The matrix method works because of the concept of fixed points and the stability of the function. The matrix used in the method has eigenvalues that can help determine the accuracy of the approximation.
  • #1

danago

Gold Member
1,123
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 a lot 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.
 
Physics news on Phys.org
  • #2
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
Hmm that method does seem good. I am still interested in the matrix method though. I am 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 I am still always going to resort to my calculator to evaluate them :)
 
  • #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.
 
  • #5
tim_lou said:
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
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
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
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:

1. How does the matrix algorithm work for calculating square roots?

The matrix algorithm works by creating a matrix that represents the number we want to find the square root of. This matrix is then manipulated using specific operations until it converges to the square root of the original number.

2. What is the advantage of using the matrix algorithm compared to traditional methods?

The matrix algorithm is advantageous because it is more efficient and faster than traditional methods such as the Babylonian method. It also has a higher accuracy and can handle larger numbers without losing precision.

3. Can the matrix algorithm be used for all numbers?

No, the matrix algorithm can only be used for positive numbers. It also has limitations for numbers with large decimal places, as it may not converge to the exact square root.

4. How do I know when the matrix algorithm has converged to the square root?

The matrix algorithm will continue to iterate until the elements in the matrix stop changing significantly. This indicates that the matrix has converged to the square root. However, it is important to check the accuracy of the result by squaring it and comparing to the original number.

5. Are there any alternative algorithms for calculating square roots?

Yes, there are various other algorithms for calculating square roots such as the Babylonian method, Newton's method, and the continued fractions method. Each algorithm has its own advantages and limitations, and the choice of which one to use may depend on the specific problem at hand.

Back
Top