for this video it is recommended that you have some familiarity with
Graeffe's method horner's method and generalized newton's method
although not entirely necessary i recommend watching my videos
in 1920 bairstow published applied aerodynamics
in which he tries to solve this eighth degree polynomial relating to stability
notice reference to horner and graeffe we'll actually come back to this much of this video is
going to be based off of a chapter from elements of numerical analysis by peter henrici i've used
this for earlier videos such as generalized fixed point iteration and generalized aitken steffensen
every polynomial can be written as a quotient times a monomial
plus a remainder this is ruffini's rule when the remainder is zero a is a root
here's an example of x to the fifth minus eight x to the fourth minus 72 x cubed plus 382 x squared
plus 727 x minus 2310 we can rewrite that as this equation notice the remainder of zero
if we tried it with x minus three we need to get a remainder of 960 that's because if we
did this multiplication we'd be off by 960. you can also try to factor out a quadratic
with our original polynomial we can factor out x squared plus x minus six with a remainder of zero
when the remainder is zero that means we can solve for the roots of x squared plus x minus six
written as x squared minus u x minus v using the quadratic equation and this is kind of the heart
of bairstow's method recall that horner's method can be written as a synthetic division for example
p of two written in form of synthetic division means we bring down the one and then multiply one
times two adding negative eight plus 2 multiplying that by our 2 and adding and going and between the
pattern and so on giving a remainder of zero and our quotient as x to the fourth minus 6x cubed
minus 84x squared plus 214x plus 1155 that was synthetic division of one variable what about two
we'll write that factor as x squared minus ux minus v and as an example
we'll try using x squared plus x minus six meaning our u is negative one and v is six
and we'll use those in our synthetic division like last time bring down the one and then multiply
negative one against our one and we can't do anything with the six yet so we'll just add those
multiply our negative nine times our negative one giving us nine and now we have something
we can do our six so six times one gives us six add all three of our terms to get negative 57
nine times negative one six times negative nine adding our three terms and so on
giving remainders of zero
the result of that division means our quotient is x cubed minus nine x squared minus 57 x plus 385
with the quantity x minus u times our remainder of zero plus zero giving our polynomial
of course our zeroed terms go away meaning we can just solve for our quadratic
with our good old quadratic equation letting a be 1 b be one and c be minus six
plug everything we get the roots of two and negative three
and if you try plugging those into a polynomial you get zero and zero but hold on let's back up
further further still one more there how do we choose u of negative one and v of six
what if we had chosen different numbers like two and three well i'll go ahead
and fill in our synthetic division giving our quotient of this and a remainder of 888 and 72
if we do our multiplications of this quantity and our right side quantity and add them
together we get this polynomial which is our original one the real question then becomes
how do we find u and v that make our remainder equal to zero
let's first rewrite our polynomial so that our coefficients are known as a and our results are
known as b i'm going to fill in the rest of our synthetic division and the right side we can say
that b sub n is equal to a sub n plus u times b sub n minus one plus v times b sub n minus two
written more generally from two to n for all i what about this part that means b sub one is
a sub one plus u times b sub zero and the part on the left b sub zero is a sub zero
if we add in two temporary zeros which we'll call b sub minus two and b sub minus one this
gives us just one equation that's true for all i giving us our quotient written here and our
remainder with our last two b's what we want is for those last two b's to be equal to zero
this means we want these two equations to sum in zero this gives us a system of nonlinear equations
now you might be wondering why are they non-linear well if we just look at b sub n minus one that is
our previous equation and you can keep doing the substitution so the nonlinear nature shows up
we'll change our notation so that we have b's are equations based
of u and v and we'll set them equal to zero we can solve it using newton's method i have
made a video on generalized newton's method if you're interested this means we'll need to take
partial derivatives to compute our jacobian of every equation against every variable
rather than looking at the entire jacobian let's just look at b sub zero what is its
change in respect to u and the answer zero there isn't any the same is true with respect to v
what about b sub one how does that change in respect to u well it's b sub zero
and with respect to v there isn't any b sub two it's change in u is
b sub one plus u times b sub zero and for its change in v it's just b sub zero like we have
in the previous equation we can rewrite our changes to be called c sub i giving just
this equation and for clarity let's change that b sub zero into be c sub zero
for the change in v it's the one ahead of it
essentially what we're doing is another synthetic division
i'll go ahead and draw up our new synthetic division and apply u and v again to give our c's
filling in the rest of the table we actually aren't going to need that last c
though for efficiency we can just remove it and write our equation like this
if we go from zero to n minus one we also need to bring in those two temporary zeros
now for our jacobian which is what we were interested in they can be written as just
our c's and this is also why we didn't need c sub n because it's not needed for the jacobian
we then plug it into newton's method and we get this system
of equations which we can then solve for our delta u and delta v
going back to our non-zero remainder by letting u be 2 and v be 3 we'll apply a second
synthetic division and plug into our equations for delta u and delta v
we'll then apply those to our u and v to get new values for u and v in this case 1.615 and 13.245
can come with new values for b and c i'm not drawing the table but you could
and come up with a new delta u and delta v giving our new values for u being 2.15 and v being 15.18
if you kept iterating the process eventually it would converge on 2 and 15. with this being our
result our quotient times x squared minus 2x minus 15 plus zero remainder with this is our quotient
we actually then apply the quadratic equation to come up with the roots of negative three and five
we then repeat these steps with q being replaced with p and restart the process our repetition
converges after seven iterations giving u of 4 and v of 77 with our quotient being x minus
2. apply the quadratic equation we come up with roots of negative seven and eleven replace q with
p and you know since our degree is less than or equal to two actually can't try another
extraction of a quadratic so we'll just solve for the root directly in this case r is two
just a quick note on our quadratic equation formula since we are using x squared minus
u x minus v that means we can always assume a is 1 and we know that b is minus u and c is minus v
if we plug those into our equation we can simplify it just to be
u plus or minus the square root of u squared plus four v all over two
let's look at our algorithm more formally from our start given our coefficients of a the first
step we'll actually want to do is normalize a this will avoid normalization later and then check if
our degree is greater than or equal to three when it is we'll start by initializing u and b let's
talk about strategies for doing this in a bit but first let's just keep going down this branch b be
synthetic division of a using u and v and check if our last two b's were zero or close enough
if they aren't compute c delta u delta v and then update u and v like we did earlier
and compute a new b variable
when they are zero apply our quadratic equation and deflate our polynomial letting a be all of our
b's except for those last two and restart then we'll check if our polynomial is of degree two
when it is we'll apply the quadratic equation on our a and when it isn't
we'll solve for the root directly finally we can stop we found all of our roots
here's the real power of bairstow's method though let's use the polynomial of x to eighth plus 15
x to the fourth minus 16. doing one iteration of baristow we solve the roots of negative one
and one using our quotient we solve for another quadratic giving the roots of negative i and i
our next set of roots are square root of two plus or minus square root of 2i
and our last set of roots is negative square root 2 plus or minus square root of 2i
bairstow's method is able to find complex roots which is the true power of the method
there was still the question though of how do you pick good starting u and v values
let's visualize the starting u and v values for this function creating a
fractal showing the number of iterations is taking to converge based off of color
this is not the complex plane our horizontal is our u and our vertical is our v
giving quite the stunning geometry what if we changed our function
here is x cubed minus one showing much more chaotic behavior
and this is x to the fourth plus one with quite stunning symmetry and a lot of chaotic
behavior meaning small changes in your u and v can leads to nicely converging
or taking a very long time to converge [or diverge]
here are some of the ways that i might recommend picking good views and v's
one is just to always start with one and one a more sophisticated version might try taking
the square root of the largest term and then using our negative u as our v you actually might
be better off taking an educated guess but the actual best approach
is to first approximate our complex pairs and reverse engineers those terms
henrici writes for most polynomials even crude approximations to quadratic factors are hard to
obtain by mere inspection we shall discuss a method that will automatically produce
good first approximations to quadratic factors with complex zeros of almost any
real polynomial referring to bernoulli's method and quotient difference algorithm
let me know if these are videos that you want me to make
as promised we're coming back to bairstow and see how he's solved
first our eighth degree equation he applies graeffe's method using root squaring
to come up with one negative root and a second negative root followed by six complex roots
he then uses those real terms and deflates the polynomial using horner's method
after deflation he then computes three quadratic vectors
with the help of two computers it took about three hours
of course this is only using graeffe's method what happened to bairstow's method?
well ... i'll let you read this paragraph but essentially he starts with those
quadratic terms and then tries to find a method to make them more accurate
using two synthetic divisions to compute deltas and then updating the quadratic
that looks a lot like the method we just talked about repeating the process to come
up with a new version of that quadratic and one more step if you're curious these are the
actual steps and the final routes that you that you would find using bairstow's method
he writes the method of an approximation will be seen to correspond with newton's method of
approximation to the value of real roots and it is greatly assisted by the use of a calculating
machine [skipping ahead] all such methods require special consideration in the case of repeated
roots but such cases are not sufficiently common occurrence to make detailed discussion necessary
bairstow devised this method in 1920 and you can use it to solve for two roots at once
it also works on complex roots and uses two variable synthetic division like graeffe it
only uses their coefficients and like horner it deflates using a quotient i do want to highlight
though that at no point does bairstow's method ever actually evaluate the polynomial
maybe at the end if you want to check your answer it's also good to have initial
starting values for u and v and you can visualize those behaviors by creating fractals
if you're interested also check out duron kerner the aberth-ehrlich and jenkins-traub
the code i wrote as well the fractals i created will be hosted on github
thank you for watching i had actually been wanting to make this video for a long time but needed to
wait until i covered newton's method for systems and nonlinear equations and graeffe's method
let me know what you thought of this video in the comments below and again thank you for watching