hello Internet Oscar Veliz again this time with a video on Horner's method
first we'll go over a brief history of it then talk about how to evaluate
polynomials and lastly how to find roots Horner's method is credited to William
George Horner who published a new method of solving numerical equations of all
orders by contains approximations in 1819 although the method had previously
been found by Paolo Ruffini in 1804 they actually had been discovered even before
then and I'm gonna apologize right now for my pronunciations of names in the
11th century al-Nawasi created his own method similar Horner's that solved for
cubic roots and then in the 14th century al-Kashi extended that to solve for roots
of higher degree al-Tusi and al-Samaw'al also figured out their own approaches that
are similar to Horner's method for solving nth-roots around this same time
in China Qin Jiushao published a treatise in 1247 that had a way similar
to Horner's that could solve roots up to 10th order earlier in the 12th century
another al-Tusi wrote a book that also included something similar Horner's
method going back to china in the 11th century Jia Xian wrote a book that's
been lost to history but is also supposed to have included Horner's
method there's also evidence that Yang Hui Li Ye and Zhu Shijie again so
sorry for my pronunciation also solved polynomials in a way similar to Horner
and probably the earliest example of Horner's method comes from chapter 4 of
the nine chapters on the mathematical art which is an ancient Chinese text and
there are likely other examples of Horner's method being discover earlier
but to make a long story short I'll leave you with this quote that says both
Ruffini and Horner were blissfully unaware that they were rediscovering a
method which could be traced back 17th centuries before we start talking about
the method let's first define what we knew at a function and the polynomial so
a function is any function that you can think of mathematically something like
sine of e to the X plus the natural log of 1 over X square plus 1 while a polynomial
is specifically an addition and multiplication of powers of coefficients
so something like d x cubed + c x squared plus b x plus a you've seen these a lot
when we evaluate polymer this can be slow you'll notice that the last
operation requires three editions and six multiplications so every X to the N
term ads n more multiplications the idea behind Horner's method is that
we'll rearrange our polynomial so if our polynomial looks like this we can factor
out an X from the last two terms and factor out an X again this leaves us
with three additions and three multiplications so it's a lot faster it
if we write it in terms of a sub n you could represent it normally like this or
rewrite it in terms like this recursively it will look something like
this let's look at an example this rewrite and evaluation process if we
take this polynomial will first rewrite it then if you want to evaluate the
polynomial let's say three we'll simply plug in three where we had X's then we
start evaluating the polynomial for this example P of 3 is equal to 960
let's evaluate that same polynomial at another value this case - we'll take
our polynomial and plug in 2 now I'm not going to show every operation here but I
want you to keep track of these numbers first 1 -6 -84 214 1155 and finally
0 so P of 2 is equal to 0 this means that 2 is a root you may see Horner's
method represented as synthetic division where we take our polynomial and keep
track of the coefficients and evaluate it at a certain value
here's how we'll do that first we take our value and put it on the left side
then write all of our coefficients next to it
first we'll bring down the first coefficient then multiply that
coefficient by the value we're searching for this case two and store it next to it
then we do addition and repeat the process so now I'll multiply this -6
times two store it to the right and we get -12 then we add it again
and so on and so forth notice the same numbers 1 -6 -84 214 155 and
0 so we know that P of 2 is equal to 0 but we also found the quotient Q with
X to the fourth minus 6 X to the third minus 84 x squared plus 214x plus 1155
this is a basis of Ruffini's Rule we evaluated a polynomial at the value 2
what we did was essentially divide that polynomial by X minus 2 and we found
these numbers they came from this if we took our polynomial and rewrite it in
terms of its roots we divide out that X minus 2 and we're left with these values
which we can expand to be the quotient that we found Ruffini's Rule says that
every polynomial is a quotient times a binomial plus a remainder so for example
polynomial that we've been using our first example was 3 so we write x minus
3 and a remainder of 960 and this was our quotient notice that P of 3 is equal
to 960 with P of 2 we found this quotient X minus 2 and remainder of 0
notice that P of 2 is equal to 0 so P of at whatever value a is equal to our
remainder and this is the basis of ruffini's rule that P of X is equal to Q
of X times X minus a plus P of a Ruffini's Rule also lets us compute the
derivative of a polynomial so if you start with Ruffini's Rule and take
the derivative of both sides we expand it using the product rule then we can
simplify this since P of a is a constant so the derivative that is 0 which we can
then simplify further notice the still requires another derivative the
derivative Q if you plug in a now we have a minus a which simply gives us the
derivative P at a is equal to Q at a here's an example the derivative process
in action let's use our same polynomial and compute its derivative using the
power rule which is this in which we can simplify to that polynomial there if you
evaluate at say the value of 2 we're given the value of 1215 if you use
Ruffin's rule instead we compute the quotient then plug in 2 and this gives
us the value of 1215 using what we know now let's talk about finding the roots
of polynomials in three different ways the algebraic way the rational root
theorem and using Newton's method the algebraic way is quite simple and
you've probably done it if for our polynomial second order we can use the
quadratic equation if it's third order we can use the cubic equation which has
a little bit longer discriminant if it's fourth order the discriminant becomes a
lot longer and if it's fifth order there actually is it an algebraic way to solve
it this is actually in the proved by the Abel-Ruffini Theorem we could instead
use the rational root theorem which says given a polynomial we test that
polynomial at every combination of values of the integer factors of a sub
zero divided by the integer factors of a sub n both positive and negative
for example polynomial all this means all the combinations of the integer
factors of 2310 divided by the energy factors of 1 which gives us these 64
test points which actually can find the roots but as the name implies this won't
work for irrational roots and the larger your numbers the more test points you
have [assuming not prime] let's instead use Newton's method but apply it to polynomials if you
haven't seen my video on Newton's method I recommend you watch it now since we're
using Newton's method we'll need the derivative which you can find using
either the power rule or ruffini's rule and whenever we evaluate a polynomial
you'll want to use Horner's method as for starting points if you have a nice
mixture of positive and negative coefficients this means your roots are
they're all negative or positive and negative so you can start at zero as a
good test point otherwise you might try using the an through of the largest
coefficient or use one of the points from the rational root theorem
whatever the case once you do find an answer from Newton's method try rounding
it with the polynomial to see if that gives you a better result then once
you've found a good enough root deflate the polynomial using ruffini's rule and
restart the process let's take our example polynomial find the derivative
in this case we'll use power rule and plug it into Newton's Horner method
starting at zero the first iteration gives us 3.17 the
second 0.86 the third two point something until we get to
1.999..98 in this case we'll actually want to round the
root to be two because that'll give us a better answer
then we'll deflate a original polynomial using the root that we found in this case
we'll make the quotient that we found using two be our new polynomial restart
the Newton-Horner method find a root of -7 deflate again find the root
deflate find the roots deflate find the root this gives us all of our roots of
-7 -3 2 5 and 11 some things to keep in mind the coefficients
that you're using don't have to be integers they were just so for our test cases and
also Newton's method can still diverge but you get quadratic convergence every
time you find a root you also can compute P of a and Q of a at the same time for
efficiency and this method will only find real roots if you need complex
roots you can use Muller's method or Bairstow's method and the code that I
used will be hosted on github sincerely thank you for watching if you have any
questions or comments about the video please be sure to leave them below or if
you have suggestions for future videos I always enjoy hearing from you
For more infomation >> Finale Massenmigration offenbar beschlossen (von Eva Herman) | 01.08.2018 | www.kla.tv/12800 - Duration: 5:28. 
For more infomation >> [ MATCH 105 ] du FIVE SONGS - Duration: 5:46. 
For more infomation >> Darısı Başımıza Final - Duration: 1:07. 
For more infomation >> أغنية شارة محققو الحيوانات مع الكلمات - Duration: 1:45. 
For more infomation >> VENOM TRAILER 2 | ORIGEM DO SIMBIONTE RIOT - CENAS ANALISADAS - Jujuba ATÔMICA - Duration: 12:31. 
For more infomation >> "Ghajinikanth" Premiere Show | Special Show | Arya | Sayesha | Santhosh P.Jayakumar | Kalakkalcinema - Duration: 2:31. 
For more infomation >> Search warrants reveal more about deadly crash - Duration: 1:48. 
Không có nhận xét nào:
Đăng nhận xét