Méthode de dichotomie (analyse matricielle)

En analyse numérique, l'algorithme de dichotomie (ou méthode de bissection ou méthode de Givens, du nom de Wallace Givens, ou méthode de Givens-Householder) est un algorithme de recherche de valeur propre, qui adapte la méthode de dichotomie en analyse réelle.

Rappels préliminaires et algorithme

Soit A une matrice hermitienne de taille N $A=(a_{i,j})_{1\leqslant i,j\leqslant N}$.

Suite de Sturm

La suite de Sturm est la suite des mineurs principaux :

$\gamma _{0}=1,\forall k\in \{1;N\},\gamma _{k}=\mathrm {det} (A_{k}),\ A_{k}=(a_{i,j})_{1\leqslant i,j\leqslant k}.$

Cette suite a la propriété suivante : le nombre de changements de signes dans la suite $\gamma _{0},\gamma _{1},\ldots ,\gamma _{N-1},\gamma _{N}$ est égal au nombre de valeurs propres négatives de A.

Ainsi, en posant, pour tout réel $\lambda$, en posant :

$\gamma _{0}(\lambda )=1,\forall k\in \{1;N\},\gamma _{k}(\lambda )=\mathrm {det} (A_{k}-\lambda I_{k}),\ A_{k}=(a_{i,j})_{1\leqslant i,j\leqslant k}.$

on a que pour tout réel $\lambda _{0}$, le nombre de changements de signes dans la suite $\gamma _{0}(\lambda _{0}),\gamma _{1}(\lambda _{0}),\ldots ,\gamma _{N-1}(\lambda _{0}),\gamma _{N}(\lambda _{0})$ est égal au nombre de valeurs propres de A plus petites que $\lambda _{0}$.

Calcul du polynôme caractéristique d'une matrice tridiagonale

On suppose A tridiagonale et symétrique, soit de la forme :

$A={\begin{pmatrix}a_{1}&b_{2}&0&\ldots &0\\b_{2}&a_{2}&b_{3}&\ddots &\vdots \\0&b_{3}&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &b_{N}\\0&\ldots &0&b_{N}&a_{N}\\\end{pmatrix}}$.

Alors son polynôme caractéristique peut s'obtenir à partir de sa suite de Sturm : en posant :

$\gamma _{0}(\lambda )=1$

$\gamma _{1}(\lambda )=a_{1}-\lambda .$

$\forall k\in [\![2;N]\!],\ \gamma _{k}(\lambda )=(a_{k}-\lambda )\gamma _{k-1}(\lambda )-b_{k}^{2}\gamma _{k-2}(\lambda ).$

On a $\chi _{A}(\lambda )=\gamma _{N}(\lambda ).$

Algorithme

Dans le cas ou A n'est pas tridiagonale, on se ramène à une matrice de cette forme.

On note $\omega (\lambda )$ la fonction qui, pour $\lambda \in \mathbb {R}$, donne le nombre de changements de signe dans $\{\gamma _{0}(\lambda ),\ldots ,\gamma _{N}(\lambda )\}$.

On considère alors un intervalle $[a,b]$ contenant toutes les valeurs propres de A, ce qui implique ainsi $\omega (a)=0,\omega (b)=N$. En calculant $\omega ({\tfrac {a+b}{2}})$, on obtient le nombres de racines sur $[a,{\tfrac {a+b}{2}}[$ et $[{\tfrac {a+b}{2}},b[$, ce qui permet de recalculer les intervalles de recherche puis d'itérer à la manière de la méthode de dichotomie.

Intérêts

Contrairement à la méthode de la puissance itérée qui ne donne que la valeur propre dominante, la méthode de dichotomie permet d'obtenir toutes les valeurs propres d'une matrice, ce qui la rapproche de la méthode de Rayleigh-Ritz, ou même une certaine partie, comme les 10% des plus grandes valeurs propres de la matrice.

Sa mise en application se prête aisément à la parallélisation.

Bibliographie

• (en) Yuli Eidelman et Iulian Haimovici, « The Bisection Eigenvalue method for unitary Hessenberg matrices via their quasiseparable structure », Electronic Transactions on Numerical Analysis, vol. 59,‎ 2023, p. 60–88 (DOI 10.1553/etna_vol59s60, lire en ligne)

• (en) R. Z. Dautov, A. D. Lyashko et S. I. Solov'ev, « The bisection method for symmetric eigenvalue problems with a parameter entering nonlinearly », Russian Journal of Numerical Analysis and Mathematical Modelling, vol. 9, n^o 5,‎ 1994, p. 417-427 (DOI 10.1515/rnam.1994.9.5.417, lire en ligne)