"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

Preprint Nr.1, 1984, pp. 97-104

Solving equations with the aid of inverse interpolation spline functions

by
C. Iancu and I. Păvăloiu

In the following we present a generalization of the result presented in the work [ 2 ] , concerning the resolution of equations using inverse interpolation spline functions.

Consider the equation

(1)

f\left(x\right)=0

Or $f:I\rightarrow\mathbb{R}$ is a real function of a real variable and I is an interval of the real axis.

We designate by $AND$ a set of $m$ real numbers distinct from I, in particular

(2)

x_{1}<x_{2}<\cdots<x_{m}

Regarding the function $f$ we will assume that its values are known $y_{i}^{\left(0\right)}=f\left(x_{i}\right),\ i=1,2,\ldots,m$ as well as the values of its successive derivatives up to the order $n-1$ to the point $x_{1},\ n\in\mathbb{N}$ , that's to say $f^{\prime}\left(x_{1}\right)=y_{1}^{\left(1\right)},f^{\prime\prime}\left(x_{1% }\right)=y_{1}^{\left(2\right)},\ldots,f^{\left(n-1\right)}\left(x_{1}\right)=% y_{1}^{\left(n-1\right)}$ .

Such a function can be obtained as a result of an experiment or, for example, as a numerical solution to a Cauchy-type problem relating to a differential equation.

To fix the ideas, we will assume that equation ( 1 ) admits a single root $\bar{x}\in I$ and that there are two real numbers $x_{p},x_{p+1}\in E$ such as $f\left(x_{p}\right)f\left(x_{p+1}\right)<0,$ that's to say $x\in\left(x_{p},x_{p+1}\right)$ .

In the work [ 2 ] the author constructs inverse interpolation spline functions of the third degree, with the help of which he proceeds to the approximation of the roots of the equations of the form ( 1 ).

In the following we propose to use the two-node Hermite-type inverse interpolation polynomial, studied in [ 3 ] , in order to present a generalization of the results contained in [ 2 ] .

We designate by $V_{x_{1}}$ a neighborhood of the point $x_{1}$ and write $F_{1}=f\left(V_{x_{1}}\right)$ . We will subsequently assume that the restriction of the function $f$ to the whole $V_{x_{1}}$ is bijective and that $y_{1}^{\left(1\right)}\neq 0;$ in this case, the successive derivatives of the function $f^{-1}$ to the point $y_{1}$ can be obtained using the formula [ 4 ] :

(3)

\left[f^{-1}\left(y_{1}\right)\right]^{\left(k\right)}=\sum\tfrac{\left(2k-2-i% _{1}\right)!\left(-1\right)^{k-1+i_{1}}}{i_{2}!\ldots i_{k}!\left(f^{\prime}% \left(x_{1}\right)\right)^{2k-1}}\big{(}\tfrac{f^{\prime}\left(x_{1}\right)}{1% !}\big{)}^{i_{1}}\ldots\big{(}\tfrac{f^{\left(k\right)}\left(x_{1}\right)}{k!}% \big{)}^{i_{k}}

where the above sum is over all integer and non-negative solutions of the system of equations

(4)		$\displaystyle i_{2}+2i_{3}+\ldots+\left(k-1\right)i_{k}$	$\displaystyle=k-1$
	$\displaystyle i_{1}+i_{2}+\ldots+i_{k}$	$\displaystyle=k-1,\qquad\ k=1,2,\ldots,n-1.$

The inverse interpolation Hermite polynomial at points $y_{1}^{\left(0\right)},y_{2}^{\left(0\right)}$ will then take the following form:

(5)

\displaystyle P_{1}\left(y\right)

\displaystyle=\sum_{j=0}^{n-1}\ \sum_{k=0}^{n-j-1}\left[f^{-1}\left(y_{1}% \right)\right]^{\left(j\right)}\tfrac{1}{k!j!}\left[\tfrac{\left(y-y_{1}\right% )^{n}}{\omega_{1}\left(y\right)}\right]_{y=y_{1}}^{\left(k\right)}\tfrac{% \omega_{1}\left(y\right)}{\left(y-y_{1}\right)^{n-j-k}}+x_{2}\big{(}\tfrac{y-y% _{1}}{y_{2}-y_{1}}\big{)}^{n}

(6)

\omega_{1}\left(y\right)=\left(y-y_{1}\right)^{n}\left(y-y_{2}\right)

We will designate by $P_{s}\left(y\right)$ the inverse Hermite interpolation polynomial in the interval $\left[y_{s},y_{s+1}\right]$ who meets the conditions:

(7)		$\displaystyle P_{s}^{\left(r\right)}\left(y_{s}\right)$	$\displaystyle=P_{s-1}^{\left(r\right)}\left(y_{s}\right),\ \ r=0,1,\ldots,n-1$
	$\displaystyle P_{s}\left(y_{s+1}\right)$	$\displaystyle=x_{s+1}$

Under these conditions, $P_{s}\left(y\right)$ will take the following form

(8)			$\displaystyle P_{s}\left(y\right)=$
		$\displaystyle=\sum_{j=0}^{n-1}\ \sum_{k=0}^{n-j-1}\left[P_{s-1}\left(y_{s}% \right)\right]^{\left(j\right)}\tfrac{1}{k!j!}\left[\tfrac{\left(y-y_{s}\right% )^{n}}{\omega_{s}\left(y\right)}\right]_{y=y_{n}}^{\left(k\right)}\tfrac{% \omega_{s}\left(y\right)}{\left(y-y_{s}\right)^{n-j-k}}+x_{s+1}\big{(}\tfrac{y% -y_{s}}{y_{s+1}-y_{s}}\big{)}^{n},$

(9)

\omega_{s}\left(y\right)=\left(y-y_{s}\right)^{n}\left(y-y_{s+1}\right)

For $s=2,3,\ldots,p$ .

It is easy to see that the expression ( 8 ) can be written in the form

(10)

\displaystyle P_{s}\left(y\right)

\displaystyle=\sum_{j=0}^{n-1}\ \sum_{k=0}^{n-j-1}\left[P_{s-1}\left(y_{s}% \right)\right]^{\left(j\right)}\tfrac{\left(-1\right)^{k}\left(y-y_{s}\right)^% {j+k}\left(y-y_{s+1}\right)}{j!\left(y_{s}-y_{s+1}\right)^{k+1}}+x_{s+1}\big{(% }\tfrac{y-y_{s}}{y_{s+1}-y_{s}}\big{)}^{n}

Or $s=2,3,\ldots,p$ .

An approximate value for the root $\bar{x}$ of equation ( 1 ) is given by

(11)

\bar{x}\simeq P_{p}\left(0\right),

that's to say

(12)

\bar{x}\simeq\sum_{j=0}^{n-1}\ \sum_{k=0}^{n-j-1}\left[P_{p-1}\left(y_{p}% \right)\right]^{\left(j\right)}\tfrac{\left(-1\right)^{j+1}y_{p}^{j+k}y_{p+1}}% {j!\left(y_{p}-y_{p+1}\right)^{k+1}}+\tfrac{\left(-1\right)^{n}x_{p+1}y_{p}^{n% }}{\left(y_{p+1}-y_{p}\right)^{n}}

We will now deal with two special cases of the problem presented above.

1. The case $n=2$ . In this case, the polynomials ( 10 ) take the following form

(13)		$\displaystyle P_{s}\left(y\right)$	$\displaystyle=\sum_{j=0}^{1}\sum_{k=0}^{1-j}\left[P_{s-1}\left(y_{s}\right)% \right]^{\left(j\right)}\tfrac{\left(-1\right)^{k}\left(y-y_{s}\right)^{j+k}% \left(y-y_{s+1}\right)}{j!\left(y_{s}-y_{s+1}\right)^{k+1}}+x_{s+1}\big{(}% \tfrac{y-y_{s}}{y_{s+1}-y_{s}}\big{)}^{2},$
	$\displaystyle\ s$	$\displaystyle=2,3,\ldots,p$

And

(14)

\displaystyle P_{1}\left(y\right)

\displaystyle=\sum_{j=0}^{1}\sum_{k=0}^{1-j}\left[f^{-1}\left(y_{1}\right)% \right]^{\left(j\right)}\tfrac{\left(-1\right)^{k}\left(y-y_{1}\right)^{j+k}% \left(y-y_{2}\right)}{j!\left(y_{1}-y_{2}\right)^{k+1}}+x_{2}\big{(}\tfrac{y-y% _{1}}{y_{2}-y_{1}}\big{)}^{2}

It is easy to see that the expression ( 12 ) can be put in this case in the form [ 1 ]

(15)

\bar{x}\simeq x_{p}+a_{p}y_{p}^{2}-y_{p}P_{p-1}^{\prime}\left(y_{p}\right)

(16)

a_{p}=\tfrac{1-P_{p-1}^{\prime}\left(y_{p}\right)\left[x_{p},x_{p+1};f\right]}% {\left(x_{p+1}-x_{p}\right)\left[x_{p},x_{p+1};f\right]^{2}}

2. The case $n=3$ . In this case ( 10 ) is written

(17)

\displaystyle P_{s}\left(y\right)

\displaystyle=\sum_{j=0}^{2}\sum_{k=0}^{2-j}\left[P_{s-1}\left(y_{s}\right)% \right]^{\left(j\right)}\tfrac{\left(-1\right)^{k}\left(y-y_{s}\right)^{j+k}% \left(y-y_{s+1}\right)}{j!\left(y_{s}-y_{s+1}\right)^{k+1}}+x_{s+1}\big{(}% \tfrac{y-y_{s}}{y_{s+1}-y_{s}}\big{)}^{3}

with

(18)

\displaystyle P_{1}\left(y\right)

\displaystyle=\sum_{j=0}^{2}\sum_{k=0}^{2-j}\left[f^{-1}\left(y_{1}\right)% \right]^{\left(j\right)}\tfrac{\left(-1\right)^{k}\left(y-y_{1}\right)^{j+k}% \left(y-y_{2}\right)}{j!\left(y_{1}-y_{2}\right)^{k+1}}+x_{2}\left(\tfrac{y-y_% {1}}{y_{2}-y_{1}}\right)^{3}

and ( 12 ) is written [ 1 ]

(19)

\bar{x}\simeq x_{p}-P_{p-1}^{\prime}\left(y_{p}\right)y_{p}+\frac{P_{p-1}^{% \prime\prime}\left(y_{p}\right)}{2}y_{p}^{2}-a_{p}y_{p}^{3}

(20)

a_{p}=\frac{1-P_{p-1}^{\prime}\left(y_{p}\right)\left[x_{p},x_{p+1};f\right]-% \frac{P_{p-1}^{\prime\prime}\left(y_{p}\right)}{2}\left[x_{p},x_{p+1};f\right]% ^{2}\left(x_{p+1}-x_{p}\right)}{\left[x_{p},x_{p+1};f\right]^{3}\left(x_{p+1}-% x_{p}\right)}

Numerical example.

We consider the equation

(21)

f\left(x\right)=4x^{3}+3x^{2}+3x-1=0

which admits the only real root $x=0,25.$

We will assume that with respect to the function $f$ from ( 21 ) we know the following values:

(22)

\begin{cases}f\left(0\right)&=-1\\ f^{\prime}\left(0\right)&=3\\ f^{\prime\prime}\left(0\right)&=6\\ f\left(0.1\right)&=-0.666\\ f\left(0.2\right)&=-0.248\\ f\left(0.3\right)&=0.278\end{cases}

It follows from ( 22 ) that $x_{p}=0.2$ And $x_{p+1}=0.3.$

If we use the string method only once in the interval $\left(0.2;\ 0.3\right)$ we get for $\bar{x}$ the following approximate value

\bar{x}\simeq 0.2471483

Applying the method given by ( 15 ) we obtain for $\bar{x}$ the approximate value

\bar{x}\simeq 0.2501480

while method ( 19 ) leads us to the following approximate value

\bar{x}\simeq 0.2504372

We note that in the case of the example treated the method which gives the best approximation of the root of the equation ( 21 ) is the method of inverse interpolation with the second degree spline function.

In the approximation formula given by ( 15 ) for the root $\bar{x}$ of equation ( 1 ), obtained using the second-order inverse interpolation spline function, is the value of the derivative $P_{p-1}^{\prime}\left(y_{p}\right)$ of the polynomial $P_{p-1}$ to the point $y_{p}$ .

It is easily seen that this value can be obtained using the first-order divided differences of the function $f$ taken on consecutive nodes and using $f^{\prime}\left(x_{1}\right)$ .

$P_{p-1}^{\prime}\left(y_{p}\right)$ which appears in ( 15 ) is expressed in particular using the following algorithm:

(23)

\left\{\begin{array}[]{l}P_{1}^{\prime}\left(y_{2}\right)=\frac{2}{\left[x_{1}% ,x_{2};f\right]}-\frac{1}{f^{\prime}\left(x_{1}\right)}\\ P_{p-1}^{\prime}\left(y_{p}\right)=\frac{2}{\left[x_{p-1},x_{p};f\right]}+2% \displaystyle\sum_{k=2}^{p-1}\tfrac{\left(-1\right)^{k}}{\left[x_{k-1},x_{k};f% \right]}-\tfrac{1}{f^{\prime}\left(x_{1}\right)},\end{array}\right.

and $p$ is an even natural number, or

(24)

\displaystyle P_{p-1}^{\prime}\left(y_{p}\right)

\displaystyle=\tfrac{2}{\left[x_{p-1},x_{p};f\right]}+2\sum_{k=2}^{p-1}\tfrac{% \left(-1\right)^{k+1}}{\left[x_{k-1},x_{k};f\right]}+\tfrac{1}{f^{\prime}\left% (x_{1}\right)}

and $p$ is an odd natural number, where

\left[x_{i},x_{i+1};f\right]=\tfrac{y_{i+1}-y_{i}}{x_{i+1}-x_{i}},\ i=1,2,% \ldots,p-1.

It is difficult to obtain formulas analogous to those given by ( 23 ) and ( 24 ) for the calculation of the values of the successive derivatives of the polynomial $P_{p-1}$ to the point $y_{p}$ in the general case and even if this can be done, they take a very complicated form.

Bibliography

[1] C. Iancu, Data analysis and processing using spline functions . Doctoral thesis, Cluj (1983), Faculty of Mathematics of Babeş-Bolyai University.
[2] A. Imamov, Reşenie nelineinîb uravnenii metodom obratnogo splain-interpolovaniis. Metodî splain-funkţii , Akademia Nauk SSSR, Novosibirsk, 81 (1979), 74–80
[3] I. Pavaloiu, ^†^†margin: $\leftarrow$ clickable Solving equations by interpolation . Dacia Publishing House, Cluj, 1981.
[4] Turowicz, BA, On higher-order derivatives of an inverse function , Colloq. Math. (1959), 83–87.

Solving equations with the aid of inverse interpolation spline functions

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

Solving equations with the aid of inverse interpolation spline functions

Bibliography

Related Posts