Halley's Method

[@OscarVeliz]

Corrections: The example at 8:08 had an error with the programming of f'(x). The bug caused the numbers in the table and the plots for that example to be incorrect. A video with a fixed example will be posted soon. There is a separate issue in that example where 2 was written as the input instead of -2. Also there is typo in the name Christopher Wren at 0:46.

[@weiyuanwu9044]

5:30 d=2f'(xn)^2 - f(xn)f''(xn), the square is missing for the first term.

[@SubhomoyHaldar]

Thank you for maintaining this gem of a channel!

[@AJ-et3vf]

Amazing channel. Thanks for this video about Halley's method. Amazing to know that it uses tangent hyperbolas to approximate the root. The Fractals toward the end are surreally beautiful!

[@hossiluc]

Majestic, thanks for the explanation

[@xamogxusx]

your channel is golden!

[@alexandrevachon541]

I did a little experimenting by modifying Halley's method formula by changing the value of 2 in both the numerator and the denominator. I call this value k, and the order of convergence changes when this value is changed: if k = -1, then the converging order is superlinear/subquadratic (around 1.617); if k = 1, then it's Schröder's method with quadratic convergence; if k = 2, then it's the standard Halley's method. If you increase the value closer to infinity or to negative infinity, then the function will ultimately end up having quadratic convergence. Formula : x_n+1 = x_n - (k*f(x_n)*f'(x_n))/(k*f'(x_n)^2-f(x_n)*f''(x_n)), where k is not equal to zero, because if it is, then the function will not converge, and gets stuck to the initial value. Have you tried that before?

[@OscarVeliz]

Were you evaluating the order numerically or theoretically? I mean did you prove it for all f or try it on a specific function?

[@alexandrevachon541]

@@OscarVeliz While I was at school, I proved it numerically: with the function x^3 - 1, and an epsilon of 10^-9, it converged in 5 iterations (alpha = 2, that's Schröder's method). With k = 2, that's Halley's method. With k = 3, it needs 4 iterations (alpha close to 2), so is k = 4. But what if these were non-integers or negative numbers? With k = -1, it converged in six iterations, this time with an alpha of around 1.617. With k = 1.5, it still converged with a near-quadratic order. My assumptions turned out better than I expected, but k must not be bigger than -1 and smaller than 1, otherwise it will not converge.

[@OscarVeliz]

The trouble with applying the order formula numerically, is that it doesn't provide a rigorous proof. It only shows that for a given function & sequence it converged with a certain order; but it doesn't give a general truth. For that, you would need to perform serious analysis similar to the proofs in the papers I reference. I normally don't cover these proofs in videos because I want to keep them short. Plus I don't think they are entirely necessary for someone learning a method, rather that a proof exists and that you can look it up if needed.

[@alexandrevachon541]

@@OscarVeliz Thanks for the advice.

[@wailmohamed8412]

amazing passion you have here! I'd suggest using better visuals and voice recorders. its great overall.

[@johnphilmore7269]

Hey Oscar! Just a quick correction: at your derivation of a,b,c, and d of the tangent hyperbola, you forgot a “^2 “ behind the “2f’(x_n)”in the equation for d. The other slides should be fine tho

[@OscarVeliz]

Thanks for point this out. There are actually a few other errors in this video that I didn't catch kzbin.info/www/bejne/apvaYZagmcmgeJo

[@johnphilmore7269]

@@OscarVeliz yeah I had a look as well at that one. Honestly I really appreciate the series. I will say, it’s been super enlightening. I’m a mathematician myself specializing in numerical analysis. As a question, I see that you also posted some multivariate algorithms. Now personally I don’t like Newton. It’s fast, yes, but it has too many failures to be applicable everywhere. Bisection is much more reliable in 1D but that goes out the window with 2D and beyond. There are algorithms that employ the Poincare Miranda Theorem to get something similar to it, but it still isn’t as reliable as before I believe. My question to you then is, what’s the most reliable method you know of in multiple dimension? Something that may be able to be combined with Newton in order to get a multivariate New Safe

[@OscarVeliz]

Sorry for not responding sooner. I just posted a new video on a more reliable verson of Newton's Method for systems kzbin.info/www/bejne/eHi9l3uur79gbcU

[@johnphilmore7269]

@@OscarVeliz I know I’ve been enjoying it greatly

[@OscarVeliz]

I got a notification that you had made another comment but it isn't showing up for me. This sometimes happens if you include links as KZbin automatically removes them for safety reasons.

[@timdudd5996]

At 8:06 I'm pretty sure that f'(-2) = 15, not 16.

[@OscarVeliz]

You are correct. I looked at my notes and found I programmed f' as 3x^2-2x instead of 3x^2-2x-1. This also impacts the plots of Newton and Halley for that example. Thank you for pointing this out. I will make fixes to the GitHub documentation, the plot in the repository, and soon I will post another video with this and other corrections.

[@physicshuman9808]

6:59 We can plug-in more and more terms and make our rate of convergence as high as we want

[@aneeshsrinivas9088]

whats the multivariable equivilent of this.

[@OscarVeliz]

I have a video on the multivariable version kzbin.info/www/bejne/rIeQaZaqoLJ0j5I

[@aneeshsrinivas9088]

Am I rite in assuming that we are approximating our function with curves of the form (a+bx+cy)/(1+dx+ey)

[@OscarVeliz]

There are many ways to derive the method. I covered a few in this video.

[@Ah7ed]

Professor, if you please, can you contact me? I need help.