如何用C中的牛顿拉夫森方法检测一个循环

Question

牛顿拉夫森方法的失效分析表明,"对于某些函数,一些起点可能进入无限循环,阻止收敛".我想在程序中检查它是否进入无限循环或不使用assert语句.如果它进入,那么程序将终止说使用这个初始猜测无法收敛.如何在程序中检测此循环？码:

int user_power, i=0, cnt=0, flag=0;
int coef[10]={0};
float x1=0, x2=0, t=0;
float fx1=0, fdx1=0;

void main()
{
    printf("\n\n\t\t\t PROGRAM FOR NEWTON RAPHSON GENERAL");
    printf("\n\n\n\tENTER THE MAXIMUM POWER:");
    scanf("%d",&user_power);

    for(i=0;i<=user_power;i++)
    {
        printf("\n\t x^%d:",i);
        scanf("%d",&coef[i]);
    }

    printf("\n");
    printf("\n\tINTIAL X1---->");
    scanf("%f",&x1);

    printf("\n ******************************************************");
    printf("\n ITERATION    X1    FX1    F'X1  ");
    printf("\n **********************************************************");

    do
    {
           cnt++;
           fx1=fdx1=0;
           for(i=user_power;i>=1;i--)
           {
                fx1+=coef[i] * (pow(x1,i)) ; //calculating f(x1)
           }
           fx1+=coef[0];
           for(i=user_power;i>=0;i--)
           {
                fdx1+=coef[i]* (i*pow(x1,(i-1))); //calculating f'(x1)
           }
           t=x2;
           assert(fdx1!=0);
           x2=(x1-(fx1/fdx1));

           x1=x2;

           printf("\n %d         %.3f  %.3f  %.3f ",cnt,x2,fx1,fdx1);

    } while((fabs(t - x1))>=0.0001);
    printf("\n\t THE ROOT OF EQUATION IS %f",x2);
    printf("\n");
}

Answer 1

您不检查周期性轨道.确定周期然后收敛到轨道太昂贵了.

如果大致满足二次收敛的条件,你可以做的是在5次牛顿迭代后检查.为此,如果函数值的减少量大于4的除数(或者在牛顿步长的步长中,它应该大于2的除数),则检查3个步骤.

如果失败了,重新启动一些(随机)修改初始点.

对于大多数问题,牛顿方法在双精度中的应用在超过双浮点格式的精度之前具有2-3步全局方向,然后是4-6步的二次收敛.因此,一个人可以更大胆,如果在10步之后迭代不收敛,则初始点是不好的,无论是导致周期性轨道还是向无穷大发散.最有可能的是,附近的初始点的行为类似,因此在下一次迭代运行的开始时对初始点进行非平凡的更改.

补充说明:

• 调查Horner方案和双Horner方案来评估多项式(及其衍生物).使用电源功能是不明智的.

• 对可能没有多项式真正根源的情况进行一些思考.

• 有关通过牛顿方法求多项式的所有根的一般概念,请参阅JH Hubbard,D.Schleicher,S.Sutherland:如何通过牛顿方法找到复多项式的所有根,Inventiones Mathematicae vol.146(2001) - 讨论了牛顿分形的全局结构