 Font Size: a A A

# Root-finding Method Research Based On Interpolation

Posted on:2019-11-25Degree:MasterType:Thesis
Country:ChinaCandidate:J E ShiFull Text:PDF
GTID:2370330548476393Subject:Computer Science and Technology
Abstract/Summary: PDF Full Text Request
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 G0?x?and G1?x? such that G0?x??f?x??G1?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 2n-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(xi,xi+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 Xi+1=?i?xi?,which are given in explicit formulae.The calculation process of xi+1=?i?xi? is relatively convenient,and easy to take a high convergence rate.In principle,the reparameterization-based method achieves the convergence rate 3·2n-3 and each iterative step costs less computation time than prevailing clipping methods.Numerical results show that the new method can achieve better performance.
Keywords/Search Tags:root-finding, progressive interpolation, bounding polynomial, efficiency index, Newton-Pad(?) approximation PDF Full Text Request
Related items
 1 Geometric Methods For Computing Real Roots Of A Non-linear Equationls 2 Progressive Interpolation And Smoothing Of Subdivision Surfaces 3 Newton Bases For Multivariate Polynomial Interpolation 4 The Interpolation Approximation Of Some Unsmooth Functions 5 The Convergence Orders Of Hermite And Lagrange Type Newton Methods And Their Optimal Formats 6 On Efficiency Analysis Of Newton-PCG Like Algorithms 7 Geometric Calculation Based On The Mixed Polynomial Interpolation And Approximation, 8 The Research On Application Of Barycentric Interpolation 9 The Derivative Approximation Of Interpolation Operators 10 A Family Of Multi-point Methods With Memory For Solving Nonlinear Equations