Итерация Удзавы - 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]

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

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

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