In this diploma seminar we study the following polynomial zerofinders: Newton's method, Ostrowski's method and Laguerre's method. We will derive them via a constrained optimization problem and will also derive some new methods using the same approach: the improved Newton's method and the discrete Laguerre's method. We will prove some theorems that give us a bound on how far a magnified step for a given method can overshoot the smallest zero of a polynomial. We will test the methods numerically and compare them to one another. We will do that for the problem of finding the smallest eigenvalue of a symmetric tridiagonal matrix. We will compare the number of steps we need for a good approximation of the smallest eigenvalue, the time complexity of the methods and rate of convergence.
|
