Scribd Logo
Importer

Bienvenue sur Scribd !

  • 30 vues

    TPVP

    Transféré par

    Rodrigue patrice Njounhassi koagne
    Ce document décrit trois méthodes pour calculer les valeurs et vecteurs propres d'une matrice: la méthode de la puissance, la méthode de Jacobi et la méthode QR. Il présente les principes théoriques de chaque méthode et propose des exercices de programmation pour les comparer numériquement sur un exemple concret.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    TPVP

    Transféré par

    Rodrigue patrice Njounhassi koagne
    30 vues3 pages
    Ce document décrit trois méthodes pour calculer les valeurs et vecteurs propres d'une matrice: la méthode de la puissance, la méthode de Jacobi et la méthode QR. Il présente les principes théoriques de chaque méthode et propose des exercices de programmation pour les comparer numériquement sur un exemple concret.

    Titre original

    TPvp

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document décrit trois méthodes pour calculer les valeurs et vecteurs propres d'une matrice: la méthode de la puissance, la méthode de Jacobi et la méthode QR. Il présente les principes théoriques de chaque méthode et propose des exercices de programmation pour les comparer numériquement sur un exemple concret.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    30 vues3 pages

    TPVP

    Transféré par

    Rodrigue patrice Njounhassi koagne
    Ce document décrit trois méthodes pour calculer les valeurs et vecteurs propres d'une matrice: la méthode de la puissance, la méthode de Jacobi et la méthode QR. Il présente les principes théoriques de chaque méthode et propose des exercices de programmation pour les comparer numériquement sur un exemple concret.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 3

    Préparation à l’Agrégation de Mathématiques

    Année 2008-2009
    TP Scilab : Méthodes de calcul des valeurs propres

    1. Quelques rappels théoriques


    1.1. La méthode de la puissance. Soit une matrice A carrée d’ordre n dont la valeur
    propre de plus grand module λ1 est unique. On note ses valeurs propres λ1 , λ2 , . . . , λn .
    On choisit un vecteur initial q0 qui n’est pas orthogonal au sous-espace propre à gauche associé
    xk
    à λ1 et tel que ||q0 || = 1. On définit la suite xk = Aqk−1 , puis qk = .
    ||xk ||
    Théorème1. On
    ka les limites suivantes :
    λ1
    – lim qk est un vecteur propre à droite de norme unité associé à λ1 ,
    k→+∞ |λ1 |
    – lim ||Aqk || = |λ1 |,
    k→+∞
    xk+1 (j)
    – lim = λ1 pour 1 ≤ j ≤ n, si qk (j) 6= 0, où y(j) est la j-ème composante de y.
    k→+∞ qk (j)
    λp+1
    Si, de plus, A est diagonalisable, le facteur de convergence de chacune de ces suites est ,
    λ1
    où p est la multiplicité de la valeur propre λ1 .
    1.2. La méthode de Jacobi. On part d’une matrice A symétrique. On construit cette fois
    ci une suite de matrices (Ak ) avec A0 = A. On passe de Ak à Ak+1 par une transformation
    telle que Ak+1 = QTk Ak Qk où Qk est une matrice orthogonale et on s’arrange pour annuler
    deux éléments symétriques hors diagonaux (Ak )p,q et (Ak )q,p .
    Théorème 2. Soient p, q deux entiers distincts et θ un réel 
    auxquels on associe la matrice
    1

    ..
    . (0)
     
     
     ←p
    cos θ sin θ

     
    1
     
     
    orthogonale O = 
     . .

    .
     . 

    1
     
     

     − sin θ cos θ 
     ←q
     .. 
     (0) . 
    1
    X X
    2
    T
    (i) Si A est symétrique, la matrice B = O AO est symétrique et vérifie Bi,j = A2i,j .
    i,j i,j
    (ii) Si Ap,q 6= 0, il existe une unique valeur de θ ∈] − π4 , 0[∪]0, π4 ] telle que Bp,q = 0. C’est
    n n
    Aq,q − Ap,p X
    2
    X
    la solution de l’équation cotg2θ = . On a alors que Bi,i = A2i,i + 2A2p,q .
    2Ap,q
    i=1 i=1

    Remarque 1 : Il y a plusieurs manières de choisir le couple (p, q). La plus classique est de
    prendre |(Ak )p,q | = max |(Ak )i,j |.
    i6=j

    Théorème 3. La suite (Ak ) converge et lim Ak = diag(λσ(i) ) pour une permutation σ ∈ Sn ,


    k→+∞
    où les λi , 1 ≤ i ≤ n, sont les valeurs propres de la matrice A.
    On suppose de plus que toutes les valeurs propres de la matrice A sont distinctes. Alors
    la suite Ωk = O1 . . . Ok converge vers une matrice orthogonale dont les vecteurs colonnes
    constituent un ensemble orthonormal de vecteurs propres de la matrice A.
    1
    2

    1.3. La méthode QR. On décrit ici seulement le principe de la méthode QR. On effectue
    la décomposition QR de la matrice A de départ et on note A = Q1 R1 , on calcule ensuite
    le produit A2 = R1 Q1 . Une fois A2 . . . Ak calculées, on effectue la décompostion QR de la
    matrice Ak que l’on note Ak = Qk Rk et on calcule le produit Ak+1 = Rk Qk .
    La matrice Ak ainsi construite vérifie donc l’égalité Ak = Q−1 −1
    k . . . Q2 AQ2 . . . Qk et a donc
    les mêmes valeurs propres que la matrice A de départ.
    Voici le théorème de convergence :
    Théorème 4. On suppose que A est inversible et que ses valeurs propres sont toutes de
    modules différents. Il existe donc une matrice inversible P telle que A = P ΛP −1 où Λ =
    diag(λ1 , . . . , λn ) et |λ1 | > · · · > |λn | > 0 et l’on suppose que la matrice P admet une factori-
    sation LU. Alors la suite de matrice (Ak ) est telle que
    lim (Ak )i,i = λi , 1 ≤ i ≤ n, et lim (Ak )i,j = 0, 1 ≤ j < i ≤ n.
    k→+∞ k→+∞

    Remarque 2 : On peut améliorer la convergence en transformant la matrice de départ


    en une ”matrice de Hessenberg supérieure” semblable (i.e. une matrice triangulaire supérieure
    avec la sous-diagonale en plus) grâce aux matrices de Householder (cf TD sur la décomposition
    QR). La décomposition QR conserve alors la structure ”Hessenberg supérieure” de la matrice.

    2. Programmation numérique
    Exercice 1 : Comparaison des différentes méthodes.
     
    a b
     c a b (0) 
     
    On rappelle que les valeurs propres exactes de la matrice 
     . .. .. ..  valent

     . . 
     (0) c a b 
    c a
    r  
    c kπ
    µk = a + 2b cos , 1 ≤ k ≤ n et qu’un vecteur propre associé à µk est xk =
    b n+1
           t
    c (1/2) kπ  c (j/2) jkπ  c (n/2) nkπ
    sin ,··· , sin ,··· , sin .
    b n+1 b n+1 b n+1
    Soit la matrice A ∈ M10 (R) définie par :


     Ai,i = 2, 1 ≤ i ≤ 10,
    Ai,i+1 = Ai+1,i = −1, 1 ≤ i ≤ 9,

     Ai,j = 0, sinon.
    1.1. Programmer la méthode de la puissance. Tracer l’évolution de la valeur propre calculée
    en fonction du nombre d’itérations. Quelle est l’erreur entre le vecteur propre approché et le
    vecteur propre exact ? Idem pour la valeur propre µ1 .
    1.2. Programmer la méthode de Jacobi et l’appliquer à la même matrice. Illustrer la conver-
    gence de la suite de matrices obtenue.
    1.3. Programmer la méthode QR et l’appliquer à la même matrice. Illustrer la convergence
    de la suite de matrices obtenue.
    1.4. Comparer les différentes méthodes entre elles, notamment en calculant le nombre
    d’itérations nécessaires.
    3

    Exercice 2 : Approfondissement
     sur la méthode de la puissance.

    0, 5172 0, 5473 −1, 224 0, 8012
     0, 5473 1, 388 1, 353 −1, 112 
    Soit la matrice A =   −1, 224 1, 353 0, 03642 2, 893  dont les valeurs propres

    0, 8012 −1, 112 2, 893 0, 05827


    sont λ1 = −4, λ2 = 3,λ3 = 2 et λ 4 = 1 et des
     vecteurs propres
     correspondant à λ1 et λ2 sont
    0.3225 −0.1290
     −0.3225 
     et u2 =  0.1290 .
     
    respectivement u1 =   0.6451   0.7419 
    −0.6129 0.6451
    2.1. Programmer la méthode de la puissance avec comme vecteur initial x0 = (1, 0, 0, 0)t .
    Etudier l’evolution de la valeur propre calculée. Tracer l’évolution de γk = ||xk ||2 en fonction
    de k.
    2.2. On part maintenant du vecteur initial x0 = (1, 1, 1, 1)t (presque orthogonal à u1 ). Même
    question.
    2.3. On part enfin du vecteur initial x0 = (1, 1, 0, 0)t (orthogonal à u1 et u2 ). Même question.

    Exercice 3 : Approfondissement
     sur la méthode de la puissance
     inverse.
    1, 349 0, 5649 −0, 4573 0, 5964
     0, 5649 2, 863 −0, 5147 0, 6596 
    Soit la matrice A =   −0, 4573 −0, 5147
     dont les valeurs propres
    3, 552 0, 5707 
    0, 5964 0, 6596 0, 5707 3, 186
    sont λ1 =  4, λ2 = 3, 95, λ3 =2 et λ4= 1 et des vecteurs propres correspondant à λ1 et λ2
    1/3 1/4
     2/3   1/2 
    sont u1 =   −1  et u2 =  1/2 .
      

    1/12 1
    3.1. Quel est le taux de convergence de la méthode de la puissance pour calculer λ1 ?
    Vérifier la lenteur de la convergence en partant de x0 = (1, 0, 0, 0)t . Afficher de temps en
    temps le vecteur propre calculé.
    3.2. On cherche à calculer le vecteur propre associé à λ2 . Calculer le taux de convergence
    de la méthode de la puissance inverse et en programmer quelques itérations pour les valeurs
    suivantes de µ : µ = 3, 96, µ = 3, 97, µ = 3, 976. Que dire de la convergence du vecteur propre
    approché ?

    3. Références
    Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Dunod.
    Lascaux-Théodor, Analyse numérique matricielle appliquée à l’art de l’ingénieur. Tome 2 ,
    Dunod.
    Serre, Les matrices, Dunod

    Vous aimerez peut-être aussi