迭代法

　　一類利用遞推公式或迴圈演算法構造序列求問題近似解的方法。例如利用關係式

，從 x ₀開始依次計算 x _1<， x ₂，…來逼近方程 x＝ f( x)的根 x 的方法和由關系式 近似求解線性代數方程 Ax= b的方法都是迭代法。一般，利用遞推關系式　　

，

構造序列{x _k}逼近所論問題解x 的方法稱為迭代法， Ψ _k稱為迭代算子或迭代函數，｛x _k｝為迭代序列。若x _k存在極限 ，則稱迭代序列收斂。若存在1≤ p＜ 以及正的常數C _p使

則稱迭代序列對於 x 具有 p階收斂速度或者說是 p階收斂的。如果對所有由迭代函數 Ψ _k產生的收斂於 x 的迭代序列｛ x _k｝，上式均成立，則稱此迭代法對於 x 是 p階收斂的。

　　對確定的正整數m，迭代算法

稱為 m步迭代法，當 m=1，稱為單步迭代法或逐步逼近法，它是最常用的迭代算法。用 m步迭代法計算時，需給定 m個初始近似x ₀，x _-1，…， x _{- m +1}。若 Ψ _k與 k無關，稱之為定常迭代法。所有定常迭代法均可化成這種形式。當單步定常迭代法 收斂於x 時，則x 為方程組x＝ Ψ(x)的解。

　　迭代法研究的主要課題是對所論問題構造收斂的迭代算法，分析它們的收斂速度及收斂范圍。迭代法的收斂性定理可分成下列三類：①局部收斂性定理：假定問題解存在，斷定當初始近似與解充分接近時迭代法收斂；②半局部收斂性定理：在不假定解存在的情況下，根據迭代法在初始近似處滿足的條件，斷定迭代法收斂於問題的解；③大范圍收斂性定理：在不假定初始近似與解充分接近的條件下，斷定迭代法收斂於問題的解。

　　對於單步定常迭代法有以下基本收斂性定理：

　　定理1　設在解x

的鄰域內， Ψ(x)連續可微， Ψ( x )的譜半徑小於1，則當初始近似x ₀與x 充分接近時，單步定常迭代法對於x 收斂。

　　定理2　設於區域S={x|‖x-x₀‖≤r}內Ψ(x)滿足條件：‖Ψ(x)-Ψ（у）‖≤q‖x-у‖，∀x，у∈S，且‖x₀-Ψ(x₀)‖≤(1-q)r，其中0＜q＜1，則x=Ψ（x）在S中存在惟一解x

，單步定常迭代法對於x 收斂，並有估計式

　　迭代法在線性和非線性方程組求解、最優化計算以及特征值計算等問題中廣泛應用。