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

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

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

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

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

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

{\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}},

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

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

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

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

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

Выполнение

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

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},

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

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

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

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

На каждом этапе мы вычисляем

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

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

p_{1}:=A^{-1}Bp_{2}

на потом.Коэффициент масштабирования определяется выражением

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Удзава, Х. (1958). «Итеративные методы вогнутого программирования». Ин Эрроу, К.Дж.; Гурвич, Л.; Узава, Х. (ред.). Исследования в области линейного и нелинейного программирования . Издательство Стэнфордского университета.
^ Jump up to: ^а ^б Элман, ХК; Голуб, Г.Х. (1994). «Неточные и заранее обусловленные алгоритмы Удзавы для решения задач седловой точки». СИАМ Дж. Нумер. Анальный. 31 (6): 1645–1661. CiteSeerX 10.1.1.307.8178 . дои : 10.1137/0731085 .
^ Брамбл, Дж. Х .; Пасчак, Дж. Э.; Васильев А.Т. (1997). «Анализ неточного алгоритма Удзавы для задач седловой точки». СИАМ Дж. Номер. Анал 34 (3): 1072–1982. CiteSeerX 10.1.1.52.9559 . дои : 10.1137/S0036142994273343 .
^ Зуленер, В. (1998). «Анализ итерационных методов решения седловых задач. Единый подход» . Математика. Комп . 71 (238): 479–505. дои : 10.1090/S0025-5718-01-01324-2 .
^ Jump up to: ^а ^б Грезер, К.; Корнхубер, Р. (2007). «О предобусловленных итерациях типа Удзавы для задачи седла с ограничениями-неравенствами». Методы декомпозиции предметной области в науке и технике XVI . Лек. Нет. Комп. наук. англ. Том. 55. С. 91–102. CiteSeerX 10.1.1.72.9238 . дои : 10.1007/978-3-540-34469-8_8 . ISBN 978-3-540-34468-1 .

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

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

[UZ58-1] Удзава, Х. (1958). «Итеративные методы вогнутого программирования». Ин Эрроу, К.Дж.; Гурвич, Л.; Узава, Х. (ред.). Исследования в области линейного и нелинейного программирования . Издательство Стэнфордского университета.

[ELGO94-2] Jump up to: ^а ^б Элман, ХК; Голуб, Г.Х. (1994). «Неточные и заранее обусловленные алгоритмы Удзавы для решения задач седловой точки». СИАМ Дж. Нумер. Анальный. 31 (6): 1645–1661. CiteSeerX 10.1.1.307.8178 . дои : 10.1137/0731085 .

[3] Брамбл, Дж. Х .; Пасчак, Дж. Э.; Васильев А.Т. (1997). «Анализ неточного алгоритма Удзавы для задач седловой точки». СИАМ Дж. Номер. Анал 34 (3): 1072–1982. CiteSeerX 10.1.1.52.9559 . дои : 10.1137/S0036142994273343 .

[4] Зуленер, В. (1998). «Анализ итерационных методов решения седловых задач. Единый подход» . Математика. Комп . 71 (238): 479–505. дои : 10.1090/S0025-5718-01-01324-2 .

[GRKO07-5] Jump up to: ^а ^б Грезер, К.; Корнхубер, Р. (2007). «О предобусловленных итерациях типа Удзавы для задачи седла с ограничениями-неравенствами». Методы декомпозиции предметной области в науке и технике XVI . Лек. Нет. Комп. наук. англ. Том. 55. С. 91–102. CiteSeerX 10.1.1.72.9238 . дои : 10.1007/978-3-540-34469-8_8 . ISBN 978-3-540-34468-1 .

[1]

[2]

[3]

[4]

[5]