Root isolation methods based upon lagrangian interpolation

Abstract

Two new methods for root isolation are presented. The methods apply to certain real-valued functions of one real variable. Each method takes a function and an interval and returns a set of subintervals in which roots are likely to occur. The methods are proven correct in exact arithmetic, i.e., each root of the function on the interval will be found in one of the subintervals returned. Both methods are based upon Lagrangian interpolation. The first method uses linear interpolation, requires that the function have two continuous derivatives and requires that the user give a bound on the absolute value of the second derivative. The second method uses quadratic interpolation and has similar requirements on the third derivative. The methods use only functional evaluations and the given bounds on derivatives; no other information about the function is required. An implementation is discussed and sample test cases are given which demonstrate the efficiency and utility of the methods. Future research on the use of the methods is also considered.

Keywords:

• Root isolation
• Lagrangian interpolation
• derivative
• convergence

C.R. Categories:

• G. 1 Numerical Analysis