Abstract
Let \(X,Y\) be two normed spaces and \(P:X\rightarrow Y\) a nonlinear operator. We consider the generalized inverse interpolation polynomial and we generalize the Steffensen method. We give some semilocal convergence results and error estimations for the chord method. We also ellaborate a general Steffensen method for which we give the convergence order.
Authors
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)
Title
Original title (in Romanian)
Consideraţii asupra metodelor iterative obţinute prin interpolare inversă
English translation of the title
Considerations regarding the iterative methods obtained by inverse interpolation
Keywords
inverse interpolation in normed spaces; nonlinear operator equations; chord method; Steffensen method; semilocal convergence
Cite this paper as:
I. Păvăloiu, Consideraţii asupra metodelor iterative obţinute prin interpolare inversă, Studii şi cercetări matematice, 23 10 (1971), pp. 1545-1549 (in Romanian).
About this paper
Journal
Studii şi cercetări matematice
Publisher Name
Academia Republicii S.R.
DOI
Not available yet.
Print ISBN
Not available yet.
Online ISBN
Not available yet.
References
[1]. Ostrowski, A.M., Reçenie uraunenii i sistem uraunenii. Maskva, 1963.
[2]. Popoviciu, Tiberiu, Sur Ia delimítation de l,erreur dans l’apptroximation des racines d’une
equalions par interpolation linieaire au quadratique. Rev.Roum. de math. pures et appl. XIII, 1 (1968), 75-78.
[3]. Pavaloiu, I., Interpolation dans des espaces linieaires normes et applications. Mathematica, Cluj (sub tipar).
Paper (preprint) in HTML form
Considerations regarding the iterative methods obtained by inverse interpolation
OF
1. AN EVALUATION OF THE ERROR IN THE CASE OF THE STRING METHOD
In paper [3], § 5, I gave a method for generating the iterative process of the string, using reverse interpolation. In this paper we will first give an assessment of the error by applying the string method only once, for which, using a suitable method, we will expand the result from the paper [2].
Let the equation be given
{:(1)P(x)=theta:}\begin{equation*}
P(x)=\theta \tag{1}
\end{equation*}
where PP is a nonlinear operator defined on the normed linear space XX and with values in the normed linear space YY. We note with bar(x)\bar{x} solution of equation (1) and with D sube XD \subseteq X, an area that contains this solution. With x_(1),x_(2)in Dx_{1}, x_{2} \in D We will note two approximate solutions of equation (1). We assume that:
a) The Operator PP admits the difference divided by the first order by the nodes x_(1),x_(2)x_{1}, x_{2}.
b) Operator [x,y;P][x, y ; P] is reversible, i.e. there is the operator [x,y;P]^(-1)[x, y ; P]^{-1}.
c) There are two constants m_(1),M_(1)m_{1}, M_{1} so that
a) The Operator PP admits the difference divided by the first order by the nodes x_(1),x_(2)x_{1}, x_{2}.
b) Operator [x,y;P][x, y ; P] is reversible, i.e. there is the operator [x,y;P]^(-1)[x, y ; P]^{-1}.
c) There are two constants m_(1),M_(1)m_{1}, M_{1} so that
0 < m_(1) <= ||[x,y;P]^(-1)|| <= M_(1) < +oo," pentru orice "x,y in D.0<m_{1} \leqq\left\|[x, y ; P]^{-1}\right\| \leqq M_{1}<+\infty, \text { pentru orice } x, y \in D .
d) For the difference divided by the second order of the operator PP There are two constants m_(2),M_(2)m_{2}, M_{2} so that
0 < m_(2) <= ||[ bar(x),x,y;P]|| <= M_(2) < +oo," pentru orice "x,y in D0<m_{2} \leqq\|[\bar{x}, x, y ; P]\| \leqq M_{2}<+\infty, \text { pentru orice } x, y \in D
e) Differences divided by orders one and two are symmetrical (according to definition 3, [3]).
Taking into account theorem 1. from [3], we can write theta=P( bar(x))=P(x_(1))−̸+[x_(1),x_(2);P](( bar(x))-x_(1))+[( bar(x)),x_(1),x_(2);P](( bar(x))-x_(2))(( bar(x))-x_(1))\theta=P(\bar{x})=P\left(x_{1}\right) \not- +\left[x_{1}, x_{2} ; P\right]\left(\bar{x}-x_{1}\right)+\left[\bar{x}, x_{1}, x_{2} ; P\right]\left(\bar{x}-x_{2}\right)\left(\bar{x}-x_{1}\right). If we apply this identity to the controller [x_(1),x_(2);P]^(-1)\left[x_{1}, x_{2} ; P\right]^{-1} Get
{:[theta=[x_(1),x_(2);P]^(-1)P(x_(1))+(( bar(x))-x_(1))+],[+[x_(1),x_(2);P]^(-1)[( bar(x)),x_(1),x_(2);P]*(( bar(x))-x_(2))(( bar(x))-x_(1))]:}\begin{gathered}
\theta=\left[x_{1}, x_{2} ; P\right]^{-1} P\left(x_{1}\right)+\left(\bar{x}-x_{1}\right)+ \\
+\left[x_{1}, x_{2} ; P\right]^{-1}\left[\bar{x}, x_{1}, x_{2} ; P\right] \cdot\left(\bar{x}-x_{2}\right)\left(\bar{x}-x_{1}\right)
\end{gathered}
and if we write down
x_(3)=x_(1)-[x_(1),x_(2);P]^(-1)*P(x_(1))x_{3}=x_{1}-\left[x_{1}, x_{2} ; P\right]^{-1} \cdot P\left(x_{1}\right)
We
{:1^('))quad bar(x)-x_(3)=-[x_(1),x_(2),P]^(-1)[( bar(x)),x_(1),x_(2);P]*(( bar(x))-x_(2))*(( bar(x))-x_(1))\left.1^{\prime}\right) \quad \bar{x}-x_{3}=-\left[x_{1}, x_{2}, P\right]^{-1}\left[\bar{x}, x_{1}, x_{2} ; P\right] \cdot\left(\bar{x}-x_{2}\right) \cdot\left(\bar{x}-x_{1}\right)
from which, taking into account the previous assumptions, we deduce
{:1^('))quad bar(x)-x_(3)=-[x_(1),x_(2),P]^(-1)[( bar(x)),x_(1),x_(2);P]*(( bar(x))-x_(2))*(( bar(x))-x_(1))\left.1^{\prime}\right) \quad \bar{x}-x_{3}=-\left[x_{1}, x_{2}, P\right]^{-1}\left[\bar{x}, x_{1}, x_{2} ; P\right] \cdot\left(\bar{x}-x_{2}\right) \cdot\left(\bar{x}-x_{1}\right)
from which, taking into account the previous assumptions, we deduce
{:[(2)m_(1)*m_(2)*||( bar(x))-x_(2)||*||( bar(x))-x_(1)|| <= ||( bar(x))-x_(3)|| <= ],[ <= M_(1)*M_(2)||( bar(x))-x_(2)||*||( bar(x))-x_(1)||_(*)]:}\begin{gather*}
m_{1} \cdot m_{2} \cdot\left\|\bar{x}-x_{2}\right\| \cdot\left\|\bar{x}-x_{1}\right\| \leqq\left\|\bar{x}-x_{3}\right\| \leqq \tag{2}\\
\leqq M_{1} \cdot M_{2}\left\|\bar{x}-x_{2}\right\| \cdot\left\|\bar{x}-x_{1}\right\|_{\cdot}
\end{gather*}
From the last inequality it follows that if x_(1)x_{1} Shi x_(2)x_{2} There are two approximate solutions of equation (1), then and x_(3)x_{3} is an approximate solution of equation (1). From inequality (2) it can be seen that in general x_(3)x_{3} is a generally better approximate solution because the margins of the evaluation contain the product ||( bar(x))-x_(1)||*||( bar(x))-x_(2)||\left\|\bar{x}-x_{1}\right\| \cdot\left\|\bar{x}-x_{2}\right\|. If we had used the generalized inverse remainder for this evaluation, we would have obtained, as shown in paper [2], a less accurate evaluation.
2. A class of STEFEENSEN METHODS
It is proven [1] that in general the methods obtained by reverse interpolation have a rather slow convergence speed even if the number of interpolation nodes increases. We will show here that these methods are interesting but, from another point of view, namely, with their help a class of iterative methods with a single step can be generated, which in turn have a high speed of convergence.
We start from the inverse interpolation polynomial constructed in [2] and consider that the operator PP of equation (1) has the form
{:(3)P(x)=x-Q(x):}\begin{equation*}
P(x)=x-Q(x) \tag{3}
\end{equation*}
and the spaces X,YX, Y they are one and the same space.
Daughter x_(0)in Xx_{0} \in X an element that is not a solution to equation (3). For abbreviation we introduce the notations
Daughter x_(0)in Xx_{0} \in X an element that is not a solution to equation (3). For abbreviation we introduce the notations
{:(4)x_(0)^(0)=x_(0)","x_(1)^(0)=Q(x_(0)^(0))","x_(2)^(0)=Q(x_(1)^(0))","dots","x_(n-1)^(0)=Q(x_(n-2)^(0)):}\begin{equation*}
x_{0}^{0}=x_{0}, x_{1}^{0}=Q\left(x_{0}^{0}\right), x_{2}^{0}=Q\left(x_{1}^{0}\right), \ldots, x_{n-1}^{0}=Q\left(x_{n-2}^{0}\right) \tag{4}
\end{equation*}
We assume that the operator QQ admits symmetrical divided differences on the node system generated by (4).
Taking into account (3) and the notations made above, we have
{:[P(x_(i)^(0))=x_(i)^(0)-Q(x_(i)^(0))=Q(x_(i-1)^(0))-Q(x_(i)^(0))=],[=[x_(i)^(0),x_(i-1)^(0);Q]*P(x_(i-1)^(0))","" pentru "i=1","2","dots","n-2.]:}\begin{gathered}
P\left(x_{i}^{0}\right)=x_{i}^{0}-Q\left(x_{i}^{0}\right)=Q\left(x_{i-1}^{0}\right)-Q\left(x_{i}^{0}\right)= \\
=\left[x_{i}^{0}, x_{i-1}^{0} ; Q\right] \cdot P\left(x_{i-1}^{0}\right), \text { pentru } i=1,2, \ldots, n-2 .
\end{gathered}
That is, equality
P(x_(i)^(0))=[x_(i)^(0),x_(i-1)^(0);Q]*P(x_(i-1)^(0)),quad i=1,2,dots,n-1.P\left(x_{i}^{0}\right)=\left[x_{i}^{0}, x_{i-1}^{0} ; Q\right] \cdot P\left(x_{i-1}^{0}\right), \quad i=1,2, \ldots, n-1 .
Applying this equality successively we deduce
{:(5){:[P(x_(i)^(0))=[x_(i)^(0),x_(i-1)^(0);Q][x_(i-1)^(0),x_(i-2)^(0);Q]dots[x_(1)^(0),x_(0)^(0);Q]*P(x_(0))],[" pentru "i=1","2","dots","n-2.]:}:}\begin{array}{r}
P\left(x_{i}^{0}\right)=\left[x_{i}^{0}, x_{i-1}^{0} ; Q\right]\left[x_{i-1}^{0}, x_{i-2}^{0} ; Q\right] \ldots\left[x_{1}^{0}, x_{0}^{0} ; Q\right] \cdot P\left(x_{0}\right) \tag{5}\\
\text { pentru } i=1,2, \ldots, n-2 .
\end{array}
We assume that the following conditions are met:
a) Inverse divided differences [y_(0)^(0),y_(1)^(0);x],dots,[y_(0)^(0),dots,y_(n-1)^(0);x]\left[y_{0}^{0}, y_{1}^{0} ; x\right], \ldots,\left[y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right], [theta,y_(0)^(0),dots,y_(n-1)^(0);x]\left[\theta, y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right] exist and are symmetrical (according to the definition 3,[3]3,[3] ), where y_(i)^(0)=P(x_(i)^(0)),i=0,1,2,dots,n-1y_{i}^{0}=P\left(x_{i}^{0}\right), i=0,1,2, \ldots, n-1.
(b) Divided differences [x_(1)^(0),x_(0)^(0);Q],dots,[x_(n-1)^(0),x_(n-2)^(0);Q]\left[x_{1}^{0}, x_{0}^{0} ; Q\right], \ldots,\left[x_{n-1}^{0}, x_{n-2}^{0} ; Q\right] exist and are bordered by the same number BB in the norm.
c) There is a number MM for which inequality occurs
a) Inverse divided differences [y_(0)^(0),y_(1)^(0);x],dots,[y_(0)^(0),dots,y_(n-1)^(0);x]\left[y_{0}^{0}, y_{1}^{0} ; x\right], \ldots,\left[y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right], [theta,y_(0)^(0),dots,y_(n-1)^(0);x]\left[\theta, y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right] exist and are symmetrical (according to the definition 3,[3]3,[3] ), where y_(i)^(0)=P(x_(i)^(0)),i=0,1,2,dots,n-1y_{i}^{0}=P\left(x_{i}^{0}\right), i=0,1,2, \ldots, n-1.
(b) Divided differences [x_(1)^(0),x_(0)^(0);Q],dots,[x_(n-1)^(0),x_(n-2)^(0);Q]\left[x_{1}^{0}, x_{0}^{0} ; Q\right], \ldots,\left[x_{n-1}^{0}, x_{n-2}^{0} ; Q\right] exist and are bordered by the same number BB in the norm.
c) There is a number MM for which inequality occurs
||[theta,y_(0)^(0),dots,E_(n-1)^(0);x]|| <= M\left\|\left[\theta, y_{0}^{0}, \ldots, \mathscr{E}_{n-1}^{0} ; x\right]\right\| \leqq M
In hypothesis a) there is the generalized polynomial of inverse interpolation, [3]. Let's note with x_(1)x_{1} the result of replacing in this polynomial the elements (4) as vertices ; in this case we will have
(6) quadx_(1)=x_(0)^(0)-[y_(0)^(0),y_(1)^(0);x]y_(0)^(0)+dots+(-1)^(n-1)[y_(0)^(0),dots,y_(n-1)^(0);x]y_(n-2)^(0)dotsy_(0)^(0)\quad x_{1}=x_{0}^{0}-\left[y_{0}^{0}, y_{1}^{0} ; x\right] y_{0}^{0}+\ldots+(-1)^{n-1}\left[y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right] y_{n-2}^{0} \ldots y_{0}^{0}
(6) quadx_(1)=x_(0)^(0)-[y_(0)^(0),y_(1)^(0);x]y_(0)^(0)+dots+(-1)^(n-1)[y_(0)^(0),dots,y_(n-1)^(0);x]y_(n-2)^(0)dotsy_(0)^(0)\quad x_{1}=x_{0}^{0}-\left[y_{0}^{0}, y_{1}^{0} ; x\right] y_{0}^{0}+\ldots+(-1)^{n-1}\left[y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right] y_{n-2}^{0} \ldots y_{0}^{0}
If with x_(1)x_{1} thus obtained, we proceed in the same way as with x_(0)x_{0} we get an element x_(2)x_{2}. In general, assuming that condition a) is also fulfilled for the other successive elements, we deduce the following iterative procedure
{:[(7)x_(k+1)=x_(0)^(k)-[y_(0)^(k),y_(1)^(k);x]y_(0)^(k)+dots],[+(-1)^(n-1)[y_(0)^(k),dots,y_(n-1)^(k);x]y_(n-2)^(k)dotsy_(0)^(k)]:}\begin{gather*}
x_{k+1}=x_{0}^{k}-\left[y_{0}^{k}, y_{1}^{k} ; x\right] y_{0}^{k}+\ldots \tag{7}\\
+(-1)^{n-1}\left[y_{0}^{k}, \ldots, y_{n-1}^{k} ; x\right] y_{n-2}^{k} \ldots y_{0}^{k}
\end{gather*}
where
x_(0)^(k)=x_(k),x_(1)^(k)=Q(x_(0)^(k)),x_(2)^(k)=Q(x_(1)^(k)),dots,x_(n-1)^(k)=Q(x_(n-2)^(k)),quad k=0,1,2,dotsx_{0}^{k}=x_{k}, x_{1}^{k}=Q\left(x_{0}^{k}\right), x_{2}^{k}=Q\left(x_{1}^{k}\right), \ldots, x_{n-1}^{k}=Q\left(x_{n-2}^{k}\right), \quad k=0,1,2, \ldots
This procedure, in order to n=2n=2, is nothing more than Steffensen's well-known method. For these reasons, the procedure (7) will be called the generalized Steffensen procedure.
Next, we will assume that hypotheses a), b) and c) are true for all kk. Applying the formula (14), (3) and taking into account the above hypothesis, we deduce the following inequality:
{:(8)||( bar(x))-x_(k+1)|| <= M||y_(n-1)^(k)||*||y_(n-2)^(k)||dots||y_(0)^(k)||","quad k=0","1","dots:}\begin{equation*}
\left\|\bar{x}-x_{k+1}\right\| \leqq M\left\|y_{n-1}^{k}\right\| \cdot\left\|y_{n-2}^{k}\right\| \ldots\left\|y_{0}^{k}\right\|, \quad k=0,1, \ldots \tag{8}
\end{equation*}
where bar(x)\bar{x} is a solution of equation (3).
From hypothesis b) the following inequalities result
From hypothesis b) the following inequalities result
||y_(s)^(k)|| <= B^(s)||y_(0)^(k)||,quad s=1,2,dots,n-1;k=0,1dots\left\|y_{s}^{k}\right\| \leqq B^{s}\left\|y_{0}^{k}\right\|, \quad s=1,2, \ldots, n-1 ; k=0,1 \ldots
From this last inequality and (8) we
deduce (9)
deduce (9)
||( bar(x))-x_(k+1)|| <= M*B^((n(n-1))/(2))*||y_(0)^(k)||^(n),quad k=0,1,2,dots\left\|\bar{x}-x_{k+1}\right\| \leqq M \cdot B^{\frac{n(n-1)}{2}} \cdot\left\|y_{0}^{k}\right\|^{n}, \quad k=0,1,2, \ldots
But
y_(0)^(k)=P(x_(0)^(k))=P(x_(k))-P( bar(x))=[( bar(x)),x_(k);P](x_(k)-( bar(x)))y_{0}^{k}=P\left(x_{0}^{k}\right)=P\left(x_{k}\right)-P(\bar{x})=\left[\bar{x}, x_{k} ; P\right]\left(x_{k}-\bar{x}\right)
and if for anything kk Inequality occurs
||[x,x_(k);P]|| <= N < +oo\left\|\left[x, x_{k} ; P\right]\right\| \leqq N<+\infty
then
{:('")"||y_(0)^(k)|| <= N*||x_(k)-( bar(x))||","quadquad k=0","1","dots:}\begin{equation*}
\left\|y_{0}^{k}\right\| \leqq N \cdot\left\|x_{k}-\bar{x}\right\|, \quad \quad k=0,1, \ldots \tag{$\prime$}
\end{equation*}
From the last inequality and from (9) we have
{:(('')")"||x_(k+1)-( bar(x))||_(-)M*B^((n^(')n-1)/(2))*N^(n)*||x_(n)-( bar(x))||^(n)" pentru "k=0","1","dots:}\begin{equation*}
\left\|x_{k+1}-\bar{x}\right\|_{-} M \cdot B^{\frac{n^{\prime} n-1}{2}} \cdot N^{n} \cdot\left\|x_{n}-\bar{x}\right\|^{n} \text { pentru } k=0,1, \ldots \tag{$\prime\prime$}
\end{equation*}
Noting H=M*B^((n(n-1))/(2))*N^(n)H=M \cdot B^{\frac{n(n-1)}{2}} \cdot N^{n} We achieve inequality
||x_(it+1)-( bar(x))|| <= H*||x_(k)-( bar(x))||^(n),quad k=0,1,2,dots\left\|x_{i t+1}-\bar{x}\right\| \leqq H \cdot\left\|x_{k}-\bar{x}\right\|^{n}, \quad k=0,1,2, \ldots
which, if we multiply by Pi^((1)/(n-1))\Pi^{\frac{1}{n-1}} and we note
delta_(k)=H^((1)/(n-1))*||x_(k)-( bar(x))||,quad k=0,1,2,dots\delta_{k}=H^{\frac{1}{n-1}} \cdot\left\|x_{k}-\bar{x}\right\|, \quad k=0,1,2, \ldots
Get
delta_(k+1) <= delta_(k)^(n)\delta_{k+1} \leq \delta_{k}^{n}
Assuming that x_(0)x_{0} it can thus be chosen that together with HH to address inequality
delta_(0) < 1\delta_{0}<1
It follows that
delta_(k+1) <= delta_(0)^(n^(k))\delta_{k+1} \leqq \delta_{0}^{n^{k}}
and so
lim_(k rarr oo)delta_(k^(˙)+1)=0\lim _{k \rightarrow \infty} \delta_{\dot{k}+1}=0
From this we deduce the convergence of the process (7). As it turns out. from inequality (10), this process has a high speed of convergence. and this speed increases in relation to nn. For example, for n=3n=3 we obtain a method which results from the analogue of Chebyshev's method.
Observation. Taking into account inequality (9') and inequality (9) we can deduce
||P(x_(k+1))|| <= N*||x_(k+1)-( bar(x))|| <= M*B^((n(n-1))/(2))*N*||P(x_(k))||^(n)\left\|P\left(x_{k+1}\right)\right\| \leq N \cdot\left\|x_{k+1}-\bar{x}\right\| \leq M \cdot B^{\frac{n(n-1)}{2}} \cdot N \cdot\left\|P\left(x_{k}\right)\right\|^{n}
to which, if we add the condition
(M*B^((n(n-1))/(2))*N)^((1)/(n-1))*||P(x_(0))|| < 1\left(M \cdot B^{\frac{n(n-1)}{2}} \cdot N\right)^{\frac{1}{n-1}} \cdot\left\|P\left(x_{0}\right)\right\|<1
We are led to the conclusion that the iterative process constructed above has the order of convergence nn.
Received at the editorial office on June 23, 1970,
Academy of the Socialist Republic of Romania, Cluj Branch. Institute of Computing
Academy of the Socialist Republic of Romania, Cluj Branch. Institute of Computing
CONSTDÉRATIONS SUR LES MÉTHODES ITERATIVES OBTAINED BY INVERSE INTERPOLATION (ABSTRACT)
By using the generalized polynomial of inverse interpolation, we give a generalization of the iterative method of solving Steffensen's operational equations. In. The first part of the book gives an evaluation of the errors in the event that the operational equation P(x)=thetaP(x)=\theta is solved by the rope method. In the second part, a general Steffensen-type method is developed for which the order of convergence and error are studied.
BIBLIOGRAPHY
- Ostrowski, A. M., Resenie uravnenii i sistem uravnenii. Moskva, 1963.
- Popoviciu, Tiberiu, On the delimitation of error in the approximation of the y'acines of an equation by linear interpolation to the quadratic. Rev. Roum. de math. pures et appl., XIII. 1, (1968), 75-78
- Păvăloiu, I., Interpolation in normative linear spaces and applications. Mathematica, Cluj (sub tipar).