Matrix computation and geometry
Presentation
Programme (detailed contents):
Part 1 :
Matrix computation for the least squares method:
- QR factorization thanks to the Gram-Schmidt and Householder method. Link with the orthogonal projection.
- Singular value decompositions and some properties: link with the euclidian norm and the approximation with a weak rank matrix.
- Solving some least square problems.
Part 2 :
Fitting:
- By cubic natural spline functions (interpolation, smoothing, and least squares).
Link with CAD:
- B-Splines, B-Spline curves, NURBS, NURBS curves, introduction to subdivision (de Casteljau’s algorithm, de Boor’s algorithm)
- Prospect: surfaces (tensor product)
Organisation:
This module is organized in course, tutorials and labworks.
Main difficulties for students:
- To go from discrete data to continuous functions.
- Piecewise functions.
Non-interpolatory functions.
Objectives
At the end of this module, the student will have understood and be able to explain (main concepts):
- QR factorization: the Gram-Schmidt and Householder methods
- Singular value decomposition
- Application to the least squares problem.
- Piecewise functions, Ck continuity, natural cubic splines and their local and global representations, basis of B-Splines, B-Spline curves and their control points.
- The extension to NURBS curves and to surface modelling in CAD.
The student will be able to:
- Determine the most efficient method to solve a least squares problem by identifying the characteristics of the problem.
- Determine and compute the interpolating spline, the smoothing spline, and the least squares spline of n given points.
- Build a B-Spline curve of n given points (analytically and by a subdivision algorithm (de Casteljau, de Boor))
Apprehend, modify a NURBS curve.
Needed prerequisite
Linear algebra, resolution of linear systems, use of matlab or python.
Form of assessment
The evaluation of outcome prior learning is made as a continuous training during the semester. According ot the teaching, the assessment will be different: as a written exam, an oral exam, a record, a written report, peers review...
Bibliography
L. D. Trefethen, D. Bau : « Numerical Linear Algebra », ISBN 0-89871-361-7.
A. Björck : « Numerical Methods for least squares problems », ISBN 0-89871-360-9.
Gilbert Demengel, Jean-Pierre Pouget : “Modèles de Bézier, des B-splines et des NURBS, ISBN2-7298-9806-9
Larry Schumaker : spline functions : basic theory, third edition, 2007, Cambridge University Press
Additional information
QR decomposition, Least square, Splines, B-Splines, NURBS, CAD.