Font Size: a A A

Geometric Methods For Computing Real Roots Of A Non-linear Equationls

Posted on:2018-11-25Degree:MasterType:Thesis
Country:ChinaCandidate:Y B ZhangFull Text:PDF
GTID:2310330512476941Subject:Computer technology
Abstract/Summary:PDF Full Text Request
The root-finding problem of nonlinear equation system is one of fundamental problem in mathematics and engineering computation,and it has wide applications in computer graphics,computer-aided design and scientific calculation.Many problems,such as collision detection in games and fluid simulation in virtual reality,can be generalized as a root-finding problem of nonlinear equations.In this work,we focus on the root-finding problem of a univariate nonlinear equation,and the main context includes two parts.Firstly,we discuss progressive interpolation method for the root-finding problem of nonlinear equations.Newton type's methods are widely applied in the root-finding problem,while its result is dependent on the selection of the initial values,which may cause divergence.In this work,we discuss the progressive interpolation method,which utilizes rational polynomials to progressive interpolate more and more points of the given function and leads to good approximation affect;it ensures that the interpolation polynomials also have real roots which can be well-approximated to roots of the given function.There is no computation of derivatives.It can achieve 3*2n-3 convergence rate by using n functional computations.Numerical examples show that it can achieve higher efficiency index and better computational robustness.Secondly,we provide new method based on rational polynomial clipping for the root-finding problem of nonlinear equations.The algorithms of many previous clipping methods has three steps.Firstly,it computes two bounding polynomials.Secondly,it divides the given interval into several subintervals by using the roots of the bounding polynomials.Finally,it clips the subintervals containing no roots.The convergence rate may be decreased for the multiple root cases.For a non-polynomial case,the computation of bounding polynomials may be even more difficult than the corresponding root-finding problem,and it is hard to extend previous clipping methods to the root-finding problem of non-polynomials.In this work,we present a new method which directly bounds the real roots of the given function f(t)It inherits the advantages of polynomial-clipping methods,and it can be easily extended to the root-finding problem of non-polynomials;furthermore,it computes the root of f(t)/f'(t)instead f(t),which leads to a much higher convergence rate even for the multiple root cases.Numerical results show that the higher convergence rate and the better efficiency index of the new method.
Keywords/Search Tags:root-finding, progressive interpolation, polynomial clipping, bounding polynomial, efficiency index
PDF Full Text Request
Related items