# BASIC NUMERICAL METHODS

Academic Year 2023/2024 - Teacher: Giovanni RUSSO

## Expected Learning Outcomes

The course is an introduction to numerical methods for the solution of basic mathematical problems. Addressed to students of the second year of Mathematics, it aims to present some basic ideas of the art numerical approximation, such as accuracy, robustness and efficiency of the methods, and fundamental techniques for the solution of linear systems, interpolation and approximation functions, solution of nonlinear equations and computation of integrals. The course provides an introduction to the use of Matlab for numerical computation. The implementational aspects of the methods are explained in part during the course, and partly during the afternoon supplementary activities (tutoring) related to the course.

In more detail, the following points are considered:

Knowledge and understanding: one of the fundamental objectives of the course is the learning of the basic methodologies for the numerical resolution of some mathematical problems such as the solution of linear systems, the approximation of data and functions, the solution of nonlinear equations, approximation of integrals. The aim is an active and critical understanding of the discipline, not limited to the mere learning of the methodologies, but also and above all a profound understanding of the basic ideas that transversally permeate the techniques relating to the various problems considered.

Ability to apply knowledge and understanding: the computational tools learned must be mastered and applied to concrete problems. The verification of learning and understanding of the methodologies, in fact, can only be carried out through the practical application of the same to various problems which are partly assigned at home and partly carried out in class.

Making judgments: students must be able to compare the different methods learned during the course, and understand which is the most suitable for solving a particular problem, taking into account both the characteristics of the problem itself (or of the problems that you intend to address) and the resources available or that you decide to use (problem of computational efficiency)

Communication skills: the students are invited to clearly explain the topics covered during the oral exam, and to explicitly illustrate the various steps in solving the problems. Even at the programming level, the clarity of the writing of the codes is taken into account in the evaluation of the documents.

Learning skills: learning is stimulated already during the lectures through direct questions from the teacher. These questions have the triple purpose of drawing the learner's attention, forcing him to think quickly about an answer, and probing the level of the class, so as to be able to better regulate the pace of the teacher's presentation, or to identify and address any critical issues together.

## Course Structure

The teaching activity consists mainly of lectures given by the teacher, during which the topics of the course are presented.

The lessons will be face-to-face, or in mixed or remote mode, depending on what is allowed by the containment measures of the pandemic, and in compliance with the safety of the students and the teacher.

During class the teacher will illustrate Python implementations of some of the methods presented in the lectures. The course is complemented by additional tutoring activities.

Students are invited to clarify any doubts during the lesson or during the office hours. It is better to clarify the doubts before taking the exam than after.

The exam consists of a practical test and an oral test.

The oral exam can be accessed only after passing the practical test.

The practical test consists in solving some proposed exercises to the computer within a time set by the teacher and in any case not exceeding three hours.

Passing the practical test allows access to the oral test in the same session or even in a subsequent session, within a year.

Learning assessment may also be carried out on line, should the conditions require it.

Information for students with disabilities and / or SLD

To guarantee equal opportunities and in compliance with the laws in force, interested students can ask for a personal interview in order to plan any compensatory and / or dispensatory measures, based on the didactic objectives and specific needs. It is also possible to contact the referent teacher CInAP (Center for Active and Participated Integration - Services for Disabilities and / or SLD) of our Department, prof. Filippo Stanco.

## Attendance of Lessons

Strongly recommended

## Detailed Course Content

Introduction to the use of the computer for numerical calculations.

Introduction to Python language. Enthought Canopy. Variables and elementary instructions. Cycles. Data structures. Modules. Use of matplotlib and numpy packages. Floating point representation. Machine numbers. Truncation and rounding. Machine operations. Digital cancellation. Order of accuracy.

Numerical linear algebra.

Elements of linear algebra: vectors, matrices, determinants, inverse matrix. Vector and matrix norms. Natural norms and their representation. Eigenvalues. Spectral radius and its properties. Some special matrices. Direct methods for solving linear systems: triangular systems, Gaussian elimination, pivoting. Factorization A = LU and PA = LU. Compact methods, Choleski factorization and their implementation in python. Conditioning of a linear system. Condition number. Sparse matrices and their representation. Eigenvalues and eigenvectors: brief review. Iterative methods for solving linear systems: Jacobi method, Gauss-Seidel method, SOR method. Stopping criteria. Pointwise and block methods (mention). Singular value decomposition (mention). Localization of the eigenvalues: the theorems Gershgorin-Hadamard. Eigenvalues calculation: direct and inverse power methods.

Approximation of functions and data.

Polynomial interpolation. Lagrange form. Linear interpolation operator. Calculation of the interpolation polynomials. Newton's formula of divided differences. The error formula (Lagrange form). Chebyshev polynomials: recursive formula, zeros, the property of minimal norm. Weierstrass theorem on approximation of a continuous function by polynomials (statement). Bernstein polynomials. The problem of the convergence of a sequence of interpolators schemes. Interpolation by piecewise-polynomials. Splines. Calculation of cubic splines. Method of least squares and applications. Normal equations and their geometric interpretation.

Solution of nonlinear equations.

General concepts. Methods of bisection, secant and Newton. General theory of iterative methods for nonlinear equations and fixed point problems. Convergence order. Stopping criteria. Aitken method for one and two order of convergence of methods.

Weighted integrals. General form of a quadrature formula. Polynomial order (or degree of precision) of a quadrature formula. Interpolatory formulas. Convergence theorem. Newton-Cotes formulas. Gaussian formulas. Composite formulas: trapezoid and Simpson formulae. Romberg method. Adaptive quadrature (notes).

## Textbook Information

The course is almost self-contained, and the subject can be prepared using the notes taken during the lectures of the professor.

In any cases, there are several excellent textbooks in English. An old, still very good one, is the classical book by Eugene Isaacson  (Author), Herbert Bishop Keller (Author):
Analysis of Numerical Methods (Dover Books on Mathematics) Revised Edition.
It can be bought on Amazon for about 15 US\$.

The book can be supplemented by
Introduction to Numerical Analysis: Second Edition (Dover Books on Mathematics) 2nd Edition, by F. B. Hildebrand, at similar price.

## Course Planning

SubjectsText References
1Introduzione all'uso del calcolatore. Introduzione all'uso del linguaggio Python. Enthought Canopy. Variabili ed istruzioni elementari. Cicli. Strutture dati. Moduli. Uso dei pacchetti matplotlib e numpy.Un'ampia documentazione su Python si trova sia on line che su carta. Si consulti il sito: http://www.python.it/doc/libri/
2Rappresentazione in virgola mobile. I numeri di macchina. Troncamento ed arrotondamento. Operazioni di macchina. Cancellazione numerica. Ordine di accuratezza.G.Naldi, L.Pareschi, G.Russo, Introduzione al calcolo scientifico, McGraw-Hill, 2001.
3Algebra lineare numerica. Richiami di algebra lineare: vettori, matrici, determinanti, matrice inversa. Norme di vettore e norme di matrice. Norme naturali e loro rappresentazione. Autovalori. Raggio spettrale e sue proprietà. Alcune matrici particolari.
4Metodi diretti per la risoluzione dei sistemi lineari: sistemi triangolari, metodo di eliminazione di Gauss, pivoting. Fattorizzazioni A=LU e PA=LU.
5Metodi compatti, fattorizzazione di Choleski e loro implementazione in python. Condizionamento di un sistema lineare. Numeri di condizionamento. Matrici sparse e loro rappresentazione.
6Metodi iterativi per la soluzione di sistemi lineari: metodi di Jacobi, metodo di Gauss-Siedel e metodo SOR. Criteri d'arresto.
7Metodi iterativi per punti e per blocchi (cenni). Decomposizione in valori singolari (cenni).
8 Autovalori ed autovettori: richiami. Localizzazione degli autovalori: i teoremi di Gershgorin-Hadamard. Calcolo degli autovalori: il metodo delle potenze, ed il metodo delle potenze inverse.
9Approssimazione di funzioni e dati. Interpolazione polinomiale. Forma di Lagrange. Operatore lineare di interpolazione. Calcolo del polinomi di interpolazione. Formula di Newton delle differenze divise.
10Il resto dell'interpolazione nelle forme di Lagrange e di Newton.
11Polinomi di Chebyshev: formula ricorsiva, zeri, proprietà di minima norma.
12Teorema di Weierstrass sulla approssimazione di una funzione continua mediante polinomi (enunciato).
13Polinomi di Bernstein. Problema della convergenza di una successione di schemi interpolatori.
14 Interpolazione mediante polinomi a tratti. Funzioni spline.
15Calcolo delle spline cubiche.
16Metodo dei minimi quadrati e applicazioni. Equazioni normali e loro interpretazione geometrica.
17Soluzione di equazioni non lineari. Concetti generali. Metodi di bisezione, delle secanti e di Newton. Teoria generale dei metodi iterativi per equazioni non lineari e problemi di punto fisso. Ordine di convergenza. Criteri d'arresto.
18Metodo di Aitken per metodi di ordine di convergenza uno e due.
19Formule di quadratura. Integrali pesati. Forma generale di una formula di quadratura. Ordine polinomiale. Formule interpolatorie.
20Teorema di convergenza. Formule di Newton-Cotes. Formule Gaussiane.
21Formule composite: trapezi e Simpson.

## Learning Assessment

### Learning Assessment Procedures

English.

The exam consists of a practical test and an oral test.

The oral exam can be accessed only after passing the practical test.

The practical test consists in solving some proposed exercises to the computer within a time set by the teacher and in any case not exceeding three hours.

Passing the practical test allows access to the oral test in the same session or even in a subsequent session, within a year.

Learning assessment may also be carried out on line, should the conditions require it.