Abstract Generated abstract
The paper develops a variant of the chord method in which interpolation nodes are chosen as the zeros of the quadratic Chebyshev polynomial, aiming to reduce interpolation remainders and improve convergence estimates. It first proves an error estimate for multivariable functions with bounded second derivatives, then applies the construction to nonlinear integral equations with Uryson operators and to systems of ordinary differential equations. Under specified boundedness and smallness conditions, the resulting linearized successive approximations are shown to converge uniquely to the solution, with explicit convergence-rate bounds. The method is presented as applicable to broader nonlinear problems treated by Newton, chord, and Chaplygin methods, with weaker initial restrictions in certain cases and without requiring a constant sign of the second derivative for differential equations.
Full Text
On the Method of Chords Constructed from Chebyshev Nodes
I. M. Derendyaev
(Presented by Academician A. N. Kolmogorov, 7 January 1958)
Mathematics
Proofs of convergence for the known approximate methods for solving various classes of nonlinear equations—the Newton method (tangent method) and the chord method—are based on similar formulas. For the Newton method such a formula is the estimate of the remainder term in Taylor’s series; for the chord method, the estimate of the remainder term in Newton’s interpolation formula:
\[ \left| f(x)-f(x_0)-\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)\right| \leq \max |f'(\tilde{x})| \cdot |(x-x_0)(x-x_1)|, \tag{A} \]
where
\[ \alpha \leq \tilde{x} \leq \beta,\qquad \alpha=\min(x_0,x_1,x),\qquad \beta=\max(x_0,x_1,x). \]
The chord method, however, possesses greater flexibility than the Newton method, owing to the fact that we still have freedom in choosing the interpolation nodes.
All that follows is based on one special case of choosing the interpolation nodes, for which it is possible to improve the general estimates of the Newton method and of the classical chord method.
Let us explain the basic idea of the method we have investigated. The convergence of the chord method will be faster the smaller the right-hand side of estimate (A). We achieve this by taking, as the nodes \(x_0, x_1\), the zeros of the quadratic Chebyshev polynomial. As is known, with such a choice of interpolation nodes the quadratic polynomial \(|(x-x_0)(x-x_1)|\) deviates least from zero.
In what follows, the zeros \(z_0, z_1\) of the quadratic Chebyshev polynomial for the interval \([\underline{x}, \bar{x}]\) will simply be called Chebyshev nodes.
Lemma 1. Let \(I\) denote a domain of \(m\)-dimensional Euclidean space \((\underline{x}_i \leq x_i \leq \bar{x}_i,\ i=1,\ldots,m)\), and let \(z_{0i}, z_{1i}\) be the Chebyshev nodes for the interval \([\underline{x}_i,\bar{x}_i]\):
\[ z_{0i}=\frac14\left[(2+\sqrt{2})\underline{x}_i+(2-\sqrt{2})\bar{x}_i\right], \]
\[ z_{1i}=\frac14\left[(2-\sqrt{2})\underline{x}_i+(2+\sqrt{2})\bar{x}_i\right] \qquad (i=1,\ldots,m). \]
Let \(f(x_1,\ldots,x_m)\) be a function continuous, together with \(f'_{x_i}\), in \(I\), whose second derivatives are bounded in the domain \(I\):
\[ \left|\frac{\partial^2 f}{\partial x_i \partial x_k}\right|<K \qquad (i,k=1,\ldots,m) \]
and suppose the inequalities
\[ \bar{x}_i-\underline{x}_i \leq 2r \qquad (i=1,\ldots,m) \]
hold.
Then for any \(x_i\) from the domain \(I\) we shall have the estimate
\[ \left| f(x_1,\ldots,x_m)-f(z_{01},\ldots,z_{0m})- \sum_{i=1}^{m} \frac{ f(z_{01},\ldots,z_{0\,i-1},z_{1i},z_{0\,i+1},\ldots,z_{0m})- f(z_{01},\ldots,z_{0m}) }{ z_{1i}-z_{0i} } (x_i-z_{0i}) \right| \leq \]
\[ \leq (2m-{}^{7}/_{4})\,mKr^2 . \]
Consider the solution of a nonlinear integral equation with a Uryson operator:
\[ x(s)-\int_{0}^{1} K[s,t,x(t)]\,dt=0. \tag{1} \]
Let the solution \(x^*(s)\) of this integral equation exist in the domain
\(I_0\bigl(|x(s)-x_0|\leq r_0,\ 0\leq s,t\leq 1\bigr)\), where \(x_0,r_0\) are constants.
We require that the kernel \(K(s,t,x)\) satisfy the following conditions:
a) the kernel \(K(s,t,x)\) is continuous in the domain
\(I_1\bigl(|x(s)-x_0|\leq (1+a/2)r_0,\ 0\leq s,t\leq 1\bigr)\), where the number \(a\) is defined below;
b) the derivative \(K'_x(s,t,x)\) is continuous and has in \(I_1\) a bounded resolvent \(|R_x|\leq B\);
c) \(|K''_{xx}(s,t,x)|\leq K\) in the domain \(I_1\).
We shall find successive approximations from the linear integral equations:
\[ x_{n+1}(s)-\int_{0}^{1} \overline K[s,t,x_n(t)] \bigl[x_{n+1}(t)-z_0^{(n)}(t)\bigr]\,dt - \]
\[ -\int_{0}^{1} K[s,t,z_0^{(n)}(t)]\,dt=0 \qquad (n=0,1,\ldots), \tag{2} \]
where
\[ \overline K[s,t,x_n(t)] = \frac{ K[s,t,z_1^{(n)}(t)]-K[s,t,z_0^{(n)}(t)] }{ z_1^{(n)}(t)-z_0^{(n)}(t) }. \]
The curves \(x=z_0^{(n)}(t)\), \(x=z_1^{(n)}(t)\), which are lines of Chebyshev nodes, are found from the formulas
\[ z_0^{(n)}(t)=\frac12\bigl[2x_n(t)-r_n\sqrt2\bigr], \qquad z_1^{(n)}(t)=\frac12\bigl[2x_n(t)+r_n\sqrt2\bigr], \qquad r_n=\left(\frac a4\right)^{2^n-1}r_0 . \]
Theorem 1. If conditions a), b), c) are fulfilled and, moreover, the inequality
\[ a=(B+1)Kr_0<4 \]
holds, then the sequence \(\{x_n(s)\}\), determined from equations (2), converges to the solution \(x^*(s)\) of equation (1), unique in the domain \(I_0\). The rate of convergence is characterized by the estimate
\[ |x_n(s)-x^*(s)|\leq \left(\frac a4\right)^{2^n-1}r_0 . \]
Let us turn to the solution of a system of ordinary differential equations. Using abbreviated notation with vector functions, instead of the system we shall have one vector equation
\[ x'=f(t,x), \tag{3} \]
where \(x(t)=[x_1(t),\ldots,x_m(t)]\) is the required \(m\)-dimensional vector function of \(t\), \(f(t,x)=[f_1(t,x),\ldots,f_m(t,x)]\) is a given vector, with the initial condition \(x|_{t_0}=y_0\).
Let, by definition: a) \(|x|=\max_i x_i\), b) \(y\geq x\), if \(y_i\geq x_i,\ i=1,\ldots,m\).
The successive approximations \(x_{n+1}=(x_{n+1,1},\ldots,x_{n+1,m})\) are determined from the linear equations:
\[ x'_{n+1}-\Phi_{n+1}(t)\bigl(x_{n+1}-z^{(n)}_0\bigr)-f\bigl(t,z^{(n)}_0\bigr)=0 \qquad (n=0,1,\ldots), \tag{4} \]
where \(\Phi_{n+1}(t)\) is a linear operator having the matrix
\[ \left\| \frac{ f_k(t,z^{(n)}_{01},\ldots,z^{(n)}_{0\,i-1},z^{(n)}_{1i},z^{(n)}_{0\,i+1},\ldots,z^{(n)}_{0m}) - f_k(t,z^{(n)}_{01},\ldots,z^{(n)}_{0m}) }{ z^{(n)}_{1i}-z^{(n)}_{0i} } \right\| \qquad (i,k=1,\ldots,m). \]
The Chebyshev-node lines \(z^{(n)}_0(t)=(z^{(n)}_{01},\ldots,z^{(n)}_{0m})\), \(z^{(n)}_1(t)=(z^{(n)}_{11},\ldots,z^{(n)}_{1m})\) are defined below.
Suppose two vector-functions \(x_0,\overline{x}_0\) are known such that on the half-segment \((t_0,t_1]\):
\[ \underline{x}_0<x^*<\overline{x}_0, \qquad x_0|_{t_0}=\overline{x}_0|_{t_0}=y_0. \]
Denote \(x_0=\frac12(\underline{x}_0+\overline{x}_0)\), \(r_0=\frac12(\overline{x}_0-\underline{x}_0)\).
We require that the right-hand side of equation (3) satisfy the following conditions:
1) the functions \(f_i(t,x)\), together with the first derivatives \(\partial f_i/\partial x_k\) \((i,k=1,\ldots,m)\), are continuous in the region \(R\) defined by the inequalities
\[ |x-x_0|\leq [1+2\max_{n,t}\psi_n(t)]\,|r_0|, \qquad t_0\leq t\leq t_1, \]
and, moreover,
\[ 0<\frac{\partial f_i}{\partial x_k}\leq L \qquad (i,k=1,\ldots,m); \]
2) the second derivatives are bounded in the region \(R\)
\[ \left|\frac{\partial^2 f_j}{\partial x_i\,\partial x_k}\right|\leq K \qquad (i,k,j=1,\ldots,m); \]
3) in the region \(R\) the inequality
\[ \exp[m(u-t)L]\leq M, \qquad t_0\leq t\leq u\leq t_1. \]
holds.
If we set
\[ \psi_n(t)= \left[\left(2m-\frac74\right)mKM|r_0|(t-t_0)\right]^{2^n-1} \left[ \prod_{k=1}^{n-1}(2^{k+1}-1)^{2^{\,n-k-1}} \right]^{-1}, \]
then the Chebyshev-node lines are determined by the formulas
\[ z^{(n)}_{0i}(t)=\frac12\left[2x_{ni}(t)-\psi_n(t)|r_0|\sqrt2\right], \]
\[ z^{(n)}_{1i}(t)=\frac12\left[2x_{ni}(t)+\psi_n(t)|r_0|\sqrt2\right] \]
\[ (i=1,\ldots,m;\ n=1,2,\ldots). \]
The proof of convergence of the successive approximations is based on the following lemma.
Lemma 2. For the numerical sequence
\[ r_0,\quad r_1=ar_0,\ldots,\quad r_n= \frac{a^{2^n-1}r_0}{ \displaystyle\prod_{k=1}^{n-1}(2^{k+1}-1)^{2^{\,n-k-1}} },\ldots, \]
where \(a,r_0\) are positive numbers, to tend to zero it is sufficient that the number \(a\) satisfy the inequality
\[ a<\xi\simeq\sqrt6. \]
The exact value of $\xi$ is equal to the limit of a certain sequence:
\[ \xi=\lim_{n\to\infty}\left[(2^{n+1}-1)\prod_{k=1}^{n-2}(2^{k+1}-1)^{2^{\,n-k-2}}\right]^{\frac{1}{2^n-1}} . \]
Theorem 2. If conditions 1)--3) and the condition
\[ a(t)=KM|r_0|(t-t_0)<\frac{\xi}{(2m-{}^7\!/{}_4)m} \]
are satisfied, then the successive approximations determined from equations (4) converge to the solution of equation (3) at a rate characterized by the estimate
\[ |x^*-x_n|<\psi_n(t)|r_0|. \]
The solution of equation (3) is unique in the domain $R_0(x_0<x<\bar{x}_0,\; t_0\leq t\leq t_1)$.
The method considered can be applied to the solution of all classes of equations that are solved by the methods of Newton and Chaplygin, for example, algebraic and transcendental equations, integro-differential equations, and partial differential equations.
In the case of a single first-order differential equation, condition 1) can be weakened: it is sufficient to require $df/dx<L$. The method contains the weaker requirement $a<4$, as compared with Newton’s method, where $a<2$. For a differential equation this condition is replaced by the still weaker one $a<4\sqrt{6}$. Thanks to this, the choice of initial approximations is facilitated, and the method can be used in combination with Newton’s method as the first step in computations.
The rate of convergence of the approximations exceeds the rate of convergence of Newton’s method under the conditions of I. P. Mysovskikh (1).
For differential equations the estimate of the rate of convergence coincides with the estimate given by E. V. Voronovskaya (2) for a modification of S. A. Chaplygin’s method constructed using linear polynomials of best approximation.
When applied to differential equations, the method does not include the requirement that the second derivative have constant sign.
Perm Mining Institute
Received
7 I 1958
REFERENCES
- I. P. Mysovskikh, Vestn. Leningrad Univ., Ser. Math., Phys. and Chem., No. 11, issue 4, 25 (1953).
- E. V. Voronovskaya, Prikl. Mat. i Mekh., 19, 121 (1955).