Householder's Method

Chapters
0:00 Intro
0:25 Derivation
1:58 History
2:34 Householder's Method
4:07 Householder's Method Example
4:41 Higher Order Householder's Method Examples
5:30 Principles of Numerical Analysis
6:03 Householder Fractals
8:10 Summary
8:41 Thank You

Suggested Videos:

Reference:

#HouseholdersMethod #NumericalAnalysis

[rasm]

Hey, mate! Thanks a lot for the videos - this is exactly what I was looking for. I know, some people are complaining that you cover a lot of methods for the same problem, but this is precisely the place to go, if you want to write highly specialized and efficient code for that particular problem. You saved me so much time by researching all these methods and comparing them! Just one minor hint: I think your comparison at 4:40 would have profited a lot if you got into a more concrete speed analysis: I mean H3 needs only half of the steps of H1, but it also needs roughly 6 times more operations at every step, so in this case Newton would be the clear winner - even though it has lesser convergence order.

[AJ-etvf]

As always, great videos with great visuals towards the end with the fractals.

[Vtalt]

Another approach is to simply expand the inverse of y=f(x) in a Taylor series at Xn and put y=0. The first few terms of the series are Truncating the series at k-th term you get recurrence relation with k+1 order of convergence. The linear term X(n+1)=Xn-f(xn)/f’(xn) corresponds to Newton’s method. Adding another term you get the recurrence with cubic convergence and so on.

[cboniefbr]

As always, great video. I love implementing code for these methods.

[ralvarezb]

I successfully implemented arbitrary order Householder method for polynomials with no symbolic calculations In python. Just calculating the derivatives of inverse function recursively. I have the same results as you with the polynomials and starting points taken from your video, but at some high order, the iterations diverges instead, I guess there are some floating point roundoff errors. Roughly speaking, In my tests there is no convergence if Householder order > Polynomial order /2. For example with polynomial at minute 4:54, I have divergence if d > 4, otherwhise the results are the same.
I take à look into your code and I can see you perform lot of symbolic calculations which leads me to reinforce this hypothesis.
I didn't yet made error propagation analysis but I have fractions with huge polynomials, may be expressing these rational polynomial functions in continuous fraction form can alleviate the problem...
For now, I'm thinking about some kind of "semi-symbolic" algorithm applying the recurrence relations that I found and working with abstract programming objects who represents the polynomial derivatives .... or may be using automatic differentiation and computation graphs

[alexandrevachon]

How do I find the fourth order Householder method? Doing so is much harder than orders 1, 2 and 3.

[StevenSiew]

Man! Householder method order 4 and 5 is complicated to calculate the form of using Mathematica. I can see why now, nobody publishes it on the online websites!!!

[benhur]

If I may ask, why did you use both Newton's and Halley's method instead of simply applying Halley's twice? Does the formula blow up in the face that much you can't really write it down anymore or is there some deeper reason to it?

[aneeshsrinivas]

if halleys method was derived from linear over linear pade approximants, what were the higher order halleys method derived from. for the method of order 3 was it a linear over quadratic approximaant, for order 4 is it linear over cubic etc etc.

[NourAlnour-fm]

Oh thank you
But I have a question
How can i know when i found the solve i need
I mean when i should to stop?? How can i know this x i need