迭代法
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
迭代法(英语:Iterative Method),在计算数学中,迭代是通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的数学过程,为实现这一过程所使用的算法统称,每一次找到的近似解都会用来求得下一个近似解。
迭代法有许多种实现的方式,也有各自的迭代终止条件。常见的迭代法是梯度下降法、爬山算法、牛顿法,也有些属于拟牛顿法(例如BFGS算法)。迭代法收敛是指在给定的近似初值下,对应的近似解数列收敛。一般会针对迭代法算法进行数学上严谨的收敛分析。不过也常常看到启发式的迭代法。
迭代法相对应的是直接法,设法用有限的步骤来找到解。若不考虑舍入误差的话,直接法有可能得到正确答案(例如用高斯消元法求解线性系统时)。若是非线性方程,只能使用迭代法。不过,就竹是线性系统,若是有许多的变量时(例如上百万个),即使用目前最好的电脑,使用直接法的成本太高(而且有些情形下是不可行的),此时也可以用迭代法来计算[1]。
吸引不动点
[编辑]若方程式可以写成f(x) = x的形式,且有一个解x是函数f的吸引不动点,则可以从x的吸引盆地中的一个点x1开始,令xn+1 = f(xn),n ≥ 1,则数列{xn}n ≥ 1会收敛在解x。此处xn是x第n次迭代或是近似的值,而xn+1则是下一次迭代或是近似的值。在数值方法中,常会用有括号的上标表示迭代次数,加上括号的目的是不会和其他上标的意义弄混(例如,x(n+1) = f(x(n)))。若函数f是连续可微,其收敛的充份条件是在不动点的附近,其导数的谱半径严格小于1。若在不动点处满足此条件,必定在不动点附近存在够小的邻区(吸引盆地)。
线性系统
[编辑]求解线性方程组的迭代方法主要分为两类,分别是定常迭代法和克雷洛夫子空间法。
定常迭代法
[编辑]简介
[编辑]定常迭代法(Stationary iterative methods)用近似原始算子的算子来求解线性系统,基于对结果误差的量测(余量),形成了修正方程,并且重复此一步骤。此方法很容易推导、实现及分析,但只针对特定矩阵才能确保其收敛。
定义
[编辑]迭代法可定义为
针对特定的线性系统以及真实解,误差为
迭代法称为线性,若存在以下矩阵使得
此一矩阵称为迭代矩阵。 有特定迭代矩阵的迭代法是收敛的,若下式成立
有一个重要的定理,提到有特定迭代矩阵的迭代法,其收敛的条件当且仅当其谱半径小于1,也就是
基础的迭代法作用原理是将矩阵分割成
且此处的矩阵需要是很容易取逆矩阵的。 因此,迭代法定义为
依此,迭代矩阵为
范例
[编辑]有些基础的定常迭代法,会将矩阵以以下方式分割
其中是的对角线部分,是的严格下三角矩阵,而是的严格上三角矩阵。
线性定常迭代法也称为松弛迭代法。
克雷洛夫子空间法
[编辑]克雷洛夫子空间法(Krylov subspace method)的作法是初始余量在A的前N次幂下(始于)的列空间张成的线性子空间。 近似解可以用在形成的数列上使余量为最小值来求得。 克雷洛夫子空间法的原形方法是共轭梯度法(CG),其中假设系统矩阵是对称正定。 针对对称矩阵(也可能包括半正定矩阵),可以用最小余量法(MINRES)。 若是非对称矩阵,可以用广义最小余量法(GMRES)及双共轭梯度法(BiCG)。
克雷洛夫子空间法的收敛
[编辑]因为这些方法会形成基,可以可知此方法会在N次迭代后收敛,其中N是系统大小。不过若是考虑舍入误差,上述的论点就不成立,而且,实务上的N可以非常的大,迭代过程在到达N次之前,已达到所需的精。这类方法的分析很困难,视算子的谱函数之复杂程度而定。
预处理子
[编辑]出现在定常迭代法的近似算子也可以整合到像是广义最小残量方法(GMRES)的克雷洛夫子空间法里(预处理的克雷洛夫子空间法,也可以视为是定常迭代法的加速),会将原始的运算子变换为大概条件更好的运算子。预处理子(preconditioner)的建构是很大的研究领域。
历史
[编辑]13世纪的伊朗数学家卡西曾用迭代法,在《The Treatise of Chord and Sine》中计算sine 1°以及π到很高的精度。 在卡尔·弗里德里希·高斯给学生的一封信中有用迭代法求解线性系统,其中求解一个四变量的系统,其作法是反复的解出余量最大的那个变量[来源请求]。
定常迭代法在杨大卫在1950年代开始的研究中有稳固的基础。共轭梯度法也是在1950年代开始的,由Cornelius Lanczos、Magnus Hestenes及Eduard Stiefel分别独立的发现,但当时对其本质以及应用都还有误解。数学家要到1970年代才了解此方法应用在偏微分方程上的效果也很好,特别是在椭圆型偏微分方程。
参见
[编辑]参考资料
[编辑]- ^ 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.
外部链接
[编辑]- Templates for the Solution of Linear Systems
- Y. Saad: Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996
|
|