7.1 Brute Force Methods
177
7.1.1 Brute Force Root Finding
Assume that we have a set of points along the curve of a continuous function f (x):
We want to solve f (x) = 0, i.e., find the points x where f crosses the x axis.
A brute force algorithm is to run through all points on the curve and check if one
point is below the x axis and if the next point is above the x axis, or the other way
around. If this is found to be the case, we know that, when f is continuous, it has to
cross the x axis at least once between these two x values. In other words, f is zero
at least once on that sub-interval.
Note that, in the following algorithm, we refer to “the” root on a sub-interval,
even if there may be more than one root in principle. Whether there are more than
one root on a sub-interval will of course depend on the function, as well as on the
size and location of the sub-interval. For simplicity, we will just assume there is at
most one root on a sub-interval (or that it is sufficiently precise to talk about one
root, even if there could be more).
Numerical Algorithm More precisely, we have a set of n + 1 points (x i , y i ), y i =
f (x i ), i = 0, . . . , n, where x 0 < . . . < x n . We check if y i < 0 and y i+1 > 0 (or
the other way around). A compact expression for this check is to perform the test
y i y i+1 < 0. If so, the root of f (x) = 0 is in [x i , x i+1 ].
Assuming a linear variation of f between x i and x i+1 , we have the approximation
f (x) ≈
f (x i+1 ) − f (x i )
x i+1 − x i
(x − x i ) + f (x i ) =
y i+1 − y i
x i+1 − x i
(x − x i ) + y i ,
which, when set equal to zero, gives the root
x = x i −
x i+1 − x i
y i+1 − y i
y i .
177
7.1.1 Brute Force Root Finding
Assume that we have a set of points along the curve of a continuous function f (x):
We want to solve f (x) = 0, i.e., find the points x where f crosses the x axis.
A brute force algorithm is to run through all points on the curve and check if one
point is below the x axis and if the next point is above the x axis, or the other way
around. If this is found to be the case, we know that, when f is continuous, it has to
cross the x axis at least once between these two x values. In other words, f is zero
at least once on that sub-interval.
Note that, in the following algorithm, we refer to “the” root on a sub-interval,
even if there may be more than one root in principle. Whether there are more than
one root on a sub-interval will of course depend on the function, as well as on the
size and location of the sub-interval. For simplicity, we will just assume there is at
most one root on a sub-interval (or that it is sufficiently precise to talk about one
root, even if there could be more).
Numerical Algorithm More precisely, we have a set of n + 1 points (x i , y i ), y i =
f (x i ), i = 0, . . . , n, where x 0 < . . . < x n . We check if y i < 0 and y i+1 > 0 (or
the other way around). A compact expression for this check is to perform the test
y i y i+1 < 0. If so, the root of f (x) = 0 is in [x i , x i+1 ].
Assuming a linear variation of f between x i and x i+1 , we have the approximation
f (x) ≈
f (x i+1 ) − f (x i )
x i+1 − x i
(x − x i ) + f (x i ) =
y i+1 − y i
x i+1 − x i
(x − x i ) + y i ,
which, when set equal to zero, gives the root
x = x i −
x i+1 − x i
y i+1 − y i
y i .