Сходимость численных методов в среднем

[VladLag]

Во всех стандартных книгах по численным методам количество шагов алгоритма оценивается исходя из наихудшего случая. На практике оно может быть во много раз меньше. Интересно, существуют ли оценки числа шагов в среднем, (то есть, их математического ожидания)? Например, известны ли оценки среднего числа шагов метода простой итерации или метода Ньютона решения уравнений, градиентных методов минимизации функций и т. д.? Если да, то где об этом можно прочитать?

[PAV]

В некоторых задачах оценки среднего делаются. Иногда они могут быть даже проще оценок наихудшего случая. Конкретно про численные методы не знаю и ссылок не дам. Но Вы должны понимать, какая тут основная сложность. Если говорить про оценки в среднем, то нужно ввести некоторую вероятностную меру на множестве тех объектов, с которым работает метод. Скажем, на множестве уравнений или функций. А это совсем не очевидно, как сделать, и что такая мера будет осмысленной.

[Zai]

Более актуальный вопрос, когда решается система нелинейных уравнений с несколькими десятками/сотнями тысяч уравнений.
Практика численных итерационных алгоритмов всегда показывает, что сходящийся процесс в конце концов все же расходится.
Оценка среднего значения( как некоторого обобщенного интеграла) весьма важна когда Вы решаете задачу с целью оценки решения с точки зрения некоторого интегрального параметра. Например, в аэродинамике Вы определяете коэффициент лобового сопротивления сложного тела, обтекаемого с отрывами. Неидеальность Ваших численных алгоритмов может быть следующей. Минимальная невязка еще падает, но сила сопротивления уже растет и лучше принять схождение алгоритма решения когда сила сопротивления до этого стабилизировалась.