Click here to load reader

Outils de base en analyse numé · PDF file En analyse numérique, un certain nombre de calculs sont faits de manière répétitive. Exemple : Résoudre un système linéaire, Inverser

  • View
    0

  • Download
    0

Embed Size (px)

Text of Outils de base en analyse numé · PDF file En analyse numérique, un certain...

  • Outils de base en analyse numérique

    Sébastien Charnoz & Adrian Daerr

    Université Paris 7 Denis Diderot CEA Saclay

  • En analyse numérique, un certain nombre de calculs sont faits de manière répétitive. Exemple :

    Résoudre un système linéaire, Inverser une matrice, Calculer le déterminant, valeurs propres, vecteurs propres

    Interpoler une fonction Extrapoler une fonction Décomposer une fonction sur une base de fonctions (ex: TF)

    « fitter » des points de mesure avec des fonctions connues Etc…

    Des algorithmes performants existent souvent, mais qui ont chacun des spécificités. En fonction de nos besoins, il faudra choisir l’algorithme adapté

  • La plupart de ces outils « de base » sont souvent déjà programmés dans des librairies de calculs mathématiques (ex: NAG) .

    De manière générale, il n’est jamais bon de l’utiliser comme une « boîte noire » : En fonction du problème, en choisissant l’algorithme le plus adapté, on peut gagner du temps de calcul , ou mieux : éviter des instabilités numériques.

    Exemple 1: Si vous avez besoins de calculer l’inverse d’une matrice, et que sont déterminant est très proche de 0 (mais non exactement 0), le calcul sera très sensibles aux erreurs de troncatures de la machine. Dans ce cas il faut préférer une inversion itérative, plutôt qu’une inversion exacte…

    Exemple 2 : Si vous souhaitez décomposer une fonction sur une base de fonctions, ll vaut mieux bien connaître cette base, sinon vous ne saurez pas vraiment ce que vous faites… Souvent, une telle décomposition engendre des instabilités dans le schémas numérique en raison de la discrétisation etc…

  • Dans ce chapitre, nous aborderons 3 points :

    Systèmes linéaires

    Calcul matriciel, inversions etc…

    Interpolation et Extrapolation de fonctions

    Différentes méthodes, décomposition sur une base, moindres carrés etc..

    Générateurs de nombres pseudo-aléatoires

    Qu’est ce qu’un bon générateur ? Comment les construire ? etc…

  • LES SYSTEMES LINEAIRES

    En analyse numérique, résoudre un système linéaires, c’est résoudre

    bAx = Où A est une matrice (à priori) inversible , b est un vecteur, et X est le vecteur inconnu.

    Les questions attenantes à ce problème sont :

    Calculer A-1, Det(A), valeurs propres de A, vecteurs propres de A

    Une dizaine de méthodes existent, mais certains outils sont commun à de nombreuses méthodes… (Pivot de Gauss, Décomposition en matrice triangulaire, Méthode de substitution )

  • Un tel système est facilement soluble dans le cas où la matrice A est triangulaire…

    Pourquoi ?

    Par ce qu’une simple substitution itérative permet de résoudre facilement le système Ex :

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    =

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    4

    3

    2

    1

    4

    3

    2

    1

    44

    3433

    242322

    14131211

    000 00

    0

    b b b b

    x x x x

    a aa aaa aaaa

    On a alors :

    ( )

    ...

    1 /

    3443 33

    3

    4444

    etc

    axb a

    x

    abx

    −=

    =

    Matrice NxN avec N=4

  • ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    =

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    4

    3

    2

    1

    4

    3

    2

    1

    44

    3433

    242322

    14131211

    000 00

    0

    b b b b

    x x x x

    a aa aaa aaaa

    D’une manière générale, on peut trouver toutes les valeurs de Xi par la méthode itérative suivante (substitution arrière)

    ⎥ ⎦

    ⎤ ⎢ ⎣

    ⎡ −=

    =

    ∑ +=

    N

    ij jiji

    ii i

    nnnN

    xab a

    x

    abx

    1

    1

    / On calcule Xn, puis Xn-1, Xn-2 … X1

  • Une méthode similaire marche aussi pour un matrice triangulaire inférieure

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    =

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    ⎟⎟ ⎟ ⎟ ⎟

    ⎜⎜ ⎜ ⎜ ⎜

    4

    3

    2

    1

    4

    3

    2

    1

    44434241

    333231

    2221

    11

    0 00 000

    b b b b

    x x x x

    aaaa aaa

    aa a

    ⎥ ⎦

    ⎤ ⎢ ⎣

    ⎡ −=

    =

    ∑ −

    =

    1

    1

    1111

    1

    / i

    j jiji

    ii i xaba

    x

    abx On calcule X1, puis X2, X3 … XN

    Substitution avant

  • Dans de nombreuses méthodes, l’objectif est de transformer A pour la rendre Triangulaire, inférieure ou supérieurs, et ensuite calculer les solutions en utilisant une substitution (avant ou arrière si A est inférieure ou supérieure).

    2 grandes méthodes EXACTES:

    ELIMINATION DE GAUSS JORDAN

    Simple à comprendre, mais nécessite de modifier b en même temps que A Ne donne pas directement A-1 et les vecteurs propres

    FACTORISATION L U

    Un peu plus subtile, ne modifie pas b, donc on peut utiliser la même décomposition pour tout vecteur b, donne A-1 et les vecteurs propres

  • Gauss Jordan (pivot de Gauss)

    Prenons l’exemple suivant :

    On conserve la ligne L1, qui sert de pivot pour éliminer l'inconnue x des autres lignes; pour cela, on retire L1 à L2, et 3 fois L1 à L3. On obtient :

  • On conserve alors la ligne L2 qui sert de pivot pour éliminer y de la troisième ligne; pour cela, on remplace la ligne L3 par L3-L2. On trouve :

    On rèsoud finalement le système par substitution arrière (car on résoud d’abord Z , puis Y, puis X)

    Comment cela se passe avec des matrices ??

  • ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    ⎛ −=

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    ⎛ −

    8 1

    2

    853 231

    221

    z y x

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    ⎛ −=

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    − −

    2 3

    2

    210 410

    221

    z y x

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    − −=

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    ⎟ ⎟ ⎟

    ⎜ ⎜ ⎜

    − −

    1 3

    2

    200 410

    221

    z y x

    pivot

    pivot

    Le pivot parcours la diagonale

  • Pivot de Gauss 4 principes fondamentaux

    On ne change pas la solution lorsque l’on :

    1. permute 2 lignes

    2. permute 2 colonnes

    3. divise par un même terme non nul les éléments d’une ligne

    4. ajoute ou retranche à une ligne un certain nombre de fois une autre ligne

    Stratégie : Transformer le système linéaire en un système équivalent … facile à résoudre

    Triangulaire !

  • Pivot de Gauss : un autre exemple

    ⎪ ⎪ ⎩

    ⎪⎪ ⎨

    =++− =++− =++ −=−+

    6 2 8 2 3 0 3 6242

    432

    4321

    421

    321

    xxx xxxx xxx

    xxx

    pivot (1)

    Attention aux valeurs nulles du pivot

  • Pivot de Gauss : un exemple

    ⎪ ⎪ ⎩

    ⎪⎪ ⎨

    =++− =++− =++ −=−+

    6 2 8 2 3 0 3 6242

    432

    4321

    421

    321

    xxx xxxx xxx

    xxx

    L2 = L2-L1 a21/pivot (1)

  • Pivot de Gauss : un exemple

    ⎪ ⎪ ⎩

    ⎪⎪ ⎨

    =++− =++− =++ −=−+

    6 2 8 2 3 0 3 6242

    432

    4321

    421

    321

    xxx xxxx xxx

    xxx

    ⎪ ⎪ ⎩

    ⎪⎪ ⎨

    =++− =++− =+++ −=−+

    6 2 8 2 3 3 0 6242

    432

    4321

    432

    321

    xxx xxxx xxx

    xxx

    L2 = L2-L1 a21/pivot (1)

  • Pivot de Gauss : un exemple

    ⎪ ⎪ ⎩

    ⎪⎪ ⎨

    =++− =++− =++ −=−+

    6 2 8 2 3 0 3 6242

    432

    4321

    421

    321

    xxx xxxx xxx

    xxx

    ⎪ ⎪ ⎩

    ⎪⎪ ⎨

    =++− =++− =+++ −=−+

    6 2 71 2 4 7 0 3 0 6242

Search related