Метод наискорейшего спуска для систем нелинейных уравнений

Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений

Автор работы: Пользователь скрыл имя, 30 Ноября 2013 в 13:35, курсовая работа

Краткое описание

В настоящее время не существует методов, которые в одинаковой мере были бы хороши для всех систем ЛАУ. Почти все методы являются ориентированными и учитывают тем или иным образом специальные свойства матриц систем ЛАУ.
В курсовом проекте я рассматриваю метод скорейшего спуска. Этот метод не входит в число методов, которые широко используются и часто встречаются в литературе. Он реже используется в практике вычислений, но тем не менее содержит глубокие идеи и входит в основы теории вычислительной алгебры.

Содержание

Введение………………………………………………………. 2
1. Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений……………………….……….3
2. Метод скорейшего спуска для случая системы линейных уравнений…………………………………………………………..11
3. Свойства приближений метода скорейшего спуска……17
Заключение……….………….…………………………………25
Список использованной литературы…………

Прикрепленные файлы: 1 файл

курсач.doc

1. Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений……………………….……….3

2. Метод скорейшего спуска для случая системы линейных уравнений……………………………… …………………………..11

3. Свойства приближений метода скорейшего спуска……17

Список использованной литературы…………….………….26

Задачи численного решения систем линейных алгебраических уравнений (ЛАУ) и систем нелинейных численных уравнений многочисленны и весьма разнообразны. Это в первую очередь объясняется многообразием матриц систем ЛАУ и просто матриц для которых необходимо проводить вычисления.

В настоящее время не существует методов, которые в одинаковой мере были бы хороши для всех систем ЛАУ. Почти все методы являются ориентированными и учитывают тем или иным образом специальные свойства матриц систем ЛАУ.

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

Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений.

Пусть имеется система нелинейных уравнений:

Систему (1) удобнее записать в матричном виде:

где — вектор – функция; — вектор – аргумент.

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

Очевидно, что каждое решение системы (1) обращает в нуль функцию U(x); наоборот, числа x₁, x₂, . x_n, для которых функция U(x) равна нулю, являются корнями системы (1).

Будем предполагать, что система (1) имеет лишь изолированное решение, которое представляет собой точку строгого минимума функции U(x). Таким образом, задача сводится к нахождению минимума функции U(x) в n-мерном пространстве

Пусть x – вектор-корень системы (1) и x (0) – его нулевое приближение. Через точку x (0) проведем поверхность уровня функции U(x). Если точка x (0) достаточна близка к корню х, то при наших предположениях поверхность уровня

будет похожа на эллипсоид.

Из точки х (0) двигаемся по нормали к поверхности U(x)=U(x (0) ) до тех пор, пока эта нормаль не коснется в некоторой точке х (1) какой-то другой поверхности уровня.

5.2. Метод градиента (метод скорейшего спуска)

Пусть имеется система нелинейных уравнений:

(5.13)

Систему (5.13) удобнее записать в матричном виде:

(5.14)

Где — вектор – функция; — вектор – аргумент.

Решение системы (5.14), как и для системы линейных уравнений (см. п. 3.8), будем искать в виде

(5.15)

Здесь и — векторы неизвестных на P и P+1 шагах итераций; вектор невязок на P-ом шаге – F(P) = F(X(P)); W‘P – транспонированная матрица Якоби на P – ом шаге;

;

.

Пример 5.2. Методом градиента вычислим приближенно корни системы

Расположенные в окрестности начала координат.

Выберем начальное приближение:

По вышеприведенным формулам найдем первое приближение:

Аналогичным образом находим следующее приближение:

Ограничимся двумя итерациями (шагами), и оценим невязку:

· Как видно из примера, решение достаточно быстро сходится, невязка быстро убывает.

· При решении системы нелинейных уравнений методом градиента матрицу Якоби необходимо пересчитывать на каждом шаге (итерации).

Вопросы для самопроверки

· Как найти начальное приближение: а) для метода Ньютона; б) для метода градиента?

· В методе скорейшего спуска вычисляется Якобиан (матрица Якоби). Чем отличается Якобиан, вычисленный для СЛАУ, от Якобиана, вычисленного для нелинейной системы уравнений?

· Каков критерий остановки итерационного процесса при решении системы нелинейных уравнений: а) методом Ньютона; б) методом скорейшего спуска?

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

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

Метод наискорейшего спуска (в англ. литературе «method of steepest descent») — это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:

— это значения аргумента функции (управляемые параметры) на вещественной области.

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

где i, j,…, n — единичные векторы, параллельные координатным осям.

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

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

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции;

— единичный вектор направления, который определяется по формуле:

— модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента:

— константа, определяющая размеры шага и одинаковая для всех i-х направлений.

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

Другими словами, величину шага определяют при решении данного уравнения:

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

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

Рис.1. Траектория движения к точке экстремума при использовании метода наискорейшего спуска, изображенная на графике линии равного уровня функции f(x)

Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев):

— траектория поиска остается в малой окрестности текущей точки поиска:

— приращение целевой функции не меняется:

— градиент целевой функции в точке локального минимума обращается в нуль:

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

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

Методика расчета

• 1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции

• 2 шаг: Задаем начальное приближение

Далее выполняется итерационный процесс.

• 3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.

• 4 шаг: Вычисление координат единичного вектора по представленным формулам

• 5 шаг: определяем шаг расчета из условия поиска экстремума для следующей функции (решения задачи одномерной оптимизации).

• 6 шаг: Определяем новые значения аргументов функции после выполнения k-го шага расчета:

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции;

• 7 шаг: проверяем критерии останова итерационного процесса. Вычислительный процесс заканчивается, когда будет достигнута точка, в которой оценка градиента будет равна нулю (коэффициенты функции отклика становятся незначимыми). В противном случае возвращаемся к шагу 3 и продолжаем итерационный расчет.

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