-Interpolation is a tool based on finding a specific function that passes through certain points. This issue is important from the point of view of applications in data processing, and in particular finding a curve showing some initial conditions. In this work, interpolation with multitude of different degrees is analyzed due to their advantages and disadvantages.
Mathematics gave the backbone to many fields of science, in particular to computer science. A large number of more and more complex algorithms or applications is based on the determination of specific elements. To this end, a numerical approach is used that the computer is able to perform. However, this approach means approximation, since it is not always possible to accurately determine any values for continuous functions. The reason is an infinite set of values.
The approximation of results is a very important aspect, above all in biometry. In [1], the authors used curve approximation to modify the set of points representing the signature. Again in [2], the idea of using interpolation was used for the purpose of verification of security protocols. Another area where approximation is used is feature extraction [3] and classification [4]. In addition, this type of mathematical operations are used in the process of creating rules for fuzzy systems [5]. In this paper, we analyze different degrees of polynomials in the interpolation process.
Polynomial interpolation is a method in numerical analysis, which purpose is to find the polynomial approximated to the original function. The interpolation works, when we have a set of points x0, x1,..., xn, which are called nodes and their values y0, y1,...,yn. The searched polynomial must satisfied a few requirements: its degree must be smaller or equal to (n 1) and points (xi; yi) must belong to it. It means, that w(x0) = y0, w(x1) = y1,..., w(xn) = yn and it will be an approximation of searched function.
Interpolation is usually used in the situation, when we have a certain number of measurements, for example in physics experiment, and we have to find an approximated function for them.
c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Let us assume, that polynomial w(x) has a following
formula
w(x) = anxn + an 1xn 1 + ::: + a2x2 + a1x + a0
(
A. Lagrange’s Polynomial
The Lagrange’s polynomial is a easier way to find searched
polynomial of the function. Instead of calculating a system
of equation or matrices, we must find the polynomial using
specific formula
(
x j=0^j6=i xi xj xj w(x) = n X f (xi) i=0 n Y
x
j=0^j6=i xi
xj
xj
(
All of approximation methods are determined by an error dependent on the features of the method. For the polynomial interpolation method, when we have function f : [a; b] ! R and its approximated polynomial calculated on set od nodes x0, x1,...,xn, the error have the following formula f (x) w(x) = Mn (x x0)(x
n! where Mn is determined by the formula: x1):::(x xn) and f (n)(x) means n-th derivative of f (x).
Mn = supjf (n)(x)j
To find the difference for various n and xi, we compared polynomials for three functions: f (x) = sin(x) 2 [0; ], g(x) = x5 + 2x2 3 2 [ 1; 1], h(x) = 1+0:108x2 2 [ 20; 20].
For each of them we used another interval and nodes to
show additional features of Lagrange’s interpolation. For the
trigonometric function f (x) = sin(x) we found the second,
third, fourth and fifth degree polynomial. The effect was
showed on Fig.1. We can see on the graph, that the second
degree polynomial, linear function, is not visible. This is due
to our interval and nodes (x0 = 0 and x1 = ) and their
values, which are 0. Because it is linear function, it found the
polynomial w(x) = 0. For a quite accurate approximation of
(
Second analyzed function is g(x), which is third degree polynomial. In this way we can say, that for n = 4 it will find precisely the same polynomial as g(x). However it finds a little different polynomial showed on Eq.9. w(x) = 3 6:710 16z +2x2 +3:610 15x3 +8:810 16x4 +x5 (9)
We can see, that coefficients for x3 and x4 are very close to be 0. In this case if indeed they would equal zero, we would get the function g(x). Similar to previous function f (x), the third degree polynomial w(x) covers original function on the graph.
The above results suggest us, that for the bigger number of the nodes we will get polynomial, which is more approximated to original function. However with bigger n, the calculating last longer and becomes less effective.
The third function h(x) = 1+0:108x2 is moe complicated, because it shows us the problem called Runge’s phenomenon. It is happening for the functions, where our nodes are equidistant. Then with increasing the degree of polynomial, quality of interpolation increases, but after a while rapidly deacreases. It is the most visible at the end of the interval, in this case [ 20; 20]. The Fig. 2 shows the effect of eqidistant nodes. We can see, that each one graph for increased degree is less effective atthe ends of interval. It is the most visible for tenth degree (red color), where difference between polynomial and original function h(x) is huge.
To prevent increasing of this error, we should find another nodes, which will be concetrated at the ends of interval. For this function we used two set of nodes to find tenth degree polynomial: xi = 20; 16; 12; 8; 4; 0; 4; 8; 12; 16; 20 (10) and x1 = 20; 19; 17; 15; 10; 5; 0; 5; 10; 15; 17; 19; 20 (11) where the first one shows us the Runge’s phenomenon and the other is to reduce difference between function and its polynomial. Comparision of both polynomials is shown on Fig.3.
Increasing density of nodes at the ends of the interval causes aproaching the polynomial to the original function, but it also caused less effectivness for values about [ 10; 5] and [5; 10]. To reduce these errors we should find more nodes in this interval and calculate a polynomial with the bigger degree. However, the calculations will last longer because of bigger set of data, which will decrease effectiveness of the interpolation.
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.