Симплексний метод Нелдера-Міда або пошук багатогранником, що деформується
У процесі
пошуку здійснюється робота з регулярними
симплексами. Регулярні багатогранники
в просторі
називаються симплексами.
Для
регулярний симплекс являє собою
рівносторонній трикутник; при
- тетраедр і т.д.
Координати
вершин регулярного симплекса в
-мірному
просторі можуть бути визначені матрицею
D, у якій
стовпці являють собою вершини симплекса,
пронумеровані від 1 до (
), а рядки – координати вершин,
.
Матриця має розмірність
:
,
де:
;
;
– відстань
між вершинами.
У
найпростішому вигляді симплексний
алгоритм полягає в наступному. Будується
регулярний симплекс. З вершини, у якій
функція
максимальна
(т.1) проводиться проектна пряма через
центр ваги симплекса. Потім т.1 виключається
і будується новий відбитий
симплекс зі старих залишених точок і
однієї нової, розташованої на проектній
прямій на належній відстані від центра
ваги.
Продовження цієї процедури, у якій щораз виключається вершина, де цільова функція максимальна, а також використання правил зменшення розміру симплекса і запобігання циклічного руху в околиці екстремуму дозволяє досить ефективно визначати мінімум для "гладких" функцій. Але для "яружних" функцій такий пошук неефективний.
У симплексному алгоритмі Нелдера і Міда мінімізація функцій перемінних здійснюється з використанням деформованого багатогранника.
Будемо
розглядати
-у
ітерацію алгоритму. Нехай
,
,
є
-ю
вершиною в
на
-му
етапі пошуку,
,
і нехай значення цільової функції у
вершині
.
Відзначимо вершини з мінімальним і
максимальним значеннями. І позначимо
їх у такий спосіб:
і
Багатогранник
у
складається з
вершин
.
Позначимо через
- центр ваги вершин без точки
з максимальним значенням функції.
Координати цього центра обчислюються
за формулою:
,
.
(13.1)
Початковий багатогранник звичайно вибирається у вигляді регулярного симплекса (з вершиною на початку координат). Можна початок координат помістити в центр ваги. Процедура відшукання вершин у , у яких має краще значення, складається з наступних операцій: 1) відображення; 2) розтягування; 3) стиск; 4) редукція.
Методи першого порядку
До методів першого порядку відносяться алгоритми, у яких у процесі пошуку крім інформації про саму функцію використовується інформація про похідні першого порядку. До групи таких методів відносяться різні градієнтні методи: найшвидшого спуску, сполучених градієнтів, багатопараметричний пошук, запропонований Мілем і Кентрелом. Розглянемо один з цих методів.
Алгоритм найшвидшого спуску
Градієнт
функції в будь-якій точці показує
напрямок найбільшого локального
збільшення
.
Тому при пошуку мінімуму
,
варто рухатися в напрямку протилежному
напрямку градієнта
в даній точці, тобто в напрямку найшвидшого
спуску.
Ітераційна формула процесу найшвидшого спуска має вид
,
(13.7)
або
.
(13.8)
Очевидно,
що в залежності від вибору параметра
траєкторії спуску будуть істотно
розрізнятися. При великому значенні
траєкторія спуску буде являти собою
коливальний процес, а при занадто великих
процес може розходитися. При виборі
малих
траєкторія спуску буде плавною, але і
процес буде сходитися дуже повільно.
Як правило
вибирають з умови
(13.9)
в
ирішуючи
одномірну задачу мінімізації з
використанням деякого одномірного
методу. У цьому випадку одержуємо
алгоритм найшвидшого спуску.
Якщо
визначається в результаті одномірної
мінімізації, то градієнт у точці чергового
наближення буде ортогональним напрямку
попереднього спуска
.
Лекція №7 Методи інтерполяції таблично заданих функцій.
Интерполя́ция—в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.
Многим из тех, кто сталкивается с научными и инженерными расчётами часто приходится оперировать наборами значений, полученных экспериментальным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.
Экстраполя́ция (от лат. extrā — вне, снаружи, за, кроме и лат. polire — приглаживаю, выправляю, изменяю, меняю[1]) — особый тип аппроксимации, при котором функция аппроксимируется внезаданного интервала, а не между заданными значениями.
Иными
словами, экстраполяция — приближённое
определение значений функции 
в
точках 
,
лежащих вне отрезка 
,
по её значениям в точках 
.
В статистике экстраполя́ция — распространение установленных в прошлом тенденций на будущий период; распространение выборочных данных на другую часть совокупности, не подвергнутую наблюдению.
Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах.