SEMINAIRE D'ANALYSE NUMERIQUE
Année universitaire 2015-2016
Jeudi 19 novembre : Jean-Pierre
DUSSAULT (Département d'informatique, Université
de Sherbrooke)
Présentation unifiée d'algorithmes de région de
confiance et d'une nouvelle variante de ARC nommée ARCq.
Le récent algorithme ARC possède une propriété remarquable, une complexité en pire cas optimale. Après une mise en contexte sur les notions de vitesse de convergence et de complexité en pire cas, nous présentons un point de vue unifié des méthodes de région de confiance et de régularisation cubique adaptative (ARC). Bien que les liens entre ces deux familles aient été mentionnés dans l'article qui introduit ARC, nous poussons plus loin l'analogie et en déduisons une démonstration de convergence globale plus simple et unifiée. Nous soulignons également les faits importants de la complexité en pire cas qui s'avère optimale pour ARCq, mais pas pour les algorithmes de région de confiance. Notre nouvelle variante, ARCq, se prête bien à des implémentations efficaces et nous en présentons deux, une matricielle de type Cholesky et une itérative basée sur des algorithmes de type Krylov; cette dernière variante peut résoudre des problèmes de très grande taille
