Линейный поиск - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Линейный поиск. Доклад-сообщение содержит 23 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ Константин Ловецкий Октябрь 2012

Слайд 2

Описание слайда:

Линейный поиск

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п. Термин backtrack был введен в 1950 году американским математиком Дерриком Генри Лемером. Незначительные модификации метода поиска с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ, поиск в глубину, метод проб и ошибок и т. д. Поиск с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания.

Слайд 8

Описание слайда:

Методы оптимизации

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

Метод наискорейшего спуска Поскольку матрица A симметрична и положительно определена, то всегда положительна. Более того, можно проверить непосредственно, что ; и лишь когда вектор ортогонален , тогда . Выбор направления спуска в виде приводит к методу наискорейшего спуска. В этом случае справедливо неравенство Отсюда следует Неравенство Канторовича

Слайд 13

Описание слайда:

Методы спуска

Слайд 14

Описание слайда:

Соответствующие методы обладают следующим хорошим свойством: Соответствующие методы обладают следующим хорошим свойством: Свойство. Метод вычисления точки минимума квадратичной функции, основанный на вычислении A-сопряженных направлений спуска, достигает результата после самое большое n итераций, если параметр вычисляется по формуле Более того, для любого k, x (k+1) является точкой минимума на подпространстве, натянутом на векторы и

Слайд 15

Описание слайда:

Метод сопряженных направлений

Слайд 16

Описание слайда:

Скорость сходимости метода может быть повышена лишь за счет проведения Скорость сходимости метода может быть повышена лишь за счет проведения предобуславливания матрицы с целью уменьшения числа обусловленности. Замечание. Случай не квадратичных функций. Метод сопряженных направлений может быть распространен и на случай не квадратичных функций. Однако в этом случае оптимальное значение параметра не может быть определено аналитически и для его отыскания придется решать одномерную оптимизационную задачу. Мало того, параметры могут определяться не единственным образом. Наиболее надежны два варианта выбора : Флетчера-Ривса (Fletcher-Reeves): Полака-Рибиера (Polak-Ribiere):

Слайд 17

Описание слайда:

Метод сопряженных направлений

Слайд 18

Описание слайда:

Метод сопряженных градиентов The algorithm is detailed for solving Ax = b where A is a real, symmetric, positive-definite matrix. The input vector x0 can be an approximate initial solution or 0.