дню інформацію. p> У більшості варіацій алгоритму Девідона функція мінімізується в кожному обраному напрямку пошуку. Для визначення мінімуму по у даному напрямку можна застосувати майже будь-яку ефективну процедуру одновимірного пошуку. Дуже важливо, щоб ця процедура була ефективною, оскільки відносно велика частина всього часу обчислення припадає на одновимірний пошук. p> Флетчер і Пауелл запропонували вибирати першу довжину з послідовності? * за допомогою наступного рівняння
,
де - найменше очікуване значення;
або покласти.
Алгоритми Пірсона
Алгоритм Пірсона № 2: Покладемо в рівнянні (1.6), а. Тоді
, (1.8)
,
де - довільна позитивно певна симетрична матриця. Алгоритм Пірсона № 2 зазвичай призводить до В«поганихВ» матрицям напрямків. p> Повторення початку алгоритму через кожні n кроків (тобто прирівнювання до після кожних n кроків) допомагає уникнути труднощів, пов'язаних з тим, що матриця напрямків перестає бути позитивно визначеною.
Алгоритм Пірсона № 3. Покладемо в рівнянні (1.6), а. br/>
Тоді, (1.9).
Метод Флетчера
, (1.10)
Описуваний алгоритм використовує (1.7а). якщо
,
і (1.10), якщо
.
Можна також використовувати лінійні комбінації рівнянь (1.10) і (1.7а). Оскільки матриця, обчислена за допомогою рівняння (1.7а), прагне до нуля із збільшенням числа кроків, а, обчислена за допомогою співвідношення (1.10), прагне до нескінченності, має сенс застосовувати обидва типи рівнянь. p> Ефективною процедуру Флетчера робить скоріше не метод обчислень, а кубічна інтерполяція при знаходженні мінімуму в даному напрямку і обмежена довжина кроку. При цьому скаляр вибирається за допомогою рівняння, де - нижня оцінка значень. (Якщо виявляється нижче, ніж, то має місце закінчення процесу.). Для досягнення мінімуму в напрямку пошуку використовується кубічна інтерполяція на інтервалі між і. Оскільки для проведення кубічної інтерполяції не потрібне використання всього інтервалу, що містить мінімум, і результат інтерполяції може виявитися незадовільним, якщо перебуває на увігнутої частини аппроксимирующего полінома, Флетчер обмежив значення таким чином: або воно повинно бути менше, ніж, одержуване за допомогою кубічної інтерполяції, або , де верхній індекс s позначає номер в послідовності кроків при одновимірному пошуку.
Після кожного кроку проводиться тест, і якщо він задоволений, то етап вважається завершеним. В іншому випадку триває кубічна інтерполяція. Остаточно процес завершується, коли. Щоб уникнути великого впливу помилок округлення або помилок програм обчислення похідних програма зупиняється, коли і і (або). p> Використовуючи ряд тестових завдань, Флетчер порівняв наведений вище алгоритм з алгоритмом Девідона - Флетчера - П...
