En analyse numérique, l'algorithme de dichotomie (ou méthode de bissection ou méthode de Givens, du nom de Wallace Givens^[1], 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^[2],[3].

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

La suite de Sturm est la suite des mineurs principaux :

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \lambda }$, en posant :

${\displaystyle \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 ${\displaystyle \lambda _{0}}$, le nombre de changements de signes dans la suite ${\displaystyle \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 ${\displaystyle \lambda _{0}}$.

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

${\displaystyle 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 :

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

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

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

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

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

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

On considère alors un intervalle ${\displaystyle [a,b]}$ contenant toutes les valeurs propres de A, ce qui implique ainsi ${\displaystyle \omega (a)=0,\omega (b)=N}$. En calculant ${\displaystyle \omega ({\tfrac {a+b}{2}})}$, on obtient le nombres de racines sur ${\displaystyle [a,{\tfrac {a+b}{2}}[}$ et ${\displaystyle [{\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.

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.

• (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)

• Portail de l’algèbre