न्यूटन रैफसन हाइब्रिड एल्गोरिदम समाधान तक नहीं पहुंच रहा है

Question

समस्या का संक्षिप्त विवरण: मैं बहुपद में रूट खोज के लिए न्यूटन रैफसन एल्गोरिदम का उपयोग करता हूं और कुछ मामलों में काम नहीं करता है। क्यूं कर?

मैंने न्यूटन रैफसन हाइब्रिड एल्गोरिदम में "सी ++ में संख्यात्मक व्यंजनों" से लिया, जो न्यू-रैफ ठीक से अभिसरण नहीं कर रहा है (कम व्युत्पन्न मूल्य के साथ या अभिसरण गति तेज नहीं है) में विभाजित होता है।

मैंने कई बहुपदों के साथ एल्गोरिदम की जांच की और यह काम किया। अब मैं अपने पास मौजूद सॉफ़्टवेयर के अंदर परीक्षण कर रहा हूं और मुझे हमेशा एक विशिष्ट बहुपद के साथ एक त्रुटि मिली है। मेरी समस्या यह है कि मुझे नहीं पता कि यह बहुपद परिणाम नतीजे क्यों नहीं मिलता है, जब बहुत से लोग करते हैं। चूंकि मैं किसी भी बहुपद के लिए एल्गोरिदम सुधारना चाहता हूं, मुझे यह जानने की जरूरत है कि कोई अभिसरण का कारण नहीं है, इसलिए मैं इसका ठीक से इलाज कर सकता हूं।

निम्नलिखित मैं उन सभी सूचनाओं को पोस्ट करूंगा जो मैं एल्गोरिदम और बहुपद के बारे में प्रदान कर सकता हूं जिसमें मुझे त्रुटि है।

बहुपद:

f'(t)= 4*t^3 + 1.671771945769790*t^2 - 7.365081720663563*t + 0.139389107255627 

प्लॉट::

जड़ें (मैटलैब से):

-2.133112008595826   1.371976341295347   0.883715461977390 
    -0.679837109933505 

f(t)= t^4 + 0,557257315256597*t^3 - 3,68254086033178*t^2 + 
+ 0,139389107255627*t + 1,75823776590795 

यह पहली व्युत्पन्न हैएल्गोरिथ्म:

double rtsafe(double* coeffs, int degree, double x1, double x2,double xacc,double xacc2) 
    { 
    int j; 
    double df,dx,dxold,f,fh,fl; 
    double temp,xh,xl,rts; 
    double* dcoeffs=dvector(0,degree); 
    for(int i=0;i<=degree;i++) 
     dcoeffs[i]=0.0; 
    PolyDeriv(coeffs,dcoeffs,degree); 
    evalPoly(x1,coeffs,degree,&fl); 
    evalPoly(x2,coeffs,degree,&fh); 
    evalPoly(x2,dcoeffs,degree-1,&df); 
if ((fl > 0.0 && fh > 0.0) || (fl < 0.0 && fh < 0.0)) 
    nrerror("Root must be bracketed in rtsafe"); 

if (fl == 0.0) return x1; 
if (fh == 0.0) return x2; 

if (fl < 0.0) { // Orient the search so that f(xl) < 0. 
    xl=x1; 
    xh=x2; 
} else { 
    xh=x1; 
    xl=x2; 
} 
rts=0.5*(x1+x2); //Initialize the guess for root, 
dxold=fabs(x2-x1); //the "stepsize before last," 
dx=dxold;   //and the last step 

evalPoly(rts,coeffs,degree,&f); 
evalPoly(rts,dcoeffs,degree-1,&dx); 

for (j=1;j<=MAXIT;j++) { //Loop over allowed iterations 

    if ((((rts-xh)*df-f)*((rts-xl)*df-f) > 0.0) //Bisect if Newton out of range, 
      || (fabs(2.0*f) > fabs(dxold*df))) { //or not decreasing fast enough. 
     dxold=dx; 
     dx=0.5*(xh-xl); 
     rts=xl+dx; 
     if (xl == rts) 
      return rts; //Change in root is negligible. 
    } else {// Newton step acceptable. Take it. 
     dxold=dx; 
     dx=f/df; 
     temp=rts; 
     rts -= dx; 
     if (temp == rts) 
      return rts; 
    } 
    if (fabs(dx) < xacc) 
     return rts;// Convergence criterion 
    evalPoly(rts,coeffs,degree,&f); 
    evalPoly(rts,dcoeffs,degree-1,&dx); 
    //The one new function evaluation per iteration. 
    if (f < 0.0) //Maintain the bracket on the root. 
     xl=rts; 
    else 
     xh=rts; 

} 
//As the Accuracy asked to the algorithm is really high (but usually easily reached) 
//the results precission is checked again, but with a less exigent result 
dx=f/df; 
if(fabs(dx)<xacc2) 
    return rts; 
nrerror("Maximum number of iterations exceeded in rtsafe"); 
return 0.0;// Never get here. 
} 

एल्गोरिथ्म अगले चर के साथ कहा जाता है:

x1=0.019 
x2=1.05 
xacc=1e-10 
xacc2=0.1 
degree=4 
MAXIT=1000 
coeffs[0]=1.75823776590795; 
coeffs[1]=0.139389107255627; 
coeffs[2]=-3.68254086033178; 
coeffs[3]=0.557257315256597; 
coeffs[4]=1.0; 

समस्या यह है कि एल्गोरिथ्म amximum पुनरावृत्तियों से अधिक है और वहाँ aproximatedly 0.15 की जड़ तक एक arror है।

तो मेरी प्रत्यक्ष और abrebiated सवाल यह है: क्यों इस बहुपद एक सटीक त्रुटि तक नहीं पहुंचता है जब कई (1000 कम से कम) अन्य बहुत समान बहुआयामी पद करना (wuth परिशुद्धता और कुछ पुनरावृत्तियों की 1e-10!)

मैं पता है कि सवाल मुश्किल है और इसमें वास्तव में सीधा जवाब नहीं हो सकता है, लेकिन मैं कुछ दिनों से इसके साथ अटक गया हूं और मुझे नहीं पता कि इसे कैसे हल किया जाए। मेरे प्रश्न को पढ़ने के लिए समय निकालने के लिए बहुत बहुत धन्यवाद।

Answer 1

मुझे यकीन है कि नहीं कर रहा हूँ वास्तव में क्यों है, लेकिन यह जांच करें कि समारोह काफी तेजी में काम करने के लिए प्रकट नहीं होता है कम हो रही है को देखने के लिए ये मामला।

यह काम करता है, तो मैं इसे इस तरह कार्य करें:

double old_f = f; 

    . 
    . 
    . 

    if ((((rts-xh)*df-f)*((rts-xl)*df-f) > 0.0) //Bisect if Newton out of range, 
     || (fabs(2.0*f) > old_f)) { //or not decreasing fast enough. 
    . 
    . 
    . 

    if (fabs(dx) < xacc) 
     return rts;// Convergence criterion 
    old_f = f; 

अद्यतन

ऐसा लगता है कि वहाँ अपने कोड में एक समस्या है जैसे:

evalPoly(rts,dcoeffs,degree-1,&dx); 

होना चाहिए

evalPoly(rts,dcoeffs,degree-1,&df); 

Answer 2

अपना कोड चलाने के बिना, मेरा प्रारंभिक अनुमान यह है कि आप समानता के लिए फ़्लोटिंग पॉइंट मानों की तुलना कर रहे हैं यह निर्धारित करने के लिए कि आपका समाधान एकत्र हो गया है या नहीं।

if (xl == rts) 
     return rts; //Change in root is negligible. 

हो सकता है कि आप इसे एक अनुपात के रूप में गणना करना चाहिए:

diff = fabs(xl - rts); 
    if (diff/xl <= 1.0e-8) // pick your own accuracy value here 
     return rts;