在数学中，函数的不动点（Fixed point, or shortened to fixpoint, also knowns as invariant point)，指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身。在科学和工程领域中，很多问题可以归结为不动点问题，如下：

x = G(x)\cdots\cdots\cdots\cdots\cdots\cdots \cdots \cdots (1)   

这里x\in \mathbb{C}^{n} 和 G: \mathbb{C}^{n}\rightarrow \mathbb{C}^{n} 是一个映射(\mathbb{C}是复数空间)。 (1)可以使用不动点迭代方法求解，如下

\textup{\textbf{Fixed-point iteration}}\\ \indent\textup{Given an initial guess}~x_0\\ \indent \text{for~k=0,1,2,}\cdots\\ \indent\indent\text{Set} ~x_{k+1}=G(x_{k})\cdots\cdots\cdots\cdots(2)\\ \indent \text{end}

此迭代格式若收敛，需要满足一定的收敛条件。在收敛性满足条件下，为了加速不动点跌倒的收敛速度，最初的想法是在迭代格式（2）后引入一个松弛迭代，进行外推加速。如下：

\left\{\begin{matrix} x^{*}_{k+1}=G(x_k)\\ x_{k+1}=\omega x^{*}_{k+1}+(1-\omega)x_k \end{matrix}\right.

这里\omega(一般选为实数，也可以是一个复数)是一个松弛因子。最终的迭代格式等价于 x_{k+1}=\omega G(x_k)+(1-\omega)x_k。借鉴这个思想，求解不动点问题(1)的安德森加速方法如下：

\noindent\textbf{Anderson~Acceleration(AA)~method}\\ \indent\textup{Given an initinal guess} ~x_{0}~ \textup{and} ~m\geqslant 1}\\ \indent\textup{Set}~x_1=G(x_0)\\ \indent \textup{for}~k=1,2,3\cdots\\ \indent\indent \textup{Set}~m_k=\min(m,k).\\ \indent\indent F_k=(f_{k-m_k},\cdots\cdots,f_k), where ~ f_i=G(x_i)-x_i.\\ \indent\indent Determine~\alpha^{(k)}=(\alpha^{(k)}_{0},\cdots\cdots,\alpha^{(k)}_{m_{k}})^T~that~solves\\ \indent\indent\indent \displaystyle\min_{\alpha=(\alpha_0,\cdots\cdots,\alpha_{mk})^T}}\|F_k\alpha\|_2~s.t.~ \sum^{m_k}_{i=0}\alpha_i=1.\\ \indent\indent\textup{Set}~x_{k+1}=\sum^{m_k}_{i=0}\alpha^{(k)}_{i}G(x_{k-m_k+i})\\ \indent \textup{end}

更一般地，可以将 x_{k+1} 表示如下：

x_{k+1}=(1-\beta_k)\sum^{m_k}_{i=0}\alpha^{(k)}_{i}x_{k-m_k+i}+\beta_k\sum^{m_k}_{i=0}\alpha^{(k)}_{i}G(x_{k-m_k+i})

这里 \beta_k是一个松弛参数。安德森加速的伪代码如下(形式和前面叙述一致，这里为了自己理解)：

安德森方法的一些小注记：(1)、安德森加速方法中一定要满足加权系数的和为一。(2)、对于加权系数可以使用最小二乘法求解。

参考文献：

（1）Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003

（2）Homer F. Walker and Peng Ni Anderson acceleration for fixed-point iterations   SIAM J. Numer. Anal., 49(4), 1715–1735

（3）Alex Toth and C. T. Kelley Convergence analysis for Anderson acceleration  SIAM J. Numer. Anal., 53(2), 805–819.

Remark:此为本人的一点笔记，不尽完善，欢迎讨论。

Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

cover

人工智能在库存管理中的应用

avatar 开放原子开发者工作坊

dubbo启动报错failed to bind nettyserver on

dubbo报错今天启动项目的时候，关掉了custom服务，<dubbo:consumer check="false"/>并且关掉了spring的elastic-job，<!--<import resource="cloud-elastic-job.xml"/>-->但是还是报错，看了下错误代码，原因是因...

avatar 开放原子开发者工作坊
cover

【Windows】redis安装

avatar 开放原子开发者工作坊