Итерация Удзавы - Uzawa iteration

В вычислительная математика, то Итерация Удзавы это алгоритм решения точка перевала проблемы. Он назван в честь Хирофуми Удзава и изначально был введен в контексте вогнутого программирования.^[1]

Основная идея

Рассмотрим задачу перевала вида

${\displaystyle {\begin{pmatrix}A&B\\B^{*}&\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}\end{pmatrix}},}$

куда ${\displaystyle A}$ симметричный положительно определенная матрица. Умножение первой строки на ${\displaystyle B^{*}A^{-1}}$ и вычитание из второй строки дает верхнетреугольную систему

${\displaystyle {\begin{pmatrix}A&B\\&-S\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}-B^{*}A^{-1}b_{1}\end{pmatrix}},}$

куда ${\displaystyle S:=B^{*}A^{-1}B}$ обозначает Дополнение Шура.С ${\displaystyle S}$ является симметричным положительно определенным, мы можем применять стандартные итерационные методы, такие как градиентный спуск метод или метод сопряженных градиентов к

${\displaystyle Sx_{2}=B^{*}A^{-1}b_{1}-b_{2}}$

чтобы вычислить ${\displaystyle x_{2}}$.Вектор ${\displaystyle x_{1}}$ можно восстановить, решив

${\displaystyle Ax_{1}=b_{1}-Bx_{2}.\,}$

Есть возможность обновить ${\displaystyle x_{1}}$ рядом ${\displaystyle x_{2}}$ во время итерации для системы дополнения Шура и, таким образом, получить эффективный алгоритм.

Выполнение

Мы начинаем итерацию сопряженного градиента с вычисления невязки

${\displaystyle r_{2}:=B^{*}A^{-1}b_{1}-b_{2}-Sx_{2}=B^{*}A^{-1}(b_{1}-Bx_{2})-b_{2}=B^{*}x_{1}-b_{2},}$

системы дополнения Шура, где

${\displaystyle x_{1}:=A^{-1}(b_{1}-Bx_{2})}$

обозначает верхнюю половину вектора решения, соответствующего первоначальному предположению ${\displaystyle x_{2}}$ для его нижней половины. Завершаем инициализацию, выбрав первое направление поиска

${\displaystyle p_{2}:=r_{2}.\,}$

На каждом шаге мы вычисляем

${\displaystyle a_{2}:=Sp_{2}=B^{*}A^{-1}Bp_{2}=B^{*}p_{1}}$

и сохранить промежуточный результат

${\displaystyle p_{1}:=A^{-1}Bp_{2}}$

для последующего использования. Коэффициент масштабирования определяется как

${\displaystyle \alpha :=p_{2}^{*}a_{2}/p_{2}^{*}r_{2}}$

и приводит к обновлениям

${\displaystyle x_{2}:=x_{2}+\alpha p_{2},\quad r_{2}:=r_{2}-\alpha a_{2}.}$

Используя промежуточный результат ${\displaystyle p_{1}}$ сохраненные ранее, мы также можем обновить верхнюю часть вектора решения

${\displaystyle x_{1}:=x_{1}-\alpha p_{1}.\,}$

Теперь осталось только построить новое направление поиска по Процесс Грама – Шмидта, т.е.

${\displaystyle \beta :=r_{2}^{*}a_{2}/p_{2}^{*}a_{2},\quad p_{2}:=r_{2}-\beta p_{2}.}$

Итерация прекращается, если остаточная ${\displaystyle r_{2}}$ стал достаточно малым или если норма ${\displaystyle p_{2}}$ значительно меньше, чем ${\displaystyle r_{2}}$ указывая, что Крыловское подпространство был почти истощен.

Модификации и расширения

Если решать линейную систему ${\displaystyle Ax=b}$ точно не выполнимо, могут применяться неточные решатели.^[2][3][4]

Если система дополнения Шура плохо обусловлена, можно использовать предварительные кондиционеры, чтобы повысить скорость сходимости лежащего в основе метода градиента.^[2][5]

Ограничения неравенства могут быть включены, например, для решения проблем с препятствиями.^[5]

Рекомендации

1. Удзава, Х. (1958). «Итерационные методы вогнутого программирования». In Arrow, K. J .; Hurwicz, L .; Удзава, Х. (ред.). Исследования по линейному и нелинейному программированию. Stanford University Press.
2. Elman, H.C .; Голуб, Г.Х. (1994). «Неточные и предварительно обусловленные алгоритмы Удзавы для задач перевала». SIAM J. Numer. Анальный. 31 (6): 1645–1661. CiteSeerX  10.1.1.307.8178. Дои:10.1137/0731085.
3. Брамбл, Дж. Х.; Pasciak, J. E .; Василев, А. Т. (1997). «Анализ неточного алгоритма Удзавы для задач перевала». SIAM J. Numer. Анальный. 34 (3): 1072–1982. CiteSeerX  10.1.1.52.9559. Дои:10.1137 / S0036142994273343.
4. Зуленер, В. (1998). «Анализ итерационных методов для задач перевала. Единый подход». Математика. Comp. 71 (238): 479–505. Дои:10.1090 / S0025-5718-01-01324-2.
5. Gräser, C .; Корнхубер, Р. (2007). «О предобусловленных итерациях типа Удзавы для задачи перевала с ограничениями-неравенствами». Методы декомпозиции доменов в науке и технике XVI. Lec. Нет. Комп. Sci. Англ. 55. С. 91–102. CiteSeerX  10.1.1.72.9238. Дои:10.1007/978-3-540-34469-8_8. ISBN  978-3-540-34468-1.

дальнейшее чтение

• Чен, Чжансинь (2006). «Методы решения линейных систем». Методы конечных элементов и их приложения. Берлин: Springer. С. 145–154. ISBN  978-3-540-28078-1.