比利时vs摩洛哥足彩
,
university of california san diego
****************************
department colloquium
konstantin tikhomirov
carnegie mellon university
average-case analysis of the gaussian elimination with partial pivoting
abstract:
the gaussian elimination with partial pivoting (gepp) is a classical algorithm for solving systems of linear equations. empirical evidence strongly suggests that for a typical square coefficient matrix, gepp is numerically stable. we obtain a (partial) theoretical justification of this phenomenon by showing that, given the random n×n standard gaussian coefficient matrix a, the growth factor of the gaussian elimination with partial pivoting is at most polynomially large in n with probability close to one. this implies that with probability close to one the number of bits of precision sufficient to solve ax=b to m bits of accuracy using gepp is m+o(log(n)), which we conjecture to be optimal by the order of magnitude. we further provide tail estimates of the growth factor which can be used to support the empirical observation that gepp is more stable than the gaussian elimination with no pivoting. based on joint work with han huang.
tianyi zheng
february 2, 2023
4:00 pm
apm 6402
****************************