Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Calculating Square Roots - Matrix Algorithm

  1. Feb 23, 2007 #1

    danago

    User Avatar
    Gold Member

    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.
     
  2. jcsd
  3. Feb 24, 2007 #2

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. Feb 24, 2007 #3

    danago

    User Avatar
    Gold Member

    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 :)
     
  5. Feb 24, 2007 #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.
     
  6. Feb 24, 2007 #5

    danago

    User Avatar
    Gold Member

    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'?
     
  7. Feb 24, 2007 #6

    danago

    User Avatar
    Gold Member

    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
     
  8. Feb 24, 2007 #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....
     
  9. Feb 24, 2007 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Feb 24, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Calculating Square Roots - Matrix Algorithm
  1. Square Roots (Replies: 5)

Loading...