Изложение метода 18 icon

Изложение метода 18



НазваниеИзложение метода 18
Дата17.10.2016
Размер
ТипИзложение




Содержание


Введение в метод 7

Метод градиентного спуска 8

Идея метода 8

Алгоритм 9

Критерий останова 9

Сходимость градиентного спуска с постоянным шагом 9

Выбор оптимального шага 10

Градиентный метод с дроблением шага 12

Метод наискорейшего спуска 13

Числовые примеры 14

Метод градиентного спуска с постоянным шагом 14

Градиентный метод с дроблением шага 14

Метод наискорейшего спуска 15

Рекомендации при программировании 16

Введение в метод 17

Постановка задачи оптимизации 17

Метод сопряжённых градиентов для квадратичного функционала 18

Изложение метода 18

Анализ метода 19

Численный пример 21

Заключение 21

Метод сопряжённых градиентов в общем случае 21

Анализ метода 22

Числовой пример 24

Рекомендации при программировании 25

Заключение 26

Введение

Используя градиентные методы, можно найти решение любой задачи нелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки X(k) осуществляется последовательный переход к некоторым другим точкам, до тех пор, пока не выявляется приемлемое решение исходной задачи.


^

Введение в метод


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

(1)

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

В статье приведены теоремы сходимости метода градиентного спуска, а также рассмотрена его варианты:

  • Метод градиентного спуска с постоянным шагом

  • Метод градиентного спуска с дроблением шага

  • Метод наискорейшего спуска
^

Метод градиентного спуска






Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в раз".
^

Идея метода


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

где выбирается

  • постоянной, в этом случае метод может расходиться;

  • дробным шагом, т.е. длина шага в процессе спуска делится на некое число;

  • наискорейшим спуском:

Алгоритм


Вход: функция

Выход: найденная точка оптимума

  1. Повторять:

  2. , где выбирается одним из описанных выше способов

  3. если выполен критерий останова, то возвращаем текущее значение
^

Критерий останова


Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:





Здеcь - значение, полученное после -го шага оптимизации. - наперед заданное положительное число.
^

Сходимость градиентного спуска с постоянным шагом


Теорема 1 «О сходимости метода градиентного спуска с постоянным шагом.»

Пусть , функция дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента : . Пусть .

Тогда при любом выборе начального приближения.

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

Определение. Дифференцируемая функция называется сильно выпуклой (с константой ), если для любых и из справедливо

Теорема 2 о сходимости метода градиентного спуска с постоянным шагом.

Пусть функция дифференцируема, сильно выпукла с константой . Пусть выполняется условие Липшица для градиента : . Пусть .

Тогда при любом выборе начального приближения.
^

Выбор оптимального шага






Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.

Константа , фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага . Нетрудно видеть, что величина минимальна, если шаг выбирается из условия , т. е. если .

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

.

В качестве и могут выступать равномерные по x оценки сверху и снизу собственных значений оператора . Если , то и метод сходится очень медленно. Геометрически случай соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на , задаваемая формулой:

.

Поведение итераций градиентного метода для этой функции изображено на рис. 2 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число (характеризующее, грубо говоря, разброс собственных значений оператора ) называют числом обусловленности функции . Если , то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.

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

Градиентный метод с дроблением шага


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

(2)

,

где - некоторая заранее выбранная константа.

Процедуру нахождения такого обычно оформляют так. Выбирается число и некоторый начальный шаг . Теперь для каждого k полагают и делают шаг градиентного метода. Если с таким условие (2) выполняется, то переходят к следующему k. Если же (2) не выполняется, то умножают на ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (2) не будет выполняться. В условиях теоремы 1 эта процедура для каждого k за конечное число шагов приводит к нужному .

Можно показать, что в условиях теоремы 2 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора на каждом шаге, заменяя ее на проблему выбора параметров и , к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
^

Метод наискорейшего спуска






Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции на луче L.

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

.

Другими словами, выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 3). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.

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

В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
^

Числовые примеры

Метод градиентного спуска с постоянным шагом


Для исследования сходимости метода градиентного спуска с постоянным шагом была выбрана функция:

.

Начальное приближение - точка (10,10). Использован критерий останова:

Результаты эксперимента отражены в таблице:

Значение шага

Достигнутая точность

Количество итераций

0.1

метод расходится

0.01

2e-4

320

0.001

2e-3

2648

0.0001

1e-2

20734

Из полученных результатов можно сделать вывод, что при слишком большом чаге метод расходится, при слишком малом сходится медленно и точчность хуже. Надо выбирать шаг наибольшим из тех, при которых метод сходится.
^

Градиентный метод с дроблением шага


Для исследования сходимости метода градиентного спуска с дроблением шага (2) была выбрана функция:

.

Начальное приближение - точка (10,10). Использован критерий останова:

Результаты эксперимента отражены в таблице:

Значение параметра

Значение параметра

Значение параметра

Достигнутая точность

Количество итераций

0.95

0.95

1

5e-4

629

0.1

0.95

1

1e-5

41

0.1

0.1

1

2e-4

320

0.1

0.95

0.01

2e-4

320

Из полученных результатов можно сделать вывод об оптимальном выборе параметров: , хотя метод не сильно чувствителен к выбору параметров.
^

Метод наискорейшего спуска


Для исследования сходимости метода наискорейшего спуска была выбрана функция:

.

Начальное приближение - точка (10,10). Использован критерий останова:

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

Метод получил точность 6e-8 за 9 итераций.

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

Недостатком методом наискорейшего спуска явлляется необходимость решать одномерную задачу оптимизации.
^

Рекомендации при программировании


При программировании методов градиентного спуска следует аккуратно относится к выбору параметров, а именно

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

  • Градиентный метод с дроблением шага не очень чувствителен к выбору параметров. Один из вариантов выбора параметров:

  • Метод наискорейшего спуска: в качестве метода одномерной оптимизации можно использовать метод золотого сечения (когда он применим).

































^

Введение в метод


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

Постановка задачи оптимизации


Пусть задано множество и на этом множестве определена целевая функция (objective function) . Задача оптимизации состоит в нахождении на множестве точной верхней или точной нижней грани целевой функции.
Множество точек, на которых достигается нижняя грань целевой функции обозначается .

Если , то задача оптимизации называется безусловной (unconstrained). Если , то задача оптимизации называется условной (constrained).
^

Метод сопряжённых градиентов для квадратичного функционала

Изложение метода


Рассмотрим следующую задачу оптимизации:

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

Каждое следующее приближение вычисляется по формуле:

Определение. Два вектора и называются сопряжёнными относительно симметричной матрицы B, если

Опишем способ построения базиса в методе сопряжённых градиентов В качестве начального приближения выбираем произвольный вектор. На каждой итерации выбираются по правилу:

Базисные вектора вычисляются по формулам:


Коэффициенты выбираются так, чтобы векторы и были сопряжёнными относительно А.


Если обозначить за , то после нескольких упрощений получим окончательные формулы, используемые при применении метода сопряжённых градиентов на практике:

^

Анализ метода


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






^

Сходимость метода


Если все вычисления точные, и исходные данные точны то метод сходится к решению системы не более чем за итераций, где - размерность системы. Более тонкий анализ показывает, что число итераций не превышает , где - число различных собственных значений матрицы A. Для оценки скорости сходимости верна следующая (довольно грубая) оценка:

, где

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

.
^

Вычислительная сложность


На каждой итерации метода выполняется операций. Такое количество операций требуется для вычисления произведения - это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций. Суммарная вычислительная сложность метода не превышает - так как число итераций не больше n.
^

Численный пример


Применим метод сопряжённых градиентов для решения системы , где

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

Заключение


Метод сопряжённых градиентов - один из наиболее эффективных методов решения СЛАУ с положительно определённой матрицей. Метод гарантирует сходимость за конечное число шагов, а нужная точность может быть достигнута значительно раньше. Основная проблема заключается в том, что из-за накопления погрешностей может нарушаться ортогональность базисных веторов , что ухудшает сходимость
^

Метод сопряжённых градиентов в общем случае


Расссмотрим теперь модификацию метода сопряжённых градиентов для случая, когда минимизируемый функционал не является квадратичным: Будем решать задачу:

.

- непрерывно дифференцируемая в функция. Чтобы модифицировать метод сопряжённых градиентов для решения этой задачи необходимо получить для формулы, в которые не входит матрица А:


можно вычислять по одной из трёх формул:

  1. - Метод Флетчера - Ривса (Fletcher–Reeves method)

  2. - Метод Полака - Райбера (Polak–Ribi`ere method)



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

Анализ метода


Если функция - не квадратичная, метод сопряжённых градиентов может и не сходиться за конечное число шагов. Кроме того, точное вычисление на каждом шаге возможно только в редких случаях. Поэтому накопление погрешностей приводит к тому, что вектора перестают указывать направление убывания функции . Тогда на каком-то шаге полагают . Совокупность всех номеров , при которых принимается , обозначим за . Номера называются моментами обновления метода. На практике часто выбирают , где - размерность пространства.
^

Сходимость метода


Для метода Флетчера - Ривса существует теорема о сходимости, накладывающая не слишком жёсткие условия на минимизируемую функцию :
Теорема.
Пусть и выполняются следующие условия:

  1. удовлетворяет строгим условиям Вольфа:



    1. где

  2. Множество ограничено

  3. Производная удовлетворяет условию Липшица с константой в некоторой окрестности

множества M: .
Тогда

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

Тем не менее, на практике метод Полака-Райбера работает лучше.
Наиболее распространённые критерии останова на практике: Норма градиента становится меньше некоторого порога
Значение функции в течении m последовательных итераций почти не изменилось
^

Вычислительная сложность


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

Числовой пример


Будем искать методом сопряжённых градиентов минимум функции . Минимум этой фнкции равен 1 и достигается в точке (5, 4). Сравним на примере этой функции методы Полака-Райбера и Флетчера-Ривса. Итерации в обоих методах прекращаются, когда на текущем шаге квадрат нормы градиента становится меньше . Для выбора используется метод золотого сечения



Метод Флетчера - Ривса

Метод Полака - Райбера

Число итераций

Найденное решение

Значение функции

Число итераций

Найденное решение

Значение функции

0.01

18

(5.01382198,3.9697932)

1.00110367

15

(5.03942877,4.00003512)

1.00155463

0.001

20

(5.01056482,3.99018026)

1.00020805

18

(4.9915894,3.99999044)

1.00007074

0.0001

24

(4.9979991,4.00186173)

1.00000747

20

(5.00336181,4.0000018)

1.0000113

0.00001

25

(4.99898277,4.00094645)

1.00000193

22

(4.99846808,3.99999918)

1.00000235

0.00001

29

(4.99974658,4.0002358)

1.00000012

26

(4.99955034,3.99999976)

1.0000002
^






Рекомендации при программировании


Реализовано два варианта метода сопряжённых градиентов: для минимизации квадратичного функционала, и для минимизации произвольной функции. В первом случае метод реализуется функцией
vector FindSolution(matrix A, vector b)
Здесь A и b - матрица и вектор, фигурирющие в определении квадратичной задачи оптимизации.
Для минимизации произвольного функционала можно использовать одну из двух функций:
vector FletcherRievesMethod(int spaceSize, Function F, vector (*GradF) (vector))
vector PolakRibiereMethod(int spaceSize, Function F, vector (*GradF) (vector))
Параметры для обеих функций совпадают и имеют следующий смысл:
spaceSize - размерность пространства( число переменных, от которых зависит минимизируемый функционал)
F - указатель на минимизируемую функцию. Функция должна иметь вид double <имя функции>( vector)
GradF - указатель на функцию, вычисляющую градиент минимизируемого функционала
Оба метода используют вспомогательную функцию для решения задачи одномерной оптимизации. В программе реализована одномерная оптимизация методом золотого сечения.








Заключение


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


Список литературы.

1. В.И. Ракитин, В.Е. Первушин. Практическое руководство по методам вычислений. 1998.

2. И.Л. Акулич Математическое программирование в примерах задачах

3. Боглаев Ю.П. Вычислительная математика и программирование. – М.: Высшая школа, 1990.

4. Демидович Б.П., Марон Н.А. Основы вычислительной математики. - М.: Наука, 1970.

5. Н.Н.Калиткин.  Численные методы. Москва «Наука», 1978.

6. Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов. Методы оптимизации. 2000.

7. Р.Р.Ахмеров.  Методы оптимизации гладких функций.

8. Васильев Ф. П.   Методы оптимизации - Издательство «Факториал Пресс», 2002

9. Петров И.Б., Лобанов А.И. - Лекции по вычислительной математике 2006


Приложение

//Программа для поиска минимума функции методом градиентного спуска

#include

#include

#include


#define METHOD (2)

//выбор метода определения длины шага

//1 - метод градиентного спуска с постоянным шагом

//2 - Градиентный метод с дроблением шага

//3 - Метод наискорейшего спуска


//константа для метода градиентного спуска с постоянным шагом

//начальное значение eps для метода с дроблением шага

#define LAMBDA_CONSTANT (1)


//параметры для метода с дроблением шага

#define DELTA_FOR_METHOD2 (0.95)

#define EPS_FOR_METHOD2 (0.1)


//максимально возможное число итераций

#define NUMBER_OF_ITERATIONS (100000)


//eps для критерия останова

#define EPS (1e-5)


//критерий останова

#define OSTANOV (2)


using namespace std;


vector goldensectionoptimize(vector x,double a, double b, int n);

double f(vector x);

vector GradientDescent(int N,vector x0,int&Iterations);


double f(vector x)

//функция минимум которой ищут

{

//int l=x.size();

//return (100*(x[1]-x[0]*x[0])*(x[1]-x[0]*x[0])+(1-x[0])*(1-x[0]));

return 10*x[0]*x[0]+x[1]*x[1];

}


vector GradientF(vector x)

//градиент исследуемой функции

{

vector tmp;

//tmp.push_back(-2*(1-x[0])-400*(x[1]-x[0]*x[0])*x[0]);

//tmp.push_back(200*x[1]);

tmp.push_back(20*x[0]);

tmp.push_back(2*x[1]);

return tmp;

}


vector GradientDescent(int N,vector x0,int&Iterations)

//minimizes N-dimensional function f; x0 - start point

{

vector old,cur_x=x0,gr;

double s,Lambda;

int j,i;


Lambda=LAMBDA_CONSTANT;

for (Iterations=1;Iterations<=NUMBER_OF_ITERATIONS;Iterations++)

{

//save old value

old=cur_x;

//compute gradient

gr=GradientF(cur_x);


if (METHOD==1)

{


Lambda=LAMBDA_CONSTANT;

//вычисляем новое значение

for(j=0;j
cur_x[j]=cur_x[j]-Lambda*gr[j];

}


if (METHOD==2)

{

//вычисляем новое значение

for(j=0;j
cur_x[j]=cur_x[j]-Lambda*gr[j];


//вычисляем квадрат нормы градиента

s=0;

for(j=0;j
s+=gr[j]*gr[j];


while (f(cur_x)>f(old)-EPS_FOR_METHOD2*Lambda*s)

{

Lambda=Lambda*DELTA_FOR_METHOD2;

//пересчет значения Лямда

cur_x=old;

for(j=0;j
cur_x[j]=cur_x[j]-Lambda*gr[j];

}

}


if (METHOD==3)

{

cur_x=goldensectionoptimize(cur_x,-10,10,100);

}


if(OSTANOV==1)

{

//условие останова 1

s=0;

for(j=0;j
s+=(old[j]-cur_x[j])*(old[j]-cur_x[j]);

s=sqrt(s);

if (s
return cur_x;

}


if(OSTANOV==2)

{

//условие останова 2

s=fabs(f(cur_x)-f(old));

if (s
return cur_x;

}


}


return cur_x;

}


int main()

{

vector x;

x.push_back(10);

x.push_back(10);

int i,Iteration;

vector ans=GradientDescent(2,x,Iteration);

cout<<"Value: "<
cout<<"Point: ";

for(i=0;i
cout<
cout<
return 0;

}


vector goldensectionoptimize(vector x,double a, double b, int n)

//метод золотого сечения одномерной оптимизации функции f

//вектор переменных x на отрезке [a,b], n итераций

{

vector tmp=x;

int i,j;

double s1;

double s2;

double u1;

double u2;

double fu1;

double fu2;

vector GF=GradientF(x);


s1 = (3-sqrt(double(5)))/2;

s2 = (sqrt(double(5))-1)/2;

u1 = a+s1*(b-a);

u2 = a+s2*(b-a);

for(j=0;j
tmp[j]=x[j]+u1*GF[j];

fu1 = f(tmp);

for(j=0;j
tmp[j]=x[j]+u2*GF[j];

fu2 = f(tmp);


for(i = 1; i <= n; i++)

{

if( fu1<=fu2 )

{

b = u2;

u2 = u1;

fu2 = fu1;

u1 = a+s1*(b-a);

for(j=0;j
tmp[j]=x[j]+u1*GF[j];

fu1 = f(tmp);

}

else

{

a = u1;

u1 = u2;

fu1 = fu2;

u2 = a+s2*(b-a);

for(j=0;j
tmp[j]=x[j]+u2*GF[j];

fu2 = f(tmp);

}

}

for(j=0;j
tmp[j]=x[j]+u1*GF[j];

fu1 = f(tmp);

for(j=0;j
tmp[j]=x[j]+u2*GF[j];

fu2 = f(tmp);


if (fu1
for(j=0;j
tmp[j]=x[j]+u1*GF[j];

else

for(j=0;j
tmp[j]=x[j]+u2*GF[j];

return tmp;

}


/* Метод сопряжённых градиентов для решения СЛАУ . */


/*Программа читает входные данные из файла input.txt и выводит решение системы в файл output.txt*/


#include "ublas/matrix.hpp"

#include "ublas/io.hpp"

#include "ublas/vector.hpp"

#include

#include

#include


using namespace boost::numeric::ublas;


//Метод решает СЛАУ Ax = b

//A - симметричная положительно определённая матрица


vector FindSolution(matrix A, vector b)

{

const double EPS = 1e-5;

//Прибижённое решение

vector x = zero_vector(A.size1());

//Невязка

vector r = b - prec_prod(A , x);

//Базисный вектор

vector p = r;

double rSquare = inner_prod(r, r);

int numIter = 0;

while (rSquare > EPS)

{

numIter++;

vector temp = prec_prod(A, p);

double alpha = rSquare / inner_prod(temp, p);

x = x + alpha * p;


vector rNew = r - alpha * temp;

double rNewSquare = inner_prod(rNew, rNew);

double beta = rNewSquare / rSquare;

r = rNew;

rSquare = rNewSquare;

p = r + beta * p;

}


std::cout <<"Число итераций: " << numIter << std::endl;

return x;

}


int main()

{

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);


int m, n;

std::cin >> n;

matrix A(n, n);

vector b(n);


for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

std::cin >> A(i, j);

for (int i = 0; i < n; i++) std::cin >> b[i];

vector x = FindSolution(A, b);


std::cout.precision(9);

std::cout << "Решение системы: " << std::endl;

std::cout << "(";

for (int i = 0; i < n; i++)

if (i < n - 1) std::cout << x[i] << ", ";

else std::cout << x[i] << ")" << std::endl;


return 0;

}


/*Метод сопряжённых градиетов для минимизации произвольной функции в R^n. */

#include

#include

#include "ublas/vector.hpp"

#include "ublas/io.hpp"


double eps = 1e-3;


using namespace boost::numeric::ublas;


typedef double (*Function)(vector) ;


double F1(vector x)

{

return (x[0] - 5) * (x[0] - 5) * (x[1] - 4) * (x[1] - 4) + (x[0] - 5) * (x[0] - 5) + (x[1] - 4) * (x[1] - 4) + 1;

}


vector GradF1(vector x)

{

vector res(x.size() );

res[0] = 2 * (x[0] - 5) * ( (x[1] - 4) * (x[1] - 4) + 1);

res[1] = 2 * (x[1] - 4) * ( (x[0] - 5) * (x[0] - 5) + 1);

return res;

}


double FQuad(vector x)

{

return (x[0] - 1) * (x[0] - 1) + (x[1] -2) * (x[1] - 2);

}


vector GradFQuad(vector x)

{

vector res(x.size());

res[0] = 2 * (x[0] - 1);

res[1] = 2 * (x[1] - 2);

return res;

}


//Одномерная оптимизация - применим метод золотого сечения

//В общем случае - требуется провести исследование, какой метод лучше применить

double FindMin(Function F, vector s, vector p)

{

const double EPS = 1e-8;

double a = 0;

double b = 1e5;

double x0 = a + 0.5 * (3 - sqrt(5.0)) * (b - a);

double x1 = b - x0 + a;


while (abs(b - a) > EPS)

{

if (F(s + x0 * p) < F(s + x1 * p) ) b = x1;

else a = x0;

x1 = x0;

x0 = b + a - x1;

}

return (a + b)/2;

}


void PrintSolution(vector x, double val, int numIter)

{

std::cout << "-----------------------" << std::endl;

std::cout << "Number of iterations: " << numIter << std::endl;

std::cout << "Computed solution: " << std::endl;

std::cout << x << std::endl;

std::cout << "Function value: " << val << std::endl << std::endl;

}


vector FletcherRievesMethod(int spaceSize, Function F, vector (*GradF) (vector))

{

//F - указатель на минимизируемую функцию

//GradF - указатель на градиент F

const double EPS = 1e-5;

//Начальное приближение

vector x = zero_vector(spaceSize);

double curVal = F(x);

double prevVal = curVal;

vector p = - GradF(x);

double gradSquare = inner_prod(p, p);


int numIter = 0;

do

{

numIter++;

double alpha, beta, newGradSquare;

vector newGrad;


//Ищем минимум F(x + alpha * p) с помощью метода одномерной оптимизации

alpha = FindMin(F, x, p);

x = x + alpha * p;


newGrad = - GradF(x);

newGradSquare = inner_prod(newGrad, newGrad);

if (numIter % (5 * spaceSize) == 0) beta = 0; //Обновление

else

beta = newGradSquare / gradSquare; //Используем метод Флетчера - Ривса

p = newGrad + beta * p;


prevVal = curVal;

curVal = F(x);


gradSquare = newGradSquare;

}

while (gradSquare > eps);


std::cout << "Fletcher-Rieves Method: " << std::endl;

PrintSolution(x, F(x), numIter);

return x;


}


vector PolakRibiereMethod(int spaceSize, Function F, vector (*GradF) (vector))

{

//F - указатель на минимизируемую функцию

//GradF - указатель на градиент F

const double EPS = 1e-5;

//Начальное приближение

vector x = zero_vector(spaceSize);

double curVal = F(x);

double prevVal = curVal;

vector grad = - GradF(x);

vector p = - grad;

double gradSquare = inner_prod(p, p);


int numIter = 0;

do

{

numIter++;

double alpha, beta, newGradSquare;

vector newGrad;


//Ищем минимум F(x + alpha * p) с помощью метода одномерной оптимизации

alpha = FindMin(F, x, p);

x = x + alpha * p;


newGrad = - GradF(x);

newGradSquare = inner_prod(newGrad, newGrad);


if (numIter % (5 * spaceSize) == 0) beta = 0; //Обновление

else

beta = -(newGradSquare - inner_prod(newGrad, grad) )/ gradSquare; //Используем метод Флетчера - Ривса

p = newGrad + beta * p;


prevVal = curVal;

curVal = F(x);


grad = newGrad;

gradSquare = newGradSquare;

}

while (gradSquare > eps );


std::cout << "Polak-Ribiere Method: " << std::endl;

PrintSolution(x, F(x), numIter);

return x;


}


int main()

{

std::cout.precision(9);

FletcherRievesMethod(2, &F1, &GradF1);

PolakRibiereMethod(2, &F1, &GradF1);


return 0;

}




Похожие:

Изложение метода 18 iconОсновоположником экспериментально-математического метода исс­ледования природы был великий итальянский ученый Галилео Галилей (1564- 1642)
Галилео Галилей (1564- 1642). Леонардо да Винчи дал лишь наброски такого метода изучения природы, Галилей же оставил развернутое...
Изложение метода 18 iconПамятка для учащихся «Как писать сжатое изложение» Внимательно прочитайте написанное вами подробное изложение
Сжатое изложение это форма обработки информации исходного текста, позволяющая проверить комплекс необходимых жизненных умений, важнейшими...
Изложение метода 18 iconГалилео Галилей (1564-1642)
Леонардо да Винчи, его основоположником считается великий итальянский ученый Галилео Галилей (1564 1642), который оставил развернутое...
Изложение метода 18 iconКак писать изложение
Пересказ это самостоятельное речевое произведение, которое можно определить как изложение "своими словами"
Изложение метода 18 iconЛекция 10. Корректность методов. Рекурсия Корректность метода. Спецификации. Триады Хоара. Предусловие метода. Постусловие метода.
Частичная корректность. Завершаемость. Полная корректность. Инвариант цикла. Вариант цикла. Подходящий инвариант. Корректность циклов....
Изложение метода 18 iconИзложение фактов изложение имевших место нарушений конвенции или протоколов к ней и подтверждающих аргументов expose des faits statement of the facts
Европейский суд по правам человека принял к рассмотрению жалобу независимого журналиста Сергея Кузнецова
Изложение метода 18 iconМетоды исследования профпсихологии
Для ис­следования этого процесса оправданно применение лонгитюдного метода, опросных методов (анкетирова­ния, интервью), психобиографии,...
Изложение метода 18 icon6С 1s22s22p2 s p
Задача №19: Описать электронное строение молекул co и cn с помощью метода валентных связей (ВС) и метода молекулярных орбиталей....
Изложение метода 18 iconОшибки выборки Типовые задачи, решаемые на основе выборочного метода. Использование выборочного метода в зоотехнии
Типовые задачи, решаемые на основе выборочного метода. Использование выборочного метода в зоотехнии
Изложение метода 18 iconИзложение по этому тексту. Задачи
Цель: Показать комплексную работу с текстом, итогом которой будет сжатое изложение по этому тексту
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами