Edison.X. Blog

[回目錄]

圖形與說明

艾肯疊代法乃為了加速定點法之收斂所使用，求解過程甚為複雜，此處不做深入探討，

但必須要提出一些對於「艾肯疊代法」的謠言

謠言 1 : 不存在不收斂問題 - 還是要看 g(x) 有沒有挑對。

謠言 2 : 必使得不收斂變收斂 - 要看實際 g(x) 情形。

筆者也不打算以證明破這二個謠言，證明實在是太長，但予以肯定的是，

若收斂時，艾肯疊代法確實收斂速度比單純之定點回路快些。

目前在做艾肯疊代時，對於迭代函式、變數取代，

實作方式不盡相同，筆者提出目前所見過之三種迭代與取代模式，

「普遍性」而言，效果最好的是 Ver3

三段虛擬碼

Algorithm Aitken-Ver1

    E0 : f(x)=0 化為 g(x) = x，初始化最小誤差 EPS，初始點 xo

    E1 :  x1 = g(x0), x2=g(x1)

    E2 :  x = (x0 * x2 - x1*x1)  / (x2 - 2*x1 +x0)

    E3 :  x0 = gx(x) , delta = abs(x-x0) 

    E4 :  if delta < eps 成立，演算法結束，傳回 x0

    E5 :  goto E1

End Algorithm

Algorithm Aitken-Ver2

    E0 : f(x)=0 化為 g(x) = x，初始化最小誤差 EPS，初始點 xo

    E1 :  x1 = g(x0), x2=g(x1) , delta = abs(x1-x2)

    E2 :  if delta < eps 成立，演算法結束，傳回 x2  

    E3 :  x = x2 - delta * delta / (x2 - 2*x1 + x0)

    E4 : x0 = x 

    E5 :  goto E1

End Algorithm

Algorithm Aitken-Ver3

    E0 : f(x)=0 化為 g(x) = x，初始化最小誤差 EPS，初始點 xo

    E1 :  x1 = g(x0), x2=g(x1) , delta = abs(x1-x2)

    E2 :  if delta < eps 成立，演算法結束，傳回 x2 

    E3 :  x = x2 - delta * delta / (x2 - 2*x1 + x0)

    E4 : x0 = g(x)

    E5 :  goto E1

End Algorithm

上面這三種都有人在用，且妙的是，針對同一函式、同一初始點，

上面三種 Aitken 及 Fix point ，最後「是否可收斂」結果不盡相同，

即使都可收斂，但出來的解品質也不盡相同。

可確定的是， 若 Aitken 與 Fix point 同時收斂，

則 Aitken 速度較快。

C 語言程式碼

/*******************************************************************/
/*                                                                 */
/*     filename : AitkenRoot.c                                     */
/*     author   : edison.shih/edisonx                              */
/*     compiler : Visual C++ 2008                                  */
/*     date     : 2011.03.07                                       */
/*                                                                 */
/*         A.L.L.      R.I.G.H.T.S.     R.E.S.E.R.V.E.             */
/*                                                                 */
/*******************************************************************/

/*----------------------------------------------------------------*\
|
| E0 :  f(x)=0 化為g(x) = x，初始化最小誤差EPS，初始點xo
| E1 :  x1 = g(x0), x2=g(x1) , delta = abs(x1-x2)
| E2 :  if delta < eps 成立，演算法結束，傳回x2
| E3 :  x = x2 - delta * delta / (x2 - 2*x1 + x0)
| E4 :  x0 = g(x)
| E6 :  goto E1
| 
\*----------------------------------------------------------------*/

#include <stdio.h>
#include <math.h>

double func(double x)
{
     double x2=x*x, x3=x2*x;
     return (x3 - 5.48*x2 -  1.4883*x + 20.394828);
}

double gfunc(double x)
{
     double x2=x*x, x3=x2*x;
     return sqrt( (x*x*x - 1.4883*x+20.394828) /5.48);
}

double AitkenRoot(double x0,              /*  初點   */
                       double (*gx)(double),   /* 適應函式*/
                       double eps,             /* 容許誤差*/
                       int max_itera)          /* 最大迭代*/
{
     double x, x1, x2;
     double delta, q;
     do{
           x1 = gx(x0), x2=gx(x1);
           delta = fabs(x2-x1);
           x = x2 - delta * delta / (x2 - 2.0*x1 + x0);
           x0 = gx(x);
     }while(delta > eps && max_itera);

     return x;
}

int main()
{
     const double eps=1E-9;
     const int max_itera=10;
     double x, x0;

     x0 = -2.0 ;
     x = AitkenRoot(x0, gfunc, eps, max_itera);
     printf("\n >func(%+.15e) = %+.15e", x, func(x));

     x0 = +2.0 ;
     x = AitkenRoot(x0, gfunc, eps, max_itera);
     printf("\n >func(%+.15e) = %+.15e", x, func(x));

     x0 = +4.0 ;
     x = AitkenRoot(x0, gfunc, eps, max_itera);
     printf("\n >func(%+.15e) = %+.15e", x, func(x));

     x0 = 0.0 ; // test
     x = AitkenRoot(x0, gfunc, eps, max_itera);
     printf("\n >func(%+.15e) = %+.15e", x, func(x));
     return 0;
}

執行結果

 >func(+2.313837835588586e+000) = +3.552713678800501e-015
 >func(+2.313837835588585e+000) = +1.421085471520200e-014
 >func(+4.947665978216175e+000) = -2.131628207280301e-014
 >func(+2.313837835588589e+000) = -3.197442310920451e-014

[回目錄]