Considerations regarding the iterative methods obtained by inverse interpolation

Ion Păvăloiu
(original), html, paper

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

PDF

Scanned paper.

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

Considerations regarding the iterative methods obtained by inverse interpolation

OF

I. PĂVĂLOIU(Cluj)

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 ) = θ (1) P ( x ) = θ {:(1)P(x)=theta:}\begin{equation*} P(x)=\theta \tag{1} \end{equation*}(1)P(x)=I
where P P PPP is a nonlinear operator defined on the normed linear space X X XXX and with values in the normed linear space Y Y YYAnd. We note with x ¯ x ¯ bar(x)\bar{x}x¯ solution of equation (1) and with D ⊆ X D ⊆ X D sube XD \subseteq XD⊆X, an area that contains this solution. With x 1 , x 2 ∈ D x 1 , x 2 ∈ D x_(1),x_(2)in Dx_{1}, x_{2} \in Dx1,x2∈D We will note two approximate solutions of equation (1). We assume that:
a) The Operator P P PPP admits the difference divided by the first order by the nodes x 1 , x 2 x 1 , x 2 x_(1),x_(2)x_{1}, x_{2}x1,x2.
b) Operator [ x , y ; P ] [ x , y ; P ] [x,y;P][x, y ; P][x,and;P] is reversible, i.e. there is the operator [ x , y ; P ] − 1 [ x , y ; P ] − 1 [x,y;P]^(-1)[x, y ; P]^{-1}[x,and;P]−1.
c) There are two constants m 1 , M 1 m 1 , M 1 m_(1),M_(1)m_{1}, M_{1}m1,M1 so that
0 < m 1 ≦ ‖ [ x , y ; P ] − 1 ‖ ≦ M 1 < + ∞ , pentru orice x , y ∈ D . 0 < m 1 ≦ [ x , y ; P ] − 1 ≦ M 1 < + ∞ ,  pentru orice  x , y ∈ D . 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 .0<m1≦‖[x,and;P]−1‖≦M1<+∞, for anything x,and∈D.
d) For the difference divided by the second order of the operator P P PPP There are two constants m 2 , M 2 m 2 , M 2 m_(2),M_(2)m_{2}, M_{2}m2,M2 so that
0 < m 2 ≦ ‖ [ x ¯ , x , y ; P ] ‖ ≦ M 2 < + ∞ , pentru orice x , y ∈ D 0 < m 2 ≦ ‖ [ x ¯ , x , y ; P ] ‖ ≦ M 2 < + ∞ ,  pentru orice  x , y ∈ D 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 D0<m2≦‖[x¯,x,and;P]‖≦M2<+∞, for anything x,and∈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 θ = P ( x ¯ ) = P ( x 1 ) −̸ + [ x 1 , x 2 ; P ] ( x ¯ − x 1 ) + [ x ¯ , x 1 , x 2 ; P ] ( x ¯ − x 2 ) ( x ¯ − x 1 ) θ = P ( x ¯ ) = P x 1 −̸ + x 1 , x 2 ; P x ¯ − x 1 + x ¯ , x 1 , x 2 ; P x ¯ − x 2 x ¯ − x 1 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)I=P(x¯)=P(x1)−̸+[x1,x2;P](x¯−x1)+[x¯,x1,x2;P](x¯−x2)(x¯−x1). If we apply this identity to the controller [ x 1 , x 2 ; P ] − 1 x 1 , x 2 ; P − 1 [x_(1),x_(2);P]^(-1)\left[x_{1}, x_{2} ; P\right]^{-1}[x1,x2;P]−1 Get
θ = [ x 1 , x 2 ; P ] − 1 P ( x 1 ) + ( x ¯ − x 1 ) + + [ x 1 , x 2 ; P ] − 1 [ x ¯ , x 1 , x 2 ; P ] ⋅ ( x ¯ − x 2 ) ( x ¯ − x 1 ) θ = x 1 , x 2 ; P − 1 P x 1 + x ¯ − x 1 + + x 1 , x 2 ; P − 1 x ¯ , x 1 , x 2 ; P ⋅ x ¯ − x 2 x ¯ − x 1 {:[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}I=[x1,x2;P]−1P(x1)+(x¯−x1)++[x1,x2;P]−1[x¯,x1,x2;P]⋅(x¯−x2)(x¯−x1)
and if we write down
x 3 = x 1 − [ x 1 , x 2 ; P ] − 1 ⋅ P ( x 1 ) x 3 = x 1 − x 1 , x 2 ; P − 1 ⋅ P x 1 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)x3=x1−[x1,x2;P]−1⋅P(x1)
We
1 ′ ) x ¯ − x 3 = − [ x 1 , x 2 , P ] − 1 [ x ¯ , x 1 , x 2 ; P ] ⋅ ( x ¯ − x 2 ) ⋅ ( x ¯ − x 1 ) 1 ′ x ¯ − x 3 = − x 1 , x 2 , P − 1 x ¯ , x 1 , x 2 ; P ⋅ x ¯ − x 2 ⋅ x ¯ − x 1 {: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)1′)x¯−x3=−[x1,x2,P]−1[x¯,x1,x2;P]⋅(x¯−x2)⋅(x¯−x1)
from which, taking into account the previous assumptions, we deduce
(2) m 1 ⋅ m 2 ⋅ ‖ x ¯ − x 2 ‖ ⋅ ‖ x ¯ − x 1 ‖ ≦ ‖ x ¯ − x 3 ‖ ≦ ≦ M 1 ⋅ M 2 ‖ x ¯ − x 2 ‖ ⋅ ‖ x ¯ − x 1 ‖ ⋅ (2) m 1 ⋅ m 2 ⋅ x ¯ − x 2 ⋅ x ¯ − x 1 ≦ x ¯ − x 3 ≦ ≦ M 1 ⋅ M 2 x ¯ − x 2 ⋅ x ¯ − x 1 ⋅ {:[(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*}(2)m1⋅m2⋅‖x¯−x2‖⋅‖x¯−x1‖≦‖x¯−x3‖≦≦M1⋅M2‖x¯−x2‖⋅‖x¯−x1‖⋅
From the last inequality it follows that if x 1 x 1 x_(1)x_{1}x1 Shi x 2 x 2 x_(2)x_{2}x2 There are two approximate solutions of equation (1), then and x 3 x 3 x_(3)x_{3}x3 is an approximate solution of equation (1). From inequality (2) it can be seen that in general x 3 x 3 x_(3)x_{3}x3 is a generally better approximate solution because the margins of the evaluation contain the product ‖ x ¯ − x 1 ‖ ⋅ ‖ x ¯ − x 2 ‖ x ¯ − x 1 ⋅ x ¯ − x 2 ||( bar(x))-x_(1)||*||( bar(x))-x_(2)||\left\|\bar{x}-x_{1}\right\| \cdot\left\|\bar{x}-x_{2}\right\|‖x¯−x1‖⋅‖x¯−x2‖. 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 P P PPP of equation (1) has the form
(3) P ( x ) = x − Q ( x ) (3) P ( x ) = x − Q ( x ) {:(3)P(x)=x-Q(x):}\begin{equation*} P(x)=x-Q(x) \tag{3} \end{equation*}(3)P(x)=x−Q(x)
and the spaces X , Y X , Y X,YX, YX,And they are one and the same space.
Daughter x 0 ∈ X x 0 ∈ X x_(0)in Xx_{0} \in Xx0∈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 ) , … , x n − 1 0 = Q ( x n − 2 0 ) (4) x 0 0 = x 0 , x 1 0 = Q x 0 0 , x 2 0 = Q x 1 0 , … , x n − 1 0 = Q x n − 2 0 {:(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*}(4)x00=x0,x10=Q(x00),x20=Q(x10),…,xn−10=Q(xn−20)
We assume that the operator Q Q QQQ 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 , … , n − 2 . 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 , … , n − 2 . {:[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}P(xi0)=xi0−Q(xi0)=Q(xi−10)−Q(xi0)==[xi0,xi−10;Q]⋅P(xi−10), for i=1,2,…,n−2.
That is, equality
P ( x i 0 ) = [ x i 0 , x i − 1 0 ; Q ] ⋅ P ( x i − 1 0 ) , i = 1 , 2 , … , n − 1 . P x i 0 = x i 0 , x i − 1 0 ; Q ⋅ P x i − 1 0 , i = 1 , 2 , … , n − 1 . 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 .P(xi0)=[xi0,xi−10;Q]⋅P(xi−10),i=1,2,…,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 ] … [ x 1 0 , x 0 0 ; Q ] ⋅ P ( x 0 ) pentru i = 1 , 2 , … , n − 2 . (5) P x i 0 = x i 0 , x i − 1 0 ; Q x i − 1 0 , x i − 2 0 ; Q … x 1 0 , x 0 0 ; Q ⋅ P x 0  pentru  i = 1 , 2 , … , n − 2 . {:(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}(5)P(xi0)=[xi0,xi−10;Q][xi−10,xi−20;Q]…[x10,x00;Q]⋅P(x0) for i=1,2,…,n−2.
We assume that the following conditions are met:
a) Inverse divided differences [ y 0 0 , y 1 0 ; x ] , … , [ y 0 0 , … , y n − 1 0 ; x ] y 0 0 , y 1 0 ; x , … , y 0 0 , … , y n − 1 0 ; x [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][and00,and10;x],…,[and00,…,andn−10;x], [ θ , y 0 0 , … , y n − 1 0 ; x ] θ , y 0 0 , … , y n − 1 0 ; x [theta,y_(0)^(0),dots,y_(n-1)^(0);x]\left[\theta, y_{0}^{0}, \ldots, y_{n-1}^{0} ; x\right][I,and00,…,andn−10;x] exist and are symmetrical (according to the definition 3 , [ 3 ] 3 , [ 3 ] 3,[3]3,[3]3,[3] ), where y i 0 = P ( x i 0 ) , i = 0 , 1 , 2 , … , n − 1 y i 0 = P x i 0 , i = 0 , 1 , 2 , … , n − 1 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-1andi0=P(xi0),i=0,1,2,…,n−1.
(b) Divided differences [ x 1 0 , x 0 0 ; Q ] , … , [ x n − 1 0 , x n − 2 0 ; Q ] x 1 0 , x 0 0 ; Q , … , x n − 1 0 , x n − 2 0 ; Q [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][x10,x00;Q],…,[xn−10,xn−20;Q] exist and are bordered by the same number B B BBB in the norm.
c) There is a number M M MMM for which inequality occurs
‖ [ θ , y 0 0 , … , E n − 1 0 ; x ] ‖ ≦ M θ , y 0 0 , … , E n − 1 0 ; x ≦ M ||[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‖[I,and00,…,Andn−10;x]‖≦M
In hypothesis a) there is the generalized polynomial of inverse interpolation, [3]. Let's note with x 1 x 1 x_(1)x_{1}x1 the result of replacing in this polynomial the elements (4) as vertices ; in this case we will have
(6) x 1 = x 0 0 − [ y 0 0 , y 1 0 ; x ] y 0 0 + … + ( − 1 ) n − 1 [ y 0 0 , … , y n − 1 0 ; x ] y n − 2 0 … y 0 0 x 1 = x 0 0 − y 0 0 , y 1 0 ; x y 0 0 + … + ( − 1 ) n − 1 y 0 0 , … , y n − 1 0 ; x y n − 2 0 … y 0 0 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}x1=x00−[and00,and10;x]and00+…+(−1)n−1[and00,…,andn−10;x]andn−20…and00
If with x 1 x 1 x_(1)x_{1}x1 thus obtained, we proceed in the same way as with x 0 x 0 x_(0)x_{0}x0 we get an element x 2 x 2 x_(2)x_{2}x2. 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 + … + ( − 1 ) n − 1 [ y 0 k , … , y n − 1 k ; x ] y n − 2 k … y 0 k (7) x k + 1 = x 0 k − y 0 k , y 1 k ; x y 0 k + … + ( − 1 ) n − 1 y 0 k , … , y n − 1 k ; x y n − 2 k … y 0 k {:[(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*}(7)xk+1=x0k−[and0k,and1k;x]and0k+…+(−1)n−1[and0k,…,andn−1k;x]andn−2k…and0k
where
x 0 k = x k , x 1 k = Q ( x 0 k ) , x 2 k = Q ( x 1 k ) , … , x n − 1 k = Q ( x n − 2 k ) , k = 0 , 1 , 2 , … x 0 k = x k , x 1 k = Q x 0 k , x 2 k = Q x 1 k , … , x n − 1 k = Q x n − 2 k , k = 0 , 1 , 2 , … 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, \ldotsx0k=xk,x1k=Q(x0k),x2k=Q(x1k),…,xn−1k=Q(xn−2k),k=0,1,2,…
This procedure, in order to n = 2 n = 2 n=2n=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 k k kkk. Applying the formula (14), (3) and taking into account the above hypothesis, we deduce the following inequality:
(8) ‖ x ¯ − x k + 1 ‖ ≦ M ‖ y n − 1 k ‖ ⋅ ‖ y n − 2 k ‖ … ‖ y 0 k ‖ , k = 0 , 1 , … (8) x ¯ − x k + 1 ≦ M y n − 1 k ⋅ y n − 2 k … y 0 k , k = 0 , 1 , … {:(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*}(8)‖x¯−xk+1‖≦M‖andn−1k‖⋅‖andn−2k‖…‖and0k‖,k=0,1,…
where x ¯ x ¯ bar(x)\bar{x}x¯ is a solution of equation (3).
From hypothesis b) the following inequalities result
‖ y s k ‖ ≦ B s ‖ y 0 k ‖ , s = 1 , 2 , … , n − 1 ; k = 0 , 1 … y s k ≦ B s y 0 k , s = 1 , 2 , … , n − 1 ; k = 0 , 1 … ||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‖andsk‖≦Bs‖and0k‖,s=1,2,…,n−1;k=0,1…
From this last inequality and (8) we
deduce (9)
‖ x ¯ − x k + 1 ‖ ≦ M ⋅ B n ( n − 1 ) 2 ⋅ ‖ y 0 k ‖ n , k = 0 , 1 , 2 , … x ¯ − x k + 1 ≦ M ⋅ B n ( n − 1 ) 2 ⋅ y 0 k n , k = 0 , 1 , 2 , … ||( 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‖x¯−xk+1‖≦M⋅Bn(n−1)2⋅‖and0k‖n,k=0,1,2,…
But
y 0 k = P ( x 0 k ) = P ( x k ) − P ( x ¯ ) = [ x ¯ , x k ; P ] ( x k − x ¯ ) y 0 k = P x 0 k = P x k − P ( x ¯ ) = x ¯ , x k ; P x k − x ¯ 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)and0k=P(x0k)=P(xk)−P(x¯)=[x¯,xk;P](xk−x¯)
and if for anything k k kkk Inequality occurs
‖ [ x , x k ; P ] ‖ ≦ N < + ∞ x , x k ; P ≦ N < + ∞ ||[x,x_(k);P]|| <= N < +oo\left\|\left[x, x_{k} ; P\right]\right\| \leqq N<+\infty‖[x,xk;P]‖≦N<+∞
then
( ′ ) ‖ y 0 k ‖ ≦ N ⋅ ‖ x k − x ¯ ‖ , k = 0 , 1 , … ( ′ ) y 0 k ≦ N ⋅ x k − x ¯ , k = 0 , 1 , … {:('")"||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*}(′)‖and0k‖≦N⋅‖xk−x¯‖,k=0,1,…
From the last inequality and from (9) we have
( ′ ′ ) ‖ x k + 1 − x ¯ ‖ − M ⋅ B n ′ n − 1 2 ⋅ N n ⋅ ‖ x n − x ¯ ‖ n pentru k = 0 , 1 , … ( ′ ′ ) x k + 1 − x ¯ − M ⋅ B n ′ n − 1 2 ⋅ N n ⋅ x n − x ¯ n  pentru  k = 0 , 1 , … {:(('')")"||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*}(′′)‖xk+1−x¯‖−M⋅Bn′n−12⋅Nn⋅‖xn−x¯‖n for k=0,1,…
Noting H = M ⋅ B n ( n − 1 ) 2 ⋅ N n H = M ⋅ B n ( n − 1 ) 2 ⋅ N n H=M*B^((n(n-1))/(2))*N^(n)H=M \cdot B^{\frac{n(n-1)}{2}} \cdot N^{n}H=M⋅Bn(n−1)2⋅Nn We achieve inequality
‖ x i t + 1 − x ¯ ‖ ≦ H ⋅ ‖ x k − x ¯ ‖ n , k = 0 , 1 , 2 , … x i t + 1 − x ¯ ≦ H ⋅ x k − x ¯ n , k = 0 , 1 , 2 , … ||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‖xit+1−x¯‖≦H⋅‖xk−x¯‖n,k=0,1,2,…
which, if we multiply by Π 1 n − 1 Π 1 n − 1 Pi^((1)/(n-1))\Pi^{\frac{1}{n-1}}P1n−1 and we note
δ k = H 1 n − 1 ⋅ ‖ x k − x ¯ ‖ , k = 0 , 1 , 2 , … δ k = H 1 n − 1 ⋅ x k − x ¯ , k = 0 , 1 , 2 , … 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, \ldotsDk=H1n−1⋅‖xk−x¯‖,k=0,1,2,…
Get
δ k + 1 ≤ δ k n δ k + 1 ≤ δ k n delta_(k+1) <= delta_(k)^(n)\delta_{k+1} \leq \delta_{k}^{n}Dk+1≤Dkn
Assuming that x 0 x 0 x_(0)x_{0}x0 it can thus be chosen that together with H H HHH to address inequality
δ 0 < 1 δ 0 < 1 delta_(0) < 1\delta_{0}<1D0<1
It follows that
δ k + 1 ≦ δ 0 n k δ k + 1 ≦ δ 0 n k delta_(k+1) <= delta_(0)^(n^(k))\delta_{k+1} \leqq \delta_{0}^{n^{k}}Dk+1≦D0nk
and so
lim k → ∞ δ k ˙ + 1 = 0 lim k → ∞   δ k ˙ + 1 = 0 lim_(k rarr oo)delta_(k^(˙)+1)=0\lim _{k \rightarrow \infty} \delta_{\dot{k}+1}=0limk→∞Dk˙+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 n n nnn. For example, for n = 3 n = 3 n=3n=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 − x ¯ ‖ ≤ M ⋅ B n ( n − 1 ) 2 ⋅ N ⋅ ‖ P ( x k ) ‖ n P x k + 1 ≤ N ⋅ x k + 1 − x ¯ ≤ M ⋅ B n ( n − 1 ) 2 ⋅ N ⋅ P x k n ||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}‖P(xk+1)‖≤N⋅‖xk+1−x¯‖≤M⋅Bn(n−1)2⋅N⋅‖P(xk)‖n
to which, if we add the condition
( M ⋅ B n ( n − 1 ) 2 ⋅ N ) 1 n − 1 ⋅ ‖ P ( x 0 ) ‖ < 1 M ⋅ B n ( n − 1 ) 2 ⋅ N 1 n − 1 ⋅ P x 0 < 1 (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(M⋅Bn(n−1)2⋅N)1n−1⋅‖P(x0)‖<1
We are led to the conclusion that the iterative process constructed above has the order of convergence n n nnn.
Received at the editorial office on June 23, 1970,
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 ) = θ P ( x ) = θ P(x)=thetaP(x)=\thetaP(x)=I 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

  1. Ostrowski, A. M., Resenie uravnenii i sistem uravnenii. Moskva, 1963.
  2. 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
  3. Păvăloiu, I., Interpolation in normative linear spaces and applications. Mathematica, Cluj (sub tipar).
1971

Related Posts