Interpolation & Curve Fitting: Methods, Errors & Applications

TAKEAWAYS:

• Interpolation approximates unknown values between known data points using polynomials (Lagrange, Newton) or splines.
• Curve fitting minimizes error between data and a model (linear, polynomial, exponential) via least squares.
• Error analysis compares exact vs. approximate solutions (truncation, rounding errors).
• Spline methods (cubic, B-splines) balance smoothness and accuracy for complex datasets.
• Real-world uses: Traffic route optimization (NTC), sensor calibration (industrial IoT), and financial forecasting (NEPSE).
• Exam focus: Derive formulas, compute interpolants, and compare methods for given data.

---

1. Introduction: Why Interpolate?

Interpolation estimates values between known data points. For example:

• Traffic engineers predict vehicle speeds at unmeasured times using speed vs. time data.
• Finance apps (e.g., NEPSE) estimate stock prices between recorded trades.
• Medical devices (e.g., ECG sensors) reconstruct heartbeats from sampled signals.

Key Idea: Given $n+1$ points $(x_i,y_i)$, find a function $P(x)$ such that $P(x_i)=y_i$.

---

---

2. Polynomial Interpolation Methods

A. Lagrange Interpolation

Definition: Constructs a polynomial $P_n(x)$ of degree $n$ passing through all $n+1$ points: $$P_n(x)=\sum _{i=0}^n{y}_i\cdot L_i(x),L_i(x)=\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^n\frac{x-x_j}{x_i-x_j}$$

Worked Example 1: Find displacement at $t=1.3$ s and $t=1.5$ s for the table:

Steps:

1. Lagrange Basis Polynomials: For $t=1.3$, compute $L_0(t),L_1(t),\dots ,L_4(t)$ and sum: $$P_4(1.3)=0.0\cdot L_0(1.3)+1.2\cdot L_1(1.3)+2.8\cdot L_2(1.3)+4.8\cdot L_3(1.3)+7.2\cdot L_4(1.3)$$
2. Calculate $L_i(1.3)$:
   • $L_1(1.3)=\frac{(1.3-0)(1.3-1)(1.3-1.5)(1.3-2)}{(0.5-0)(0.5-1)(0.5-1.5)(0.5-2)}\approx 0.125$
   • Similarly compute others (use a calculator for precision).
3. Sum: $$P_4(1.3)\approx 1.2\times 0.125+2.8\times 0.375+4.8\times 0.375+7.2\times 0.125=3.6\text{ cm}$$ Repeat for $t=1.5$: $P_4(1.5)=4.8$ cm (exact, since $t=1.5$ is a data point).

Visualization:

Advantages:

• Exact for given data points.
• Simple to derive for small $n$.

Disadvantages:

• High-degree polynomials oscillate (Runge’s phenomenon).
• Computationally expensive for large $n$.

---

B. Newton’s Divided Differences

Definition: Uses divided differences to build a polynomial incrementally: $$P_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\dots$$ where $f[x_i,\dots ,x_{i+k}]$ are divided differences.

Worked Example 2: Recompute $P_4(1.3)$ using Newton’s method.

Steps:

1. Divided Differences Table:

   $t$	$f(t)$	$f[\cdot ,t]$	$f[\cdot ,\cdot ,t]$	$f[\cdot ,\cdot ,\cdot ,t]$	$f[\cdot ,\cdot ,\cdot ,\cdot ,t]$
   0.0	0.0
   0.5	1.2	2.4
   1.0	2.8	3.2	1.6
   1.5	4.8	4.8	3.2	3.2
   2.0	7.2		4.8	4.8	3.2

2. Polynomial: $$P_4(t)=0.0+2.4(t-0.0)+1.6(t-0.0)(t-0.5)+3.2(t-0.0)(t-0.5)(t-1.0)+3.2(t-0.0)(t-0.5)(t-1.0)(t-1.5)$$

3. Evaluate at $t=1.3$: Substitute and compute (use Horner’s method for efficiency): $$P_4(1.3)\approx 3.6\text{ cm}(\text{same as Lagrange})$$

Advantages:

• Efficient for adding new data points (incremental).
• Avoids recomputing the entire polynomial.

Disadvantages:

• Still suffers from high-degree oscillations.

---

---

3. Error Analysis

Interpolation Error: For a function $f(x)$, the error $E(x)=f(x)-P_n(x)$ is: $$E(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\prod _{i=0}^n(x-x_i),\xi \in (a,b)$$ Key Insight: Error depends on:

1. The derivative $f^{(n+1)}(\xi )$ (higher derivatives = larger error).
2. The spacing of $x_i$ (uneven spacing increases error).

Example: For $f(x)=e^x$ interpolated at $x=0,1,2$, the error at $x=1.5$ is: $$E(1.5)=\frac{e^{\xi }}{6}(1.5)(0.5)(-0.5)(-1.5),\xi \in (0,2)$$ Since $e^{\xi }\le e^2\approx 7.39$, $|E(1.5)|\le 0.31$.

---

---

4. Spline Interpolation

Problem: Polynomial interpolation fails for large $n$ due to oscillations. Solution: Use piecewise polynomials (splines).

A. Cubic Splines

Definition: A piecewise cubic polynomial $S(x)$ where:

1. $S(x_i)=y_i$ for all $i$.
2. $S^{\prime }(x_i)$ and $S^{\prime \prime }(x_i)$ are continuous.
3. $S^{\prime \prime \prime }(x)=0$ on each subinterval $[x_i,x_{i+1}]$.

Natural Spline: $S^{\prime \prime }(x_0)=S^{\prime \prime }(x_n)=0$.

Worked Example 3: Fit a cubic spline to the displacement data.

Steps:

1. Set up equations for continuity and smoothness: $$S_i(x)=a_i+b_i(x-x_i)+c_i(x-x_i{)}^2+d_i(x-x_i{)}^3,x\in [x_i,x_{i+1}]$$
2. Boundary conditions:
   • $S^{\prime \prime }(0)=0$, $S^{\prime \prime }(2)=0$.
3. Solve for coefficients (use matrix methods or software).

Advantages:

• Smoother than high-degree polynomials.
• Local control (changing one point only affects nearby segments).

Disadvantages:

• More complex to compute than Lagrange/Newton.

---

---

5. Curve Fitting (Least Squares)

Problem: Data has noise; interpolation overfits. Solution: Find a function $f(x)$ that minimizes the sum of squared errors: $$\underset{a_0,\dots ,a_n}{\min }\sum _{i=1}^m[y_i-(a_0+a_1{x}_i+\cdots +a_n{x}_i^n){]}^2$$

A. Linear Least Squares

For $f(x)=a_0+a_{1}x$, solve: $$\left[\begin{array}{c}{a}_0\\ a_1\end{array}\right]={\left[\begin{array}{cc}\sum x_i^2& \sum x_i\\ \sum x_i& n\end{array}\right]}^{-1}\left[\begin{array}{c}\sum x_i{y}_i\\ \sum y_i\end{array}\right]$$

Worked Example 4: Fit a line to noisy displacement data:

Steps:

1. Compute sums: $$\sum x_i=4.0,\sum y_i=15.7,\sum x_i^2=7.75,\sum x_i{y}_i=26.35$$
2. Solve: $$\left[\begin{array}{cc}7.75& 4.0\\ 4.0& 5\end{array}\right]\left[\begin{array}{c}{a}_0\\ a_1\end{array}\right]=\left[\begin{array}{c}26.35\\ 15.7\end{array}\right]$$ $$\Rightarrow a_0=0.1,a_1=3.5$$ So, $f(t)=0.1+3.5t$.

Visualization:

Advantages:

• Robust to noise.
• Works for linear/nonlinear models.

Disadvantages:

• No guarantee of passing through any data point.

---

B. Polynomial Least Squares

Extend to higher-degree polynomials by solving a normal equations system: $${\mathbf{A}}^T\mathbf{Aa}={\mathbf{A}}^T\mathbf{y}$$ where $\mathbf{A}$ is the Vandermonde matrix.

---

---

6. Applications in Engineering

A. Traffic Flow Modeling (NTC)

Problem: Predict vehicle speeds at unmeasured times using speed vs. time data. Method: Cubic splines to smooth speed profiles and avoid oscillations. Example: Given speeds at $t=0,5,10,15$ minutes, fit a spline to estimate speed at $t=7$ minutes.

B. Sensor Calibration (Industrial IoT)

Problem: Calibrate a temperature sensor using known reference points. Method: Polynomial interpolation to map sensor readings to true temperatures. Example: A sensor reads 100, 200, 300 at true temps 20°C, 40°C, 60°C. Interpolate for a reading of 150.

C. Financial Forecasting (NEPSE)

Problem: Estimate stock prices between trading hours. Method: Least squares to fit a trend line to historical closing prices. Example: Fit a line to NEPSE index values at 10 AM, 2 PM, and 4 PM to predict the 1 PM value.

---

---

7. Choosing the Right Method

---

8. Exam Tips

1. Derive Formulas: For Lagrange/Newton, show the general form and steps to compute coefficients.
2. Error Analysis: Always state the error formula $E(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\prod (x-x_i)$.
3. Compare Methods: For a given dataset, justify why splines or least squares are better than polynomials.
4. Numerical Stability: Avoid high-degree polynomials; prefer splines or low-degree fits.
5. Real-World Context: Relate problems to traffic, finance, or sensor data (e.g., "Predict NEPSE index at 1 PM using least squares").
6. Graphs: Always sketch the data points and interpolant/curve fit in your answer.

Common Pitfalls:

• Forgetting to check for oscillations (Runge’s phenomenon).
• Misapplying boundary conditions in splines.
• Ignoring error bounds in interpolation.

---

In the Real World

1. eSewa/Khalti (Digital Payments):

   • Idea Used: Least Squares Curve Fitting
   • How: eSewa’s fraud detection models fit transaction patterns to a curve (e.g., linear or polynomial) to flag anomalies. For example, if a user’s spending jumps from ₹500/day to ₹5000/day, a least-squares fit to their historical data would show this as a 3σ outlier.

2. Pathao (Ride-Hailing):

   • Idea Used: Spline Interpolation
   • How: Pathao’s dynamic pricing algorithm uses cubic splines to estimate demand between pickup locations. For instance, if demand is known at 3 locations (A, B, C) along a route, splines smooth the demand curve to predict prices at intermediate points (e.g., between A and B).

3. NTC (Traffic Management):

   • Idea Used: Polynomial Interpolation + Least Squares
   • How: NTC uses Lagrange interpolation to estimate traffic flow at unmonitored intersections based on sensor data from nearby points. For example, if traffic volume is recorded at 8 AM, 10 AM, and 12 PM, they interpolate the 9 AM volume. Least squares refines this by fitting a trend line to noisy sensor data over weeks.

4. NEPSE (Stock Exchange):

   • Idea Used: Newton’s Divided Differences
   • How: Analysts use Newton’s interpolation to estimate intra-day stock prices. For example, if NEPSE’s index is recorded at 10 AM (1200), 12 PM (1210), and 2 PM (1230), they compute the polynomial to predict the 11 AM value. This helps traders make split-second decisions.

5. Bank Loan Interest Calculation (Nabil, Global IME):

   • Idea Used: Polynomial Curve Fitting
   • How: Banks use least-squares polynomial fits to model interest rate trends. For example, if historical interest rates for 1-year loans are known at 5%, 6%, and 7% for years 2020, 2021, and 2022, they fit a quadratic curve to predict the 2023 rate. This helps in setting competitive loan rates.

---

Worked Example Tied to Real Life

Problem: A Daraz delivery driver records the distance covered (in km) at hourly intervals during a route. Use Newton’s divided differences to estimate the distance covered at t=2.4 hours.

Solution:

1. Divided Differences Table:

   t	f(t)	f[·,t]	f[·,·,t]	f[·,·,·,t]	f[·,·,·,·,t]
   0.0	0.0
   1.0	5.2	5.2
   2.0	9.8	4.6	-0.6
   3.0	14.1	4.3	0.1	0.7
   4.0	18.7	4.6	0.3	0.2	-0.5

2. Newton Polynomial: $$P_4(t)=0.0+5.2(t)-0.6(t)(t-1)+0.7(t)(t-1)(t-2)-0.5(t)(t-1)(t-2)(t-3)$$

3. Evaluate at t=2.4: $$P_4(2.4)=5.2(2.4)-0.6(2.4)(1.4)+0.7(2.4)(1.4)(0.4)-0.5(2.4)(1.4)(0.4)(-0.6)\approx 12.8\text{ km}$$ Interpretation: The driver has covered approximately 12.8 km after 2.4 hours.

Visualization: