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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Оно существует и единственно всилу положительной определённости матрицы A.Из единственности x⋆ следует, что некоторый вектор x ∈ Rnявляется решением системы уравнений тогда и только тогда,когда x − x⋆ = 0.Это, в свою очередь, равносильно kx − x⋆ k2A = 0.С другой стороны, учитывая симметричность матрицы A иравенство Ax⋆ = b, получаем− hAx⋆ , xiΨ (x) =12 hAx, xi− hb, xi ==12 hAx, xi− hAx⋆ , xi + 12 hAx⋆ , x⋆ i − 21 hAx⋆ , x⋆ i=12=12 hA(x=12k x12 hAx, xihAx, xi − hAx, x⋆ i − hAx⋆ , xi + hAx⋆ , x⋆ i − 12 hAx⋆ , x⋆ i− x⋆ ), x − x⋆ i − 12 hAx⋆ , x⋆ i− x⋆ k2A − 12 hAx⋆ , x⋆ i.Иными словами, функционал Ψ (x) отличается от половиныквадрата энергетической нормы погрешности лишь постояннымслагаемым 12 hAx⋆ , x⋆ i.Как следствие, Ψ (x) действительно достигает своего единственногоминимума при том же значении x, что и k x − x∗ k2A ,то есть на решении x⋆ рассматриваемой линейной системы.Как следствие, Ψ (x) действительно достигает своего единственногоминимума при том же значении x, что и k x − x∗ k2A ,то есть на решении x⋆ рассматриваемой линейной системы.ОпределениеДля симметричной положительно определённой матрицы Aотображение Ψ : Rn → R, действующее по правилуΨ (x) = 21 hAx, xi − hb, xi,называют функционалом энергии.Объяснение термина в том, что Ψ (x) является квадратичнойформой от x, и потому имеет сходство с выражениями дляразличных видов энергии в физических системах.Кинетическая энергия тела равна 21 mv 2 .Энергия упругой деформации пружины равна 21 kx2 , и т.

п.Типичный график функционала энергии и его линии уровня.Поскольку A — симметричная матрица, тоA = Q⊤DQ,где Q — ортогональная матрица, D = diag λ1 , λ2 , . . . , λn —диагональная матрица, на главной диагонали которой стоятсобственные значения λi (A) матрицы A, причём в силуположительной определённости матрицы A все λi (A) > 0.Подставляя в выражение для функционала энергии Ψ (x), получимΨ (x) = 21 Q⊤DQx, x − hb, xi= 12 D(Qx), Qx − hQb, Qxi=где обозначено y = Qx.12 hDy, yi− hQb, yi,Итак, в изменённой системе координат, которая получается спомощью ортогонального линейного преобразования переменных,выражение для функционала энергии Ψ (x) есть половина суммыквадратов с коэффициентами, равными собственным значениямматрицы A, т.

е. член 12 hDy, yi, минус линейный член hQb, yi.Таким образом, график функционала энергии Ψ— это эллиптический параболоид.Возможно, он сдвинут относительно начала координати ещё повёрнут.Его поверхности уровня (линии уровня в двумерном случае) —эллипсоиды (эллипсы), в центре которых находится искомоерешение системы уравнений.При этом форма эллипсоидов уровня находится в зависимости отразброса коэффициентов при квадратах переменных, то есть отспектрального числа обусловленности матрицы A, cond2 (A).Чем больше эта обусловленность, тем сильнее сплющеныэллипсоиды уровня.Для плохообусловленных СЛАУ решение находится на днедлинного и узкого «оврага».решение Ax = b⇐⇒нахождение min Ψ (x).Метод наискорейшего спускаМы рассмотрели две вариационные переформулировки задачирешения системы линейных алгебраических уравнений Ax = b.Как находить минимум соответствующих функционалов?Метод наискорейшего спускаМы рассмотрели две вариационные переформулировки задачирешения системы линейных алгебраических уравнений Ax = b.Как находить минимум соответствующих функционалов?Пусть f : Rn → R — некоторая функция, ограниченная снизуна всём пространстве Rn и принимающая своё наименьшеезначение в x⋆ , так чтоf (x) ≥ f (x⋆ ) = minn f (x)x∈Rдля любых x ∈ Rn .Нам нужно найти точку x⋆ .Саму функцию f , для которой ищется экстремум,в теории оптимизации называют целевой функцией.Различают экстремумы локальные и глобальные.локальныеминимумыглобальныйминимумЛокальными называются экстремумы, в которых значения целевойфункции лучше, чем в некоторой окрестности рассматриваемойточки.Локальными называются экстремумы, в которых значения целевойфункции лучше, чем в некоторой окрестности рассматриваемойточки.Глобальные экстремумы доставляют функции значения, лучшиесреди всех значений функции на всей её области определения.Локальными называются экстремумы, в которых значения целевойфункции лучше, чем в некоторой окрестности рассматриваемойточки.Глобальные экстремумы доставляют функции значения, лучшиесреди всех значений функции на всей её области определения.Нас в связи с задачей минимизации функционала энергииинтересуют, конечно, его глобальные минимумы.Типичным подходом к решению задач оптимизации являетсяитерационное построение последовательности значений аргумента{ x(k) }, которая «минимизирует» целевую функцию f .Мы строим последовательность { x(k) }, для которойlim f (x(k) ) = minn f (x).k→∞x∈RЕсли построенная последовательность { x(k) } сходитсяк некоторому пределу, то он и является решением задачи x⋆в случае непрерывной функции f .Метод градиентного спуска является способом построенияпоследовательности, которая является минимизирующей дляопределённого класса дифференцируемых целевых функций.Он основан на том, что направление наибольшего убывания целевойфункции в точке x̃ противоположно направлению градиентаf ′ (x̃) = ∇f (x̃) =f1′ (x̃), f2′ (x̃), .

. . , fn′ (x̃)⊤.Метод градиентного спускаПусть уже найдено какое-то приближение x(k) , k = 0, 1, 2, . . . , кточке минимума функции f (x).Из x(k) мы сдвигаемся по направлению наибольшего убыванияцелевой функции, которое противоположно направлению градиентаf ′ (x(k) ), т. е. берёмx(k+1) ← x(k) − τk f ′ (x(k) ),где τk — величина шага, которая выбирается из условия убыванияцелевой функции на рассматриваемой итерации.Далее можно повторить этот шаг ещё раз и ещё .

. . столько,сколько нужно для достижения желаемого приближения кминимуму.Если целевая функция имеет более одного локального экстремума,то метод может сходиться к какому-нибудь одному из них, которыйне обязательно является глобальным.Если целевая функция имеет более одного локального экстремума,то метод может сходиться к какому-нибудь одному из них, которыйне обязательно является глобальным.К счастью, этот феномен не реализуется в случае минимизациифункционала энергии Ψ (x), порождаемого системой линейныхуравнений с симметричной положительно определённой матрицей.Свойства Ψ (x) достаточно хороши.Он является гладким, имеет одну стационарную точку, одинлокальный минимум, который одновременно и глобален.Типичный график функционала энергии и его линии уровня.Вычислим градиент функционала энергии:nnnnXX∂Ψ (x)∂  1 XXbi x i  =aij xi xj −alj xj − bl ,=∂xl∂xl2i=1 j=1i=1j=1l = 1, 2, .

. . , n.Множитель 1/2 исчезает в результате потому, что в двойной суммепомимо квадратичных слагаемых aii x2i остальные слагаемыеприсутствуют парами, как aij xi xj и aji xj xi , причём aij = aji .Вычислим градиент функционала энергии:nnnnXX∂Ψ (x)∂  1 XXbi x i  =aij xi xj −alj xj − bl ,=∂xl∂xl2i=1 j=1i=1j=1l = 1, 2, . .

. , n.Множитель 1/2 исчезает в результате потому, что в двойной суммепомимо квадратичных слагаемых aii x2i остальные слагаемыеприсутствуют парами, как aij xi xj и aji xj xi , причём aij = aji .В целом′Ψ (x) =∂Ψ (x)∂Ψ (x) ∂Ψ (x),,...,∂x1∂x2∂xn⊤= Ax − b,т.

е. градиент функционала Ψ равен невязке решаемой системылинейных уравнений в рассматриваемой точке.Важнейшиий вывод из этого факта:метод Ричардсона (простой итерации)x(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, . . . ,является методом градиентного спуска для минимизациифункционала энергии Ψ , в котором шаг τk выбран постоянными равным τ .Важнейшиий вывод из этого факта:метод Ричардсона (простой итерации)x(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, .

. . ,является методом градиентного спуска для минимизациифункционала энергии Ψ , в котором шаг τk выбран постоянными равным τ .Вообще, метод градиентного спуска оказывается равносильнымпростейшему нестационарному итерационному методуx(k+1) ← x(k) − τk (Ax(k) − b),k = 0, 1, 2, . . . .Выбор величины шага τk является очень ответственным делом, таккак от него зависит и наличие сходимости, и её скорость.Выбор величины шага τk является очень ответственным делом, таккак от него зависит и наличие сходимости, и её скорость.Спуск по направлению антиградиента обеспечивает убываниецелевой функции лишь при достаточно малых шагах.Выбор величины шага τk является очень ответственным делом, таккак от него зависит и наличие сходимости, и её скорость.Спуск по направлению антиградиента обеспечивает убываниецелевой функции лишь при достаточно малых шагах.При неудачно большой величине шага мы можем попасть в точку,где значение функционала не меньше, чем в текущей точке.Выбор величины шага τk является очень ответственным делом, таккак от него зависит и наличие сходимости, и её скорость.Спуск по направлению антиградиента обеспечивает убываниецелевой функции лишь при достаточно малых шагах.При неудачно большой величине шага мы можем попасть в точку,где значение функционала не меньше, чем в текущей точке.С другой стороны, слишком малый шаг приведёт к оченьмедленному движению в сторону решения.Для градиентного метода с постоянным шагом его трактовка какметода Ричардсона (простой итерации) позволяет выбрать шагτk = const, который наверняка обеспечивает сходимость процесса.Для градиентного метода с постоянным шагом его трактовка какметода Ричардсона (простой итерации) позволяет выбрать шагτk = const, который наверняка обеспечивает сходимость процесса.Вспомним известный результатоб оптимизации скалярного предобуславливателя.Если положительные числа µ и M — это нижняя и верхняяграницы спектра положительно определённой матрицы A решаемойсистемы, то для сходимости следует взятьτk = τ =2.M +µДругой способ выбора шага состоит в том, чтобы потребовать τkнаибольшим возможным, обеспечивающим убывание функционалаΨ вдоль выбранного направления спуска по антиградиенту.При этом получается разновидность градиентного спуска,называемая методом наискорейшего спуска.Его теория была разработанав конце 40-х годов XX века Л.В.

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

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