Sp-алгоритм метода решений частичных проблем собственных значений. Градиентный метод расходящегося ряда. Метод Девидона-Флетчера- Пауэлла

где ,

Точка задается пользователем, величина шага определяется из условия:

                                 (4)

Решение задачи (4) может  осуществляться как из условий  , или из условий , , где - полином, аппроксимирующий функцию , так и численно, то есть путем поиска решения задачи методами одномерной оптимизации.

Формулы (2), (3) при аналитическом  решении задачи (4) обеспечивают построение последовательности положительно определенных матриц, таких, что при . Следствием этого для квадратичной функции является тот факт, что направления будут Н-сопряженными и, следовательно, алгоритм ДФП сойдется не более, чем за n шагов.

Для неквадратичных функций  алгоритм перестает быть конечным, и его сходимость зависит от точности решения  задачи (4). Глобальную сходимость алгоритма можно гарантировать лишь при его обновлении через каждые n шагов, т.е. когда в формуле (1)

 Построение последовательности заканчивается в точке , для которой , где ε –заданное число, или при (М – предельное число итераций), или при двукратном одновременном выполнении неравенств и . Как только условия выполнились, полагаем .

Недостаток алгоритма  ДФП состоит в том, что его  условия сходимости довольно чувствительны  к неточностям в подзадачах одномерной минимизации. Основным достоинством является сочетание высокой скорости сходимости с невысокой трудоемкостью итерации.

 

Иллюстрация метода:

 

 

Алгоритм:

1. Задать . Найти градиент  .
2. Положить k=0,  ;
3. Вычислить  ;
4. Проверить критерий окончания :

а) если критерий выполнен, то ;

б) если нет, то перейти  к шагу 5).

5. Проверить условие :

а) если неравенство выполнено  и  , то ;

б) если неравенство выполнено, но , то при заданном предельном количестве итераций решение не найдено;

в) иначе, перейти при k=0 к шагу 10, а при k>0 к шагу 6.

6. Вычислить .
7. Вычислить .
8. Вычислить

  .

 

9. Вычислить .
10. Определить
11. Вычислить из условия ;
12. Вычислить
13. Проверить условия и :

а) если оба неравенства  выполняются в двух последовательных итерациях с номерами k и k-1, то расчет окончен и ;

б) если нет, то положить k=k+1 и перейти к шагу 3).

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

 

В своей работе я исследовала  и реализовала метод решения  частичной проблемы собственных  значений и методы многомерной оптимизации.

Решены поставленные задачи - были разработаны и реализованы алгоритмы следующих методов:

- для решения частичной  проблемы собственных значений: метод скалярных произведений;

- для проведения многомерной  оптимизации: метод расходящегося  ряда.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемых источников.

 

1. Вержбицкий В.М. //Численные методы. Численные методы: Учеб. пособие для вузов. — М.: Высш. шк., 2001. — 382 с.:ил. ISBN 5-06-003982-Х
2. Бахвалов Н. С., Жидков Н. П., Кобелько Г.М. //Численные методы.-М.: Наука, 1987г.
3. Васильев Ф.П.//Численные методы решения экстремальных задач.-М.: Наука, 1990г.
4. Волков Б. А.// Численные методы.-М.: Наука, 1990г.
5. Пантелеев А.В., Летова Т.А.// Методы оптимизации в примерах и задачах: Учеб. пособие. -2-е изд.,исправл.-М.:Высш.шк., 2005. -544с.:ил. ISBN 5-06-004137-9
6. Интернет ссылка www.exponenta.ru.
7. Деннис Дж., Шнабель Р.// Численные методы безусловной оптимизации и решения НУ: пер. с англ.-М.: Мир, 1988-440с. ISBN 5-03-001102-1
8. Срочко В.А.// Численные методы: Курс лекций. – Иркутск. Иркут. ун-т, 2003.-168с.
9. Пшеничный Б.Н., Ланилин Ю.М.//Численные методы в экстремальных задачах. –М.: Наука, 1975.