牛顿方法程序(在C中)循环无限运行 [英] Newton's method program (in C) loop running infinitely

问题描述

C语言中的此代码(后附)使用 Newton-Raphson方法在特定间隔内找到多项式的根.

This code(attached with the post) in C uses Newton - Raphson method to find roots of a polynomial in a particular interval.

对于某些像x^3 + x^2 + x + 1的多项式来说，这段代码工作得很好，但是对于诸如x^3 - 6*x^2 + 11*x - 6的某些多项式来说，运行时是无限的.也就是说，对于在输入间隔中具有一或零个根的多项式，此代码可以正常工作，但是如果存在多个根，则它会无限期运行.

This code works perfectly fine for some polynomials like x^3 + x^2 + x + 1 but runtime gets infinite for some polynomials like x^3 - 6*x^2 + 11*x - 6 . That is this code works fine for polynomials having one or zero root in the entered interval but if more than one roots are present then it runs indefinitely.

请让我知道是否有人找到解决方案.我已经在代码中写了一些注释来指导读者，但是如果有人觉得难以理解，可以在注释中提问，我会解释的.

Please let me know if someone finds a solution for this. I have written comments in the code to guide the reader but still if anyone finds it difficult to understand, can ask in the comments, I'll explain it.

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

int check(float num)                          //just a function to check for  the correct input
{
    char c;
    scanf("%c",&c);

    if(isalpha((int)c))
        printf("you entered an alphabet\n");

    else
        printf("you entered a character, please retry\n");

    return 0;
}

float func(float *p,int order,double x)                     //calculates the value of the function required in the formmula in main
{
    double fc=0.0;
    int i;

    for(i=0;i<=order;i++)
    {
        fc=fc+(double)(*p)*pow(x,(double)i);
        p++;
    }

    return fc;
}

float derv(float *q,int order,double x)               //calculates the derivative of the function required in the formmula in main
{     
    double dv=0.0,i;

    for(i=1;i<=order;i++)
    {
        dv=dv+(double)(*q)*(pow(x,(double)(i-1)))*(double)i;
        q++;
    }

    return dv;
}


int main()
{
    float coeff[1000];
    int order,count=0,i,j=0;
    char ch;
    float a,b;
    double val[5];

    printf("roots of polynomial using newton and bisection method\n");
    printf("enter the order of the equation\n");

    while(scanf("%d",&order)!=1)
    {
        printf("invalid input.please retry\n");
        while(getchar()!='\n'){}          
    }     

    printf("enter the cofficients\n");

    for(i=0;i<=order;i++)
    {
        printf("for x^%d  :",order-i);
        printf("\n");

        while(scanf("%f",&coeff[i])!=1)
        {
            check(coeff[i]);
        }   
    }

    while(getchar()!='\n'){}                                 //this clears the buffer accumulated upto pressing enter

    printf("the polynomial you entered is :\n");

    for(i=0;i<=order;i++)
    {
        printf(" %fx^%d ",coeff[i],order-i);
    }

    printf("\n");

    //while(getchar()!='\n'){};

    /* fflush(stdout);
    fflush(stdin);*/

    printf("plese enter the interval domain [a,b]\n");
    printf("enter a and b:\n");
    scanf("%f %f",&a,&b);

    while(getchar()!='\n'){}

    printf("the entered interval is [%f,%f]",a,b);

    fflush(stdout);
    fflush(stdin);

    //this array is used to choose a different value of x to apply newton's formula recurcively in an interval to scan it roperly for 3 roots

    val[0]=(double)b;       
    val[1]=(double)a;
    val[2]=(double)((a+b)/2);

    double t,x=val[0],x1=0.0,roots[10];

    while(1)
    {

        t=x1;
        x1=(x-(func(&coeff[0],order,x)/derv(&coeff[0],order,x)));           //this is the newton's formula

        x=x1;

        if((fabs(t - x1))<=0.0001 && count!=0)
        {
            roots[j]=x;
            j++;
            x=val[j];   // every time a root is encountered this stores the root in roots array and runs the loop again with different value of x to find other roots
            t=0.0;
            x1=0.0;
            count=(-1);

            if(j==3)
                break;
        }

        count++;
    }

    printf("the roots are = \n");

    int p=0;

    for(j=0;j<3;j++)
    {
        if(j==0 && roots[j]>=a && roots[j]<=b)
        {
            printf("  %f  ",roots[j]);
            p++;
        }

        if(fabs(roots[j]-roots[j-1])>0.5 && j!=0 && roots[j]>=a && roots[j]<=b)
        {
            printf(" %f  ",roots[j]);
            p++;
        }
    }

    if(p==0)
        printf("Sorry,no roots are there in this interval \n");

    return 0;
}

推荐答案

您没有正确地计算函数或导数，因为您以相反的顺序存储系数，但没有考虑到这一点.

You're not calculating the function or the derivative correctly, because you store the coefficients in reverse order but you aren't accounting for that.

当打印出方程式时，您可以通过打印order-i来做:

When you print out the equation, you do account for it, by printing order-i:

printf(" %fx^%d ",coeff[i],order-i);

所以您需要在func中做同样的事情:

So you need to do the same thing in func:

fc=fc+(double)(*p)*pow(x,(double)(order-i));

和derv:

dv=dv+(double)(*q)*(pow(x,(double)((order-i)-1)))*(double)(order-i);

之所以适用于像x^3 + x^2 + x + 1这样的多项式，是因为在该示例中，所有系数都是相同的，因此，如果向前或向后读取数组，它都不会有所不同.

The reason it's working for polynomials like x^3 + x^2 + x + 1 is because in that example all the coefficients are the same so it won't make a difference if you read the array forwards or backwards.

此外，如Johnathon Leffler在评论中提到的那样，您可能需要考虑其他原因导致方法无法收敛.您可以为循环设置最大迭代次数，如果超过最大次数则中断.

In addition, you may need to account for other reasons the method can fail to converge, as mentioned by Johnathon Leffler in a comment. You can set a maximum number of iterations for your loop and just break out if it exceeds the maximum.

一种调试类似这样的东西(当然是使用调试器)的好方法是添加一些额外的printf语句以显示正在计算的值.您可以通过在Google搜索中输入方程式来理清输出，它将给出该函数的交互式图形.

A good way to debug something like this (besides using a debugger of course) is to add a few extra printf statements to show the values that are being calculated. You can sanity check the output by entering the equation into a Google search, it will give an interactive graph of the function.

这篇关于牛顿方法程序(在C中)循环无限运行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！