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

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

Текст из файла (страница 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, т.

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

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