Bairstow's Method

[@OutbackCatgirl]

love it :3 consider speaking slower and enunciating a little more, there were parts i had to rewatch. otherwise lovely work

[@karolleszynski1963]

Best stuff i could find on yt. Well done

[@MATHsegnale]

Wow! I was not aware of this method! The example when you were able to factor out an irreducible polynomial of degree 2 is great! Thank you!

[@NoNTr1v1aL]

Absolutely amazing video! Subscribed.

[@leesweets4110]

Could you cover Vincent's method of polynomial root finding? The p_{n+1} = x^n * p_{n}( h + 1/x), counting sign changes and generating a continued fraction of the root? The Vincents method article in wikipedia is rather weak, imo. You can actually find more details on it in the "Root Isolation" article. I dont know if you distinguish root isolation from root finding, but the approach actually hones in on individual roots as tightly as you want. Nevertheless I still find it rather confusing and difficult to implement.

[@OscarVeliz]

Adding it to the queue. Thanks for the suggestion.

[@leesweets4110]

@@OscarVeliz Youre very welcome.

[@uzivatel123]

amazing channel

[@alexandrevachon541]

I've been waiting a long time for this. It is quite well explained, and worthy of being a potential winner of Summer of Maths Exposition II. For the Jacobian multiplied by the 2x1 matrix, Cramer's rule would also have done the trick for the iteration process.

[@alexandrevachon541]

Also to mention that if you add a relaxation parameter for the Newton iteration, you can make fractal spirals from Bairstow's method!

[@OscarVeliz]

Solving with Cramer is an elegant approach. Definitely a good idea to use the relaxation variable as well. I actually wanted to make this video right after Horner. Once I started researching and saw that Bairstow used Graeffe and Generalized Newton's Method, I decided to shelve it until after I could make a series on nonlinear systems; when I could make a new series devoted to polynomials. Thanks for the SoME2 well-wishes 🤞

[@alexandrevachon541]

@@OscarVeliz I hope that making fractals from the Jenkins-Traub algorithm is possible...

[@leesweets4110]

@@OscarVeliz What are we talking about? Do you have a video? Im sincerely interested in this topic now that its been mentioned.

[@symbolspangaea]

Thank you! really interesing topic

[@nzuckman]

I wonder if you could figure out good starting values of u and v statistically by sampling the fractals they make for some set of polynomials, and picking out the non-chaotic regions to make a sort of heat map or histogram of good u and v values. 🤔

[@OscarVeliz]

It is an entriguing idea supposing that polynomials of the same degree will behave similarly. Another way to alter the fractal might be to color-code based on which pair of roots were converged to.

[@abdoulkarenzo3138]

Thx prof , can you apload the videos about interpolation

[@AJ-et3vf]

Awesome video! Thank you!

[@OscarVeliz]

Thanks for always watching.

[@alexandrevachon541]

I had an amazing idea: what if we combine Bairstow's and Broyden's methods to make a hybrid method? Or make a variant that has Halley's method in it? Also to point out that it only works with polynomials, like Laguerre, Horner, Durand-Kerner and Aberth-Ehrlich, as well as Jenkins-Traub. However, if you want to use sin(x) and cos(x), then the best you could do is to approximate it using Taylor series. Speaking of Jenkins-Traub, I doubt anyone has ever tried to make fractals using this algorithm. Is it possible?

[@OscarVeliz]

Using Broyden instead of Newton for Bairstow is somewhat redundant since most of the motiviation for Broyden is that the Jacobian is difficult to find and invert. In this case, applying Newton is no trouble since it gives direct formulas for Δu and Δv. Replacing the Newton approach with Halley on the other hand sounds like it could make for a significant speedup at the tradeoff for complexity. It isn't something I have seen someone do yet I don't see why not. It is worth investigating. Correct, Bairstow's Method only applies to finding the roots of polynomials. For other functions, they can be proxied by using Taylor Series. I'm still wrapping my head around Jenkins-Traub so I am unsure. Currently, I am in the process of moving so I have less time than I would like to work on videos.

[@jacknguyen5220]

I've implemented this before myself for real polynomial factoring. The way I dealt with divergence was with a basic divergence check followed by a re-initialization, which usually works in a few tries but can still struggle in some cases. The other problem I've faced is the fact that polynomial division has a tendency to accumulate a lot of error, causing later factors to become significantly less accurate than the first few factors. I'd definitely love to know some ways to tackle these issues.

[@OscarVeliz]

Random restart in the case of divergence is a good strategy. Finding a close approximation using something like Bernoulli's Method usually also works. One way to avoid that compounding error is to fine tune the quadratic factors against the original polynomial.