Критерии толерантности по методу Брента

Question

Критерий остановки для метода Брента:

if abs(m) <= tol or fb == 0.0 then    // root found (interval is small enough) 
    found := true;

Однако, что если abs(m) достигнет указанного допуска, но значение f(b) не близко к нулю? Будет ли этот случай считаться неуместным или успешно сходящимся? Я вижу, что abs(m) < tolerance, то есть |b-a| < tolerance, но значение функции не равно нулю или где-либо близко. Разве весь смысл метода Брента в том, чтобы найти root функции такой, что f(b) == 0.0 или ниже определенного допуска?

Всегда ли так, когда достигается сходимость |b-a| < tolerance, даже если значение функции не близко к нулю, т.е. ниже заданного допуска?

Answer 1

Если r - это root, то вы хотите приблизительно r (не f(r)) с точностью до заданного допуска, что именно здесь и происходит. Конечно, возможно, что график f почти вертикальный в этой точке, поэтому, если b - ваше приближение, f(b) не близко к 0. Если это произойдет, вам нужно меньше терпимости. Для большинства приложений знание от root до 6 десятичных знаков более чем достаточно, но если ваше приложение включает функцию, значения которой могут резко измениться в ответ на изменение 7-го десятичного знака, вы, конечно, столкнетесь с проблемами. По этой причине в курсе численного анализа выражения для ошибки в методе включают в себя оценки производных. Вам нужно какое-то предположение о гладкости, чтобы получить разумные результаты.

Answer 2

Метод Брента - это метод брекетинга, который означает, что он сохраняет интервал брекетинга, что означает две точки с противоположным знаком в значении их функции во время итерации. Отсюда следует, что в этом интервале длины m происходит смена знака, поэтому по теореме о промежуточном значении существует "точное" root, близкое к b с расстоянием, не превышающим m.

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

из пример и график с использованием расширенного W.-pol. .

С другой стороны, числовая функция может не выглядеть нечеткой при увеличении , но тогда она будет кусочно постоянной и может не иметь точки со значением ноль,

(горизонтальный масштаб в частях 1e-14) из пример и график с использованием факторизованного W.-pol. .