迭代法

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

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

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

吸引不动点

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

线性系统

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

定常迭代法

简介

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

定义

迭代法可定义为

$\mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0$

针对特定的线性系统$A\mathbf {x} =\mathbf {b}$以及真实解$\mathbf {x} ^{*}$，误差为

$\mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.$

迭代法称为线性，若存在以下矩阵$C\in \mathbb {R} ^{n\times n}$使得

$\mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0$

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

$\lim _{k\rightarrow \infty }C^{k}=0\,.$

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

$\rho (C)<1\,.$

基础的迭代法作用原理是将矩阵$A$分割成

$A=M-N$

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

$M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.$

依此，迭代矩阵为

$C=I-M^{-1}A=M^{-1}N\,.$

范例

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

$A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})$

其中$D$是$A$的对角线部分，$L$是$A$的严格下三角矩阵，而$U$是$A$的严格上三角矩阵。

• 理察森法：$M:={\frac {1}{\omega }}I\quad (\omega \neq 0)$
• 雅可比法：$M:=D$
• 阻尼雅可比法：$M:={\frac {1}{\omega }}D\quad (\omega \neq 0)$
• 高斯-赛德尔迭代: $M:=D+L$
• 逐次超松弛迭代法（SOR）：$M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)$
• 对称逐次超松弛迭代法 (SSOR): $M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})$

线性定常迭代法也称为松弛迭代法。

克雷洛夫子空间法

主条目：克雷洛夫子空间

克雷洛夫子空间法（Krylov subspace method）的作法是初始余量在A的前N次幂下（始于$A^{0}=I$）的列空间张成的线性子空间。 近似解可以用在形成的数列上使余量为最小值来求得。 克雷洛夫子空间法的原形方法是共轭梯度法（CG），其中假设系统矩阵$A$是对称正定。 针对对称矩阵（也可能包括半正定矩阵）$A$，可以用最小余量法（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年代才了解此方法应用在偏微分方程上的效果也很好，特别是在椭圆型偏微分方程。

参见

• 解析解
• 迭代
• 迭代函数
• 逼近
• 数值分析
• 非线性最小二乘法
• 求根算法

外部链接

• Templates for the Solution of Linear Systems
• Y. Saad: Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996