Математика Лекции и примеры решения задач Физический смысл дифференциала. Производная сложной функции Раскрытие неопределенностей Ряды Фурье Преобразование Фурье Двойной интеграл Векторная алгебра

Решение нелинейных систем методами спуска

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

   (4.16)

 Из функций f(x,y), g(x,y) системы (4.l6) образуем новую функцию

Ф

Так как эта функция не отрицательная, то найдется точка (вообще говоря, не единственная)  такая, что

 ФФ

Рис. 4.1. Пространственная интерпретация метода наискорейшего спуска для функции (4.17)

Рис. 4.2. Траектория наискорейшего спуска для функции (4.17) в плоскости ХОУ

Следовательно, если тем или иным способом удается получить точку , минимизирующую функцию Ф(x,y), и если при этом окажется, что ФФ, то точка  - истинное решение системы (4.16), поскольку

  Ф=0

Последовательность точек   - приближений к точке  минимума функции Ф(х,у) - обычно получают по рекуррентной формуле

  (4.18)

где k=0, l, 2,...,  - вектор, определяющий направление минимизации, а  - скалярная величина, характеризующая величину шага минимизации (шаговый множитель). Учитывая геометрический смысл задачи минимизации функций двух переменных Ф(x,y) - "спуск на дно" поверхности z = Ф(x,y) (рис. 4.1), итерационный метод (4.18) можно назвать методом спуска, если вектор  при каждом k является направлением спуска (т. e. существует такое >0, что Ф, и если множитель  подбирается так, чтобы выполнялось условие релаксации Φ, означающее переход на каждой итерации в точку с меньшим значением минимизируемой функции.

Таким образом, при построении численного метода вида (4.18) минимизации функции Ф(x,y) следует ответить на два главных вопроса: как выбирать направление спуска  и как регулировать длину шага в выбранном направлении с помощью скалярного параметра - шагового множителя . Приведем простые соображения по этому поводу.

При выборе направления спуска естественным является выбор такого направления, в котором минимизируемая функция убывает наиболее быстро.

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

 Ф=

антиградиент функции Ф(х,у). Таким образом, из семейства методов (4.18) выделяем градиентный метод

  (4.19)

Оптимальный шаг в направлении антиградиента - это такой шаг, при котором значение Φ наименьшее среди всех других значений Ф(х,у) в этом фиксированном направлении, т.е. когда точка  является точкой условного минимума. Следовательно, можно рассчитывать на наиболее быструю сходимость метода (4.19), если полагать в нем

  (4.20)

Такой выбор шагового множителя, называемый исчерпывающим спуском, вместе с формулой (4.19) определяет метод наискорейшего спуска.

Геометрическая интерпретация этого метода хорошо видна на рис. 4.1, 4.2. Характерны девяностоградусные изломы траектории наискорейшего спуска, что объясняется исчерпываемостью спуска и свойством градиента (а значит, и антиградиента) быть перпендикулярным к линии уровня в соответствующей точке.

Метод Ньютона

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

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

 

где

  (4.21)

 - матрица вторых производных:

 

Условие минимума   по : . Вычислим градиент из  из (4.22) и найдем значение :

  (4.22)

Для учета фактических особенностей минимизируемой функции будем использовать в (4.22) значения градиента и матрицы вторых производных, вычисленных не по аппроксимирующей (.), а непосредственно по минимизируемой функции F(x). Заменяя (.) в (4.22), найдемдлину шага .

 =. (4.23)

Метод Ньютона реализуется следующей последовательностью действий:

1. 3адается (произвольно) точка начального приближения .

2. Вычисляется в цикле по номеру итерации k=0, 1,:

значение вектора градиеита   в точке ;

значение матрицы вторых производных ;

значение матрицы обратной матрице вторых производных ;

значение шага  по формуле (4.23);

новоезначениеприближения  по формуле (4.19).

3. Закончить итерационный процесс, используя одно из условий, описанных в разд. 2.5.

Оценка погрешности метода Ньютона дается формулой

 

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

Достоинства метода Ньютона.

Для квадратической функции метод позволяет найти минимум за один шаг.

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

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

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


Практикум по теме «Тройной интеграл»