疊代計算

疊代特性

在計算機科學中，疊代是程式中對一組指令（或一定步驟）的重複。它既可以被用作通用的術語（與“重複”同義），也可以用來描述一種特定形式的具有可變狀態的重複。

在第一種意義下，遞歸是疊代的一個例子，但是通常使用一種遞歸式的表達。比如用0!=1，n!=n*(n-1)!來表示階乘。而疊代通常不是這樣寫的。

而在第二種（更嚴格的）意義下，疊代描述了在指令式程式語言中使用的編程風格。與之形成對比的是遞歸，它更偏向於聲明式的風格。

終止準則

由於數值疊代是逐步逼近最優點而獲得近似解的，它無限地接近於最優點卻又不是理論上的最優點，所以就需要考慮在什麼樣的條件下才終止疊代，獲得一個足夠精度的近似極小點，這一條件就是疊代計算的終止準則。

對最最佳化問題常用的疊代過程終止準則一般有以下幾種。

(1) 點距準則

當相鄰兩疊代點X^(k)、X^(k+1)之間的距離已達到充分小時，即小於或等於規定的某一很小正數ε時，疊代終止。一般用兩個疊代點向量差的模來表示，即

或用X^(k)、X^(k+1)在各坐標軸上的分量來表示，即

(2)函式下降量準則

當相鄰兩疊代點X^(k)、X^(k+1)的目標函式值的下降量已達到充分小時，疊代終止。一般用目標函式值下降量的絕對值來表示，即

或用目標函式值下降量的相對值來表示，即

(3)梯度準則

當目標函式在疊代點的梯度已達到充分小時，疊代終止。一般用梯度向量的模來表示，即

以上各式中的ε是根據設計要求預先給定的疊代精度。

在最佳化設計中，一般只要滿足以上終止準則之一，則可認為設計點收斂於極值點。應該指出，有時為了防止當函式變化劇烈時，點距準則雖已滿足，求得的最優值f(X^(k+1))與真正的最優值f(x*)仍相差較大；或當函式變化緩慢時，目標函式值下降量準則雖已得到滿足，但所求得的最優點X^(k+1)與真正的最優點X*仍相距較遠，往往將前兩種終止準則結合起來使用，要求同時成立。至於梯度準則，僅用於需要計算目標函式梯度的最最佳化方法中。