=Paper=
{{Paper
|id=Vol-2472/p6
|storemode=property
|title=Analysis of the degree of polynomials in the interpolation problem
|pdfUrl=https://ceur-ws.org/Vol-2472/p6.pdf
|volume=Vol-2472
|authors=Alicja Winnicka
}}
==Analysis of the degree of polynomials in the interpolation problem==
https://ceur-ws.org/Vol-2472/p6.pdf
Analysis of the degree of polynomials
in the interpolation problem
Alicja Winnicka
Institute of Mathematics
Silesian University of Technology
Kaszubska 23, 44-100 Gliwice, Poland
Email: Alicja.Lidia.Winnicka@gmail.com
Abstract—Interpolation is a tool based on finding a specific Let us assume, that polynomial w(x) has a following
function that passes through certain points. This issue is impor- formula
tant from the point of view of applications in data processing,
and in particular finding a curve showing some initial conditions. w(x) = an xn + an−1 xn−1 + ... + a2 x2 + a1 x + a0 (1)
In this work, interpolation with multitude of different degrees is
analyzed due to their advantages and disadvantages. Rememebring that w(xi ) = yi we can write the system of
equations
I. I NTRODUCTION
an xn0 + an−1 xn−1
0 + ... + a1 x0 + a0 = y0
Mathematics gave the backbone to many fields of science,
n n−1
an x1 + an−1 x1 + ... + a1 x1 + a0 = y1
in particular to computer science. A large number of more
... .
and more complex algorithms or applications is based on the
an xnn−1 + an−1 xn−1
+ ... + a x + a = y
determination of specific elements. To this end, a numerical
n−1 1 n−1 0 n−1
a x n + a
n−1
approach is used that the computer is able to perform. How- n n n−1 xn + ... + a1 xn + a0 = yn
ever, this approach means approximation, since it is not always (2)
possible to accurately determine any values for continuous which can be calculated as the system of matrices
functions. The reason is an infinite set of values. x0 xn−1 xn−2
n
0 0 ... x0 1 an y0
The approximation of results is a very important aspect, xn xn−1 xn−2 ... x1 1 an−1 y1
1 1 1 = (3)
above all in biometry. In [1], the authors used curve approxi-
... ... ... ... ... ... ... ...
mation to modify the set of points representing the signature. xnn xn−1 xnn−2 ... xn 1 a0 yn
n
Again in [2], the idea of using interpolation was used for
We have to find coefficients a0 , a1 ,...,an , but the condition
the purpose of verification of security protocols. Another
number of this matrix may be large. Additionaly number of
area where approximation is used is feature extraction [3]
equations may cause difficulty in calculating it fast enough.
and classification [4]. In addition, this type of mathematical
In due to it, the simpler method was created – writing the
operations are used in the process of creating rules for fuzzy
polynomial as Lagrange’s polynomial.
systems [5]. In this paper, we analyze different degrees of
polynomials in the interpolation process. A. Lagrange’s Polynomial
The Lagrange’s polynomial is a easier way to find searched
II. P OLYNOMIAL I NTERPOLATION
polynomial of the function. Instead of calculating a system
Polynomial interpolation is a method in numerical analysis, of equation or matrices, we must find the polynomial using
which purpose is to find the polynomial approximated to the specific formula
original function. The interpolation works, when we have a n n
set of points x0 , x1 ,..., xn , which are called nodes and their X Y x − xj
w(x) = yi (4)
values y0 , y1 ,...,yn . The searched polynomial must satisfied i=0
xi − xj
j=0∧j6=i
a few requirements: its degree must be smaller or equal to
(n − 1) and points (xi , yi ) must belong to it. It means, that Values yi can be replaced with values of function our f (xi )
w(x0 ) = y0 , w(x1 ) = y1 ,..., w(xn ) = yn and it will be an and then polynomial will have following formula
approximation of searched function. n n
X Y x − xj
Interpolation is usually used in the situation, when we have w(x) = f (xi ) (5)
a certain number of measurements, for example in physics i=0
xi − xj
j=0∧j6=i
experiment, and we have to find an approximated function for and w(x) will be an approximation of function f (x) and will
them. have common points in x0 , x1 ,..., xn .
c 2019 for this paper by its authors. Use permitted under Creative Com- The Alg. 1 shows the pseudocode of finding the Lagrange’s
mons License Attribution 4.0 International (CC BY 4.0). polynomial for any number of nodes n.
27
Figure 1: Two functions with their polynomial interpolations for various n.
Figure 2: The function, which shows us the problem called Runge’s phenomenon.
28
Data: Given set of points x0 , x1 , ..., xn and values in sin(x) five nodes was enough. The found polynomial has a
these points y0 , y1 , ..., yn following formula
Result: The polynomial w approximated to the
original function
Start; w(x) = 0.99x + 0.05x2 − 0.23x3 + 0.04x4 (8)
w(x) = 0;
i = 0; and covers the original function on the graph.
j = 0; Second analyzed function is g(x), which is third degree
for i ≤ n do polynomial. In this way we can say, that for n = 4 it will
Φ = 1; find precisely the same polynomial as g(x). However it finds
for j ≤ i − 1 do a little different polynomial showed on Eq.9.
x−x
Φ = Φ xi −xjj ;
w(x) = −3−6.710−16z +2x2 +3.610−15 x3 +8.810−16 x4 +x5
j + +;
(9)
end
for i + 1 ≤ j ≤ n do We can see, that coefficients for x3 and x4 are very close to
x−x be 0. In this case if indeed they would equal zero, we would
Φ = Φ xi −xjj ;
get the function g(x). Similar to previous function f (x), the
j + +; third degree polynomial w(x) covers original function on the
end graph.
w = w + yi Φ;
The above results suggest us, that for the bigger number of
i + +;
the nodes we will get polynomial, which is more approximated
end
to original function. However with bigger n, the calculating
Return w as found polynomial;
last longer and becomes less effective.
Stop; 1
Algorithm 1: Polynomial interpolation algorithm. The third function h(x) = 1+0.08x 2 is moe complicated,
because it shows us the problem called Runge’s phenomenon.
It is happening for the functions, where our nodes are equidis-
B. Error of polynomial interpolation tant. Then with increasing the degree of polynomial, quality
of interpolation increases, but after a while rapidly deacreases.
All of approximation methods are determined by an error
It is the most visible at the end of the interval, in this case
dependent on the features of the method. For the polynomial
[−20, 20]. The Fig. 2 shows the effect of eqidistant nodes.
interpolation method, when we have function f : [a, b] → R
We can see, that each one graph for increased degree is less
and its approximated polynomial calculated on set od nodes
effective atthe ends of interval. It is the most visible for tenth
x0 , x1 ,...,xn , the error have the following formula
degree (red color), where difference between polynomial and
original function h(x) is huge.
Mn
f (x) − w(x) = (x − x0 )(x − x1 )...(x − xn ) (6) To prevent increasing of this error, we should find another
n! nodes, which will be concetrated at the ends of interval. For
where Mn is determined by the formula: this function we used two set of nodes to find tenth degree
Mn = sup|f (n) (x)| (7) polynomial:
(n)
and f (x) means n-th derivative of f (x). xi = −20, −16, −12, −8, −4, 0, 4, 8, 12, 16, 20 (10)
III. E XPERIMENTS
and
To find the difference for various n and xi , we compared
polynomials for three functions: x1 = −20, −19, −17, −15, −10, −5, 0, 5, 10, 15, 17, 19, 20
• f (x) = sin(x) ∈ [0, π], (11)
5 2
• g(x) = x + 2x − 3 ∈ [−1, 1], where the first one shows us the Runge’s phenomenon and
1
• h(x) = 1+0.08x2 ∈ [−20, 20]. the other is to reduce difference between function and its
For each of them we used another interval and nodes to polynomial. Comparision of both polynomials is shown on
show additional features of Lagrange’s interpolation. For the Fig.3.
trigonometric function f (x) = sin(x) we found the second, Increasing density of nodes at the ends of the interval causes
third, fourth and fifth degree polynomial. The effect was aproaching the polynomial to the original function, but it also
showed on Fig.1. We can see on the graph, that the second caused less effectivness for values about [−10, −5] and [5, 10].
degree polynomial, linear function, is not visible. This is due To reduce these errors we should find more nodes in this
to our interval and nodes (x0 = 0 and x1 = π) and their interval and calculate a polynomial with the bigger degree.
values, which are 0. Because it is linear function, it found the However, the calculations will last longer because of bigger set
polynomial w(x) = 0. For a quite accurate approximation of of data, which will decrease effectiveness of the interpolation.
29
Figure 3: Two different set of nodes for the same function h(x).
IV. C ONCLUSION
In this paper we compared the degree of polynomials in
polynomial interpolation. This is accurate method for function,
which are similar to polynomials and usually the better result
is given for the bigger number of nodes. Howevere with
increasing number of nodes and degree of polynomial, the
time for calculations increases too.
R EFERENCES
[1] D. Połap and M. Woźniak, “Flexible neural network architecture for
handwritten signatures recognition,” International Journal of Electronics
and Telecommunications, vol. 62, no. 2, pp. 197–202, 2016.
[2] M. Rocchetto, L. Viganò, and M. Volpe, “An interpolation-based method
for the verification of security protocols,” Journal of Computer Security,
vol. 25, no. 6, pp. 463–510, 2017.
[3] P. Upchurch, J. Gardner, G. Pleiss, R. Pless, N. Snavely, K. Bala, and
K. Weinberger, “Deep feature interpolation for image content changes,”
in Proceedings of the IEEE conference on computer vision and pattern
recognition, 2017, pp. 7064–7073.
[4] S. Niklaus, L. Mai, and F. Liu, “Video frame interpolation via adaptive
convolution,” in Proceedings of the IEEE Conference on Computer Vision
and Pattern Recognition, 2017, pp. 670–679.
[5] L. Yang, F. Chao, and Q. Shen, “Generalized adaptive fuzzy rule
interpolation,” IEEE Transactions on Fuzzy Systems, vol. 25, no. 4, pp.
839–853, 2016.
[6] R. Damaševičius, C. Napoli, T. Sidekerskienė, and M. Woźniak, “Imf
mode demixing in emd for jitter analysis,” Journal of Computational
Science, vol. 22, pp. 240–252, 2017.
[7] M. Wozniak, C. Napoli, E. Tramontana, G. Capizzi, G. L. Sciuto, R. K.
Nowicki, and J. T. Starczewski, “A multiscale image compressor with
rbfnn and discrete wavelet decomposition,” in 2015 International Joint
Conference on Neural Networks (IJCNN). IEEE, 2015, pp. 1–7.
30