Click here to load reader

MACS1. Cours d’ Analyse numé halpern/teaching/MACS1_2010/systemes.pdf · PDF fileLe Calcul Scientifique se propose de mettre un problème issu de la phy- sique, de l’économie,

  • View
    220

  • Download
    0

Embed Size (px)

Text of MACS1. Cours d’ Analyse numé halpern/teaching/MACS1_2010/systemes.pdf · PDF...

  • MACS1.

    Cours d Analyse numrique

    L. Halpern

    24 septembre 2010

  • 2

  • Table des matires

    I Introduction gnrale 7

    II Rsolution numrique de systmes linaires 11

    1 Gnralits 13

    1.1 Rappels sur les matrices . . . . . . . . . . . . . . . . . . . . . 13

    1.1.1 Dfinitions . . . . . . . . . . . . . . . . . . . . . . . . . 13

    1.1.2 Cas particulier de matrices . . . . . . . . . . . . . . . . 15

    1.1.3 Dterminants . . . . . . . . . . . . . . . . . . . . . . . 15

    1.1.4 Produit de matrices par blocs . . . . . . . . . . . . . . 16

    1.2 Rduction des matrices . . . . . . . . . . . . . . . . . . . . . . 17

    1.3 Algorithme, complexit . . . . . . . . . . . . . . . . . . . . . . 18

    1.4 Systmes linaires, dfinitions . . . . . . . . . . . . . . . . . . 19

    1.5 Norme de vecteurs et de matrices . . . . . . . . . . . . . . . . 22

    1.6 Conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . 25

    1.6.1 Erreur darrondi . . . . . . . . . . . . . . . . . . . . . . 25

    1.6.2 Conditionnement dun problme . . . . . . . . . . . . . 26

    1.6.3 Conditionnement dune matrice . . . . . . . . . . . . . 26

    1.7 Notion de prconditionnement . . . . . . . . . . . . . . . . . . 29

    2 Mthodes directes 31

    2.1 Mthode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . 31

    2.1.1 Systmes triangulaires . . . . . . . . . . . . . . . . . . 31

    2.1.2 Dcomposition LU : un rsultat thorique . . . . . . . 33

    2.1.3 Dcomposition LU : mthode de Gauss . . . . . . . . 35

    2.1.4 Mthode de Crout . . . . . . . . . . . . . . . . . . . . 39

    2.1.5 Complexit de lalgorithme . . . . . . . . . . . . . . . . 40

    2.1.6 mthode du pivot partiel . . . . . . . . . . . . . . . . . 41

    2.2 Mthode de Cholewski . . . . . . . . . . . . . . . . . . . . . . 45

    3

  • 3 Mthodes itratives 473.1 Suite de vecteurs et de matrices . . . . . . . . . . . . . . . . . 473.2 Mthode de Jacobi, Gauss-Seidel, S.O.R. . . . . . . . . . . . . 483.3 Rsultats gnraux de convergence . . . . . . . . . . . . . . . 503.4 Cas des matrices hermitiennes . . . . . . . . . . . . . . . . . . 513.5 Cas des matrices tridiagonales . . . . . . . . . . . . . . . . . . 513.6 Matrices diagonale dominante . . . . . . . . . . . . . . . . . 513.7 La matrice du laplacien . . . . . . . . . . . . . . . . . . . . . . 523.8 Complexit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

    4 Calcul des valeurs propres et vecteurs propres 554.1 Gnralits, outils matriciels . . . . . . . . . . . . . . . . . . . 55

    4.1.1 Matrices de Householder . . . . . . . . . . . . . . . . . 554.1.2 Quotients de Rayleigh . . . . . . . . . . . . . . . . . . 564.1.3 Conditionnement dun problme de valeurs propres . . 57

    4.2 Dcompositions . . . . . . . . . . . . . . . . . . . . . . . . . . 574.2.1 Dcomposition QR . . . . . . . . . . . . . . . . . . . . 574.2.2 Tridiagonalisation dune matrice symtrique . . . . . . 59

    4.3 Algorithmes pour le calcul de toutes les valeurs propres dunematrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.3.1 Mthode de Jacobi . . . . . . . . . . . . . . . . . . . . 594.3.2 Mthode de Givens ou bisection . . . . . . . . . . . . . 60

    4.4 Mthode de la puissance itre . . . . . . . . . . . . . . . . . . 62

    4

  • Bibliographie

    [1] G. Allaire, S.M. Kaber, Algbre linaire numrique. Ellipses, 2002

    [2] M. Schatzmann, Numerical Analysis, A Mathematical Introduc-tion.Oxford University Press, 2002.

    [3] P. Lascaux, R. Theodor,Analyse numrique matricielle applique lartde lingnieur. Masson.

    [4] E. Hairer : consulter la page http ://www.unige.ch/ hairer/polycop.html

    5

  • 6

  • Premire partie

    Introduction gnrale

    7

  • Le Calcul Scientifique se propose de mettre un problme issu de la phy-sique, de lconomie, de la chimie, de lingnierie, en quations, cest ltapede la modlisation, et de les rsoudre. Ces quations sont souvent trs com-plexes, et font intervenir normment de paramtres. Elles sont en gnralimpossible rsoudre de faon exacte (comme le serait une quation diffren-tielle du second degr par exemple, modlisant le mouvement dun pendulede longueur l :

    x +g

    lsinx = 0. (1)

    Le problme linaris pour de petits mouvements du pendule scrit

    x +g

    lx = 0 (2)

    peut se rsoudre sous la forme x = x0cos

    glt + x0sin

    glt. On peut alors

    calculer x(t) pour tout temps de faon exacte (modulo les erreurs darrondi).Par contre on ne connait pas de solution exacte de lquation (1). On estdonc amen en chercher une solution approche en un certain nombre depoints (cf cours de mise niveau) : On souhaite calculer x dans lintervalle]0, T [, connaissant x(0) = x0 et x

    (0) = x0. On se donne une suite dinstantstn = nt, avec T = Nt, et on crit une approximation de la drive seconde

    x(tn) =x(tn+1) 2x(tn) + x(tn1)

    t2+ O(t2) (3)

    et on remplace lquation par

    yn+1 2yn + yn1t2

    +g

    lsin(yn) = 0. (4)

    Puisque lon a une quation de rcurrence 2 niveaux, il faut se donner y0et y1. Nous verrons plus tard comment calculer y1. Lquation (4) est uneapproximation de lquation (1). Il est souhaitable que

    1. (4) ait une solution unique,

    2. yn x(tn), cest la consistance,3. une erreur petite sur les donnes initiales y0 et y1 produise une erreur

    faible sur yn : cest la stabilit.

    Ce sont les 3 notions de base en Calcul Scientifique. Lquation (4) peutaussi se mettre sous forme condense, F (Y ) = b, cest alors un systme nonlinaire dont il faut trouver une solution.

    Lapproximation par diffrences finies de (2) scrit

    yn+1 2yn + yn1t2

    +g

    lyn = 0. (5)

    9

  • Elle peut se mettre sous forme dun systme linaire, cest--dire AY = b, o

    A =

    1 00 1 00 1 1

    . . .. . .

    . . . 10 1

    , Y =

    y0...yN

    , b =

    y0y10...0

    ,

    avec = 2+g

    lt2. De manire gnrale, toute quation issue de la modlisa-

    tion est ensuite discrtise puis mise sous la forme dun systme, diffrentielou non, linaire ou non. Tout commence par la rsolution des systmes li-naires, puis des quations non linaires, puis des quations diffrentielles.Nous verrons en deuxime anne les modles dquations aux drives par-tielles.

    10

  • Deuxime partie

    Rsolution numrique de

    systmes linaires

    11

  • Chapitre 1

    Gnralits

    Sommaire

    1.1 Rappels sur les matrices . . . . . . . . . . . . . . . 13

    1.1.1 Dfinitions . . . . . . . . . . . . . . . . . . . . . . 13

    1.1.2 Cas particulier de matrices . . . . . . . . . . . . . 15

    1.1.3 Dterminants . . . . . . . . . . . . . . . . . . . . . 15

    1.1.4 Produit de matrices par blocs . . . . . . . . . . . . 16

    1.2 Rduction des matrices . . . . . . . . . . . . . . . . 17

    1.3 Algorithme, complexit . . . . . . . . . . . . . . . . 18

    1.4 Systmes linaires, dfinitions . . . . . . . . . . . . 19

    1.5 Norme de vecteurs et de matrices . . . . . . . . . 22

    1.6 Conditionnement . . . . . . . . . . . . . . . . . . . . 25

    1.6.1 Erreur darrondi . . . . . . . . . . . . . . . . . . . 25

    1.6.2 Conditionnement dun problme . . . . . . . . . . 26

    1.6.3 Conditionnement dune matrice . . . . . . . . . . . 26

    1.7 Notion de prconditionnement . . . . . . . . . . . 29

    1.1 Rappels sur les matrices

    1.1.1 Dfinitions

    Une matrice (m,n) est un tableau m lignes et n colonnes

    A =

    a11 a12 a1na21 a22 a2n...

    .... . .

    ...am1 am2 amn

    13

  • Cest aussi la matrice dune application linaire A de Kn dans Km o K estR ou C : une base e1, , en tant choisie dans Kn, et une base f1, , fmdans Km, A est dfini par

    1 j n,A(ej) =n

    i=1

    aijfi

    Le j-me vecteur colonne de A reprsente donc la dcomposition de A(ej)dans la base f1, , fm.

    Dfinition 1.1 Lapplication linaire A est injective si

    A(x) = 0 x = 0

    Dfinition 1.2 Lapplication linaire A est surjective si pour tout b dansKm, on peut trouver x dans Kn tel que A(x) = b

    Dfinition 1.3 Lapplication linaire A est bijective si elle est la fois in-jective et surjective.

    Si A est bijective , on a m = n, la matrice A est carre.Oprations sur les matrices

    1. Somme : On peut ajouter deux matrices de mme dimension (m,n) et

    (A+B)ij = (A)ij + (B)ij

    2. Produit par un scalaire : Pour dans K, on peut faire le produit Aet

    (A)ij = (A)ij

    3. Produit de 2 matrices : Pour A(m,n) et B(n, p) on peut faire le produitAB, de dimension(m, p) et

    (AB)ij =

    n

    k=1

    (A)ik(B)kj

    4. Transpose dune matrice : Pour A(m,n) la transpose de A est dedimension (n,m) et est dfinie par ( tA)ij = Aji.

    5. Adjointe dune matrice : Pour A(m,n) ladjointe de A est de dimension(n,m) et est dfinie par (A)ij = Aji.

    6. Inverse dune matrice carre : on dit que la matrice carre A est in-versible si il existe une matrice B telle que AB = BA = I. La matriceB est appele linverse de A et note A1.

    14

  • 1.1.2 Cas particulier de matrices

    Toutes les matrice considres dans ce paragraphe sont carres.

    1. Matrices symtriques : elles vrifient tA = A, ou encore aij = aji.

    2. Matrices hermitiennes : elles vrifient A = A, ou encore aij = aji.

    3. Matrices diagonales : elles vrifient aij = 0 pour i 6= j.4. Matrices triangulaires infrieures : elles vrifient aij = 0 pour j > i, i.e.

    elles ont la forme

    A =

    0 0 0 0 0 . . . 0 0 0

    5. Matrices triangulaires suprieures : elles vrifient aij = 0 pour j < i,i.e. elles ont la forme

    A =

    0 0 0

    . . . 0 0 0 0 0 0

    Les matrices triangulaires sont importantes pour