You're very sneaky with the surprise! 1/phi and -phi are the two other roots! I found them by trying to factor x⁵ - 5x + 3 via trial and error and finding (x² + x - 1)(x³ - x² + 2x - 3) = 0 This somewhat reminds me of generating functions, specifically this result involving the Fibonacci numbers: 1/(1 - x - x²) = 1 + x + 2x² + 3x³ + 5x⁴ + 8x⁵ + . . . By the way, I used the cubic formula on the second factor; the root you found in the video can be written as such: ⅙ × (2 + ∛(260 + 4 √4725) + ∛(260 - 4 √4725)) Math is fun! :)
Yeah , number opposite to golden ratio and reciprocal of golden ratio , there is also third one but i didnt recognize it Two other roots are complex x^5-5x+3=(x^3 - x^2 + 2x - 3)(x^2 + x - 1)
@@MathNerd1729 👍 And I am glad that you enjoyed it too. This is just a warm up to a video coming in a week or two. Btw I used the Lagrange resolvent for that cubic.
@@blackpenredpen Nice! I just massaged it into a depressed cubic then used "Cardano's" Formula since I couldn't be bothered to remember Lagrange's resolvent. I made a slight mistake in depressing the cubic on my first attempt though, so maybe it would've been better to use Lagrange. 😂
Just realized sometimes maths is hard because we aren't taught the basics like this. My Lecturer did this whole chapter without drawing a single graph.
Pretty bad teacher, tbh. Every book that exposes the Newton's method has a graph that makes it limpid how it works. I'm pretty sure Newton himself has a graph of it in his publication. Wikipedia has a nice animation
And some teachers just 'Memorise' everything and expect you to follow along word by word. My teacher told me its wrong to use notations of xn-1 and xn instead of xn and xn+1 cause according to him n starts at 0 and my notation would give a negative symbol for x. He walked away even before I could argue how starting n at 1 would fix everything 😅
Just taught this to my grade 11's this week. They loved how we can finally solve equations involving different classes of functions, where no closed form solutions are possible. The best part of Newton's Method is that with a good "First Guess" the solution converges very quickly to remarkable accuracy. We also discussed and I showed them graphically, what happens when you do not start off with a good initial value.
@@NoNameAtAll2 In getting ready for AP exams and working through the curriculum, I find that I have very little time to do anything but teach concepts and then solve as many different types of problems as possible. This is not a complaint, rather, the joy of what we are discussing is in the pure application of using these great tricks to actually work out real world useful problems.
Newton's method is easy to do with a calculator. First enter the initial guess and press = (or Exe on some models). Then enter the x-f(x)/f'(x) using Ans in place of x. Then you just hit = until the value does not change. Many calculators have built in Newton's method. I tried to trick it by giving initial value where f'(x)=0 but it did not fool. They likely use some small difference in x instead of a true derivate. The nice thing in Newton's method is that even if you make an error it likely just slows you down, you will not get a wrong answer.
x^5 - 5x + 3 can also be solved using a recursive definition for x. x^5 = 5x - 3 x = (5x-3)^(1/5) Now, replace the value of x with (5x-3)^(1/5) x = 5(5x-3)^(1/5)+3)^(1/5) The idea is that if you substitute this enough times, eventually you can plug in ANY value for the x on the right hand side and it will still return one root of x, at which point you can use polynomial division to reduce it to a solveable quartic equation, as the more times the definition is plugged in, the more this calculation will tend to converge on a single value, the solution to x^5 - 5x + 3. In a way, this is like a recursive sequence, where u[n+1] = (5(u[n])+3)^(1/5). In fact, you can use this recursive method for any equation with 2 instances of the variable - I don't know if it could possibly be adapted for more than 2 values. Hope someone found this useful!
You can also x^5 - 5x + 3 = 0 as 5x = x^5 + 3 x = (x^5 + 3)/5 and ist this as another Banach fixpoint iteration. For the initial value x0 = 0 or -1 or +1, it converges to 0.618... For x0 = 2 or -2, it diverges to infinite. If I remember correctly from the numerics lecture, if you write x = phi(x) then in order to converge, | phi'(x) |
Very good explanations, but two things: 1.) I would improve the sketch by adding vertical lines, e.g. from (x1, 0) to (x1, f(x1)), not only the tangents, so you can see a zig-zag pattern in the sketch, which better demonstrates the iteration process. 2.) I learned the formula x_{n+1} = x_n - f(x_n)/f'(x_n) which is easier to write down and memorize than x_n = x_{n-1} - f(x_{n-1}) / f'(x_{n-1}) due to the shorter indices.
Circa 5:00 Rather than calculating the equation of the tangent line, you only need the slope, ie the "rise over run", so f'(x₁) = f(x₁)/(x₁ - x₂) which trivially rearranges to x₂ = x₁ - f(x₁)/f'(x₁) It's basically the same thing, but I think it's easier to explain. Edit: forgot my ₁s inside the f() f'()
I just calculated solutions of quadratic using this method and rounding up to sixth decimal place and compared it with delta results and they were extremely close to each other. Newton was a genius by inventing this, and he was doing all his calculations without computers which is even more insane
f(x) = x⁵ - 5x + 3 = 0 f'(x) = 5(x⁴ - 1) I get x = 1.275682204... = R₁ for that first solution you got (the largest of the 3 real roots); we agree on that. For the next one to the left, I get x = .6180339887... = R₂ And for the smallest of the 3 real roots, I get x = -1.618033989... = R₃ , and I recognize these as R₂ = 1/ϕ [= ϕ-1] and R₃ = -ϕ. This means that g(x) = x² + x - 1 is a factor of f(x). [The monic quadratic in x, with sum-of-zeros = S, and product-of-zeros = P, is x² - Sx + P.] Dividing, we get f(x)/g(x) = x³ - x² + 2x - 3 = h(x) whose only real zero must be R₁ . My calculator confirms this. At this point, you could get down to a quadratic (which will have to have a discriminant < 0), by dividing: h(x)/(x-R₁) = x² + bx + c = q(x) which we can find by noting that multiplying (x-R₁)q(x) and setting it equal to h(x), tells us that b - R₁ = -1; and R₁c = 3. Thus, b = R₁ - 1 = .275682204... c = -3/R₁ = -2.351682881... So finally, (R₄ , R₅) = -.137841102... ± (1.527312251...)i Fred PS. Zeros R₂ and R₃ can be verified using the relation of Fibonacci numbers to powers of ϕ: ϕⁿ = F[n]ϕ + F[n-1] R₂ = 1/ϕ = ϕ⁻⁻¹ = ϕ-1 R₂⁵ = ϕ⁻⁻⁵ = F[-5]ϕ + F[-6] = 5ϕ - 8 f(R₂) = R₂⁵ - 5R₂ + 3 = 5ϕ - 8 - 5ϕ + 5 + 3 = 0 R₃ = -ϕ R₃⁵ = -ϕ⁵ = -F[5]ϕ - F[4] = -5ϕ - 3 f(R₃) = R₃⁵ - 5R₃ + 3 = -5ϕ - 3 - 5(-ϕ) + 3 = 0
Congrats, you are too smart. But would be cool to get the exact algebric solutions with the cubic equation that you finded, this w'ont be easy, if I get time I'll do this.
@@Pedro-yv1kk Spoiler Alert: It's already been done by Math Nerd 1729, in a reply to bprp's self-pinned comment. His/her real zero simplifies to: ⅙[2 + ∛(60√21 + 260) - ∛(60√21 - 260)] That cubic being h(x) = x³ - x² + 2x - 3 Math Nerd 1729 doesn't provide the complex conjugate pair of zeros, but if you're better versed in the cubic solution formula than I am, maybe you can deduce them from the information above. Fred
@@maximilianthegreatest The sum of all n zeros of an n-degree polynomial is always -b/a, where a is the leading coefficient and b is the next one; the (n-1)st power. So whenever the (n-1)-power term vanishes, the sum of solutions is 0. And of course, so is the average, which = sum/n. Fred
This is very easy to approximate just by inspection. Use 0.6 since the x^5 term will be very small, and -5x will be -3, thus "almost" solving the equation. From there, I can just check values close to 0.6 on a computer, which I did, and quickly got about 0.618034.
This is best video about newton's method I didn't understand how got formula y-f(x_1) = f`(x_1) (x-x_1) Some else mentioned right angle to drive the equation, maybe that video explained how derive equation. He really used decimal value 1.67 instead of 1 2/3 or 5/3
This formula is according to the straight line equation，y-y1=k(x-x1). Just putting the f(x1) as y1, the derivative of the function as k, and x1 as x1, which the blogger has mentioned in the video. And I suppose you could understand better now. 😊
Let p_n(x) be a trinomial of the form x^n + b x + c. If b is (-1)^n F_n and c is (-1)^(n - 1) F_n-1 with F the Fibonacci numbers, then p has a factor of x^2 + x - 1. So for example p_10(x) = x^10 + 55 x - 34 has factor x^2 + x - 1. The other factor is a polynomial with its coefficients taken from the Fibonacci series, in this case x^8 - x^7 + 2 x^6 - 3 x^5 + 5 x^4 - 8 x^3 + 13 x^2 - 21 x + 34. This ties in to the generating function of 1/(x^2 + x + 1).
Finding all solutions here is simple: just find x values where the derivative is zero and run Newtons method at most once on both sides of the x values found. For instance, in this example we have f’(x) = 5x^4 - 5. Setting f’(x)=0 gives x=1 and x=-1 as solutions where the slope is 0. This means that there will be 3 solutions, since there are 3 different intervals where the slope does not equal 0: [-inf, -1), (-1, 1), and (1, +inf). Now just pick points within each interval and run Newton’s method to find the 3 solutions.
Thanks for this video, it helps me to understand the deduction part of this Newton-Raphson method, and it’s linked to the straight line equation unexpectedly. Wow!
We had some weird calculus aasignment in school where you were supposed to prove that the integral of -ax^2+b from root to root always was 3/2. I thought it didnt make any sense
I was surprised it took 7 iteration to get that approximation, I thought it would converge much faster, and 3-4th iteration will be already quite precise
But we *do* have formulas for 5th and higher degree polynomials! It's just that the formulas involve operations slightly more complicated than roots. You say that you can solve a quadratic polynomial by completing the square or using the quadratic formula, but to do this, you have to introduce this crazy square-root operation. How do you define that?, and how do you calculate that? You define a square root as a solution to a particular equation, pretty circular if you ask me. And you can calculate it by hand using a technique that goes back to the early days of Algebra but is basically Newton's Method in disguise. And so, when the time comes to solve arbitrary quintic polynomials, you can define a new operation, slightly more complicated than the 5th root, as the solution to a particular equation. With the help of that, there's a formula to solve any 5th-degree polynomial (even ones that can't be factored). And you can go on and do the 6th degree and higher with the help of additional operations. Just like with the square root, these operations are all defined as the solutions to certain polynomial equations, and they can be calculated by hand to arbitrary precision using techniques that are basically Newton's Method.
My C++ Solution to use this Newton's method: #include #define pb push_back using namespace std; double F (double x) { // define the polynomial function here return x*x*x -x - 1; } double F1 (double x) { // define the derivative of the polynomial function here return 3*x*x - 1; } // Showing Each Iteration Function void draw(vector& v) { cout
Speaking the numerical methods did you try calculating polynomial roots using eigenvalue methods Two of the companion matrices are already in Hessenberg form Suggested method for calculating eigenvalues is QR method with shifts To QR decomposition we can multiply matrix A by rotation matrices xor by reflection matrices I didnt find how to choose clever shift Double implicit shift is tempting because entries of matrix are real but eigenvalues may be complex
Still haven't found a great video on the doubly implicit shifted QR algorithm, I'd love to see one some day. Pretty rough way to calculate polynomial roots, though you get all the values in one algorithm at least (and eigenvalues/eigenvectors for nearly any complex square matrix on top of that). Edit: And no need for derivatives either!
If you want to approximate roots of polynomial x^n=c_{1}x^{n-1}+c_{2}x^{n-2}+...+c_{n} with eigenvalues method you place coefficients c_{1}, c_{2},...,c_{n} in the first row xor last column , put ones just below main diagonal and everywhere else put zero In this way you will create companion matrix To get QR decomposition we can use multiplication by rotation matrices xor multiplication by reflection matrices Basic QR algorithm looks as follows A_{i}=Q_{i}R_{i} A_{i+1}=R_{i}Q_{i} but for faster convergence clever choice of shift is helpful For me doubly implicit shift is tempting because matrix entries are real and eigenvalues may be complex but there are other strategies for choosing shift
Yeah, regular QR algorithm is pretty simple, it's the implicit double shift that I struggle with. Trying to find the submatricies of the Shur form without explicitly forming the matrix is where my brain shuts down. I said it's a rough way to find the polynomial roots because you need the double shift to find complex roots using QR while Newton's method can find all complex roots with good enough starting points.
@@onlythefacts999 I found some examples that unshifed QR method doesnt converge to Schur form (fe matrix similar to the companion matrix of odd or even polynomial) (real eigenvalues on diagonal , complex eigenvalues from 2x2 block on diagonal) Moreover there can be found matrices for which convergence is very slow
As you noted, Newton's Method doesn't always work, but there _is_ a theorem that sometimes guarantees that it will. It's fairly intuitive if you think about it this way: First of all, if the derivative of the function is zero, then of course Newton's method doesn't work at all, as you noted. On the other hand, if the _value_ of the function is zero, then you already have the solution, and Newton's method finishes after 0 steps. In general, if the derivatives are small in absolute value, then that's bad; while if the values are small in absolute value, then that's good. Putting these together, if the difference between two successive approximations (which is a value divided by a derivative) is small, then that's a good sign. A little less obvious, but also true, is that if the _second_ derivatives are small in absolute value, then that is good too. (One way to see this is to imagine that you're travelling along a tangent line that closely follows the curve; if the second derivative is rather large, then the curve will quickly pull away from your tangent line, and you will not be heading towards a solution after all.) So here's the theorem: If you start with one guess x0 and use Newton's method to get a second guess x1, then you can look at the interval J that has x0 at one endpoint and x1 in the middle. If on that interval J, the absolute value of f″(x) is always at most the absolute value of f′(x1) divided by the length of the interval J (in other words, |f″(x)| ≤ ½|f′(x1)f′(x0)/f(x0)|), then you're guaranteed that Newton's Method, starting from x0 as you did, will converge to a solution in the interval J. (And then this is the _only_ solution in that interval.) There are even more general versions of this, where the function doesn't have to be twice differentiable, and where you have a function of several variables. With some additional assumptions, you can also guarantee that Newton's Method converges _quickly_ (which is again something that usually happens but not always). Look up Kantorovich's Theorem if you want to see the fancy versions.
You can also use this theorem to prove that at the end of the video, you got the answer correct to 4 decimal places. Just because two successive guesses give the same answer to 4 decimal places, does _not_ guarantee this by itself! (After all, your first two guesses were both 2 to 0 decimal places, yet the final answer is 1 to 0 decimal places.) But using Kantorovich's theorem, starting from 1.2757, you get an interval which is so small that everything in it rounds to 1.2757 and in which the solution is guaranteed to be. (This takes a bit of calculation to check.) Therefore, the answer _must_ be 1.2757 to 4 decimal places.
OK, is there any way to set this up to solve x as the limit of when xn - xn-1 goes to 0? I guess for the other solutions start at 0 and -2. That should get there, right? There is a solution between 0 (pos) and 1 (neg) and a solution between -1 (pos) and -2 (neg), but -1 will blow up so start at -2
Hello guys, anyone who is new to the newton formula should read this! If the given function has like points with a slope of 0 (don't how they are called, I'm german we have some funny names for them) you might have a little problem with them... Suppose your new x-Value has a slope of 0, now think about that what might happen... →The problem is that your new tangent line will never cross the x plane! Why is that? Since the slope is 0, the tangent line will also have a slope of 0 being just flat line. Therefore you can't continue with the newton formula... :( In order to avoid this, you might prove with f'(x)=0 if the given function has points with a slope of 0. Those points are like borders for this method. You should always have a clue how the given function looks like, you could make a table with the x-values and their corresponding f(x) values to somehow have an overlook. This method could also go away from the zero digit you want. Therefore remember to make a little table to see where a zero digit should be, and when the function is going up or down, also look up if there are 0-slope points near your zero digit! Your initial x-value for the newton method is very important, you should choose it smart and not make your Life hard. (I might post a good sheet explaing this with graphics later on, I have to translate it first) little secret: this method could end up in an infinite loop where your x1 value gives the new x2 value, and the x2 value gives you the old x1 value. To prove it lets say that n(x) = x - f(x) / f'(x), then you make up this equation: x = n(x) - f(n(x)) / f'(n(x)) and solve it for x... :D
I like to call this method "Chain chugging." Because it's essentially plugging and chugging every solution into the same formula until it stops varying so much.
I absolutely hate when im just walking on the side of the street and some random guy asks me how to do Newton's method But thankfully I dont have to worry about this anymore 😮💨
One technique I learned from the HP-15C manual is once you know one solution to the equation, create a new equation f(x)/(x-1st_solution) and solve for that. While being aware that this will cause a division by zero if the algorithm tries the first solution again. Quick n' dirty python code to run newton method: def f(x): return x**5-5*x+3 def f1(x): return 5*x**4-5 def newton(x): i = 2000 for n in xrange(2000): x=x-f(x)/f1(x) print 'newton after %d iterations x=%.30f y=%.30e' % (i, x, f(x)) return x newton(1.5) # newton after 2000 iterations x=1.275682203650984947174151784566 y=0.000000000000000000000000000000e+00 newton(0.0) # newton after 2000 iterations x=0.618033988749894791503436408675 y=0.000000000000000000000000000000e+00 newton(-500.0) # newton after 2000 iterations x=-1.618033988749894902525738871191 y=-1.776356839400250464677810668945e-15
Enjoyed to see your video with help me in better understanding of maths Through your videos it make me feel that maths in flowing in my vein Thanks to give thie type of content
When I was taught it, it was called just, "Newton's Method." Later I started seeing it called the "Newton-Raphson Method." I guess I'm in Achtung Baby's camp; when I refer to it, I just go with the shorter name. Fred
I noticed that if you choose a guess close to that local max on the side of a board on the left 3:14, then the tangent line’s x-intercept can overgo the answer, i think if it does that we need to continue to work with that guees, Id like to see a formula for a relation of the slope of the guess point and the distance of a guess from the solution TO the interval when tangent line overgoing the answer, and if this formula exists than the first point at which tangent line over goes the answer would be the answer. In other words I described the point whos tangent line solve newton’s method in just one step. What happens when x-intercept of a tangent line over goes the answer? Do we continue by starting again with that acquired guess, i can think that we now go in the opposite direction. i think because formula works with different slopes, its should be ready for the to slope going in a different direction. That is equivalent to starting Newton’s method all over again with that acquired overflown guess point
Not for humans, but if you write a program, it's better to find every local min/max with the first and second derivatives and do a binary search between them to get the approximation of the roots. It's pretty fast and simple.
Can you not take the limit of Xn as x goes to infinity? I think it is doable because you have Xn+1 = g(Xn) so you solve limit L=g(L) Where g(x)= x - f(x)/f'(x). You basically have to solve L= L -f(L)/f(L) Which is f(L)/f'(L) =0 And now that I wrote it I get why this is not helpful lol i just got back to f(x)=0
What would you do if all the zeroes of a function are complex? Would you still use Newton’s method? Maybe using tangent parabolas instead of tangent lines to approximate?
Fun fact, x^5-5x+3 is actually factorable and we will factor it soon! Try "my first quintic equation" here 👉 th-cam.com/video/YkEPMf1l2os/w-d-xo.html
You're very sneaky with the surprise!
1/phi and -phi are the two other roots!
I found them by trying to factor x⁵ - 5x + 3 via trial and error and finding (x² + x - 1)(x³ - x² + 2x - 3) = 0
This somewhat reminds me of generating functions, specifically this result involving the Fibonacci numbers:
1/(1 - x - x²) = 1 + x + 2x² + 3x³ + 5x⁴ + 8x⁵ + . . .
By the way, I used the cubic formula on the second factor; the root you found in the video can be written as such:
⅙ × (2 + ∛(260 + 4 √4725) + ∛(260 - 4 √4725))
Math is fun! :)
Yeah , number opposite to golden ratio and reciprocal of golden ratio , there is also third one but i didnt recognize it
Two other roots are complex
x^5-5x+3=(x^3 - x^2 + 2x - 3)(x^2 + x - 1)
@@MathNerd1729 👍
And I am glad that you enjoyed it too. This is just a warm up to a video coming in a week or two. Btw I used the Lagrange resolvent for that cubic.
@@blackpenredpen Nice! I just massaged it into a depressed cubic then used "Cardano's" Formula since I couldn't be bothered to remember Lagrange's resolvent. I made a slight mistake in depressing the cubic on my first attempt though, so maybe it would've been better to use Lagrange. 😂
Every quintic is factorable since it has zeroes!!
man i absolutely hate it when someone jumps out of the blue and asks me to solve a quintic equation :/
I had that happen at the supermarket last week. My milk spoiled and my eggs hatched while I was helping him work it out.
Were it a lady, I would be very much attracted to her...
Indeed, tfw.
I was unable to solve it and now I am chilling with Satan (●__●).
I've learned how to solve cubics recently. NEVER trying quartics...
15:19 "Everything is doable if you have patience. But I have a calculator"
*Proof mathematicians are not accountants*
"Everything is doable if we have patience."
-BlackPenRedPen, 2022 15:19
lol : )
Just realized sometimes maths is hard because we aren't taught the basics like this. My Lecturer did this whole chapter without drawing a single graph.
Pretty bad teacher, tbh. Every book that exposes the Newton's method has a graph that makes it limpid how it works. I'm pretty sure Newton himself has a graph of it in his publication. Wikipedia has a nice animation
And some teachers just 'Memorise' everything and expect you to follow along word by word. My teacher told me its wrong to use notations of xn-1 and xn instead of xn and xn+1 cause according to him n starts at 0 and my notation would give a negative symbol for x. He walked away even before I could argue how starting n at 1 would fix everything 😅
Intact 😢
Teachers are mostly incompetent
The other two solutions are
x = -1.618034 and
x = 0.618034
And I see why you said the answers would be interesting !!
golden ratio and its inverse?
negative golden ratio and positive reciprocal
Just taught this to my grade 11's this week. They loved how we can finally solve equations involving different classes of functions, where no closed form solutions are possible. The best part of Newton's Method is that with a good "First Guess" the solution converges very quickly to remarkable accuracy. We also discussed and I showed them graphically, what happens when you do not start off with a good initial value.
have you shown them 3blue1brown's video on Newton's fractal?
@@NoNameAtAll2 In getting ready for AP exams and working through the curriculum, I find that I have very little time to do anything but teach concepts and then solve as many different types of problems as possible. This is not a complaint, rather, the joy of what we are discussing is in the pure application of using these great tricks to actually work out real world useful problems.
the "first guess" is the crucial part.
@@NoNameAtAll2 i have, it was mind blowing 🤯🤯🤯
Newton's method is easy to do with a calculator. First enter the initial guess and press = (or Exe on some models). Then enter the x-f(x)/f'(x) using Ans in place of x. Then you just hit = until the value does not change.
Many calculators have built in Newton's method. I tried to trick it by giving initial value where f'(x)=0 but it did not fool. They likely use some small difference in x instead of a true derivate.
The nice thing in Newton's method is that even if you make an error it likely just slows you down, you will not get a wrong answer.
the fact that he manages to explain everything and write it all on one small board is amazing!
im almost graduating at mathematics and i cant express how much i love your yt channel
x^5 - 5x + 3 can also be solved using a recursive definition for x.
x^5 = 5x - 3
x = (5x-3)^(1/5)
Now, replace the value of x with (5x-3)^(1/5)
x = 5(5x-3)^(1/5)+3)^(1/5)
The idea is that if you substitute this enough times, eventually you can plug in ANY value for the x on the right hand side and it will still return one root of x, at which point you can use polynomial division to reduce it to a solveable quartic equation, as the more times the definition is plugged in, the more this calculation will tend to converge on a single value, the solution to x^5 - 5x + 3. In a way, this is like a recursive sequence, where u[n+1] = (5(u[n])+3)^(1/5).
In fact, you can use this recursive method for any equation with 2 instances of the variable - I don't know if it could possibly be adapted for more than 2 values.
Hope someone found this useful!
You made a small algebraic error, that should be x^5 = 5x -3 , not plus 3
@@anshumanagrawal346 Thank you, I've corrected it now.
You can also x^5 - 5x + 3 = 0 as
5x = x^5 + 3
x = (x^5 + 3)/5
and ist this as another Banach fixpoint iteration.
For the initial value x0 = 0 or -1 or +1, it converges to 0.618...
For x0 = 2 or -2, it diverges to infinite.
If I remember correctly from the numerics lecture, if you write
x = phi(x)
then in order to converge, | phi'(x) |
Very good explanations, but two things:
1.) I would improve the sketch by adding vertical lines, e.g. from (x1, 0) to (x1, f(x1)), not only the tangents, so you can see a zig-zag pattern in the sketch, which better demonstrates the iteration process.
2.) I learned the formula
x_{n+1} = x_n - f(x_n)/f'(x_n)
which is easier to write down and memorize than
x_n = x_{n-1} - f(x_{n-1}) / f'(x_{n-1})
due to the shorter indices.
Circa 5:00 Rather than calculating the equation of the tangent line, you only need the slope, ie the "rise over run", so
f'(x₁) = f(x₁)/(x₁ - x₂) which trivially rearranges to x₂ = x₁ - f(x₁)/f'(x₁)
It's basically the same thing, but I think it's easier to explain.
Edit: forgot my ₁s inside the f() f'()
I just calculated solutions of quadratic using this method and rounding up to sixth decimal place and compared it with delta results and they were extremely close to each other. Newton was a genius by inventing this, and he was doing all his calculations without computers which is even more insane
Literally just co-wrote a paper on Galois. I love this video so much.
Newton, what a legend 😎
So are you, Mr Einstein!
@@blackpenredpen thanks! :)
I just did a tutorial about newton method for UG students last week
Perfect!
@@blackpenredpen why would anyone think to use the intermediate value theorem? I don't see why anyone would? Hope you can respond when you can.
f(x) = x⁵ - 5x + 3 = 0
f'(x) = 5(x⁴ - 1)
I get x = 1.275682204... = R₁ for that first solution you got (the largest of the 3 real roots); we agree on that.
For the next one to the left, I get x = .6180339887... = R₂
And for the smallest of the 3 real roots, I get x = -1.618033989... = R₃ , and I recognize these as R₂ = 1/ϕ [= ϕ-1] and R₃ = -ϕ.
This means that g(x) = x² + x - 1 is a factor of f(x). [The monic quadratic in x, with sum-of-zeros = S, and product-of-zeros = P, is x² - Sx + P.]
Dividing, we get
f(x)/g(x) = x³ - x² + 2x - 3 = h(x)
whose only real zero must be R₁ . My calculator confirms this.
At this point, you could get down to a quadratic (which will have to have a discriminant < 0), by dividing:
h(x)/(x-R₁) = x² + bx + c = q(x)
which we can find by noting that multiplying (x-R₁)q(x) and setting it equal to h(x), tells us that
b - R₁ = -1; and R₁c = 3. Thus,
b = R₁ - 1 = .275682204...
c = -3/R₁ = -2.351682881...
So finally,
(R₄ , R₅) = -.137841102... ± (1.527312251...)i
Fred
PS. Zeros R₂ and R₃ can be verified using the relation of Fibonacci numbers to powers of ϕ:
ϕⁿ = F[n]ϕ + F[n-1]
R₂ = 1/ϕ = ϕ⁻⁻¹ = ϕ-1
R₂⁵ = ϕ⁻⁻⁵ = F[-5]ϕ + F[-6] = 5ϕ - 8
f(R₂) = R₂⁵ - 5R₂ + 3 = 5ϕ - 8 - 5ϕ + 5 + 3 = 0
R₃ = -ϕ
R₃⁵ = -ϕ⁵ = -F[5]ϕ - F[4] = -5ϕ - 3
f(R₃) = R₃⁵ - 5R₃ + 3 = -5ϕ - 3 - 5(-ϕ) + 3 = 0
Holly schiedd....
Congrats, you are too smart. But would be cool to get the exact algebric solutions with the cubic equation that you finded, this w'ont be easy, if I get time I'll do this.
@@Pedro-yv1kk Spoiler Alert: It's already been done by Math Nerd 1729, in a reply to bprp's self-pinned comment. His/her real zero simplifies to:
⅙[2 + ∛(60√21 + 260) - ∛(60√21 - 260)]
That cubic being
h(x) = x³ - x² + 2x - 3
Math Nerd 1729 doesn't provide the complex conjugate pair of zeros, but if you're better versed in the cubic solution formula than I am, maybe you can deduce them from the information above.
Fred
The average of the solutions is 0. Why does this happen?
@@maximilianthegreatest The sum of all n zeros of an n-degree polynomial is always -b/a, where a is the leading coefficient and b is the next one; the (n-1)st power.
So whenever the (n-1)-power term vanishes, the sum of solutions is 0. And of course, so is the average, which = sum/n.
Fred
This is very easy to approximate just by inspection. Use 0.6 since the x^5 term will be very small, and -5x will be -3, thus "almost" solving the equation. From there, I can just check values close to 0.6 on a computer, which I did, and quickly got about 0.618034.
It's phi-1
This is best video about newton's method
I didn't understand how got formula y-f(x_1) = f`(x_1) (x-x_1)
Some else mentioned right angle to drive the equation, maybe that video explained how derive equation.
He really used decimal value 1.67 instead of 1 2/3 or 5/3
This formula is according to the straight line equation，y-y1=k(x-x1). Just putting the f(x1) as y1, the derivative of the function as k, and x1 as x1, which the blogger has mentioned in the video. And I suppose you could understand better now. 😊
Let p_n(x) be a trinomial of the form x^n + b x + c. If b is (-1)^n F_n and c is (-1)^(n - 1) F_n-1 with F the Fibonacci numbers, then p has a factor of x^2 + x - 1. So for example p_10(x) = x^10 + 55 x - 34 has factor x^2 + x - 1. The other factor is a polynomial with its coefficients taken from the Fibonacci series, in this case x^8 - x^7 + 2 x^6 - 3 x^5 + 5 x^4 - 8 x^3 + 13 x^2 - 21 x + 34. This ties in to the generating function of 1/(x^2 + x + 1).
I'm Chinese from Mainland China. I guess you are from Hongkong or Singapore.
Wonderful lecture! Difficult problem made easy!
The explanation is very beautiful. Thank you for these efforts🤍🤍
Finding all solutions here is simple: just find x values where the derivative is zero and run Newtons method at most once on both sides of the x values found. For instance, in this example we have f’(x) = 5x^4 - 5. Setting f’(x)=0 gives x=1 and x=-1 as solutions where the slope is 0. This means that there will be 3 solutions, since there are 3 different intervals where the slope does not equal 0: [-inf, -1), (-1, 1), and (1, +inf). Now just pick points within each interval and run Newton’s method to find the 3 solutions.
Thanks for this video, it helps me to understand the deduction part of this Newton-Raphson method, and it’s linked to the straight line equation unexpectedly. Wow!
We had some weird calculus aasignment in school where you were supposed to prove that the integral of -ax^2+b from root to root always was 3/2. I thought it didnt make any sense
Newton's method is also one of the easiest (or at least most well known) methods for solving Kepler's equation for the eccentric anomaly.
i was talking to my friend about this today, and you released a video on it. coincidence 😄
😆
It's not a coincidence. BPRP is watching you.
try consecutive derivatives equation = 0 (zero points of the equation nth-derivatives) to get the newton's method initial guess x0 regions directly
Thanks for this video , I have a better un comprehension of this optimization’s method
Congrats for the 903k followers. You will get a million just fast!!!
I was surprised it took 7 iteration to get that approximation, I thought it would converge much faster, and 3-4th iteration will be already quite precise
But we *do* have formulas for 5th and higher degree polynomials! It's just that the formulas involve operations slightly more complicated than roots.
You say that you can solve a quadratic polynomial by completing the square or using the quadratic formula, but to do this, you have to introduce this crazy square-root operation. How do you define that?, and how do you calculate that? You define a square root as a solution to a particular equation, pretty circular if you ask me. And you can calculate it by hand using a technique that goes back to the early days of Algebra but is basically Newton's Method in disguise.
And so, when the time comes to solve arbitrary quintic polynomials, you can define a new operation, slightly more complicated than the 5th root, as the solution to a particular equation. With the help of that, there's a formula to solve any 5th-degree polynomial (even ones that can't be factored). And you can go on and do the 6th degree and higher with the help of additional operations. Just like with the square root, these operations are all defined as the solutions to certain polynomial equations, and they can be calculated by hand to arbitrary precision using techniques that are basically Newton's Method.
I have used this at work to find roots and called it Newton iteration
My C++ Solution to use this Newton's method:
#include
#define pb push_back
using namespace std;
double F (double x) {
// define the polynomial function here
return x*x*x -x - 1;
}
double F1 (double x) {
// define the derivative of the polynomial function here
return 3*x*x - 1;
}
// Showing Each Iteration Function
void draw(vector& v) {
cout
He's the guy Steven's dad compares his son with
1:20 there is a quintic formula using series
Give us video on finite series please
16:48" I don't have enough space, so just trust me on that."
Now where have I heard that before?
I made an algorithm now that uses this method, ty for showing it.
Speaking the numerical methods did you try calculating polynomial roots using eigenvalue methods
Two of the companion matrices are already in Hessenberg form
Suggested method for calculating eigenvalues is QR method with shifts
To QR decomposition we can multiply matrix A by rotation matrices xor by reflection matrices
I didnt find how to choose clever shift
Double implicit shift is tempting because entries of matrix are real but eigenvalues may be complex
Still haven't found a great video on the doubly implicit shifted QR algorithm, I'd love to see one some day.
Pretty rough way to calculate polynomial roots, though you get all the values in one algorithm at least (and eigenvalues/eigenvectors for nearly any complex square matrix on top of that).
Edit: And no need for derivatives either!
If you want to approximate roots of polynomial x^n=c_{1}x^{n-1}+c_{2}x^{n-2}+...+c_{n} with eigenvalues method
you place coefficients c_{1}, c_{2},...,c_{n} in the first row xor last column , put ones just below main diagonal and everywhere else put zero
In this way you will create companion matrix
To get QR decomposition we can use multiplication by rotation matrices xor multiplication by reflection matrices
Basic QR algorithm looks as follows
A_{i}=Q_{i}R_{i}
A_{i+1}=R_{i}Q_{i}
but for faster convergence clever choice of shift is helpful
For me doubly implicit shift is tempting because matrix entries are real and eigenvalues may be complex
but there are other strategies for choosing shift
Yeah, regular QR algorithm is pretty simple, it's the implicit double shift that I struggle with. Trying to find the submatricies of the Shur form without explicitly forming the matrix is where my brain shuts down.
I said it's a rough way to find the polynomial roots because you need the double shift to find complex roots using QR while Newton's method can find all complex roots with good enough starting points.
@@onlythefacts999 I found some examples that unshifed QR method doesnt converge to Schur form (fe matrix similar to the companion matrix of odd or even polynomial)
(real eigenvalues on diagonal , complex eigenvalues from 2x2 block on diagonal)
Moreover there can be found matrices for which convergence is very slow
@@onlythefacts999 Have you read Numerical recipes in C ? There is an example of qr method with Hessenberg reduction , shifts and deflation
I’m in the middle of making a video on the Newton-Raphson method! ❤️
Thank u man , u make math fun and easy
As you noted, Newton's Method doesn't always work, but there _is_ a theorem that sometimes guarantees that it will. It's fairly intuitive if you think about it this way:
First of all, if the derivative of the function is zero, then of course Newton's method doesn't work at all, as you noted. On the other hand, if the _value_ of the function is zero, then you already have the solution, and Newton's method finishes after 0 steps. In general, if the derivatives are small in absolute value, then that's bad; while if the values are small in absolute value, then that's good. Putting these together, if the difference between two successive approximations (which is a value divided by a derivative) is small, then that's a good sign. A little less obvious, but also true, is that if the _second_ derivatives are small in absolute value, then that is good too. (One way to see this is to imagine that you're travelling along a tangent line that closely follows the curve; if the second derivative is rather large, then the curve will quickly pull away from your tangent line, and you will not be heading towards a solution after all.)
So here's the theorem: If you start with one guess x0 and use Newton's method to get a second guess x1, then you can look at the interval J that has x0 at one endpoint and x1 in the middle. If on that interval J, the absolute value of f″(x) is always at most the absolute value of f′(x1) divided by the length of the interval J (in other words, |f″(x)| ≤ ½|f′(x1)f′(x0)/f(x0)|), then you're guaranteed that Newton's Method, starting from x0 as you did, will converge to a solution in the interval J. (And then this is the _only_ solution in that interval.)
There are even more general versions of this, where the function doesn't have to be twice differentiable, and where you have a function of several variables. With some additional assumptions, you can also guarantee that Newton's Method converges _quickly_ (which is again something that usually happens but not always). Look up Kantorovich's Theorem if you want to see the fancy versions.
You can also use this theorem to prove that at the end of the video, you got the answer correct to 4 decimal places. Just because two successive guesses give the same answer to 4 decimal places, does _not_ guarantee this by itself! (After all, your first two guesses were both 2 to 0 decimal places, yet the final answer is 1 to 0 decimal places.) But using Kantorovich's theorem, starting from 1.2757, you get an interval which is so small that everything in it rounds to 1.2757 and in which the solution is guaranteed to be. (This takes a bit of calculation to check.) Therefore, the answer _must_ be 1.2757 to 4 decimal places.
OK, is there any way to set this up to solve x as the limit of when xn - xn-1 goes to 0?
I guess for the other solutions start at 0 and -2. That should get there, right? There is a solution between 0 (pos) and 1 (neg) and a solution between -1 (pos) and -2 (neg), but -1 will blow up so start at -2
use newton's method, no quintic formula
Detailed and interesting explanation
Thank you 👍
VERY INFORMATION VIDEO!!! TANK YU!! (soryr for bad egluish)
Hello guys, anyone who is new to the newton formula should read this!
If the given function has like points with a slope of 0 (don't how they are called, I'm german we have some funny names for them) you might have a little problem with them...
Suppose your new x-Value has a slope of 0, now think about that what might happen...
→The problem is that your new tangent line will never cross the x plane! Why is that? Since the slope is 0, the tangent line will also have a slope of 0 being just flat line. Therefore you can't continue with the newton formula... :(
In order to avoid this, you might prove with f'(x)=0 if the given function has points with a slope of 0. Those points are like borders for this method.
You should always have a clue how the given function looks like, you could make a table with the x-values and their corresponding f(x) values to somehow have an overlook.
This method could also go away from the zero digit you want.
Therefore remember to make a little table to see where a zero digit should be, and when the function is going up or down, also look up if there are 0-slope points near your zero digit!
Your initial x-value for the newton method is very important, you should choose it smart and not make your Life hard.
(I might post a good sheet explaing this with graphics later on, I have to translate it first)
little secret: this method could end up in an infinite loop where your x1 value gives the new x2 value, and the x2 value gives you the old x1 value. To prove it lets say that n(x) = x - f(x) / f'(x), then you make up this equation: x = n(x) - f(n(x)) / f'(n(x)) and solve it for x... :D
I genuinely thought the Pokemon ball is an eraser
you can use it to solve implicit equations often too
Very well explained. Thank you so much
I used this method for a subject at my university, It's wonderful! can you do the same thing with Lagrange?
I like to call this method "Chain chugging." Because it's essentially plugging and chugging every solution into the same formula until it stops varying so much.
also you can show that you have the solution when Xn = Xn-1:
Xn = Xn-1 - f(Xn-1) / f'(Xn-1)
Xn = Xn - f(Xn) / f'(Xn)
0 = - f(Xn) / f'(Xn)
f(Xn) = 0
00:46 we don't have to worry ;
Because we will learn how to manage with such problem in next 20min.😁
I absolutely hate when im just walking on the side of the street and some random guy asks me how to do Newton's method
But thankfully I dont have to worry about this anymore 😮💨
One technique I learned from the HP-15C manual is once you know one solution to the equation, create a new equation f(x)/(x-1st_solution) and solve for that. While being aware that this will cause a division by zero if the algorithm tries the first solution again.
Quick n' dirty python code to run newton method:
def f(x):
return x**5-5*x+3
def f1(x):
return 5*x**4-5
def newton(x):
i = 2000
for n in xrange(2000):
x=x-f(x)/f1(x)
print 'newton after %d iterations x=%.30f y=%.30e' % (i, x, f(x))
return x
newton(1.5)
# newton after 2000 iterations x=1.275682203650984947174151784566 y=0.000000000000000000000000000000e+00
newton(0.0)
# newton after 2000 iterations x=0.618033988749894791503436408675 y=0.000000000000000000000000000000e+00
newton(-500.0)
# newton after 2000 iterations x=-1.618033988749894902525738871191 y=-1.776356839400250464677810668945e-15
Enjoyed to see your video with help me in better understanding of maths
Through your videos it make me feel that maths in flowing in my vein
Thanks to give thie type of content
Starting with an initial guess of x = o, you'd get x = 0.61803.... approximately.
"Take the derivative,
Take the derivative,
Take the derivative,
Take the derivative,
Take the derivative."
~BPRP, 2022
I like that you hold a Pokémon ball plush the entire equation
It's secretly his microphone 😯
@@danieltefera7347 or he’s probably teaching it to Pikachu and he can hear it from the Pokéball
@@abemcg3803 lol
Actually, when I was taught this method, it was named the Newton-Raphson method.
The two names are interchangeable. Plain old Newton's Method uses less syllables 😅
When I was taught it, it was called just, "Newton's Method." Later I started seeing it called the "Newton-Raphson Method."
I guess I'm in Achtung Baby's camp; when I refer to it, I just go with the shorter name.
Fred
Imagine someone jumping you to ask a math problem, math teacher problems lol.
wow , thanks , now i know where the formula comes from
Newton is the real genius.
I literally lost my ear drums when you said "suppose" In the beginning
Aw, man! I hate it when I'm walking down the street and some stranger approaches me with a quintic ecuation!
I noticed that if you choose a guess close to that local max on the side of a board on the left 3:14, then the tangent line’s x-intercept can overgo the answer, i think if it does that we need to continue to work with that guees, Id like to see a formula for a relation of the slope of the guess point and the distance of a guess from the solution TO the interval when tangent line overgoing the answer, and if this formula exists than the first point at which tangent line over goes the answer would be the answer. In other words I described the point whos tangent line solve newton’s method in just one step. What happens when x-intercept of a tangent line over goes the answer? Do we continue by starting again with that acquired guess, i can think that we now go in the opposite direction. i think because formula works with different slopes, its should be ready for the to slope going in a different direction. That is equivalent to starting Newton’s method all over again with that acquired overflown guess point
Little known fact: BlackPenRedPen is married to BluePenGreenPen.
Not for humans, but if you write a program, it's better to find every local min/max with the first and second derivatives and do a binary search between them to get the approximation of the roots. It's pretty fast and simple.
Lol I love that idea
and I love when u said not for humans
The real top G
Excellent lesson for Newton's method!
i just loked up the quartic formula and i dont even know how insane a person must be to memorize that
Can you please do a video on Galois Theory?
I'm pretty sure you made a video about it either in another channel or even in this one
Yes. An old one with the omega constant. But you will see why this thing again 😃
@@blackpenredpen interesting
Can you please solve x^(4-2x)*e^x=1?
Can you make a video using the quartic formula ?? 😬😬😬
You can solve a quintic solvable using method of Piezas III.
What is coefficient of x^3n in expension of (1+x+x²+x³......x^2n)³
finally, I see your video just after its release. btw my DP is made from a mathematical function (cause of your inspiration).
Can you not take the limit of Xn as x goes to infinity?
I think it is doable because you have Xn+1 = g(Xn) so you solve limit L=g(L)
Where g(x)= x - f(x)/f'(x).
You basically have to solve L= L -f(L)/f(L)
Which is f(L)/f'(L) =0
And now that I wrote it I get why this is not helpful lol i just got back to f(x)=0
nice work 👑 am introducing mathematics in simple ways
I want to see quarntic formula please
Thank you!
Thanks a lot!
What about x^5 -3x +5 = 0
With x1 = 1
What if you take 3 derivatives at least and then see were the possible roots are and then use Newton in order to go close to the value
Thank you legend !
The Quartic formula is bigger than lord of the rings 💀
waiting for your IMO related videos
What would you do if all the zeroes of a function are complex? Would you still use Newton’s method? Maybe using tangent parabolas instead of tangent lines to approximate?
I just got done with SecMath3. How does one calculate the derivative?
1.27568
Great job ❤🎉
BPRP really pulled out a "trust me, bro" at 6:44 lol good vid nonetheless
Merci, on connaît que cette théorie converge lentement mais sûrement.
How do we find the two complex roots? Find the reals and then polynomial division to get to a quadratic equation?
Just put in a complex guess
Thanj youuuu so much! :)))
How do we get the basic formula at 5:00 ? I don't understand the thought process
y-y1=m(x-x1) equation of the line with the given point (x1, y1) and slope m
So what happens when the root falls at an extremum of f(x)?