"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

Preprint Nr.1, 1987, pp.130-134

An algorithm in the solving of equations by interpolation

Ion Pavaloiu

Let us designate by $f:I\rightarrow{\mathbb{R}}$ a function where $I$ is an interval of the real axis. We consider the equation

(1)

f\left(x\right)=\theta,

and we assume that this equation has only one solution $\bar{x}\in I$ . We designate by $F=f\left(I\right)$ the set of velors of the function $f$ For $x\in I$ . We will assume that the function $f$ admits an inverse function $f^{-1}:F\rightarrow I$ .

We designate by $x_{i}\in I,\ i=1,2,\ldots,n+1,\ x_{i}\neq x_{j}$ For $i\neq j$ , $n+1$ different approximations of the solution $\bar{x}$ from equation ( 1 ) and we write $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ .

The polynomial

(2)

L_{n}\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1}|y\right)=\sum_{i=1}^{n+1}x_{i}% \tfrac{\omega\left(y\right)}{\left(y-y_{i}\right)\omega^{\prime}\left(y_{i}% \right)}

(3)

\omega\left(y\right)=\prod\limits_{i=1}^{n+1}\left(y-y_{i}\right)

check the conditions

(4)

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

And $\bar{x}\in I,$ SO $0\in F$ And $f^{-1}\left(0\right)=\bar{x}$ . In this case, make them $y=0$ an ( 2 ) we obtain an approximation for $\bar{x}$ , that's to say

(5)

\bar{x}\simeq L_{n}\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1}|0\right).

Taking into account the inequality

(6)			$\displaystyle f^{-1}\left(0\right)-L_{n}\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1% }\|0\right)=$
		$\displaystyle=\left(-1\right)^{n+1}\left[y_{1},y_{2},\ldots,y_{n+1},0;f^{-1}\|0% \right]y_{1}y_{2}\ldots y_{n+1}$

and write about it $x_{n+2}=L_{n}\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1}|0\right),$ we get

(7)

\bar{x}-x_{n+2}=\left(-1\right)^{n+1}\left[y_{1},y_{2},\ldots,y_{n+1},0;f^{-1}% \right]y_{1}y_{2}\ldots y_{n+1}.

We deduce that, ignoring the factor

\left(-1\right)^{n+1}\left[y_{1},y_{2},\ldots,y_{n+1},0;f^{-1}\right]

$x_{n+2}$ will be an approximation for $\bar{x}$ , all the better as the numbers $y_{1},y_{2},\ldots,y_{n+1}$ are closer to $0$ .

Let us now designate by $x_{i+1},x_{i+2},\ldots,x_{i+n+1}\in I,\ n+1$ approximations of the solution $\bar{x},$ so the numbers

(8)

x_{i+n+2}=L_{n}\left(y_{i+1},y_{i+2},\ldots,y_{i+n+1};f^{-1}|0\right)

can also be considered as approximations for $\bar{x}$ .

We will now assume that for all $u_{1},\ldots,u_{n+1}\in F,$

\left|\left[u_{1},u_{2},\ldots,u_{n+1},0;f^{-1}\right]\right|\leq M<+\infty.

We then have

(9)

\left|\bar{x}-x_{i+n+2}\right|\leq M\cdot\left|y_{i+1}\right|\cdot\left|y_{i+2% }\right|\cdots\left|y_{i+n+1}\right|,\qquad i=0,1,\ldots\ ,

If the first order divided difference of the function $f$ is limited, that is to say $\left|\left[x,y;f\right]\right|\leq\beta$ for all $x,y\in I,$ then we get from ( 9 )

(10)

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

\displaystyle\leq M\beta^{n+1}\left|\bar{x}-x_{i+1}\right|\left|\bar{x}-x_{i+2% }\right|\ldots\left|\bar{x}-x_{i+n+1}\right|,\quad i=1,2,\ldots

We will write $\alpha=M\beta^{n+1}$ And $\rho_{i}=\alpha^{\frac{1}{n}}\left|\bar{x}-x_{i}\right|,\ i=1,2,\ldots$

It then follows from ( 10 )

(11)

\rho_{i+n+2}\leq\rho_{i+1}\cdot\rho_{i+2}\cdots\rho_{i+n+1},\qquad i=0,1,2,\ldots

We now consider the equation to differences

(12)

\gamma_{i+n+2}=\gamma_{i+1}+\gamma_{i+2}+\ldots+\gamma_{i+n+1},\qquad i=0,1,\ldots

and we assume that there exists a number $d<1$ such as $\rho_{s}\leq d^{\gamma_{s}}$ For $s=1,2,\ldots,n+1$ .

We associate to equation ( 12 ) the equation

(13)

t^{n+1}=t^{n}+t^{n-1}+\ldots+t+1.

In this case, the solution to equation ( 12 ) can be expressed as follows:

(14)

\gamma_{i+k}=C_{1}t_{1}^{i+k}+C_{2}t_{2}^{i+k}+\ldots+C_{n+1}t_{n+1}^{i+k}

Or $t_{1},t_{2},\ldots,t_{n+1}$ are the roots of equation ( 13 ) and $C_{1},C_{2},\ldots,C_{n+1}$ are determined by the initial conditions $\gamma_{s}=\gamma_{s}^{0},\ s=1,2,\ldots,n+1.$

It is easily seen that equation ( 13 ) has only one real root $\omega;\ 1<\omega<2$ .

If we admit that

(15)

\rho_{s}\leq d^{\omega^{s}};\ s=1,2,\ldots,n+1

then we easily deduce from ( 11 ) that the inequalities ( 15 ) hold for all $s\in{\mathbb{N}}$ , which means that

(16)

\lim_{n\rightarrow\infty}\rho_{n}=0

that is to say that the continuation $\left(x_{n}\right)_{n=1}^{\infty}$ converges to the solution of equation ( 1 ).

We will subsequently present an algorithm for calculating the values of polynomials. $\omega_{k}\left(0\right)$ And $\omega_{k}^{\prime}\left(y_{i}\right),\ i=k,\ k+1,\ldots,k+n,$ Or

(17)

\omega_{k}\left(y\right)=\prod\limits_{i=k}^{k+n}\left(y-y_{i}\right),\qquad k% =1,2,\ldots

The polynomials ( 17 ) are used to construct the sequence of inverse Lagrange interpolation polynomials, which lead to the sequence of approximations $\left(x_{n}\right)_{n=1}^{\infty}$ , whose elements are given by the equality ( 8 ).

It follows from ( 17 )

\omega_{k+1}\left(y\right)=\omega_{k}\left(y\right)\cdot\tfrac{y-y_{n+k+1}}{y-% y_{k}}

from which we deduce the relationship

(18)

\omega_{k+1}\left(0\right)=\omega_{k}\left(0\right)\cdot\tfrac{y_{n+k+1}}{y_{k}}

which provides us with a recurrence formula for calculating the values of polynomials $\omega_{k}$ For $y=0$ .

For $\omega_{k+1}^{\prime}\left(y\right)$ We have

\omega_{k+1}\left(y\right)=\tfrac{\left[\omega_{k}\left(y\right)\left(y-y_{n+k% +1}\right)+\omega_{k}\left(y\right)\right]\left(y-y_{k}\right)-\omega_{k}\left% (y\right)\left(y-y_{n+k+1}\right)}{\left(y-y_{k}\right)^{2}}.

We deduce the following recurrence formulas:

(19)

\omega_{k+1}^{\prime}\left(y_{i}\right)=\begin{cases}\omega_{k}^{\prime}\left(% y_{i}\right)\tfrac{y_{i}-y_{n+k+1}}{y_{i}-y_{k}},&\text{pour }i=\overline{k+1,% k+n}\\ \omega_{k}\tfrac{y_{i}}{y_{i}-y_{k}},&\text{pour \ }i=n+k+1\end{cases}

The recurrence relations ( 18 ) and ( 19 ) offer us the possibility of obtaining the sequence of inverse Lagrange interpolation polynomials, using at any iteration step certain elements which have already been calculated during the previous step.

Bibliography

[1] I. Pavaloiu, ^†^†margin: $\leftarrow$ clickable Solving equations by interpolation , Dacia Publishing House, Cluj-Napoca, 1981.

Institute of Mathematics

Post Office 1, PO Box 68

3400 Cluj-Napoca, Romania

This paper is in a final form and no version of it will be submitted for publication elsewhere.

An algorithm in the solving of 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

References

Paper (preprint) in HTML form

An algorithm in the solving of equations by interpolation

Bibliography

Related Posts