- •Приближенные числа
- •Правила вычислений с приближенными числами.
- •Приближенное решение алгебраических и трансцендентных уравнений. Отделение корней и уточнение приближенных корней. Графическое решение уравнений.
- •Метод половинного деления (метод «вилки»).
- •Метод хорд.
- •Метод Ньютона (метод касательных).
- •Метод итерации. Приведение уравнений к виду, удобному для итерации.
- •Приближенное решение систем линейных уравнений. Метод итераций.
- •Приближенное решение систем нелинейных уравнений. Метод итерации.
- •Постановка задачи интерполирования функций. Общее решение задачи интерполирования функции полиномом.
- •Интерполяционная формула Лагранжа
- •Интерполирование сплайнами
- •14 Аппроксимирование функций (15 не нашли)
- •Аппроксимирование функций. Метод ортогональных функций.
- •Квадратурная формула Ньютона-Котеса
- •Квадратурная формула Гаусса
- •Численные метода решения задачи Коши для обыкновенных дифференциальных уравнений. Метод Эйлера. Метод Эйлера-Коши
- •Метод Рунге-Кутта
- •Редукция к задаче Коши двухточечной краевой задачи для линейного уравнения второго порядка.
- •Метод коллокации.
- •23.Аппроксимация производных конечно-разностными соотношениями.
- •Метод конечных разностей численного решения обыкновенных дифференциальных уравнений.
- •Принципы построения сеток на плоскости и в пространстве.
- •26. Построение разностных схем для уравнений параболического типа.
- •27. Экстремумы функций. Классификация методов безусловной оптимизации.
- •28. Общая характеристика методов оптимизации нулевого порядка.
- •Метод прямого поиска (метод Хука-Дживса).
- •Метод деформируемого многогранника (метод Нелдера-Мида).
- •Метод вращающихся координат (метод Розенброка).
- •Метод параллельных касательных (метод Пауэлла).
- •Общая характеристика методов оптимизации первого порядка.
- •34.Метод наискорейшего спуска
- •35. Общая характеристика методов оптимизации второго порядка. Метод Ньютона.
- •36. Метод Ньютона с регулировкой шага (метод с переменной метрикой)
- •37. Метод статистических испытаний (метод Монте-Карло)
- •38. Вычисление кратных интегралов методом Монте-Карло
- •39. Структура искусственной нейронной сети (инс)
- •40. Компьютерная модель нейрона (нейроэлемента, нэ)
- •41. Функции активации нейроэлементов
- •45.Методы обучения элементарного перцептрона.
- •46.Многослойный перцептрон.
- •47. Понятие обучающей выборки.
34.Метод наискорейшего спуска
В этом методе на каждой итерации величина шага аk выбирается из условия минимума функции f(x) в направлении спуска, т.е.
f(x[k]-αkf `(x[k]))=min f (x[k]-αf `(x[k]))
α≥0
Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(х) убывает.
С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции φ(а) = f(x[k] - af'(x[k])).
Алгоритм.
Задаются координаты начальной точки х[0].
В точке х[k], k = 0, 1, 2,..., вычисляется значение градиента f'(х[k]).
Определяется величина шага ak путем одномерной минимизации по a функции j(a) = f(x[k] - af'(x[k])).
Определяются координаты точки х[k + 1] : xi[k+ 1] = xi[k] - akf’i(x[k]), i = 1, ..., n.
Проверяются условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. Иначе – переход к п.1.
В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k + 1] (Рис. 8.9).
Траектория спуска -- зигзаг, соседние звенья зигзага ортогональны друг другу. Действительно, шаг ak выбирается путем минимизации по a функции
j(a) = f(x[k] - af'(x[k])).
Необходимое условие минимума функции dj(a)/da = 0.
Найдя производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:
dj(a)/da = -f'(x[k+1]) f'(x[k]) = 0.
Градиентные методы сходятся к минимуму со скоростью геометрической прогрессии для гладких выпуклых функций.
У таких функций наибольшее M и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)
мало отличаются друг от друга, т. е. матрица H(х)хорошо обусловлена.
На практике минимизируемые функции, как правило, имеют плохо обусловленные матрицы вторых производных (m/М « 1) .
Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на порядки!), чем в других направлениях.
Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 8.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными.
Направление антиградиента этих функций (Рис. 8.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.
Рис. 8.10. Овражная функция.
Скорость сходимости градиентных методов сильно зависит от точности вычислений градиента. Потеря точности (обычно в окрестности минимума или в «овражной» ситуации) может вообще нарушить сходимость процесса градиентного спуска.
Поэтому градиентные методы часто используют на начальной стадии решения задачи.
При этом точка х[0] находится далеко от минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.
Затем применяют другие, более эффективные методы.
35. Общая характеристика методов оптимизации второго порядка. Метод Ньютона.
Методы безусловной оптимизации второго порядка используют вторые частные производные минимизируемой функции f(х). Эти методы называют иногда квази-Ньютоновскими.
Идея методов.
Необходимым условием экстремума функции многих переменных f(x) в точке х* является равенство нулю ее градиента в этой точке:
f’(x*) = 0.
Разложение f'(х) в окрестности точки x[k]в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде
f’(x) = f’(x[k]) + f”(x[k])(x - x[k]) = 0.
Здесь f”(x[k]) = Н(x[k]) – матрица вторых производных (матрица Гессе) минимизируемой функции.
Следовательно, итерационный процесс для построения последовательных приближений к решению задачи минимизации функции f(х) описывается выражением
х[k+1]= х[k] - H-1 (x[k])f'(x[k]) ,
где H-1(x[k]) – обратная матрица для матрицы Гессе, а -H-1(x[k])f'(x[k]) = р[k] – направление спуска.
Полученный метод минимизации называют методом Ньютона.
Очевидно, что в данном методе величина шага вдоль направления р[k]полагается равной единице.
Последовательность точек {x[k]}, получаемая в результате применения итерационного процесса, при определенных предположениях сходится к некоторой стационарной точке х* функции f(х).
Если матрица Гессе Н(х*) положительно определена, точка х* будет точкой строгого локального минимума функции f(x).
Последовательность {х[k]}сходится к точке х* только в том случае, когда матрица Гессе целевой функции положительно определена на каждой итерации.
Если функция f(x)является квадратичной, то, независимо от начального приближения х[0] и степени “овражности”, с помощью метода Ньютона ее минимум находится за один шаг.
Это объясняется тем, что направление спуска -H-1(x[k])f'(x[k]) = р[k] в любых точках х[0] всегда совпадает с направлением в точку минимума х*.
Если же функция f(х) не квадратичная, но выпуклая, метод Ньютона гарантирует ее монотонное убывание от итерации к итерации.
При минимизации “овражных” функций скорость сходимости метода Ньютона более высока по сравнению с градиентными методами.
В таком случае вектор р[k]не указывает направление в точку минимума функции f(х), однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент.
Существенный недостаток метода Ньютона – зависимость сходимости для невыпуклых функций от начального приближения x[0].
Если x[0] далека от точки минимума, метод может расходиться, т. е. каждая следующая точка будет более удаленной от точки минимума, чем предыдущая.
Сходимость метода, независимо от начального приближения, обеспечивается выбором не только направления спуска
р[k] = -H-1(x[k])f'(x[k]),
но и величины шага a вдоль этого направления.
Соответствующий алгоритм называют методом Ньютона с регулировкой шага. Употребляется также термин метод с переменной метрикой.
Итерационный процесс в таком случае определяется выражением
x[k + 1] = x[k] - akH-1(x[k])f’(x[k]).
Величина шага ak выбирается из условия минимума функции f(х)поaв направлении движения, т. е. в результате решения задачи одномерной минимизации:
Вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограммах оптимизации полагается H-1(x[k])= Е , где Е -- единичная матрица. Очевидно, что итерация при этом осуществляется по методу наискорейшего спуска.
Существуют и широко применяются две основные модификации алгоритма метода с переменно метрикой:
алгоритм Дэвидона-Флетчера-Пауэлла (Davidon-Fletcher-Powell, DFPалгоритм)
алгоритм Бройдена-Флетчера-Гольдфарба-Шанно (Broyden-Fletcher- Goldfarb-Shanno, BFGSалгоритм).
Между ними есть малые отличия в ошибках округления, устойчивости и др.
(в 36 наверно)