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, C^k 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.