Méthode de Householder

Page d’aide sur les redirections

« Itération de Householder » redirige ici. Pour les autres significations, voir Itération (homonymie).

Cet article est une ébauche concernant l’analyse.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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. C2).

L'algorithme est itératif et de convergence cubique ; il se généralise à des fonctions Cn 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 − f ( x k ) f ′ ( x k ) × ( 1 + h k ) {\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\times (1+h_{k})}

avec

h k = f ( x k ) f ″ ( x k ) 2 f ′ ( x k ) 2 {\displaystyle h_{k}={\frac {f(x_{k})f''(x_{k})}{2f'(x_{k})^{2}}}}

à partir d'une estimation x0 de a.

On retrouve la méthode de Halley en remplaçant (1 + hk) par 1/(1 − hk) pour hk << 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 Cn + 1 :

x k + 1 = x k + ( n + 1 ) ( 1 / f ) ( n ) ( x k ) ( 1 / f ) ( n + 1 ) ( x k ) {\displaystyle 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)
  • icône décorative Portail de l'analyse