3

enter image description here

This is the matrix that is used to find the square root of a number (M). p and q is an estimate of the root of M in a fraction form (5=10/2 or 5/1) and a and b is a new fraction of a closer approximate of M. Repeating this improve accuracy where the a and b of the previous iteration are the new p and q (a=p and b=q).

What I am asking is how does this method work? Any guidance as to finding how this method work will be appreciated, and if any further information is required, just let me know. My teacher suggests that deep algebraic equations are not necessary, but if they are required, I will try my best to understand and interpret them.

Brayden
  • 31
  • Hint: decompose the matrix in its Eigenvalue/Eigenvector representation and observe what goes on when you iterate. –  May 12 '14 at 06:52

1 Answers1

3

From the matrix, we have the simultaneous equations: $p+Mq=a$ and $p+q=b$.

Then we have the iterations $\frac{p'}{q'}=\frac{p+Mq}{p+q}$, and assume that $\frac{p}{q}$ converges, then $\frac{p}{q}=\frac{p'}{q'}=\frac{p+Mq}{p+q}\Rightarrow p(p+q)=q(p+Mq)\Rightarrow p^2=Mq^2$, which implies $\frac{p}{q}=\sqrt{M}$.

Since the iterations (of $\frac{p}{q}$) is bounded by $\frac{a}{b}$ and $\sqrt{M}$, and it is strictly increasing (/decreasing) depending on the values of $a$ and $b$ you choosed. By the monotone convergence theorem, then the sequence is convergent.

Samuel Tang
  • 31
  • 1
  • So, how does converging work since I've never heard of it? – Brayden May 13 '14 at 06:11
  • A sequence is called convergent if when the iteration gets farther, then it is more or less fixed. For example, $\frac{1}{2^n}$ is convergent to 0 as $n$ tends to infinity. Try to imagine that an increasing sequence with a upper bound is convergent, as the greatest possible value the sequence could attain is actually the bound. If not, the upper bound could be lowered to restrict the sequence. – Samuel Tang May 15 '14 at 15:50