omg thank you so much, i dont know why there arent much theory vids and only "resolving excercices " vids i just wanted to understand why i was doing what i was doing and why it was right. Some wise person said once "theres not better practice than a good theory" .
Man you are the only one who have shown history.not only that you have mentioned what muslim mathematician did.In todays world our contribution in math and science are not heard.thanks man.I love how you show how mathematician all around the world invented same topic,without restricting only what europeans discovered.
Dear Oscar, may I know if there are methods for solving system of polynomials equations? (I have watched your series of Newton's method, however, even global Newton's method might stuck at some local minimum point, right?)
I haven't covered anything specifically for systems of polynomial equations. But for solving systems of nonlinear equations, the generalized secant method ua-cam.com/video/p2OPlnHJPNI/v-deo.html tends toward convergence. Also, Generalized Aitken-Steffensen Method guarantees convergence ua-cam.com/video/-x9_fSNrX3w/v-deo.html
I would really like to see a proof of why Horner scheme gives the quotient. I understand why it gives the remainder of division, but it giving the quotient looks like magic. I saw some proofs by solving equations for polynomial coefficients, but I wonder if there's a quick and simple argument, at least for low degrees like 2 and 3.
For more efficiency, you could also replace the Newton step in the Newton-Horner method with the Halley step to create Halley-Horner, or with the Householder step to create Householder-Horner. But what if you wanted to avoid derivatives? Then switch to Steffensen's method to create Steffensen-Horner, or to the secant method to create Secant-Horner.
Or you switch to finding multiple roots at once such as with Bairstow's Method, Durand-Kerner Method (ua-cam.com/video/5JcpOj2KtWc/v-deo.html), or Aberth-Ehrlich Method (ua-cam.com/video/XIzCzfMDSzk/v-deo.html); all of which even find complex roots by default.
@@OscarVeliz Yeah. It reminds me for Bairstow's method being explored in much detail, still waiting in the queue... The problem with these methods, is that my calculator doesn't support complex numbers, and I have to do it by hand.
Consider using Durand-Kerner (ua-cam.com/video/5JcpOj2KtWc/v-deo.html), Aberth-Ehrlich (ua-cam.com/video/XIzCzfMDSzk/v-deo.html), Laguerre's Method (ua-cam.com/video/blOARV4lnIM/v-deo.html), or Bairstow's Method (in the video queue).
@@OscarVeliz speaking the polynomial root finding , there is also eigenvalue method There are two companion matrices in upper Hessenberg form and two with lower Hessenberg form and we can apply QR method to one of them, QR decomposition can be easily derived by multiplication by rotation matrices - from left to get R matrix and from right to get Q matrix How can I choose shift (without complex arithmetics) to accelerate the convergence There also slow convergence with repeated roots I wrote code for Bairstow's method based on one of the videos on youtube , I also wrote code for eigenvalues method but i probably didnt choose shift well and as stop condition i gave maximum number of iterations This approach is space costly but is implemented in Octave and numpy and even they dont manage the repeated roots
Nice video. Unfortunately, I find the derivative of your words with respect to time higher than average wpm though applying Rolle's Theorem this is not absolutely true. Just kidding. Please keep on posting videos.
Hi, thank you so much for explaining, although I didn't get the Newton-Horners scheme - could somebody please tell me how did we get the new polynomials every restart of the method?
It depends. If you already have programmed a working Newton's Method, then you could use it as-is to find a single root (but it will be slightly inefficient). In order to deflate though you would have to apply Ruffini's Rule. But if you didn't want to use Horner's method, then you would need to divide your function call by the root you found, i.e. let newf(x) = f(x)/(x-r), as well as every other subsequent root that you find. For an example of using Newton-Horner, check out my implementation hosted in the channel's GitHub repository. The link is in the description.
omg thank you so much, i dont know why there arent much theory vids and only "resolving excercices " vids i just wanted to understand why i was doing what i was doing and why it was right.
Some wise person said once "theres not better practice than a good theory" .
Thank you so much! I finally understand this, thanks to you. The history part was interesting as well. Great video!
Thank you so much. I couldn't have asked for a better explanation!
Thanks, great video. I'm here trying to solve horner's method using recursions (thought I had no interest in root-finding)
Man you are the only one who have shown history.not only that you have mentioned what muslim mathematician did.In todays world our contribution in math and science are not heard.thanks man.I love how you show how mathematician all around the world invented same topic,without restricting only what europeans discovered.
very well organized explanation.Thank you!
Great Work
Dear Oscar, may I know if there are methods for solving system of polynomials equations? (I have watched your series of Newton's method, however, even global Newton's method might stuck at some local minimum point, right?)
I haven't covered anything specifically for systems of polynomial equations. But for solving systems of nonlinear equations, the generalized secant method ua-cam.com/video/p2OPlnHJPNI/v-deo.html tends toward convergence. Also, Generalized Aitken-Steffensen Method guarantees convergence ua-cam.com/video/-x9_fSNrX3w/v-deo.html
@@OscarVelizThankyou Oscar!
Awesome video! Thank you!
I would really like to see a proof of why Horner scheme gives the quotient. I understand why it gives the remainder of division, but it giving the quotient looks like magic. I saw some proofs by solving equations for polynomial coefficients, but I wonder if there's a quick and simple argument, at least for low degrees like 2 and 3.
For more efficiency, you could also replace the Newton step in the Newton-Horner method with the Halley step to create Halley-Horner, or with the Householder step to create Householder-Horner. But what if you wanted to avoid derivatives? Then switch to Steffensen's method to create Steffensen-Horner, or to the secant method to create Secant-Horner.
Or you switch to finding multiple roots at once such as with Bairstow's Method, Durand-Kerner Method (ua-cam.com/video/5JcpOj2KtWc/v-deo.html), or Aberth-Ehrlich Method (ua-cam.com/video/XIzCzfMDSzk/v-deo.html); all of which even find complex roots by default.
@@OscarVeliz By the way, you didn't showcase the secant fractal... but I have generated some fractals from it. So no need to showcase it?
I'm not quite sure what you mean.
@@OscarVeliz Yeah. It reminds me for Bairstow's method being explored in much detail, still waiting in the queue... The problem with these methods, is that my calculator doesn't support complex numbers, and I have to do it by hand.
excellent teaching! respect...
You give me the 3Blue1Brown vibes haha, loving what you do anyways, keep it up~
Excellent
u are a god
I still don't get it why does when you multiply all the roots of the quotient it is equal to using synthetic division
Is it just me or does he sound like 3blue1brown
I stopped halfway, then had to check the name as well.
I almost thought he is Grant tho
What about version for quadratic divisor ?
It would be helpful for deflation with quadratic with complex roots
Consider using Durand-Kerner (ua-cam.com/video/5JcpOj2KtWc/v-deo.html), Aberth-Ehrlich (ua-cam.com/video/XIzCzfMDSzk/v-deo.html), Laguerre's Method (ua-cam.com/video/blOARV4lnIM/v-deo.html), or Bairstow's Method (in the video queue).
@@OscarVeliz speaking the polynomial root finding , there is also eigenvalue method There are two companion matrices in upper Hessenberg form and two with lower Hessenberg form and we can apply QR method to one of them, QR decomposition can be easily derived by multiplication by rotation matrices - from left to get R matrix and from right to get Q matrix
How can I choose shift (without complex arithmetics) to accelerate the convergence
There also slow convergence with repeated roots
I wrote code for Bairstow's method based on one of the videos on youtube ,
I also wrote code for eigenvalues method but i probably didnt choose shift well and as stop condition i gave maximum number of iterations
This approach is space costly but is implemented in Octave and numpy and even they dont manage the repeated roots
Nice video. Unfortunately, I find the derivative of your words with respect to time higher than average wpm though applying Rolle's Theorem this is not absolutely true. Just kidding. Please keep on posting videos.
Hi, thank you so much for explaining, although I didn't get the Newton-Horners scheme - could somebody please tell me how did we get the new polynomials every restart of the method?
You use the quotient from Ruffin's Rule.
So we add use horner method to use newton method???
It depends. If you already have programmed a working Newton's Method, then you could use it as-is to find a single root (but it will be slightly inefficient). In order to deflate though you would have to apply Ruffini's Rule. But if you didn't want to use Horner's method, then you would need to divide your function call by the root you found, i.e. let newf(x) = f(x)/(x-r), as well as every other subsequent root that you find. For an example of using Newton-Horner, check out my implementation hosted in the channel's GitHub repository. The link is in the description.
@@OscarVeliz Thanks
Nice tutorial, next time explain history at the end for people who care,
Thank you so much for this video though!
You can simply forward the video. Don't Be Stingy.
I usually skip parts of the video till I get something I want, often skipping by 5 seconds or fast-forwarding.