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

Министерство образования  и науки Российской Федерации

Государственное образовательное  учреждение

высшего профессионального образования

«Оренбургский Государственный  Университет»

 

Факультет экономики и управления

Кафедра математических методов и  моделей в экономике

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

по дисциплине «Численные методы»

 

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

Метод Девидона-Флетчера- Пауэлла»

ГОУ ОГУ 080116.5011.09 ОО

 

 

                

       

 

Руководитель     

_________________Яркова О.  Н.

Исполнитель  

студент гр. 09ММЭ

____________Салахутдинова  Р.М

 «_____» _______________2011 г.

 

 

 

 

 

 

 

 

 

 

 

Оренбург 2011

                                         Содержание

            Введение…………………………………………………………………..3

1. Методы решения частичной проблемы собственных

значений…………………………………………………………………………..5

                1.1 Степенной метод…………………………………………………..5

    1.2 Метод скалярных произведений…………………………………7

2. Методы многомерной оптимизации………………………………...8

                2.1 Метод расходящегося ряда……………………………………….8

            3. Метод Девидона – Флетчера – Пауэлла…………………………….10

Заключение……………………………………………………………...13

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

                                

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Часто в практических вычислениях бывают нужны не все  собственные значения, а лишь некоторые  из них. В этих случаях нецелесообразно  решать полную проблему собственных  значений.

Для решения частичной проблемы собственных значений, состоящей в определении одного или нескольких собственных значений и соответствующих им собственных векторов, обычно используются итерационные методы. Строится такой итерационный процесс, который сходится к одному собственному значению и собственному вектору, причем используемые алгоритмы обычно весьма экономичны.

Итерационный процесс  строится на основании применения методов  итераций к решению системы уравнений  . (1)

Используем метод простой  итерации. Пусть X⁽⁰⁾ - начальное приближение собственного вектора X, причем собственные векторы на каждой итерации нормированы. Итерационный процесс запишется в виде  

        (2)

Подставляя в правую часть этой системы вектор X⁽⁰⁾, получаем после его умножения слева на матрицу A некоторый вектор Y⁽¹⁾. После нормировки этого вектора он представится в виде Y⁽¹⁾ = l ⁽¹⁾X⁽¹⁾, где l ⁽¹⁾ - постоянная, X⁽¹⁾ - нормированный вектор. Теперь нужно X⁽¹⁾ снова подставить в правую часть (32) и найти новые приближения l ⁽²⁾ и X⁽²⁾. Итерационный процесс продолжается до установления постоянных значений l и X. При этом найденное число l - наибольшее по модулю собственное значение данной матрицы A, а X - соответствующий ему собственный вектор.

Скорость сходимости этого итерационного процесса зависит  от удачного выбора начального приближения. Если начальный вектор близок к истинному собственному вектору, то итерации сходятся быстро.

Для решения системы (1) можно использовать и другие итерационные методы. В частности, метод Ньютона  дает лучшую сходимость, если удачно выбрано  начальное приближение X⁽⁰⁾. В этом случае бывает достаточно нескольких итераций.

В некоторых задачах  нужно искать не наибольшее, а наименьшее собственное значение матрицы A. В этом случае можно умножить систему (1) на обратную матрицу A^-1:

.

Отсюда, деля обе части этого равенства на l и учитывая, что A^-1A = E, получаем

. (3)

Эта задача отличается от ранее рассматриваемой тем, что  здесь будет вычисляться наибольшее собственное значение 1/l , что будет  достигнуто при наименьшем l . Следовательно, рассмотренный выше итерационный процесс может быть использован также для нахождения наименьшего собственного значения обратной матрицы (собственные значения матриц A и A^-1 обратны друг другу).

 

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

Задачи:

разработать и реализовать  алгоритмы следующих методов:

- степенной метод;

- метод расходящегося ряда;

- метод  Девидона-Флетчера-Пауэлла.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.  Методы решения частичной проблемы собственных

 значений

Пусть наибольшее по модулю собственное значение матрицы А  l₁  вещественное и простое. Предположим, что собственные числа матрицы пронумерованы следующим образом:

Для нахождения l₁ выберем Y⁽⁰⁾  — начальный вектор. Y⁽⁰⁾  следует выбирать так, чтобы коэффициент l₁ в разложении Y⁽⁰⁾ =l₁x₁+l₂x₂+…l_nx_n  не был бы слишком мал. Здесь x₁, x₂,…, x_n — собственные векторы, так что Ax_i=l_ix_i, i=1,…,n. Y⁽⁰⁾ выбирается опытным путем.

Далее строится последовательность векторов Y⁽¹⁾, Y⁽²⁾,… по формуле Y^(k+1)=AY^(k).

1.  Степенной метод.

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

Пусть о вещественной nxn матрицы А известно, что она является матрицей простой структуры, т.е имеет ровно n линейнонезависимых собственных векторов(базис):

    (1)

Пусть нумерация этих векторов отвечает упорядочению соответствующих  им собственных чисел по убыванию модулей:

                                 (2)

Ставим задачу приближенного  вычисления наибольшего по модулю собственного числа λ₁    и соответственного ему собственного вектора x ₁ данной матрицы А.

Возьмем произвольный ненулевой  вектор y⁽⁰⁾ и запишем его разложение по базису собственных векторов:

                       (3)     

Выполним первую итерацию вектора    y⁽⁰⁾  умножением равенства (3) слева на матрицу А:

В силу последнее можно переписать в виде:

Выполняем вторую итерации по такому же принципу и получаем:

k-я итерация вектора y⁽⁰⁾ с помощью матрицы А дает вектор:

  (4)  

Или, с учетом представления x₁, x₂ ,.., x_n в исходном базисе

Берем отношение компонент  итерированного вектора:

   

(5)

 

Представляя вектор y^(k) на основе (4)

   (6)

можно сделать вывод, что в силу , в фигурных скобках выражения (6) линейной комбинации векторов x₁ , x₂,..,x_n с ростом k начнет доминировать первое слагаемое. Это означает, что вектор y^(k) от итерации к итерации будет давать все большее хорошее приближение к собственному вектору x₁  по направлению.

1.2 Метод скалярных произведений.

Модификация степенного метода называется методом скалярных произведений. Реализовать её можно в виде SP-алгоритма.

Алгоритм метода

Шаг 1. Дана симметричная  n×n -матрица А, произвольный  начальный вектор  y⁽⁰⁾, малое число ε>0 , число λ⁽⁰⁾ для начального сравнения. Положить k=1.

Шаг 2.Вычистить скаляры s⁽⁰⁾=(y⁽⁰⁾, y⁽⁰⁾), 
׀׀ y⁽⁰⁾ ׀׀₂=√ s⁽⁰⁾ и вектор x⁽⁰⁾= y⁽⁰⁾/ ׀׀ y⁽⁰⁾ ׀׀_2.

Шаг 3.Вычислить y^(k)=Ax^(k-1) (итерация нормированного вектора).

Шаг 4. Вычислить s^(k)=(y^(k), y^(k)) и t^(k)=(y^(k), x^(k-1) ),  
׀׀ y^(k) ׀׀₂=√ s^(k), x^(k)= y^(k)/ ׀׀ y^(k) ׀׀₂ , λ^(k)= s^(k)/t^(k) . 
 
Шаг 5.Если |λ^(k) - λ^(k-1)|>ε, то положить k:=k+1 и вернуться к шагу 3, иначе завершить работу алгоритма, считая λ₁:≈ λ^(k) , x₁:≈ x^(k).

                            

 

 

 

 

 

 

 

 

 

 

 

 

2. Методы многомерной оптимизации

 

2.1 Метод расходящегося  ряда.

 

 Градиент функции в некоторой точке направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня в этой точке. Находясь в очередной точке и каждый раз выбирая в качестве направления движения градиент (или антиградиент - вектор противоположной направленности), мы приходим к итерационному процессу возрастания (убывания) функции. Этот итерационный процесс можно выразить следующей формулой:

где - параметр, определяющий длину и направление очередного шага;

-grad   - антиградиент функции в текущей точке.

Вектор  задает направление убывания функции в точке x, если .

Градиентные методы представляют собой методы спуска, в которых  в качестве направлений убывания выбирается направление антиградиента  функции.

  ,где   -grad

Метод вида:   , где , называется методом спуска, если вектор на каждом шаге принадлежит множеству направлений убывания функции в точке ,

Начиная с некоторого x⁰ , строится последовательность такая, что  , при всех .

 Критерием остановки  итерационной последовательности  являются обычно следующие неравенства:

      или      ║grad ║ .

 

Априорный выбор коэффициентов (метод расходящегося ряда), т. е    - выбирается до начала вычислений. Например, , т. е ряд расходящийся, а ряд - сходящийся. Условие сходимости ряда из квадратов накладывается, чтобы добиться достаточно быстрой сходимости последовательности к нулю, с целью обеспечения сходимости метода в окрестности точки минимума функции, а условие расходимости  ряда    нужно для обеспечения достижения точки минимума даже при неудачном выборе начального  приближения.

 

Алгоритм  метода расходящегося ряда.

1. Задаём точку начального приближения , - точность результатов. На первом шаге считаем k:=1,задаем с.
2. Вычисляем значение α_k=c/(k+1), находим точку следующего приближения , где h^k значение антиградиента функции в точке x^k.
3. Проверяем критерий остановки. Если норма градиента в точке x^k+1 меньше ε, то останавливаемся, иначе увеличиваем k на единицу и возвращаемся к пункту 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  Метод  Девидона – Флетчера – Пауэлла.

 

Рассмотрим алгоритм Девидона–Флэтчера–Пауэлла (Д-Ф-П) минимизации дифференцируемой функции нескольких переменных.

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

Пусть дана функция  на множестве и имеющая непрерывные частные производные во всех его точках. Требуется найти локальный минимум функции на множестве допустимых решений , т.е. найти такую точку , что

Стратегия метода ДФП состоит в построении последовательности точек , k=0,1…, таких, что . Точки последовательности вычисляются по правилу:

                                   (1)

где есть матрица размера nxn, которая вычисляется по правилу:

                                                   (2)

,                                           (3)

где ,

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

                                 (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.