METHODS OF NUMERICAL APROXIMATION
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2020/2021
- Teacher
- GAETANO ZANGHIRATI
- Credits
- 9
- Didactic period
- Primo Semestre
- SSD
- MAT/08
Training objectives
- The topics included in the lectures provide wide knowledge about the theory and the methods of data and function numerical approximation, in both the continuous and the discrete cases. Part of the hours are dedicated to laboratory activities, where the Optimization Toolbox for Matlab if used for programming exercises.
The main knowledge provided by the course will be:
- general formulation of the approximation problem in functional spaces, both in the continuous and in the discrete cases;
- main algorithms for the solution of the linear approximation problem with Euclidean norm, in both the continuous and the discrete cases;
- main algorithms for the solution of the nonlinear approximation problem with Euclidean norm in the discrete case;
- main algorithms for the solution of the linear approximation problem with infinity norm, in both the continuous and the discrete cases;
- outline of the main algorithms for the solution of the nonlinear approximation problem with infinite norm in the discrete case.
The main skills that students should acquire (that is to say, the abilities to apply their knowledge) will be:
- to be able to mathematically formulate the approximation problem, for functions and observations;
- to be able to assess which approach is preferable for a given problem;
- to know how to solve a linear approximation problem with Euclidean norm in a number of ways, in both the continuous and the discrete cases;
- to be able to mathematically formulate the nonlinear approximation problem in the discrete setting;
- to be able to solve simple discrete nonlinear approximation problems by using various methods;
- to be able to write Matlab code that allow to compute the solution of an approximation problem, both in the linear and in the non-linear cases. Prerequisites
- Basics on Numerical Analysis and Numerical Computations, direct and iterative methods for linear systems. Methods for numerical interpolation and integration. Basics on the Matlab functions and programming features.
To successfully attend the course, the following knowledge and skills need to be acquired from the Geometry 1, Calculus 1 and 2, Numerical Analysis 1 and Computer Programming courses:
- linear algebra (matrix calculus, vector spaces, basis changes, diagonalization, etc.);
- trigonometry, numerical sequences, limits of sequences and functions;
- differential calculus and integral calculus in several variables;
- finite arithmetic and computations, numerical error propagation;
- numerical methods (both direct and iterative) for solving systems of linear equations;
- numerical methods for solving nonlinear equations;
- numerical methods for polynomial interpolation;
- principles of structured programming and ability to write simple codes in a programming language;
- at least basic knowledge of the Matlab language.
Knowing the Matlab language is highly recommended and of considerable help in general, but is essential to be able to use the Optimization Toolbox in laboratory exercises. Course programme
- The course lasts 63 hours, approximately 50 of which are for theoretical lessons and the rest for programming exercises with Matlab. The time scheduling (indicated in parentheses) may vary, even significantly, depending on the difficulties the students will have in the different segments of the program.
The topics to be covered in the lessons are as follows:
— Introduction to the fundamental concepts of numerical approximation, Chebyshev and Bernstein polynomials, rational functions, exponential sums; approximant selection criteria. (4)
— Linear approximation problem: formulation of both the continuous and the discrete cases in Lp spaces. (2)
— The fundamental theorem of linear approximation in Lp spaces. (1)
— Approximation by ordinary least squares (OLS), continuous case: generalized polynomial of best approximation; normal equations; algebraic, orthogonal and orthonormal polynomials; generalized Fourier series; Bessel inequality, Parseval identity, Gram-Schmidt process; convergence in the Euclidean norm; Legendre polynomials, Clenshaw-Curtis formula, Fourier series and its convergence. (9)
— OLS approximation, discrete case: normal equations, existence and uniqueness of the solution; acceptability of the statistical model, geometric interpretation; generalized inverse and Moore-Penrose pseudoinverse; solution and conditioning of the normal equations system; maximum rank and incomplete rank cases; discrete orthogonal polynomials; singular value decomposition (SVD); solution of the linear problem by the SVD; statistical interpretation and Gauss-Markoff theorem. (10)
— Total Least Squares (TLS): separation of the singular values, the solution by SVD, solution uniqueness; relationship with OLS, conditioning, sensitivity; minimax characterization of the singular values; the linear regression problem of the orthogonal distance. (6)
— Introduction to the nonlinear least squares problem (NLS): concepts, short recall of optimization techniques; first order methods: Gauss-Newton (G-N) and relaxed G-N; descent property of the G-N direction; relevance of the Jacobian's numerical rank; basics of the trust-region method. (2)
— Newton-type methods for NLS: local convergence rate; the hybrid Newton method and its solution by SVD; basics of quasi-Newton methods for NLS: RANK1, DFP and BFGS; non-linear regression of the orthogonal distance; the nonlinear approximation problem of the geometrical fit with geometric elements. (2)
— Approximation in Chebyshev norm, continuous case: minimax polynomial; De La Vallée-Puossin theorem, the Chebyshev equioscillation theorem, uniqueness of the solution; Remez's second algorithm; convergence for continuous functions, Jackson's estimate, minimax rest; minimax trigonometric polynomial for periodic functions. (7)
— Approximation in Chebyshev norm, discrete case: general concepts; the m = n + 1 case: solution existence and uniqueness; alternation property; De La Vallee-Puossin theorem, algebraic polynomial case, Vandermonde determinants; the general m > n + 1 case: solution uniqueness, exchange method for discrete data. (8)
— Laboratory: trigonometric polynomials and FFT applied to the approximation problem; TLS exercises and the linear regression problem of the orthogonal distance; introduction to the Matlab Optimization toolbox, function handles, M-functions with variable number of arguments; circular 2D geometric regression bylsqnonlin; images and SVD; Remez's algorithm for the continuous case. (12) Didactic methods
- The course includes theoretical lessons on all of the above mentioned topics, as well as programming sessions for the Matlab implementation of algorithms and their test on some simple problems. Lectures and programming sessions will be given at classroom and/or in streaming (synchronous modality). In case of need, guiding video material will possibly be provided in support of or in substitution of the programming sessions (asynchronous modality).
Learning assessment procedures
- Purpose of the examination tests is to check whether the students achieved an adequate level of the course educational goals or not, with respect to both the knowledge and the skills, including the laboratory part in Matlab.
The examination consists of an oral test, divided in two parts:
- in the first part, open questions are asked on all of the lectures topics;
- the second part is dedicated to a discussion on Matlab exercises, both those provided during the lessons and those assigned as homework. The sources of homework exercises have to be delivered to the teacher before to start the oral test.
The final rating is given by the sum of the the evaluation of the first part, which in general cannot exceed 28/30, and that of the second part. The maximum score on the second part varies between 2/30 and 10/30, depending on the amount of time that it was possible to devote to the lab during the course: hence, this cannot be predicted in advance. However, if no Matlab exercises are delivered, the exam is compromised. Reference texts
- - Åke Björck, "Numerical Methods for Least Squares Problems", SIAM, 1996. ISBN-13: 978-0-898713-60-2. ISBN-10: 0-89871-360-9.
- Matlab Optimization Toolbox User's Guide.
- Teacher's notes.
