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

В вычислительной математике , то итерация Узава алгоритм для решения седловых точек задач. Он назван в честь Хирофуми Удзавы и изначально был введен в контексте вогнутого программирования. ^[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}}$

Модификации и расширения [ править ]

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

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

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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