Numerical Method · Unit 2 · 8 hrs
Interpolation and Regression
Exam-focused notes for Interpolation and Regression (Numerical Method, CSC212): what the TU syllabus asks and how it has actually been tested, with 18 solved past questions from this unit.
What this unit covers
- Interpolation vs Extrapolation
- Lagrange's Interpolation
- Newton's Interpolation using divided differences, forward differences and backward differences
- Cubic spline interpolation
- Introduction of Regression
- Regression vs Interpolation
- Least squares method
- Linear Regression
- Non-linear Regression by fitting Exponential and Polynomial
Lagrange's Interpolation
Write an algorithm and program to implement Lagrange interpolation method.[10]
Lagrange interpolation is a method of constructing a polynomial that passes through a given set of data points. Given n+1 data points (x₀, y₀), (x₁, y₁), ..., (xₙ, yₙ), the Lagrange interpolating polynomial is: $$Pn(x) = \sum{i=0}^{n} Li(x) \cdot f(xi)$$ wh...
Full solved answer →Find the lowest degree polynomial, which passes through the following points. Using this polynomial estimate f(x) at x = 0.
$$\begin{array}{c|cccccc} X & -2 & -1 & 1 & 2 & 3 & 4 \ \hline F(x) & -19 & 0 & 2 & -3 & -4 & 5 \end{array}$$
[5]
X -2 -1 1 2 3 4 ----------------------- F(x) -19 0 2 -3 -4 5 Find the lowest degree polynomial through these 6 points, then estimate $f(0)$. Using Newton's Divided Difference Interpolation. First differences: $$f[x0,x1]=\frac{0-(-19)}{-1-(-2)}=\frac{19}{1}=...
Full solved answer →Newton's Interpolation using divided differences, forward differences and backward differences
Consider the following data points. Estimate $f(0.6)$ using Newton's interpolation formula.
$$\begin{array}{c|ccccc} x & 0.1 & 0.2 & 0.3 & 0.4 & 0.5 \ \hline f(x) & 2.68 & 3.04 & 3.38 & 3.69 & 3.97 \end{array}$$
[5]
x 0.1 0.2 0.3 0.4 0.5 ---------------------------- f(x) 2.68 3.04 3.38 3.69 3.97 - Step size $h = 0.1$ (equally spaced) - Target: $f(0.6)$ Since $x = 0.6$ lies beyond the last point $x = 0.5$, use Newton's Backward Difference Formula with base $xn = 0.5$. -...
Full solved answer →Define the terms interpolation and extrapolation. Write down the algorithm and program for Newton's divided difference interpolation.[10]
Interpolation is the process of estimating the value of a function at a point that lies within the range of the given data points. That is, if we have data points $x0, x1, \ldots, xn$, interpolation finds $f(x)$ for some $x$ such that $x0 \leq x \leq xn$. E...
Full solved answer →Newton's Backward Difference Table
Construct Newton's backward difference table for given data points and approximate the value of $f(x)$ at $x=45$.
$$\begin{array}{c|ccccc} x & 10 & 20 & 30 & 40 & 50 \ \hline f(x) & 0.985 & 0.934 & 0.866 & 0.766 & 0.643 \end{array}$$
[5]
x 10 20 30 40 50 ------------------------ f(x) 0.985 0.934 0.866 0.766 0.643 - Step size: $h = 10$ - $xn = 50$, $f(xn) = 0.643$ - Interpolation point: $x = 45$ - $s = \dfrac{x - xn}{h} = \dfrac{45 - 50}{10} = -0.5$ $\nabla f = f(xi) - f(x{i-1})$ First diffe...
Full solved answer →Newton's Interpolation
What is Newton's interpolation? Obtain the divided difference table from the following data set and estimate the f(x) at x = 2 and x = 5.
$$\begin{array}{c|ccccc} x & 3.2 & 2.7 & 1.0 & 4.8 & 5.6 \ \hline f(x) & 22.0 & 17.8 & 14.2 & 38.3 & 51.7 \end{array}$$
[5]
Newton's interpolation constructs an interpolating polynomial through unequally (or equally) spaced data points using divided differences. Its form is: $$Pn(x) = f[x0] + f[x0,x1](x-x0) + f[x0,x1,x2](x-x0)(x-x1) + \cdots$$ $i$ $xi$ $f(xi)$ ------------------...
Full solved answer →Newton's Forward Difference Table
Construct Newton's forward difference table for the given data points and approximate the value of $f(x)$ at $x = 15$.
$$\begin{array}{c|ccccc} x & 10 & 20 & 30 & 40 & 50 \ \hline F(x) & 0.173 & 0.342 & 0.5 & 0.643 & 0.766 \end{array}$$
[5]
x F(x) --------- 10 0.173 20 0.342 30 0.500 40 0.643 50 0.766 Spacing $h = 10$, $x0 = 10$. Required: $f(15)$. --- First differences ($\Delta$): - $0.342 - 0.173 = 0.169$ - $0.500 - 0.342 = 0.158$ - $0.643 - 0.500 = 0.143$ - $0.766 - 0.643 = 0.123$ Second di...
Full solved answer →Non-linear Regression by fitting Exponential and Polynomial
What is regression analysis? Fit a second order polynomial for the following data values.
$$\begin{array}{c|ccccc} x & 2 & 4 & 6 & 8 & 10 \ \hline y & 1.4 & 2.0 & 2.4 & 2.6 & 2.8 \end{array}$$
[5]
Regression analysis is a statistical technique used to determine the best-fit mathematical relationship between a dependent variable and one or more independent variables. Unlike interpolation (which forces the curve through every data point), regression mi...
Full solved answer →Fit the quadratic curve through the following data points and estimate the value of f(x) at x=2.
$$\begin{array}{c|ccccc} x & 1 & 3 & 4 & 5 & 6 \ \hline y & 2 & 7 & 8 & 7 & 5 \end{array}$$
[5]
$x$ 1 3 4 5 6 -------------------- $y$ 2 7 8 7 5 $n = 5$. Fit $y = a0 + a1 x + a2 x^2$ by least squares and find $f(2)$. --- $x$ $y$ $x^2$ $x^3$ $x^4$ $xy$ $x^2y$ --------------------- 1 2 1 1 1 2 2 3 7 9 27 81 21 63 4 8 16 64 256 32 128 5 7 25 125 625 35 1...
Full solved answer →Fit the quadratic function for the data given below using least square method.
| x | 1.0 | 1.5 | 2.0 | 2.5 | 3.0 | 3.5 | 4.0 |
|---|---|---|---|---|---|---|---|
| f(x) | 2.7 | 4.0 | 5.8 | 8.3 | 11.2 | 15.0 | 19.0 |
[5]
$n = 7$ $x$ 1.0 1.5 2.0 2.5 3.0 3.5 4.0 ---------------------------------------- $y=f(x)$ 2.7 4.0 5.8 8.3 11.2 15.0 19.0 Model: $y = a0 + a1 x + a2 x^2$ $x$ $y$ $x^2$ $x^3$ $x^4$ $xy$ $x^2y$ --------------------------------------------- 1.0 2.7 1.00 1.000 1...
Full solved answer →Fit the curve $y = ae^{bx}$ through the following data points.
| x | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| y | 1.65 | 2.70 | 4.50 | 7.35 |
[5]
$x$ 1 2 3 4 ------------------------- $y$ 1.65 2.70 4.50 7.35 $n = 4$ Taking natural logarithm: $$\ln y = \ln a + bx$$ Let $Y = \ln y$, $A = \ln a$, $B = b$: $$Y = A + Bx$$ $x$ $y$ $Y=\ln y$ $x^2$ $xY$ -------------------------- 1 1.65 0.50078 1 0.50078 2 2...
Full solved answer →Cubic spline interpolation
Given the data points below, find cubic spline which belongs to $1 \leq x \leq 3$ and estimate $f(2)$ using cubic splines.
$$\begin{array}{c|ccc} x & 1.0 & 3.0 & 4.0 \ \hline f(x) & 1.5 & 4.5 & 9.0 \end{array}$$
[5]
i $xi$ $fi$ ----------------- 0 1.0 1.5 1 3.0 4.5 2 4.0 9.0 Number of intervals $n = 2$. We use natural cubic spline (standard assumption when no end conditions given). --- $$h0 = x1 - x0 = 2, \qquad h1 = x2 - x1 = 1$$ Natural boundary conditions: $M0 = 0,\...
Full solved answer →Spline Interpolation vs Lagrange Interpolation
Key Differences:
-
Degree of polynomial: Lagrange interpolation uses a single polynomial of degree $n-1$ for $n$ points, while spline interpolation uses piecewise polynomials (typically cubic) of lower degree on each subinterval.
-
Smoothness: Spline interpolation ensures continuity of the function and its derivatives at knots, providing smoother curves. Lagrange interpolation may exhibit oscillations (Runge's phenomenon).
-
Computational efficiency: Spline interpolation is more efficient for large datasets and avoids high-degree polynomial issues.
-
Local vs global: Spline interpolation is local (changes in one interval don't affect others), while Lagrange interpolation is global.
Cubic Spline Interpolation
Given data:
$$\begin{array}{c|cccc} x & -1 & 1 & 2 & 3 \ \hline f(x) & -10 & -2 & 14 & 86 \end{array}$$
Step 1: Set up intervals and spacing
- Interval 1: $[-1, 1]$, $h_1 = 2$
- Interval 2: $[1, 2]$, $h_2 = 1$
- Interval 3: $[2, 3]$, $h_3 = 1$
Step 2: Calculate second differences
$$\Delta f_1 = \frac{-2-(-10)}{2} = 4, \quad \Delta f_2 = \frac{14-(-2)}{1} = 16, \quad \Delta f_3 = \frac{86-14}{1} = 72$$
Step 3: Set up system for second derivatives (assuming natural spline: $M_0 = M_3 = 0$)
$$h_1 M_0 + 2(h_1+h_2)M_1 + h_2 M_2 = 6(\Delta f_2 - \Delta f_1)$$ $$2(2) + 2(3)M_1 + 1 \cdot M_2 = 6(16-4) = 72$$ $$6M_1 + M_2 = 72 \quad \text{...(1)}$$
$$h_2 M_1 + 2(h_2+h_3)M_2 + h_3 M_3 = 6(\Delta f_3 - \Delta f_2)$$ $$M_1 + 4M_2 = 6(72-16) = 336 \quad \text{...(2)}$$
Solving: From (1): $M_2 = 72 - 6M_1$
Substituting into (2): $M_1 + 4(72-6M_1) = 336$ $$M_1 + 288 - 24M_1 = 336$$ $$M_1 = -\frac{48}{23}, \quad M_2 = \frac{1656}{23}$$
Step 4: Estimate $f(0)$ and $f(4)$
For $f(0)$ (in interval $[-1, 1]$): Using cubic spline formula with $x = 0$, $t = \frac{0-(-1)}{2} = 0.5$:
$$f(0) = -10(1-t)^3 + (-2)t^3 + \frac{M_0}{6}(1-t)^3 \cdot 2^3 + \frac{M_1}{6}t^3 \cdot 2^3$$
$$f(0) = -10(0.125) - 2(0.125) + \frac{1}{6} \cdot (-\frac{48}{23}) \cdot 0.125 \cdot 8$$
$$\boxed{f(0) \approx -6}$$
For $f(4)$: Since $x = 4$ is outside the data range $[-1, 3]$, extrapolation using the last spline segment $[2, 3]$ gives:
$$\boxed{f(4) \approx 158}$$
[10]
Feature Lagrange Interpolation Cubic Spline Interpolation --------- Approach Single global polynomial of degree $(n-1)$ through all $n$ points Piecewise cubic polynomials between consecutive points Degree Grows with number of points Always cubic in each sub...
Full solved answer →What are the problems with polynomial interpolation for a large number of data set? How such problems are addressed? Explain with an example. [5]
When the number of data points is large, a single polynomial of degree n-1 must be fitted through all n points. This approach suffers from several serious problems: For a large number of data points, a high-degree interpolating polynomial tends to oscillate...
Full solved answer →Linear Regression
Linear Regression Question
What is linear regression? Fit the linear function to the following data.
$$\begin{array}{c|cccccccc} x & 1.0 & 1.2 & 1.4 & 1.6 & 1.8 & 2.0 & 2.2 & 2.4 \ \hline f(x) & 2.0 & 2.6 & 3.9 & 6.0 & 9.3 & 15.0 & 20.6 & 30.4 \end{array}$$
[5]
Linear regression is a curve-fitting technique that determines the best-fit straight line through a set of data points using the least squares principle, which minimizes the sum of squares of the residuals (vertical deviations) between observed values and t...
Full solved answer →The fit function of type $y = a + bx$ for the following points using the least square method.
$$\begin{array}{c|cccccc} X & -1 & 1.2 & 2 & 2.7 & 3.6 & 4 \ \hline F(x) & 1 & 20 & 27 & 33 & 41 & 45 \end{array}$$
[5]
X -1 1.2 2 2.7 3.6 4 --------------------------- F(x) 1 20 27 33 41 45 Number of points: $n = 6$ Normal equations for $y = a + bx$: $$\sum y = na + b\sum x$$ $$\sum xy = a\sum x + b\sum x^2$$ x y x² xy --------------------------- -1 1 1.00 -1.0 1.2 20 1.44 ...
Full solved answer →Regression vs Interpolation
How interpolation differs from regression? Write down algorithm and program for Lagrange interpolation.[10]
Basis Interpolation Regression --------- Definition Estimating the value of a function at a point within the range of known data points Finding the best-fit curve that approximates the relationship between variables Data Fit The curve passes exactly through...
Full solved answer →Least squares method
What is least squares approximation of fitting a function? How does it differ with polynomial interpolation? Explain with suitable example. [5]
Least squares approximation is a method of fitting a function (usually a polynomial) to a set of data points such that the sum of the squares of the errors (residuals) between the actual data values and the approximated function values is minimized. When we...
Full solved answer →Make Unit 2 stick
Practice CSC212 with flashcards & quizzes