Abstract
We consider a function \(f\in C^{n-1}[a,b]\) and the nodes \(a=x_{0}<x_{1}<\ldots<x_{m}=b\). Given the values \begin{align}f\left( x_{i}\right) =&u_{i}, \quad i=1,…,m \\ f^{\left( k\right) }\left( x_0\right) =&p_{0}^{k},\quad k=1,…,n-1,\end{align} we show that there exists on each interval \(\left[ x_{i-1},x_{i}\right] ,\ i=1,…,m,\) a unique polynomial \(P_{i}\) of degree \(m\) that satisfies \begin{align} P\left( x_{i}\right) =& u_{i}, \\ P_{i}^{\left( k\right) }\left( x_{i}\right) =&P_{i-1}^{\left( k\right) }\left(x_{i}\right) ,\quad k=1,…,n-1,\end{align} i.e. the resulted polynomials are successively joined. In this paper we show how these polynomials may be constructed. The functions \(f\) is therefore approximated by these polynomials.
Original Title (in French)
Sur l’intérpolation à l’aide des polynômes raccordées
Authors
Ion Păvăloiu
Tiberiu Popoviciu Institute of Numerical Analysis
Keywords
approximation by polynomials, joined polynomials, Hermite interpolation
Cite this paper as:
I. Păvăloiu, Sur l’intérpolations à l’aide des polynômes raccordées, Mathematica, 6(27) (1964) no. 2, pp. 295-299 (in French).
About this paper
Journal
Mathematica
Publisher Name
Editura Academiei R.S. Române
DOI
Not available yet.
Print ISBN
Not available yet.
Online ISBN
Not available yet.
Google Scholar Profile
References
[1] Boor Carl de, Bicubic spline interpolation. Journal of Mathenatics and Physics. 41 (1962) 3.
[2] I959.
Paper (preprint) in HTML form
ON INTERPOLATION WITH CONNECTED POLYNOMIALS
- Either f(x)inC^(n-1)f(x) \in C^{n-1} a bounded function, defined in the interval [a,b][a, b] and either a=x_(0) < x_(1) < dots < x_(m)=ba=x_{0}<x_{1}<\ldots<x_{m}=b a division of 1 interval [a,b][a, b].
Suppose that we know the values of 1a function f(x)f(x) In the m+1m+1 Interval division nodes [a,b][a, b] as well as the values of the successive derivatives of 1a function f(x)f(x) in the initial node x_(0)x_{0}.
We ask:
{:[(1)f(x_(i))=u_(i)","quad i=1","0","dots","n],[f^((k))(x_(0))=p_(0)^(k)","quad k=1","2","dots","n-1]:}\begin{align*}
f\left(x_{i}\right) & =u_{i}, \quad i=1,0, \ldots, n \tag{1}\\
f^{(k)}\left(x_{0}\right) & =p_{0}^{k}, \quad k=1,2, \ldots, n-1
\end{align*}
Either P_(n)\mathcal{P}_{n} the class of all functions defined in the interval [x_(0),x_(m)]\left[x_{0}, x_{m}\right] and who in each of the intervals [x_(i-1),x_(i)]i=1,2,dots,m\left[x_{i-1}, x_{i}\right] i=1,2, \ldots, m are identically equal to a polynomial P_(n_(i))(x)P_{n_{i}}(x) of degree nn.
Definite n. We call a connected polynomial of the order n-1n-1, each function varphi(x)\varphi(x) who belongs to the p_(n)p_{n} and for which we have
P_(n_(i))^((k))(x_(i))=P_(n_(i+1))^((k))(x_(i)),quad{:[(2)i=1","2","dots","m-1],[k=0","1","dots","n-1.]:}P_{n_{i}}^{(k)}\left(x_{i}\right)=P_{n_{i+1}}^{(k)}\left(x_{i}\right), \quad \begin{align*}
& i=1,2, \ldots, m-1 \tag{2}\\
& k=0,1, \ldots, n-1 .
\end{align*}
Let be the values given (1) - we ask to determine the polynomial P(x)P(x) connected of 1 order n-1n-1 who meets the conditions:
P(x_(i))=u_(i),quad i=0,1,dots,mP\left(x_{i}\right)=u_{i}, \quad i=0,1, \ldots, m
{:(3)P^((k))(x_(0))=p_(0)^(k)","quad k=1","2","dots","n-1:}\begin{equation*}
P^{(k)}\left(x_{0}\right)=p_{0}^{k}, \quad k=1,2, \ldots, n-1 \tag{3}
\end{equation*}
Lemma 1. If we give the values
{:[f^((k))(a)=beta_(k)","quad k=0","1","dots","n-1],[(4)f(c)=gamma_(0)","quad c!=a]:}\begin{align*}
& f^{(k)}(a)=\beta_{k}, \quad k=0,1, \ldots, n-1 \\
& f(c)=\gamma_{0}, \quad c \neq a \tag{4}
\end{align*}
where c is a point in the interval [a,b][a, b] then there exists a single polynomial of degree, Q_(n)(x)Q_{n}(x) of the form Q_(n)(x)=sum_(j=0)^(n)alpha_(j)(x-a)^(j)Q_{n}(x)=\sum_{j=0}^{n} \alpha_{j}(x-a)^{j} which satisfies conditions (4) in points a and c.
Proof: Writing that the polynomial Q_(n)(x)Q_{n}(x) satisfies the conditions (4) we obtain for the determination of alpha_(j),quad j= bar(0,n)\alpha_{j}, \quad j=\overline{0, n} the following system of algebraic linear equations:
{:[(5)l!alpha_(l)=beta_(l)","quad l=0","1","dots","n-1],[alpha_(0)+alpha_(1)(c-a)+dots+alpha_(n)(c-a)^(n)=gamma_(0)]:}\begin{align*}
& l!\alpha_{l}=\beta_{l}, \quad l=0,1, \ldots, n-1 \tag{5}\\
& \alpha_{0}+\alpha_{1}(c-a)+\ldots+\alpha_{n}(c-a)^{n}=\gamma_{0}
\end{align*}
We determinant of the system has the form:
{:(6)Delta=|[1,0,.,.,0,0],[0,1!,.,.,.,0,0],[.,.,.,.,.,.,.],[.,.,.,.,.,.,.],[.,0^(˙),.,.,.,.,.],[0,.,.,.,(n-1)!,0],[1,c-a,.,.,(c-a)^(n-1),(c-a)^(n)]|=prod_(i=0)^(n-1)i!(c-a)^(n):}\Delta=\left|\begin{array}{ccccccc}
1 & 0 & . & . & 0 & 0 \tag{6}\\
0 & 1! & . & . & . & 0 & 0 \\
. & . & . & . & . & . & . \\
. & . & . & . & . & . & . \\
. & \dot{0} & . & . & . & . & . \\
0 & . & . & . & (n-1)! & 0 \\
1 & c-a & . & . & (c-a)^{n-1} & (c-a)^{n}
\end{array}\right|=\prod_{i=0}^{n-1} i!(c-a)^{n}
Given that we have assumed that c!=ac \neq a, it follows that Delta!=0\Delta \neq 0 and consequently, the system (5) has a single solution.
Solving system (5) we obtain for alpha_(0),dots,alpha_(n)\alpha_{0}, \ldots, \alpha_{n}
(7)
(7)
alpha_(l)=(beta_(l))/(l!),quad l=0,1,dots,n-1\alpha_{l}=\frac{\beta_{l}}{l!}, \quad l=0,1, \ldots, n-1
alpha_(n)=(gamma_(0)-beta_(0))/((c-a)^(n))-sum_(k=1)^(n-1)(beta_(k))/(k!(c-a)^(n-k))\alpha_{n}=\frac{\gamma_{0}-\beta_{0}}{(c-a)^{n}}-\sum_{k=1}^{n-1} \frac{\beta_{k}}{k!(c-a)^{n-k}}
Lemma 2. Let ( x_(0),x_(1),x_(2)x_{0}, x_{1}, x_{2} ) a given system of three consecutive knots, such that we have,
Deltax_(0)=x_(1)-x_(0)!=0,Deltax_(1)=x_(2)-x_(1)!=0.\Delta x_{0}=x_{1}-x_{0} \neq 0, \Delta x_{1}=x_{2}-x_{1} \neq 0 .
If P(x)P(x) and R(x)R(x) are two degree polynomials nn who belong to the class P_(n)P_{n} and who on the knots x_(0),x_(1),x_(2)x_{0}, x_{1}, x_{2} meet the conditions
{:[(8)R^((k))(x_(0))=p_(0)^(k)","quad k= bar(1,n-1)","quad R(x_(0))=u_(0)","quad R(x_(1))=u_(1)],[P^((k))(x_(1))=p_(1)^(k)","quad k= bar(1,n-1)","quad P(x_(1))=u_(1)","quad P(x_(2))=u_(2)]:}\begin{gather*}
R^{(k)}\left(x_{0}\right)=p_{0}^{k}, \quad k=\overline{1, n-1}, \quad R\left(x_{0}\right)=u_{0}, \quad R\left(x_{1}\right)=u_{1} \tag{8}\\
P^{(k)}\left(x_{1}\right)=p_{1}^{k}, \quad k=\overline{1, n-1}, \quad P\left(x_{1}\right)=u_{1}, \quad P\left(x_{2}\right)=u_{2}
\end{gather*}
then the necessary and sufficient conditions for the point to be x_(1)x_{1} we have
{:(9)P^((k))(x_(1))=R^((k))(x_(1))","quad k=1","n-1:}\begin{equation*}
P^{(k)}\left(x_{1}\right)=R^{(k)}\left(x_{1}\right), \quad k=1, n-1 \tag{9}
\end{equation*}
is that between p_(1)^(k),p_(0)^(k),k=1,2,dots,n-1,u_(0),u_(1)p_{1}^{k}, p_{0}^{k}, k=1,2, \ldots, n-1, u_{0}, u_{1}, we have the relations:
where
where
{:[(10)p_(1)^(k)=sum_(i=0)^(n-k-1)p_(0)^(k+i)(Deltax_(0)^(i))/(i!)+Aprod_(i=n-k+1)^(n)i Deltax_(0)^(n-k)],[(11)A=(u_(1)-u_(0))/(Deltax_(n)^(0))-sum_(i=1)^(n-1)(p_(0)^(i))/(i!Deltax_(0)^(n-i))]:}\begin{gather*}
p_{1}^{k}=\sum_{i=0}^{n-k-1} p_{0}^{k+i} \frac{\Delta x_{0}^{i}}{i!}+A \prod_{i=n-k+1}^{n} i \Delta x_{0}^{n-k} \tag{10}\\
A=\frac{u_{1}-u_{0}}{\Delta x_{n}^{0}}-\sum_{i=1}^{n-1} \frac{p_{0}^{i}}{i!\Delta x_{0}^{n-i}} \tag{11}
\end{gather*}
Demonstration.
Necessity: Polynomials P(x)P(x) and R(x)R(x) unambiguously determined by the conditions (8) have the form:
{:(12)R(x)=u_(0)+sum_(i=1)^(n-1)(p_(0)^(i)(x-x_(0))^(i))/(i!)+[(u_(1)-u_(0))/(Deltax_(0)^(n))-sum_(i=1)^(n-1)(p_(0)^(i))/(i!Deltax_(0)^(n-i))](x-x_(0))^(n):}\begin{equation*}
R(x)=u_{0}+\sum_{i=1}^{n-1} \frac{p_{0}^{i}\left(x-x_{0}\right)^{i}}{i!}+\left[\frac{u_{1}-u_{0}}{\Delta x_{0}^{n}}-\sum_{i=1}^{n-1} \frac{p_{0}^{i}}{i!\Delta x_{0}^{n-i}}\right]\left(x-x_{0}\right)^{n} \tag{12}
\end{equation*}
P(x)=u_(1)+sum_(i=1)^(n-1)(p_(1)^(i)(x-x_(1))^(i))/(i!)+[(u_(2)-u_(1))/(Deltax_(1)^(n))-sum_(i=1)^(n-1)(p_(1)^(i))/(i!Deltax_(1)^(n-i))](x-x_(1))^(n)P(x)=u_{1}+\sum_{i=1}^{n-1} \frac{p_{1}^{i}\left(x-x_{1}\right)^{i}}{i!}+\left[\frac{u_{2}-u_{1}}{\Delta x_{1}^{n}}-\sum_{i=1}^{n-1} \frac{p_{1}^{i}}{i!\Delta x_{1}^{n-i}}\right]\left(x-x_{1}\right)^{n}
If we now write that these polynomials satisfy conditions (9), we successively obtain relations (10).
Sufficiency. If between p_(0)^(k),p_(1)^(k),k=1,2,dots,n-1,u_(0),u_(1)p_{0}^{k}, p_{1}^{k}, k=1,2, \ldots, n-1, u_{0}, u_{1}, there are relations (10), so we verify directly by calculation that the polynomials (12) satisfy the relations (9).
Consequence. If the values (1) are given, then there is a unique system of values
p_(i)^(j),i= bar(1),m- bar(1),j= bar(1,n-1)p_{i}^{j}, i=\overline{1}, m-\overline{1}, j=\overline{1, n-1}
which with the values (1) unambiguously determine a connected polynomial of the order n-1n-1, which satisfies the conditions (3).
Values p_(i)^(j),i=1,m-1,j= bar(1,n-1)p_{i}^{j}, i=1, m-1, j=\overline{1, n-1} are given by the following recurrence formulas:
{:[(13)p_(i+1)^(j)=sum_(k=0)^(n-j-1)p_(i)^(j+k)(Deltax_(i)^(k))/(k!)+A_(i)prod_(k=n-j+1)^(n)k*Deltax_(i)^(n-j)],[j=1","2","dots n-1","i=0","1","dots","m-2]:}\begin{align*}
p_{i+1}^{j} & =\sum_{k=0}^{n-j-1} p_{i}^{j+k} \frac{\Delta x_{i}^{k}}{k!}+A_{i} \prod_{k=n-j+1}^{n} k \cdot \Delta x_{i}^{n-j} \tag{13}\\
j & =1,2, \ldots n-1, i=0,1, \ldots, m-2
\end{align*}
where
A_(i)=(u_(i+1)-u_(i))/(Deltax_(i)^(n))-sum_(k=1)^(n-1)(p_(i)^(k))/(k!Deltax^(n-k)),i= bar(0,m-2)A_{i}=\frac{u_{i+1}-u_{i}}{\Delta x_{i}^{n}}-\sum_{k=1}^{n-1} \frac{p_{i}^{k}}{k!\Delta x^{n-k}}, i=\overline{0, m-2}
and
Deltax_(i)=x_(i+1)-x_(i),i= bar(0,m-2)\Delta x_{i}=x_{i+1}-x_{i}, i=\overline{0, m-2}
From lemnes 1 and 2 the following theorem follows:
THEORÈA I_(i)\mathrm{I}_{\mathrm{i}}. If the values (1) are given, then the function f(x)f(x) corresponds to a single connected polynomial of order n-1n-1 which takes these values from the nodes x_(i),i=0,mx_{i}, i=0, m.
THEORÈA I_(i)\mathrm{I}_{\mathrm{i}}. If the values (1) are given, then the function f(x)f(x) corresponds to a single connected polynomial of order n-1n-1 which takes these values from the nodes x_(i),i=0,mx_{i}, i=0, m.
Let us designate by S_(n)(U,P)S_{n}(U, P) the linear space of all connected polynomials of order n-1n-1 of the interval [x_(0),x_(m)]\left[x_{0}, x_{m}\right]. We have the following consequence:
Consequence. Space S_(n)(U,P)S_{n}(U, P) is a linear space of dimension m+nm+n.
Demonstration. Theorem 1 corresponds to each vector
(u_(0),dots,u_(m),p_(0)^(1),dots,p_(0)^(n-1))\left(u_{0}, \ldots, u_{m}, p_{0}^{1}, \ldots, p_{0}^{n-1}\right)
a connected polynomial determined without ambiquity u(x)inS_(n)(U,P)u(x) \in S_{n}(U, P).
Conversely, the equalities (1) cause that each polynomial U(x)inS_(n)(U,P)U(x) \in S_{n}(U, P) corresponds to a single vector
Conversely, the equalities (1) cause that each polynomial U(x)inS_(n)(U,P)U(x) \in S_{n}(U, P) corresponds to a single vector
(U_(0),dots,U_(m),p_(0)^(1),dots,p_(0)^(n-1))\left(U_{0}, \ldots, U_{m}, p_{0}^{1}, \ldots, p_{0}^{n-1}\right)
Lemma 2 and its consequence provide a practical procedure for calculating the approximate value of the function f(x)f(x) at each point,
bar(x)in[a,b],quad bar(x)!=x_(i),quad i= bar(0,m)\bar{x} \in[a, b], \quad \bar{x} \neq x_{i}, \quad i=\overline{0, m}
if we give the values (1).
If u(x)u(x) is the connected polynomial of order n-1n-1 which satisfies conditions (3) then we mean by its approximate value of the function f(x)f(x) in the point bar(x)\bar{x} The value of the polynomial u(x)u(x) in the point bar(x)\bar{x} and write f(x)≃u(x)f(x) \simeq u(x).
If u(x)u(x) is the connected polynomial of order n-1n-1 which satisfies conditions (3) then we mean by its approximate value of the function f(x)f(x) in the point bar(x)\bar{x} The value of the polynomial u(x)u(x) in the point bar(x)\bar{x} and write f(x)≃u(x)f(x) \simeq u(x).
For the determination of the polynomial U(x)U(x) we proceed as
follows: Either x_(k) < x < x_(k+1)x_{k}<x<x_{k+1}. Now using the recurrence formulas (13) we successively calculate the values:
follows: Either x_(k) < x < x_(k+1)x_{k}<x<x_{k+1}. Now using the recurrence formulas (13) we successively calculate the values:
p_(1)^(j),p_(2)^(j),dots,p_(k-1)^(j),p_(k)^(j),j= bar(1,n-1)p_{1}^{j}, p_{2}^{j}, \ldots, p_{k-1}^{j}, p_{k}^{j}, j=\overline{1, n-1}
The polynomial U(x)U(x) for x_(k) < x < x_(k+1)x_{k}<x<x_{k+1} then takes the following form:
{:(14)U(x)=u_(k)+sum_(i=1)^(n-1)(p_(k)^(i))/(i!)(x-x_(k))^(i)+A_(k)(x-x_(k))^(n):}\begin{equation*}
U(x)=u_{k}+\sum_{i=1}^{n-1} \frac{p_{k}^{i}}{i!}\left(x-x_{k}\right)^{i}+A_{k}\left(x-x_{k}\right)^{n} \tag{14}
\end{equation*}
where
A_(k)=(u_(k+1)-u_(k))/(Deltax_(k)^(n))-sum_(i=1)^(n-1)(p_(k)^(i))/(i!Deltax_(k)^(n-i))A_{k}=\frac{u_{k+1}-u_{k}}{\Delta x_{k}^{n}}-\sum_{i=1}^{n-1} \frac{p_{k}^{i}}{i!\Delta x_{k}^{n-i}}
and
Deltax_(k)=x_(k+1)-x_(k)\Delta x_{k}=x_{k+1}-x_{k}
Calculation of the coefficients of the polynomial U(x)U(x) for
x_(k) < x < x_(k+1)k= bar(1,m)x_{k}<x<x_{k+1} k=\overline{1, m}
As we can see, is easily algorithmizable, so the results can be obtained simply with the help of a numerical electronic computing machine.
BIBLIOGRAPHY
[1] Boor Car1 (de), Bicubic spline interpolation. Journal of Mathematics and Physics. 41, 3 (1962).
[2] Березин И. С., Жидков Н. П, Методы вышислении. Государственное издательство Физико-математематическои Литературы, Москва, 1959. Received on the 19th. XI. 1963
[2] Березин И. С., Жидков Н. П, Методы вышислении. Государственное издательство Физико-математематическои Литературы, Москва, 1959. Received on the 19th. XI. 1963