迭代法(英语:Iterative Method),在计算数学中,迭代是通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的数学过程,为实现这一过程所使用的算法统称,每一次找到的近似解都会用来求得下一个近似解。

迭代法有许多种实现的方式,也有各自的迭代终止条件。常见的迭代法是梯度下降法爬山算法牛顿法,也有些属于拟牛顿法(例如BFGS算法)。迭代法收敛是指在给定的近似初值下,对应的近似解数列收敛。一般会针对迭代法算法进行数学上严谨的收敛分析。不过也常常看到启发式的迭代法。

迭代法相对应的是直接法,设法用有限的步骤来找到解。若不考虑舍入误差的话,直接法有可能得到正确答案(例如用高斯消元法求解线性系统时)。若是非线性方程,只能使用迭代法。不过,就竹是线性系统,若是有许多的变量时(例如上百万个),即使用目前最好的电脑,使用直接法的成本太高(而且有些情形下是不可行的),此时也可以用迭代法来计算[1]

吸引不动点

若方程式可以写成f(x) = x的形式,且有一个解x是函数f的吸引不动点,则可以从x吸引盆地中的一个点x1开始,令xn+1 = f(xn),n ≥ 1,则数列{xn}n ≥ 1会收敛在解x。此处xnxn次迭代或是近似的值,而xn+1则是下一次迭代或是近似的值。在数值方法中,常会用有括号的上标表示迭代次数,加上括号的目的是不会和其他上标的意义弄混(例如,x(n+1) = f(x(n)))。若函数f连续可微,其收敛的充份条件是在不动点的附近,其导数的谱半径严格小于1。若在不动点处满足此条件,必定在不动点附近存在够小的邻区(吸引盆地)。

线性系统

求解线性方程组的迭代方法主要分为两类,分别是定常迭代法和克雷洛夫子空间法。

定常迭代法

简介

定常迭代法(Stationary iterative methods)用近似原始算子的算子来求解线性系统,基于对结果误差的量测(余量英语Residual (numerical analysis)),形成了修正方程,并且重复此一步骤。此方法很容易推导、实现及分析,但只针对特定矩阵才能确保其收敛。

定义

迭代法可定义为

 

针对特定的线性系统 以及真实解 ,误差为

 

迭代法称为线性,若存在以下矩阵 使得

 

此一矩阵称为迭代矩阵。 有特定迭代矩阵 的迭代法是收敛的,若下式成立

 

有一个重要的定理,提到有特定迭代矩阵 的迭代法,其收敛的条件当且仅当其谱半径小于1,也就是

 

基础的迭代法作用原理是将矩阵 分割英语Matrix splitting

 

且此处的矩阵 需要是很容易取逆矩阵的。 因此,迭代法定义为

 

依此,迭代矩阵为

 

范例

有些基础的定常迭代法,会将矩阵 以以下方式分割

 

其中  的对角线部分,  的严格下三角矩阵,而  的严格上三角矩阵。

线性定常迭代法也称为松弛迭代法英语Relaxation (iterative method)

克雷洛夫子空间法

克雷洛夫子空间法(Krylov subspace method)的作法是初始余量在A的前N次幂下(始于 )的列空间张成线性子空间。 近似解可以用在形成的数列上使余量为最小值来求得。 克雷洛夫子空间法的原形方法是共轭梯度法(CG),其中假设系统矩阵 对称正定。 针对对称矩阵(也可能包括半正定矩阵) ,可以用最小余量法英语Minimal residual method(MINRES)。 若是非对称矩阵,可以用广义最小余量法英语generalized minimal residual method(GMRES)及双共轭梯度法英语biconjugate gradient method(BiCG)。

克雷洛夫子空间法的收敛

因为这些方法会形成基,可以可知此方法会在N次迭代后收敛,其中N是系统大小。不过若是考虑舍入误差,上述的论点就不成立,而且,实务上的N可以非常的大,迭代过程在到达N次之前,已达到所需的精。这类方法的分析很困难,视算子的谱函数之复杂程度而定。

预处理子

出现在定常迭代法的近似算子也可以整合到像是广义最小残量方法(GMRES)的克雷洛夫子空间法里(预处理英语preconditioning的克雷洛夫子空间法,也可以视为是定常迭代法的加速),会将原始的运算子变换为大概条件更好的运算子。预处理子(preconditioner)的建构是很大的研究领域。

历史

13世纪的伊朗数学家卡西曾用迭代法,在《The Treatise of Chord and Sine》中计算sine 1°以及π到很高的精度。 在卡尔·弗里德里希·高斯给学生的一封信中有用迭代法求解线性系统,其中求解一个四变量的系统,其作法是反复的解出余量最大的那个变量[来源请求]

定常迭代法在杨大卫英语D.M. Young在1950年代开始的研究中有稳固的基础。共轭梯度法也是在1950年代开始的,由Cornelius Lanczos英语Cornelius LanczosMagnus Hestenes英语Magnus HestenesEduard Stiefel英语Eduard Stiefel分别独立的发现,但当时对其本质以及应用都还有误解。数学家要到1970年代才了解此方法应用在偏微分方程上的效果也很好,特别是在椭圆型偏微分方程。

参见

参考资料

  1. ^ Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil. Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver. Journal of Computational Physics. 2015, 303: 222. Bibcode:2015JCoPh.303..222A. arXiv:1501.03358 . doi:10.1016/j.jcp.2015.09.040. 

外部链接