跳转到内容

迭代法

本页使用了标题或全文手工转换
维基百科,自由的百科全书

迭代法(英语: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. 

外部链接

[编辑]