Efficient Techniques for Finding Polynomial Roots
Discover various methods for efficiently finding polynomial roots, including deflation, Muller's method, Laguerre's method, and eigenvalue methods. Learn how these techniques reduce effort and minimize inaccuracy in root-finding processes, suitable for numerical analysis and computational mathematics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Root Finding Methods 9.5.0 9.5.4
Deflation Reduces effort of finding polynomial s roots As each root r is found, find Q(x) such that P(x) = (x r)Q(x) The roots of Q will be the remaining roots of P Q will be one degree lower than P This therefore reduces the effort required to find new roots Forward deflation new polynomial coefficients are computed from highest power to lowest Opposite for backward deflation Amounts to synthetic division Complex roots can be deflated by either converting to a complex data type, or deflating by a quadratic factor
Inaccuracy Since each iteration relies on the numerical accuracy of all previously found roots, errors can accumulate Error accumulation can be: stable plus or minus only a few multiples of the machine s precision unstable erosion of significant figures For stable deflation: forward deflation divide out the root of smallest absolute value backward deflation divide out the root of largest absolute value To further minimize errors, each root found should be treated as tentative, then polished later
Mullers Method Start with three arbitrary guesses ??, ?? 1, ?? 2 To find next approximation of the root: The sign in the denominator is chosen for greatest absolute value
Laguerres Method Assume that the root ?0 is some distance ? from the current guess ? ? ?0= ? where and ? is the order of the polynomial and the sign in the denominator (of 9.5.11) is chosen such that it has the highest absolute value Start with an arbitrary trial value ?, calculate ?, then use ? ? as the next trial value
Eigenvalue Methods The eigenvalues of a matrix are the roots of the characteristic polynomial ? ? = det[A ?I] Root finding is not an efficient way of finding eigenvalues, but finding eigenvalues is an efficient way of finding roots Create a matrix from the polynomial whose roots you wish to find Methods for finding eigenvalues, described in chapter 11, can then be used to find the eigenvalues of the new matrix, which are the roots of the original polynomial
