Equilibrage Minimax Des Contributions Elémentaires Dans L’élimination Symétrique Complete

Abstract

Les factorisations symétriques des matrices définies positives constituent l’un des fondements de l’algèbre linéaire numérique. Les travaux existants se sont principalement attachés à améliorer la stabilité numérique à réduire le remplissage des matrices creuses ou à construire des approximations de faible rang. Dans cet article, nous proposons un point de vue différent :

Nous montrons qu’à toute élimination symétrique complète est naturellement associée une suite de contributions élémentaires correspondant aux diminutions successives de la trace induites par le complément de Schur. La somme de ces contributions est indépendante de l’ordre de l’élimination et coïncide exactement avec la trace de la matrice initiale. L’ordre d’élimination n’agit donc pas sur la quantité totale extraite mais uniquement sur sa séparation au cours de la factorisation.

Cette observation conduit à la formulation d’optimisation : Déterminer l’ordre d’élimination qui minimise la plus grande contribution élémentaire produite pendant toute la factorisation. Nous montrons que ce problème possède une structure récursive naturelle gouvernée par les compléments de Schur et qu’il satisfait le principe d’optimisation de Bellman. Nous établissons plusieurs propriétés fondamentales de cette nouvelle fonction de valeur, caractérisons une famille de factorisations parfaitement équilibrées et analysons une stratégie gloutonne fondée sur la minimisation de la contribution immédiate. Nous démontrons que cette stratégie est optimale en dimension deux et qu’elle constitue en dimension trois, une 2 approximation optimale de la solution minimax.