Keywords

1 Introduction

Many problems in data processing require solving nonlinear equations to obtain the desired result: parametrical identification, fitting data using a specific model, some cases of indirect measurements, etc. In most cases, the data to be processed aren’t accurate and, consequently, the equations to be solved have uncertain parameters. That’s the reason why the roots of such equations cannot be found precise: we always will face the residual uncertainty inherited from the inaccurateness of equation parameters. So, the trials to interpret the roots estimates as quantities, which values are only corrupted with round-off errors and errors caused by using an iterative numerical algorithm of equation solving, aren’t correct—if we solve the required equation analytically, calculate the roots directly using corresponding expressions and don’t allow round-off errors to occur, then it still does not make the root estimate absolutely accurate. If we don’t consider this circumstance, then we overestimate the preciseness of our knowledge on obtained results which in turn leads to an increase in the risks of making erroneous decisions in the future. As en example, we can consider the root of the function \(f\left( {x,a,b} \right) = a \cdot x + b\), where values of a and b aren’t known accurately. If we know that the value of a is inside the interval \(I_{a}\) = [1; 2] and the value of b is inside the interval \(I_{b}\) = [−2; −1] then the root of the function f is inside \(I_{x}\) = [0.5; 2]. Applying any numerical method to solve the equation \(f\left( {x,a,b} \right) = 0\) considering the uncertainty of a and b will bring us to the interval wider than the mentioned interval \(I_{x}\). So, these bounds for the equation root’s possible value are the accurate limits that can be reached for some combination of values a from \(I_{a}\) and b from \(I_{b}\).

This paper discusses the interval bisection method for solving nonlinear equations in which parameters are known approximately—in practice, usually, all we know is the interval of possible values of these parameters.

2 Solving Nonlinear Equations for Indirect Measurements

All the data that we encounter in real-world conditions are uncertain—from world constants to measurement results. In some cases, we can neglect this uncertainty in our calculations and reasoning, but, in other cases, we cannot because of the big price we will pay: decisions made without taking into account the uncertainty of source data may be ill-founded. The absolute accurateness is the distortion of reality, and, in practice, we always need to know the quality of our results. The natural scientific area, in which there are the regulatory requirements to accompany each result with individual characteristics of its uncertainty, is metrology and science on measurements. So, the most relevant example of applications where we deal with equations with inaccurate parameters is the case of indirect measurements when we calculate the value of interest from the measurement results of the related quantities connected with it with the known dependence. Without loss of generality, we can consider the problem of solving indirect measurements equations to illustrate the approach proposed and describe details.

Many quantities cannot be measured directly for various reasons. In these cases, indirect measurements can be used. Firstly, the mathematical model is constructed and tested that describes the interconnection between quantities measured directly and values to be found out. After performing all corresponded measurements, the necessary values are computed as the root of the equation or the solution of the equations system relating the participating quantities. The calculation of the result is an essential part of the indirect measurements and should be taken into account during metrological characteristics estimation. It should be metrologically verified like any other measurement procedure or conversion. Indeed, as it was mentioned earlier, all results of calculations with uncertain data are always inaccurate too—the uncertainty inherited from the input data cannot be overcome. The only thing that can be performed is to analyze how the uncertainty transforms during the computations and to estimate the value of the final calculations results error.

To date, there are many approaches and methods to support metrologically computations—including solving equations with inaccurate parameters (usually being direct measurement results). These methods can be grouped into two big sets: methods that use randomization (Monte Carlo approach [1], the Cauchy deviate method [2, 3] and related techniques) and methods that perform automatic analysis of the computational algorithm by overloading the operations performed during calculations—assuming a linear approximation (automatic differentiation of first order [4, 5] as the most valuable approach, finite differences and complex step derivatives estimates [6, 7] and similar techniques for sensitivity analysis) and in the common case (interval arithmetic [8, 9] and its extensions and modifications like affine arithmetic [10, 11] or others [12, 13] joined with random variables processing approaches like probability boxes framework [14, 15]). All of these techniques were developed for the wide class of computational problems with inaccurate input data and can be used in computational metrology.

Numerous different methods are developed and used to search the roots of nonlinear equations. The most popular of them are Newton and Newton–Raphson methods, secant method, bisection method, etc [16]. The first three methods need the initial guess as a first estimation of the root, and the last-mentioned one needs the interval of root localization. If the initial guess is unsuccessful, then the iterative process can diverge, and no root can be obtained at all. In many cases, it is impossible to determine if the guess is acceptable or not before the iterative process starts. In constrast, the bisection method guarantees that the final result of root estimation will be got and supposes a very simple procedure to test if the initial localization interval is acceptable or not.

We should consider the additional sides of the issue to determine what method for solving equations from the listed above is better for metrological practice. So for this, we analyze the details of the metrological supporting the corresponding computational procedures. Approaches for processing initial data uncertainty using randomization might cause the situation when the Newton, Newton–Raphson, and secant methods will diverge—so, we should recognize corresponded  iterations during the Monte Carlo method execution or similar approaches applying and should stop timely and throw out the wrong results from consideration. This complicates the procedure of root finding. The same situation may occur if we use operator overloading—the procedure that converges being executed with individual numbers as input variables may begin to diverge if it is executed with intervals or interval-valued quantities like probability boxes. Thus, this can bring us to an unacceptable situation if the equation to be solved is the equation of indirect measurements—we will not obtain any measurement result at all because of the computational procedure. To address these shortcomings, we suggest using the bisection method that always ensures the final result obtaining. Besides, supporting the bisection with one of the discussed approaches for estimating uncertainty inherited from the initial data doesn’t bring us to the iterative process divergence. So, combining the bisection method with any kind of procedure of metrological supporting is the preferable way to solve nonlinear equations of indirect measurements.

This paper presents the interval version of the bisection method for solving nonlinear equations with interval-valued parameters that are commonplace in metrological practice. The proposed method is fully in line with metrological requirements that is an advantage in comparison with traditionally used approaches [17, 18]. The way is proposed for taking into account the uncertainty of initial data during equation solving and reasonably set the moment to stop the iteration process.

3 The Interval Bisection

Let \(\vec{x}^{{\text{T}}} = \left( {x_{1} ,\;x_{2} ,\;x_{3} ,\;...,\;x_{n} } \right)\) be the direct measurement results, and \(f\left( {y,\;\vec{x}} \right) = 0\) be the equation that connects these measurands with quantity y that is supposed to be measured indirectly. Let \(\Delta x_{1} ,\;\Delta x_{2} ,\;\Delta x_{3} ,\;...,\;\Delta x_{n}\) be the absolute errors of \(x_{1} ,\;x_{2} ,\;x_{3} ,\;...,\;x_{n}\) correspondingly, and let it be known that their maximum possible values satisfy the restrictions: \(\left| {\Delta x_{i} } \right| < \Delta_{i}\), i = 1, 2, …n.

The traditional bisection method [19] ignores that quantities \(x_{1} ,\;x_{2} ,\;x_{3} ,\;...,\;x_{n}\) are inaccurate and treats them as the only possible values of parameters of the equation to be solved. Let the interval \(I_{1} = \left[ {a,\;b} \right]\) be the localization bounds for y. In metrology during indirect measurements, we usually face equations representing zeros of the monotonic functions f. So we have the only root because, for one set of direct measurement results, we must have the only one corresponding value of the indirect measurement. If the values \(f\left( {a,\;\vec{x}} \right)\) and \(f\left( {b,\;\vec{x}} \right)\) have different signs, then interval I will contain the only root. For problems from other fields, we should start with such an interval of values of argument y that will provide different signs of function f values obtained at the interval’s left and right bounds. Then, we can be sure that not less than one root is inside this interval.

For each step of bisection, the current interval of root localization is divided into two equal parts, and the one that contains the root is chosen. To determine what half should be preferred, the sign of value \(f\left( {0.5 \cdot \left( {a + b} \right),\;\vec{x}} \right)\) in the middle of interval I should be calculated. The obtained narrowed interval is new localization bounds for equation root, and then the new iteration starts, and all described operations are repeated. So, let the localization interval for i-th iteration step be \(I_{i} = \left[ {a_{i} ,\;b_{i} } \right]\). If \(f\left( {a_{i} ,\;\vec{x}} \right) \cdot f\left( {0.5 \cdot \left( {a_{i} + b_{i} } \right),\;\vec{x}} \right) > 0\), then \(a_{i + 1} = 0.5 \cdot \left( {a_{i} + b_{i} } \right)\), \(b_{i + 1} = b_{i}\). If \(f\left( {0.5 \cdot \left( {a_{i} + b_{i} } \right),\;\vec{x}} \right) \cdot f\left( {b_{i} ,\;\vec{x}} \right) > 0\), then \(a_{i + 1} = a_{i}\), \(b_{i + 1} = 0.5 \cdot \left( {a_{i} + b_{i} } \right)\). The interval \(I_{i + 1} = \left[ {a_{i + 1} ,\;b_{i + 1} } \right]\) is the localization interval for the next iteration.

The situation stops to be unambiguous if taking into account the information on the uncertainty of initial data. Since some iteration, we will not be able to determine exactly the sign of the value \(f\left( {0.5 \cdot \left( {a_{i} + b_{i} } \right),\;\vec{x}} \right)\) because of the influence of uncertainty of direct measurement results \(\vec{x}\) acting as equality parameters. So, we will not be able to decide what half of the current localization interval contains the root of the equation to be solved: for some possible values of \(\vec{x},\) it will be in the left half, and for other possible values – in the right half.

The solution allowing to overcome this obstacle is to use one of the methods discussed in the previous section of the paper that provides each calculation of the function \(f\left( {y,\;\vec{x}} \right)\) with its individual uncertainty estimate \(\Delta f\left( {y,\;\vec{x}} \right)\). Then we will be able to determine the moment when the traditional bisection method faces at current iteration i such center \(c_{i} = 0.5 \cdot \left( {a_{i} + b_{i} } \right)\) of the current root localization interval \(I_{i} = \left[ {a_{i} ,\;b_{i} } \right]\) that satisfies the condition \(\Delta f\left( {c_{i} ,\;\vec{x}} \right) > \left| {f\left( {c_{i} ,\;\vec{x}} \right)} \right|\). This inequality indicates the situation described above when we cannot choose half of the localization interval for the next bisection iteration. Really, if it holds, then there are no reasons to consider the value \(f\left( {c_{i} ,\;\vec{x}} \right)\) differing from zero. The equivalent form of the inequality is \(0 \in \left( {f\left( {c_{i} ,\;\vec{x}} \right) \pm \Delta f\left( {c_{i} ,\;\vec{x}} \right)} \right)\), so we see that any positive or negative values \(f\left( {c_{i} ,\;\vec{x}} \right)\) lying inside the interval determining by mentioned inequality could be formed by distorting the true value equal to zero by measurement errors. In this paper, we suggest using the moment when the analyzed inequality holds as the transition to the second stage of the modified bisection method.

So, the following simple algorithm can describe the first stage of the proposed approach.

figure a

On the second stage of the interval bisection, we need to narrower the last obtained interval \(I_{i} = \left[ {a_{i} ,\;b_{i} } \right]\) of root localization that provides the unambiguous sign of function f at its bounds:

$$\Delta f\left( {a_{i} ,\;\vec{x}} \right) < \left| {f\left( {a_{i} ,\;\vec{x}} \right)} \right| \text{ and } \Delta f\left( {b_{i} ,\;\vec{x}} \right) < \left| {f\left( {b_{i} ,\;\vec{x}} \right)} \right|$$

The goal of each iteration of the second stage of the proposed method is to narrower these bounds to such an interval \(I_{i + 1} = \left[ {a_{i + 1} ,\;b_{i + 1} } \right]\) that ensures holding the condition \(I_{i+1} \subseteq I_{i}\) and guarantees at the same time that the sign of function \(f\left( {y,\;\vec{x}} \right)\) at \(y = a_{i + 1}\) and \(y = b_{i + 1}\) isn’t ambiguous:

$$\Delta f\left( {a_{i + 1} ,\;\vec{x}} \right) < \left| {f\left( {a_{i + 1} ,\;\vec{x}} \right)} \right| \text{ and } \Delta f\left( {b_{i + 1} ,\;\vec{x}} \right) < \left| {f\left( {b_{i + 1} ,\;\vec{x}} \right)} \right| .$$

Surprisingly, the traditional bisection approach can be easily applied for this purpose. We can reformulate the problem to be solved in the following manner:

  • to find the root’s minimum possible value, we need to solve equation \(\Delta f\left( {y_{\min } ,\;\vec{x}} \right) = \left| {f\left( {y_{\min } ,\;\vec{x}} \right)} \right|\) for \(y_{\min }\) within the localization interval \(\left[ {a_{i} ,\;c_{i} } \right]\);

  • to find the root’s maximum possible value, we need to solve equation \(\Delta f\left( {y_{\max } ,\;\vec{x}} \right) = \left| {f\left( {y_{\max } ,\;\vec{x}} \right)} \right|\) for \(y_{\max }\) within the localization interval \(\left[ {c_{i} ,\;b_{i} } \right]\).

Here, as before, \(c_{i} : = 0.5 \cdot \left( {a_{i} + b_{i} } \right)\) is the center of interval \(I_{i}\) that is obtained on the last iteration of the first stage of interval bisection.

Thus, at every new iteration, we need to examine the left and right bound of the interval that localizes the equation root separately. To finish the iterative process, we propose the following rule. It is rational to stop improving the interval estimating when the interval length refining on the next iteration is less than the given constant ε > 0:

$$\left\| {I_{i} } \right\| - \left\| {I_{i+1} } \right\| < \varepsilon .$$

Solving the metrological problems, the uncertainty bounds for the obtained root’s value should be rounded – this circumstance is the natural opportunity to determine the best moment to stop the interval bisection method. If the rounded bounds of the interval of root localization obtained on the previous iteration are the same as the rounded bounds of the interval of root localization obtained on the current iteration, then we should finish. The rounding is suggested to be performed in a metrological sense.

The algorithm of the second stage of the interval bisection is the following.

figure b

4 Illustrating Example

To make the proposed ideas of the interval bisection method clearer, let us examine some function \(f\left( {y,\;\vec{x}} \right) = \exp \left( {x_{1} \cdot y} \right) + x_{2} \cdot y\) depending on the variable of our interest y and a set of parameters \(\vec{x}\) that are known with uncertainty. Let us find the root of the equation \(f\left( {y,\;\vec{x}} \right) = 0\) using the discussed approach.

From the physical sense, this equation models the environmental pollution caused by the point source. The parameters \(\vec{x}\) describe the characteristics of the environment and the pollution. From the mathematical viewpoint, this problem is equivalent to calculating the standard Lambert W-function [20].

The values \(\vec{x}^{{\text{T}}} = \left( {x_{1} ,\;x_{2} } \right)\) aren’t known exactly. All we know about values \(\vec{x}\) is that \(x_{1} \in \left[ { - 0.11,\; - 0.09} \right]\) and \(x_{2} \in \left[ { - 5.05,\; - 4.95} \right]\). So, \(\left( {x_{1} ,\;x_{2} } \right) = \left( { - 0.10,\; - 5.00} \right)\) and \(\left( {\Delta x_{1} ,\;\Delta x_{2} } \right) = \left( {0.01,\;0.05} \right)\). Let us try as the start root’s localization interval the interval \(I_{0} = \left[ {a_{0} ,\;b_{0} } \right] = \left[ {0,\;1} \right]\). These bounds satisfy the condition of the bisection method applicability condition: \(f\left( {a_{0} ,\;\vec{x}} \right) \cdot f\left( {b_{0} ,\;\vec{x}} \right) < 0\).

The entire iterative process that corresponds to using the interval bisection for the mentioned equation is presented in Fig. 1. We can see that, as a result, we obtain further unimprovable interval estimation of the root that cannot be narrower because of the uncertainty of the solved equation parameters. Figure 1 also illustrates that, during the first stage of the interval bisection method, this approach reproduces the traditional scheme of the bisection and that the second stage essence is in narrowing the last localization interval obtained at the first stage.

Fig. 1
figure 1

Intervals of root localization for different stages of the proposed algorithm

Full size image
Fig. 2
figure 2

Illustration of the first stage of the interval bisection algorithm

Full size image

In Fig. 2, the results of the first stage execution of the proposed method are illustrated. The stop condition is satisfied on the 4th iteration when we cannot, for the first time, determine the sign of the function f in the center of the root localization interval. So, we go to the second part of the method.

The results obtained on the several iterations of the second stage of interval bisection are illustrated in Figs. 3, 5, and 6. We can see how the left and right bounds of the localization interval are refined. For convenience, in Figs. 3, 5, and 6, the independent indexing of iterations is used: index j = 0 corresponds to the beginning of the second stage of interval bisection when dealing with the localization interval obtained on the last iteration of the method’s first stage.

Fig. 3
figure 3

Results of the first stage of the interval bisection algorithm and the transition to the second stage

Full size image
Fig. 4
figure 4

Results of the first iteration of the second stage of the interval bisection algorithm

Full size image
Fig. 5
figure 5

Results of the second iteration of the second stage of the interval bisection algorithm

Full size image
Fig. 6
figure 6

Final results of the interval bisection algorithm

Full size image

In Fig. 6, we see the final iteration of the proposed approach. It corresponds to the stopping rule taken from the metrological nature of the solving problem: if we round the uncertainty bounds of the root’s estimate at the current iteration, then the new iteration will not bring the refining, and we should finish. The obtained bounds are \(\left[ {0.172,\;0.219} \right]\).

5 Conclusions

In this paper, the interval extension of the bisection method is proposed for solving nonlinear equations with inaccurate parameters. A simple and effective algorithm is presented that brings with the guarantee to the root estimation. The clear stopping rules are proposed that naturally follow from the problem and allow to finish the iterative process of equation solving earlier in full correspondence with known initial data on the equation to be solved. The proposed approach remains the important property of the bisection method—all the intermediate interval estimates of the root possible values contain the exact bounds.