Let \((X,d)\) be a metric space, \(D\subset (X,d)\) and \(f:D \longrightarrow \mathbb{R}\) a continuous function (with respect to the metric \(d\) and the Euclidean metric on \(\mathbb{R}\)) . Under suitable conditions on the function \(f\) and the set \(D\), we prove the existence of zeros of the function \(f\) on \(D\) by using the so-called \(\alpha\)-dense curves. To be more precise, we prove that if \(f(x_{1})f(x_{2})<0\) for some \(x_{1},x_{2}\in D\) and \(D\) is densifiable then \(f\) has some zero in \(D\). Moreover, from this result we derive a numerical method to approximate, with arbitrarily small error, at least one of these zeros. In particular, as a compact interval \([a,b]\) is densifiable, our method generalizes the well known bisection method. The feasibility and reliability of the proposed method is illustrated by several numerical examples.
The well known bisection method (see, for instance, [1, 2]) is a robust numerical method used to approximate the zeros of a real-valued function. It is based on the Intermediate Value Theorem, which states that if a continuous function \(f:[a,b]\longrightarrow \mathbb{R}\) (we assume \(\mathbb{R}\) is endowed with the Euclidean metric) has different signs at the endpoints of an interval \([a,b]\), then there exists at least one zero of \(f\) within that interval. That is to say, there exists \(x^{*}\in [a,b]\) such that \(f(x^{*})=0\). The bisection method iteratively refines the interval in which a zero exists until a desired level of accuracy is reached. Some generalizations and improvements of this method can be found in [3– 7] and references therein. For completeness, we show in Algorithm 1 the pseudo-code of the bisection method.
Let us note that if we remove the condition \(b-a\geq \delta\) in the while loop of Algorithm 1, theoretically we obtain \(c\in [a,b]\) such that \(f(c)\leq \varepsilon\). As proven in [1, p. 262], under this condition, the convergence of the bisection method is at least linear. Also, the number of iterations in the bisection method to attain the desired approximation is \[n:=\lceil \frac{ \ln \big( \frac{b-a}{2\varepsilon} \big) }{\ln(2)}\rceil,\] where \(\lceil x\rceil\) denotes the ceiling of \(x\), i.e., the smallest integer greater than or equal to \(x\). However, for computational reasons that condition can not be removed, because the computer works with a finite number of decimal places. So, if we remove the condition \(b-a\geq \delta\), the loop of Algorithm 1 may never end.
On the other hand, in the present paper we consider a continuous function \(f:D\subset (X,d)\longrightarrow \mathbb{R}\), where \((X,d)\) is a metric space (\(\mathbb{R}\) is assumed to be endowed with the Euclidean metric) and \(D\neq \emptyset\), and we analyze, under suitable conditions, the problem of finding some zero of \(f\) in \(D\). For this, we will the use so-called \(\alpha\)-dense curves, explained in detail in §2. To be more precise, if there are \(x_{1},x_{2}\in D\) such that \(f(x_{1})f(x_{2})<0\) and \(D\) is densifiable (i.e., for any arbitrarily small \(\alpha>0\), there exists an \(\alpha\)-dense curve in \(D\)), then we prove in Theorem 1 that \(f\) has some zero in \(D\). Moreover, from the proof of Theorem 1 we propose a numerical method to approximate some zeros of \(f\) in the densifiable set \(D\). Noticing that a compact interval \([a,b]\) of the real line is, in particular, a densifiable set (see Proposition 1), our result is a generalization of the bisection method.
We provide in §4 some numerical examples to illustrate the proposed method and, to conclude our exposition, in §5 we discuss briefly its advantages and drawbacks.
We need to recall the concepts of \(\alpha\)-dense curves and densifiable sets, introduced in [8]. In what follows, \((X,d)\) will be a metric space and \(\mathcal{B}(X)\) the class of the non-empty and bounded subsets of \(X\). Also, in what follows, all subsets of \(\mathbb{R}^{d}\), for a given integer \(d\geq 1\), are assumed endowed with the Euclidean metric if otherwise is not specified.
Definition 1. Let \(\alpha > 0\) and \(D\in \mathcal{B}(X)\). A continuous function \(\gamma :[0,1]\longrightarrow (X,d)\) is said to be an \(\alpha\)-dense curve in \(D\) if the following conditions are satisfied:
(i) \(\gamma ([0,1])\subset D\).
(ii) For every \(x\in D\) there exists \(y\in \gamma([0,1])\) such that \(d(x,y)\leq \alpha\).
If for each \(\alpha >0\) there is an \(\alpha\)-dense curve in \(D\), then \(D\) is said to be densifiable.
Let us note that, for a given \(D\in \mathcal{B}(X)\), fixed \(x_{0}\in D\), the mapping defined as \(\gamma(t):=x_{0}\) for all \(t\in [0,1]\) is, trivially, an \(\alpha\)-dense curve in \(D\), for any \(\alpha \geq \mathrm{Diam}(D)\), the diameter of \(D\). Therefore, the class of \(\alpha\)-dense curves in \(D\) is non-empty for each \(\alpha \geq \mathrm{Diam}(D)\). Also, taking into account that fixed an integer \(n\geq 1\) a continuous function from \([0,1]\) onto \([0,1]^{n}\), is called a space-filling curve (see [9]), it is clear that the \(\alpha\)-dense curves are a generalization of the space-filling curves. Moreover, Mora [10] proved that the space-filling curves can be characterized in terms of the \(\alpha\)-dense curves. A detailed exposition of the \(\alpha\)-dense curves as well as theirs applications can be found in [8, 9– 19] and references therein.
In the present paper, and according with Schaeffer’s book [20], we mean that a subset \(B\) of \((X,d)\) is precompact (some authors call it totally bounded) if for each \(\varepsilon>0\) there is a finite set \(\{x_{1},\ldots,x_{n}\}\subset B\) such that \[\displaystyle B\subset \bigcup_{i=1}^{n}\bar{B}(x_{i},\varepsilon),\] where \(\bar{B}(x,r)\) stands for the closed ball centered at \(x\) and radius \(r>0\). We have the following result to characterize the precompact sub-sets of a metric space (see [13, 21]).
Proposition 1. Let \(D\in\mathcal{B}(X)\) be arc-wise connected. Then, \(D\) is densifiable if and only if it is precompact.
We show in the below example that, in general, the arc-wise connectedness in the above result can not be removed.
Example 1. In the Euclidean plane consider the following compacts, connected but not arc-wise connected sets \[\begin{array}{lll} \displaystyle D_{1}:=\left\{ \left(x, \sin\left(\frac{1}{x}\right) \right): x\in (0,1] \right\} \bigcup \left\{ (0,y): y\in [-1,1] \right\} ,\\ \\ \displaystyle D_{2}:=\left\{ \left(x, \sin\left(\frac{1}{x}\right) \right): x\in [-1,0) \cup (0,1] \right\} \bigcup \left\{ (0,y): y\in [-1,1] \right\} . \end{array}\] Then, it is easy to check that \(D_{1}\) is densifiable but there is not an \(\alpha\)-dense curve in \(D_{2}\) for any \(0<\alpha<1\). Consequently, \(D_{2}\) is not densifiable.
We provide some examples of \(\alpha\)-dense curves, in the specified sets, that will be used in §4.
Example 2. Let two integers \(n , m>1\), \(B:=\prod_{i=1}^{n}[a_{i},b_{i}]\) for certain \(a_{i},b_{i}\in\mathbb{R}\) with \(a_{i} < b_{i}\) for \(i=1,\ldots, n\), and \(\alpha:=M\frac{\sqrt{n-1}}{m}\) where \(M :=\max\{b_{i}-a_{i}:i=1,\ldots, n\}\). Define the function \(\gamma_{\alpha} :[0,1]\longrightarrow \mathbb{R}^{n}\) as \[\gamma_{\alpha} (t ):=\left( a_{1}+\left(b_{1}-a_{1}\right)t, a_{2}+\frac{b_{2}-a_{2}}{2}\left(1-\cos(m \pi t )\right) ,\ldots, a_{n}+\frac{b_{n}-a_{n}}{2}\left(1-\cos(m^{n-1}\pi t )\right) \right) ,\] for each \(t\in [0,1]\). Then, \(\gamma_{\alpha}\) is an \(\alpha\)-dense curve in \(B\) (see [11, Corollary 9.5.5]). For \(B:=[0,1]^{n}\), we show in Figure 1 the graphs of some of these curves, for the indicated values of \(m\) and \(n\).
As we will see in the below examples, the above \(\alpha\)-dense curve are useful to define other \(\alpha\)-dense curves in other metric spaces.
Example 3. Consider \(\mathbb{R}^{\mathbb{N}}\), the product of \(\mathbb{N}\)-copies of \(\mathbb{R}\), endowed with the metric \[d_{\mathbb{N}}\big( \mathbf{x},\mathbf{y} \big):=\sum_{n\geq 1} 2^{-n} \frac{|x_{n}-y_{n}|}{1+|x_{n}-y_{n}|},\quad \textrm{for all }\mathbf{x}:=(x_{n})_{n\geq 1},\mathbf{y}:=(y_{n})_{n\geq 1}\in\mathbb{R}^{\mathbb{N}} .\]
Fixed an integer \(n_{0}>1\), let \(B:=\prod_{n\geq 1} [a_{n},b_{n}]\), with \(a_{n},b_{n}\in \mathbb{R}\) with \(a_{n}<b_{n}\) for each \(n\geq 1\), and \(B_{0}:=\prod_{n=1}^{n_{0}} [a_{n},b_{n}]\subset \mathbb{R}^{n_{0}}\). Let \(\gamma_{\alpha_{0}}=(\gamma_{\alpha_{0}}^{1},\ldots , \gamma_{\alpha_{0}}^{n_{0}})\) be an \(\alpha_{0}\)-dense curve in \(B_{0}\), for some \(\alpha_{0}>0\). Let \(\alpha:=\alpha_{0}+\sum_{n\geq n_{0}+1}2^{-n}\) and define \(\gamma_{\alpha}:=(\gamma_{\alpha}^{n})_{n\geq 1}: [0,1] \longrightarrow (\mathbb{R}^{\mathbb{N}} , d_{\mathbb{N}})\) as \[\gamma_{\alpha}^{n}(t):=\left\{\begin{array}{lll} \gamma_{\alpha_{0}}^{n}(t),& \textrm{for } n\leq n_{0} \\ \\ \xi_{n}(t), & \textrm{for } n\geq n_{0}+1 \end{array}\right. \quad \textrm{for all }n\in\mathbb{N}\textrm{ and } t\in [0,1] ,\] where, for each \(n\geq n_{0}+1\), \(\xi_{n}:[0,1]\longrightarrow [a_{n},b_{n}]\) is an arbitrary continuous function. Then, \(\gamma_{\alpha}\) is an \(\alpha\)-dense curve in \(B\) (see [13, 18]).
Example 4. We recall that for each integer \(n\geq 0\), the \(n\)-th Chebyshev polynomial is defined as \(T_{n}(x):=\cos(n\arccos (x))\), for each \(x\in [-1,1]\). Let us denote by \(\mathcal{C}[-1,1]\) the Banach space of the continuous functions defined on \([-1,1]\), endowed its usual supremum norm. It is a known fact (see, for instance, [22, Chapter 4]) that given \(h\in \mathcal{C}[-1,1]\) it can be written as a series of Chebyshev polynomials. That is to say, \[h(x)=\sum_{n\geq 0} a_{n}T_{n}(x) \quad \textrm{with } a_{n}:=\int_{-1}^{1}\frac{h(x)T_{n}(x) }{\sqrt{1-x^{2}}}dx, \quad \textrm{for all } n\geq 0.\] Fixed a sequence \((r_{n})_{n\geq 0}\) of positive numbers such that \(\sum_{n\geq 0}r_{n}<\infty\), consider the set \[D:=\big\{ \sum_{n\geq 0} a_{n}T_{n}(x): |a_{n}|\leq r_{n} \textrm{ for each } n\geq 0 \big\}\subset \mathcal{C}[-1,1] .\] Let us note that as \(\sum_{n\geq 0}r_{n}<\infty\), each series in \(D\) is uniformly convergent and therefore, \(D \subset \mathcal{C}[-1,1]\) as indicated above. Clearly, \(D\) is convex. Also, given any sequence \((h_{k}(x))_{k\geq 1}\subset K\), put \(h_{k}(x):= \sum_{n\geq 0} a_{n}^{(k)}T_{n}(x)\), with \(|a_{n}^{(k)}|\leq r_{n}\) for each \(n\geq 0\) and \(k\geq 1\), \((h_{k}(x))_{k\geq 1}\) has a converging sub-sequence. Indeed, let \(c_{0}\) be the Banach space of the null sequences, endowed its usual supremum norm and consider the set \[A:=\big\{ (a_{n}^{(k)})_{k\geq 1}: n\geq 1 \big\} \subset c_{0}.\] Then, by [23, Theorem II.4.1], \(A\) is precompact. Consequently, \(A\) has convergent sub-sequence, put \((a_{n}^{(k_{j})})_{j\geq 1}\), and thus \((h_{k_{j}}(x))_{k\geq 1}\) converges (uniformly) to a function in \(\bar{K}\),the closure of \(K\). In other words, \(D\) is precompact. So, by Proposition 1, the set \(D\) is densifiable. In fact, we show in the following lines an example of \(\alpha\)-dense curve in \(D\) for an arbitrary \(\alpha>0\).
Fixed an integer \(n_{0}\geq 1\), let \(\gamma_{\alpha_{0}}:=(\gamma_{\alpha_{0}}^{0},\ldots, \gamma_{\alpha_{0}}^{n_{0}})\) be an \(\frac{\alpha_{0}}{n_{0}+1}\)-dense curve in \(\prod_{n=0}^{n_0}[-r_{n},r_{n}]\subset \mathbb{R}^{n_{0}+1}\) for some \(\alpha_{0}>0\). Define \(\alpha:=\alpha_{0}+2\sum_{n\geq n_{0}+1} r_{n}\) and \(\gamma_{\alpha}:=(\gamma_{\alpha}^{n})_{n\geq 1}: [0,1] \longrightarrow (\mathbb{R}^{\mathbb{N}}, d_{\mathbb{N}})\), \(d_{\mathbb{N}}\) being the metric given in Example 3, as \[\gamma_{\alpha}^{n}(t):= \sum_{n=0}^{n_{0}} \gamma_{\alpha}^{n}(t)T_{n}(x) +\sum_{n\geq n_{0}+1}\xi_{n}(t)T_{n}(x) \quad \textrm{for all } t\in [0,1] ,\] where, for each \(n\geq n_{0}+1\), \(\xi_{n}:[0,1]\longrightarrow [-r_{n},r_{n}]\) is an arbitrary continuous function. It is easy to check that \(\gamma_{\alpha}\) is an \(\alpha\)-dense curve in \(D\). Also, it is clear that \(\alpha \rightarrow 0\) as \(n_{0} \rightarrow \infty\), that is, \(\alpha\) can be arbitrarily small.
As in the previous section \((X,d)\) is a metric space. Assume \(f:D\subseteq X \longrightarrow \mathbb{R}\) is a given function. Denote by \(\mathcal{Z}_{D}(f)\) the zeros of \(f\) in the set \(D\), that is to say \[\mathcal{Z}_{D}(f) :=\big\{ x\in D: f(x)=0 \big\}.\] Assume \(\gamma_{\alpha}:[0,1]\longrightarrow (X,d)\) is an \(\alpha\)-dense curve in \(D\), for some \(\alpha>0\). Assume \(\mathcal{Z}_{D}(f) \neq\emptyset\). If \(x^{*}\in \mathcal{Z}_{D}(f)\), there is \(t\in [0,1]\) such that \(d(x^{*},\gamma_{\alpha}(t))\leq \alpha\). In particular, if \(D\) is densifiable, we can take \(\alpha\) arbitrarily small. This means that, for a given \(x^{*}\in \mathcal{Z}_{D}(f)\) and a prescribed \(\alpha>0\), there is \(y^{*}\in \gamma_{\alpha}([0,1])\) that is at a distance from \(x^{*}\) less than or equal to \(\alpha\). This observation can be formally proved in the following result.
Proposition 2. Let \(f:D\subseteq X \longrightarrow \mathbb{R}\) be a function such that \(\mathcal{Z}_{D}(f) \neq\emptyset\). Assume that \(D\) is densifiable, and let \((\alpha_{n})_{n\geq 1}\) be a sequence of positive numbers such that \(\lim \limits_{n}\alpha_{n}=0\). Also, for each \(n\geq 1\), let \(\gamma_{\alpha_{n}}:[0,1]\longrightarrow (X,d)\) be an \(\alpha_{n}\)-dense curve in \(D\). Then, if \(x^{*}\in \mathcal{Z}_{D}(f)\) there exists a sequence \(( t_{n})_{n\geq 1}\subset [0,1]\) such that \[\lim_{n} d \big( \gamma_{n}(t_{n}), x^{*} \big)=0 .\]
Proof. Let \(x^{*}\in \mathcal{Z}_{D}(f)\). As, for each \(n\geq 1\), \(\gamma_{\alpha_{n}}\) is an \(\alpha_{n}\)-dense curve in \(D\) there is \(t_{n}\in [0,1]\) such that \(d(x^{*} , \gamma_{\alpha_{n}}(t_{n}) )\leq \alpha_{n}\). As \(\lim \limits_{n}\alpha_{n}=0\), the result follows. ◻
In the above result, we assume \(\mathcal{Z}_{D}(f) \neq\emptyset\) and \(D\) is densifiable, and we prove that a given \(x^{*}\in \mathcal{Z}_{D}(f)\) can be approximated by using \(\alpha\)-dense curves. In the following result, we state sufficient conditions on \(f\) and \(D\) to ensure that \(\mathcal{Z}_{D}(f) \neq\emptyset\). Moreover, under such conditions, we provide below (see Algorithm 2) a numerical method to, by using \(\alpha\)-dense curves, approximate some \(x^{*}\in \mathcal{Z}_{D}(f)\).
Now, we can prove our main result, which reads as follows.
Theorem 1. Let \(f:D\subseteq (X,d) \longrightarrow \mathbb{R}\) be a continuous function. Assume the following conditions:
(1) There are \(x_{1},x_{2}\in D\) such that \(f(x_{1})f(x_{2})<0\).
(2) The set \(D\) is densifiable.
Then, \(\mathcal{Z}_{D}(f)\neq\emptyset\). Moreover, there is a small enough \(\alpha>0\), an \(\alpha\)-dense curve in \(D\), put \(\gamma_{\alpha}\), such that \(\gamma_{\alpha}(t^{*})\in \mathcal{Z}_{D}(f)\) for some \(t^{*} \in [0,1]\).
Proof. According to (1), let \(x_{1},x_{2}\in D\) such that \(f(x_{1})f(x_{2})<0\), without lost of generality assume \(f(x_{1})>0\) and \(f(x_{2})<0\). By the continuity of \(f\), there are \(r_{1},r_{2}>0\) such that \[f(x)>0 \textrm{ for all } x\in B(x_{1},r_{1})\cap D, \quad f(x)<0 \textrm{ for all } x\in B(x_{2},r_{2})\cap D \label{eq_3_10} \tag{1}\] where \(B(x,r)\) stands for the open ball centered at \(x\) and radius \(r>0\).
Let \(0<\alpha<\min\{r_{1},r_{2}\}\) and \(\gamma_{\alpha}\) an \(\alpha\)-dense curve in \(D\). The existence of such curve is guaranteed by condition (2). Let \(t_{1},t_{2}\in (0,1)\) such that \[d(x_{1},\gamma_{\alpha}(t_{1})) \leq \alpha \quad \textrm{and} \quad d(x_{2},\gamma_{\alpha}(t_{2})) \leq \alpha . \label{eq_3_12} \tag{2}\] Then, noticing (1) and (2), we have \[f\big( \gamma_{\alpha}(t_{1})\big) f\big( \gamma_{\alpha}(t_{2})\big) <0. \label{eq_3_13} \tag{3}\] Therefore, by the Intermediate Value Theorem there is \(t^{*}\in (t_{1},t_{2})\) such that \(f ( \gamma_{\alpha}(t^{*} ) )=0\) and the proof is completed. ◻
Let us note that in the above result, the densifiability of the set \(D\), in general, can not be removed, as we show in the following simple example.
Example 5. Let \(D:=\{(-1,1),(-1-1),(1,-1),(1,1)\}\subset \mathbb{R}^{2}\), and \(f:D\longrightarrow \mathbb{R}\) the function \(f((x_{i},x_{j})):=x_{i}x_{j}\), for each \((x_{i},x_{j})\in D\). It is clear that \(f\) is continuous and \(f((-1,-1))f((1,-1))=-1<0\) but \(\mathcal{Z}_{D}(f) = \emptyset\).
The set \(D\) is not densifiable. Indeed, if \(\gamma\) is an \(\alpha\)-dense curve in \(D\), since \(\gamma([0,1])\) is arc-wise connected, then \(\gamma(t)\) must be equal to \((x_{i},x_{j})\) for some \((x_{i},x_{j})\in D\) and all \(t\in [0,1]\). Therefore, \(\alpha=2\sqrt{2}\) and consequently \(D\) can not be densifiable.
On the other hand, it is important to stress that Theorem 1, implicitly, provides us a method to approximate some zero of the function \(f\). Indeed, let \(f:D\subseteq (X,d) \longrightarrow \mathbb{R}\) be as in Theorem 1. Then, there are \(\alpha>0\) and \(t^{*}\in(t_{1},t_{2})\), for certain \(t_{1},t_{2}\in (0,1)\), such that \(f(\gamma_{\alpha}(t^{*}) )=0\), \(\gamma_{\alpha}\) being an \(\alpha\)-dense curve in \(D\). Also, noticing (3) and reasoning as in the bisection method, there exists \(\eta>0\) such that \[f\big( \gamma_{\alpha}( t_{1}^{*}) \big) f\big( \gamma_{\alpha}( t_{2}^{*} ) \big) < 0 ,\quad \textrm{whenever } t_{1}^{*}\in (t^{*}-\eta,t^{*}),t_{2}^{*}\in (t^{*} , t^{*}+\eta). \label{eq_3_14} \tag{4}\]
So, if we find \(t_{1}^{*},t_{2}^{*}\in (0,1)\) obeying the above inequality, by applying the bisection method to the function \(f\circ \gamma_{\alpha}:[t_{1}^{*},t_{2}^{*}]\longrightarrow \mathbb{R}\) we can obtain an approximation of \(\gamma_{\alpha}(t^{*}) \in \mathcal{Z}_{D}(f)\). A way to find some \(\alpha>0\) and \(t_{1}^{*},t_{2}^{*}\in (0,1)\) satisfying (4) is explained in the below lines.
Let \((N_{k})_{k\geq 1}\) a sequence of positive integers such that \(\lim \limits_{n} N_{k}=\infty\) and \(\gamma_{\alpha_{N_{k}}}\) an \(\alpha_{N_{k}}\)-dense curve in \(D\). Assume \(\lim \limits_{k}\alpha_{N_{k}}=0\). Construct a set of points \[S_{N_{k}}:=\left\{t_{1,n}^{N_{k}},t_{2,n}^{N_{k}}:n=1,\ldots , N_{k}\right\}\subset [0,1] ,\] such that \(S_{N_{k}}\) becomes into a dense sequence in \([0,1]\) when \(k\rightarrow \infty\). For instance, for each \(N_{k}\) we can take \[t_{1,n}^{N_{k}}\sim \mathcal{U}\left[ \frac{n-1}{N_{k}},\frac{n}{N_{k}} \right] \textrm{ and } t_{2,n}^{N_{k}}\sim \mathcal{U}\left[ \frac{n-1}{N_{k}},\frac{n}{N_{k}} \right], \quad \textrm{for each }n=1,\ldots, N_{k} ,\] where \(t\sim \mathcal{U}[a,b]\) means that \(t\) is a sample of a random variable uniformly distributed in \([a,b]\). Note that, as the set of points \(\{\frac{n-1}{N_{k}}, \frac{n}{N_{k}}:n=1,\ldots, N_{k}\}\) becomes into a dense sequence in \([0,1]\) when \(k\rightarrow \infty\), the set \(S_{N_{k}}\) too. Therefore, for large enough \(k\), there are \(t_{1,n}^{N_{k}},t_{2,n}^{N_{k}}\in S_{N_{k}}\) for some \(1\leq n\leq N_{k}\) such that \[t_{1}^{*}:=\min\left\{ t_{1,n}^{N_{k}},t_{2,n}^{N_{k}}\right\}\in (t^{*}-\eta,t^{*}),\quad t_{2}^{*}:=\max\left\{ t_{1,n}^{N_{k}},t_{2,n}^{N_{k}}\right\}\in (t^{*},t^{*}+\eta),\] and \(\alpha_{N_{k}}\leq \alpha\), where \(\alpha>0\) obeys (4). So, (4) holds as claimed.
We present in Algorithm 2 the pseudo-code of the above described method to find an approximation of some \(x^{*}\in \mathcal{Z}_{D}(f)\).
Remark 1. Note that we can define \(S_{N_{k}}:=\{ \frac{n-1}{N_{k}},\frac{n}{N_{k}}:n=1,\ldots, N_{k} \}\), because of this set becomes into a dense sequence in \([0,1]\) if \(N_{k}\rightarrow \infty\). The reason to define \(S_{N_{k}}\) as above is because, after some numerical experiments, with this set Algorithm 2 finds more zeros of \(f\) in the set \(D\).
Assume that the while loop in Algorithm 2 ends after \(k^{*}\) iterations. Then, if we denote by \(\# \Sigma\) the number of intervals of the set \(\Sigma\) and by \(\beta_{k}\) the number of function evaluations (F.E.) that uses bisection method (Algorithm 1) to approximate a zero of \(f(\gamma_{\alpha_{N_{k}}}(t))\) in each interval of \(\Sigma\), the number of F.E. in Algorithm 2 is
\[N^{*}:=\underbrace{2 \sum_{k=1}^{k^{*}} N_{k}}_{\substack{\text{F.E. in the for loop of lines 6-12} \\ \text{of Algorithm 2}}} + \underbrace{ \beta_{1} +\ldots + \beta_{\# \Sigma} }_{\substack{\text{F.E. of Algorithm 1 } \\ \text{to find the desired approximation}}} . \label{eq_3_16} \tag{5}\] In a completely analogous way, we can find an upper bound for the computational time of Algorithm 2 in terms of computational time of the for loop of lines 6-12 and the computational time of the bisection method. Also, if we assume that \(\beta\) is an upper bound for \(\beta_{1},\ldots,\beta_{\# \Sigma }\) and \(\nu_{k^{*}}\) is the first sum in (5), we find that \(N^{*}\leq \nu_{k^{*}}+ \# \Sigma \beta\). So, roughtly speaking the computational complexity of Algorithm 2 is, in the worst case, an \(\mathcal{O}(\beta)\).
In this section, by some numerical examples, we will illustrate the feasibility and reliability of Algorithm 2. For the Bisection method (Algorithm 1), we take \(\varepsilon=\delta=10^{-10}\) in all the examples. Also, the notation used in the tables is the following:
(i) For the indicated values of \(k\), \(N_{k}\) is the number of subintervals of \([0,1]\) (of the form indicated in Algorithm 2) where we seek the zeros of the function \(f\).
(ii) The number \(\alpha_{N_{k}}>0\) is the density of the used \(\alpha\)-dense curve.
(iii) \(\# \tilde{\mathcal{Z}}_{D}(f)\) and Avg. Err. \(\tilde{\mathcal{Z}}_{D}(f)\) are, respectively, the cardinality and the average of the error approximations of the set \(\tilde{\mathcal{Z}}_{D}(f)\) found by Algorithm 2, that is, these sets are \[\# \tilde{\mathcal{Z}}_{D}(f) := \# \big\{\gamma_{\alpha}( t^{*})\in D :t^{*} \in [0,1] \textrm{ is found by Algorithm 2} \big\} ,\] and \[\textrm{Avg. Err. } \tilde{\mathcal{Z}}_{D}(f) := \frac{1}{ \# \tilde{\mathcal{Z}}_{D}(f)} \sum_{\gamma_{\alpha}(t^{*}) \in \tilde{\mathcal{Z}}_{D}(f) } | f\big( \gamma_{\alpha}(t^{*}) \big)| ,\] respectively, where \(\gamma_{\alpha}\) is the \(\alpha\)-dense curve in Algorithm 2 for which the algorithm meets the exit condition.
(iv) F.E.and C.T. denote, respectively, the number of function evaluations and the computational time, in seconds, in Algorithm 2.
Example 6. Let \(f:D:=[-1,1]^{2}\longrightarrow \mathbb{R}\) be the function defined as \[f(x,y):=(x^{2}+y^{2})^{3} – 4x^{2}y^{2} ,\quad \textrm{for all } (x,y)\in D. \label{eq_4_10} \tag{6}\] In this example, Algorithm 2 can be used to obtain some points on the plane curve defined by \(f(x,y)=0\). The \(\alpha\)-dense curve used in Algorithm 2 is that of Example 2. We present in Table 1 the obtained results, and in Figure 2 the graphs of \(f(\gamma_{0.04}(t))\) and the set \(\tilde{\mathcal{Z}}_{D}(f)\) returned by Algorithm 2 for the indicated values of \(k,N_{k}\) and \(\alpha_{N_{k}}\).
| \(k\) | \(N_{k}\) | \(\alpha_{N_{k}}\) | \(\# \tilde{\mathcal{Z}}_{D}(f)\) | Avg. Err. \(\tilde{\mathcal{Z}}_{D}(f)\) | F.E. | C.T. |
|---|---|---|---|---|---|---|
| 1 | 10 | 0.040 | 5 | 5.6E-11 | 215 | 0.06 |
| 2 | 50 | 0.020 | 15 | 3.9E-11 | 1017 | 0.44 |
| 3 | 100 | 0.013 | 32 | 5.0E-11 | 2184 | 0.93 |
| 4 | 200 | 0.010 | 64 | 5.2E-11 | 4236 | 1.38 |
Example 7. For computation reasons we consider the space \(\mathbb{R}^{15}\) as an approximation of the space \(\mathbb{R}^{\mathbb{N}}\) of Example 2, endowed with the metric \[\tilde{d}\big( \mathbf{x},\mathbf{y} \big):=\sum_{n=1}^{15} 2^{-n} \frac{|x_{n}-y_{n}|}{1+|x_{n}-y_{n}|},\quad \textrm{for all }\mathbf{x}:=(x_{n})_{n\geq 1},\mathbf{y}:=(y_{n})_{n\geq 1} \in\mathbb{R}^{15} .\] Let \(\mathbf{x}_{0}:=(-1,\frac{1}{2},-\frac{1}{3},\ldots,\frac{1}{10})\in\mathbb{R}^{15}\) and \(f:D:=[0,1]^{15}\longrightarrow \mathbb{R}\) the function \[f(\mathbf{x}):= \big( 1 + \tilde{d}(\mathbf{x},\mathbf{x}_{0} ) \big)^{2}\sin\big( 2\pi \tilde{d}(\mathbf{x},\mathbf{x}_{0} )\big) -\frac{\sqrt{2}}{2},\quad \textrm{for all } \mathbf{x}\in [0,1] ^{15} . \label{eq_4_12} \tag{7}\]
Following Example 3, we will consider the \(\alpha\)-dense curve \[\gamma_{\alpha}(t):=\left\{\begin{array}{lll} \gamma_{\alpha_{0}}^{n}(t),& \textrm{for } n\leq10 \\ \\ t, & \textrm{for } 11\leq n\leq 15 \end{array}\right. \quad \textrm{for all }t\in [0,1] ,\] where \((\gamma_{\alpha_{0}}^{1}(t),\ldots, \gamma_{\alpha_{0}}^{10}(t))\) stands for the \(\alpha_{0}\)-dense curve in \([0,1]^{10}\) of Example 2. The obtained results are presented in Table 2.
| \(k\) | \(N_{k}\) | \(\alpha_{N_{k}}\) | \(\# \tilde{\mathcal{Z}}_{D}(f)\) | Avg. Err. \(\tilde{\mathcal{Z}}_{D}(f)\) | F.E. | C.T. |
|---|---|---|---|---|---|---|
| 1 | 10 | 0.380 | 6 | 2.5E-11 | 974 | 11.5 |
| 2 | 50 | 0.026 | 16 | 2.1E-11 | 2754 | 33.8 |
| 3 | 100 | 0.003 | 45 | 4.7E-11 | 7049 | 83.62 |
| 4 | 200 | 0.002 | 68 | 4.5E-11 | 11756 | 143.8 |
Example 8. Let the set \[D:=\big\{ \sum_{n= 0}^{6} a_{n}T_{n}(x): |a_{n}|\leq \frac{1}{n^{2}} \textrm{ for each } n\geq 0 \big\}\subset \mathcal{C}[-1,1] .\] So, as in the previous example, for computational reasons, \(D\) is a truncated subset of that given in Example 4. Also, let \(D:=\prod_{i=0}^{6}[-\frac{1}{n^{3}},\frac{1}{n^{3}}]\) and, \(\gamma_{\alpha_{0}}\) an \(\alpha_{0}\)-dense curve in \(D\), for some \(\alpha_{0}>0\), as given in Example 2. Following Example 3, we will consider the \(\alpha\)-dense curve \[\gamma_{\alpha}(t):=\left\{\begin{array}{lll} \gamma_{\alpha_{0}}^{n}(t),& \textrm{for } 0\leq n\leq 5 \\ \\ \frac{1}{216} \sin(2\pi t), & \textrm{for } n=6 \end{array}\right. \quad \textrm{for all }t\in [0,1] ,\] with \(\alpha=\alpha_{N_{k}}\) for all \(k\geq 1\) is indicated in Table 3. Let \(f:D\longrightarrow \mathbb{R}\) defined as \[f(h)(x):=2 \ln\big(1+ \big| \int_{-1}^{1} h(x)dx \big| \big) + \Big[\int_{-1}^{1} h(x)dx \Big]^{2} -\frac{1}{2} \label{eq_4_14} \tag{8}\] for each \(h\in D\). We show in Table 3 the results returned by Algorithm 2.
| \(k\) | \(N_{k}\) | \(\alpha_{N_{k}}\) | \(\# \tilde{\mathcal{Z}}_{D}(f)\) | Avg. Err. \(\tilde{\mathcal{Z}}_{D}(f)\) | F.E. | C.T. |
|---|---|---|---|---|---|---|
| 1 | 10 | 0.031 | 1 | 2.3E-11 | 149 | 0.5 |
| 2 | 50 | 0.031 | 3 | 8.0E-11 | 461 | 1.1 |
| 3 | 100 | 0.031 | 2 | 5.4E-11 | 444 | 1.1 |
| 4 | 200 | 0.031 | 7 | 6.6E-11 | 1221 | 1.9 |
In Figure 3 we show the graph of the function \(f(\gamma_{0.031}(t))\) and two functions in the set \(\tilde{\mathcal{Z}}_{D}(f)\) returned by Algorithm 2.
In the present paper we have proved, under suitable conditions and by using \(\alpha\)-dense curves, the existence of zeros of a given continuous function \(f:D\subseteq (X,d) \longrightarrow \mathbb{R}\). Moreover, from our main result we provide a numerical method based on \(\alpha\)-dense curves and the bisection method, the pseudo-code shown in Algorithm 2 to approximate some zeros of such function in the set \(D\). The feasibility and reliability of our method are illustrated with numerical examples in §4.
As we have pointed out in §1, the bisection method has many generalizations and improvements, so in future works could be interesting to study and generalize some of these methods by using \(\alpha\)-dense curves.
Although Algorithm 2 is a generalization of the bisection method, it is not free of drawbacks. For instance, the proposed method in the present paper has the same limitations that the bisection method. That is to say, a change of sign of the function is necessary to guarantee that Algorithm 2 works. Indeed, consider the function \(f(x,y):=(x-0.5)^{2}+(y-0.5)^{2}\) defined on \([0,1]^{2}\) and \(\gamma_{\alpha}\) the \(\alpha\)-dense curve of Example 2, for any \(\alpha>0\). Clearly, \(\mathcal{Z}_{[0,1]^{2}}(f)=\{(0.5,0.5)\}\) but \(f(\gamma_{\alpha}(t^{*}))\neq 0\) for each \(t^{*}\in[0,1]\) as \(\gamma_{\alpha}(t)\neq (0.5,0.5)\) for each \(t\in[0,1]\). In other words, Algorithm 2 is not able to approximate all the zeros of \(f\) in the densifiable set \(D\).
Gautschi, W. (2011). Numerical Analysis. Springer Science & Business Media.
Hoffman, J. D., & Frankel, S. (2018). Numerical Methods for Engineers and Scientists. CRC press.
Etesami, R., Madadi, M., Mashinchi, M., & Ganjoei, R. A. (2021). A new method for rooting nonlinear equations based on the Bisection method. MethodsX, 8, 101502.
GALVÁN, M. L. (2019). The multivariate bisection algorithm. Revista De La Unión Matemática Argentina, 60(1), 79-98.
Gulshan, G., Budak, H., Hussain, R., & Sadiq, A. (2023). Generalization of the bisection method and its applications in nonlinear equations. Advances in Continuous and Discrete Models, 2023(1), 18.
Samuelsson, C. (2015). The stochastic simplex bisection algorithm. Procedia Computer Science, 51, 855-864.
Wu, X. (2005). Improved Muller method and bisection method with global and asymptotic superlinear convergence of both point and interval for solving nonlinear equations. Applied Mathematics and Computation, 166(2), 299-311.
Mora, G., & Cherruault, Y. (1997). Characterization and generation of \(\alpha\)-dense curves. Computers & Mathematics with Applications, 33(9), 83-91.
Sagan, H. (2012). Space-Filling Curves. Springer Science & Business Media.
Mora, G. (2005). The Peano curves as limit of \(\alpha\)-dense curves. RACSAM, 99(1), 23-28.
Cherruault, Y., & Mora, G. (2005). Optimisation Globale: Théorie Des Courbes [Alpha]-Denses. Economica.
García, G. (2023). Continuous global optimization on fractals through \(\alpha\)-dense curves. Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas, 117(4), 165.
Garcıaa, G. (2022). Generation of \(\alpha\)-dense curves in infinite dimensional Banach spaces. Functional Analysis, Approximation and Computation 14(1), 55–65 (2022).
García, G. (2019). Approximating roots of nonlinear systems by \(\alpha\)-dense curves. Numerical Algorithms, 82(3), 749-760.
García, G. (2024). A numerical method to approximate the solutions of nonlinear systems in densifiable sets. Numerical Algorithms, 96(4), 1925-1943.
Garcıa, G. (2017). Interpolation of bounded sequences by \(\alpha\)-dense curves. J. Interpolat. Journal of Interpolation and Approximation in Scientific Computing, 2017, 1-9.
García, G., & Mora, G. (2021). Approximating multiple integrals of continuous functions by \(\delta\)-uniform curves. Annali Dell’universita’di Ferrara, 67(1), 59-71.
Mora, G., & Mira, J. A. (2003). Alpha-dense curves in infinite dimensional spaces. International Journal of Pure and Applied Mathematics, 5(4), 433-445.
Rahal, M., Abdelkader, Z., & Rachid, E. (2019). Generating \(\alpha\)-dense curves in non-convex sets to solve a class of non-smooth constrained global optimization. Croatian Operational Research Review, 289-314.
Schaefer, H.H. (1971). Topological Vector Spaces, Springer-Verlag, New York.
Mora, G., & Redtwitz, D. A. (2011). Densifiable metric spaces. Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas, 105(1), 71-83.
Silverman, R. A. (1972). Special Functions and Their Applications. Courier Corporation.
Toledano, J. M. A., Benavides, T. D., & Acedo, G. L. (1997). Measures of noncompactness in metric fixed point theory (Vol. 99). Springer Science & Business Media.
