The document Methods of Interpolation - Interpolation and Extrapolation, Business Mathematics and Statistics B Com Notes | EduRev is a part of the B Com Course Business Mathematics and Statistics.

All you need of B Com at this link: B Com

**Introduction **

We discuss here a number of interpolation methods that we commonly nd in computer graphics and geometric modeling. Interpolation means to calculate a point or several points between two given points. For a given sequence of points, this means to estimate a curve that passes through every single point.

**Linear Interpolation**

Linear interpolation is the simplest interpolation method. Applying linear interpolation to a sequence of points results in a polygonal line where each straight line segment connects two consecutive points of the sequence. Therefore, every segment (P; Q) is interpolated independently as follows:

P (t) = (1 t) :P + t :Q (1)

where t ∈ [0; 1]. By varying t from 0 to 1 we get all the intermediate points between P and Q. Note that P (t) = P for t = 0 and P (t) = Q for t = 1. For values of t < 0 and t > 1 result in extrapolation, that is, we get points on the line dened by P , Q, but outside the segment (P; Q).

**Cosine Interpolation**

As shown in Fig. ??, the curve resulting from Linear interpolation has discontinuities at each point. In certain circumstances, we need a smoother interpolating function, that is a function that allows for a smooth transition between consecutive segments. The cosine interpolation carries out a transition that looks smooth, though every segment is interpolated independently .

**Cubic Interpolation**

...

**Hermite Interpolation**

...

Linear Interpolation Let us now dene linear interpolation in more mathematical terms.

**Denition 1**. A linear interpolation is an affine transformation from an unit interval [0; 1] to a straight line segment in R^{n} , where f_{1} (t); : : : ; f_{n} (t) are the function components of f along each coordinate axis.

See Lecture 1 for more details on affine transformations. By denition, an affine transformation preserves barycentric combinations. Therefore, if t ∈ [0; 1] is dened as a barycentric combination of the points 0; 1 ∈ R

t = α_{0} :0 + α_{1} :1; with α_{0} + α_{1} = 1

then,

with α_{0} = 1 - t and α_{1} = t. This is illustrated in Fig.??, where we intuitively see that the linear interpolation preserves the ratio

**Linear Interpolation and Barycentric Coordinates**

Let us rst see the relation between collinearity and barycentric coordinates. Let P_{0} , P , P_{1} be three collinear points in R^{3} . Then, P is the barycentric combination of P_{1} and P_{2 }given as follows:

where α_{0} and α_{1} are the barycentric coordinates of P with respect to P_{0} and P_{1} , that is

where D(; ) denotes the signed Euclidean distance between two points.

We are now at a position that allows to show that the linear interpolation is given by Eq. (1). Taking into consideration the above expressions for α_{0} and α_{1} , and the fact that a linear interpolation preserves barycentric coordinates, we have:

where

that is,

P (t) = (1 t) :P_{0} + t :P_{1}

**Linear Interpolation and Geometric Ratios **

By de nition, the ratio of three collinear points P_{0} , P , and P_{1} is given by

Taking into account the expressions of the barycentric coordinates α_{0} , 1 given above, we have

We know that an affine transformation f : [0; 1] → R^{n} preserves barycentric coordinates; as a consequence, the ratio of barycentric coordinates is also preserved. Therefore, r(P_{0} ; P; P_{1} ) remains unchanged by affine transformations, that is,

In short, an affine transformation preserves the geometric ratio of collinear points, that is, the image of a straight line segment is a straight line segment.

**Linear Interpolation over [a; b] **

The interval [a; b] can be obtained from the affine transformation of the interval [0; 1]. With t ∈ [0; 1] and u∈ [a; b], this affine trnsformation is given by

so, replacing the expression of t into

P (t) = (1 t)P_{0} + tP_{1}

we have

Because a; u; b and 0; t; 1 have the same geometric ratio as P_{0} ; P; P_{1} , we end up showing that the linear interpolation is invariant under affine domain mappings. By affine domain mapping we mean an affine transformation from the real line to itself.

**Piecewise Linear Interpolation**

Piecewise linear interpolation involves not two points but a sequence of points P_{0} ; P_{1} ; : : : ; P_{N} ∈ R^{n} such that a linear interpolation is applied to two consecutive points of this sequence. The result is a polyline P, called piecewise linear interpolant of all points P_{0} ; P_{1} ; : : : ; P_{N} . This is illustrated in FIg. ??, where we determine a point in each segment for every t ∈ [0; 1].

If the points P_{0} ; P_{1} ; : : : ; P_{N} are on a curve C , we say that the resulting polyline P is a piecewise linear interpolant of the curve C ; symbolically, we write P = P(C ).

The piecewise linear interpolation enjoys two properties, as described in the sequel.

**Property L4.1 (affine Invariance ) **

If a curve C is sub ject to an affine transformation f , then a piecewise linear interpolant of f (C ) is an affine transformation of the original piecewise linear interpolant, that is,

P(f (C )) = f (P(C ))

**Property L4.2 (Variance Diminishing ) **

Let P(C ) be a piecewise linear interpolant of the curve C , and π an arbitrary hyperplane that intersects both C and P(C ). Then, we have

that is, the number of intersection points between the plane and the interpolant is less or equal to the number of points resulting from the intersection between and the curve.

This is so because, unlike a straight line segment of the interpolant, the curve segment passing through the two endpoints of such a straight line segment is not necessarily convex.

**The Menelaus Theorem **

Let us now have a look at an important theorem in the context of piecewise linear interpolation.

**Theorem 2.** Let A; B ; C ∈ R^{2} be three points dening two straight lines that meet at B , and D; E ; F points in the lines dened by (B ; C ), (A; C ), and (A; B ), respectively, each one of which is distinct from the vertices of the triangle ΔAB C . Then, the points D; E ; F are said to be collinear if and only if

**Proof** Let us consider the piecewise linear interpolant of the points P_{0} ; P_{1} ; P_{2} . Let us apply the same linear interpolation to two points t; u ∈ [0; 1] ⊂ R in a way we get two image points P (t); P (u) in the straight line segment (P_{0} ; P_{1} ), and other two image points Q(t); Q(u) in the straight line segment (P_{1} ; P_{2} ) in R_{2} , as illustrated in Fig. ??.

We intend to prove that

For that purpose, we have only to determine the unknown third ratio , that is, we have to determine the barycentric coordinates of P . Taking into account that P is a barycentric combination of both straight line segments (P (u); Q(u)) and (P (t); Q(t)), we have

(2)

Now, let us substitute the expressions of

and

into (7) so that we get

(3)

By combining (7) and ((3)), we have

(4)

that is,

(5)

or, equivalently,

(6)

Substituting these barycentric coordinates in (7), we obtain

(7)

Finally, we can write down

**Repeated Linear Interpolation**

Let us now see how repeated linear interpolation allows for a procedure to construct parabolas. As we will see in lectures to come, the generalization of this procedure leads us to the construction of B'ezier curves.

So, let P_{0} ; P_{1} ; P_{2} be three points in R^{2} . Using piecewise linear interpolation, we determine two points for a given t ∈ R, one in the straight line dened by (P_{0} ; P_{1} ) and another dened by (P_{1} ; P_{2} ), as follows:

(8)

where the exponent 1 indicates the degree of the polynomial. By applying the same linear interpolation at t ∈ R to the new segment , we have

(9)

Substituting the expressions of given by (8) into (9), we obtain

(10)

which is a degree-2 polynomial representing a parabola. This construction procedure for parabolas uses repeated linear interpolation.

**Property L4.3 (Convex Hull ) **

The construction of a parabola using repeated linear interpolation enjoys the following the convex hull property, because

**Property L4.4 (Affine Invariance )**

Taking into consideration the ratios

we conclude that the above construction of a parabola is invariant under affine transformations because the piecewise linear interpolation is affine invariant.

122 videos|142 docs

### Binomial Expansion - Interpolation and Extrapolation, Business Mathematics and Statistics

- Video | 09:41 min
### Binomial Expansion - Interpolation and Extrapolation, Business Mathematics and Statistics

- Doc | 7 pages
### Methods of Extrapolation - Interpolation and Extrapolation, Business Mathematics and Statistics

- Doc | 2 pages
### Newton's Interpolation - Interpolation and Extrapolation, Business Mathematics and Statistics

- Doc | 5 pages
### Lagrange Interpolation Method - Business Mathematics and Statistics

- Video | 05:20 min