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

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

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

Канторовичем.Другой способ выбора шага состоит в том, чтобы потребовать τkнаибольшим возможным, обеспечивающим убывание функционалаΨ вдоль выбранного направления спуска по антиградиенту.При этом получается разновидность градиентного спуска,называемая методом наискорейшего спуска.Его теория была разработанав конце 40-х годов XX века Л.В.

Канторовичем.Для определения величины шага τk в методе наискорейшего спусканужно подставить выражениеx(k) − τk Ψ ′ (x(k) ) = x(k) − τk (Ax(k) − b)в аргумент функционала энергиии продифференцировать по τk .Для удобства выкладок обозначим невязку r (k) := Ax(k) − b.ТогдаΨ x(k) − τk r (k) = 21 A(x(k) − τk r (k) ), x(k) − τk r (k) − hb, x(k) − τk r (k) i=12Ax(k) , x(k) − τk Ax(k) , r (k) + 21 τk2 Ar (k) , r (k)− h b, x(k) i + τk h b, r (k) i.Для удобства выкладок обозначим невязку r (k) := Ax(k) − b.ТогдаΨ x(k) − τk r (k) = 21 A(x(k) − τk r (k) ), x(k) − τk r (k) − hb, x(k) − τk r (k) i=12Ax(k) , x(k) − τk Ax(k) , r (k) + 21 τk2 Ar (k) , r (k)− h b, x(k) i + τk h b, r (k) i.При дифференцировании выписанного выражения по τk независящие от него члены исчезнут, и мы получимdΨ x(k) − τk r (k) = − Ax(k) , r (k) + τk hAr (k) , r (k) i + hb, r (k) idτk = τk Ar (k) , r (k) − Ax(k) − b, r (k)= τk Ar (k) , r (k) − hr (k) , r (k) i.Таким образом, в точке экстремума по τk из условияdΨ x(k) − τk r (k) = 0dτkнеобходимо следуетhr (k) , r (k) iτk = (k) (k) .Ar , rТаким образом, в точке экстремума по τk из условияdΨ x(k) − τk r (k) = 0dτkнеобходимо следуетhr (k) , r (k) iτk = (k) (k) .Ar , rПри найденном значении τk функционал энергии действительнодостигает минимума по выбранному направлению спуска, так кактогда его вторая производная по τk равнаhAr (k) , r (k) i,и она положительна.Псевдокод метода наискорейшего спускадля решения систем линейных уравнений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(k) }, порождаемая методом наискорейшегоспуска, сходится к решению x⋆ системы уравнений Ax = b излюбого начального приближения x(0) .Скорость этой сходимости оценивается неравенствомkx(k)⋆− x kA ≤M −µM +µkk x(0) − x⋆ kA ,k = 0, 1, 2, .

. . ,где µ, M — нижняя и верхняя границы спектра матрицы A.Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П. ШарыйКафедра математического моделирования НГУЛекция 22 декабря 2017 г.ТеоремаЕсли A — симметричная положительно определённая матрица, топоследовательность {x(k) }, порождаемая методом наискорейшегоспуска, сходится к решению x⋆ системы уравнений Ax = b излюбого начального приближения x(0) .Скорость этой сходимости оценивается неравенствомkx(k)⋆− x kA ≤M −µM +µkk x(0) − x⋆ kA ,k = 0, 1, 2, . .

. ,где µ, M — нижняя и верхняя границы спектра матрицы A.Для доказательства Теоремынам будет необходим следующий вспомогательный факт.ПредложениеПусть A — симметричная положительно определённая матрица,порождающая энергетическую норму k · kA в Rn .Если S — матрица, которая является значением некоторогомногочлена от матрицы A, то для любого вектора x ∈ RnсправедливоkSxkA ≤ kSk2 kxkA .Доказательство.Умножение матриц в общем случае некоммутативно.Но если в произведении двух матриц один из сомножителейявляется значением какого-то полинома от второго сомножителя,то эти матрицы перестановочны.Доказательство.Умножение матриц в общем случае некоммутативно.Но если в произведении двух матриц один из сомножителейявляется значением какого-то полинома от второго сомножителя,то эти матрицы перестановочны.В самом деле, пустьS = α0 I + α1 A + . . .

+ αn An ,тогдаAS = A(α0 + α1 A + . . . + αn An )= α0 A + α1 A2 + . . . + αn An+1= (α0 + α1 A + . . . + αn An )A = SA.Теперь заметим, что матрица S симметрична одновременно с A.Тогда S = QΣQ⊤ , где Q — ортогональная матрица,а Σ = diag {s1 , s2 , . . . , sn } — диагональная матрица,имеющая по диагонали собственные числа S.Их модули являются сингулярными числами σi (S) матрицы S.ПолучаемkSxk2A = hASx, Sxi = hSAx, Sxi= QΣQ⊤ Ax, QΣQ⊤ x = ΣQ⊤ Ax, ΣQ⊤ x≤ max s2i Q⊤ Ax, Q⊤ x = max |si |2 QQ⊤ Ax, xii=2 max σi (S)hAx, xi = kSk22 kxk2Ai2с учётом того, что max σi (S) = kSk22 .iДоказательство теоремы.Оно будет получено путём сравнения метода наискорейшего спускас методом градиентного спуска с постоянным оптимальным шагом,т. е.

методом Ричардсона.Доказательство теоремы.Оно будет получено путём сравнения метода наискорейшего спускас методом градиентного спуска с постоянным оптимальным шагом,т. е. методом Ричардсона.Пусть в результате выполнения (k − 1)-го шага методанаискорейшего спуска получено приближение x(k−1) .Далее делаем k-ый шаг, который даёт x(k) .Доказательство теоремы.Оно будет получено путём сравнения метода наискорейшего спускас методом градиентного спуска с постоянным оптимальным шагом,т. е. методом Ричардсона.Пусть в результате выполнения (k − 1)-го шага методанаискорейшего спуска получено приближение x(k−1) .Далее делаем k-ый шаг, который даёт x(k) .Обозначим также через x̃ результат выполнения с x(k−1) одногошага метода Ричардсона (простой итерации):x̃ = x(k−1) − τ Ax(k−1) − b .Мы уже знаем, что метод Ричардсона (простой итерации)совпадает с методом градиентного спуска с постоянным шагом.Мы уже знаем, что метод Ричардсона (простой итерации)совпадает с методом градиентного спуска с постоянным шагом.Как следствие, из самого построения метода наискорейшегоградиентного спуска вытекает, что при любом выборе параметра τΨ (x(k) ) ≤ Ψ (x̃)— вдоль направления антиградиента метод наискорейшего спускаидёт так, что уменьшает функционал энергии Ψ наиболее сильно.Далее, вспомним равенствоΨ (x) =12 hAx, xi− hb, xi =12 kx− x⋆ k2A − 21 hAx⋆ , x⋆ i,которое было получено при выводе функционала энергии Ψ (x).Далее, вспомним равенствоΨ (x) =12 hAx, xi− hb, xi =12 kx− x⋆ k2A − 21 hAx⋆ , x⋆ i,которое было получено при выводе функционала энергии Ψ (x).Так как 12 hAx⋆ , x⋆ i — постоянное вычитаемое, то изΨ (x(k) ) ≤ Ψ (x̃)следует(k)12 kx− x⋆ k2A ≤12 kx̃− x⋆ k2A ,то естьk x(k) − x⋆ kA ≤ kx̃ − x⋆ kA .— метод, обеспечивающий лучшее убывание функционалаэнергии обеспечивает также лучшее приближение к решениюв энергетической норме.Итакx̃ = x(k−1) − τ (Ax(k−1) − b),k = 1, 2, .

. . .Итакx̃ = x(k−1) − τ (Ax(k−1) − b),k = 1, 2, . . . .С другой стороны, если x⋆ — решение системы уравнений Ax = b,то естьAx⋆ = b,тоx⋆ = x⋆ − τ (Ax⋆ − b).Вычитая это равенство из равенства для x̃, получимx̃ − x⋆ = x(k−1) − x⋆ − τ (Ax(k−1) − Ax⋆ )= (I − τ A)(x(k−1) − x⋆ ),k = 1, 2, . . . .Матрица (I − τ A) являетсямногочленом первой степени от матрицы A.Поэтому можем применить доказанное ранее Предложение обоценке в энергетической норме:k x̃ − x⋆ kA ≤ kI − τ Ak2 k x(k) − x⋆ kA ,и это оценка итерации стационарного метода Ричардсона.Матрица (I − τ A) являетсямногочленом первой степени от матрицы A.Поэтому можем применить доказанное ранее Предложение обоценке в энергетической норме:k x̃ − x⋆ kA ≤ kI − τ Ak2 k x(k) − x⋆ kA ,и это оценка итерации стационарного метода Ричардсона.У метода наискорейшего спуска оценка заведомо не хуже этойоценки для любого τ , в частности, той, в которой взято значениепараметра шага2,τ=M +µоптимальное для спуска с постоянным шагом.Тогда в соответствии с равенствомkI − τопт Ak2 =M −µ.M +µдля метода Ричардсона (простой итерации) получаемkx(k)⋆− x kA ≤M −µM +µk x(k−1) − x⋆ kA ,k = 1, 2, .

. . .Отсюда следует утверждение теоремы.Градиент функционала энергии нормален к его поверхностямуровня, а шаг в методе наискорейшего спуска идёт до пересеченияс касательным эллипсоидом.x⋆x(0)Градиент функционала энергии нормален к его поверхностямуровня, а шаг в методе наискорейшего спуска идёт до пересеченияс касательным эллипсоидом.x⋆x(0)Поэтому траектория метода наискорейшего спуска являетсяломаной с перпендикулярными звеньями.Доказательство Теоремы основано на мажоризации наискорейшегоспуска методом Ричардсона (простой итерации) и может показатьсядовольно грубым.Но оценка сходимости в действительности весьма точно передаётособенности поведения метода — его замедление при M ≫ µ.Доказательство Теоремы основано на мажоризации наискорейшегоспуска методом Ричардсона (простой итерации) и может показатьсядовольно грубым.Но оценка сходимости в действительности весьма точно передаётособенности поведения метода — его замедление при M ≫ µ.Тогда матрица A плохообусловлена, cond(A) ≫ 1, и медленноезигзагообразное движение к решению в методе наискорейшегоспуска подтверждается на практике.Искомое решение находится на дне глубокого и вытянутого оврага,а метод «рыскает» от одного склона оврага к другому вместо того,чтобы идти напрямую к глубочайшей точке — решению.Метод сопряжённых градиентовМетодами сопряжённых направлений для решения системлинейных уравнений Ax = b называют методы, в которых решениеищется в виде линейной комбинации векторов, ортогональных вкаком-то специальном скалярном произведении.Обычно это скалярное произведение порождено матрицей системыили же какой-либо матрицей, связанной с матрицей системы.Метод сопряжённых градиентовМетодами сопряжённых направлений для решения системлинейных уравнений Ax = b называют методы, в которых решениеищется в виде линейной комбинации векторов, ортогональных вкаком-то специальном скалярном произведении.Обычно это скалярное произведение порождено матрицей системыили же какой-либо матрицей, связанной с матрицей системы.Таким образом, решение представляется в видеx=x(0)+nXci s(i) ,i=1гдеx(0) — начальное приближение,s(i) , i = 1, 2, .

. . , n, — векторы «сопряжённых направлений»,ci — коэффициенты разложения решения по ним.Термин «сопряжённые направления»имеет происхождение в аналитической геометрии.Направления, задаваемые векторами u и v, называютсясопряжёнными относительно поверхности второго порядка,задаваемой уравнением hRx, xi = const c симметричнойматрицей R, если hRu, vi = 0.Термин «сопряжённые направления»имеет происхождение в аналитической геометрии.Направления, задаваемые векторами u и v, называютсясопряжёнными относительно поверхности второго порядка,задаваемой уравнением hRx, xi = const c симметричнойматрицей R, если hRu, vi = 0.В методах сопряжённых направлений последовательно строитсябазис из векторов s(i) и одновременно находятся коэффициенты ci ,i = 1, 2, . .

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

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