[回目錄]


圖形與說明

 

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

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

謠言 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

 

[回目錄]

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()