Quadrature, élémentaire et composée N fois. Ordre m.
Expression et majoration de l'erreur à l'aide des noyaux de Peano : si Q est d'ordre m alors l'erreur pour f égale l'integrale de K indice (m+1) fois la dérivée (m+1)-ieme de f.
Exemple : méthodes des rectangles, du point milieu, des trapèzes, de Simpson.
Comment construire des méthodes d'ordre élévé ? Déterminant de Van der Mond, méthodes de Newton-Cotes.
Que ce passe-t-il en cas de petites erreurs dans l'évaluation de f ? Stabilité numérique.
Comment accélérer la convergence ? Développement asymptotique, formule d'Euler-Mac Laurin (sans preuve), méthode de Romberg. (21 septembre)
Introduction. Résoudre Ax=b sans calculer l'inverse de A. Quand A n'est pas carré, ou n'est pas de rang égale à sa taille, que faire ? Pour un système sur-dimensionné (par exemple plus d'équations que d'inconnues) il se peut qu'il n'y ait pas de solutions : chercher alors à minimiser l'erreur revient à projeter le second membre b sur l'image de A. Pour un système sous-dimensionné (plus d'inconnues que d'équations), les solutions forment un espace affine non réduit à un point. Trouver la plus petite solution revient à à projeter 0 sur cet espace affine.
Gauss, LU, Cholesky. Méthodes en n-1 étapes pour une matrice carré de taille n, visant à se ramener à un système triangulaire, donc facile à résoudre en n^2+O(n) opérations arithmétiques (oa). LU permet de résoudre économiquement plusieurs systèmes succéssivement. La factorisation A=LU se fait en place (pas de stokage mémoire supplémentaire), en (2/3)n^3+O(n^2) oa. Choleski est la variante adaptée aux matrices symétriques définies positive, elle utilise n racines carrées et coûte moitié moins d'oa.
Householder, QR. Méthodes en n-1 étapes comme Gaus et LU, mais on remplace les transvections par d'autres pertubations de rang 1 de l'identité qui sont plus stables, les symétries hyperplanes othogonales, symétries de Householder. On obtient ainsi une factorisation A=QR avec Q othogonale et R triangulaire supérieure, en (4/3)n^3+O(n^2) oa. Il n'est pas utile de stocker Q dans une matrice nxn, il suffit de garder en mémoire les éléments beta et v qui définissent chacune des symétries de Householder par I+beta*v*v^T. On peut alors calculer les produits Qy ou Q^Ty de Q ou Q^T par un vecteur y de taille n en 2n^2+O(n) oa.
Lors du calcul des éléments beta et v, il convient de prendre garde au mauvais conditionnement d'éventuelles soustractions de nombres positifs. Le truc de la quantité conjuguée permet de surmonter cette difficulté.
Aux références déjà données ci-dessus, on peut ajouter Matrix Computations, de G.H. Golub et C.F. Van Loan.
(12 octobre)
modifié le 16 oct. 2006