常用算法設計方法
常用算法設計方法
一、迭代法
迭代法是用於求方程或方程組近似根的一種常用的算法設計方法。設方程為f(x)=0,用某種數學方法匯出等價的形式x=g(x),然後按以下步驟執行:
(1) 選一個方程的近似根,賦給變數x0;
(2) 將x0的值儲存於變數x1,然後計算g(x1),並將結果存於變數x0;
(3) 當x0與x1的差的絕對值還小於指定的精度要求時,重複步驟(2)的計算。
若方程有根,並且用上述方法計算出來的近似根序列收斂,則按上述方法求得的x0就認為是方程的根。上述算法用C程序的形式表示為:
【算法】迭代法求方程的根
{ x0=初始近似根;
do {
x1=x0;
x0=g(x1); /*按特定的方程計算新的近似根*/
} while ( fabs(x0-x1)>Epsilon);
printf(「方程的近似根是%f\n」,x0);
}
迭代算法也常用於求方程組的根,令
X=(x0,x1,…,xn-1)
設方程組為:
xi=gi(X) (I=0,1,…,n-1)
則求方程組根的迭代算法可描述如下:
【算法】迭代法求方程組的根
{ for (i=0;i<n;i++)
x=初始近似根;
do {
for (i=0;i<n;i++)
y=x;
for (i=0;i<n;i++)
x=gi(X);
for (delta=0.0,i=0;i<n;i++)
if (fabs(y-x)>delta) delta=fabs(y-x);
} while (delta>Epsilon);
for (i=0;i<n;i++)
printf(「變數x[%d]的近似根是 %f」,I,x);
printf(「\n」);
}
具體使用迭代法求根時應注意以下兩種可能發生的情況:
(1) 如果方程無解,算法求出的近似根序列就不會收斂,迭代程序會變成死循環,因此在使用迭代算法前應先考察方程是否有解,並在程序中對迭代的次數給予限制;
(2) 方程雖然有解,但迭代公式選項不當,或迭代的初始近似根選項不合理,也會導致迭代失敗
|