That is easily resolved by replacing 2 with 3 throughout (7/3 < 3). It does change things for this particular example, but that doesn't invalidate the method more generally.
Interesting to compare the p/q -> (p+2q)/(p+q) to what you get with Newton's method, which is p/q -> (p^2 + 2 q^2)/(2 pq). So for example we get 3/2 -> 17/12 -> 577/408 in just two steps!
@@AxisAngles Indeed! This iteration is is linear (it works by finding an x-intercept of a secant through point at x=1 for f(x)=x^2-b), newton's is quadratic (x-intercept of the tangent to f(x)=x^2-b).
It’s maddening how often I’m like “yep, totally following this” and then BOOM, “yeah, I’m totally lost”. On the plus side, I feel really good when I follow the whole thing.
lol I recently quit smoking and suddenly developed a desire to learn calculus. Watching these videos is like seeing amazing architecture just as you are learning what the T-square and compass are for. Now; how does this propelling pencil work... :P
For anyone wondering where (x+b)/(x+1) comes from, it's the false position (regula falsi) iteration for root-finding on f(x)=(x^2-b), using the bracket [1,x], replacing the x with a new one, keeping 1 fixed. The other, more well known, is the Newton's, method, which yields (x+b/x)/2 and converges faster.
Thank you, I did wonder where this expression (x+b)/(x+1) came from! I wasn't familiar with the classic, pre-calculus, false position (regula falsi) iteration method for solving equations, but as I understand from en.m.wikipedia.org/wiki/Regula_falsi, here we are using double false position, which is mathematically equivalent to linear interpolation: you take two points on the curve y=f(x), (x₁, f(x₁)) and (x₂,f(x₂)), and, for an estimate of a root of f(x)=0, see where the line joining these two points intersects the x-axis, which is at: x=(f(x₁)x₂-f(x₂)x₁)/(f(x₁)-f(x₂)) (I checked this). To iterate, you then replace x₁ or x₂ by x, and then repeat the process. In this case, as you said, we take f(x)=x²-b and x₁=1 (fixed), with our current estimate being x₂. Then the next estimate is then x=(f(1)x₂-f(x₂)×1)/(f(1)-f(x₂)) =((1-b)x₂-(x₂²-b))/(1-b-(x₂²-b)) =((x₂²-b)-(1-b)x₂)/((x₂²-b)-(1-b)) =(x₂²+(b-1)x₂-b)/(x₂²-1) =(x₂-1)(x₂+b)/((x₂+1)(x₂-1)) =(x₂+b)/(x₂+1) the expression used in the video. For the next iteration we set x₂=x (keeping x₁=1 fixed) and repeat the process. I presume that if we take f(x)=x³-b, then the same method will give x=(x₂²+x₂+b)/(x₂²+x₂+1) the expression used in the video.
This isn't fast, necessarily, but my favourite method for finding the roots of polynomials is to use perturbation series. x^5 - x - 1 = 0 is not solvable by radicals. However, x^5 - 1 = 0 is, and quite trivially, too. So let's consider x^5 - εx - 1 = 0, and try to find the limit as ε→1. We do this by expanding x as a power series in ε: x = a0 + a1 ε + a2 ε^2 + ... And then we substitute this back into the original equation. Taking the power of an infinite power series is not difficult: x^5 = a0^5 + 5 a0^4 a1 ε + (5 a0^4 a2 + 10 a0^3 a1^2) ε^2 + ... And so we have: (a0^5-1) + (5*a0^4*a1-a0) ε + (5 a0^4 a2+10 a0^3 a1^2 - a1) ε^2 + ... = 0 This equation must hold for all ε, therefore each of the coefficients of ε^k must be zero, giving the system of equations: a0^5 - 1 = 0 5 a0^4 a1 - a0 = 0 5 a0^4 a2 + 10 a0^3 a1^2 - a1 = 0 ... The first equation is the equation we decided we could solve, and the others give you the other coefficients in terms of a0: a1 = 1/(5 a0^3) a2 = -1/(25 a0^7) a3 = 1/(125a0^11) ... And so: x = a0 + ε/(5 a0^3) - ε^2/(25 a0^7) + ε^3/(125a0^11) + ... And you can now easily take the limit as ε→1. Amazingly, this is one power series that gives you ALL of the roots of x^5 - x - 1. All you need to do is choose a different fifth root of unity for a0. Choosing a0 = 1 as an example gives: x = 1 + 1/5 - 1/25 + 1/125 + ... Those three terms give 1.168; the actual real root is 1.167303978... There is a catch. The series may not converge fast, and it may not converge at all, although you can try to be smart about how you evaluate it (e.g. using Shanks transformation or a Pade approximant).
Using the binomial theorem, (a^3 + b)^(1/3) ~ a + b/(3a^2) for appropriate values of a and b. For the cube root of 5, we may use a = 1.7 and b = 0.087, and then the approximation is 1.7100346...
a/b -> (a²+2b²) / (2ab) converges in second order (waaay more faster) 3/2 -> 17/12 -> 577/408 -> 665857/470832 -> ... It is a subsequence of the former one in the video but skips (quadratically) more and more elements of it.
This series doesn't always converge. For example, if I choose a0 = 4 and b = 27 I would expect it to converge to 3, but I get: 4., 2.2381, 4.1526, 2.16089, 4.32043, 2.08394, 4.50085, 2.00937, 4.68954, 1.93926, 4.8806}. In fact for any a0 and b = 27, it looks like it "converges" to ak = 6.0756 ak+1 = 1.59106. Another example, if a0=4 and b = 22, we a1 is 42/21 == 2. a2 is 28/7 == 4, so it just repeats 4,2,4,2...
The amazing thing about the (p + 2q)/(p + q) rational approximation is that the initial value doesn't have to be all that close to sqrt(2). If you start it at a million it converges on sqrt(2) to eight significant figures within ten iterations.
For square roots of integers, I like to find the continued fraction expansion, hence solve Pell's equation, then define a recurrence relation providing a sequence of integers whose ratio tends to a + b sqrt(n). For sqrt(2), the continued fraction is simply [1;2,2,2,2,...], the resulting recurrence relation is a0 = 0, a1 = 1, a{n+2} = 2a{n+1} + a{n}, so sequence 0, 1, 2, 5, 12, 29, 70,... with ratio tending to 1 + sqrt(2). The arithmetic is quite easy to do in one's head and gives very efficient rational approximations - with the number of correct significant digits being roughly the sum of the number of digits in the numerator and denominator.
For the last part, the one with the polynomial, you could have said that f is bijective on the interval that we need (it is strictly monotone, plus it is continuous), so it has an inverse. The equation becomes f(x) = f^(-1)(x) which is equivalent to f(x) = x. And then you get a simpler polynomial, I believe. Very nice video!
Equivalent over the real numbers maybe, but I don't think they're equivalent equations because they have different numbers of roots. f(x)=x ⇒ f(x)=f^{-1}(x) is clear, but how do you propose to get the converse (which is the important direction)?
@@schweinmachtbree1013 well, i am not sure how "careful" this is, but the graph of the inverse function is symmetrical to the graph of the function itself, the axis of symmetry being the identical function. So the only places where these 2 functions will meet is on the line of g(x) = x. Thus the equivalence
I don't think this works, since taking f(x):=1/x, for example, we have that f(f(x))=x holds for all real x since f is an involution, but f(x)=x gives x^2=1, which only has two solutions.
@@alexanderbasler6259 Good point, and f(x) := -x gives another counterexample. I Googled it, and the implication f(x)=f^{-1}(x) ⇒ f(x)=x holds for any _increasing_ f :D
Hi, For the square root, I know this : x_{n+1} = ( x_{n} + A/x_{n}) / 2 , which converges towards sqrt(A). By like TheEternalVortex I think the Newton's method is better and gives a quadratic convergence.
Oh dear! In that case you can't prove it, because it's false. After all, if you take one of the other real roots as a seed, then the odd terms of your sequence will all equal that root. I suspect that the even terms will also be fixed at that or another root, but this is just a guess.
I tried to do it in a simpler way, by using the recursion a_n+1 = (a_n + b)/(a_n^2 + 1) instead. Unfortunately, this doesn't converge for b = 5. For b = 2, it does converge to the third root of 2, but only _very_ slowly.
A very good point. You could also weave this into a motivation for the construction of f in the first place. (Edit: on reflection, I'm not sure that f having exactly one fixed point, 5^{1/3}, is enough to show A = 5^{1/3} = B. We know A and B are fixed points of f^2, but a priori we don't know A and B are fixed points of f. Some further argument is required. It would be nice though to remove the grunginess of explicitly composing f with itself.)
But you can immediately show that a_n = a_n+1 = cube root of 5 satisfies a_n+1 = (a_n^2 + a_n + 5)/(a_n^2 + a_n + 1) Why is it necessary so solve f(f(x)) = x?
1:30 After only 2 or 3 more iterations, your error from sqrt(2) is about the same as 355/113 from pi, while (Mathologer) "17/12 is like the '22/7 from pi' for sqrt(2)." By the way, how do you change the root from 2 to 3 and onward in general?
you can’t; the generalisation using geometric series does not converge at all for large enough nth roots, the admissible values for which they do vanish
So to show it in the general case, if you define f(x) as in the video, then simplify f(f(x)) = x you get some complicated fifth degree polynomial. But you can now factor x^3 - a from it (I checked in Mathematica this works). This seems impractical to do by hand however, I wonder if there's a nicer way?
Solve for x in f(x) = x, you don't need to do it for f(f(x)) (and it wouldn't be enough anyway, otherwise you didn't prove it for odd terms, only even terms) But for your quintic, doing euclidean division by x³-b is doable by hand
Well that Mathematica computation is a general proof; you'd just have to check that the resulting quadratic factor has no real roots (by looking at B^2 - 4AC), like Michael did in the special case.
@@schweinmachtbree1013 Unfortunately, unless I've made a mistake, the quadratic factor (3x^2 +(4-b)x+(b+2)) has real roots if b is above ~20.4, so I don't think this method is enough to prove convergence to b^1/3 for all b. Briefly skimming the paper Michael mentioned, it seems there's some restriction on the gap between the initial seed and the root you're approximating, which presumably determines where the iteration spirals to on a cobweb diagram and hence converging to the right root.
Thats the key demo that 0.99999 is NOT 1. We can see on this video that the limit of a rational number is equal to an irrational number but the limit=irrational does not mean rational=irrational it would be a contradiction So same thing with 0.9999 its limits is 1 but that for the same reason dosent mean 0.99999=1 great im done i can rest in peace now. If the limit of A=B you are not allowed to say A=B because they live on different sets and you end up with these kind of contradictions
Wait. 7/3 is already greater than your upper bound of 2.
That is easily resolved by replacing 2 with 3 throughout (7/3 < 3). It does change things for this particular example, but that doesn't invalidate the method more generally.
Doesn't matter too much, since f(7/3) = (whatever it was in the thumbnail) is in [1, 2], so start there.
@@minamagdy4126he means 5⅓ cannot be approximately equal 7/3 since 7/3>8⅓, therefore 5⅓ is approximately bigger than 8⅓.
23:38 Good Place To Thank People For Watching
Interesting to compare the p/q -> (p+2q)/(p+q) to what you get with Newton's method, which is p/q -> (p^2 + 2 q^2)/(2 pq). So for example we get 3/2 -> 17/12 -> 577/408 in just two steps!
Yeah! I also noticed that the number of steps of (p + 2q)/(p + q) required to match newtons method seems to double each time.
@@AxisAngles Indeed! This iteration is is linear (it works by finding an x-intercept of a secant through point at x=1 for f(x)=x^2-b), newton's is quadratic (x-intercept of the tangent to f(x)=x^2-b).
It’s maddening how often I’m like “yep, totally following this” and then BOOM, “yeah, I’m totally lost”.
On the plus side, I feel really good when I follow the whole thing.
one of my physics friends always says " getting confused, but in the good way!"
lol I recently quit smoking and suddenly developed a desire to learn calculus. Watching these videos is like seeing amazing architecture just as you are learning what the T-square and compass are for.
Now; how does this propelling pencil work... :P
For anyone wondering where (x+b)/(x+1) comes from, it's the false position (regula falsi) iteration for root-finding on f(x)=(x^2-b), using the bracket [1,x], replacing the x with a new one, keeping 1 fixed.
The other, more well known, is the Newton's, method, which yields (x+b/x)/2 and converges faster.
Thank you, I did wonder where this expression (x+b)/(x+1) came from!
I wasn't familiar with the classic, pre-calculus, false position (regula falsi) iteration method for solving equations, but as I understand from en.m.wikipedia.org/wiki/Regula_falsi, here we are using double false position, which is mathematically equivalent to linear interpolation: you take two points on the curve y=f(x), (x₁, f(x₁)) and (x₂,f(x₂)), and, for an estimate of a root of f(x)=0, see where the line joining these two points intersects the x-axis, which is at:
x=(f(x₁)x₂-f(x₂)x₁)/(f(x₁)-f(x₂))
(I checked this).
To iterate, you then replace x₁ or x₂ by x, and then repeat the process.
In this case, as you said, we take f(x)=x²-b and x₁=1 (fixed), with our current estimate being x₂.
Then the next estimate is then
x=(f(1)x₂-f(x₂)×1)/(f(1)-f(x₂))
=((1-b)x₂-(x₂²-b))/(1-b-(x₂²-b))
=((x₂²-b)-(1-b)x₂)/((x₂²-b)-(1-b))
=(x₂²+(b-1)x₂-b)/(x₂²-1)
=(x₂-1)(x₂+b)/((x₂+1)(x₂-1))
=(x₂+b)/(x₂+1)
the expression used in the video.
For the next iteration we set x₂=x (keeping x₁=1 fixed) and repeat the process.
I presume that if we take f(x)=x³-b, then the same method will give
x=(x₂²+x₂+b)/(x₂²+x₂+1)
the expression used in the video.
This isn't fast, necessarily, but my favourite method for finding the roots of polynomials is to use perturbation series.
x^5 - x - 1 = 0 is not solvable by radicals. However, x^5 - 1 = 0 is, and quite trivially, too. So let's consider x^5 - εx - 1 = 0, and try to find the limit as ε→1.
We do this by expanding x as a power series in ε:
x = a0 + a1 ε + a2 ε^2 + ...
And then we substitute this back into the original equation. Taking the power of an infinite power series is not difficult:
x^5 = a0^5 + 5 a0^4 a1 ε + (5 a0^4 a2 + 10 a0^3 a1^2) ε^2 + ...
And so we have:
(a0^5-1) + (5*a0^4*a1-a0) ε + (5 a0^4 a2+10 a0^3 a1^2 - a1) ε^2 + ... = 0
This equation must hold for all ε, therefore each of the coefficients of ε^k must be zero, giving the system of equations:
a0^5 - 1 = 0
5 a0^4 a1 - a0 = 0
5 a0^4 a2 + 10 a0^3 a1^2 - a1 = 0
...
The first equation is the equation we decided we could solve, and the others give you the other coefficients in terms of a0:
a1 = 1/(5 a0^3)
a2 = -1/(25 a0^7)
a3 = 1/(125a0^11)
...
And so:
x = a0 + ε/(5 a0^3) - ε^2/(25 a0^7) + ε^3/(125a0^11) + ...
And you can now easily take the limit as ε→1. Amazingly, this is one power series that gives you ALL of the roots of x^5 - x - 1. All you need to do is choose a different fifth root of unity for a0.
Choosing a0 = 1 as an example gives:
x = 1 + 1/5 - 1/25 + 1/125 + ...
Those three terms give 1.168; the actual real root is 1.167303978...
There is a catch. The series may not converge fast, and it may not converge at all, although you can try to be smart about how you evaluate it (e.g. using Shanks transformation or a Pade approximant).
Using the binomial theorem, (a^3 + b)^(1/3) ~ a + b/(3a^2) for appropriate values of a and b. For the cube root of 5, we may use a = 1.7 and b = 0.087, and then the approximation is 1.7100346...
Nice! The error will be O(b/a³).
a/b -> (a²+2b²) / (2ab) converges in second order (waaay more faster) 3/2 -> 17/12 -> 577/408 -> 665857/470832 -> ... It is a subsequence of the former one in the video but skips (quadratically) more and more elements of it.
This series doesn't always converge. For example, if I choose a0 = 4 and b = 27 I would expect it to converge to 3, but I get: 4., 2.2381, 4.1526, 2.16089, 4.32043, 2.08394, 4.50085, 2.00937,
4.68954, 1.93926, 4.8806}. In fact for any a0 and b = 27, it looks like it "converges" to ak = 6.0756 ak+1 = 1.59106.
Another example, if a0=4 and b = 22, we a1 is 42/21 == 2. a2 is 28/7 == 4, so it just repeats 4,2,4,2...
If anyone is CLOSE to Michael's mathematical and language arts abilities then they are at the ROOT of excellence!!!
The amazing thing about the (p + 2q)/(p + q) rational approximation is that the initial value doesn't have to be all that close to sqrt(2). If you start it at a million it converges on sqrt(2) to eight significant figures within ten iterations.
This isn't actually surprising. If you start with a large seed, the next term is just slightly greater than 1, and then it's plain sailing.
@@MichaelRothwell1Nobody said it was! It's amazing nonetheless
For square roots of integers, I like to find the continued fraction expansion, hence solve Pell's equation, then define a recurrence relation providing a sequence of integers whose ratio tends to a + b sqrt(n). For sqrt(2), the continued fraction is simply [1;2,2,2,2,...], the resulting recurrence relation is a0 = 0, a1 = 1, a{n+2} = 2a{n+1} + a{n}, so sequence 0, 1, 2, 5, 12, 29, 70,... with ratio tending to 1 + sqrt(2). The arithmetic is quite easy to do in one's head and gives very efficient rational approximations - with the number of correct significant digits being roughly the sum of the number of digits in the numerator and denominator.
For the last part, the one with the polynomial, you could have said that f is bijective on the interval that we need (it is strictly monotone, plus it is continuous), so it has an inverse. The equation becomes f(x) = f^(-1)(x) which is equivalent to f(x) = x. And then you get a simpler polynomial, I believe. Very nice video!
Equivalent over the real numbers maybe, but I don't think they're equivalent equations because they have different numbers of roots. f(x)=x ⇒ f(x)=f^{-1}(x) is clear, but how do you propose to get the converse (which is the important direction)?
@@schweinmachtbree1013 well, i am not sure how "careful" this is, but the graph of the inverse function is symmetrical to the graph of the function itself, the axis of symmetry being the identical function. So the only places where these 2 functions will meet is on the line of g(x) = x. Thus the equivalence
@@orbualexandru8592 Ah of course, you're right (Edit: kind of right)
I don't think this works, since taking f(x):=1/x, for example, we have that f(f(x))=x holds for all real x since f is an involution, but f(x)=x gives x^2=1, which only has two solutions.
@@alexanderbasler6259 Good point, and f(x) := -x gives another counterexample. I Googled it, and the implication f(x)=f^{-1}(x) ⇒ f(x)=x holds for any _increasing_ f :D
1959 math journal... Cool. Must have a great collection of cool math books.
He wanted to show 10 rather than n>=0 in what he is trying to prove.
13:30 Pretty sure 7/3 > 2 lol
Depends on the size of 2 😂
He probably meant 3 earlier and just ran with it.
Similar but faster approximation to cube root of p: a/b -> (2a³+pb³)/(3a²b)
Hi,
For the square root, I know this : x_{n+1} = ( x_{n} + A/x_{n}) / 2 , which converges towards sqrt(A).
By like TheEternalVortex I think the Newton's method is better and gives a quadratic convergence.
Well, of course, but NM requires computing the derivative which Archimedes didn't know.
@@ddognine no need for that in the discrete case.
7/3 is grater than 2 but from your video it seems that it is less
23:00 The general equation is (x^3-b)[3x^2+(4-b)x+(b^2+b)] which has 3 real solutions for b>6.797 (or b
Oh dear! In that case you can't prove it, because it's false. After all, if you take one of the other real roots as a seed, then the odd terms of your sequence will all equal that root. I suspect that the even terms will also be fixed at that or another root, but this is just a guess.
Oops. Not 1
Sqrt(x)= ((3x+a)/(x+3a))(sqrt(a))
Where a is close to x whose squre root is known.
Sqrt(2)=((3×2+1)/(3×1+2))*sqrt(1)
This gives 7/5.
I tried to do it in a simpler way, by using the recursion a_n+1 = (a_n + b)/(a_n^2 + 1) instead. Unfortunately, this doesn't converge for b = 5. For b = 2, it does converge to the third root of 2, but only _very_ slowly.
i think we can directly check for the fixed points of f not f^2 to see that it converges to the cubic root of 5
A very good point. You could also weave this into a motivation for the construction of f in the first place. (Edit: on reflection, I'm not sure that f having exactly one fixed point, 5^{1/3}, is enough to show A = 5^{1/3} = B. We know A and B are fixed points of f^2, but a priori we don't know A and B are fixed points of f. Some further argument is required. It would be nice though to remove the grunginess of explicitly composing f with itself.)
But you can immediately show that a_n = a_n+1 = cube root of 5 satisfies
a_n+1 = (a_n^2 + a_n + 5)/(a_n^2 + a_n + 1)
Why is it necessary so solve f(f(x)) = x?
1:30 After only 2 or 3 more iterations, your error from sqrt(2) is about the same as 355/113 from pi, while (Mathologer) "17/12 is like the '22/7 from pi' for sqrt(2)."
By the way, how do you change the root from 2 to 3 and onward in general?
you can’t; the generalisation using geometric series does not converge at all for large enough nth roots, the admissible values for which they do vanish
I think the upper bound should have been chosen as 3
So to show it in the general case, if you define f(x) as in the video, then simplify f(f(x)) = x you get some complicated fifth degree polynomial. But you can now factor x^3 - a from it (I checked in Mathematica this works). This seems impractical to do by hand however, I wonder if there's a nicer way?
Solve for x in f(x) = x, you don't need to do it for f(f(x)) (and it wouldn't be enough anyway, otherwise you didn't prove it for odd terms, only even terms)
But for your quintic, doing euclidean division by x³-b is doable by hand
Well that Mathematica computation is a general proof; you'd just have to check that the resulting quadratic factor has no real roots (by looking at B^2 - 4AC), like Michael did in the special case.
@@schweinmachtbree1013 Unfortunately, unless I've made a mistake, the quadratic factor (3x^2 +(4-b)x+(b+2)) has real roots if b is above ~20.4, so I don't think this method is enough to prove convergence to b^1/3 for all b. Briefly skimming the paper Michael mentioned, it seems there's some restriction on the gap between the initial seed and the root you're approximating, which presumably determines where the iteration spirals to on a cobweb diagram and hence converging to the right root.
Can't find the previous video.
Anyone with the link?
Probably this one: ua-cam.com/video/Bw38m7aP4hQ/v-deo.html
@@gonzus1966 thanks!
7 / 3 > 2, just for fun!
Nice thumbnail
I wonder what algorithm my calculator uses - probably Newton's method
Can anyone share me if there is a video talking about p+2q/p+q is closer than p/q? Want to visit the video but can’t find it😢
You need to write that correctly as (p + 2q)/(p + q).
Newton's method converges faster. And it's not that much harder to compute.
Thats the key demo that 0.99999 is NOT 1. We can see on this video that the limit of a rational number is equal to an irrational number but the limit=irrational does not mean rational=irrational it would be a contradiction So same thing with 0.9999 its limits is 1 but that for the same reason dosent mean 0.99999=1 great im done i can rest in peace now. If the limit of A=B you are not allowed to say A=B because they live on different sets and you end up with these kind of contradictions