lopt5 (1013497)

Файл №1013497 lopt5 (Лекционный курс)lopt5 (1013497)2017-06-17СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 5МЕТОДЫ ПЕРВОГО ПОРЯДКАПостановка задачиПусть дана функция f ( x) , ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех его точках.Требуется найти локальный минимум функции f ( x) на множестве допустимыхрешений X = R n , т.е. найти такую точку x ∗ ∈ R n , чтоf ( x ∗ ) = minn f ( x) .x∈ RА. МЕТОД ГРАДИЕНТНОГО СПУСКА С ПОСТОЯННЫМ ШАГОМСтратегия поиска{ }) < f (x ) , k = 0,1,… . Точки последовательности { x } вы-Стратегия решения задачи состоит в построении последовательности точек x k ,(k = 0,1,… , таких, что f x k +1kkчисляются по правилу( )x k +1 = x k − t k ∇f x k , k = 0,1,… ,( )где точка x 0 задается пользователем; ∇f x k – градиент функции f ( x ) , вычисленный вточке x k ; величина шага t k задается пользователем и остается постоянной до тех пор,пока функция убывает в точках последовательности, что контролируется путем проверки() ( )() ( )( )выполнения условия f x k +1 − f x k < 0 или f x k +1 − f x k < − ε ∇f x kПостроение последовательности( )∇f x k{x }k2,0 < ε < 1 .заканчивается в точке x k , для которой< ε1 , где ε1 – заданное малое положительное число, или k ≥ M , где M – пре-дельное число итераций, или при двукратном одновременном выполнении двух нера-() ( )венств x k +1 − x k < ε 2 , f x k +1 − f x k< ε 2 , где ε 2 – малое положительное число.Вопрос о том, может ли точка x k рассматриваться как найденное приближение искомой точки минимума, решается с помощью дополнительного исследования.Геометрическая интерпретация метода для n = 2 приведена на рис.

1.43x2C1 > C 2 > C 3f ( x ) = C1x0− ∇f ( x 0 )x1x∗x2f (x ) = C3f (x ) = C 20x1Рис. 1З а м е ч а н и я.1. Методы первого порядка при определенных условиях гарантируют сходимость{ } к стационарной точке x , где ∇f (x ) = 0 . Следовательно, най∗последовательности x k∗денная в результате применения метода точка x ∗ нуждается в дополнительном исследовании с целью ее классификации.2. Условия окончания процесса поиска для большинства методов первого и второго порядков одни и те же (совпадают с применяемыми в методе А).Б. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКАСтратегия поиска{ }) < f (x ) , k = 0,1,… . Точки последовательности { x } вы-Стратегия решения задачи состоит в построении последовательности точек x k ,(k = 0,1,… , таких, что f x k +1kkчисляются по правилу( )x k + 1 = x k − t k ∇f x k ,где точка x 0 задается пользователем; величина шага t k определяется для каждого значения k из условия(.( )) → mintϕ(t k ) = f x k − t k ∇f x kkЭта задача может решаться с использованием необходимого условия минимумаdϕd 2ϕ= 0 и последующей проверкой достаточного условия минимума> 0 .

Другой2dt kdt k44путьсвязанmin ϕ ( t k ) =t k ∈ ⎡⎣ a, b ⎤⎦ции.сиспользованиемmint k ∈ ⎡⎣ a, b ⎤⎦(( ))kf x − t k ∇f xkчисленныхметодов,когдаищетсяс помощью методом одномерной минимиза-Геометрическая интерпретация метода для n = 2 приведена на рис. 2.C1 > C 2x2f ( x ) = C1x0− ∇f ( x 0 )x1f (x ) = C 2x1Рис. 2В.

МЕТОД ПОКООРДИНАТНОГО СПУСКАСтратегия поиска{ }) < f (x ) , k = 0,1,…. Точки последовательности { x } вы-Стратегия решения задачи состоит в построении последовательности точек x k ,(k = 0,1,…, таких, что f x k +1kkчисляются по циклам в соответствии с правилом⎛ ∂ f (x ) ⎞⎟x jk +1 = x jk − t k ⎜⎜⋅ e k +1 ,⎟x∂jk+1k⎠x =x⎝где j – номер цикла вычислений; j = 0,1, 2,… ; k – номер итерации внутри цикла,k = 0,1, … , n − 1 ; ek +1 , k = 0,1, … , n − 1 – единичный вектор, (k + 1) -я проекция которогоравна 1; точка x 00 задается пользователем; величина шага t k выбирается из условия⎛⎞2⎛ ∂ f (x ) ⎞⎟ − f x jk < 0 или f x jk +1 − f x jk < − ε ∇f x jk⎟f ⎜ x jk − t k ⎜⎜⋅e.k+1⎟⎜⎟⎝ ∂ x k +1 ⎠ x = x jk⎝⎠Если выбранное условие при текущем t k не выполняется, шаг уменьшается вдвое⎛ ∂ f (x ) ⎞⎟⋅ e k +1 вычисляется заново.

Легко видеть, что при фиксирои точка x jk − t k ⎜⎜⎟⎝ ∂ x k +1 ⎠ x = x jk( )() ( )( )ванном j за одну итерацию с номером k изменяется только одна проекция точки x jk ,45имеющая номер k + 1 , а в течение всего цикла с номером j , т.е. начиная с k = 0 и кончая k = n − 1 , изменяются все n проекций точки x j 0 . После этого точке x jn присваивается номер x j +1, 0 и она берется за начальную точку для вычислений в ( j + 1) -м цикле.Полученные в результате вычислений точки могут быть записаны как элементыпоследовательности{x l },l = n⋅ j +kгде–порядковый{x l } = {x 0 = x 00 , x1 = x 01,..., x n = x 0n = x10 , x n+1 = x11, x n+2 = x12 ,...} .номерточки,т.е.Геометрическая интерпретация метода для n = 2 приведена на рис. 3.x2f (x ) = C 2C1 > C 2xx 0001− ∇f ( x 00 )x 02x∗f ( x ) = C1x1Рис.

3Г. МЕТОД ГАУССА–ЗЕЙДЕЛЯСтратегия поискаСтратегия метода Гаусса–Зейделя (Gauss–Seidel) состоит в построении последова-({ }довательности { x } вычисляются по правилу) ( )тельности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … . Точки послеk⎛ ∂ f (x ) ⎞⎟x jk +1 = x jk − t k ⎜⎜⋅ e k +1 ,⎟x∂jk⎝ k +1 ⎠ x = xгде j – номер цикла вычислений, j = 0,1, 2, … ; k – номер итерации внутри цикла,k = 0,1, … , n − 1 ; ek +1 – единичный вектор, (k + 1) -я проекция которого равна 1; точкаx 00 задается пользователем, величина шага t k выбирается из условия⎛⎞⎛ ∂ f (x ) ⎞⎟⎟⋅eϕ(t k ) = f ⎜ x jk − t k ⎜⎜k +1 ⎟ → min .⎟⎜tkx∂jk⎝ k +1 ⎠ x = x⎝⎠46Данная задачаявляется задачей одномерной минимизации функции⎛⎞⎛ ∂ f (x ) ⎞⎟ и может быть решена либо с использованием ус⎟e⋅ϕ(t k ) = f ⎜ x jk − t k ⎜⎜k+1⎟⎜⎟x∂jkk+1⎠x =x⎝⎝⎠2d ϕdϕ= 0,> 0 , либо численно с использованием методов одномерной минимиловийdt kdt k 2зации, как задача ϕ ( t k ) →mint k ∈ ⎡⎣ a, b ⎤⎦.При фиксированном j за одну итерацию с номером kизменяется только однаjkпроекция точки x , имеющая номер k + 1 , а в течение всего цикла с номером j , т.е.

начиная с k = 0 и кончая k = n − 1 , изменяются все n проекций точки x j 0 . После этоготочке x jn присваивается номер x j +1,0 и она берется за начальную точку для вычисленийв ( j + 1) -м цикле.Полученные в результате вычислений точки могут быть записаны как элементыпоследовательности{ xl} ,l = n⋅ j +kгде–порядковыйномерточки,т.е.{x l } = {x 0 = x 00 , x1 = x 01,..., x n = x 0n = x10 , x n +1 = x11, x n + 2 = x12 ,...} .Геометрическая интерпретация метода для n = 2 приведена на рис.

4.f ( x ) = C1x2C1 > C 2x 01x 00x 02f ( x) = C 2x1Рис. 4Д. МЕТОД ФЛЕТЧЕРА–РИВСАСтратегия поискаСтратегия метода Флетчера–Ривса (Fletcher–Reeves) состоит в построении после-({ }последовательности { x } вычисляются по правилу:) ( )довательности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … . Точкиk47x k +1 = x k + t k d k , k = 0,1,… ;( )( )∇f (x ))∇f (xd 0 = −∇f x 0 ; d k = − ∇f x k + β k −1 d k −1 , k ≥ 1 ;2kβ k −1 =k −12.Точка x 0 задается пользователем, величина шага t k определяется для каждого()значения k из условия ϕ(t k ) = f x k + t k d k → min .tkРешение задачи одномерной минимизации может осуществляться либо из условияd 2ϕdϕ= 0,> 0 , либо численно с использованием методов одномерной минимизации,d tkdt k 2когда решается задача ϕ ( t k ) →.mint k ∈ ⎡⎣ a, b ⎤⎦Для квадратичных функций f ( x ) с матрицей Гессе H > 0 метод Флетчера–Ривсасходится к точке минимума за число шагов, не превышающее n – размерность вектора x .Для неквадратичных функций, как правило, используется алгоритм Полака–Рибьера (Polak–Ribiere), когда величина β k −1 вычисляется следующим образом:β k −1( ( )[ ( ) (( )⎧ ∇ f x k , ∇ f x k − ∇f x k − 1⎪⎪2=⎨∇f x k −1⎪⎪⎩ 0, k ∈ J ,) ] ),k ∉ J,где J = {0, n, 2n, …} .

В отличие от алгоритма Флетчера–Ривса алгоритм Полака–Рибьерапредусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов. Геометрическая интерпретация метода для n = 2 изображена на рис. 5.x2x00f ( x) = C10d = −∇f ( x )− ∇f ( x 1 )x1β0ddC1 > C 2f ( x) = C 210x∗0x1Рис. 548МЕТОДЫ ВТОРОГО ПОРЯДКАА. МЕТОД НЬЮТОНАСтратегия поискаСтратегия метода Ньютона (Newton) состоит в построении последовательности то-{ }()( )чек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … .

Точки последовательностивычисляются по правилу( ) ( )x k +1 = x k − H −1 x k ∇f x k , k = 0, 1,… ,где x 0 – задается пользователем, а направление спуска d k определяется для каждого( ) ( )значения k по формуле d k = − H −1 x k ∇f x k , величина шага t k = 1 .З а м е ч а н и е. Для квадратичных функций при определенных условиях [1,2] метод сходится к стационарной точке за одну итерацию.Б. МЕТОД НЬЮТОНА–РАФСОНАСтратегия поискаСтратегия метода Ньютона–Рафсона (Newton–Raphson) состоит в построении по-{ }() ( )следовательности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … . Точкипоследовательности вычисляются по правилу( ) ( )x k +1 = x k − t k H −1 x k ∇f x k , k = 0,1, … ,где x 0 задается пользователем, а величина шага t k определяется из условия(( ) ( )) → min .ϕ(t k ) = f x k − t k H −1 x k ∇f x ktkЭта задача может решаться либо аналитически с использованием необходимогоd 2ϕdϕусловия минимума= 0 и последующей проверкой достаточного условия> 0,dt kd tk 2либо численно как задача ϕ ( t k ) →mint k ∈ ⎡⎣ a, b ⎤⎦, где интервал [a , b ] задается пользователем.49З а м е ч а н и е.

Характеристики

Тип файла
PDF-файл
Размер
307,49 Kb
Тип материала
Высшее учебное заведение

Тип файла PDF

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

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

Список файлов лекций

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6390
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее