Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации

И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации, страница 19

DJVU-файл И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации, страница 19 Алгоритмы оптимизации основанные на методе проб и ошибок (2638): Книга - 5 семестрИ.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации: Алгоритмы оптимизации основанные на методе проб и о2019-05-09СтудИзба

Описание файла

DJVU-файл из архива "И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации", который расположен в категории "". Всё это находится в предмете "алгоритмы оптимизации основанные на методе проб и ошибок" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 19 - страница

Основной цикл. П1. Вычислить Ч1» (х»). 1Ч. Если Ч1» (х») = О, то положить х' = х» и прекратить вычисления; иначе перейти к шагу Ч. Ч. Найти е из условия е = гп!п [ео> ~[Ч1» (х») ~[). Ч1. Найти матрицу Н, (з) размера а х а, /-й столбец которой вычисляется по формуле о (Ч1»(Х + е/) — Ч1о(х»», 1=1, 2, ..., и, где е/ — /-й орт. ЧП.

Если существует обратная матрица Н» ' (е) и выполняется неравенство (Ч1» (х»), Н» (е) Ч1» (х»» ) О, то вычислить вектор й~(е) = — Н» ' (е) 71»(х») н перейти к шагу ЧП1; иначе положить е = з/2 и перейти к шагу Ч1. (Шаги ЧП! — ХЧП1 предназначены для вычисления такого р, что р(! — а)(Ч/о( ), а»(»<1»( '+ рй»(з»вЂ” — 1.( ')<р (Ч1.(х»). Ь»(а».

ЧП1. Определить функции 0»(Л) =1,(х»+ Л/»»(е)) — 1,(х") — Л(1 — я)(71»(х ), й»(е»; ф»(Л) =1»("+Лй»(з»-1»(х»)-Р" (Ч1»( ), 6'(з». 1Х. Положить р = р. Х. Вычислить О» (р). Х1. Если 0» (р,) = О, то положить р = р и перейти к шагу Х1Х; если О» (р) < О, то положить р = р + р и перейти к шагу Х; если О» (р) ) О, то перейти к шагу ХП.

ХП. Вычислить ф» (р). ХП1. Если ф» (р) < О, то положить р = р и перейти к шагу Х1Х; иначе положить ао — — р — р, Ь, = р и перейти к шагу Х1Ч; Х1Ч. Положить 1 = О. ХЧ. Вычислить значение о, = (а, + Ь;)/2. ХЧ1. Вычислить О» (о,), ф» (о,). ХЧП. Если О, (и,) !о 0 и ф» (ио) < О, то положить р = о, и перейти к шагу Х1Х; иначе перейти к шагу ХЧП1. ХЧП1. Если О» (о,) ) О, то положить а, ы = ао Ь,+~ = о„ ! = 1+ 1 и перейти к шагу ХЧ; иначе положить а~+~ = п„Ь»ы = *= Ь„( = 1+ 1 и перейти к шагу ХЧ. Х!Х. Если выполняется неравенство 1 ( '+ рй" ('» — 1. (») < — 1' вб то перейти к шагу ХХ; иначе положить е = е/2 и перейти к шагу т71. ХХ.

Вычислить следующее приближение ха-ь' = х" + рй" (е). ХХ[. Положить й = й + 1 и перейти к шагу 1П. Теорема 4. Если выполнены условия: (з) — функция [е дважды непрерывно дифференцируема и ее матрица Гессе невырождена при всех х из достаточно большой области; (В) — функция 7е строго выпукла; (И) — начальное приближение х' в алгоритме 4 таково, что множество Х, = (х([е (х) (~е(хе), х Е В") ограничено,.то бесконечная последовательность (ха)ь" е, порожденная алгоритмом 4, сходится к точке минимума х* функции 7е.

В работе [2881 утверждается, что алгоритм 4 имеет сверхлинейную сходимость. Библиографические уаиаиия. Параграф основан на работах [285, 320, 4861. Методы Ньютона решения задач безусловной оптимизации изучались также [186, 16, 49, 413, 423, 200, 105, 106, 278, 62, 498, 390[. В работах 1469, 544[ изучается метод Ньютона для вырожденных случаев.

В работах [537, 538[ нриводятся модели обобщенных алгоритмов и на их основании устанавливается глобальная сходимость модификаций метода Ньютона. 2.3. Методы двойственнык направлений 3 а д а ч а О. Найти агн ппп 7е (х) для заданной непрерывно ксяи дифференцируемой функции 7з 1 В" — В'. Методы двойственных направлений, обладая сверхлииейной скоростью сходимости, требуют, по сравнению с методами типа Ньютона — Канторовича, значительно меньшего количества вычислений (примерио в и раз),.при этом нет необходимости вычислять втоРые пРоизвоДные фУнкции 7е. С помощью лишь пеРвых пРоизводных так организуется процесс вычислений, что направление поиска приближается к направлению метода Ньютона — Канторовича.

1. Основной вариант А лгоритм л Н а ч а л о. 1. Выбрать: произвольное начальное приближение х'с В"; произвольную линейно-независимую систему и-мерных векторов рце, рц — ', ..., ре — ы-'1 (в частности, можно взять столбцы единичной матрицы 1 размера п Х п); константы у 0 (рекомендуется выбирать у Е [10 ', 10 1), [) Е (0,1) (рекомендуется выбивать Р = 0,8), е Е (О, т[з). 11. Положить Ф = О, р = 1, га = р". О с н о в н о й ц и к л. П[. Вычислить Р)е (ха), 87 1Ч. Если 710 (х") = О, то положить х' = хй н прекратить вычисления; иначе перейти к шагу Ч. Ч. Положить рй = р.

Ч1. Вычислить точку х = х" — рй Ч10 (х'). Ч!1. Если выполняется неравенство !0(х) !0(хй) (~ — ерй (0!0(хй) Ч10 (хй)) то перейти к шагу Ч1П; иначе положить р, = рйр н перейти к шагу Ч1. ЧШ. Положить хй+' = х и перейти к шагу 1Х. 1Х. Вычислить векторы !й-!-1 хй+1 хй. ай+ =%70(х+ ) — Ч10(х ). Х. Если выполняется неравенство (Рй,й — 0 — и ай+1) ~ У1Рй,й — 0з — и), !!00+!!! то перейти к шагу ХЧ; иначе положить б = 1 и перейти к шагу Х1. Х1. Вычислить вектор г'+' = бр" ' — !"-'!. Х11. Если ) гй+' ) (( гй ), то перейти к шагу Х111; иначе положить б = бр н перейти к шагу Х1.

ХП1. Вычислить Ч)'0 (хй + гй+'). Х!Ч. Вычислить вектор ей+! Ч): (хй+ !.й+!) Ч! (хй) ХЧ. Вычислить вектор рй+1.й+! (рй,й-<0-1! б!й+1) й,й — !»-!! ХЧ1. Положить! = О. ХЧП. Вычислить вектор рй!.1 й ! рй й ! (рй,й ! ай+1) рй ! ! й-!-1 ХЧ[П. Если 1( а — 2, то положить / = 1+ 1 и перейти к шагу ХЧ11; иначе перейти к шагу Х1Х.

Х1Х. Если й ( и — 1, то положить й = й + 1 и перейти к шагу Ш; иначе перейти к шагу ХХ, ХХ. Вычислить 7)0 (хй+'). ХХ1. Если Ч)'0 (хй-1!) = О, то положить х* = х"+' и прекратить вычисления; иначе перейти к шагу ХХ11. ХХ11. Вычислить вектор 0-1 /10+1 ~ (Чй (хй+1) рй+1,0+! 1) гй+1 ! ХХ1П. Если Я0 (хй+'), й"+') ( О, то положить рй+! = р и перейти к шагу ХХ1Ч; иначе перейти к шагу ХХЧ1.

ХХ1Ч. Вычислить точку х = хй+' + рй-! !)10+1. ХХЧ. Если выполняется неравенство Ь (х) — 10( "+')(ар+ (ч)0(х"+') л'!!). 88 то положить х»+о = х и перейти к шагу ХХХ1; иначе положить Р»-»~ = рр»„»с и перейти к шагу ХХ1Ч. ХХЧ1 Ес:ли (й~о (х'+'), 6»ы) ) О, то положить р,„, = р и перейти к шагу ХХЧИ; иначе положить р».ьс = р и перейти к шагу ХХ1Х.

ХХЧ!1 Вычислить точку х = х»+' — р»+сй»-~'. ХХЧ11!. Если выполняется неравенство 1о (х) — 1» (х"+') ( — ер»+ (Чо (х'+'), й'+'), то положить х»+' = х и перейти к шагу ХХХ1; иначе положить р»-»с = ~р»~-с и перейти к шагу ХХЧП. ХХ1Х. Вычислить точиУ х = х"+' — Р»+с»>1» (х»+с). ХХХ. Если выполняется неравенство 1» (х) — с о (х»+') ( ер»+с ) Чс'о (х»+') с(», то положить х'+» = х н перейти к шагу ХХХ1; иначе положить р»»с = рр»+с и перейти к шагу ХХ1Х. ХХХ1. Положить й = Ф + 1 и перейти к шагу 1Х.

Теорема». Если функция 1о дважды непрерывно дифференциру- ема и ее матрица вторых производных удовлетворяет условию У,!У(о((Ч~Д(х)У, У)(У»(У((», У»~У,)О при любых х, у Е 11", то бесконеч я последовательность (х»)» о, порожденная алгоритмом 1, сходится к решению х* задачи О со сверхлинейной скоростью (х"+с — х*!(а)»лХн+с ... Хм+с, где а, >Ч ( оо; Ъ.к+с ( 1 при любом 1 ~ О; )с., -~ О при с' -» оо, пРичем ~о (х»~-с) ( ~о (х»)с й = О, 1, ....

Для реализации методов двойственных направлений на ЭВМ требуется хранить в памяти'две системы векторов: г", г' — '...,, 㻠— '"-" и р»", р" » — ', ... р" » — с"-и Р' т. е. фактически две матрицы размера и х и. Частично этот недостаток устраняется, если в качестве векторов г» исполь- зовать векторы, направленные по координатным осям, так как в этом случае в памяти машины необходимо хранить лишь один и-мерный вектор вместо системы г», ..., г'-с" — 'с.

2. Модифицированный метод двойетвениых ваправлеввй, ие требуюшвй вычислении прововодвых Алгоритм 2 Н а ч а л о. !. Выбрать: произвольное начальное приближение х' ~ И"; произвольную систему и-мерных линейно независимых векторов р", р' — ', ..., ро — с"-'> (в частности, можно взять столбцы единичной матрицы ! размера и х и); константы уо ) О, а, Е (О. !), е р (О, >1»), б ) О, 1) 1; последовательность ($»)»" о, стремя- щуюся к нулю достаточно медленно (в частности, можно выбрать ~„= 1((й+ 1), й = О, 1, ...).

П. Положить й = О и перейти к шагу Х!Ч. 0 с н о в н о й ц и к л. П1. Вычислить вектор г», используя для этого алгоритм 2А, или по формуле г» = х» — х" — ', 1Ч. Вычислить вектор у» = х» + г". Ч. Вычислить р = ~! г» '1!. Ч1. Вычислить и-мерные векторы О», »р», »р», /-е компоненты которых О!=А(х»+Ре') — Ьо(х»))(1», (=1, ..., и; % = (1»(У + ре») 1»(У )И» ! 1ю ° ° ° и' »Р!. = »а!. — О», 1 = 1, ..., и, где е' — )сй орт. ЧП. Положить ф' = »р», ЧП1.

Вычислить скалярное произведение (р»-" †", »р»). 1Х. Если (р' '» — ", »р») = О, то положить р = )»/2 и перейти к шагу Ч1; иначе перейти к шагу Х. Х. Вычислить вектор р»,» (1!(р»-Ъ,»-о,г!,»)) р» — 1,» — о Х1. Положить ! = О. ХИ. Вычислить вектор р»,» — »-! р» — !,» — ! — ! (р» — !, » — ! — !»)!») р»,» Х1И.

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