- •Приближенные числа
- •Правила вычислений с приближенными числами.
- •Приближенное решение алгебраических и трансцендентных уравнений. Отделение корней и уточнение приближенных корней. Графическое решение уравнений.
- •Метод половинного деления (метод «вилки»).
- •Метод хорд.
- •Метод Ньютона (метод касательных).
- •Метод итерации. Приведение уравнений к виду, удобному для итерации.
- •Приближенное решение систем линейных уравнений. Метод итераций.
- •Приближенное решение систем нелинейных уравнений. Метод итерации.
- •Постановка задачи интерполирования функций. Общее решение задачи интерполирования функции полиномом.
- •Интерполяционная формула Лагранжа
- •Интерполирование сплайнами
- •14 Аппроксимирование функций (15 не нашли)
- •Аппроксимирование функций. Метод ортогональных функций.
- •Квадратурная формула Ньютона-Котеса
- •Квадратурная формула Гаусса
- •Численные метода решения задачи Коши для обыкновенных дифференциальных уравнений. Метод Эйлера. Метод Эйлера-Коши
- •Метод Рунге-Кутта
- •Редукция к задаче Коши двухточечной краевой задачи для линейного уравнения второго порядка.
- •Метод коллокации.
- •23.Аппроксимация производных конечно-разностными соотношениями.
- •Метод конечных разностей численного решения обыкновенных дифференциальных уравнений.
- •Принципы построения сеток на плоскости и в пространстве.
- •26. Построение разностных схем для уравнений параболического типа.
- •27. Экстремумы функций. Классификация методов безусловной оптимизации.
- •28. Общая характеристика методов оптимизации нулевого порядка.
- •Метод прямого поиска (метод Хука-Дживса).
- •Метод деформируемого многогранника (метод Нелдера-Мида).
- •Метод вращающихся координат (метод Розенброка).
- •Метод параллельных касательных (метод Пауэлла).
- •Общая характеристика методов оптимизации первого порядка.
- •34.Метод наискорейшего спуска
- •35. Общая характеристика методов оптимизации второго порядка. Метод Ньютона.
- •36. Метод Ньютона с регулировкой шага (метод с переменной метрикой)
- •37. Метод статистических испытаний (метод Монте-Карло)
- •38. Вычисление кратных интегралов методом Монте-Карло
- •39. Структура искусственной нейронной сети (инс)
- •40. Компьютерная модель нейрона (нейроэлемента, нэ)
- •41. Функции активации нейроэлементов
- •45.Методы обучения элементарного перцептрона.
- •46.Многослойный перцептрон.
- •47. Понятие обучающей выборки.
36. Метод Ньютона с регулировкой шага (метод с переменной метрикой)
Употребляется также термин метод с переменной метрикой. Эти методы еще называют методами Ньютона ‑Рафсона, или демпфированными методами Ньютона. Они строятся по аналогии с градиентными методами с переменным шагом. Итерационный процесс в таком случае определяется выражением:
.
– обратная матрица для матрицы Гессе; – направление спуска.
Величина шага выбирается из условия минимума функции f(x)поαв направлении движения, т.е. в результате решения задачи одномерной минимизации:
Вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограмме оптимизации полагают , где E–единичная матрица. Очевидно, что итерация при этом осуществляется по методу наискорейшего спуска.
(Методы Ньютона требуют меньшей итерации, но по времени они могут быть намного больше.)
Он обладает сверх линейной или квадратичной скоростью сходимости в зависимости от требований.
В ряде случаев целесообразно комбинированное использование градиентных методов и метода Ньютона. В начале процесса оптимизации, когда точка x[0] находится далеко от точки экстремума x*, можно применять какой-либо вариант градиентных методов. Далее, при уменьшении скорости сходимости – метод Ньютона.
Алгоритм метода Ньютона
1. В начальной точке х[0] вычисляется вектор
р[0] = -H-1(x[0])f'(x[0])
2. На k-й итерации определяются шаг ak и точка х[k + 1] .
3. Вычисляется величина f(x[k + 1]).
4. Проверяются условия выхода, которые аналогичны условиям выхода изпри методе наискорейшего спуска. Если эти условия выполняются, вычисления прекращаются. Иначе -- вычисляется новое направление
p[k + 1] = -H-1(x[k + 1])f’(x[k + 1])
и осуществляется переход к следующей итерации.
Количество вычислений на одной итерации методом Ньютона, как правило, гораздо больше, чем в градиентных методах.
Причина -- необходимость вычисления и обращения матрицы вторых производных целевой функции.
С другой стороны, на получение решения с достаточной точностью с помощью метода Ньютона обычно требуется намного меньше итераций, чем при использовании градиентных методов.
Поэтому метод Ньютона существенно более эффективен. Он обладает сверхлинейной или квадратичной скоростью сходимости в зависимости от требований, которым удовлетворяет минимизируемая функция f(x).
В некоторых задачах трудоемкость итерации методом Ньютона может перекрыть выигрыш от малого их числа.
37. Метод статистических испытаний (метод Монте-Карло)
Общая схема метода Монте-Карло:
Допустим, что нам требуется вычислить какую-то неизвестную величину m. Попытаемся придумать такую случайную величину ξ, чтобы Mξ=m. Пусть при этом Dξ=b2.
Рассмотрим N случайных величинξ1,ξ2,…,ξN, распределения которых совпадают с распределениемξ.Если N достаточно велико, то согласно центральной предельной теореме теории вероятностей распределение суммы ρN=ξ1+ξ2+…+ξN будет приблизительно нормальным с параметрами a = Nm, σ2=Nb2, из правила «трех сигм» следует, что
Если мы поделим неравенство, стоящее в фигурной скобке, на N, то получим эквивалентное неравенство и вероятность его останется такой же:
Последнее соотношение перепишем в несколько ином виде:
Это — чрезвычайно важное для метода Монте-Карло соотношение. Оно дает нам и метод расчета m, и оценку погрешности.
В самом деле, найдем N значений случайной величиныξ.Все равно, находить ли один раз по одному значению каждой из величин ξ1,ξ2,…,ξN или найти N значений одной величины ξ, так как все эти случайные величины совпадают (имеют одно и то же распределение). Из (1) видно, что среднее арифметическоеэтих значений будет приближенно равно m. С большой вероятностью ошибка такого приближения не превосходит величины . Очевидно, эта ошибка стремится к нулю с ростом N.
При относительно небольшом числе испытаний в силу случайных причин меньшее число испытаний может иногда дать более точный результат, чем большее число испытаний.