{
"cells": [
{
"cell_type": "markdown",
"id": "56889fcd-f08a-4475-9928-af817748f5c8",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "a24d0f65f17b686af2bd6a59ddc28500",
"grade": false,
"grade_id": "cell-5e2b58ff19f0997c",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"## Numerical Analysis - Fall semester 2025\n",
"# Serie 08 - Interpolation"
]
},
{
"cell_type": "markdown",
"id": "5d0c899b-58da-49e8-ace0-828c8d5b60ca",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "10edd7f8d5f42ef44d458651f4e462e8",
"grade": false,
"grade_id": "cell-e56f5ef08590e711",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"First, we will need to import some of the usual packages. You will have to run this cell every time you restart your notebook."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7d640d3e-d688-47ad-95b6-96eed7152684",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "c421cd6444adfd593791bcaa50c264d3",
"grade": false,
"grade_id": "cell-6bbe893666203fcf",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"import scipy as sp"
]
},
{
"cell_type": "markdown",
"id": "e28c8be9-80d5-4168-8c0e-2bb5d3925c06",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "397b88dc3d00e445fda7c42125519752",
"grade": false,
"grade_id": "cell-21702acd622409d7",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"### Simple polynomial interpolation"
]
},
{
"cell_type": "markdown",
"id": "e24a1318-bbc7-4c35-a333-f49a837ea8e6",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "8c331c4a4ee740edc9eb85bbb27bdd06",
"grade": false,
"grade_id": "cell-4cb2537f66cd892a",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"We have the following data\n",
"\n",
"\\begin{align*}\n",
"x_0=0 \\quad & y_0=12, \\\\\n",
"x_1=1 \\quad & y_1=18, \\\\\n",
"x_2=2 \\quad & y_2=6.\n",
"\\end{align*}"
]
},
{
"cell_type": "markdown",
"id": "83ec0ada-c0ee-4eff-b09f-91a9fefa1fe4",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "cdaac5b4e7b908198898458c78826585",
"grade": false,
"grade_id": "cell-eae9b3444545bcc0",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
"\n",
"**Exercise 1:** Find the second order polynomial interpolating the data by setting up and solving the linear system with the Vandermonde matrix.\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e872398c-41f4-49f5-b779-6945c9ffeecb",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "12574dc41920017a8113ac108f322abd",
"grade": false,
"grade_id": "cell-9d483aa33a68eb6d",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "eaee1e7b-ede4-44ca-aa7a-d95bbd5e3a61",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "ef09f72acf873ffb49cf584f56261c82",
"grade": false,
"grade_id": "cell-7e65398ebdd6886a",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
"\n",
"**Exercise 2:** Find the second order polynomial interpolating the data by using `np.polyfit`, evaluate the resulting polynomial at $100$ evenly spaced points in the interval $[-1, 3]$ by using `np.polyval`, and use them to visualize the polynomial on the same plot with the data.\n",
"\n",
"*Hint:* To plot individual data points, use `plt.scatter`. To find out more about a function's inputs and outputs, use `help(function_name)`.\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "29a9caf6-f274-48b7-89fb-e93a4c42cdfa",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "7fdd5598d280efd9fb2facf7cf56ffe9",
"grade": false,
"grade_id": "cell-9b9bb5f23dec69e1",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "c3bacfe2-119a-4fae-abf4-5b39aa701ba3",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "4b270bdac2a5ed9fe81e325c0a3ae7e5",
"grade": false,
"grade_id": "cell-c76fe18176498d71",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": true
}
},
"source": [
"\n",
"\n",
"**Exercise 3 (Theoretical):** Find the three polynomials of the Lagrangian basis corresponding to the points $x_0=0, x_1=1$ and $x_2=2$.\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "5e3345ca-ba08-4698-b584-c539039a087e",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "3f2a78a9ec11a571b8e64ed33ee9ad07",
"grade": false,
"grade_id": "cell-947dc5151412a6ab",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": true
}
},
"source": [
"\n",
"\n",
"**Exercise 4 (Theoretical):** Using your result from the previous exercise, write down the second order polynomial interpolating the data. Compare the resulting polynomial to what you have found with the Vandermonde matrix at the beginning of this section.\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "171e46ca-4033-43d5-aa35-918e83028b80",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "df8248ef848a1226e6d2ca28f02a40ca",
"grade": false,
"grade_id": "cell-231501d536ca7f10",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"### Interpolating functions at uniform and non-uniform nodes"
]
},
{
"cell_type": "markdown",
"id": "20cecddd-9da9-4501-8b33-1b0b9c58b2b7",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "f36d7fbc75f70f199ab16ea0154efe4a",
"grade": false,
"grade_id": "cell-cf07ec01b52c57c1",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"We are given the data $(x_i,y_i)$, $i=0,1,\\ldots,n$, where the $x_i$ are $n+1$ nodes in the interval $[a,b]=[-5,5]$ and\n",
"the values $y_i$ come from evaluation of the *Runge* function\n",
"$$\n",
" g(x)= \\frac{1}{1+x^2}\n",
"$$\n",
"without any measurement error, namely $y_i = g(x_i)$. We want\n",
"to apply polynomial interpolation to the function $g$ from the data $(x_i,y_i)$."
]
},
{
"cell_type": "markdown",
"id": "44ec24f9-28db-486c-aede-8d7843df0fac",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "48127dc8aecd9082be9330eb898f1098",
"grade": false,
"grade_id": "cell-3713f2f8c72dc60b",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
"\n",
"**Exercise 5:** For degrees $n=6$ and $n=12$, compute the polynomial $p_n$ interpolating the data $(x_i,y_i)$, $i=0,1,...,n$ with uniformly spaced nodes\n",
"\n",
"\\begin{equation*}\n",
" x_i = a + \\frac{i}{n} (b - a), ~i=0,1,...,n.\n",
"\\end{equation*}\n",
"\n",
"Visualize the function and the interpolating polynomial at $1'000$ evenly spaced points in the interval $[-5, 5]$. What do you observe?\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a4403392-5586-4756-ba1f-310ebd20a19d",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "747c91c587db41b2b15bdc02cc0444b6",
"grade": false,
"grade_id": "cell-7ef3e42056d8af80",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "25ec3b7a-b5d1-424c-9bac-d084594c286f",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "6dd90a1c632668da874660c9a97f3c8b",
"grade": false,
"grade_id": "cell-cea090203d5bd4f8",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
"\n",
"**Exercise 6:** Repeat the previous exercise for the Chebyshev nodes, i.e. nodes which are given by\n",
"\n",
"\\begin{equation*}\n",
" x_i = \\frac{b+a}{2} - \\frac{b-a}{2} \\cos\\left(\\frac{(i+1/2)\\pi}{n+1}\\right), ~i=0,1,...,n.\n",
"\\end{equation*}\n",
"\n",
"Compare the result to the previous exercise. Explain the difference using what you have learned in the lecture.\n",
"\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c80748c6-96b9-4063-b385-6e14cee9f702",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "20749bd64c358b0ac9df63d07495aed8",
"grade": false,
"grade_id": "cell-72d8d1630a517dcb",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "f01a8636-d4a0-49e9-9d89-c094396475c4",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "63b163a72541ec668873d0704c820dcf",
"grade": false,
"grade_id": "cell-edc009ca3aeda977",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": true
}
},
"source": [
"\n",
" \n",
"**Exercise 7 (Theoretical):** Let $a, b \\in \\mathbb{R}$ such that $a < b$. Given $n \\in \\mathbb{N} \\setminus \\{0\\}$, define $h = (b-a)/n$ and, for all $i \\in \\{0, \\dots, n\\}$, $x_i = a+hi$. Prove that, for all $x \\in [a, b]$\n",
"\n",
"$$\n",
"|\\prod_{i=0}^n (x-x_i)| \\le n! h^{n+1} / 4.\n",
"$$\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "ad0cc246-9347-4104-bfe4-f3a0e19dfc2a",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "f344782b8bffa358ba1cb2ac6d021a4b",
"grade": false,
"grade_id": "cell-3270c931b3a927db",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": true
}
},
"source": [
"\n",
" \n",
"**Exercise 8 (Theoretical):** Use the bound from the previous exercise and a theorem seen in a lecture that if $f \\in \\mathrm{C}^{n+1}([a, b], \\mathbb{R})$ and $p_n : \\mathbb{R} \\to \\mathbb{R}$ is the polynomial function of degree at most $n$ such that $p_n(x_i) = f(x_i)$ for all $i \\in \\{0, \\dots, n\\}$, then\n",
"\\begin{equation*}\n",
"\\max_{x \\in [a, b]} |f(x)-p_n(x)| \\le \\frac{1}{4(n+1)} \\left(\\frac{b-a}{n}\\right)^{n+1} \\max_{x \\in [a, b]} |f^{(n+1)}(x)|.\n",
"\\end{equation*}\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "0be30898-1de3-4750-b510-87c88ca004ed",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "3e6e7d48fdcb481d9f4f63288d5b079d",
"grade": false,
"grade_id": "cell-8cc7f4e29978a25b",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"### Interpolation with cubic splines"
]
},
{
"cell_type": "markdown",
"id": "a2399b12-afe7-46b8-8de0-afc31f306fe4",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "45d3e9b850df42e37d7ae9271c9a135c",
"grade": false,
"grade_id": "cell-09a88f08fb9c51f5",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"We consider the functions\n",
"\n",
"$$\n",
"g_1(x) = \\sin(5 x)\n",
"$$\n",
"\n",
"and \n",
"\n",
"$$\n",
"g_2(x) = x |x|\n",
"$$\n",
"\n",
"on the interval $[-1, 1]$."
]
},
{
"cell_type": "markdown",
"id": "5fef24d8-2835-4b97-a2cd-f4359ba9bd68",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "1941f1b853c6e94a30a6cf64b0da0bfa",
"grade": false,
"grade_id": "cell-227a5ecccdbaacf4",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
" \n",
"**Exercise 9:** Use cubic splines to interpolate the functions $g_1$ and $g_2$ at $n + 1$ equidistant nodes for $n = 2^k$ and $k = 4, 5, \\dots, 8$ in the interval $[-1, 1]$. For every $h = 2 / n$, approximate the maximum absolute error\n",
"\n",
"$$\n",
"E_{3, h} = \\max_{x \\in [-1, 1]} |g(x) - s_{3, h}(x)|\n",
"$$\n",
"\n",
"by evaluating the spline and the function in $100$ equally spaced points within the interval $[-1, 1]$ and computing the maximum absolute distance attained in these points. Plot $E_{3, h}$ against all $h$ for both functions in a log-log plot (use `plt.loglog` for this).\n",
"\n",
"*Hint:* The SciPy function `spline = sp.interpolate.CubicSpline(x, y)` interpolates some data `x` and `y` with a cubic spline, and returns a a function `spline`, which can be called to evaluate the spline at some points. \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9ee591b5-ba1f-404e-977c-cd61efc57ca2",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "22bd9a5b1931c4557dbc0d912d8e2d8f",
"grade": false,
"grade_id": "cell-16828d478bb8ef2c",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "1ba42156-1c02-4a00-b8b1-fcc789dd6435",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "646d2b7e85ab8cd9ba9e07a56ed541bf",
"grade": false,
"grade_id": "cell-5b39b5b957674ceb",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"## The end\n",
"\n",
"Splendid! You have reached the end of the eighth exercise notebook."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.3"
}
},
"nbformat": 4,
"nbformat_minor": 5
}