Алгоритм Марквардта

Крок 1. Задати х⁽⁰⁾ початкове наближення до х^*, М – максимально припустима кількість ітерацій, Е –параметр збіжності.

Крок 2. Покласти К = 0, ⁽⁰⁾ = 10⁴.

Крок 3. Обчислити

Крок 4. Перевірити чи виконується нерівність < Е.

Якщо так – перейти до кроку 11, ні – перейти до наступного кроку.

Крок 5. Перевірити чи виконується нерівність К М.

Так - перейти до кроку 11, ні - перейти до наступного кроку.

Крок 6. Обчислити S(х^(к)) за формулою (4.16).

Крок 7. Покласти х^(к+1) = х^(к) + S(х^(к)).

Крок 8. Чи виконується нерівність < .

Так - перейти до кроку 9, ні - перейти до кроку 10.

Крок 9. Покласти ^(к+1)=1/2 ^(к), К=К+1. Перейти до кроку 3.

Крок 10. Покласти ^(К+1)= 2 ^(к). Перейти до кроку 6.

Крок 11. Друк результатів і зупинка.

Метод Марквардта характизується відносною простотою, властивістю спадання цільової функції при переході від ітерації до ітерації, високою швидкістю збіжності в околі точки мінімуму х^*, а також відсутністю процедури пошуку уздовж прямої. Головний недолік методу полягає в необхідності обчислення матриці Гессе й наступного рішення системи лінійних рівнянь, що відповідають рівнянню (4.16). Цей метод широко використається при рішенні задач, у яких f(х) записується у вигляді суми повних квадратів. Задача такого типу виникає, наприклад, у регресійному аналізі:

f(х) = f (х) + f (х) + … + … + f (х) (4.18)

Метод Марквардта відрізняється високою ефективністю при рішенні задач такого типу.

4.2 Порядок виконання роботи

4.2.1 Написати програму, що реалiзує один з градієнтних методів багатовимірної оптимізації.

4.2.2 За допомогою розробленої програми знайти мiнiмум функцiї (табл.. 1.1).

4.2.3 Порiвняти безградієнтні та градієнтні методи багатовимірної оптимізації за точнiстю знаходження оптимиму, кiлькiстю iтерацiй та часом роботи.

4.3 Зміст звіту

4.3.1 Сформульована мета роботи.

4.3.2 Алгоритм та програма, що реалізує обраний метод.

4.3.3 Результати роботи програми.

4.3.4 Аналіз отриманих результатів і висновки.

4.4 Контрольні питання

4.4.1 Які недоліки має метод Коши?

4.4.2 Які переваги методу Коши?

4.4.3 Властивості методу Ньютона.

4.4.4 Що покладено в основу методу Марквардта?

ЛІТЕРАТУРА

1. Банди Б. Методы оптимизации. Вводный курс: Пер с англ..-М.: Радио и связь, 1988.-128 с.

2. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.: Мир, 1981.-368 с.

3. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.-534 с.

4. Аоки М. Введение в методы оптимизации. - М.: Наука, 1977. – 343 с.

5. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. – 176 с.

6. Вагнер Г. Основы исследования операций: в 3х т.: Пер. с англ. – М.: Мир. Т.1, 1972. – 336 с., Т.2, 1973. – 488 с., Т.3, 1973. – 502 с.

7. Вентцель Е.С. Исследование операций. - М.: Сов. радио, 1972. - 552 с.

8. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. -М.: Мир, 1985.-509 с.

9. Деннис Дж. мл., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. - М.: Мир, 1988.- 440с.

10. Зайченко Ю.П. Исследование операций. – К.: Вища школа, 1979. – 392 с.

11. Зайченко Ю.П., Шумилова С.А. Исследование операций. Сборник задач. – К.: Вища школа, 1984. – 224 с.

12. Исследование операций: Пер. с англ.: В 2х т.: / Под ред. Дж. Моудера, С. Элмаграби. – М.: Мир, 1981. Т.1 – 712 с., Т.2 – 678 с.

13. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. - М.: Наука, 1978. - 352 с.

14. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. - М.: Наука, 1975.- 319 с.

15. Таха, Хэмди А. Введение в исследование операций: В 2х кн.: Пер. с англ. – М.: Мир, 1985. кн. 1 – 479 с., кн. 2 – 496 с.