Généralités - Mohamed Amine EL AFRIT
Déjà dans un seul espace vectoriel à dimension peu élevée, le formulaire de ......
A tout vecteur de on peut associer un scalaire positif appelé norme du vecteur ...
part of the document
tion.3
Dans le cas général, INCORPORER Equation.3 , maximum des valeurs singulières INCORPORER Equation.3 avec INCORPORER Equation.3 les valeurs propres (positives) de la matrice symétrique INCORPORER Equation.3 . (?)
Soit A une matrice carré quelconque n x n. Pour toutes normes de matrice induite, on a INCORPORER Equation.3 .
Conditionnement dune matrice inversible :
Considérons un système linéaire AX=b. L'expérience de Wilson met un évidence une instabilité des calculs dans certains cas. Si l'on modifie sensiblement les paramètres de la matrice A, ou du second membre b, on peut trouver des résultats complètement différends !
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3 avec INCORPORER Equation.3
Soit une matrice Q orthogonale : INCORPORER Equation.3 et INCORPORER Equation.3
Les bons conditionnements sont les petits conditionnements (au mieux 1 pour les matrices orthogonales).
Pour A symétrique : INCORPORER Equation.3 ; dans la cas général : INCORPORER Equation.3
Théorèmes sur le conditionnement :
Théorème : INCORPORER Equation.3 . On a INCORPORER Equation.3 . Théorème : INCORPORER Equation.3 . On a INCORPORER Equation.3 .
Remarque : Le conditionnement traduit l'amplification des grandeurs relatives.
Inverse numérique dune matrice :
Soit A une matrice inversible et A-1 son inverse théorique. M est un inverse de A du point de vue numérique si :
INCORPORER Equation.3 est petit, ce qui correspond à M=A-1
INCORPORER Equation.3 est petit, ce qui correspond à A=M-1
INCORPORER Equation.3 sont petits, ce qui correspond à INCORPORER Equation.3
On s'adapte au calcul que l'on veut faire. Notons que l'on résout rarement un système linéaire en calculant l'inverse INCORPORER Equation.3
Systèmes linéaires Ax=b : méthodes directes
Formules de Crammer
Cette méthode nécessite le calcul d'un déterminant, dont la complexité est en n!. La compléxité de la formule de Cramer est en n 2 n!. Par conséquent, cette méthode n'est pas utilisable en informatique.
Méthode du pivot de Gauss
À la kème étape : pour INCORPORER Equation.3 INCORPORER Equation.3 . On pose INCORPORER Equation.3 .
L'algorithme à une complexité en INCORPORER Equation.3 .
Le problème des coefficients diagonaux nuls : il faut permuter les lignes lorsque apparaît un zéro sur la diagonale.
Stratégie du pivot maximum partiel :
On permute la kème ligne et la ième ligne avec i tel que INCORPORER Equation.3 . Pour des raisons de stabilité numérique, on divise par le terme de la colonne k, qui a la plus grande valeur absolue.
Stratégie du pivot avec seuil :
On effectue une permutation uniquement des INCORPORER Equation.3 . Cependant cette méthode peut être mise en défaut. Il vaut mieux utiliser la méthode du pivot maximum partiel, qui n'est pas vraiment plus coûteuse en calcul.
Calcul de linverse
Une idée pour résoudre le sytème Ax=b serait de calculer linverse de A. En effet, on a INCORPORER Equation.3 .
Méthode de Shermann Morison
Soit A une matrice n x n, réelle inversible, dont on connaît linverse A-1 ; soit B une perturbation, on cherche à calculer INCORPORER Equation.3 .
On démontre que si INCORPORER Equation.3 , alors INCORPORER Equation.3 , avec INCORPORER Equation.3 .
On suppose maintenant que la perturbation ne modifie quun seul en INCORPORER Equation.3 : INCORPORER Equation.3 . Notons INCORPORER Equation.3 . Alors on trouve INCORPORER Equation.3 .
Elimination de Gauss
On applique la stratégie du pivot partiel maximum, au calcul de linverse.
On considère une matrice A inversible, de dimension n
On résout INCORPORER Equation.3 , ce qui revient à écrire INCORPORER Equation.3 . On procède par élimination de Gauss, ce qui donne une matrice triangulaire supérieure (complexité en n3). Ensuite, on réalise n remontées, une par vecteur INCORPORER Equation.3 (complexité en n 2).
En résumé, on a INCORPORER Equation.3 et INCORPORER Equation.3 une matrice triangulaire supérieure.
On veut traiter tous les seconds membres en une seule passe ; pour cela on considère la matrice n x 2n suivante : INCORPORER Equation.3 qui après calculs donne INCORPORER Equation.3 .
On donne ici un exemple décriture en langage de description algorithmique :
Procédure pivot ( k , l : entiers ; OK : booléens )
Début
Max := INCORPORER Equation.3 ;
l := k ;
Pour i := k+1 à n faire
Si max < INCORPORER Equation.3
Alors
Début
Max := INCORPORER Equation.3 ;
l := i ;
Fin ;
OK := Max > ( ;
Fin ;
Procédure permuter ( k , l : entiers )
Début
Si INCORPORER Equation.3
Alors
Pour j := k à 2n faire
Début
c := INCORPORER Equation.3 ;
INCORPORER Equation.3 : = INCORPORER Equation.3 ;
INCORPORER Equation.3 := c ;
Fin ;
Fin ;
On donne maintenant le programme principal, réalisant le calcul de linverse.
Début
Initialiser A et lire ( ;
/* triangularisation */
Pour k := 1 à n faire
Début
Pivot (k , l , OK ) ;
Si non(OK)
Alors
Début
Ecrire « matrice non inversible » ;
Exit echec ;
Fin ;
Permuter ( k , l ) ;
Pour j := k+1 à 2n faire
INCORPORER Equation.3 ;
Pour i := k+1 à n faire
Pour j := k+1 à 2n faire
INCORPORER Equation.3 ; Fin ;
/* n remontées */
Pour k := 1 à n faire
Pour i := n-1 à 1 par pas de -1 faire
Début
s := 0 ;
Pour j := i+1 à n faire
INCORPORER Equation.3 ;
INCORPORER Equation.3 ;
Fin ;
Fin ;
Remarques :
Choix du pivot : pour des raisons de stabilité numérique, on divise toujours par le terme de la colonne k qui a la plus grande valeur absolue (Cf. Pivot partiel maximum).
Recherche du pivot : si la plus grande valeur absolue est inférieure à la précision machine (, alors on arrête en disant que la matrice nest pas inversible à ( près (test dinversibilité informatique). Cependant, elle peut très bien être inversible du point de vue mathématique !
Factorisation A=LU
Soit A une matrice régulière, de dimension n.
Lien avec la méthode de Gauss
On applique la méthode de Gauss sans pivoter. U est une matrice triangulaire supérieure réelle, telle que INCORPORER Equation.3 . On donne la définition des matrices INCORPORER Equation.3 avec INCORPORER Equation.3 pour INCORPORER Equation.3 .
On démontre que linverse des Jk existe et que INCORPORER Equation.3 est une matrice triangulaire inférieure, avec des 1 sur la diagonale. En fait, on a INCORPORER Equation.3 .
Calcul algorithmique des coefficients de L et de U
On procède par identification en utilisant les propriétés de L (triangulaire inférieure avec une diagonale de 1) et de U (triangulaire supérieure). On cherche un algorithme par ligne donnant les INCORPORER Equation.3 .
Pour i := 1 à n faire
Début
Pour j := 1 à i-1 faire
INCORPORER Equation.3 ;
/* avec INCORPORER Equation.3 */
Pour j := i à n faire
INCORPORER Equation.3 ;
Fin ;
Remarque : L et U écrasent la matrice A.
Cas particulier des matrices à « structure bande »
INCORPORER Equation.3
La largeur de la bande est W = P+Q+1
On ne stocke dans une structure de donnée appropriée que la bande, soit un O(W.N), ce qui est intéressant si W( N)
INCORPORER Equation.3 , avec Q une matrice orthogonale et INCORPORER Equation.3 , avec INCORPORER Equation.3 une matrice triangulaire supérieure.
Théorème : minimiser INCORPORER Equation.3 pour N supérieur à 3 ou 4
Soit INCORPORER Equation.3 avec INCORPORER Equation.3 de dimension N. Le vecteur INCORPORER Equation.3 minimise INCORPORER Equation.3 si et seulement si INCORPORER Equation.3 est solution de INCORPORER Equation.3 .
Obtention de la factorisation A = QR par Householder
Définition des matrices de Householder
Soit u un vecteur unitaire INCORPORER Equation.3 de dimension m. On définit la matrice de Householder de dimensio INCORPORER Equation.3 INCORPORER Equation.3 . INCORPORER Equation.3 est symétrique et orthogonale INCORPORER Equation.3 . On note également INCORPORER Equation.3 en posant INCORPORER Equation.3 .
Propriété fondamentale des matrices de Householder
Soit a un vecteur de dimension m, non nul. Il existe H, une matrice de Householder, telle que INCORPORER Equation.3 avec ( un réel.
Preuve :
INCORPORER Equation.3
On choisit le signe de ( : le signe opposé à a1.
On pose INCORPORER Equation.3 .
On choisit INCORPORER Equation.3 .
Principe de l'algorithme de factorisation
On veut obtenir la matrice INCORPORER Equation.3 à partir de la matrice INCORPORER Equation.3 . On procède colonne par colonne.
On rappelle la géométrie de INCORPORER Equation.3 .
Occupons nous de la première colonne de INCORPORER Equation.3 . Il existe une matrice de Householder INCORPORER Equation.3 de dimension m telle que INCORPORER Equation.3 , où la première colonne de INCORPORER Equation.3 est INCORPORER Equation.3 .
On s'intéresse maintenant à la 2ème colonne. Il existe une matrice de Householder INCORPORER Equation.3 de dimension m-1 telle que INCORPORER Equation.3 , avec INCORPORER Equation.3 . Ainsi la première colonne de INCORPORER Equation.3 reste inchangée par rapport à INCORPORER Equation.3 et l'on a fabriqué la deuxième colonne INCORPORER Equation.3 .
Il vient INCORPORER Equation.3 On itère la méthode N fois et il l'on obtient la factorisation INCORPORER Equation.3 avec INCORPORER Equation.3 et INCORPORER Equation.3 .
Obtention de INCORPORER Equation.3 au cours de l'algorithme de factorisation
En vérité, on peut habilement intégrer le calcul de INCORPORER Equation.3 à l'algorithme précédent. Cela est simple, il suffit de rajouter une N+1 colonne à la matrice initiale, INCORPORER Equation.3 . Ainsi après N itérations, on obtiendra le résultat INCORPORER Equation.3 toujours dans la même colonne.
Obtention de la factorisation A = QR par Givens
(
)
Résolution des équations non linéaires
Méthode de dichotomie
Considérons une fonction f en dimension 1. On isole une racine unique dans un intervalle INCORPORER Equation.3 . On divise l'intervalle en deux à chaque étape, on identifie le sous - intervalle contenant la racine en comparant le signe du milieu INCORPORER Equation.3 avec INCORPORER Equation.3 . Et on réitère. La précision obtenue au bout de k itérations est INCORPORER Equation.3 . La méthode de la dichotomie est robuste, mais n'est pas généralisable à la dimension n.
Généralités
Méthode convergente, d'ordre p
Une méthode itérative est convergente : INCORPORER Equation.3 solution, si INCORPORER Equation.3 . On dit que la méthode est dite d'ordre p.
Théorème du point fixe
Soit INCORPORER Equation.3 k-lipschitzienne contractante : INCORPORER Equation.3 avec INCORPORER Equation.3 . Soit INCORPORER Equation.3 et INCORPORER Equation.3 . Alors on a INCORPORER Equation.3 tel que INCORPORER Equation.3 .
Pour appliquer ce théorème, il suffit de vérifier qu'il existe une boule INCORPORER Equation.3 sur laquelle, on a la propriété INCORPORER Equation.3 avec INCORPORER Equation.3 . L'inégalité des accroissement finis nous donne INCORPORER Equation.3 .
Méthode d'itérations successives pour résoudre INCORPORER Equation.3
Posons INCORPORER Equation.3 . Si INCORPORER Equation.3 est point fixe de ( alors INCORPORER Equation.3 est solution de INCORPORER Equation.3 . On définit alors la récurrence suivante : INCORPORER Equation.3 .
Méthode de Newton - tangente
En dimension 1 pour des réels, INCORPORER Equation.3 . La méthode de la tangente est d'ordre 2. Inconvénient, si on part d'une certaine boule , la méthode converge, sinon l'algorithme peut osciller et ne pas converger ! Cette méthode se généralise à la dimension n. Pour des complexes, on peut employer deux fois cette méthode.
Méthode de Newton - Raphson
En dimension n, INCORPORER Equation.3 où INCORPORER Equation.3 avec INCORPORER Equation.3 (matrice jacobienne). INCORPORER Equation.3 est inversible et permet le calcul de INCORPORER Equation.3 à chaque itération. Si on part d'une certaine boule au voisinage de la solution, la méthode est convergente d'ordre 2. Si on fait un choix au hasard pour INCORPORER Equation.3 , il faut prévoir un test d'arrêt au bout de 100 itérations par exemple pour éviter le cas d'oscillations ! La complexité globale est en n3.
Variante si m grand
La complexité globale passe en n2 après la première utilisation
Factorisation PA=LU
Méthode de Bairstow dans le cas des polynômes
On cherche à résoudre INCORPORER Equation.3 , avec INCORPORER Equation.3 .
Méthode
On cherche INCORPORER Equation.3 qui divise P. On a INCORPORER Equation.3 (division euclidienne). Pour déterminer les coefficients ( et (, on cherche une racine de l'application INCORPORER Equation.3 .
On veut appliquer la méthode de Newton - Raphston en dimension 2. Il faut d'abord calculer la matrice jacobienne J : on établit des formules par récurrence assez complexes
Puis, on applique effectivement la méthode de Newton - Raphston, à partir de INCORPORER Equation.3 , qui donne INCORPORER Equation.3 (sous réserve que l'on se trouve initialement dans une boule suffisamment proche de la solution pour que la méthode soit effectivement convergente).
Finalement, le polynôme INCORPORER Equation.3 fournit deux racines de P. On réitère la méthode sur INCORPORER Equation.3 tel que INCORPORER Equation.3 . Cependant, les itérations successives entraînent une perte progressive de la précision.
Variante
Pour ne pas choisir INCORPORER Equation.3 complètement au hasard, une méthode consiste à sélectionner une centaine de couples et à choisir, pour débuter l'algorithme, celui qui rend le polynôme minimum.
Amélioration de la précision
La racine obtenue étant assez proche de la racine réelle, on effectue la méthode de la tangente pour améliorer la précision. Tous les 4 ou 5 coups, on améliore la précision avec la précision avec la méthode de la tangente. Cette dernière méthode ne s'applique qu'aux racines réelles (on applique deux fois la méthode pour les racines complexes).
Méthode de Bernouilli pour le calcul de la racine dominante si elle est unique
???
Valeurs propres et vecteurs propres
Conditionnement
Théorème
Si A est diagonalisable en INCORPORER Equation.3 avec P la matrice de passage. Pour tout INCORPORER Equation.3 , pour toute valeur propre ( de INCORPORER Equation.3 , il existe une valeur propre (' de A telle que INCORPORER Equation.3 . Le meilleur cas possible est A symétrique, la matrice de passage est orthogonale et son conditionnement égale à 1.
Bissection de Givens - Householder
Méthode
Chercher une matrice tridiagonale semblable à A ayant même valeur propre.
Chercher ces valeurs propres.
Tridiagonalisation
Cet algorithme utilise des matrices de Householder. On procède bloc par bloc, en dimension décroissante.
INCORPORER Equation.3
1ère étape : INCORPORER Equation.3 avec INCORPORER Equation.3 et INCORPORER Equation.3 la matrice de Householder. On découpe INCORPORER Equation.3 en bloc selon le schéma : INCORPORER Equation.3 . Par la suite, INCORPORER Equation.3 . On sait trouver INCORPORER Equation.3 tel que INCORPORER Equation.3 avec ( un réel. Voilà ce qui en définitive va rendre la matrice tridiagonale.
On applique la même méthode que précédemment avec une dimension en moins
On réitère la méthode n fois en totalité. Finalement, on obtient INCORPORER Equation.3 où INCORPORER Equation.3 est une matrice tridiagonale semblable à A.
Optimisation des calculs
On intègre le calcul de ( dans la méthode et on optimise le produit des 3 matrices.
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3 et INCORPORER Equation.3
INCORPORER Equation.3
Méthode de recherche des valeurs propres
à partir de la matrice tridiagonale M, on va construire le polynôme caractéristique dont les racines sont précisément les valeurs propres.
Soit bi les coefficients diagonaux, et ci les coefficients sous-diagonaux. On a INCORPORER Equation.3 , INCORPORER Equation.3 et pour tout INCORPORER Equation.3 , INCORPORER Equation.3 . Attention au cas particulier où un ci est nul ! Il faut distinguer deux polynômes caractéristiques.
INCORPORER Equation.3 est le polynôme caractéristique de Mi où Mi est la sous-matrice de dimension i extraite de M de telle sorte que Mn = M.
Le coefficient dominant de Pi est INCORPORER Equation.3 .
Si INCORPORER Equation.3 alors INCORPORER Equation.3 et INCORPORER Equation.3 sont de signe opposé.
Pi a exactement i racines réelles distinctes qui séparent les i+1 racines de Pi+1.
Bissection de Givens
Soit ( un réel. Soit INCORPORER Equation.3 . On définit INCORPORER Equation.3 le nombre de changement de signe dans INCORPORER Equation.3 . Alors INCORPORER Equation.3 représente le nombre de racines de Pi qui sont inférieures et distinctes de (.
On ordonne les (i de manière croissante : INCORPORER Equation.3 . Considérons un intervalle INCORPORER Equation.3 contenant (i. Soit INCORPORER Equation.3 (bissection). On calcule INCORPORER Equation.3 . Si INCORPORER Equation.3 , alors INCORPORER Equation.3 sinon INCORPORER Equation.3 . On réitère
Une variante pour éviter les overflows
(
)
Méthode de la puissance itérée
Soit A une matrice quelconque, éventuellement à coefficient complexe.
Théorème
Soit A diagonalisable dont la valeur propre (1 (de plus grand module) est unique. Soit INCORPORER Equation.3 un vecteur non orthogonal au sous-espace propre à gauche associé à (, tel que INCORPORER Equation.3 . On suppose INCORPORER Equation.3 , INCORPORER Equation.3 . Alors, on a : INCORPORER Equation.3 le vecteur propre associé à (1 et INCORPORER Equation.3 pour tout j tel que INCORPORER Equation.3 .
En pratique !
En pratique l'hypothèse " INCORPORER Equation.3 un vecteur non orthogonal au sous-espace propre à gauche associé à (" n'est pas nécessaire, car le phénomène d'arrondi permet de s'éloigner du cas orthogonal !
Si A n'est pas diagonalisable, la méthode fonctionne encore, mais la convergence est plus lente.
En pratique, on choisit la norme infinie, et INCORPORER Equation.3 .
Méthode de la déflation
On suppose maintenant que l'on connaît (1 et u1, avec INCORPORER Equation.3 et la base de vecteur propre INCORPORER Equation.3 . On cherche (2 et u2.
On suppose INCORPORER Equation.3 (A symétrique ?). Le principe est simple, on forme la matrice B tel que INCORPORER Equation.3 . Cette matrice possède les mêmes valeurs propres, les mêmes vecteurs propres, sauf (1 et u1. Par conséquent, si l'on applique la méthode de la puissance itérée, on va obtenir (2 et u2.
En pratique, on ne calcule pas B
La seule différence avec la méthode de la puissance itérée est dans la formule INCORPORER Equation.3 . (Phénomène d'arrondi compensatoire inverse
)
Cette méthode permet en réitérant de trouver (3, (4 mais pas au delà, car il y a répercussion des erreurs d'arrondi.
Méthode de la puissance itérée inverse
Cette méthode permet de calculer la plus petite valeur propre (n et son vecteur propre un. On prend INCORPORER Equation.3 et on applique la méthode de la puissance itérée à B, ce qui donne INCORPORER Equation.3 et INCORPORER Equation.3 .
Pour trouver la valeur propre la plus proche de (, on applique la méthode de la puissance itérée à INCORPORER Equation.3 , ce qui donne INCORPORER Equation.3 et INCORPORER Equation.3 .
Approximation polynomiale & Intégration numérique
Approximations polynomiales
Polynômes orthogonaux
Soit INCORPORER Equation.3 avec INCORPORER Equation.3 un poids. Considérons INCORPORER Equation.3 avec Pi un polynôme de degrés i. Alors INCORPORER Equation.3 pour INCORPORER Equation.3 .
Legendre
INCORPORER Equation.3 , INCORPORER Equation.3 , INCORPORER Equation.3 .
INCORPORER Equation.3 , INCORPORER Equation.3 , INCORPORER Equation.3 .
INCORPORER Equation.3 .
Laguerre
INCORPORER Equation.3 , INCORPORER Equation.3 , INCORPORER Equation.3 .
INCORPORER Equation.3 , INCORPORER Equation.3 , INCORPORER Equation.3
INCORPORER Equation.3 .
Hermite
INCORPORER Equation.3 .
INCORPORER Equation.3 , INCORPORER Equation.3 , INCORPORER Equation.3 .
INCORPORER Equation.3 .
Tchebychev
INCORPORER Equation.3 .
INCORPORER Equation.3 , INCORPORER Equation.3 , INCORPORER Equation.3 .
formule explicite : INCORPORER Equation.3 . INCORPORER Equation.3 a n zéros, INCORPORER Equation.3 pour INCORPORER Equation.3 et n+1 extrema sur INCORPORER Equation.3 .
INCORPORER Equation.3 , INCORPORER Equation.3 .
Théorèmes
Soit INCORPORER Equation.3 . Alors INCORPORER Equation.3 .
Soit INCORPORER Equation.3 avec INCORPORER Equation.3 et ( fixé. Alors INCORPORER Equation.3 INCORPORER Equation.3 .
Soit INCORPORER Equation.3 avec INCORPORER Equation.3 et ( fixé. Alors INCORPORER Equation.3 INCORPORER Equation.3 .
Algorithme de Remes
Soient un intervalle INCORPORER Equation.3 , et un fonction INCORPORER Equation.3 . INCORPORER Equation.3 . On cherche un polynôme P de degrés inférieur ou égal à n tel que INCORPORER Equation.3 pour tout polynôme Q de degrés inférieur ou égal à n.
Théorème
On considère INCORPORER Equation.3 n+2 points de INCORPORER Equation.3 .
INCORPORER Equation.3 (equioscillations)
INCORPORER Equation.3 pour tout Q tel que INCORPORER Equation.3 , c'est-à-dire que P est la meilleure approximation pour les points INCORPORER Equation.3 , mais pas meilleure approximation uniforme.
Corollaire
Posons INCORPORER Equation.3 . Si INCORPORER Equation.3 alors INCORPORER Equation.3 pour tout polynôme Q de degrés n. P est la meilleure approximation uniforme sur INCORPORER Equation.3 .
Algorithme
Du point de vue informatique, on se donne une tolérance INCORPORER Equation.3 , d'où si INCORPORER Equation.3 , alors pour tout polynôme Q de degrés n INCORPORER Equation.3
Choisir n+2 points.
Si condition vrai, alors fin.
Sinon, échange : on introduit y en respectant le principe d'oscillation
???
On recommence avec la nouvelle famille de points.
On démontre que l'algorithme converge.
Approximation par interpolation
Considérons n+1 points INCORPORER Equation.3 . Soit P un polynôme de degrés n tel que INCORPORER Equation.3 . Un tel polynôme existe et on démontre qu'il est unique. On définit INCORPORER Equation.3 un polynôme de degrés n. On a INCORPORER Equation.3 . Alors INCORPORER Equation.3 .
Formule de Gregory - Newton
Soit h le pas. INCORPORER Equation.3 . On définit INCORPORER Equation.3 , INCORPORER Equation.3 ,
On commence par calculer les INCORPORER Equation.3 pour INCORPORER Equation.3 . La formule de Gregory - Newton définit le polynôme P de degrés n INCORPORER Equation.3 avec INCORPORER Equation.3 et INCORPORER Equation.3 . Remarquons que si INCORPORER Equation.3 et INCORPORER Equation.3 . On estime l'erreur INCORPORER Equation.3 avec INCORPORER Equation.3 . INCORPORER Equation.3 ne converge pas vers f à cause des INCORPORER Equation.3 . Aussi pour avoir la convergence uniforme sur INCORPORER Equation.3 , on réalise l'interpolation sur N sous-segments de longueur INCORPORER Equation.3 avec 5 ou 6 points (en pratique).
Intégration numérique
Si INCORPORER Equation.3 converge uniformément vers f sur INCORPORER Equation.3 , alors INCORPORER Equation.3 tend vers INCORPORER Equation.3 . On partage l'intervalle INCORPORER Equation.3 en N sous-segments INCORPORER Equation.3 de longueur INCORPORER Equation.3 , avec INCORPORER Equation.3 et INCORPORER Equation.3 .
Stabilité
Les formules sont de la forme INCORPORER Equation.3 avec nécessairement INCORPORER Equation.3 .
La méthode est stable si pour tout h, il existe A tel que INCORPORER Equation.3 , avec INCORPORER Equation.3 .
Théorème : Si INCORPORER Equation.3 alors la formule est stable.
Formule des rectangles
Sur chaque sous-segment INCORPORER Equation.3 , on approche f avec un polynôme de degrés 0, c'est-à-dire par une constante égale à la valeur milieu. Donc INCORPORER Equation.3 . On estime l'erreur INCORPORER Equation.3 . Cette méthode est d'ordre 2, et non d'ordre 1 comme on le croit souvent !
Formule des trapèzes
Les polynômes qui interpolent sont de degrès 1, ce sont des droites. INCORPORER Equation.3 . On estime l'erreur INCORPORER Equation.3 . Cette méthode est d'ordre 2 et n'est pas meilleur que celle des rectangles (sinon moins bonne).
Formule de Simpson
INCORPORER Equation.3 . La méthode est d'ordre 4.
Spline
Théorème
Soi INCORPORER Equation.3 . Il existe une et une seule fonction INCORPORER Equation.3 sur INCORPORER Equation.3 tel que INCORPORER Equation.3 . Sur chaque segment INCORPORER Equation.3 , INCORPORER Equation.3 est un polynôme de degrés 2k-1 avec INCORPORER Equation.3 qui existe et INCORPORER Equation.3 , de telle sorte donc que INCORPORER Equation.3 soit de classe 2k-2 sur INCORPORER Equation.3 .
Spline cubique (k = 2)
(
)
Équations différentielles
Généralités
Problème de Cauchy
Soit INCORPORER Equation.3 , continue, telle que INCORPORER Equation.3 . étant donnée une condition initiale INCORPORER Equation.3 , on cherche INCORPORER Equation.3 de classe C1 telle que INCORPORER Equation.3 , problème de Cauchy dimension M et d'ordre 1.
Le problème de Cauchy de dimension M et d'ordre P : INCORPORER Equation.3 . On se ramène au problème de Cauchy d'ordre 1 en posant INCORPORER Equation.3 , de dimension INCORPORER Equation.3 .
Théorème (K - lipschitzienne)
Si il existe K tel que INCORPORER Equation.3 , alors le problème de Cauchy d'ordre 1 possède une solution unique.
Méthode de résolution numérique
On se place dans le cadre de ce théorème, et l'on cherche à calculer une solution. On divise l'intervalle INCORPORER Equation.3 en N de telle sorte que INCORPORER Equation.3 ; INCORPORER Equation.3 avec le pas INCORPORER Equation.3 . On voudrait que les INCORPORER Equation.3 soient proches de INCORPORER Equation.3 . La formule générale employée pour la résolution numérique des équations différentielles est INCORPORER Equation.3 .
Stabilité
On introduit une perturbation, INCORPORER Equation.3 , et l'on observe le comportement de la méthode. Posons INCORPORER Equation.3 . La méthode est stable si et seulement si INCORPORER Equation.3 .
Consistance
La méthode est consistante si et seulement si INCORPORER Equation.3 . La méthode est consistante d'ordre p si et seulement si INCORPORER Equation.3 .
Convergence
La méthode est convergente si et seulement si INCORPORER Equation.3 . Il y a convergence d'ordre p si et seulement si INCORPORER Equation.3 .
Si la méthode est stable et consistante [d'ordre p], alors la méthode est convergente [d'ordre p].
Théorème stabilité
Si il existe K tel que INCORPORER Equation.3 , c'est-à-dire si ( est K - lipschitzienne, alors la méthode est stable.
Théorème consistance
Si INCORPORER Equation.3 , on a consistance d'ordre 1.
Si de plus, INCORPORER Equation.3 , alors on a consistance d'ordre 2.
Si de plus, INCORPORER Equation.3 , alors on a consistance d'ordre 3.
Etc.
Méthode de Euler
INCORPORER Equation.3 , ordre 1, stabilité acquise (( et f lipschitzienne). Intuitivement, on traduit la formule du taux d'accroissement INCORPORER Equation.3 . La formule sera donc INCORPORER Equation.3 .
Méthode du développement de Taylor
INCORPORER Equation.3 , consistante de l'ordre que l'on veut, stabilité acquise. Mais en pratique les calculs de dérivées rend la méthode impraticable !
Méthode de Runge - Kutta
Ordre 2
On cherche INCORPORER Equation.3 . L'ordre 1 impose INCORPORER Equation.3 et l'ordre 2 impose INCORPORER Equation.3 .
Si INCORPORER Equation.3 , alors INCORPORER Equation.3 , d'où la formule INCORPORER Equation.3 . Soit le prédicteur INCORPORER Equation.3 , la méthode s'écrit : INCORPORER Equation.3 La méthode est d'ordre 2, et correspond à une amélioration de Euler : le taux d'accroissement est calculé pour le point milieu INCORPORER Equation.3 .
Si INCORPORER Equation.3
Ordre 4
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
INCORPORER Equation.3
Choix de h
On se donne une tolérance ( > 0.
On choisit arbitrairement h et on applique la méthode.
On recommence avec INCORPORER Equation.3 . Si le résultat obtenu pour un pas divisé par 2, est à ( près celui obtenu pour un pas de h alors le pas est bon, sinon on réitère. Attention il faut comparer INCORPORER Equation.3 et INCORPORER Equation.3 .
Méthode à pas multiples
(
)
Équations différentielles du 2ème ordre (avec conditions aux bords)
Problème de Dirichlet
Méthode des différences finies
Méthode des éléments finis
Transformée de Fourier discrète
Algorithme de TFD rapide
(
)
Application
(
)
Cette partie a été rédigée en privilégiant les notes de cours plutôt que celle de TD, où les notations et les méthodes diffèrent sur quelques points.
vecteur propre à gauche pour ( si INCORPORER Equation.3
vecteur propre à gauche pour ( si INCORPORER Equation.3
Esnard Aurélien Algorithmique Numérique
B
A
C
B
A
C
