Методы средней точки и секущих

Метод средней точки является эффективным методом уменьшения интервала неопределенности на основе информации, вычисленной только в одной пробной точке.

Алгоритм метода средней точки (метод Больцано) Задать интервал унимодальности [a, b] и параметр сходимости .

Положить R=b, L=a; (при этом f'(a)0).

Вычислить z=(R+L)/2 и f'(z).

Если |f'(z)|, то Стоп;

иначе, если f'(z)<0, то L=z; перейти к 2;

иначе, R=z и перейти к 2.

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

Метод секущих как раз и использует информацию не только о знаке производной, но и о величине этой производной. Предположим, что в процессе поиска стационарной точки функции f (x) в интервале унимодальности [a, b] обнаружены две точки L и R, в которых знаки производных различны. В этом случае алгоритм метода секущих позволяет аппроксимировать функцию f'(x) «секущей прямой» (или «хордой») и найти точку, в которой секущая графика f'(x) пересекает ось абсцисс (рис. 1.8). Таким образом следующее приближение к стационарной точке x* определяется по формуле.

z=.

Если модуль f'(z) не больше параметра сходимости, то поиск точки минимума завершен. В противном случае нужно выбрать одну из точек L или R, чтобы знаки производной в этой точке и точке z были различны, а затем повторить итрерацию. Например, в ситуации, изображенной на рис. 1.8, в качестве этих точек должны быть выбраны точки z и R. Этот метод в ряде случаев позволяет исключать более половины интервала неопределенности.

f'(x).

L z x* R.

Рис. 1.8 Метод секущих

Легко видеть, что в отличие от метода средней точки метод секущих основан на исследовании не только знака, но и значений производной в пробных точках и поэтому в ряде случаев позволяет исключить более половины интервала поиска.