Interval Methods for Bounding the Range of Polynomials and Solving Systems of Nonlinear Equations
Volker Stahl · 2007
This thesis describes systematically known and new results on bounding the range of polynomials and solving systems of nonlinear equations using interval methods Range of Polynomials Bounding the range of polynomials is an important sub problem in many disciplines of scienti c computing The main original results of this thesis are as follows Centered Form We give a new more elementary proof of the known quadratic convergence of centered forms Horner Form For every polynomial f there exists an interval Of such that for every interval X whose interior is disjoint fromOf the Horner evaluation of f onX is exact The smallest such Of is the hull of all roots of the intermediate polynomials arising during the Horner evaluation of f During evaluation of f on X this non overestimation condition can be decided without additional computation We failed to nd a necessary and su cient non overestimation condition but found some further su cient conditions If the input interval of the Horner form contains zero then we bisect it at zero and evaluate both parts separately As both parts have one endpoint zero the total cost for both evaluations is comparable to the cost of the ordinary Horner form but gives usually tighter inclusions If the dense Horner form evaluated on X overestimates then any bisection of X gives an improvement If X is centered then bisection at the midpoint reduces the overestimation error of the dense Horner form at least by half This observation is used to reduce the overestimation error of the dense Taylor form at least by half Mean Value Form The width of the mean value form is the same for any choice of a center between the optimal centers of the bicentered mean value form This width is smaller than if the center is chosen di erently Hence the midpoint is a width optimal center for the mean value form Bernstein Form For the Bernstein form we show that it is inclusion monotone and that it gives the exact range provided the input interval is small enough If the input interval contains zero we bisect it at zero and evaluate the parts separately This gives tighter inclusions and allows faster evaluation because each sub interval has one endpoint zero and hence the Taylor coe cient computation is trivial Interpolation Form We present some accuracy improvements of interpolation forms by combining them with the concept of slopes and bicentered forms Nested Form For multivariate polynomials we de ne the nested form which is motivated by eliminating common subexpressions and by exploiting the subdistributivity law It is roughly as accurate as the Horner form but less expensive Experimental Comparison Finally we compare various univariate and multivariate range computa tion methods experimentally in the context of Newton s method and a global optimization algorithm Therefore we give an implementation of extended interval arithmetic on top of the IEEE standard and prove its correctness Solution of Systems of Equations The second part of the thesis is devoted to solving systems of nonlinear equations Our contribution is as follows Acceleration In order to accelerate the known algorithms we introduce a new operation called tigh tening The idea is to evaluate a multivariate equation in all variables except for one on the given box and to solve the obtained univariate interval equation Tightening can be applied directly to the given equations or to linearizations of them When applied to linearizations tightening is equivalent to the non preconditioned Hansen Sengupta operator with a di erent strategy for choosing equa tions and variables We give a uniform and geometric framework for linearized tightening and the Hansen Sengupta operator Then we give a new condition for non existence of solutions for linearized tightening According to experimental results tightening usually leads to signi cant speedups Termination Certain interval methods fail to terminate if the search space is decomposed in such a way that a solution lies on the boundary of some sub box We solve this problem by slightly enlarging the given box X obtaining X testing whether the Hansen Sengupta operator converges starting from X and if so iterating until we obtain a box Y which is either in the interior of X or disjoint fromX We prove correctness and termination of this algorithm under the assumption that the system has only nitely many simple solutions and the oating point number accuracy is high enough Application to Robotics We apply the techniques developed above to the robot inverse kinematics prob lem Exploiting the inherent structure of this problem results in a signi cant e ciency improvement Experimental results of a parallel implementation on a workstation network and on a super computer using PVM are reported