Méthode de Householder

En analyse numérique, la méthode de Householder désigne un algorithme de recherche d'un zéro d'une fonction utilisé pour les fonctions d'une variable réelle dérivables deux fois et à dérivée seconde continue (i.e. C²).

L'algorithme est itératif et de convergence cubique ; il se généralise à des fonctions Cⁿ avec une convergence d'ordre n + 1.

Il doit son nom à son inventeur, le mathématicien Alston Scott Householder.

Énoncé

Soit f une fonction C² et a un zéro de f. La méthode de Householder consiste à itérer :

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\times (1+h_{k})$

avec

$h_{k}={\frac {f(x_{k})f''(x_{k})}{2f'(x_{k})^{2}}}$

à partir d'une estimation x₀ de a.

On retrouve la méthode de Halley en remplaçant (1 + h_k) par 1/(1 − h_k) pour h_k << 1 dans la relation de récurrence ci-dessus.

Généralisation

Les méthodes Householder généralisent la méthode de Newton (cas n = 0) et la méthode de Halley (cas n = 1) dans le cas d'une fonction C^{n + 1} :

$x_{k+1}=x_{k}+(n+1){\frac {(1/f)^{(n)}(x_{k})}{(1/f)^{(n+1)}(x_{k})}}$

Leur vitesse de convergence est d'ordre n + 2.

Voir aussi

Liens externes

• (en) Newton's method and high order iterations, Pascal Sebah et Xavier Gourdon, 2001
• (en) Eric W. Weisstein, « Householder's Method », sur MathWorld

Bibliographie

• (en) Alston Scott Householder, Numerical Treatment of a Single Nonlinear Equation, McGraw Hill Text, New York, 1970 (ISBN 0-07-030465-3)