Root-finding Method Research Based On Interpolation

The root-finding problem of nonlinear equations is one of the basic problems in the fields of computational mathematics and engineering calculation.It has very wide applications in computer graphics,computer aided design and scientific computing.For example,collision detection,ray tracing and fluid simulation in graphics,can be summed up as a root-finding problem of nonlinear equations.This thesis focuses on the root-finding problem of a univariate nonlinear equation f?x?= 0,and the main context includes:?1?An approximation method based on polynomial interpolationGiven f?x?,two bounding polynomials G₀?x?and G₁?x? such that G₀?x??f?x??G₁?x? are obtained by interpolating several points of f?x?.It is applied for obtaining a series of two-side inequality of special functions sinc?x?and arcsin?x?,and the results are better than those of the existing methods.Because the roots of a function can be bounded by those of its bounding polynomials,the new method can also be directly applied for the root-finding problem of nonlinear equations.In principle,it can directly construct bounding polynomials under certain conditions,and also works for non-polynomial cases.?2?A progressive root-finding method for nonlinear equations which is based on Newton-Pad??? ApproximationThe Newton's method has wide applications,while the result depends on the initial value and may cause divergence.This paper discusses a progressive root-finding method based on Newton-Pad??? Approximation.It calculates the root of a series of rational functions of the form[1/i-3]_f,i= 3,4,… + 1,which continuously approach the root of f?x?in the given interval.The derivation process of the iterative formula are also given,and the convergence order of the method is proved to be 2^n-1,where n?>2?is the number of the functional evaluations.Numerical examples are given to compare with different methods,and it shows that the new method can achieve higher convergence rate and better computational stability.?3?A root-finding method based on the reparameterization techniqueIn prevailing root-finding methods,the iterative formula is often transformed into the solution of a equation h(x_i,x_i+1)= 0,which is not easy to achieve a high convergence rate.This paper presents a new root-finding method based on the reparameterization technique,the basic idea is to progressively construct reparameterization functions X_i+1=?_i?x_i?,which are given in explicit formulae.The calculation process of x_i+1=?_i?x_i? is relatively convenient,and easy to take a high convergence rate.In principle,the reparameterization-based method achieves the convergence rate 3·2^n-3 and each iterative step costs less computation time than prevailing clipping methods.Numerical results show that the new method can achieve better performance.