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

Сентябрь 3, 2022

Главная
Алгебра
Линейный поиск

Содержание

2. Линейный поиск Методика линейного поиска Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия останова итеративного процесса.
3. Однако простейшая процедура, заключающаяся в выборе достаточно большого начального значения , которое затем уменьшается (делением пополам)
4. Это требование обеспечивает некую усредненную скорость спуска на очередной итерации не меньше определенной доли от величины,
5. Свойство. Предположим, что для всех . Тогда существует интервал такой, что в методе спуска условия (*)
6. Линейный поиск
7. http://www.hbmeyer.de/backtrack/backtren.htm Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой требуется полный
8. Методы оптимизации Методы спуска минимизации квадратичных функций Для методов спуска особый интерес представляют такие функции, для
9. Методы спуска для квадратичных функций В частности, при заданном направлении спуска можно определить оптимальную величину шага
10. Методы спуска для квадратичных функций Отклонение от точного решения на -м шаге процесса минимизации можно вычислить
11. Методы спуска для квадратичных функций С другой стороны, поэтому из предыдущей формулы следует, что Обозначим ,
12. Метод наискорейшего спуска Поскольку матрица A симметрична и положительно определена, то всегда положительна. Более того, можно
13. Лемма. (Неравенство Канторовича) Пусть - симметричная положительно определенная матрица с наибольшим и наименьшим по модулю значениями
14. Соответствующие методы обладают следующим хорошим свойством: Свойство. Метод вычисления точки минимума квадратичной функции, основанный на вычислении
15. Метод сопряженных направлений A-сопряженные направления можно вычислять в соответствии со следующей процедурой. Для начального приближения положим
16. Скорость сходимости метода может быть повышена лишь за счет проведения предобуславливания матрицы с целью уменьшения числа
17. Метод сопряженных направлений Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная
18. Метод сопряженных градиентов The algorithm is detailed for solving Ax = b where A is a
19. The gradient method
20. The gradient method
21. The gradient method Alfio Quarteroni, Riccardo Sacco, Fausto Saleri Numerical Mathematics
22. Функция Розенброка
24. Скачать презентацию

Слайд 2

Линейный поиск
Методика линейного поиска
Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия

останова итеративного процесса. При этом предполагается, что условия, определяющие направление спуска,
выполнены.

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

Слайд 3

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

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

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

Слайд 4

Это требование обеспечивает некую усредненную скорость спуска на очередной итерации не

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

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

Слайд 5

Свойство. Предположим, что для всех . Тогда существует интервал такой, что

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

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

Слайд 6

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

Слайд 7

http://www.hbmeyer.de/backtrack/backtren.htm
Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой

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

Линейный поиск с возвратом

Слайд 8

Методы оптимизации
Методы спуска минимизации квадратичных функций
Для методов спуска особый интерес представляют

такие функции, для
которых параметр шага может быть вычислен точно. Например,
квадратичные функции
где симметричная и положительно определенная матрица и
В этом случае необходимое условие того, что точка минимума функции f(x),
это то, что является решением системы .
В самом деле, легко проверить, что
Как следствие, все итеративные методы решения систем линейных
алгебраических уравнений могут успешно применяться при решении задач
минимизации.

Слайд 9

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

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

Слайд 10

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

процесса минимизации
можно вычислить по формуле:

Слайд 11

Методы спуска для квадратичных функций
С другой стороны,
поэтому из предыдущей формулы следует,

что
Обозначим , где

Слайд 12

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

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

Слайд 13

Лемма. (Неравенство Канторовича) Пусть - симметричная положительно определенная матрица с наибольшим

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

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

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

Слайд 14

Соответствующие методы обладают следующим хорошим свойством:
Свойство. Метод вычисления точки минимума квадратичной

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

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

Слайд 15

Метод сопряженных направлений
A-сопряженные направления можно вычислять в соответствии со следующей процедурой.

Для начального приближения положим и формулы метода сопряженных градиентов записываются в виде:

Зная число обусловленности матрицы можно оценить скорость сходимости метода:

Слайд 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.

Example code in GNU Octave

function [x] = conjgrad(A,b,x)
r=b-A*x;
p=r;
rsold=r'*r;
for i=1:size(A)(1)
Ap=A*p;
alpha=rsold/(p'*Ap);
x=x+alpha*p;
r=r-alpha*Ap;
rsnew=r'*r;
if sqrt(rsnew)<1e-10 break;
end
p=r+rsnew/rsold*p;
rsold=rsnew;
end
end

Слайд 19

The gradient method

Слайд 20

The gradient method

Слайд 21

The gradient method
Alfio Quarteroni, Riccardo Sacco, Fausto Saleri
Numerical Mathematics

Слайд 22

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

Содержание

Линейный поискМетодика линейного поискаРассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия

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

Это требование обеспечивает некую усредненную скорость спуска на очередной итерации не

Свойство. Предположим, что для всех . Тогда существует интервал такой, что

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

http://www.hbmeyer.de/backtrack/backtren.htmПоиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой

Методы оптимизацииМетоды спуска минимизации квадратичных функцийДля методов спуска особый интерес представляют

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

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

Методы спуска для квадратичных функцийС другой стороны,поэтому из предыдущей формулы следует,

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

Лемма. (Неравенство Канторовича) Пусть - симметричная положительно определенная матрица с наибольшим

Соответствующие методы обладают следующим хорошим свойством:Свойство. Метод вычисления точки минимума квадратичной

Метод сопряженных направленийA-сопряженные направления можно вычислять в соответствии со следующей процедурой.

Скорость сходимости метода может быть повышена лишь за счет проведения предобуславливания

Метод сопряженных направленийИллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и

Метод сопряженных градиентовThe algorithm is detailed for solving Ax = b

The gradient method

The gradient method

The gradient methodAlfio Quarteroni, Riccardo Sacco, Fausto SaleriNumerical Mathematics

Функция Розенброка

Похожие презентации

Линейный поиск
Методика линейного поиска
Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия

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

http://www.hbmeyer.de/backtrack/backtren.htm
Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой

Методы оптимизации
Методы спуска минимизации квадратичных функций
Для методов спуска особый интерес представляют

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

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

Методы спуска для квадратичных функций
С другой стороны,
поэтому из предыдущей формулы следует,

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

Соответствующие методы обладают следующим хорошим свойством:
Свойство. Метод вычисления точки минимума квадратичной

Метод сопряженных направлений
A-сопряженные направления можно вычислять в соответствии со следующей процедурой.

Скорость сходимости метода может быть повышена лишь за счет проведения
предобуславливания

Метод сопряженных направлений
Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и

Метод сопряженных градиентов
The algorithm is detailed for solving Ax = b

The gradient method
Alfio Quarteroni, Riccardo Sacco, Fausto Saleri
Numerical Mathematics