Algorithms using a branch and bound method for finding all real solutions to an equation of one variable

Algorithms using a branch and bound method for finding all real solutions to an equation of one variable

0.00 Avg rating0 Votes
Article ID: iaor19881142
Country: Japan
Volume: 32
Issue: 1
Start Page Number: 16
End Page Number: 33
Publication Date: Mar 1989
Journal: Journal of the Operations Research Society of Japan
Authors:
Keywords: engineering, combinatorial analysis, programming: branch and bound
Abstract:

This paper, proposes algorithms using a branch and bound method for finding all real solutions to an equation f(x)=0 of one variable x on an interval [a,b]. P([c,d]) denotes the subproblem in which one finds all approximate solutions to f(x)=0 on [c,d]ℝ[a,b]. The algorithms repeat the following procedure for each subproblem P([c,d]) (the first subproblem is P([a,b])) until all the subproblems are terminated: If the subproblem is solved P([c,d]) then it is terminated, otherwise it is split into two new subproblems P[(c,e]) and P([e,d]) for e=(c+d)/2. Here the subproblem P([c,d]) can be solved when there is no solution of f(x)=0 on [c,d] or when there exists a solution of f(x)=0 on [c,d] and the width d-c is sufficiently small. It is assumed that there are two functions g(x) and h(x) such that f(x)=f(x)-h(x) and one of the following conditions holds: (1) The functions g(x) and h(x) are continuous and monotone increasing. (2) The first derivatives g'(x) and h'(x) are continuous and monotone increasing. (3) The second derivatives g“(x) and h”(x) are continuous and monotone increasing. Then new sufficient conditions are presented for the equation f(x)=0 to have to solution on [c,d]. Those conditions are used in the algorithms for solving subproblems. It is also shown that if the function f(x) is a sum of elementary functions then there exist the functions g(x) and h(x) which satisfy the above assumption. Furthermore sufficient conditions are given for the equation f(x)=0 to have exactly one solution on [c,d]. Two algorithms are proposed which solve the subproblem P([c,d]) efficiently when the conditions hold. [In Japanese.]

Reviews

Required fields are marked *. Your email address will not be published.