Главная » Просмотр файлов » 1611688847-5b7354cc83380cb6c671f7c9dd5f83f8

1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 25

Файл №826648 1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (2017- Лекции Шарый) 25 страница1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648) страница 252021-01-26СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

. , n.Наиболее популярными представителями методов сопряжённыхнаправлений являются методы сопряжённых градиентов,«Conjugate Gradient Method» или просто «CG»Напомним важные фактыТеоремаВектор x⋆ ∈ Rn является решением системы линейныхалгебраических уравнений Ax = b с симметричной положительноопределённой матрицей A тогда и только тогда, когда ондоставляет минимум функционалуΨ (x) = 21 hAx, xi − hb, xi.Напомним важные фактыТеоремаВектор x⋆ ∈ Rn является решением системы линейныхалгебраических уравнений Ax = b с симметричной положительноопределённой матрицей A тогда и только тогда, когда ондоставляет минимум функционалуΨ (x) = 21 hAx, xi − hb, xi.ФункционалΨ (x) = 12 hAx, xi − hb, xi,который является квадратичной формой от вектора переменных x,называют функционалом энергии.Типичный график функционала энергии и его линии уровня.Метод наискорейшего спуска для решения систем линейныхалгебраических уравнений Ax = b с симмметричнойположительно-определённой матрицейk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )r (k) ← Ax(k) − b ;τk ←k r (k) k22;hAr (k) , r (k) ix(k+1) ← x(k) − τk r (k) ;k ← k + 1;END DOЕсли матрица A плохообусловлена, то искомое решение находитсяна дне глубокого и вытянутого оврага, а метод «рыскает» от одногосклона к другому вместо того, чтобы идти напрямую к решению.x⋆x(0)Если матрица A плохообусловлена, то искомое решение находитсяна дне глубокого и вытянутого оврага, а метод «рыскает» от одногосклона к другому вместо того, чтобы идти напрямую к решению.x⋆x(0)Можно ли скорректировать это движение к решению,чтобы оно было «более прямым»?Метод спуска — способ минимизации целевой функции.Пусть уже найдено какое-то приближение x(k) , k = 0, 1, 2, .

. . ,к точке минимума функции f (x).Выбираем направление спуска s в точке x(k) .Переходим из x(k) по направлению s на некоторый шаг τk ,полагаяx(k+1) ← x(k) + τk s.Шаг τk выбирается из условия убывания целевой функции.Далее мы можем повторить этот шаг ещё раз и ещё . .

.столько, сколько нужно для достижения желаемогоприближения к минимуму.Метод спуска — способ минимизации целевой функции.Пусть уже найдено какое-то приближение x(k) , k = 0, 1, 2, . . . ,к точке минимума функции f (x).Выбираем направление спуска s в точке x(k) .Переходим из x(k) по направлению s на некоторый шаг τk ,полагаяx(k+1) ← x(k) + τk s.Шаг τk выбирается из условия убывания целевой функции.Далее мы можем повторить этот шаг ещё раз и ещё . . .столько, сколько нужно для достижения желаемогоприближения к минимуму.Как выбрать хорошее направление спуска s? . . .Метод сопряжённых градиентовПусть к началу k-го шага метода сопряжённых градиентовуже найдено приближение к решению x(k−1) .Следующее направление спуска s(k) выбираетсякак линейная комбинация векторов−∇Ψ (x(k−1) ), т.

е. антиградиента функционала энергии Ψв точке x(k−1) , который противоположен вектору невязкиr (k−1) := Ax(k−1) − b,предыдущего направления спуска s(k−1) .Метод сопряжённых градиентовПусть к началу k-го шага метода сопряжённых градиентовуже найдено приближение к решению x(k−1) .Следующее направление спуска s(k) выбираетсякак линейная комбинация векторов−∇Ψ (x(k−1) ), т. е.

антиградиента функционала энергии Ψв точке x(k−1) , который противоположен вектору невязкиr (k−1) := Ax(k−1) − b,предыдущего направления спуска s(k−1) .На математическом языке:s(k) = −r (k−1) + υk s(k−1)с некоторым коэффициентом υk ∈ R.При этом коэффициент υk определяется так,чтобы направления спуска s(k) и s(k−1) были A-ортогональными:hAs(k) , s(k−1) i = hs(k) , As(k−1) i = 0.Тогдаh−r (k−1) + υk s(k−1) , As(k−1) i = 0,так что− hr (k−1) , As(k−1) i + υk hs(k−1) , As(k−1) i = 0.Окончательно,υk =hr (k−1) , As(k−1) i.hs(k−1) , As(k−1) i(1)Метод сопряжённых градиентовОбщая вычислительная схемаx(k+1) ← x(k) + τk s— как и у всех методов спуска.Величина шага τk берётся так, чтобы обеспечить наибольшееубывание функционала энергии вдоль направления спуска.Это аналогично методу наискорейшего спуска,но направление спуска теперь берётся другим.Метод сопряжённых градиентовДля определения величины шага τk в методе спуска нужноподставить x(k) + τk s в аргумент функционала энергии Ψ ,затем продифференцировать полученное выражение по τk .Метод сопряжённых градиентовДля определения величины шага τk в методе спуска нужноподставить x(k) + τk s в аргумент функционала энергии Ψ ,затем продифференцировать полученное выражение по τk .ИмеемΨ x(k) + τk s = 21 A(x(k) + τk s), x(k) + τk s − hb, x(k) + τk si=12Ax(k) , x(k) + τk Ax(k) , s +− h b, x(k) i − τk h b, si.1 22 τkAs, sПри дифференцировании выписанного выражения по τk независящие от него члены исчезнут, и мы получимdΨ x(k) + τk s = Ax(k) , s + τk hAs, si − hb, sidτk = τk As, s + Ax(k) − b, s= τk As, s + hr (k) , si,где обозначено r (k) := Ax(k) − b — невязка приближения x(k) .При дифференцировании выписанного выражения по τk независящие от него члены исчезнут, и мы получимdΨ x(k) + τk s = Ax(k) , s + τk hAs, si − hb, sidτk = τk As, s + Ax(k) − b, s= τk As, s + hr (k) , si,где обозначено r (k) := Ax(k) − b — невязка приближения x(k) .Таким образом, в точке экстремума по τk условиенеобходимо влечётdΨ x(k) − τk s = 0dτkhr (k) , si.τk = − As, s(2)Легко видеть, что при найденном значении τkфункционал энергии Ψ действительно достигаетминимума по выбранному направлению спуска s.Это следует из того, что вторая производная по τk равнаd2Ψ x(k) + τk s = As, s > 0,2dτkв силу положительной определённости матрицы A.Метод сопряжённых градиентовШаг 1.Выбираем начальное приближение x(0) и находим направлениеспуска на первом шагеs(1) = −∇Ψ (x(0) ) = −r (0) = −(Ax(0) − b)— направление антиградиента функционала энергии в точке x(0) .Метод сопряжённых градиентовШаг 1.Выбираем начальное приближение x(0) и находим направлениеспуска на первом шагеs(1) = −∇Ψ (x(0) ) = −r (0) = −(Ax(0) − b)— направление антиградиента функционала энергии в точке x(0) .Следующее приближение x(0) выбирается по формуле (2) какx(1) ← x(0) + τ1 s(1) ,гдеτ1 = −hr (0) , r (0) ihr (0) , s(1) i=,hAs(1) , s(1) ihAr (0) , r (0) iт.

е. чтобы минимизировать функционал энергии на этом шаге.Метод сопряжённых градиентовШаг k, k = 2, 3, . . . .Пусть уже известно приближение x(k−1)и направление спуска s(k−1) , по которому оно было получено.Выбираем следующим направлением спуска векторs(k) = −r (k−1) + υk s(k−1) ,(3)гдеr (k−1) = Ax(k−1) − b— невязка в точке x(k−1) ,а коэффициент υk выбирается в соответствии с формулой (1):υk =h r (k−1) , As(k−1) i.hs(k−1) , As(k−1) i(4)Метод сопряжённых градиентовШаг k, k = 2, 3, . . . . (продолжение)Вычисляем следующее приближение к решениюx(k) ← x(k−1) + τk s(k) ,гдеτk = −hr (k−1) , s(k) i.hAs(k) , s(k) iМетод сопряжённых градиентовШаг k, k = 2, 3, .

. . . (продолжение)Вычисляем следующее приближение к решениюx(k) ← x(k−1) + τk s(k) ,гдеτk = −hr (k−1) , s(k) i.hAs(k) , s(k) iКак следствие, невязка на k-ом шаге метода сопряжённыхградиентов изменяется следующим образомr (k) = Ax(k) − b= A x(k−1) + τk s(k) − b= r (k−1) − τk As(k) .(5)ПредложениеВ методе сопряжённых градиентов векторы невязок, получаемые наследующих друг за другом шагах, ортогональны друг другу:h r (k−1) , r (k) i = 0,k = 1, 2, .

. . ,Векторы невязок ортогональны направлениям спуска на текущем ипредыдущем шагах метода сопряжёных градиентов:h r (1) , s(1) i = 0,h r (k) , s(k) i = h r (k) , s(k−1) i = 0,k = 2, 3, . . . .Доказательство.Прежде всего, отметим, что−hr (1) , s(1) i = hr (1) , r (0) i = hAx(1) − b, r (0) i= hAx(0) − τ1 Ar (0) − b, r (0) i = hr (0) − τ1 Ar (0) , r (0) i= hr (0) , r (0) i − τ1 hAr (0) , r (0) i = 0в силу определения τ1 .Доказательство.Прежде всего, отметим, что−hr (1) , s(1) i = hr (1) , r (0) i = hAx(1) − b, r (0) i= hAx(0) − τ1 Ar (0) − b, r (0) i = hr (0) − τ1 Ar (0) , r (0) i= hr (0) , r (0) i − τ1 hAr (0) , r (0) i = 0в силу определения τ1 .Далее доказательство продолжается по индукции.Рассмотрим k-ый шаг метода сопряжённых градиентов.Из расчётных формул (5) следует, чтоhr (k) , s(k) i = hr (k−1) , s(k) i − τk hAs(k) , s(k) i = 0,так какτk = −hr (k−1) , s(k) i.hAs(k) , s(k) iПоэтому на основе (3) и (5) можем заключить, чтоhr (k) , s(k−1) i = hr (k−1) , s(k−1) i − τk hAs(k) , s(k−1) i|{z}=0= −τk A(−r (k−1) + υk s(k−1) ), s(k−1)= −τk −hAr (k−1) , s(k−1) i + υk hAs(k−1) , s(k−1) i = 0в силу определения υk .Наконец, в силу доказанного результата и определения sk , т.

е.формулы (3), имеем0 = hs(k) , r (k) i = −hr (k−1) , r (k) i + υk hs(k−1) , r (k) i.Выше мы показали, чтоhr (k) , s(k−1) i = hs(k−1) , r (k) i = 0.Таким образом, в самом делеhr (k) , r (k−1) i = 0.Это завершает доказательство Предложения.На самом деле, справедлив более общий результатТеоремаВ методе сопряжённых градиентов векторы последовательныхневязок r (k) = Ax(k) − b, k = 0, 1, 2, .

. ., образуют ортогональнуюсистему векторов, т. е.h r (i) , r (j) i = 0,i 6= j.В методе сопряжённых градиентов векторы последовательныхнаправлений спуска s(k) , k = 1, 2, . . ., являются A-ортогональнымидруг другу, т. е.h s(i) , s(j) iA = h As(i) , s(j) i = 0,i 6= j.Иными словами,ортогональны не только следующие друг за другомвектора невязок, но все эти невязки вообще взаимноортогональны друг другу;A-ортогональны не только следующие друг задругом вектора направлений спуска, но все этинаправления вообще взаимно A-ортогональныдруг другу.Иными словами,ортогональны не только следующие друг за другомвектора невязок, но все эти невязки вообще взаимноортогональны друг другу;A-ортогональны не только следующие друг задругом вектора направлений спуска, но все этинаправления вообще взаимно A-ортогональныдруг другу.Для удобства и без большого ограничения общности условимсясчитать, что s(0) = 0, т.

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

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

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

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