Главная » Просмотр файлов » Теормин (extended) (2003)

Теормин (extended) (2003) (1125525), страница 3

Файл №1125525 Теормин (extended) (2003) (Теормин (extended) (2003)) 3 страницаТеормин (extended) (2003) (1125525) страница 32019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

. .(2)При этом необходимо учитывать, что на каждом шаге приближения все точки uk должныпринадлежать U. Для простоты будем считать, чтоαk = α ≡ const(3)Теорема 14. Пусть U ⊂ H — выпуклое, замкнутое множество, J(u) ∈ C1 (U) исильно выпукла с коэффициентом κ > 0, J 0 (u) ∈ Lip(U) с константой L > 0. Пустьтакже α ∈ 0, L2κ2 . Тогда для любого начального приближения u0 ∈ U метод (2), (3)сходится:√kuk − u∗ kH 6 ku0 − u∗ kH ·q k (α), где 0 < q(α) = 1 − 2κα + α2 L2 < 1.(4)11Метод условного градиентаВ этом пункте рассматривается задача минимизации следующего вида:J(u) → inf, u ∈ U ⊂ H.(1)Идея метода условного градиента основана на том, что в окрестности точки uk функционал J(u) можно приближенно представить какJ(u) ' J(uk ) + hJ 0 (uk ), u − uk i .Так как J(uk ) близко к J(u), то мы стараемся минимизировать скалярное произведение Jk (u) = hJ 0 (uk ), u − uk i .

Введём обозначениеuk = argmin Jk (u).(2)u∈UТогда итерационная последовательность рассматриваемого метода описывается как(3)uk+1 = uk + αk (uk − uk ),гдеαk = argmin J (uk + α (uk − uk ))(4)06α61Лемма 1 (оценка скорости сходимости числовой последовательности).Пусть для монотонной числовой последовательности {ak }∞k=0 :a0 > a1 > . . .

> an > . . . > 0выполняется условиеak − ak+1 > C·a2kk = 0, 1, 2, . . .a0m = 0, 1, 2, . . .(∗).1 + a0 CmТеорема 15. Пусть U ⊂ H — выпуклое, замкнутое, ограниченное множество,J(u) ∈ C1 (U) и выпукла, J 0 (u) ∈ Lip(U) с константой L > 0, D = diamU. Тогда 1J(u0 ) − J∗=OJ(uk ) − J∗ 6(5).J(u0 )−J∗kk1+Тогда верна оценка:am 62LDЕсли J(u) сильно выпукла, то, кроме этого, выполнено условиеκkuk − u∗ k2H 6 J(uk ) − J∗ .2Метод НьютонаРассматриваем задачу минимизации функции J(u):J(u) → inf, u ∈ U ⊆ H(1)Идея метода Ньютона похожа на метод условного градиента, но здесь мы будем использовать не линейную, а квадратичную аппроксимацию функции J(u) в окрестноститочки uk :1 000J(u) ' J(uk ) + hJ (uk ), u − uk i + hJ (uk )(u − uk ), u − uk i .2Обозначим выражение в квадратных скобках через Jk (u) (квадратично по u).На каждом шаге процесса находится минимумuk = argmin Jk (u).(2)u∈UИ вычисляется следующее приближение по формулам (в общем случае):uk+1 = uk + αk (uk − uk ),αk = argmin J(uk + α(uk − uk )).06α6112Но мы будем рассматривать метод в более простом варианте, когда αk не минимизируются и принимаются равными 1.

В этом случае uk+1 = uk . Это “классический” методНьютона.Теорема 16. Пусть U ⊂ H — выпуклое, замкнутое множество, причём int U 6= ∅,J(u) ∈ C2 (U) и сильно выпукла с коэффициентом κ > 0, J 00 (u) ∈ Lip(U) с константойLku1 − u0 kH < 1, то метод (2) сходится к u∗ и верна следующаяL > 0. Тогда если q = 2κоценка скорости сходимости:−12κ 2k 2k,1−q·qkuk − u∗ kH 6Lk = 0, 1, 2, . . .(3).Метод сопряжённых направлений (градиентов)В этом пункте рассмотрим задачу минимизации для функционалов специального видав конечномерном гильбертовом пространстве:J(u) =1hAu, ui − hf, ui → inf,2u ∈ Rn = U,A∗ = A > 0.(1)Критерием оптимальности для такой задачи является условие J 0 (u∗ ) = 0, котороеэквивалентно условию Au∗ = f.Идея метода сопряжённых градиентов заключается в следующем.

Пусть {pk }n−1k=0 —базис в Rn . Тогда для любой точки u0 из Rn выполнено равенствоu∗ − u0 = α0 p0 + α1 p1 + . . . + αn−1 pn−1 .Таким образом, u∗ представимо в видеu∗ = u0 + α0 p0 + α1 p1 + . . . + αn−1 pn−1 .Тогда итерационную последовательность данного метода можно описать какu0 = u0u1 = u0 + α0 p0u2 = u0 + α0 p0 + α1 p1...(точное описание итерации будет дано ниже).Подействовав на вышеприведённое равенство оператором A, получимf − Au0 = α0 Ap0 + α1 Ap1 + . . . + αn−1 Apn−1 .Выражение f − Au0 считаем известным, и наша задача состоит в нахождении αi , атакже “правильного” выбора базиса {pk }.13Определение.

Векторы p и q называются сопряжёнными относительно матрицыR = R∗ > 0, если hRp, qi = 0. По-другому это называют ортогональностью относительноскалярного произведения hp, qiR = hRp, qi .Если {pk }n−1k=0 — базис из сопряжённых относительно A векторов, тоαk =hf − Au0 , pk i,hApk , pk ik = 0, n − 1.(α)Лемма 2. Пусть H = Rn , A = A∗ > 0, {pk }n−1k=0 — базис из сопряжённых относительноA векторов, uk = uk−1 + αk−1 pk−1 , где αk вычисляются по формулам (α). Тогдаαk = αk∗ = argmin J(uk + αpk ) = −−∞<α<+∞hJ 0 (uk ), pk iHhApk , pk iH(2)иhJ 0 (uk+1 ), pk iH = 0 ∀k = 0, n − 1(3)Опишем подробнее итерации в рассматриваемом методе. В качестве первого приближения берём любую точку из Rn , а первый вектор будущего базиса вычисляем какзначение производной функции J(u) в данной точке:∀u0 ∈ Rnp0 = −J 0 (u0 )Теперь пусть требуется вычислить k + 1-ю итерацию, когда предыдущие k уже вычислены, тогда применяем следующие формулы:uk+1 = uk + αk pk ,(4u)0pk+1 = −J (uk+1 ) + βk pk(4p)αk здесь вычисляются по формулам (α) или (2) (обозначим для однообразия формулы(2) как (4α)).

Коэффициенты же βk берутся таким образом, чтобы для pk+1 сохраняласьортогональность (сопряжённость) с pk :βk =hJ 0 (uk+1 ), Apk ihApk , pk i(4β)Теорема 17. Пусть H = Rn — гильбертово пространство, J(u) = 12 hAu, ui − hf, ui ,A∗ = A > 0. Тогда метод (4) сходится к u∗ за конечное число шагов (не превосходящее n), причём(a) hApk , pm i = 0 ∀k 6= m;(b) hJ 0 (uk ), J 0 (um )i = 0 ∀k 6= m;(c) hJ 0 (uk ), pm i = 0 ∀m = 0, 1, . .

. , k − 1.14Метод покоординатного спускаЗдесь мы будем рассматривать экстремальную задачу в конечномерном гильбертовомпространстве H = Rn :J(u) → inf, u ∈ Rn .Пусть {pk }nk=1 — базис в Rn . Положим pn+1 = p1 , pn+2 = p2 , . . . Пусть также u0 ∈ Rn —некое начальное приближение. Предположим, что уже построены k приближений uk имы находимся на k + 1-ом шаге итерации.Назовём (k + 1)-й шаг итерации удачным, еслиJ(uk − αk pk+1 ) < J(uk ),J(uk + αk pk+1 ) < J(uk ).В противном случае назовём шаг неудачным.Если шаг удачный, то обновляем uk (берём то значение, где меньше J(uk+1 )) и неменяем αk : αk+1 = αk . Если же шаг неудачный, то переходим к обработке pk+2 .Кроме того, ведётся подсчёт неудачных шагов “подряд”. Если это число становитсяравным размерности пространства, то происходит дробление α: uk+1 оставляем равнойuk , переходим к обработке вектора pk+2 , и полагаем αk+1 = λαk , где λ ∈ (0, 1) — наперёдзаданный коэффициент дробления (обычно его берут равным 1/2).Теорема 18.

Пусть функция J(u) ∈ C1 (Rn ) и выпукла, множество ЛебегаM (u0 ) = {u ∈ Rn |J(u) 6 J(u0 )} ограничено. Тогда описанный выше процесс сходится и по функции и по аргументу:J(uk ) → J∗ ;k→∞ρ(uk , U∗ ) → 0.k→∞Задачи линейного программированияВ этом пункте мы рассмотрим задачу минимизации функционала J(u) = hc, ui в гильбертовом пространстве H = Rn , где c фиксировано из Rn .Общая задача линейного программирования рассматривается на множестве(1)U = {u ∈ Rn | hai , ui = bi , hai , ui 6 bj , i = 1, m, j = 1, s}Если ввести ряд обозначений:b1a1b1a1 a2  b2  b2  a2 A= ··· , A =  ··· , b =  ··· , b =  ··· ,bmasambsто множество U можно описать в более компактной матричной форме:U = {u ∈ Rn |Au = b, Au 6 b}.Наряду с общей задачей (1) мы будем рассматривать каноническую задачу линейногопрограммирования на множествеU = {u ∈ Rn |Au = b, u > 0}.Заметим, что задача (1) сводится к задаче (2).

Действительно, положим в (1)wi = max{0, ui } > 0,vi = max{0, −ui } > 0,15y = b − Au > 0.(2)Тогда можно рассмотреть задачу (2) относительно новой переменной z:z = (y, v, w) ∈ R2n+s , z > 0J(u) = hc, ui = hc, w − vi — линейна по z (не зависит от y),а ограничения задаются равенством A(w − v) = b.Определение.

Точка v выпуклого множества U называется угловой точкой этогомножества, если из соотношения v = αx + (1 − α)y, где x, y ∈ U, α ∈ (0, 1), следует, чтоv = x = y.Теорема 19 (критерий угловой точки для канонического U). Пусть матрицаA = (A1 |A2 |· · ·|An ) (расписано по столбцам). Точка v является угловой точкой канонического множества U тогда и только тогда, когда существует набор столбцовAj1 , Aj2 , .

. . , Ajr (j1 < j2 < · · · < jr ), r = rank A, причёмAj1 vj1 + Aj2 vj2 + · · · + Ajr vjr = b,(3)/ Jb = {j1 , j2 , . . . , jr } vj = 0.где vji > 0 (i = 1, r), а ∀j ∈Определение. Угловая точка v канонического множества U называется невырожденной, если существует такой набор Jb , что vj > 0 для всех j ∈ Jb . Эти координаты (j)называются базисными для точки v:B = (Aj1 |Aj2 | . . . |Ajr ) — базис v.Определение. Если у множества U все угловые точки невырожденные, то задачаминимизации (2) называется невырожденной.Симплекс-методЗдесь мы применим аппарат угловых точек для рассмотрения оптимизационной задачиследующего вида:J(u) = hc, ui → infu ∈ U = {u > 0, Au = b}(1)Идея метода лежит в переборе лишь только угловых точек множества U.

Часто этопозволяет найти оптимальное решение быстрее рассмотренных выше методов. Перейдемк описанию симплекс-метода.Пусть имеется угловая точка v множества U (каким образом она находится, намсейчас не важно). Будем считать также, что из матрицы A выкинуты все линейно зависимые строки (в системе нет линейно зависимых уравнений), то есть r = rank A = m.Находясь в условиях Теоремы 19, можно записать, что vb = (vj1 , . . . , vjr ) — базисныедля v, vjr > 0, а остальные vj равны нулю.

Обозначим через Jb множество {j1 , . . . , jr },а через Jf — множество {1, . . . , n}\Jb . Пусть далее для соответствующих Aji матрицаB = (Aj1 |Aj2 |· · ·|Ajr ), а остальные столбцы матрицы A образую некую матрицу Fr×(n−r) .По определению B и Теореме 19 det B 6= 0, и существует обратная матрица B −1 .Разобьём вектор u = (u1 , . . . , un ) на базисные переменные ub = (uj1 , . . . , ujn ) и насвободные переменные uf . Тогда условие Au = b можно записать как Bub + F uf = b.16В этом случае для ub в (1) справедливо равенство ub = B −1 b − B −1 F uf , а так как Av = bтогда и только тогда, когда Bvb + F vf = Bvb = b, то это равенство можно переписатькак ub = vb − B −1 F uf .

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

Тип файла
PDF-файл
Размер
1,07 Mb
Высшее учебное заведение

Список файлов ответов (шпаргалок)

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