Date of Award
Dr. Jeffrey Ovall
Polynomials, Numerical analysis, Equations -- Numerical solutions
The problem of solving polynomial equations is one of the oldest problems in mathematics. Many ancient civilizations developed systems of algebra which included methods for solving linear equations. Around 2000 B.C.E. the Babylonians found a method for solving quadratic equations which is equivalent to the modern quadratic formula. Several Italian Renaissance mathematicians found general methods for finding roots of cubic and quartic polynomials. But it is known that there is no general formula for finding the roots of any polynomial of degree 5 or higher using only arithmetic operations and root extraction. Therefore, when presented with the problem of solving a fifth degree or higher polynomial equation, it is necessary to resort to numerical approximations.
The best existing numerical methods for polynomial root-finding are already able to produce accurate and precise results with errors on the order of machine precision. However, these methods assume that the polynomial coefficients are known exactly. In real-world situations where polynomial functions are used to interpolate measured data this is not the case. This leads to unacceptably large errors in the computed roots due to a phenomenon known as ill-conditioning, where small changes to the coefficients result in disproportionately large changes to the roots.
The objective of this research is to develop a methodology for finding polynomial roots with reasonable accuracy even in a real-world situation where the polynomial itself is not known exactly. This is achieved by using a change of basis; in other words, representing an arbitrary polynomial in terms of so-called Chebyshev polynomials. The proposed methodology is experimentally shown to tolerate uncertainties at least a thousand times larger than those which can be tolerated without using Chebyshev polynomials.
Tsai, Edison, "A Method for Reducing Ill-Conditioning of Polynomial Root Finding Using a Change of Basis" (2014). University Honors Theses. Paper 109.