SCIP in C++11 ― 1.3.4節 その6

反復改良法：問題1.46

Newton法の抽象とは別の方向に、不動点探索とかの話をもう一段抽象化する話。

平均緩和法を抽象化した時のコードと重複する部分はバッサリ略。

----

const function<double(double)> iterativeImprove

(const function<double(double)>& transformer,

 const function<bool(double)>& isGoodEnough)

{

    function<double(double)> Try;

    Try=[transformer,isGoodEnough,&Try](const double guess)

        ->const double{

        if(isGoodEnough(guess)){return(guess);}

        return(Try(transformer(guess)));};

   

    return(Try);

}

const double fixedPoint

(const function<double(double)>& f, const double firstGuess)

{

    const double tolerance(0.00001);

    const function<bool(double)> isCloseEnough=

        [tolerance,f](const double guess)

        {return(abs(guess-f(guess))<tolerance);};

    return((iterativeImprove(f,isCloseEnough))(firstGuess));

}

const double sqrtIterative(const double x){

    return(iterativeImprove

           ([x](const double guess){return(average(guess,x/guess));},

            [x](const double guess){

                return(abs(x-guess*guess)<0.001);

            })(1.0));

}

int main(int argc, char** argv)

{

    cout<<setprecision(16)

        <<"sqrt(2) with iteration (Sec.1.1.7)="

        <<sqrtIterative(2.0)<<endl;

    cout<<setprecision(16)

        <<"sqrt(2) with fixed point (Sec.1.3.3)="

        <<sqrtFixed(2.0)<<endl;

    return(0);

}

----

出力

----

sqrt(2) with iteration (Sec.1.1.7)=1.41421568627451

sqrt(2) with fixed point (Sec.1.3.3)=1.41421568627451