1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 61
Текст из файла (страница 61)
Желая приобрести гладкость получаемого функционалапо неизвестной переменной x, обычно берут евклидову норму невязки, или даже её квадрат, т. е. скалярное произведение hAx − b, Ax − bi,чтобы не привлекать взятия корня. Получающаяся задача минимизации величины kAx − bk22 называется линейной задачей о наименьших3723. Численные методы линейной алгебрыквадратах, и мы рассмотрим её подробнее в §3.15.Ещё одним фактом, который служит теоретической основой для вариационных методов решения систем линейных алгебраических уравнений являетсяТеорема 3.10.1 Вектор x⋆ ∈ Rn является решением системы линейных алгебраических уравнений Ax = b с симметричной положительноопределённой матрицей A тогда и только тогда, когда он доставляетминимум функционалу Ψ (x) = 21 hAx, xi − hb, xi.Доказательство.
Если A — симметричная положительно-определённая матрица, то, как мы видели в §3.3а, выражением 21 hAx, xi задаётсятак называемая энергетическая норма k · kA векторов из Rn .Далее, пусть x⋆ — решение рассматриваемой системы линейных алгебраических уравнений Ax = b, которое существует и единственно всилу положительной определённости матрицы A.
Из единственностиx⋆ следует, что некоторый вектор x ∈ Rn является решением системыуравнений тогда и только тогда, когда x − x⋆ = 0. Это, в свою очередь,равносильно kx − x⋆ k2A = 0.С другой стороны, учитывая симметричность матрицы A и равенство Ax⋆ = b, получаемΨ (x) =12 hAx, xi=12 hAx, xi=12=12 hA(x=12k x− hb, xi =12 hAx, xi− hAx⋆ , xi− hAx⋆ , xi + 21 hAx⋆ , x⋆ i − 21 hAx⋆ , x⋆ ihAx, xi − hAx, x⋆ i − hAx⋆ , xi + hAx⋆ , x⋆ i − 12 hAx⋆ , x⋆ i− x⋆ ), x − x⋆ i − 12 hAx⋆ , x⋆ i− x⋆ k2A − 21 hAx⋆ , x⋆ i.(3.117)Иными словами, функционал Ψ (x) отличается от половины квадрата энергетической нормы погрешности лишь постоянным слагаемым1⋆⋆⋆2 hAx , x i (которое заранее неизвестно из-за незнания нами x ).
Какследствие, Ψ (x) действительно достигает своего единственного минимума при том же значении аргумента, что и k x − x∗ k2A , т. е. на решенииx⋆ рассматриваемой линейной системы.Функционал Ψ (x) = 12 hAx, xi − hb, xi, который является квадратичной формой от вектора переменных x, обычно называют функционалом энергии из-за его сходства с выражениями для различных видов3.10.
Нестационарные итерационные методы373энергии в физических системах. К примеру, кинетическая энергия теламассы m, движущегося со скоростью v, равна 21 mv 2 . Энергия упругойдеформации пружины с жёсткостью k, растянутой или сжатой на величину x, равна 12 kx2 , и т. п.Рис.
3.21. Типичный график функционалаэнергии и его линии уровня.Поскольку A — симметричная матрица, то ортогональным преобразованием подобия она может быть приведена к диагональной матрицеD, на главной диагонали которой стоят собственные значения A:A = Q⊤DQ,причём в силу положительной определённости матрицы A диагональные элементы D положительны. Подставляя это представление в выражение для функционала энергии Ψ (x), получимΨ (x) = 12 Q⊤DQx, x − hb, xi= 12 D(Qx), Qx − hQb, Qxi=где обозначено y = Qx.12 hDy, yi− hQb, yi,3743.
Численные методы линейной алгебрыИтак, в изменённой системе координат, которая получается с помощью ортогонального линейного преобразования переменных, выражение для функционала энергии Ψ (x) есть половина суммы квадратов с коэффициентами, равными собственным значениям матрицы A,т. е. член 21 hDy, yi, минус линейный член hQb, yi. Таким образом, график функционала энергии — это эллиптический параболоид, возможно, сдвинутый относительно начала координат и ещё повёрнутый, а егоповерхности уровня (линии уровня в двумерном случае) — эллипсоиды (эллипсы), в центре которых находится искомое решение системыуравнений.
При этом форма эллипсоидов уровня находится в зависимости от разброса коэффициентов при квадратах переменных, т. е. отчисла обусловленности матрицы A. Чем больше эта обусловленность,тем сильнее сплющены эллипсоиды уровня, так что для плохообусловленных СЛАУ решение находится на дне длинного и узкого «оврага».3.10бМетод наискорейшего спускаВ предшествующем пункте были предложены две вариационные переформулировки задачи решения системы линейных алгебраическихуравнений. Как находить минимум соответствующих функционалов?Прежде, чем строить конкретные численные алгоритмы, рассмотримобщую схему.Пусть f : Rn → R — некоторая функция, ограниченная снизу навсём пространстве Rn и принимающая своё наименьшее значение в x⋆ ,так чтоf (x) ≥ f (x⋆ ) = minn f (x)x∈Rдля любых x ∈ Rn .Нам нужно найти точку x⋆ .
При этом саму функцию f , для которойищется экстремум, в теории оптимизации называют целевой функцией.Различают экстремумы локальные и глобальные. Локальными называют экстремумы, в которых значения целевой функции лучше,чем в некоторой окрестности рассматриваемой точки. Глобальные экстремумы доставляют функции значения, лучшие среди всех значенийфункции на всей её области определения.
Нас в связи с задачей минимизации функционала энергии интересуют, конечно, его глобальныеминимумы.Типичным подходом к решению задач оптимизации является итерационное построение последовательности значений аргумента { x(k) },3.10. Нестационарные итерационные методы375которая «минимизирует» функцию f в том смысле, чтоlim f (x(k) ) = minn f (x).k→∞x∈RЕсли построенная последовательность { x(k) } сходится к некоторомупределу, то он и является решением задачи x⋆ в случае непрерывнойфункции f .Метод градиентного спуска является способом построения последовательности, которая является минимизирующей для определённогокласса дифференцируемых целевых функций, и заключается в следующем. Пусть уже найдено какое-то приближение x(k) , k = 0, 1, 2, .
. . , кточке минимума функции f (x). Естественная идея состоит в том, чтобы из x(k) сдвинуться по направлению наибольшего убывания целевойфункции, которое противоположно направлению градиента f ′ (x(k) ),т. е. взятьx(k+1) ← x(k) − τk f ′ (x(k) ),(3.118)где τk — величина шага, которая выбирается из условия убывания целевой функции на рассматриваемой итерации. Далее мы можем повторить этот шаг ещё раз и ещё . . . столько, сколько требуется длядостижения требуемого приближения к минимуму.Если целевая функция имеет более одного локального экстремума,то этот метод может сходиться к какому-нибудь одному из них, который не обязательно является глобальным. К счастью, подобный феномен не может случиться в интересующем нас случае минимизациифункционала энергии Ψ (x), порождаемого системой линейных уравнений с симметричной положительно определённой матрицей.
СвойстваΨ (x) достаточно хороши, и он имеет один локальный минимум, который одновременно и глобален.Вычислим градиент функционала энергии:nnnnXX∂Ψ (x)∂ 1 XXalj xj − bl ,bi xi=aij xi xj −=∂xl∂xl2 i=1 j=1j=1i=1l = 1, 2, . . . , n. Множитель 1/2 исчезает в результате потому, что в двойной сумме помимо квадратичных слагаемых aii x2i остальные слагаемыеприсутствуют парами, как aij xi xj и aji xj xi , причём aij = aji . В целом⊤∂Ψ (x) ∂Ψ (x)∂Ψ (x)′Ψ (x) =,,...,= Ax − b,∂x1∂x2∂xn3763. Численные методы линейной алгебрылокальныеминимумыглобальныйминимумРис. 3.22.
Глобальные и локальные минимумы функции.т. е. градиент функционала Ψ равен невязке решаемой системы линейных уравнений в рассматриваемой точке. Важнейшим выводом изэтого факта является тот, что метод простой итерации (3.104)–(3.115)является ни чем иным, как методом градиентного спуска (3.118) дляминимизации функционала энергии Ψ , в котором шаг τk выбран постоянным и равным τ . Вообще, метод градиентного спуска (3.118) оказывается равносильным простейшему нестационарному итерационномуметоду (3.116).Выбор величины шага τk является очень ответственным делом, таккак от него зависит и наличие сходимости, и её скорость. Спуск понаправлению антиградиента обеспечивает убывание целевой функциилишь при достаточно малых шагах, и потому при неудачно большойвеличине шага мы можем попасть в точку, где значение функционала не меньше, чем в текущей точке.
С другой стороны, слишком малый шаг приведёт к очень медленному движению в сторону решения.Для градиентного метода с постоянным шагом его трактовка как метода простой итерации позволяет, опираясь на результат §3.9г, выбратьшаг τk = const, который наверняка обеспечивает сходимость процесса.Именно, если положительные числа µ и M — это нижняя и верхняяграницы спектра положительно определённой матрицы A решаемой3.10. Нестационарные итерационные методы377системы, то в соответствии с (3.105) для сходимости следует взятьτk = τ =2.M +µДругой способ выбора шага состоит в том, чтобы потребовать τ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) = 12 A(x(k) − τk r(k) ), x(k) − τk r(k) − hb, x(k) − τk r(k) i= 12 Ax(k) , x(k) − τk Ax(k) , r(k) + 12 τ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τkhr(k) , r(k) iτk = (k) (k) .Ar , rЛегко видеть, что при найденном значении τk функционалом энергии действительно достигается минимум по выбранному направлению3783.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
