Solving equations by interpolation

by
Ion Păvăloiu

1. Divided difference notation.

Let $X$ And $Y$ two normed linear spaces and $G:X\rightarrow Y$ an application. We consider $n+1$ distinct elements of space $X$

(1)

x_{1},x_{2},\ldots,x_{n+1}.

We designate by $L\left(X,Y\right)$ the set of linear and continuous applications defined on $X$ and values in $Y$ and we define by recurrence the following sets:

L_{i}\left(X,Y\right)=L\left(X,L_{i-1}\left(X,Y\right)\right),\ \;\;i=2,3,\ldots

L_{1}\left(X,Y\right)=L\left(X,Y\right).

In other words, the sets $L_{i}\left(X,Y\right)$ are the spaces of applications $i$ -linear and continuous defined on $X$ and values in $Y .$

Definition 1 .

The application $\left[.,.;G\right]:X^{2}\rightarrow L\left(X,Y\right)$ is called the first-order divided difference of the approximation $G$ on the points $x_{i},x_{j}$ of the system ( 1 ) if

1)

$\left[x_{i},x_{j};G\right]\left(x_{j}-x_{i}\right)=G\left(x_{j}\right)-G\left(% x_{i}\right)$
2)

if there exists the derivative in the Fréchet sense of the application $G$ on the point $x_{i},$ SO $\left[x_{i},x_{i};G\right]=G^{\prime}\left(x_{i}\right).$

We have defined above the divided difference of order one of the application $G$ on two arbitrary elements of the system ( 1 ).

Now considering consecutive points of the system ( 1 ) we can consider the following divided differences:

\left[x_{1},x_{2};G\right],\left[x_{2},x_{3};G\right],\ldots,\left[x_{n},x_{n+% 1};G\right].

Using the divided differences defined above we define the notion of divided difference of order $n$ $\left(n>1\right)$ of the application $G .$

We assume that we have defined the application $\left[\cdot,\cdot,\ldots,\cdot;G\right]:X^{i+1}\rightarrow L_{i}\left(X,Y\right)$ with the help of which we can define the divided differences of order $\ i$ of the application $G$ on $i+1$ any elements of the system ( 1 ).

Let $\left[x_{k+1},x_{k+2},\ldots,x_{k+i+1};G\right]$ And $\left[x_{k},x_{k+1},\ldots,x_{k+i};G\right]$ two divided differences of order $i$ on the points $x_{k+1},x_{k+2},\ldots,x_{k+i+1}$ respectively $x_{k},x_{k+1},\ldots,x_{k+1}$ of the system ( 1 ).

Definition 2 .

The application $\left[\cdot,\cdot,\ldots,\cdot;G\right]:X^{i+2}\rightarrow L_{i+1}\left(X,Y\right)$ is called divided difference of order $i+1$ of the application $G$ on the points $x_{k},x_{k+1},\ldots,x_{k+i+1},$ if

1)

$\displaystyle\left[x_{k},\ldots,x_{k+i+1};G\right]\left(x_{k+i+1}-x_{k}\right)=$

$\displaystyle=\left[x_{k+1},\ldots,x_{k+i+1};G\right]-\left[x_{k},\ldots,x_{k+% i};G\right]$
2)

if there exists the derivative in the sense of Fréchet of order $i+1$ of the application $G$ on the point $x_{i},$ SO:

$\left[x_{s},x_{s},\ldots,x_{s};G\right]=\tfrac{1}{\left(i+1\right)!}G^{\left(i% +1\right)}\left(x_{s}\right).$

In order to be able to use these divided differences in the construction of interpolation polynomials, it is necessary to introduce the notion of divided difference symmetrical with respect to the points considered.

Definition 3 .

The Divided Difference $\left[x_{1},x_{2},\ldots,x_{k};G\right]$ Or $x_{1},x_{2},\ldots,x_{k}$ are points of the system ( 1 ) is said to be symmetrical with respect to the points, if we have:

(2)

\left[x_{1},x_{2},\ldots,x_{k};G\right]=\left[x_{i_{1}},x_{i_{2}},\ldots,x_{i_% {k}};G\right]

for each permutation $\left(i_{1},i_{2},\ldots,i_{k}\right)$ numbers $\left(1,2,3,\ldots,k\right).$

If $X=Y=\mathbb{R}$ then, equality ( 2 ) is always verified. Then the divided differences of the real functions of a real variable are symmetric with respect to the points considered.

If we now assume for example $X=\mathbb{R}^{2}$ And $Y=\mathbb{R},$ $f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ and if we designate by $\left(u^{\prime},v^{\prime}\right),$ $\left(u^{\prime\prime},v^{\prime\prime}\right)$ two points of $\mathbb{R}^{2},$ We have

(3)

\left[x^{\prime},x^{\prime\prime};f\right]=\left[\tfrac{f\left(u^{\prime},v^{% \prime}\right)-f\left(u^{\prime\prime},v^{\prime}\right)}{u^{\prime}-u^{\prime% \prime}},\tfrac{f\left(u^{\prime\prime},v^{\prime}\right)-f\left(u^{\prime% \prime},v^{\prime\prime}\right)}{v^{\prime}-v^{\prime\prime}}\right]

x^{\prime}=\left(u^{\prime},v^{\prime}\right)\ \text{et }x^{\prime\prime}=% \left(u^{\prime\prime},v^{\prime\prime}\right).

We show that the divided difference ( 3 ) satisfies conditions ( 1 ) and ( 2 ) of definition 1 , but that it is not symmetric with respect to the points $x^{\prime}$ And $x^{\prime\prime}.$

But we can construct a divided difference on these points which is symmetric. For example if we consider the divided difference defined by:

	$\displaystyle\left[x^{\prime},x^{\prime\prime};f\right]=$	$\displaystyle\tfrac{1}{2}\left[\tfrac{f\left(u^{\prime},v^{\prime}\right)-f]% \left(u^{\prime\prime},v^{\prime}\right)}{u^{\prime}-u^{\prime\prime}}+\tfrac{% f\left(u^{\prime\prime},v^{\prime}\right)-f\left(u^{\prime\prime},v^{\prime% \prime}\right)}{v^{\prime\prime}-v^{\prime}}\right.,$
		$\displaystyle\quad\left.\tfrac{f\left(u^{\prime\prime},v^{\prime}\right)-f% \left(u^{\prime\prime},v^{\prime\prime}\right)}{v^{\prime}-v^{\prime\prime}}+% \tfrac{f\left(u^{\prime},v^{\prime\prime}\right)-f\left(u^{\prime},v^{\prime}% \right)}{v^{\prime\prime}-v^{\prime}}\right]$

so we obviously have

\left[x^{\prime},x^{\prime\prime};f\right]=\left[x^{\prime\prime},x^{\prime};f\right]

Be it now $X=Y=C\left[0,1\right]$ where by $C\left[0,1\right]$ we designate the set of functions defined and contained on the interval $\left[0,1\right].$ Now let us consider the application $F:C\left[0,1\right]\times C\left[0,1\right]$ given by the following equality:

F\left(x\right)\left(s\right)=\int_{0}^{1}K\left(s,t,x\left(t\right)\right)dt

Or $K:\left[0,1\right]\times\left[0,1\right]\times\mathbb{R}\rightarrow\mathbb{R}$ is a continuous function over its entire domain of definition.

Be it now $n+1$ -functions

(4)

x_{1},x_{2},\ldots,x_{n+1}

from space $C\left[0,1\right]$ which have the property that $x_{j}\left(t\right)\neq x_{i}\left(t\right)$ For $i\neq j$ and for each $t\in\left[0,1\right].$

The application's split difference $F$ on functions $x_{i},x_{j}$ of the system ( 4 ) can be defined using the following equality:

\left[x_{1},x_{2};F\right]h\left(s\right)=\int_{0}^{1}\tfrac{K\left(s,t,x_{2}% \left(t\right)\right)-K\left(s,t,x_{1}\left(t\right)\right)}{x_{2}\left(t% \right)-x_{1}\left(t\right)}h\left(t\right)dt

h\in C\left[0,1\right].

It is immediately shown that the linear application defined above has the properties ( 1 ) and ( 2 ) of definition 1 .

If we designate by $\left[x_{i},x_{i+1},\ldots,x_{i+s};K\right]$ the divided difference of order $s$ of the function $K$ , then the divided difference of order $s$ of the application $F$ is defined by the following equality:

	$\displaystyle\left[x_{i},x_{i+1},\ldots,x_{i+s};F\right]h_{1}h_{2}\ldots h_{3}=$
	$\displaystyle={\int_{0}^{1}}\left[x_{i},x_{i+1},\ldots,x_{i+s};K\right]h_{1}% \left(t\right)h_{2}\left(t\right)\ldots h_{s}\left(t\right)dt$

h_{1},h_{2},\ldots,h_{s}\in C{\left[0,1\right]}.

2. Interpolation

In all that follows we will assume that the divided differences are symmetrical with respect to the points considered.

We now designate, by $\ L_{n}:X\rightarrow Y$ an application defined by the equality:

(5)		$\displaystyle L_{n}\left(x\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{n+1};G\right]\left(x-x_{n}\right)% \ldots\left(x-x_{1}\right)$

So we have the following theorem:

Theorem 1 .

The application $L_{n}$ defined by ( 5 ) has the following properties

1)

$L_{n}\left(x_{i}\right)=G\left(x_{i}\right),\ \;\;i=1,2,\ldots,n+1$
2)

$G\left(x\right)-L_{n}\left(x\right)=\left[x,x_{1},\ldots,x_{n+1};G\right]\left% (x-x_{n+1}\right)\ldots\left(x-x_{1}\right)$ For $x\in X,$ $x\neq x_{i},$ $i=1,2,\ldots,n+1.$

Demonstration..

We prove equality 2) by induction. For $n=0$ equality 2) is obvious because $G\left(x\right)-G\left(x_{1}\right)=\left[x,x_{1};G\right]\left(x-x_{1}\right)$ which is none other than equality 1) of definition 1. We assume that equality 2) is true by $n=k$ and we will show that it is also true for $n=k+1.$

Indeed, if the following equality takes place

(6)	$\displaystyle G\left(x\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x-x_{1}% \right)+\ldots$
	$\displaystyle+\left[x_{1},x_{2},\ldots,x_{k+1};G\right]\left(x-x_{k}\right)% \ldots\left(x-x_{1}\right)$
	$\displaystyle+\left[x,x_{1},\ldots,x_{k+1};G\right]\left(x-x_{k+1}\right)% \ldots\left(x-x_{1}\right),$

then, taking into account equality

\left[x,x_{1},\ldots,x_{k+1};G\right]=\left[x,x_{1},\ldots,x_{k+2};G\right]% \left(x-x_{k+2}\right)+\left[x_{1},x_{2},..,x_{k+2};G\right]

which results from the definition of the divided difference of order $k+2.$ The following equality results:

	$\displaystyle G\left(x\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{k+2};G\right]\left(x-x_{k+1}\right)% \ldots\left(x-x_{1}\right)$
		$\displaystyle+\left[x,x_{1},\ldots,x_{k+2};G\right]\left(x-x_{k+2}\right)% \ldots\left(x-x_{1}\right)$

which shows that equality 2) holds for $n=k+1.$

It remains to demonstrate the equalities 1). From the definition of the application $L_{n}$ it results:

(7)		$\displaystyle L_{n}\left(x_{i}\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x_{i}-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{i};G\right]\left(x_{i}-x_{i-1}\right% )\ldots\left(x_{i}-x_{1}\right).$

If we now consider the last term on the right of equality ( 7 ) and take into account the equality:

	$\displaystyle\left[x_{1},x_{2},\ldots,x_{i};G\right]\left(x_{i}-x_{i-1}\right)=$
	$\displaystyle=\left[x_{i-1},x_{1},\ldots,x_{i-2},x_{i};G\right]\left(x_{i}-x_{% i-1}\right)$
	$\displaystyle=\left[x_{1},x_{2},\ldots,x_{i-2},x_{i};G\right]-\left[x_{i-1},x_% {1},\ldots,x_{i-2};G\right]$
	$\displaystyle=\left[x_{1},x_{2},\ldots,x_{i-1},x_{i};G\right]-\left[x_{1},x_{2% },\ldots,x_{i-2},x_{i-1};G)\right]$

we get

	$\displaystyle L_{n}\left(x_{i}\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x_{i}-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{i-2},x_{i};G\right]\left(x_{i}-x_{i-% 2}\right)\ldots\left(x_{i}-x_{1}\right).$

Proceeding in the same way after a finite number of steps we arrive at the following equality:

L_{n}\left(x_{i}\right)=G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x_% {i}-x_{1}\right)=G\left(x_{1}\right)+G\left(x_{i}\right)-G\left(x_{1}\right)=G% \left(x_{i}\right).

The application $L_{n}$ is called the Lagrange interpolation polynomial of the application $G$ on the knots $x_{i},i=1,2,\ldots,n+1$ of the system ( 1 ) ∎

3. Solving equations by interpolation

We consider the equation

(8)

G\left(x\right)=\theta

$\theta$ is the zero element of the space $Y$ And $G:X\rightarrow Y$ is a nonlinear operator.

To solve equation ( 8 ) we can proceed as follows.

Assuming that the points of the system ( 1 ) are in a neighborhood of the solution $\bar{x}$ from equation ( 8 ), from equality 2) (theorem 1 ) the following equality results:

G\left(\bar{x}\right)=L_{n}\left(\bar{x}\right)+\left[\bar{x},x_{1},\ldots,x_{% n+1};G\right]\left(\bar{x}-x_{n+1}\right)\ldots\left(\bar{x}-x_{1}\right)=\theta

from which it results

\left\|L_{n}\left(\bar{x}\right)\right\|\leq\left\|\left[\bar{x},x_{1},\ldots,% x_{n+1};G\right]\right\|\left\|x-x_{1}\right\|\ldots\left\|x-x_{n+1}\right\|.

If we now assume that we have the inequalities $\left\|\bar{x}-x_{i}\right\|\leq\varepsilon,$ $i=\overline{1,n+1}$ Or $\varepsilon$ is a real and positive number, then we have:

\left\|L_{n}\left(\bar{x}\right)\right\|\leq\left\|\left[\bar{x},x_{1},\ldots,% x_{n+1};G\right]\right\|\varepsilon^{n+1}

from which it follows that to find an approximation of the solution $\bar{x}$ you just have to solve the following equation:

(9)

L_{n}\left(x\right)=\theta.

The method outlined above has some drawbacks, including:

First, solving an equation in the form ( 9 ) even in the case $n=1$ is a difficult mathematical problem and the difficulty of the problem increases considerably if $n>1.$ Even in the case $X=Y={\mathbb{R}},$ that is to say, when $L_{n}$ is an algebraic polynomial with real coefficients, the problem can be very difficult because of the fact that an algebraic equation of degree $n$ has $n$ roots, and then it is necessary to choose the root of equation ( 9 ) which approaches the root $\bar{x}$ of equation ( 8 ).

Second, it is well known that the position of the roots of an algebraic equation in the plane and the nature of these roots can change considerably when the coefficients of the equation are affected by non-essential errors.

In the following we will present another method by which some of the difficulties mentioned above can be eliminated.

We assume that linear operators

\left[x_{i},x_{j};G\right]\in L\left(X,Y\right),\ \;\;i\neq j;j=1,2,\ldots,n+1

are reversible.

It follows that $G\left(x_{i}\right)\neq G\left(x_{i}\right),$ $i\neq j.$ Be it now $D$ any set of elements of space $X .$ We designate by $\bar{G}=G|_{D}$ the restriction of the application $G$ to the whole $D .$

We assume that the application $\bar{G}$ is a homeomorphism of sets $D$ And $G\left(D\right).$ Where by $G\left(D\right)$ we have designated the image of the whole $D$ by $G .$

We have the following theorem:

Theorem 2 .

If the linear operator $\left[x_{i},x_{j};G\right],$ Or $x_{i},x_{j}\in D$ is invertible, then the equality holds:

\big{[}y_{i},y_{j},\bar{G}^{-1}\big{]}=\left[x_{i},x_{j};G\right]^{-1}

y_{i}=G\left(x_{i}\right)\ \ \text{et\ \ }y_{j}=G\left(x_{j}\right).

Demonstration..

From the definition of divided difference of order 1 it follows that

G\left(x_{j}\right)=G\left(x_{i}\right)=\left[x_{i},x_{j};G\right]\left(x_{j}-% x_{j}\right)

\left[x_{i},x_{j};G\right]^{-1}\left(y_{j}-y_{i}\right)=x_{j}-x_{i}

That's to say

\bar{G}^{-1}\left(y_{j}\right)-\bar{G}^{-1}\left(y_{i}\right)=\left[x_{i},x_{j% };G\right]^{-1}\left(y_{j}-y_{i}\right)

from which results the equality of the statement of the theorem.

Let us now $x_{1},$ $x_{2},\ldots,x_{n+1},$ $n+1$ - elements of the set $D .$

We designate by $y_{1},y_{2},\ldots,y_{n+1}$ application values $G$ on these points, that is to say $y_{i}=G\left(x_{i}\right),$ $i=1,2,\ldots,n+1.$ We consider the application $L_{n}:Y\rightarrow X$ given by

(10)		$\displaystyle L_{n}\left(y\right)=$	$\displaystyle x_{1}+\big{[}y_{1},y_{2};\bar{G}^{-1}\big{]}\left(y-y_{1}\right)+\ldots$
		$\displaystyle+\big{[}y_{1},\ldots,y_{n+1};\bar{G}^{-1}\big{]}\left(y-y_{n}% \right)\left(y-y_{n+1}\right)\ldots\left(y-y_{1}\right)$

which verifies equalities

(11)

\bar{G}^{-1}\left(y\right)=L_{n}\left(y\right)+\big{[}y,y_{1},\ldots,y_{n+1};% \bar{G}^{-1}\big{]}\left(y-y_{n+1}\right)\ldots\left(y-y_{1}\right)

And

(12)

\bar{G}^{-1}\left(y_{i}\right)=L_{n}\left(y_{i}\right)=x_{i},\qquad i=1,2,% \ldots,n+1.

If we now assume that the solution $\bar{x}$ of equation ( 8 ) belongs to the set $D,$ so obviously $\bar{x}=\bar{G}^{-1}\left(\theta\right)$ and from ( 11 ) we deduce:

(13)

\bar{x}=\bar{G}^{-1}\left(\theta\right)=L_{n}\left(\theta\right)+\left(-1% \right)^{n+1}\big{[}\theta,y_{1},\ldots,y_{n+1};\bar{G}^{-1}\big{]}y_{n+1}% \ldots y_{1}.

If we designate by

(14)

\bar{x}=L_{n}\left(\theta\right)

we deduce:

(15)

\left\|\bar{x}-\bar{x}\right\|\leq\big{\|}\big{[}\theta,y_{1},\ldots,y_{n+1};% \bar{G}^{-1}\big{]}\big{\|}\cdot\left\|y_{n+1}\right\|\ldots\left\|y_{1}\right\|.

From equality ( 15 ) it follows that if the elements $x_{1},x_{2},\ldots,x_{n+1}$ are chosen in such a way that $\left\|y_{1}\right\|=\left\|G\left(x_{i}\right)\right\|<\varepsilon,\ i=1,2,% \ldots,n+1$ Or $\varepsilon$ is a sufficiently small real number, then $\bar{x}$ is a good approximation for $\bar{x}.$

For clarity we refer to $L_{n}\big{(}y_{1},y_{2},\ldots,y_{n+1};\bar{G}^{-1}|y\big{)}$ the operator $L_{n}\left(y\right)$ given by the relation ( 10 ). Now let $x_{1},$ $x_{2},\ldots,x_{n+1},n+1$ -given initial elements and either $\left(x_{n}\right)_{n=1}^{\infty}$ the sequence generated by the recurrence relation:

(16)

x_{i+n+1}=L_{n}\big{(}y_{i,}y_{i+1},\ldots,y_{i+n};\bar{G}^{-1}|\theta\big{)},% \qquad i=1,2,\ldots\eqqed

We will now present some special cases of the iterative process ( 16 ).

A. Let $x_{1}$ And $x_{2}$ two arbitrary elements of space $X .$ If we consider the first two terms of the inverse interpolation polynomial ( 10 ) taking into account Theorem 2 , we have

(17)

x_{k+1}=x_{k-1}-\left[x_{k-1},x_{k};G\right]^{-1}G\left(x_{k-1}\right),\qquad k% =2,3,\ldots

which is nothing other than the extension of the rope method.

B. In case we consider three initial elements $x_{1},x_{2},x_{3}\in X$ and we limit ourselves to the first three terms of the relation ( 10 ) we have:

(18)	$\displaystyle x_{k}=$	$\displaystyle x_{k-3}-\left[x_{k-3},x_{k-2};G\right]^{-1}G\left(x_{k-3}\right)$
	$\displaystyle-\left[x_{k-3},x_{k-2};G\right]^{-1}\left[x_{k-3},x_{k-1},x_{k-1}% ;G\right]\left[x_{k-3},x_{k-1};G\right]^{-1}\cdot$
	$\displaystyle\quad\cdot G\left(x_{k-3}\right)\cdot\left[x_{k-1},x_{k-2};G% \right]^{-1}G\left(x_{k-2}\right),\qquad k=4,5,\ldots$

This method is an extension to linear space $X$ of a method analogous to the well-known Tchebycheff method. From ( 15 ) and ( 16 ) we deduce

(19)

\displaystyle\left\|\bar{x}-x_{i+n+1}\right\|

\displaystyle\leq\big{\|}\big{[}\theta,y_{i},\ldots,y_{n+1};\bar{G}^{-1}\big{]% }\big{\|}\cdot\left\|y_{i}\right\|\ldots\left\|y_{n+1}\right\|,

$i=1,2,\ldots$

Regarding the method ( 16 ) the following two questions arise:

1. What are the conditions for the convergence of the method ( 16 ).

2. In the case of convergence of method ( 16 ), what is the speed of convergence?

Concerning the convergence speed of an iterative method of type ( 16 ), AM Ostrowski [ 1 ] showed that the order of convergence of this method does not exceed 2, for each given number of interpolation points.

In the following we will show that if at each iteration step we choose the interpolation points appropriately, then the order of convergence increases considerably.

As is well known for the resolution of an equation of the form ( 8 ) by an iterative method it is necessary to highlight an application $Q:X\rightarrow X$ which has the property that each solution of equation ( 8 ) is a fixed point for the application $Q .$

An operator $Q$ which has the above property is said to be an iterative operator attached to equation ( 8 ).

For the operators attached to equation ( 8 ) we can define the notion of order.

Definition 4 .

Either $D\subseteq X$ a set of space elements $X$ And $\rho>0$ a real number.

We say that the iterative operator $Q$ to order $k$ $\left(k>0\ \text{nombre r\'{e}el}\right)$ on the whole $D,$ with respect to equation ( 8 ) if for each $x\in D$ we have

(20)

\left\|G\left(Q\left(x\right)\right)\right\|\leq\rho\left\|G\left(x\right)% \right\|^{k}.

Let us now $Q_{1},Q_{2},..,Q_{n};n$ -iterative operators attached to equation ( 8 ) , respectively of order $k_{1},k_{2},\ldots,k_{n}.$

We consider an arbitrary element $x_{0}\in X$ and designate by $x_{s}^{0};s=\overline{1,n}$ the following expressions:

(21)

x_{1}^{0}=Q_{1}\left(x_{0}\right),\;\;x_{s}^{0}=Q_{s}\left(x_{s-1}^{0}\right),% \;\;s=2,3,\ldots,n

If the initial elements in the iterative method ( 16 ) are:

(22)

x_{0},x_{1}^{0},\ldots,x_{n}^{0}

so if we write $y_{0}^{0}=G\left(x_{0}\right),y_{i}^{0}=G\left(x_{i}^{0}\right),i=1,2,\ldots,n,$ we have:

(23)

x_{1}=L_{n}\big{(}y_{0}^{0},y_{1}^{0},\ldots,y_{n}^{0};\bar{G}^{-1}|\theta\big% {)}.

We now assume that we have built the first $i+1$ elements of the suite $\left(x_{n}\right)_{n=0}^{\infty}$ then the element $x_{n+1}$ is obtained in the following way:

We write:

(24)

x_{1}^{i}=Q_{1}\left(x_{i}\right),\ \;\;x_{j}^{i}=Q_{j}\left(x_{j-1}^{i}\right% ),\ \;\;j=2,3,\ldots,n

And

y_{0}^{i}=G\left(x_{i}\right),\ \;\;y_{j}^{i}=G\left(x_{j}^{i}\right),\ \;\;j=% 1,2,\ldots,n

So the element $x_{i+1}$ has the following form:

(25)

x_{i+1}=L_{n}\big{(}y_{0}^{i},y_{1}^{i},\ldots,y_{n}^{i};\bar{G}^{-1}|\theta% \big{)}

From ( 15 ) and ( 25 ) we have:

(26)

\left\|\bar{x}-x_{i+1}\right\|\leq\big{\|}\big{[}\theta,y_{0}^{i},\ldots,y_{n}% ^{i};\bar{G}^{-1}\big{]}\big{\|}\left\|y_{0}^{i}\right\|\ldots\left\|y_{n}^{i}% \right\|.

But since we assumed that iterative operators $Q_{j},\ j=1,2,\ldots,n$ have the orders respectively $k_{j},$ with the constants $\rho_{j};\ j=1,2,\ldots,n$ the following relationships result:

(27)

\left\|y_{0}^{i}\right\|=\left\|G\left(x_{i}\right)\right\|

And

(28)	$\displaystyle\left\\|y_{s}^{i}\right\\|$	$\displaystyle\leq\left\\|G\left(x_{s}^{i}\right)\right\\|=\left\\|G\left(Q_{s}% \left(x_{s-1}^{i}\right)\right)\right\\|\leq\rho_{s}\left\\|G\left(Q_{s-1}\left(% x_{s-2}^{i}\right)\right)\right\\|^{k_{s}}$
	$\displaystyle\leq\rho_{s}\rho_{s-1}^{k_{s}}\left\\|G\left(Q_{s-2}\left(x_{s-3}% \right)\right)\right\\|^{k_{s}\cdot k_{s-1}}$
	$\displaystyle\leq\rho_{s}\cdot\rho_{s-1}^{k_{s}}\cdot\rho_{s-1}^{k_{s}\cdot k_% {s-1}}\ldots\rho_{1}^{k_{s}k_{s-1}\ldots k_{2}}\cdot\left\\|G\left(x_{i}\right)% \right\\|^{k_{1}\cdot k_{2}\ldots k_{s}}$

For $s=1,2,\ldots,n.$

If we write now

(29)

C_{s}=\rho_{s}\rho_{s-1}^{k_{s}}\cdot\rho_{s-2}^{k_{s}k_{s-1}}\ldots\rho_{1}^{% k_{s}k_{s-1}\ldots k_{2}};\ \;\;s=2,3,\ldots,n,

(30)

K=\textstyle\prod\limits_{s=2}^{n}C_{s}

And

(31)

m=1+k_{1}+k_{1}k_{2}+\ldots+k_{1}\cdot k_{2}\ldots k_{n}

and if we assume that the divided differences $\big{[}\theta,y_{0}^{i},y_{1}^{i},\ldots,y_{n}^{i};\bar{G}^{-1}\big{]}$ are strongly bounded by the same constant $M>0,$ then we deduce from ( 26 );

(32)

\left\|\bar{x}-x_{i+1}\right\|\leq MK\left\|G\left(x_{i}\right)\right\|^{m},% \qquad i=0,1,\ldots

If we now assume that the first-order divided differences of the application $G$ are strongly bounded by the same constant $B>0,$ we have:

(33)

\left\|G\left(x_{i}\right)\right\|\leq B\left\|\bar{x}-x_{i}\right\|\qquad i=0% ,1,\ldots

Taking into account inequalities ( 33 ) and ( 32 ) we obtain:

(34)

\left\|\bar{x}-x_{i+1}\right\|\leq MKB^{m}\left\|\bar{x}-x_{i}\right\|,\qquad i% =0,1,\ldots

By multiplying the inequalities ( 34 ) by $\left(MKB^{m}\right)^{\frac{1}{m-1}}$ and writing

\delta_{k}=\left(MKB^{m}\right)^{\frac{1}{m-1}}\left\|\bar{x}-x_{k}\right\|,% \qquad k=0,1,\ldots,

we obtain from ( 34 )

(35)

\delta_{i+1}\leq\delta_{i}^{m},\qquad i=0,1,\ldots

We will now admit that we can choose the constants $M,$ $K,$ $B$ and the initial point $x_{0}$ in such a way that $\delta_{0}<1.$

From inequalities ( 35 ) we deduce:

\delta_{i+1}\leq\delta_{0}^{m^{i}},\qquad i=0,1,\ldots

hence taking into account the condition $\delta_{0}<1$ we deduce

\lim_{i\rightarrow\infty}\delta_{i+1}=0

That's to say

\lim_{i\rightarrow i}x_{i+1}=\bar{x}.

We now consider some special cases of the iterative method ( 25 ).

1. If we consider a single iterative operator $Q$ of order $k=1$ then the iterative method ( 25 ) returns to the well-known Aitken-Steffensen method. In this case we have: $m=2.$

2. If $Q_{1}=Q_{2}=\ldots=Q_{n},\ \ k_{1}=k_{2}=\ldots=k_{n}=k,\$ Or $k\neq 1$ SO $C_{s}=\rho^{\frac{k^{n+1}-1}{k-1}}$ And $m=\frac{k^{n+1}-1}{k-1}.$

3. If $Q_{1}=Q_{2}=\ldots=Q_{n}$ And $\ k_{1}=k_{2}=\ldots=k_{n}=1,$ SO $C_{s}=\rho^{s}$ And $m=n.$

Noticed .

The order of convergence given by equality ( 31 ) of method ( 25 ) is the largest possible with respect to the iterative operators $Q_{1},$ $Q_{2},\ldots,Q_{n}$ given, if the order in which they are applied to obtain the elements ( 24 ), is given by the decreasing order of the numbers $k_{1},$ $k_{2},\ldots,k_{n}.$ That is, the order of convergence $m$ is maximal if $k_{1}\geq k_{2}\geq\ldots\geq k_{n}$ and minimal if $k_{1}\leq k_{2}\leq\ldots\leq k_{m}.$ ∎

Bibliography

[1] AM Ostrowski, Reşenie uravnenii i sistem uravnenii, Izd. inostr. bed. Moskva (1963).
[2] I. Păvăloiu, ^†^†margin: clickable $\rightarrow$ Interpolation in normed linear spaces and applications , Mathematica, Cluj, nr. 12 (35) , 2, (1970), pp. 309–324.
[3] I. Păvăloiu, ^†^†margin: clickable $\rightarrow$ Introducere în teoria aproximării soluţiilor ecuaţiilor , Editura Dacia, 1976.
[4] T. Popoviciu, ^†^†margin: clickable $\rightarrow$ Introduction to the theory of divided differences , Mathematical Bulletin of the Romanian Society of Sciences, 42 , 1, (1940) pp. 65–78. JSTOR
[5] AS Sergeev, O metode hord, Sibirski mat. Jurnal, XI, (2), (1961), pp. 282–289.
[6] JF Traub, Iterative Methods for the Solution of Equations, Prentice Hall, Series in Automatic Computation, 1964.
[7] S. Ul'm, Ob obobscennyh razdelennîh raznostiah , II, Izv. Nauk Estonskoi SSR, 16 , 2, (1967), 146–155.

Received, 8.IV.1980

(28)	$\displaystyle\left\\|y_{s}^{i}\right\\|$	$\displaystyle\leq\left\\|G\left(x_{s}^{i}\right)\right\\|=\left\\|G\left(Q_{s}% \left(x_{s-1}^{i}\right)\right)\right\\|\leq\rho_{s}\left\\|G\left(Q_{s-1}\left(% x_{s-2}^{i}\right)\right)\right\\|^{k_{s}}$
	$\displaystyle\leq\rho_{s}\rho_{s-1}^{k_{s}}\left\\|G\left(Q_{s-2}\left(x_{s-3}% \right)\right)\right\\|^{k_{s}\cdot k_{s-1}}$
	$\displaystyle\leq\rho_{s}\cdot\rho_{s-1}^{k_{s}}\cdot\rho_{s-1}^{k_{s}\cdot k_% {s-1}}\ldots\rho_{1}^{k_{s}k_{s-1}\ldots k_{2}}\cdot\left\\|G\left(x_{i}\right)% \right\\|^{k_{1}\cdot k_{2}\ldots k_{s}}$

Solving equations by interpolation

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Solving equations by interpolation

1. Divided difference notation.

Definition 1 .

Definition 2 .

Definition 3 .

2. Interpolation

Theorem 1 .

Demonstration..

3. Solving equations by interpolation

Theorem 2 .

Demonstration..

Definition 4 .

Noticed .

Bibliography

Related Posts

	$\displaystyle\left[x_{k},\ldots,x_{k+i+1};G\right]\left(x_{k+i+1}-x_{k}\right)=$
	$\displaystyle=\left[x_{k+1},\ldots,x_{k+i+1};G\right]-\left[x_{k},\ldots,x_{k+% i};G\right]$