Андерсон ускорение

В математике ускорение Андерсона , также называемое перемешиванием Андерсона , представляет собой метод ускорения скорости сходимости итераций с фиксированной точкой . Представлено Дональдом Г. Андерсоном, ^[1] этот метод можно использовать для поиска решения уравнений с неподвижной точкой. $f(x)=x$ часто возникающие в области вычислительной техники .

Определение

Дана функция $f:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ , рассмотрим задачу нахождения неподвижной точки $f$ , что является решением уравнения $f(x)=x$ . Классический подход к проблеме заключается в использовании итерационной схемы с фиксированной точкой ; ^[2] то есть при первоначальном предположении $x_{0}$ для решения, чтобы вычислить последовательность $x_{i+1}=f(x_{i})$ до тех пор, пока не будет выполнен некоторый критерий сходимости. Однако сходимость такой схемы в общем случае не гарантирована; более того, скорость сходимости обычно линейна, что может стать слишком медленным, если вычисление функции $f$ является вычислительно дорогостоящим. ^[2] Ускорение Андерсона — это метод ускорения сходимости последовательности с фиксированной точкой. ^[2]

Определить остаток $g(x)=f(x)-x$ , и обозначим $f_{k}=f(x_{k})$ и $g_{k}=g(x_{k})$ (где $x_{k}$ соответствует последовательности итераций из предыдущего пункта). Учитывая первоначальное предположение $x_{0}$ и целочисленный параметр $m\geq 1$ , метод можно сформулировать следующим образом: ^[3]^{[примечание 1]}

x_{1}=f(x_{0})

\forall k=1,2,\dots

m_{k}=\min\{m,k\}

G_{k}={\begin{bmatrix}g_{k-m_{k}}&\dots &g_{k}\end{bmatrix}}

\alpha _{k}=\operatorname {argmin} _{\alpha \in A_{k}}\|G_{k}\alpha \|_{2},\quad {\text{where}}\;A_{k}=\{\alpha =(\alpha _{0},\dots ,\alpha _{m_{k}})\in \mathbb {R} ^{m_{k}+1}:\sum _{i=0}^{m_{k}}\alpha _{i}=1\}

x_{k+1}=\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f_{k-m_{k}+i}

где умножение матрицы на вектор $G_{k}\alpha =\sum _{i=0}^{m_{k}}(\alpha )_{i}g_{k-m_{k}+i}$ , и $(\alpha )_{i}$ это $i$ -й элемент $\alpha$ . Для завершения итераций метода можно использовать обычные критерии остановки. Например, итерации можно остановить, если $\|x_{k+1}-x_{k}\|$ попадает под установленный допуск или когда остаточная $g(x_{k})$ попадает под установленный допуск. ^[2]

Было обнаружено, что по сравнению со стандартной итерацией с фиксированной точкой этот метод сходится быстрее и более устойчив, а в некоторых случаях позволяет избежать расхождения последовательности с фиксированной точкой. ^[3]^[4]

Вывод

Для решения $x^{*}$ , мы это знаем $f(x^{*})=x^{*}$ , что эквивалентно тому, что $g(x^{*})={\vec {0}}$ . Поэтому мы можем перефразировать проблему как задачу оптимизации, в которой мы хотим минимизировать $\|g(x)\|_{2}$ .

Вместо того, чтобы идти прямо из $x_{k}$ к $x_{k+1}$ выбрав $x_{k+1}=f(x_{k})$ как и в итерации с фиксированной точкой , давайте рассмотрим промежуточную точку $x'_{k+1}$ что мы выбираем линейную комбинацию $x'_{k+1}=X_{k}\alpha _{k}$ , где вектор коэффициентов $\alpha _{k}\in A_{k}$ , и $X_{k}={\begin{bmatrix}x_{k-m_{k}}&\dots &x_{k}\end{bmatrix}}$ матрица, содержащая последний $m_{k}+1$ точки и выберите $x'_{k+1}$ так, что это минимизирует $\|g(x'_{k+1})\|_{2}$ . Поскольку элементы в $\alpha _{k}$ суммируясь до единицы, мы можем сделать приближение первого порядка $g(X_{k}\alpha _{k})=g\left(\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}x_{k-m_{k}+i}\right)\approx \sum _{i=0}^{m_{k}}(\alpha _{k})_{i}g(x_{k-m_{k}+i})=G_{k}\alpha _{k}$ , и наша задача состоит в том, чтобы найти $\alpha$ что сводит к минимуму $\|G_{k}\alpha \|_{2}$ . После того, как нашел $\alpha _{k}$ , мы могли бы в принципе вычислить $x'_{k+1}$ .

Однако, поскольку $f$ призван приблизить точку к $x^{*}$ , $f(x'_{k+1})$ вероятно, ближе к $x^{*}$ чем что $x'_{k+1}$ есть, поэтому имеет смысл выбрать $x_{k+1}=f(x'_{k+1})$ скорее, чем $x_{k+1}=x'_{k+1}$ . Кроме того, поскольку элементы в $\alpha _{k}$ суммируясь до единицы, мы можем сделать приближение первого порядка $f(x'_{k+1})=f\left(\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}x_{k-m_{k}+i}\right)\approx \sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f(x_{k-m_{k}+i})=\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f_{k-m_{k}+i}$ . Поэтому мы выбираем

$x_{k+1}=\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f_{k-m_{k}+i}$ .

Решение задачи минимизации

На каждой итерации алгоритма ограниченной оптимизации задача $\operatorname {argmin} \|G_{k}\alpha \|_{2}$ , при условии $\alpha \in A_{k}$ необходимо решить. Задачу можно переформулировать в нескольких эквивалентных формулировках: ^[3] получение различных методов решения, которые могут привести к более удобной реализации:

определение матриц ${\mathcal {G}}_{k}={\begin{bmatrix}g_{k-m_{k}+1}-g_{k-m_{k}}&\dots &g_{k}-g_{k-1}\end{bmatrix}}$ и ${\mathcal {X}}_{k}={\begin{bmatrix}x_{k-m_{k}+1}-x_{k-m_{k}}&\dots &x_{k}-x_{k-1}\end{bmatrix}}$ , решать $\gamma _{k}=\operatorname {argmin} _{\gamma \in \mathbb {R} ^{m_{k}}}\|g_{k}-{\mathcal {G}}_{k}\gamma \|_{2}$ , и установите $x_{k+1}=x_{k}+g_{k}-({\mathcal {X}}_{k}+{\mathcal {G}}_{k})\gamma _{k}$ ; ^[3]^[4]
решать $\theta _{k}=\{(\theta _{k})_{i}\}_{i=1}^{m_{k}}=\operatorname {argmin} _{\theta \in \mathbb {R} ^{m_{k}}}\left\|g_{k}+\sum _{i=1}^{m_{k}}\theta _{i}(g_{k-i}-g_{k})\right\|_{2}$ , затем установите $x_{k+1}=x_{k}+g_{k}+\sum _{j=1}^{m_{k}}(\theta _{k})_{j}(x_{k-j}-x_{k}+g_{k-j}-g_{k})$ . ^[1]

Для обоих вариантов задача оптимизации имеет форму неограниченной линейной задачи наименьших квадратов , которую можно решить стандартными методами, включая QR-разложение. ^[3] и разложение по сингулярным значениям , ^[4] возможно, включение методов регуляризации для устранения недостатков рангов и проблем обусловленности в задаче оптимизации. Решение задачи наименьших квадратов путем решения нормальных уравнений обычно не рекомендуется из-за потенциальных численных нестабильностей и, как правило, высоких вычислительных затрат. ^[4]

Застой в методе (т.е. последующие итерации с одинаковым значением, $x_{k+1}=x_{k}$ ) приводит к сбою метода из-за сингулярности задачи наименьших квадратов. Аналогично, почти стагнация ( $x_{k+1}\approx x_{k}$ ) приводит к плохой обусловленности задачи наименьших квадратов. При этом выбор параметра $m$ может иметь значение при определении условия задачи наименьших квадратов, как обсуждается ниже . ^[3]

Релаксация

Алгоритм можно модифицировать, вводя переменный параметр релаксации (или параметр смешивания). $\beta _{k}>0$ . ^[1]^[3]^[4] На каждом шаге вычисляйте новую итерацию как $x_{k+1}=(1-\beta _{k})\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}x_{k-m_{k}+i}+\beta _{k}\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f(x_{k-m_{k}+i})\;.$ Выбор $\beta _{k}$ имеет решающее значение для свойств сходимости метода; в принципе, $\beta _{k}$ может меняться на каждой итерации, хотя часто его выбирают постоянным. ^[4]

Выбор $м.$

Параметр $m$ определяет, сколько информации из предыдущих итераций используется для вычисления новой итерации $x_{k+1}$ . С одной стороны, если $m$ выбирается слишком маленьким, используется слишком мало информации, и сходимость может быть нежелательно медленной. С другой стороны, если $m$ слишком велика, информация из старых итераций может сохраняться для слишком многих последующих итераций, так что сходимость снова может быть медленной. ^[3] Более того, выбор $m$ влияет на размер задачи оптимизации. Слишком большое значение $m$ может ухудшить условия задачи наименьших квадратов и стоимость ее решения. ^[3] В общем, конкретная проблема, которую необходимо решить, определяет лучший выбор $m$ параметр. ^[3]

Выбор $мк$ _$$

Применительно к описанному выше алгоритму выбор $m_{k}$ на каждой итерации могут быть изменены. Одна из возможностей – выбрать $m_{k}=k$ за каждую итерацию $k$ (иногда называемое ускорением Андерсона без усечения). ^[3] Таким образом, каждая новая итерация $x_{k+1}$ вычисляется с использованием всех ранее вычисленных итераций. Более сложный метод основан на выборе $m_{k}$ так, чтобы поддерживать достаточно малую обусловленность для задачи наименьших квадратов. ^[3]

Отношения с другими классами методов

Метод Ньютона можно применить для решения задачи $f(x)-x=0$ вычислить фиксированную точку $f(x)$ с квадратичной сходимостью. Однако такой метод требует оценки точной производной $f(x)$ , что может стоить очень дорого. ^[4] аппроксимация производной с помощью конечных разностей , но она требует многократного вычисления Возможная альтернатива — $f(x)$ на каждой итерации, что опять же может оказаться очень дорогостоящим. Ускорение Андерсона требует только одной оценки функции $f(x)$ на итерацию и без оценки ее производной. С другой стороны, сходимость ускоренной Андерсоном последовательности фиксированных точек в целом по-прежнему линейна. ^[5]

Некоторые авторы указали на сходство схемы ускорения Андерсона с другими методами решения нелинейных уравнений. В частности:

Эйерт ^[6] и Фанг и Саад ^[4] интерпретировал алгоритм в классе квазиньютоновских методов и методов мультисекущих, обобщающих известный метод секущих , для решения нелинейного уравнения $g(x)=0$ ; они также показали, как схему можно рассматривать как метод класса Бройдена ; ^[7]
Уокер и Ни ^[3]^[8] показал, что схема ускорения Андерсона эквивалентна методу GMRES в случае линейных задач (т.е. задачи поиска решения задачи $A\mathbf {x} =\mathbf {x}$ для некоторой квадратной матрицы $A$ ), и, таким образом, его можно рассматривать как обобщение GMRES на нелинейный случай; аналогичный результат был получен Вашио и Остерли. ^[9]

Более того, несколько эквивалентных или почти эквивалентных методов были независимо разработаны другими авторами. ^[9]^[10]^[11]^[12]^[13] хотя чаще всего в контексте какого-то конкретного интересующего приложения, а не как общий метод для уравнений с фиксированной точкой.

Пример реализации MATLAB

Ниже приведен пример реализации на языке MATLAB схемы ускорения Андерсона для поиска фиксированной точки функции. $f(x)=\sin(x)+\arctan(x)$ . Обратите внимание:

задача оптимизации решалась в виде $\gamma _{k}=\operatorname {argmin} _{\gamma \in \mathbb {R} ^{m_{k}}}\|g_{k}-{\mathcal {G}}_{k}\gamma \|_{2}$ использование QR-разложения;
вычисление QR-разложения неоптимально: действительно, на каждой итерации к матрице добавляется один столбец ${\mathcal {G}}_{k}$ , и, возможно, будет удален один столбец; этот факт можно использовать для эффективного обновления QR-разложения с меньшими вычислительными затратами; ^[14]
алгоритм можно сделать более эффективным с точки зрения использования памяти, сохраняя только несколько последних итераций и остатков, если весь вектор итераций $x_{k}$ не нужен;
код непосредственно обобщается на случай векторного числа $f(x)$ .

f = @(x) sin(x) + atan(x); % Function whose fixed point is to be computed.x0 = 1; % Initial guess.k_max = 100; % Maximum number of iterations.tol_res = 1e-6; % Tolerance on the residual.m = 3; % Parameter m.x = [x0, f(x0)]; % Vector of iterates x.g = f(x) - x; % Vector of residuals.G_k = g(2) - g(1); % Matrix of increments in residuals.X_k = x(2) - x(1); % Matrix of increments in x.k = 2;while k < k_max && abs(g(k)) > tol_res    m_k = min(k, m);     % Solve the optimization problem by QR decomposition.    [Q, R] = qr(G_k);    gamma_k = R \ (Q' * g(k));     % Compute new iterate and new residual.    x(k + 1) = x(k) + g(k) - (X_k + G_k) * gamma_k;    g(k + 1) = f(x(k + 1)) - x(k + 1);     % Update increment matrices with new elements.    X_k = [X_k, x(k + 1) - x(k)];    G_k = [G_k, g(k + 1) - g(k)];     n = size(X_k, 2);    if n > m_k        X_k = X_k(:, n - m_k + 1:end);        G_k = G_k(:, n - m_k + 1:end);    end     k = k + 1;end% Prints result: Computed fixed point 2.013444 after 9 iterationsfprintf("Computed fixed point %f after %d iterations\n", x(end), k);

См. также

Примечания

^ Эта формулировка отличается от той, которую дал первоначальный автор; ^[1] это эквивалентная, более явная формулировка, данная Уокером и Ни. ^[3]

Ссылки

^ Jump up to: ^а ^б ^с ^д Андерсон, Дональд Г. (октябрь 1965 г.). «Итерационные процедуры для нелинейных интегральных уравнений» . Журнал АКМ . 12 (4): 547–560. дои : 10.1145/321296.321305 .
^ Jump up to: ^а ^б ^с ^д Квартерони, Альфио ; Сакко, Риккардо; Салери, Фаусто. Численная математика (2-е изд.). Спрингер. ISBN 978-3-540-49809-4 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Уокер, Гомер Ф.; Ни, Пэн (январь 2011 г.). «Ускорение Андерсона для итераций с фиксированной точкой». SIAM Journal по численному анализу . 49 (4): 1715–1735. CiteSeerX 10.1.1.722.2636 . дои : 10.1137/10078356X .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Фанг, Хорен; Саад, Юсеф (март 2009 г.). «Два класса многосекущих методов нелинейного ускорения». Численная линейная алгебра с приложениями . 16 (3): 197–221. дои : 10.1002/nla.617 .
^ Эванс, Клэр; Поллок, Сара; Ребхольц, Лео Г.; Сяо, Мэнъин (20 февраля 2020 г.). «Доказательство того, что ускорение Андерсона улучшает скорость сходимости в линейно сходящихся методах фиксированной точки (но не в тех, которые сходятся квадратично)». SIAM Journal по численному анализу . 58 (1): 788–810. arXiv : 1810.08455 . дои : 10.1137/19M1245384 .
^ Эйерт, В. (март 1996 г.). «Сравнительное исследование методов ускорения сходимости итеративных векторных последовательностей». Журнал вычислительной физики . 124 (2): 271–285. дои : 10.1006/jcph.1996.0059 .
^ Бройден, CG (1965). «Класс методов решения нелинейных одновременных уравнений» . Математика вычислений . 19 (92): 577–577. дои : 10.1090/S0025-5718-1965-0198670-6 .
^ Ни, Пэн (ноябрь 2009 г.). Андерсон Ускорение итерации с фиксированной точкой с применением к расчетам электронных структур (доктор философии).
^ Jump up to: ^а ^б Остерли, CW; Васио, Т. (январь 2000 г.). «Ускорение нелинейных многосеточных нелинейных подпространств Крылова с применением к рециркуляционным потокам». Журнал SIAM по научным вычислениям . 21 (5): 1670–1690. дои : 10.1137/S1064827598338093 .
^ Пулай, Петер (июль 1980 г.). «Ускорение сходимости итерационных последовательностей. Случай scf-итерации». Письма по химической физике . 73 (2): 393–398. дои : 10.1016/0009-2614(80)80396-4 .
^ Пулай, П. (1982). «Улучшено ускорение сходимости SCF». Журнал вычислительной химии . 3 (4): 556–560. дои : 10.1002/jcc.540030413 .
^ Карлсон, Нил Н.; Миллер, Кейт (май 1998 г.). «Разработка и применение градиентно-взвешенного кода конечных элементов I: в одном измерении». Журнал SIAM по научным вычислениям . 19 (3): 728–765. дои : 10.1137/S106482759426955X .
^ Миллер, Кейт (ноябрь 2005 г.). «Нелинейный Крылов и подвижные узлы в методе прямых». Журнал вычислительной и прикладной математики . 183 (2): 275–287. дои : 10.1016/j.cam.2004.12.032 .
^ Дэниел, JW; Грэгг, Всемирный банк; Кауфман, Л.; Стюарт, GW (октябрь 1976 г.). «Реортогонализация и устойчивые алгоритмы обновления $QR$-факторизации Грама-Шмидта» . Математика вычислений . 30 (136): 772–772. дои : 10.1090/S0025-5718-1976-0431641-8 .

[4] Эта формулировка отличается от той, которую дал первоначальный автор; ^[1] это эквивалентная, более явная формулировка, данная Уокером и Ни. ^[3]

[Anderson1965-1] Jump up to: ^а ^б ^с ^д Андерсон, Дональд Г. (октябрь 1965 г.). «Итерационные процедуры для нелинейных интегральных уравнений» . Журнал АКМ . 12 (4): 547–560. дои : 10.1145/321296.321305 .

[Quarteroni-Sacco-2] Jump up to: ^а ^б ^с ^д Квартерони, Альфио ; Сакко, Риккардо; Салери, Фаусто. Численная математика (2-е изд.). Спрингер. ISBN 978-3-540-49809-4 .

[Walker2011-3] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Уокер, Гомер Ф.; Ни, Пэн (январь 2011 г.). «Ускорение Андерсона для итераций с фиксированной точкой». SIAM Journal по численному анализу . 49 (4): 1715–1735. CiteSeerX 10.1.1.722.2636 . дои : 10.1137/10078356X .

[Fang2009-5] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Фанг, Хорен; Саад, Юсеф (март 2009 г.). «Два класса многосекущих методов нелинейного ускорения». Численная линейная алгебра с приложениями . 16 (3): 197–221. дои : 10.1002/nla.617 .

[Evans2020-6] Эванс, Клэр; Поллок, Сара; Ребхольц, Лео Г.; Сяо, Мэнъин (20 февраля 2020 г.). «Доказательство того, что ускорение Андерсона улучшает скорость сходимости в линейно сходящихся методах фиксированной точки (но не в тех, которые сходятся квадратично)». SIAM Journal по численному анализу . 58 (1): 788–810. arXiv : 1810.08455 . дои : 10.1137/19M1245384 .

[7] Эйерт, В. (март 1996 г.). «Сравнительное исследование методов ускорения сходимости итеративных векторных последовательностей». Журнал вычислительной физики . 124 (2): 271–285. дои : 10.1006/jcph.1996.0059 .

[Broyden1965-8] Бройден, CG (1965). «Класс методов решения нелинейных одновременных уравнений» . Математика вычислений . 19 (92): 577–577. дои : 10.1090/S0025-5718-1965-0198670-6 .

[Ni2009-9] Ни, Пэн (ноябрь 2009 г.). Андерсон Ускорение итерации с фиксированной точкой с применением к расчетам электронных структур (доктор философии).

[Washio1997-10] Jump up to: ^а ^б Остерли, CW; Васио, Т. (январь 2000 г.). «Ускорение нелинейных многосеточных нелинейных подпространств Крылова с применением к рециркуляционным потокам». Журнал SIAM по научным вычислениям . 21 (5): 1670–1690. дои : 10.1137/S1064827598338093 .

[Pulay1980-11] Пулай, Петер (июль 1980 г.). «Ускорение сходимости итерационных последовательностей. Случай scf-итерации». Письма по химической физике . 73 (2): 393–398. дои : 10.1016/0009-2614(80)80396-4 .

[12] Пулай, П. (1982). «Улучшено ускорение сходимости SCF». Журнал вычислительной химии . 3 (4): 556–560. дои : 10.1002/jcc.540030413 .

[Carlson1998-13] Карлсон, Нил Н.; Миллер, Кейт (май 1998 г.). «Разработка и применение градиентно-взвешенного кода конечных элементов I: в одном измерении». Журнал SIAM по научным вычислениям . 19 (3): 728–765. дои : 10.1137/S106482759426955X .

[Miller2005-14] Миллер, Кейт (ноябрь 2005 г.). «Нелинейный Крылов и подвижные узлы в методе прямых». Журнал вычислительной и прикладной математики . 183 (2): 275–287. дои : 10.1016/j.cam.2004.12.032 .

[15] Дэниел, JW; Грэгг, Всемирный банк; Кауфман, Л.; Стюарт, GW (октябрь 1976 г.). «Реортогонализация и устойчивые алгоритмы обновления $QR$-факторизации Грама-Шмидта» . Математика вычислений . 30 (136): 772–772. дои : 10.1090/S0025-5718-1976-0431641-8 .

[1]

[2]

[3]

[примечание 1]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]