An algorithm in the solving of equations by interpolation

Abstract

Consider the nonlinear equation in \(R\), \(f\left( x\right) =0\), where \(f:A\rightarrow B \), \((A,B\subseteq \mathbb{R})\) which is assumed bijective. The Lagrange inverse interpolation polynomial leads to an iterative method of the form \[x_{i+n+2}=L_{n}[ y_{i+1},y_{i+2},…,y_{i+n+1}:f_{|0}^{-1}],\ \quad x_{1},x_{2},…,x_{n+1}\in I.\] At each iterative step we need to compute the values \(\omega_{k}\left( x\right) \) and \(\omega_{k}^{\prime}\left( y_{i}\right) ,\ i=k,\ldots,k+n\), where \(\omega_{k}\left( y\right) =\Pi_{i=k}^{k_{n}}\left( y-y_{k}\right) \). We give an algorithm for computing \(\omega_{k+1}\left( 0\right) \) and \(\omega_{k+1}^{\prime}\left( y_{i}\right) \) using \(\omega_{k}\left(0\right) \) and \(\omega_{k}^{\prime}\left( y\right) \).

Authors

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)

Title

Original title (in French)

Un algorythme de calcul dans la résolution des equations par interpolation

English translation of the title

An algorithm in the solving of equations by interpolation

Keywords

nonlinear equation in \(\mathbb{R}\); inverse interpolation; iterative method; Lagrange polynomial; inverse Lagrange interpolation polynomial

PDF

Cite this paper as:

I. Păvăloiu, Un algorythme de calcul dans la résolution des equations par interpolation, Seminar on functional analysis and numerical methods. Preprint no. 1 (1987), pp. 130-134 (in French).

About this paper

Journal

Seminar on functional analysis and numerical methods,
Preprint

Publisher Name

“Babes-Bolyai” University,
Faculty of Mathematics,
Research Seminars

DOI

Not available yet.

References

[1] I. Pavaloiu, Rezolvarea ecuatiilor prin interpolare, Editura Dacia, Cluj-Napoca, 1981.

Paper (preprint) in HTML form

Un Algorythme de Calcul dans la Résolution des Équations par Interpolation

"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

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


Un Algorythme de Calcul dans la Résolution des Équations par Interpolation

Ion Păvăloiu

Désignons par f:I une fonction où I est un intervalle de l’axe réel. Nous consiérons l’équation

(1) f(x)=θ,

et nous supposons que cette équation admet une seule solution x¯I. Nous désignons par F=f(I) l’ensemble des velaurs de la fonction f pour xI. Nous supposerons que la fonction f admet une fonction inverse f1:FI.

Nous désignons par xiI,i=1,2,,n+1,xixj pour ij, n+1 approximations différentes de la solution x¯ de l’équation (1) et nous écrivons yi=f(xi),i=1,2,,n+1.

Le polynome

(2) Ln(y1,y2,,yn+1;f1|y)=i=1n+1xiω(y)(yyi)ω(yi)

(3) ω(y)=i=1n+1(yyi)

vérifie les conditions

(4) Ln(y1,y2,,yn+1;f1|yi)=xi,i=1,2,,n+1.

Si x¯I, alors 0F et f1(0)=x¯. En ce cas, en faisent y=0 an (2) nous obenons une approximation pour x¯, c’est-à-dire

(5) x¯Ln(y1,y2,,yn+1;f1|0).

En tenant compte de l’énégalité

(6) f1(0)Ln(y1,y2,,yn+1;f1|0)=
=(1)n+1[y1,y2,,yn+1,0;f1|0]y1y2yn+1

et en écrivent xn+2=Ln(y1,y2,,yn+1;f1|0), nous obtenons

(7) x¯xn+2=(1)n+1[y1,y2,,yn+1,0;f1]y1y2yn+1.

Nous en déduisons qu’abstraction faite du facteur

(1)n+1[y1,y2,,yn+1,0;f1]

xn+2 sera une approximation pour x¯, d’autant meilleure que les nombres y1,y2,,yn+1 sont plus proches de 0.

De’signons à présent par xi+1,xi+2,,xi+n+1I,n+1 approximations de la solution x¯, alors les nombres

(8) xi+n+2=Ln(yi+1,yi+2,,yi+n+1;f1|0)

peuvent eux aussi considèrés comme des approximations pour x¯.

Nous supposerons à présent que pour tous les u1,,un+1F,

|[u1,u2,,un+1,0;f1]|M<+.

Nous avons alors

(9) |x¯xi+n+2|M|yi+1||yi+2||yi+n+1|,i=0,1,,

Si  la differences divisee du premier ordre de la fonction f est bornee, c’est-à-dire |[x,y;f]|β pour tous les x,yI, alors nous obtenons de (9)

(10) |x¯xi+n+2| Mβn+1|x¯xi+1||x¯xi+2||x¯xi+n+1|,i=1,2,

Nous écrirons α=Mβn+1 et ρi=α1n|x¯xi|,i=1,2,

Il résulte alors de (10)

(11) ρi+n+2ρi+1ρi+2ρi+n+1,i=0,1,2,

Nous consiérons à présent l’équation aux différences

(12) γi+n+2=γi+1+γi+2++γi+n+1,i=0,1,

et nous supposons gu’il existe un nombre d<1 tel que ρsdγs pour s=1,2,,n+1.

Nous associons à l’équation (12) l’équation

(13) tn+1=tn+tn1++t+1.

En ce cas, la solution de l’équation (12) peut s’exprimer comme suit:

(14) γi+k=C1t1i+k+C2t2i+k++Cn+1tn+1i+k

t1,t2,,tn+1 sont les racines de l’équation (13) et C1,C2,,Cn+1 se déterminent par les conditions initiales γs=γs0,s=1,2,,n+1.

On constate facilement que l’équation (13) admet une seule racine réelle ω; 1<ω<2.

Si nous admettons que

(15) ρsdωs;s=1,2,,n+1

alors nous déduisons facilement de (11) que les inégalités (15) ont lieu pour tout s, ce qui signifie que

(16) limnρn=0

c’est-à-dire que la suite (xn)n=1 converge vers la solution de l’équation (1).

Nous présenterons par la suite un algorythme de calcul des  valeurs des polynomes ωk(0) et ωk(yi),i=k,k+1,,k+n,

(17) ωk(y)=i=kk+n(yyi),k=1,2,

Les polynomes (17) sont utilisés à la construction de la suite de polynomes d’interpolation inverse de Lagrange, qui conduisent à la suite d’approximations (xn)n=1, dont les éléments sont donnés par l’égalité (8).

Il résulte de (17)

ωk+1(y)=ωk(y)yyn+k+1yyk

d’où nous déduisons la relation

(18) ωk+1(0)=ωk(0)yn+k+1yk

qui nous offre une formule des récurrence pour le calcul des valeurs des polynomes ωk pour y=0.

Pour ωk+1(y) nous avons

ωk+1(y)=[ωk(y)(yyn+k+1)+ωk(y)](yyk)ωk(y)(yyn+k+1)(yyk)2.

Nous en déduisons les formules de récurrence suivantes:

(19) ωk+1(yi)={ωk(yi)yiyn+k+1yiyk,pour i=k+1,k+n¯ωkyiyiyk,pour i=n+k+1

Les relations de récurrence (18) et (19) nous offrent la posibilité d’obtenir la suite de polynomes d’interpolation inverse de Lagrange, an utilisent à un pas quelconque d’itération certaine éléments qui ont déjà calculés au cours du pas précédent.

Bibliographie



Institutul de Matematică

Oficiul Poştal 1, C.P. 68

3400 Cluj-Napoca, Romania




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

1987

Related Posts