Implementation and comparison of methods for real root isolation of univariate polynomials

Abstract

Sturm ve sürekli kesir yöntemi (CF) tek değişkenli polinomlarda reel kök izolasyonu (her kök için ayrık aralıklar bulmak) için yaygın olarak kullanılan iki yöntemdir. Yöntemlerin performansı polinom derecesine, köklerin yakınlığına ve katsayı büyüklüğüne bağlıdır. Kök sınırları seçimi de performansı etkilemektedir. Bu çalışmada bu parametrelerin kök izolasyon yöntemi performansını nasıl etkilediği incelenmiştir. CF yönteminin genel olarak daha iyi performans gösterdiği bilinmektedir.There are mainly two methods to isolate the real roots of a polynomial, i.e., to find separate intervals for all real roots so that each interval has only one real root. These are Sturm's method and method of continued fractions. The performance of the methods depends on the degree, root separation, and coefficient sizes of polynomial. The selection of the bounds also affects the performance. In this thesis we study how do these parameters affect the performance of the real root isolation methods. It is known that performance of continued fractions method is better in many cases.