Abstract Generated abstract
This paper develops operator-theoretic generalizations of Newton and Chaplygin methods for solving nonlinear equations in ordered Banach-type and K-spaces. It replaces derivative inverses in iterative schemes by more general auxiliary operators, not necessarily invertible, and gives convergence conditions using monotone majorant operators, Volterra operators, and ordered interval estimates. The results include error bounds for a Newton-type iteration, comparison theorems for additive operators, existence and uniqueness criteria based on operator inequalities, and two-sided Chaplygin-type algorithms producing monotone sequences that bracket least and greatest solutions. The paper also indicates how truncated Volterra series yield computational schemes intermediate between simple fixed-point iteration and methods using exact inverse operators.
Full Text
MATHEMATICS
S. N. SLUGIN
ON THE THEORY OF THE METHODS OF NEWTON AND CHAPLYGIN
(Presented by Academician S. L. Sobolev, 14 I 1958)
- In an analogue of Newton’s method \((^1)\) for the approximate solution of the equation \(P(x)=0\), the algorithm
\[ x_{n+1}=x_n-\Gamma_n^{-1}P(x_n), \tag{1} \]
is used, where \(\Gamma_x=P'(x_n)\) or \(\Gamma_n=P'(x_0)\). Instead of the derivative operators \(\Gamma_n\) in (1), one may take an operator \(L\), having an inverse \(L^{-1}\), “close” to \(P'(x)\) in the Banach norm \((^2)\) (our notation). We may impose weaker restrictions on the operator \(L\) and choose a simpler (not necessarily invertible) operator convenient for computations.
Let \(X\) be a space of type \((B_K)\) \((^3)\). We shall use the notation:
\[ V^n(z)=V[V^{n-1}(z)], \qquad V^0=I, \qquad I(x)\equiv x, \qquad \Delta U=U(x+\Delta x)-U(x). \]
Theorem 1. Suppose that on the set \(G\subset X\): 1) \(|\Delta U|\le V(|\Delta x|)\), where \(U=I-LP\); 2) the operator \(V\) is monotonically increasing; 3) \(G\) contains the bounded sphere \((x_0,R)\):
\[ |x-x_0|\le R=\sum_{k=0}^{\infty}V^k(z), \qquad z=|LP(x_0)|; \tag{2} \]
4) the operator \(LP\) is \((bk)\)-continuous; 5) the equation \(L(y)=0\) has the unique zero solution.
Then the algorithm
\[ x_{n+1}=x_n-LP(x_n)\qquad (n=0,1,2,\ldots) \tag{3} \]
converges in the sphere \((x_0,R)\) to the solution \(x^*\) of the equation \(P(x)=0\) with rate
\[ |x_n-x^*|\le \sum_{k=n}^{\infty}V^k(z). \tag{4} \]
For condition 2) it is sufficient that the operator \(V\) be additive; for 4), \((o)\)-continuity of \(V\) is sufficient; for 5), additivity and invertibility of the operator \(L\) are sufficient. If \(V\) is not additive, then in the inequalities (2), (4) one may take \(|V_k|\), and, in general, a stronger estimate is obtained than when using the ordinarily employed (in Banach spaces) power \(\|V\|^k\) or even the norm \(\|V^k\|\) of the iteration.
The operator \(V\) is called Volterra if \((I-V)^{-1}=\sum_{k=0}^{\infty}V^k\). In this case \(R=(I-V)^{-1}(z)\). If \(V\) is additive, then \(|x_n-x^*|\le V^n(R)\).
- In what follows \(X\) is a \(K\)-space \((^3)\). For practical estimates of a solution it is sometimes necessary to establish an operator analogue of Chaplygin’s theorem—
Lygina [^4] on differential inequalities, i.e., the establishment of conditions sufficient for the inequality \(P(x)\geq 0\) to imply \(x\geq x^*\), where \(P(x^*)=0\). For an additive invertible operator \(P\) this means its positive invertibility, i.e., \(P^{-1}>0\).
Theorem 2 (comparison of additive operators). If the operators \(\Gamma\) and \(\Lambda\) are additive and invertible, \(\Gamma>\Lambda\), \(\Gamma^{-1}>0\), \((I-\Gamma^{-1}\Lambda)^n(x)\overset{(o)}{\to}0\) \((n\to\infty)\), then \(\Lambda^{-1}>0\).
Theorem 3 (on operator inequalities). Suppose that on the set \(G\subset X\) the following conditions hold: \(P(x_0)>0\) (or \(<0\)); \(\Gamma(\Delta x)\geq \Delta P\geq \Lambda(\Delta x)\) for \(\Delta x>0\); the operators \(\Gamma\) and \(\Lambda\) are additive and positively invertible; the operator \(\Gamma^{-1}P\) is monotonically continuous; the set \(G\) contains \([x_1,x_0]\) (or \([x_0,x_1]\)), where \(x_1=x_0-\Lambda^{-1}P(x_0)\).
Then on this interval there exists a unique solution of the equation \(P(x)=0\).
From this, in particular, it is not difficult to obtain the comparison theorem from the paper [^5].
- Let us construct an algorithm of Chaplygin type on the basis of replacing the operator \(\Gamma_n^{-1}\) in the algorithm of Theorem 1 of the paper [^6], similarly to how this was done above.
Theorem 4. Suppose that on each \([a,b]\subseteq[x_0,\bar{x}_0]\) there exist additive positively invertible operators \(\underline{\Gamma}(a,b)\) and \(\bar{\Gamma}(a,b)\) such that throughout \([a,b]\)
\[ \underline{\Gamma}(a,b)(x-a)\geq P(x)-P(a),\qquad \bar{\Gamma}(a,b)(b-x)\geq P(b)-P(x). \]
Suppose there exists an additive positively invertible operator \(\Gamma\geq\underline{\Gamma}(a,b)\), \(\Gamma\geq\bar{\Gamma}(a,b)\) on all \([a,b]\), the operator \(\Gamma^{-1}P\) is monotonically continuous, and \(P(x_0)\leq 0\leq P(\bar{x}_0)\).
Define the algorithm
\[ \underline{x}_{n+1}=\underline{x}_n-\underline{L}_n(\underline{z}_n),\qquad \bar{x}_{n+1}=\bar{x}_n-\bar{L}_n(\bar{z}_n), \tag{5} \]
where \(P(\underline{x}_n)\leq \underline{z}_n\leq 0\leq \bar{z}_n\leq P(\bar{x}_n)\), the operators \(L_n\) are positive and homogeneous,
\[ \underline{\Gamma}_n\underline{L}_n\leq I,\qquad \bar{\Gamma}_n\bar{L}_n\leq I,\qquad \underline{\Gamma}_n=\underline{\Gamma}(\underline{x}_n,\bar{x}_n),\quad \bar{\Gamma}_n=\bar{\Gamma}(\underline{x}_n,\bar{x}_n). \]
Then the algorithm determines sequences \(x_n\) satisfying the inequalities
\[ \underline{x}_n\leq \underline{x}_{n+1}\leq \underline{x}\leq \bar{x}\leq \bar{x}_{n+1}\leq \bar{x}_n, \]
where \(\underline{x},\bar{x}\) are the least and greatest solutions on \([x_0,\bar{x}_0]\) of the equation \(P(x)=0\).
For uniqueness of the solution it is sufficient that there exist an additive positively invertible operator \(\Lambda\) such that \(\Delta P\geq \Lambda(\Delta x)\) for \(\Delta x>0\).
If it is known in advance that the solution is unique, then the condition \(x_0\leq \bar{x}_0\) need not be imposed. Instead of the conditions imposed on \(L_n\), it is sufficient to require that \(\underline{\Gamma}_n\underline{L}_n(\underline{z}_n)\geq \underline{z}_n\), \(\bar{\Gamma}_n\bar{L}_n(\bar{z}_n)\leq \bar{z}_n\). Under some additional assumptions concerning \(L_n(z_n)\), the algorithm converges to the solution. Instead of continuity of the operator \(\Gamma^{-1}P\), one may require continuity of the operators \(\Gamma\) and \(P\). This remark also applies to Theorem 3.
Putting \(\Gamma_n=\bar{\Gamma}_n\), \(L_n=\Gamma_n^{-1}\), we obtain the algorithms of the paper [^7].
Theorem 5. If, under the conditions of Theorem 4, the operators \(I-\Gamma_n\) are positive Volterra operators, then one may take as \(L_n\)
\[ \sum_{k=0}^{m}(I-\Gamma_n)^k \]
where \(m\) is arbitrary.
Hence, for \(z_n=P(x_n)\), acting in the space of collections of derivatives, one can, in particular, obtain (concrete) algorithms of work\({}^{8}\). They occupy an intermediate place between the algorithms
\[ x_{n+1}=x_n-P(x_n) \]
and the more complicated, but more rapidly convergent,
\[ x_{n+1}=x_n-\Gamma_n^{-1}P(x_n). \]
- The additivity and positive invertibility condition on the operator \(\Gamma'\), usually used in analogues of Chaplygin’s method\({}^{6,7}\), can be replaced by another one.
Theorem 6. Let the following conditions be fulfilled on the set \(G\subset X\): \(P(x_0)>0\) (or \(<0\)), \(\Gamma(\Delta x)\geq \Delta P\) for \(\Delta x>0\); there exists an operator \(L\) such that \(L>0\), \(\Gamma L\leq I\) (or \(L(y)<0\leq \Gamma L(y)-y\) for \(y<0\)); the equation \(L(y)=0\) has the unique zero solution; the operator \(LP\) is monotonically continuous; \(\Delta U\leq \Delta V\) for \(\Delta x>0\), where \(U=I-LP\); the operator \(V\) is monotonically increasing; the set \(G\) contains the bounded interval
\[ [x_0-R,x_0]\quad (\text{or }[x_0,x_0+R]), \]
where
\[ R=\sum_{k=0}^{\infty}V^k(z),\qquad z=|LP(x_0)|. \]
Then the equation \(P(x)=0\) has on this interval a solution \(x^*\), which can be obtained by algorithm (3), and moreover \(x_n\searrow x^*\) (or \(x_n\nearrow x^*\)) with rate
\[ |x_n-x^*|\leq \sum_{k=n}^{\infty}V^k(z). \]
A consequence of this is Theorem 3 under the additional condition: the operator \(V=I-\Gamma^{-1}\Lambda\) is Volterra. The theorem can be modified by replacing algorithm (3) with an algorithm of the form (5).
Kazan State
University
Received
13 I 1958
CITED LITERATURE
\({}^{1}\) L. V. Kantorovich, DAN, 76, No. 1, 17 (1951).
\({}^{2}\) B. A. Vertgeim, Uspekhi Mat. Nauk, 12, issue 1 (73), 166 (1957).
\({}^{3}\) L. V. Kantorovich, B. Z. Vulikh, A. G. Pinsker, Functional Analysis in Semi-Ordered Spaces, Moscow–Leningrad, 1950.
\({}^{4}\) S. A. Chaplygin, A New Method of Approximate Integration of Differential Equations, Moscow–Leningrad, 1950.
\({}^{5}\) N. V. Azbelev, DAN, 89, No. 4, 589 (1953).
\({}^{6}\) S. N. Slugin, DAN, 103, No. 4, 565 (1955).
\({}^{7}\) A. N. Baluev, Vestn. LGU, No. 13, issue 3, 27 (1956).
\({}^{8}\) G. A. Artemov, DAN, 101, No. 2, 197 (1955).