Square Root of 2, Newton's method vs Euler's method
HTML-код
- Опубликовано: 24 окт 2018
- Approximating Sqrt(2), Newton's Method vs Euler's Method
Check out Quahntasy on Optical Tweezers, • Nobel Prize in Physics...
sqrt(2), original raw file (uncut, unedited, full version): • Sqrt(2), Newton's Meth...
Newton's Method in details: • Newton's method and Om...
Euler's Method in details: • Euler's Method (introd...
⭐️Please subscribe for more math content!
☀️support bprp on Patreon: / blackpenredpen
Guess what my first job was! • My First Job Story ,
My simple setup: 😃 • My Simple RUclips Setu... ,
Check out my site & social media
😃 blackpenredpen.com
😃 / blackpenredpen
😃 / blackpenredpen
Thank you for supporting! You're awesome and I know it!
blackpenredpen | 曹老師
Thanks a lot, blackpenredpen. I can’t even begin to explain how much your help meant to me.
Quahntasy - Animating Universe expecting good content. subscribed
As soon as I finish commenting on how much I enjoyed this presentation, I'm going to check out your content. Props to BlackpenRedpen for the courtesy.
Nice a lot!
D i thatI
Try Newton's method in RATIONAL ARITHMETIC, i.e. all numbers are of the form p/q where p and q are integers. It gets astonishingly accurate, astonishingly quickly. In fact this is giving you the same answer which you had before, i.e. root(2) = 1.4142135.... It's just that the answer comes out as an integer divided by another integer.
The sequence goes: 1/1 3/2 17/12 577/408 665857/470832. That last one has an error of 4.5 x 10^(-5)
This sequence is IDENTICAL to what you would get in real numbers, i.e. 1 1.5 1.4166666667 1.414215686 1.414213562
I use Newton's method as he had much better hair.
He looks like markiplier
Dude, what kind of bias is that LOL
Kkkkkkkkkkkk I agree with you
Nah man I won't believe that he actually had that log hair for all I know he could be the one using a wig which he takes off while sleeping
314 aka pi likes
Engineering Students:
sqrt(2) = 1.414 = 1
sqrt(2) = 1.414 = 1 = sin(x)
sqrt(2)=1.414=1
1^2=2=1+1
sqrt(8)=2sqrt(2)=2.828=3=e=pi
=> e/pi = e/sqrt(8) = sqrt(8)/pi = 1
ice_SZN take sqrt(2) = 2, no way it won’t handle
And don’t forget: g = π^2
No we don't do that
Why do you have a thermal detonator in your hand
What? Isnt that a regular psy amp?
@@Skandalos Isn't it?
@@rayniac211 Is it not?
You're all wrong. He doesn't use a thermonuclear detonator. He is using a droid from the future which is telling him what to say to the camera.
Ah Ah, but it ties up one hand so he has to keep twiddling his pen colors around like a one-hand card shuffle, and it must get soar too! ✍
You remind me how much fun Math has been for me over my years. I was never a whiz, reached my level of incompetence at the advanced undergraduate level, but it's fun and interesting to see your, Mathologer, and a few others' discussions. I was born in 1948, 71 as of this comment.
happy 73rd birthday :)
I would love to talk to you sometime. What field did you study and where did it take you after school?
@@TheGeckoIsKing I Went to San Diego State 1966-1971 when the Computer Science department was one Fortran class in the Math Dept. Which, of course, I signed up for and loved. After graduation I sort of drifted around a bit trying to find an interesting position. I went back to school, taking several C. S. courses. My friend who worked for a conpany contracting software services to the Navy suggested I put my app in with them. I worked with them for a couple of years, becoming a hot-shit Cobol programmer (no kidding). I was invited to work directly for the Navy, doing Avionics Software Engineering. I did that for 34 years, mostly legacy systems coded in Assembly. It was great, even junior engineers participate in the entire process from system engineering to full-up testing. I do not Grok O. O. systems, they make little sense to me. Very long response, apologies for that.
@@inyobill that's sounds very interesting I bet that you have a lot of curious stories
IIRC newton's method basically doubles the precise number of digits at each step.
It also has the advantage (in this situation) of being able to pick up where you left off - you can always add more accuracy by iterating for longer, but with Euler's you need to start over.
Lmao just draw an unit square and measure the diagonal with a ruler
Been there, done that
You got a ruler that can measure to 5 decimals?
@@pendragon7600 you don't?
What a pleb
@@membrillo1896 I don't need one because I can measure perfectly by sight alone
@@pendragon7600 You can use a compass and draw a circle with radius 1, then measure the length of the cord between two points separated by 90 degrees.
Little strange and unfair to compare two methods which are designed for two completely different things. Newton’s method - finds roots numerically
Euler’s method - finds numerical solution to differential equations.
Would have made more sense to compare Newton’s method to the secant method or some other numerical root solver :)
TranbärsJuice It is not unfair since he used both methods within their respective designed realms of application. I think the problem is not the comparison itself, but the rigor with which each method was applied.
@Herr Vorragend
I understood what you said after reading it three times.
@Herr Vorragend lollll
Maybe look at Mueller’s method or Sidi
@Herr Vorragend why don't you delete the extra comments?
Euler's Method isn't used for this purpose though; you got an inaccurate estimate for sqrt(2), but you also got estimates for the sqrt of 1.2, 1.4, 1.6 and 1.8. Newton's Method got you an accurate estimate of sqrt(2), but you learned nothing about the other values.
Euler's Method and Newton's Method are used for different problems, and it's not fair to apply Euler's Method to a roots problem and then be disappointed when it doesn't produce as accurate a result as you would have hoped with that step size.
Luke Longworth (hehe, I know, that's the secret. This video is for both math and entertainment purpose. )
It is not unfair, as he actually used each method within their own realm of application, and he obtained different consequences as a result. Euler’s method can be refined.
@@blackpenredpen 你好喜欢用括号啊
Zhang Jackson 哈哈 被發現了
Yuu
Try using both methods for a system of ordinary differential equations, and try using RK45 instead of vanilla Euler. That's where Euler methods are most effective. Newton's method and other fixed point iterative methods are pretty much the best for most solvers in numerical analysis.
Both shine at different objectives. Newton is great for finding roots, RK is great for numerical integration.
Much prefer the Casio Method.
me too
For some reason, I find it really cool when you say "well well"... it feels like you're a detective and you just figured out a big part of a case xD really cool!
Your videos are great and informative. Keep up the good work!
You are doing too much effort for youtube...3-4 videos in 24hours...
Hats off to you...
Hopr u reach a million soon
Start with 1.4 squared = 1.96.
Then 2 = (1.4 + epsilon)^2 = 1.96 + 2.8 epsilon + epsilon^2, throw out last term.
Then epsilon = 0.04/2.8 = 0.0143
So then 1.4 + epsilon = 1.4143 after one iteration. Keep going . . .
This method actually does simplify to the Newton method but is more intuitive, in my opinion.
Yeah, as you pointed out, this is just Newton's method using a starting point of sqrt(1.96)=1.4 instead of sqrt(1)=1
Another great method I found, with iteration:
Say you wanted the square root of A.
x = sqrt(A)
x^2 = A
x = A/x
2x = A/x + x
x = (A/x + x)/2
So the formula we'd use is
x_n = (A/x_{n-1} + x_{n-1})/2
Then iterate, begin maybe with x_0 = 1 or something you're sure is close, easy enough.
Using a calculator, you just put in your first guess, then '=' to set your initial ANS value, then type the formula, using 'ANS' instead of 'x'.
Then just spam that '=' key until the result in your calculator stops changing. Done.
Extra, play around with a 'b' variable where we can say
x = A/x
(b+1)x = A/x + bx
x = (A/x + bx)/(b + 1)
x_n = (A/x_{n-1} + bx_{n-1})/(b + 1)
'b' can be anything
Thanks of the comment. Yes, I actually know about that. That will be my continuation video to my inf. cont. fraction of sqrt(2) video and my Omega constant video.
www.wolframalpha.com/input/?i=1%2B1%2F(2%2B1%2F(2%2B1%2F(2%2B1%2F(2%2B1%2F(2%2B1%2F2))))
Your first formula is exactly the same as the Newton method, the extra formula loses the quadratic convergence rate so i would avoid it
In fact, that's called a fixed point method, because you write x=f(x) for some function f. In your case,
f(x)=(A/x+bx)/(b+1)
It's the Babylonian method!
The way I visualize it is with a "starting rectangle" of area A and with a base of length x0. That means that the height is A/x0.
If you take the average of both side, your new value (let's name it x1) will be between x0 and A/x0, and A/x1 too! So you have another rectangle with base x1, height A/x1 and an area of A, where the base and the height are closer to each other than in our starting rectangle.
So each time you repeat that process, you get a rectangle with a base and a height closer to each other. In other words, your rectangle gets "squarier".
I love that way of visualising it!
It seems that Euler's formula needs to be integrated because h needs to be 1/ infinity to give an very tiny step. that looks exactly like how we take a limit and figured out to perform integrations. While Newton's formula is an iterative process in which you can stop at any atribary point. The interesting part is that as the iterations tend toward infinity that the rate of change in the approximation tends towards zero. There seems to be some connection between the two. Is there a hybrid formula that uses both concepts?
Recommended to my dog. He said you are cool ;) Still not at his level tho.
Wow, today I have studied the Newton method in Numerical Analysis class , and by chance I see this video.
Great video 👍
They both do!!! Thinking of the tools they had to work with ... what an incredible feat by both ... both exceptional geniuses... with the pendulum leaning towards Newton in this round.
If you know the function and the derivative finding the zero isn't so hard. When all you know is the differential equation you can't even use Newton's method. Euler's method is more general and useful in application for this reason.
Wow we just learned Newton's method in class today.
Nice vid!! Keep it up!
For "Well Behaved" functions ( ie. polynomials, trig, etc ) Newton's Method is excellent at approximating the root very quickly, especially if you do a bit of work in advance and smartly come up with a good initial value. For example: solve ( cos(x) = x ) , when you draw a graph of cos(x) and y= x together, you can see that they cross each other to the left of x = 1. Thus an initial guess of x = .8 will zero in on the root of .739 085 very quickly. Love Newton's Method for getting roots fast.
Those "Well behaved" functions need an actual name. They have so many names like good functions or nice functions etc.
@@soubhagyarajkhandual I think infinitely differentiable analytic function is the term.
Infinitely differentiable means no order of differentiation ever has a discontinuity.
Analytic means that it is possible for a Taylor series to model the function. An example of a non-analytic function is a function where all derivatives equal zero at the point in question, and the Taylor series would give you a constant.
This is awesome! Sweet comparison!
: )
Very nice demonstration of the two methods. I solve a lot of cubic equations (equations of state), which are solved even faster using a third order Newton's method. This method is attributed to Hailey of Hailey's comet fame, and uses the first and second derivatives. The generalized method is known as Householder's method.
Interesting historical context thanks
As you were posing this contest, all I could do was smile and think, "This is gonna be a blowout!!"
Fred
ffggddss : )
Yay!
Excellent video!
Awesome the connection between equations and where they come from should be made while we are learning to solve them
Now it all makes sense. Thanks a lot.
I hardly understood a word, but I found this utterly fascinating!!
Are there any function where doing it one way is easy and the other way hard, and vice versa? Given that you find different derivatives?
Sad brain noises
Thanks man. I missed both of these in IB HL because I was sick.
you are so great . really love your maths
Good tutorial.. Very complete
The 1.414 value is also used in sinusoidal electrical power calculations. RMS (root mean square) effective power vs Peak power. Certain numbers are magical.
fellow electric student here 👋
Great video as always! .. I'd like to see Newton's method for finding imaginary roots of polynomials (say 3rd degree for instance) if you please.
can you integrate 2*sqrt(1+(d(sqrt(r²-x²))/dx)²) form -r to r with two different method ?
Regardless of the fact that both methods have different purposes, the choice for x0 and by extension the convergence area are relevant. Of course the initial guess must be somewhat accurate, though choosing x0 < 0 would result in convergence to -sqrt(2) instead, to give an example
Also worth looking at Goldschmidt's method. Let Y be your initial approximation to sqrt(n).
Start with: x0 = n/Y, y0 = 1/2Y
Then iterate:
ri = 0.5 - xi yi
x_{i+1} = xi + xi * ri
y_{i+1} = yi + yi * ri
Then the x's will converge to sqrt(n) and the y's will converge to 1/2sqrt(n). This is interesting because n doesn't appear anywhere in the iteration loop!
Great lecture !
Sir Isaac Newton delivers the knockout punch!
Excellent!
Though I've never done a numerical analysis course, I knew Newton's approximation would win. I was first exposed to it as an adult through learning about the Fast inverse square root in the source code for the Quake computer game.
I have never seen anything this beautiful ❤
Did Newton actually write it that way, or was this done somehow with his favorite geometric method instead?
I had to code Newton's method for a given function that was fairly hard to derivate.
It was a massive pain to translate that derivative to Java, but in the end it worked.
would be great to see a follow up with a larger step size for faster convergence on eulers method.
i love to watching your videos! Did you make video about why integral is equal to area under curve? or if you didnt, could you do please?
Hey blackpenredpen, towards the end is that your ordering of bball GOAT candidates?
: )
How many Euler steps do you need to take to get the same approximation as Newton?
It was at about this level of math when I decided to be a history major.
lmfao
My guy is clearly interested in math. Why do you think he got this far?
will the type of function-equation matter ? Will the Eulers method be better with other type of functions ?
Newton will win for sure, got good vibes
Ha! Yes, I figured it was Newton, too ... but both incredible geniuses... especially considering the tools and knowledge of the day they had to work with.
Very good comparison demonstration. When would the Euler's method converge faster than the Newton's method, given the same number of iterations?
How about arctan(1) * 4 and different ways to increase convergence rate?
By the way, could you possibly demonstrate the geometric method Newton used to figure differentials, please? I hear it may be a lost method. His "method of Fluxions" I think it was.
great video :)
Anyone an idea, which method calculators use?
I have a TI-30 from my high school days and I pressed 2 and the sqrt key, and that was much faster than either approach.
How well does Euler's work when you use F(x,y)=y/(2*x) ?
can u convert it to ratio of two integers?
can someone explain this to me ? this is in my course calculus 2 and I have no idea how did it come and how to use it ? thanks in advance :)
Area(T(s))=det(T)*area(s)
Why did newton divide the function by its derivative? What is the intuition behind that?
You are excellent sir.
Science and Maths are the best . Thanks
The expression for Newton's Method for sqrt can be simplified to x[n+1]=(x[n]+c/x[n])/2 where c is the number of which we want
the square root. In this form the method is almost intuitive.
Also for floating point computations, we have a quick method of .getting a great first approximation. Mearly cut the exponent in half. Also in the NR method the error is determined only by the last step
7:00
The ratio of ‘mathematical ease’ between the methods checks out as 2N : 5E - ?
Interesting presentation.
Is there a cutoff point where Euler's method becomes more accurate?
legends! epic battle!
this is awesome
do you know the long division style method of getting a square root? each step gives precisely a single digit, just like long division
en.wikipedia.org/wiki/Shifting_nth_root_algorithm
But how to understand which value is correct
But how do we derive the infinite series SQRT(2)=1+1/(2+1/2+1/2+1/2....). We approximated the value in successive steps but how do we define it as an infinite series in this way?
Unlisted? Damn, I clicked fast!
What would happen if you used RK4 instead of Euler's?
I always recommend you for mathematical background to people trying to understand quantum mechanics. You forgot these.
How about using the partial fractions from the continued fraction for sqrt(2) that you demonstrated 3 weeks ago? 1, 3/2 (1.5), 7/5 (1.4), 17/12 (1.416666), 41/29 (1.41379), 99/70 (1.41429), 239/169, (1.4142), 577/408 (1.4142156), 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, 275807/195025, 665857/470832.... wait, Newton's Method starting with 1 hits a few of these but much much quicker. Newton for the win!
Chip Rollinson yup. I plan to do that too in a few weeks.
Look up "Numerical Methods", it's a core computer science course and is typical of modern calculative approaches to projections and machine learning. If you can't do something algebraically, you're stuck with numerical techniques. good luck. It's as Aid-Climbing is to free climbing, certain win, not graceful.
What happened to Raphson?
Chevy SparkEV Newton was having a case with Raphson, he was a man that like Descartes got a lot of trouble to end his "college", Newton as I said had the case with him and to help his good friend rise in life, told to the royal society that Raphson created the method, after a few years Euler was studying the books that came from the europe math and found this method, the conclusion he got was that Raphson didn't discovered the method, so the famous man called this method not from Raphson, but " Newton-Raphson method"
Video omits Raphson is my q.
You kept reminding me of the Ood from Doctor Who holding that sphere. LOL :P
I know this is for more generalized functions, but for the square root in particular, the Bakhshali method is tough to beat. It has quartic convergence. You can augment any method by using a pade approximant for making a good initial guess
I pity the fool who doesn’t use the pade approximant
@@andybaldman Pade approximants are great for a lot of stuff. Shout out to Halley's method too, which is sort of a relative of the pade approximant
What about some other ODE solver like rk44. More computations per step though.
newton's method seems like a pd (proportional-derivative) controller algorithm, there is something that i barely remember about approximating a computer simulation, it was like 1/6*X1+2/6*X2+2/6*X3+1/6*X4 = X2 in short summing the values that computed using what we got at that point with 1,2,2,1 coefficients and getting our next value... maybe it can approximate quicker than that
How many steps before they give the same answer?
Go Euler! (Haven’t watched his method yet 😝)
There's also the binary search method. Consider the interval [a,b] where f(a) is a different sign than f(b). Find the midpoint of the interval, if the sign of the function at that x value is the same as the sign of f(a), then the new interval becomes [f((a+b)/2),f(b)], otherwise the new interval becomes [f(a),f((a+b)/2)]. The final answer is the midpoint of the final interval.
Starting with a = 1 and b = 2:
[1,2] -> [1,1.5] -> [1.25,1.5] -> [1.375,1.5] -> [1.375, 1.4375] -> [1.40625, 1.4375], so the final answer is 1.421875. It's not as accurate, but it requires no calculus and it gives you more control over how accurate you want the approximation to be. Since the size of the interval halves every iteration, you get 1 decimal digit of precision for about every 4 iterations (because log_2(10) is about 3.3).
who else thought the video wasnt of balckpenredpen until this man appeared😂🤣
Interesting video, how about convergence properties for each method? We see that Newton’s method looks best here, but there must be times when Euler’s is better right?
They can both be made arbitrarily precise but Newton's method will always converge faster. This is because in Newton's method you know what the function is and it's derivative, while with Euler's method you only have the differential equation. That loss of information makes Euler's method more general but less precise.
If you know ln(2), there is another way you can approximate sqrt(2) with euler's method, use the function y = 2^x which at x=0.5 equals sqrt(2). It's defining differential equation is y' = y*ln(2) and you know that y(0) = 2^0 = 1, so if you know ln(2), this is also a way to approximate sqrt(2).
I programmed all 3 ways on python, euler's method with y=2^x is more accurate than with y=sqrt(x), but still newton's method wins.
Show how to approximate the Lambert W function using Netwon's method.
WarpRulez
I did already. Check description. I showed how to approximate W(1)
I think he already did that in an other video if I recall correctly. Not sure though.
Newton is good but complicated, you have to calculate the derivative and is inestable on maxima (division by zero)
# Copyright 2020.11.09. 신촌우왕TV수학자.천재작곡가 All rights reserved.
# Reference: ruclips.net/video/-70MzMXpMIc/видео.html (연구 완료: 2020.11.09.)
# Python Code:
# [쌍곡선(xy=2) + (조화평균
Nice!
Congratulations from France
Yay! Three cheers for Newton
help me 72^x + 7^x = 80 which is the exact value of X?
Start with X=1, Y=1, and h=1. Euler gives X = 1.5. Square to give Y = 2.25. and h= -0.25.
Using this variation, h gets smaller each time around, and you can stop when you have the accuracy you want.
They both have their place
Winer heron with heron's formula : √a=(n+a/n)/2
What about Pythagoreans Theorem saying walking northwest at π/4 or 45 degrees any distance means moving the square root of that distance north or east formulations? They are all geometric cos(∆=π/4) and sin(∆=π/4) geometrically finding those positive only distance square roots.
This was fun
I think it depend on the value of the number. For example for sqrt(2) Newton's method is better but that's not always the case