In the last video we know three interesting methods to calculate square
roots. We are going to explain why these methods work. Firstly we have long
division. We use square root of 42 as an example. In the first step we write down
the number whose square is just less than 42, in this case 6, and perform
subtraction like you do in division. Since square root of 4200 is equal to 10
times square root of 42, we can move the decimal point one slice to the right
without affecting the quotient. Then we want to have sixty x squared just under
4200, and from the subtraction process we have 4200 minus 60 squared equals 600.
Doing expansion on the first expression, we have x times 120 x just under 4200
minus 60 squared, and the second expression tells us that it is 600, so we
have x times 120 x just under 600. This is exactly why in the next step we will
multiply 6 by 2 to get 12 and look for the numberx so that 120 x times x is
just under 600. This explanation can be generalized to every slice and every
square root. Secondly we have continued fraction. There are two bits we want to
explain: first, why does truncating at a finite layer gives approximates and
second, why does the multiplying and adding thing work. In case you forget the
multiplying and adding, this illustrates the process as taken from the previous video.
For the first bit we use square root of five as an example, which has the
continued fraction expression shown on screen. We denote everything in the
ellipsis by x then x has to be between 0 & 1. By letting x equals 0,we have the
fraction to be roughly 2.236, and by letting x equals 1, we have the fraction
to also be roughly 2.236. Since x is between 0 and 1, the real value of square
root of 5 must be between these two fractions. As you can see, these two
fractions are already very close to each other and in fact closer when we
truncate it at a lower layer. Therefore the sequence of truncated continued
fraction would get closer and closer to square root of 5. For the second bit, the
main thing we need to prove is this white boxed formula, and we would use
mathematical induction to prove it. If we want to prove a statement is true for
all natural number n, we first have to prove that when n reaches the smallest
possible value, the statement is true, also known as the base case; and whenever
the statement is true for n equals k, it is also true for n equals k plus 1, also
known as the inductive step. Then the statement will be true for all natural
number n. So for the base case it is n equals 2 because the statement does not
make sense if n is anything lower than 2. So we replace the statement by the case
when n equals 2. But before that we need to make sense of what p_0, q_0,
p_1 and q_1 are. So we proceed as shown.
Put these aside we now focus on p_2 over q_2 and write it in full. Now we want to
have a little algebra.
Now notice from the left, we have p_0 equals a_0, so we replace a_0
by p_0 here, then do the same for q_0, p_1 and q_1 respectively.
This is exactly what we want to prove! So we have successfully finished the base
case. For the inductive step, remember that we want to prove the case for n
equals k plus 1 based on the assumption that it is true when n equals k. Now like
what we did for the base case, write down the definition of p_(k+1) over q_(k+1),
which can be written like this. Rewrite the continued fraction in the
denominator as shown. This is for less ambiguity when we move on. We can write
this fraction to be a new p_k / q_k now since this is true for all K we can
decrease the subscripts for one and two to get these two relations.
Now based on this yellow box, which is assumed to be true, we can rewrite the
fraction here. Remember that b_k is actually a_(k+1), so we can do a
simple replacement here. By doing some algebra, we have this. Look at the white
boxes. We can again do some replacements in the denominator.
Similarly for another set of white boxes we can do replacements in the numerator,
which is exactly what we want to prove in the first place! With both base case
and inductive step done, we can prove that the formula is true for all n at
least two. I know that it is a lot to take in
especially the inductive step so pat yourself on the back if you can follow
so far. Rewatch the entire proof if you want. The third method is Babylonian
method. The basic idea is to improve the original guess by taking the average of
the previous value and a over the previous value, but why does it work?
Let's say the distance between a_0 and square root of a is less than some
error bound epsilon. Square the inequality then divided it by 2a_0 and we
claim that the boxed expression is a better estimate than a_0, so we write
it as a_1. Now look at these two error bounds. a_1 is a better approximate if
epsilon squared over 2 a naught is smaller than epsilon,which can be
rewritten as epsilon smaller than 2a_0, but what does that mean?
Substitute this back to the original error bound,and with some algebraic
manipulation, we have this inequality. Since square root of a is positive, it
must be greater than zero. Rearranging we have a_0 to be larger than one
third of its actual value. That means whenever a_0 is greater than square
root of a divided by three, the error between the iterations and square root
of a would get smaller, but what about when it is smaller than square root of a
divided by three but still positive? Remember what we have done. This boxed
expression tells us that a_0 squared plus a divided by two a_0
is actually larger than square root of a, so a_1 is then larger than square root of
a, which is of course larger than square root of a divided by three, so what does
that mean? Whenever a_0 is between zero and square root of a divided by
three, then a_1 would be greater than this threshold, and so the iterations
thereafter would get closer and closer to square root of a. If you don't
understand all these there is a way to visualize what is happening. Here is the
graph y equals x squared minus a and the positive x intercept is the square root
we want to approximate. We select a very large a_0, then construct a tangent
to the curve at x equals a_0 and the x-intercept of the tangent would be
a_1, and then we can construct another tangent at x equals a_1 and the
x-intercept of this tangent would be a_2. So we can visually see that the
iterations get closer and closer to square root of a. if a_0 is much
smaller than square root of a, then we similarly construct a tangent to the
curve at x equals a_0, and the x intercept of the tangent would be a_1
and we can carry on with what we have above.
If you know calculus here is a bit of detail why the iterations from the
visual process are the same as the one that we have been talking about. From the
definition of derivative at a point being slope of tangent, we have this
general formula. Some of you might recognize this as the Newton's method.
Since F of a_0 and f' of a_0 can be readily calculated, we
substitute it back to the Newton's method formula. With a bit of algebra we
can see that it is exactly the same iteration we have seen before. The next
video is about whether each of these three methods can be generalized to cube
roots. Subscribe if you want more of these math videos. See you next time!