5.3.2. Градиентные методы: функция Find



Если вы решаете "хорошие" уравнения, как все те, которые были приведены в предыдущих разделах, то, вообще говоря, можете никогда не задумываться, как именно Find ищет их корни. Однако даже в этом случае полезно представлять, что происходит "за кадром", т. е. какие действия совершаются в промежутке между введением необходимых условий после ключевого слова Given и получением результата после применения функции Find. Это важно хотя бы с позиций выбора начальных значений переменных перед вычислительным блоком. Рассмотрим в данном разделе некоторые особенности численных методов и возможности установки их различных параметров, которые предоставляет Find.

Принцип действия градиентных алгоритмов

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

одним неизвестным f (x)=0 для функции f(х)=х2+5х+2, график которой показан на рис. 5.8. Принцип градиентных методов состоит в последовательных приближениях к истинному решению уравнения, которые вычисляются с помощью производной от f (х). Приведем наиболее простую форму алгоритма, называемого методом Ньютона:

1. За нулевую итерацию принимается введенное пользователем начальное значение х0=х.

2. В точке х0 методом конечных разностей вычисляется производная f (x0).

3. Пользуясь разложением Тейлора, можно заменить f (х) в окрестности х0 касательной — прямой линией f (x)=f (x0) +f (х0)-(х-х0).

4. Определяется точка x1, в которой прямая пересекает ось х (рис. 5.8).

5. Если f (x1)<TOL, то итерации прерываются, и значение x1 выдается в качестве решения. В противном случае x1 принимается за новую итерацию, и цикл повторяется: строится касательная к f (х) в точке x1, определяется х2 — точка ее пересечения с осью х и т.д.



Рис. 5.8. Иллюстрация метода Ньютона


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

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

Чтобы отыскать точку, соответствующую каждой новой итерации, требуется приравнять оба равенства нулю, т. е. решить на каждом шаге полученную систему линейных уравнений.

Выбор градиентного алгоритма

Как уже отмечалось, Mathcad предлагает три различных варианта градиентных методов. Чтобы поменять численный метод:

1. Щелкните правой кнопкой мыши на названии функции Find.

2. Наведите указатель мыши на пункт Nonlinear (Нелинейный) в контекстном меню.

3. В появившемся подменю (рис. 5.9) выберите один из трех методов: Conjugate Gradient (Сопряженных градиентов), Quasi-Newton (квазиньютоновский) или Levenberg-Marquardt (Левенберга—Маркарда).



Рис. 5.9. Выбор численного алгоритма


Чтобы вернуть автоматический выбор типа численного метода, в контекстном меню надо выбрать пункт AutoSelect (Автоматический выбор). Если установлена опция автоматического выбора (о чем говорит флажок, установленный в пункте AutoSelect), то текущий тип численного метода можно узнать, вызвав то же самое подменю и посмотрев, который из них отмечен точкой. Два последних метода являются квази-ньютоновскими, основная идея которых была рассмотрена выше. Первый из них, метод сопряженных градиентов, является двухшаговым — для поиска очередной итерации он использует как текущую, так и предыдущую итерации. Алгоритм Левенберга подробно описан в справочной системе Mathcad, а подробную информацию о методах Ньютона и сопряженных градиентов можно найти в большинстве книг по численным методам.

Параметры градиентных алгоритмов

Помимо выбора самих методов имеется возможность устанавливать их некоторые параметры. Для этого нужно вызвать с помощью того же контекстного меню диалоговое окно Advanced Options (Дополнительные параметры), выбрав в контекстном меню пункты Nonlinear / Advanced options (Нелинейный / Дополнительные параметры). В этом диалоговом окне (рис. 5.10) имеется пять групп переключателей по два в каждой.

В первой строке — Derivative estimation (Аппроксимация производной) — определяется метод вычисления производной Forward (Вперед) или Central (Центральная). Они соответствуют аппроксимации производной либо правой (двухточечная схема "вперед"), либо центральной (трехточечная симметричная схема) конечной разностью.

ПРИМЕЧАНИЕ

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




Рис. 5.10. Диалоговое окно Advanced Options


Во второй строке — Variable estimation (Аппроксимация переменных) — можно определить тип аппроксимации рядом Тейлора. Для рассмотренного нами в этом разделе случая аппроксимации касательной прямой линией выберите переключатель Tangent (Касательная), для более точной квадратичной аппроксимации (параболой) выберите Quadratic (Квадратичная). Следующая группа переключателей — Linear variable check (Проверка линейности) — позволяет в специфических задачах сэкономить время вычислений. Если вы уверены, что нелинейности всех функций, входящих в уравнение, мало сказываются на значениях всех их частных производных, то установите переключатель Yes (Да). В этом случае производные будут приняты равными константам и не будут вычисляться на каждом шаге.

ВНИМАНИЕ!

С осторожностью изменяйте параметры численных методов. Пользуйтесь ими, когда решение не находится при выставленных по умолчанию параметрах, или когда расчеты занимают очень продолжительное время.



Пара переключателей Multistart (Сканирование) задает опцию поиска глобального или локального минимума или максимума. Если выставлен переключатель Yes (Да), Mathcad будет пытаться найти наиболее глубокий экстремум из области, близкой к начальному приближению. Эта опция предназначена, в основном, для настройки (тех же самых градиентных) алгоритмов поиска экстремума, а не для решения алгебраических уравнений (см. главу 6).

Наконец, последний переключатель — Evolutionary (Эволюционный алгоритм), — если установить его в положение Yes (Да), позволяет использовать модификацию численного метода для решения уравнений, определяемых не обязательно гладкими функциями. Как мы убедились в этом разделе, все градиентные методы, реализованные в функции Find, требуют многократного вычисления производных. Если вы работаете с достаточно гладкими функциями, то градиентные методы обеспечивают быстрый и надежный поиск корня. Для поиска корня недостаточно гладких функций одной переменной следует либо выставить данную опцию функции Find, либо использовать метод секущих (функцию root). Помните, что правильный выбор численного метода и его параметров может помочь при решении нестандартной задачи, которая при стандартных установках может и не поддаваться решению.