About this summary

These notes are a summary of Simone Rebegoldi's 2024 Course in UNIMORE's Computer Science curriculum, originally called Calcolo Numerico; they're mostly based on his slides and exercises, following the same program. I will eventually cite additional sources whenever used.

I wrote these notes mostly as a way of studying and revising my knowledge; I had zero prior experience with the field before this course, don't expect much!

The program

This is what you'll find here:

• Machine arithmetic notions and analysis of rounding errors;
• Methods of solving linear systems: Gauss-Jordan elimination, LU, QR, Crout, Cholesky and Singular Value decompositions, iterative methods (like Jacobi and Gauss-Seidel) and analysis of their convergence.
• Methods of solving non-linear systems: Bisection, Newton, secant and fixed-point methods, analysis of their convergence, plus gradient-based methods and their application in Machine Learning.
• Approximation of Data and Functions: The mathematical problem of representation, polynomial interpolation and spline interpolation functions, the least squares method in approximation.
• Implementation of the previously mentioned methods, along with exercises.

The practical part of the course is presented in the MATLAB environment; all code is also compatible with the free software alternative GNU Octave. Viceversa, if I happened to label a block of code in these notes as Octave code, it can be ran in MATLAB too.

What is Numerical Analysis?

Numerical Analysis is a discipline that studies the numerical solution of mathematical problems on an electronic computer, attempting to find an approximation of the theoretical result with the use of algorithms (a non-ambiguous sequence of instructions that, given an input, returns a solution in finite time).

For example, to find the derivative of a given function $\mathcal{f}$, while in calculus we would apply theorems and definitions to find the analytical form of $\mathcal{f}'$, in numerical analysis we instead "settle" for calculating $y$, an approximation of the result of $\mathcal{f}'(x)$ given $x\in\mathbb{R}$.

Numerical algorithms and their application

An example of an algorithm is the following C-style function:

int find_max(int n, int a[])
{
	int M = a[0];
	for (int i = 1; i < n; i++)
	{
		if (M < a[i]) M = a[i]; 
	} 
	return M;
}

What it does is that, given a sequence $a_1,a_2,...,a_n$ of length $n$, it finds the quantity $$M = \max_{1 \leq i \leq n} a_i$$Here is the same algorithm in equivalent MATLAB (or Octave) code:

function maxVal = find_max(a)
    maxVal = a(1);
    for i = 2:length(a)
        if a(i) > maxVal
            maxVal = a(i);
        end
    end
end

It's not always possible to directly translate the thought process of solving a mathematical calculus problem into an algorithm: for example, we can't compute a Taylor expansion with just the Taylor formula as the $\lim{\to\infty}$ would result in an infinite loop. To handle this and create a finite algorithm, we need to introduce a new tolerance parameter that determines at which iteration the summation stops; the lower the tolerance, the higher the precision of our result.

In numerical analysis, finite execution time is not the only limitation: since algorithms are run by computers, any result, whether final or intermediate, has to be stored in memory, which is finite itself, to be used. This means real numbers have to be approximated, and one of the main concerns of the field is making these approximations as accurate as possible while also avoiding the sacrifice of too much speed and space.

Before continuing, I suggest looking at the next chapter, a simple cheatsheet I made for the main MATLAB operations and features. I also recommend trying to reimplement all the algorithms we will see on your own first, if you can, and then fiddling around with them a bit to more easily understand the math behind the intuition.