{
"cells": [
{
"cell_type": "markdown",
"id": "56889fcd-f08a-4475-9928-af817748f5c8",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "f665680d0f1d9218c2dd3c2420afc976",
"grade": false,
"grade_id": "cell-5e2b58ff19f0997c",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"## Numerical Analysis - Fall semester 2025\n",
"# Serie 03 - Linear systems and least squares "
]
},
{
"cell_type": "markdown",
"id": "e59533b3-b808-4126-b177-3390877b24ad",
"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": "5afb622e-c357-4a77-9356-e75ad0400743",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "896fc9aab44afbe84f4354fdd6801bb3",
"grade": false,
"grade_id": "cell-44ae0a875bc8bfaa",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"outputs": [],
"source": [
"import numpy as np\n",
"import scipy as sp\n",
"import matplotlib.pyplot as plt\n",
"import matplotlib\n",
"import timeit\n",
"import sys"
]
},
{
"cell_type": "markdown",
"id": "c6a11316-90ea-4626-9f28-a2e771931fb6",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "f0b8279a2c332bec3f7b89a911ff690f",
"grade": false,
"grade_id": "cell-84aa00fc84169745",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"### Error indicators for linear systems"
]
},
{
"cell_type": "markdown",
"id": "96ada285-fd70-4e32-8922-9698937feaef",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "82031fd28faf02a67ccff395b6f84f71",
"grade": false,
"grade_id": "cell-a8820993a4136c45",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"We consider the Vandermonde matrix\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 1 & t_1 & t_1^2 & \\cdots & t_1^{n-1}\\\\\n",
" 1 & t_2 & t_2^2 & \\cdots & t_2^{n-1} \\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
" 1 & t_n & t_n^2 & \\cdots & t_n^{n-1} \n",
"\\end{bmatrix} \\in \\mathbb{R}^{n\\times n},\n",
"$$\n",
"\n",
"where the points $t_1, \\ldots, t_n$ are equispaced in the interval $[0, 1]$. For a set of points `t`, the Vandermonde matrix can be generated with `A = np.vander(t, increasing=True)`\n",
"\n",
"We want to solve the linear system $A\\mathbf{x}=\\mathbf{b}$ for $\\mathbf{x}$ where\n",
"$$\n",
"\\mathbf{b} = \\begin{bmatrix}\n",
" 1+t_1^2 \\\\\n",
" 1+t_2^2 \\\\\n",
" \\vdots \\\\\n",
" 1+t_n^2 \n",
"\\end{bmatrix} \\in \\mathbb{R}^{n}.\n",
"$$\n",
"Clearly, the exact solution is $\\mathbf{x}=(1,0,1,0\\ldots,0)^\\top \\in \\mathbb{R}^{n}$."
]
},
{
"cell_type": "markdown",
"id": "4dd7a1a8-6d06-445e-b79e-1c8a06b60168",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "a0c6bcb12ede408bb89af50aaecda758",
"grade": false,
"grade_id": "cell-c4b90ad935697c8b",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
" \n",
"**Exercise 1:** For $n=4$, solve the linear system numerically using the command `np.linalg.solve`. Let $\\mathbf{x_c}$ be the obtained solution. Compute the relative error $\\varepsilon=\\|\\mathbf{x_c}-\\mathbf{x}\\| / \\|\\mathbf{x}\\|$. \n",
"\n",
"*Hint:* The Euclidean norm of a vector can be computed with the NumPy command `np.linalg.norm`.\n",
"
\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b39c4e6b-b1b0-49b1-af62-1c3fe8cc0de0",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "cc89afce5895f1d3ed21d65fceef56b8",
"grade": false,
"grade_id": "cell-25b5edf479728cc5",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "c869583c-d712-46dc-88bb-efaee81612de",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "f565e9a16a5b21af4746cce688b9412b",
"grade": false,
"grade_id": "cell-082097f7af39bc91",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
" \n",
"**Exercise 2:** For the same linear system but for matrix sizes $n=4, 6, 8, \\ldots, 20$, visualize the relative error $\\varepsilon$ and the normalized residual $r = \\|\\mathbf{b}-A\\mathbf{x_c}\\|/\\|\\mathbf{b}\\|$ in terms of $n$, in two graphs, one in logarithmic scale (`plt.loglog`) and one in semi-logarithmic scale (`plt.semilogy`). What type of growth do we see for the error $\\varepsilon$? Is the residual $r$ a good indicator of the error $\\varepsilon$?\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "453aed5a-d2e3-4d05-8a32-dc45bf98a76d",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "d0d7041222cb5b8d67deba6c302241fd",
"grade": false,
"grade_id": "cell-eabe04df715c7588",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "3a449edc-be9a-48f3-b0ac-f73faea9de57",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "928f2d97c73e58bfd436b1d7051a1363",
"grade": false,
"grade_id": "cell-a0ae4caad8c3c188",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"We now consider a different matrix\n",
"$$\n",
"B = \\begin{bmatrix} 2 & -1 & & & \\\\ -1 & 2 & \\ddots & & \\\\ & \\ddots\n",
"& \\ddots & \\ddots & \\\\ & &\\ddots & \\ddots & -1 \\\\ &&&-1&2 \\end{bmatrix} \\in \\mathbb{R}^{n \\times n}\n",
"$$\n",
"which can be generated with the command `B = np.diag(2 * np.ones(n), 0)-np.diag(np.ones(n - 1), 1) - np.diag(np.ones(n - 1), -1)`.\n",
"\n",
"We want to solve the linear system $B \\mathbf{y}=\\mathbf{c}$ where $\\mathbf{c}=(2,2,\\cdots,2)^\\top \\in \\mathbb{R}^{n}$. The exact solution in this case is\n",
"$$\n",
"\\mathbf{y} =\n",
"\\begin{bmatrix}\n",
"1\\cdot(n) \\\\\n",
"2\\cdot(n-1)\\\\\n",
"3\\cdot(n-2)\\\\\n",
"\\vdots \\\\\n",
"n\\cdot 1 \n",
"\\end{bmatrix} \\in \\mathbb{R}^{n}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "7fe8c0a4-4177-4764-a252-37fe0eecb25c",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "c2696c27404c103f52f3392debefc947",
"grade": false,
"grade_id": "cell-c568133a88fa9b70",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"\n",
" \n",
"**Exercise 3:** For $n=5, 10, \\ldots, 100$, repeat the previous exercise for the matrix $B$. Comment on the result.\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "261e974b-2fea-4b8f-ad53-7ce4a6cbcc5e",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "6fc91cb4244905722ea12f6119d2b3a6",
"grade": false,
"grade_id": "cell-06fbc99ea2e15816",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "4f21d81b-8a71-47b6-83bc-0748ed5bdf53",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "309d7cc02c302799b8b74f75a31e7f4b",
"grade": false,
"grade_id": "cell-32ac17238c11e7c0",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"### Least squares solution"
]
},
{
"cell_type": "markdown",
"id": "4b2c97a9-957d-4f05-b8f1-babf80072401",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "7bbaf6bb7cdb801e16a29f6796008b82",
"grade": false,
"grade_id": "cell-35894ac7feb6c7ef",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": true
}
},
"source": [
"\n",
" \n",
"**Exercise 4 (Theoretical):** Derive the least-squares solution to $A \\mathbf{x} = \\mathbf{b}$ for a matrix $A$ with linearly independent columns. That is, show that $\\mathbf{x}^{\\ast} = (A^{\\top} A)^{-1} A^{\\top} \\mathbf{b}$ is the minimizer of the least-squares problem\n",
"$$\n",
"\\mathbf{x}^{\\ast} = \\arg\\min_{\\mathbf{x} \\in \\mathbb{R}^m} ~\\lVert A \\mathbf{x} - \\mathbf{b} \\rVert^2\n",
"$$\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "4064c37b-f1b9-46ef-bc51-1a69c4215a37",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "81618250ed89d6d0a5fe9f99213ad7cf",
"grade": false,
"grade_id": "cell-f940899dd63121ec",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": true
}
},
"source": [
"\n",
" \n",
"**Exercise 5 (Theoretical):** Compute the least-squares solution $\\mathbf{x}^{\\ast}$ for $A \\mathbf{x} = \\mathbf{b}$ \n",
"$$\n",
"A = \\begin{bmatrix} 1 & -1 \\\\ 1 & 0 \\\\ 1 & 1 \\end{bmatrix} \\quad \\text{and} \\quad \\mathbf{b} = \\begin{bmatrix} 1 \\\\ 1/2 \\\\ 1/3 \\end{bmatrix}\n",
"$$\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "2443aa45-0fca-4113-995c-70e9adc40d89",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "markdown",
"checksum": "b1b60b8b905a1385c06dc3dbc34bc7c8",
"grade": false,
"grade_id": "cell-a26fae9678ff662c",
"locked": true,
"schema_version": 3,
"solution": false,
"task": false
}
},
"source": [
"
\n",
"\n",
"## The end\n",
"\n",
"Congratulations! You have made it to the end of the third 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
}