Abstract Generated abstract
This paper studies iterative methods for solving the transcendental equation f(x)=0 under minimal regularity assumptions. It introduces auxiliary functions based on a strictly increasing comparison function g and derives bounds and monotonicity conditions used to locate zeros on intervals to the right or left of an initial point. The main results give necessary and sufficient conditions for iterative processes to converge to the minimal zero in (x0,b) or the maximal zero in (a,x0), requiring only continuity of f in the basic construction. Additional variants using absolute values and fixed lower bounds are discussed, together with comparisons of step size and conditions under which convergence is at least geometric.
Full Text
G. I. CHAVDIROV
ON THE THEORY OF ITERATIVE PROCESSES
(Presented by Academician A. N. Tikhonov on 2 III 1967)
The solution of many applied problems leads to the solution of the transcendental equation
\[ f(x)=0. \tag{1} \]
There are many methods for solving it, the most widespread being iterative ones. To justify the convergence of an iterative process for \(f(x)\), boundedness of the derived numbers in a neighborhood of its zeros is required. Generally speaking, the convergence of the process depends on the initial approximations. In paper (1), iterative processes were constructed which, under one-sided boundedness of the derived numbers of \(f(x)\), converge to the minimal zero of \(f(x)\) on \((x_0,b)\) or to the maximal zero of \(f(x)\) on \((a,x_0)\) (independently of the initial approximations).
In the present paper iterative processes are constructed and investigated which converge to the minimal zero of \(f(x)\) on \((x_0,b)\) or to the maximal zero of \(f(x)\) on \((a,x_0)\) (independently of the initial approximations). Here only continuity of \(f(x)\) on \((a,b)\) is required.
For simplicity in the formulation of the theorem, we adopt the following notation. Denote by \(\mathcal K\) the set of all functions in \(C(-\infty,\infty)\) that are strictly increasing and tend to \(+\infty\) or to \(-\infty\) as \(x\to+\infty\) or \(x\to-\infty\), respectively. Denote by \(\eta_f\) the greatest lower bound of the set of zeros of \(f(x)\) in \((x_0,b)\), and by \(\xi_f\) the least upper bound of the set of zeros of \(f(x)\) on \((a,x_0)\). Denote by \(\mathcal E\) the set of those \(x\in(a,b)\) for which \(f(x)-qf(x_0)<0\), where \(0<q<1\) is a certain fixed number.
Let us consider the function
\[ M(q,g,x_0,x)=[f(x)-qf(x_0)]/[g(x)-g(x_0)]. \]
It is not difficult to see that \(M(q,g,x_0,x)\), as a function of the variable \(x\), is continuous on \((a,x_0)\) and \((x_0,b)\);
\[ \lim_{x\to x_0-0} M(q,g,x_0,x)=+\infty,\qquad \lim_{x\to x_0+0} M(q,g,x_0,x)=-\infty . \]
If \(\mathcal E\cap(a,b)\) is empty, then equation (1) has no solutions in \((a,b)\). For computing the exact lower and exact upper bounds of the function \(M(q,g,x_0,x)\) with respect to \(x\), it is useful to establish conditions under which the function \(M(q,g,x_0,x)\) is monotone with respect to \(x\).
Theorem 1. If \(f'(x)\) and \(g'(x)\) exist on \((x_0,b)\), the derivative \(g'(x)>0\) is finite, and
\[ \left| \begin{matrix} f'(x) & f'(\xi)\\ g'(x) & g'(\xi) \end{matrix} \right|<0, \]
when \(x_0<\xi\le x<b\), then \(M(q,g,x_0,x)\) decreases with respect to \(x\) on \((x_0,b)\).
One can establish conditions under which the function \(M(q,g,x_0,x)\) increases with respect to \(x\) on \((x_0,b)\).
It is not difficult to prove that the function \(M(q,g,x_0,x)\) is bounded below on \((x_0,b)\) and bounded above on \((a,x_0)\). With the aid of \(M(q,g,x_0,x)\) we construct the function
\[ P_{+}(q,g,x_0)=\inf_{x_0<x\le b} M(1,g,x_0,x). \]
It is clear that: 1) \(P_{+}(q,g,x_0)\) exists and is finite; 2) if \(\mathcal E\cap(x_0,b)\) is nonempty, then \(P_{+}(q,g,x_0)<0\); 3) \(P_{+}(q,ag,x_0)\) is monotone with respect to \(a\) and decreases with respect to \(q\).
Lemma 1. If \(f'(x)\) and \(g'(x)\) exist, with \(g'(x)>0\) and finite on \((x_0,b)\), then
\[ P_+(q,g,x_0)\ge \inf_{x_0\le x\le b}\frac{f'(x)}{g'(x)}+(1-q)\frac{f(x_0)}{g(b)-g(x_0)}. \]
Lemma 2. If \(\mathscr E\cap (x_0,b)\) is empty, then
\[ P_+(q,g,x_0)\ge -\frac{\max_{x_0\le x\le b}|f(x)|+qf(x_0)} {g(x_0+\delta)-g(x_0)}, \]
where \(\delta>0\) is such that \(f(x)-qf(x_0)\ge 0\) on \((x_0,x_0+\delta)\).
Obviously, such a \(\delta\) exists, since \(f(x)\in C(a,b)\), \(0<q<1\), and, moreover, \(f(x_0)>0\), where \(x_0\in(a,b)\).
Lemma 3. If on \([\alpha,\beta]\) \(f(x)>0\), where \([\alpha,\beta]\subset(a,b)\), then \(P_+(q,g,x_0)\) is bounded below with respect to \(x_0\in[\alpha,\beta]\).
In terms of \(P_+(q,g,x_0)\) one can prove existence theorems for solutions of equation (1).
Theorem 2. If
\[ P_+(q,g,x_0)\le qf(x_0)/[g(x_0+\delta)-g(x_0)] \]
(where \(\delta>0\) is such that \(f(x)-qf(x_0)\ge 0\) on \((x_0,x_0+\delta)\)), then equation (1) has at least one solution on \((x_0,b)\).
Theorem 3. If there exists a number \(\xi\in(x_0,b)\) such that on \((x_0,\xi)\) \(f'(x)\) and \(g'(x)\) exist and the inequality
\[ \inf_{x_0\le x\le \xi}\frac{f'(x)}{g'(x)}[g(x)-g(\xi)]\ge f(x_0), \]
holds, then equation (1) has at least one solution on \((x_0,\xi)\).
With the aid of the function \(P_+(q,g,x_0)\) one can construct an iterative process that converges to \(\eta_f\).
Theorem 4. In order that the sequence obtained in the process
\[ x_{n+1}=g^{-1}\left[g(x_n)-\frac{qf(x_n)}{P_+(q,g,x_n)}\right], \tag{A} \]
converge to \(\eta_f\), it is necessary and sufficient that: 1) \(P_+(q,g,x_n)<0\), if \(f(x_n)\ne 0\); 2) all elements of the sequence \(x_n\) do not exceed the number \(b\).
Here \(g^{-1}\) denotes the function inverse to \(g\), whose existence follows from the definition of the set \(\mathscr K\).
Remark. If equation (1) has at least one solution on \((x_0,b)\), then all the conditions of Theorem 4 are fulfilled, and the sequence \(\{x_n\}\) obtained in the process (A) converges to \(\eta_f\).
It is not difficult to show that if in the process (A) one replaces \(g(x)\) by \(mg(x)\), \(m>0\), then the same sequence \(\{x_n\}\) is obtained.
One can construct the process
\[ x_{n+1}=g^{-1}[g(x_n)-qf(x_n)/P_-(q,g,x_n)], \tag{A\(_0\)} \]
where
\[ P_-(q,g,x_n)=\sup_{a\le x\le x_n} M(q,g,x_n,x). \]
For the process (A\(_0\)) the following holds.
Theorem 5. The sequence obtained in the process (A\(_0\)) converges to \(\xi_f\) if and only if: 1) \(P_-(q,g,x_n)>0\) for all \(x_n\) for which \(f(x_n)\ne 0\); 2) all elements of the sequence \(\{x_n\}\) exceed the number \(a\).
Remark. If equation (1) has at least one solution on \((a,x_0)\), then the sequence \(\{x_n\}\) obtained in the process (A\(_0\)) converges to \(\xi_f\).
With the help of the function
\[ \overline{M}(q,g,x_0,x)=\bigl[|f(x)|-qf(x_0)\bigr]/[g(x)-g(x_0)] \]
one can construct
\[ \overline{P}_{+}(q,g,x_0)=\inf_{x_0\le x\le b}\overline{M}(q,g,x_0,x). \]
It is clear that \(\overline{P}_{+}(q,g,x_0)\ge P_{+}(q,g,x_0)\). Therefore
\[ \overline{P}_{+}(q,g,x_0)\ge -qf(x_0)/[g(x_0+\delta)-g(x_0)], \]
where \(\delta>0\) is a number such that \(f(x_0)-qf(x_0)>0\) on \((x_0,x_0+\delta)\).
If one constructs the process by the formula
\[ x_{n+1}=g^{-1}\bigl[g(x_n)-qf(x_n)/\overline{P}_{+}(q,g,x_n)\bigr], \tag{A_1} \]
then the conditions necessary and sufficient for the convergence of the sequence \(\{x_n\}\), which is obtained in the process \((A_1)\), are all the conditions of Theorem 4 with the sole difference that, in the statement of this theorem, instead of \(P_{+}(q,g,x_n)\) one must take \(\overline{P}_{+}(q,g,x_n)\). Suppose that \(P_{+}(q,g,\xi)\) is bounded below relative to \(\xi\in(x_0,b)\) by some number \(m\), and equation (1) has at least one solution on \((x_0,b)\). Then the sequence
\[ x_{n+1}=g^{-1}\bigl[g(x_n)-qf(x_n)/m\bigr] \]
converges to \(\eta_f\).
Analogously to the processes \((A_0)\) and \((A_1)\), one can construct processes that converge to \(\xi_f\).
Remark. If equation (1) has at least one solution on \((x_0,b)\), then \(\overline{P}_{+}(q,g,x_0)\) and, consequently, \(P_{+}(q,g,x_0)\) cannot be positive. Therefore the sequences obtained in the processes \((A)\), \((A_1)\), \((A_2)\) are nondecreasing. An analogous remark holds for the process \((A_0)\).
Theorem 6. Let
\[ x_1=g^{-1}\bigl[g(x_0)-qf(x_0)/P_{+}(q,g,x_0)\bigr], \]
\[ \overline{x}_1=g^{-1}\bigl[g(x_0)-qf(x_0)/\overline{P}_{+}(q,g,x_0)\bigr], \]
and, moreover, \(\mathcal{E}\cap(x_0,b)\) be nonempty. Then \(\overline{x}_1\ge x_1\).
Theorem 7. Let in the processes
\[ x_1=g_1^{-1}\bigl[g_1(x_0)-qf(x_0)/m\bigr],\qquad \overline{x}_1=g_2^{-1}\bigl[g_0(x_0)-qf(x_0)/m\bigr] \]
and 1) \(P_{+}(q,g_i,x_0)\ge m,\ i=1,2;\) 2) \(g_1(x_0)=g_2(x_0)\), \(g_1'(x)>g_2'(x)\) for \(x\in(x_0,b)\). Then \(\overline{x}_1<x_1\).
The rate of convergence in the process \((A_1)\) depends on \(q\), \(g\), and \(x_0\). It can be shown that if in the process \((A_1)\) \(\mathcal{E}\cap(x_0,b)\) is nonempty and \(q_1>q_2\), then \(x_1(q_1,g,x_0)>x_2(q_1,g,x_0)\) for identical initial approximations.
In studying the rate of convergence of the sequence \(\{x_n\}\) obtained in the process \((A)\), one has to impose on \(f(x)\) and \(g(x)\) certain additional conditions.
Theorem 8. Let: 1) \(f(x)\) and \(g(x)\) have derivatives on \((\xi,\eta_f)\), with: a) \(f'(x)/g'(x)<r_0<0\) for \(x\in(\xi,\eta_f)\); b) \(0<g'(x_{n+1})/g'(x_n)<r\), for \(x_n\in(\xi,\eta_f)\), where \(x_0<\xi<\eta_f\); 2) \(r_2\le P_{+}(q,g,x)\le r_3<0\); 3) \((qr_0+r_3/r_1)/r_2>1\). Then, beginning with some index, the series
\[ \sum_{n=1}^{\infty}(x_{n+1}-x_n) \]
will decrease no more slowly than a geometric progression.
I express my gratitude to Academician A. N. Tikhonov, Professor V. A. Il’in, and Professor K. T. Akhmedov for useful discussions of the work.
Azerbaijan State University
named after S. M. Kirov
Received
30 I 1967
REFERENCES
- G. I. Chadyrov, Problems of Computational Mathematics and Computer Technology, Baku, 1965.