Научная библиотека

3. Метод парабол.

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

На практике часто имеет и первую производную и вторую. Поэтому для нахождения нулей первой производной применяют метод линеаризации, что приводит к такому итерационному процессу:

в простейших задачах нулевое приближение можно выбрать графически. Формулу (11) можно получит несколько иным способом.

Разложим в точке по формуле Тейлора, ограничившись тремя членами, т. е. аппроксимируем кривую параболой

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

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

Это эквивалентно замене кривой на интерполяционную параболу, построенную по трем точкам . Обычно выбирают вспомогательный шаг при ручных расчетах с небольшим числом знаков и при расчетах на ЭВМ; тогда характер сходимости вблизи экстремума вплоть до расстояний практически не отличается от квадратичного. Формула (12) наиболее, часто употребляется в практических расчетах.

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

и требует только одного вычисления функции за итерацию. Однако ранее уже отмечалось, что такая замена производных разделенными разностями уменьшает скорость сходимости. Можно показать, используя описанную в главе V, § 2, п. 7 технику, что вблизи невырожденного минимума

Во-первых, отсюда видно, что только если выполнено условие это приблизительно показывает размеры окрестности корня, в которой Итерации сходятся. Эта окрестность может быть небольшой, если велика.

Во-вторых, асимптотическая скорость сходимости определяется показателем степени при в правой части соотношения (14). Этот показатель невелик; поэтому сходимость настолько медленна, что три итерации по этой формуле только немного сильней уменьшают погрешность, чем одна итерация по формуле (12). А поскольку формула (13) недостаточно испытана на практике, то нет уверенности, что она окажется лучше.

Заметим, что во всех вариантах метода парабол для успешной работы необходимы «кухонные» поправки к алгоритму. В ходе вычислений надо проверять, движемся ли мы к минимуму: вторая разность, стоящая в знаменателе формулы (12), или вторая производная в знаменателе формулы (11) должна быть положительной. Если она отрицательна, то итерации сходятся к максимуму, и надо сделать какой-то шаг в обратном направлении, причем достаточно большой.

Вычислив новое приближение, надо обязательно проверить, уменьшилась ли функция. Если оказалось, что

то значение нельзя использовать и надо просто сделать от точки какой-то шаг в сторону убывания функции. Обычно делают шаг величиной и проверяют условие убывания функции; если оно снова не выполнено, то уменьшают вдвое и делают шаг опять из точки и так до тех пор, пока не добьются убывания функции.

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

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

Если так сделать не удается, то выбирают несколько начальных приближений в разных участках отрезка b], и из каждого начального приближения проводят какой-нибудь итерационный процесс поиска минимума. Некоторые из этих итерационных процессов могут сходиться к одному и тому же локальному минимуму, а некоторые к другим. Остается сравнить найденные локальные минимумы между собой и выбрать наименьший (если это требуется по условиям задачи).

Описанный способ не дает гарантии того, что будут найдены все минимумы (и тем самым, что будет найден абсолютный минимум). Но для недостаточно изученной функции такой гарантии не дают никакие способы.