Analyse du cas moyen de l'élimination gaussienne avec pivotage partiel

Résumé L'élimination gaussienne avec pivotage partiel (GEPP) est un algorithme classique pour résoudre des systèmes d'équations linéaires. Bien que dans certains cas, la perte de précision dans GEPP due aux erreurs d'arrondi puisse être très significative, des preuves empiriques suggèrent fortement que pour une matrice de coefficients carrée typique, GEPP est numériquement stable. Nous obtenons une justification théorique (partielle) de ce phénomène en montrant que, étant donné la matrice de coefficients gaussiens standard A de taille n x n, le facteur de croissance de l'élimination gaussienne avec pivotage partiel est au plus polynomialement grand en n avec une probabilité proche de un. Cela implique qu'avec une probabilité proche de un, le nombre de bits de précision suffisant pour résoudre Ax = b A x = b avec une précision de m bits en utilisant GEPP est m + O (n), ce qui améliore une estimation antérieure de m + O (² n) de Sankar, et que nous conjecturons être optimal par l'ordre de grandeur. Nous fournissons en outre des estimations de queue du facteur de croissance qui peuvent être utilisées pour soutenir l'observation empirique que GEPP est plus stable que l'élimination gaussienne sans pivotage.