c++ - सन्निकटन खोज कैसे काम करती है




math approximation (2)

secant और bisection विधि का संयोजन ज्यादा बेहतर है:

हम सेक्टर्स द्वारा रूट का अनुमान लगाते हैं, और रूट को द्विभाजन के रूप में ब्रैकेटेड रखते हैं।

हमेशा अंतराल के दो किनारों को रखें ताकि एक किनारे पर डेल्टा नकारात्मक हो, और दूसरे पर यह सकारात्मक हो, इसलिए जड़ अंदर रहने की गारंटी है; और रोकने के बजाए, धर्मनिरपेक्ष विधि का उपयोग करें।

स्यूडोकोड:

given a function f
given two points a, b, such that a < b and sign(f(a)) /= sign(f(b))
given tolerance tol
find root z of f such that abs(f(z)) < tol     -- stop_condition

DO:
    x = root of f by linear interpolation of f between a and b
    m = midpoint between a and b

    if stop_condition holds at x or m, set z and STOP

    [a,b] := [a,x,m,b].sort.choose_shortest_interval_with_
                                   _opposite_signs_at_its_ends

यह स्पष्ट रूप से अंतराल [a,b] , या प्रत्येक पुनरावृत्ति पर भी बेहतर करता है; इसलिए जब तक कि कार्य अत्यंत खराब व्यवहार नहीं करता है (जैसे, कहते हैं, sin(1/x) x=0 पास), यह बहुत तेज़ी से अभिसरण करेगा, प्रत्येक पुनरावृत्ति चरण के लिए, f केवल दो मूल्यांकन ले रहा है।

और हम खराब व्यवहार के मामलों का पता लगा सकते हैं कि ba बहुत छोटा नहीं हो जाता है (अगर हम परिमित परिशुद्धता के साथ काम कर रहे हैं, तो दोगुने में)।

[प्रस्तावना]

यह क्यू एंड ए मेरे सन्निकटन खोज वर्ग के आंतरिक कामकाज को और अधिक स्पष्ट रूप से समझाने के लिए है जो मैंने पहली बार यहां प्रकाशित किया था

  • ट्रान्सेंडैंटल समीकरण के समाधान की बढ़ती सटीकता

मुझे इस बारे में अधिक विस्तृत जानकारी के लिए कुछ समय पहले ही (विभिन्न कारणों से) अनुरोध किया गया था, इसलिए मैंने इस बारे में प्रश्नोत्तर शैली विषय लिखने का फैसला किया जिसे मैं भविष्य में आसानी से संदर्भित कर सकता हूं और इसे बार-बार समझाने की आवश्यकता नहीं है।

[सवाल]

बहुपद, पैरामीट्रिक फ़ंक्शंस या हल (कठिन) समीकरणों (जैसे ट्रांसडेंटल) की फिटिंग हासिल करने के लिए रियल डोमेन ( double ) में मूल्यों / मापदंडों को कैसे अनुमानित करें?

प्रतिबंध

  • वास्तविक डोमेन ( double परिशुद्धता)
  • C ++ भाषा
  • सन्निकटन की विन्यास योग्य परिशुद्धता
  • खोज के लिए ज्ञात अंतराल
  • सज्जित मूल्य / पैरामीटर कड़ाई से एकरस नहीं है या बिल्कुल काम नहीं करता है

अपक्षय खोज

यह बाइनरी सर्च का सादृश्य है, लेकिन इसके प्रतिबंधों के बिना, जिन्होंने O(n.log(n)) जटिलता को साझा करते हुए फ़ंक्शन / मान / पैरामीटर को खोजा है, उन्हें सख्ती से मोनोटोनिक फ़ंक्शन होना चाहिए।

उदाहरण के लिए मान लें कि निम्नलिखित समस्या है

हम फ़ंक्शन y=f(x) को जानते हैं और x0 ऐसे खोजना चाहते हैं जैसे y0=f(x0) । यह मूल रूप से उलटा कार्य करने के लिए किया जा सकता है f लेकिन कई कार्य हैं जो हमें नहीं पता है कि इसके विपरीत कैसे गणना करें। तो ऐसे मामले में इसकी गणना कैसे करें?

knowns

  • y=f(x) - इनपुट फ़ंक्शन
  • y0 - बिंदु y मान चाहता था
  • a0,a1 - समाधान x अंतराल सीमा

अननोंस

  • x0 - वांछित बिंदु x मान रेंज x0=<a0,a1> में होना चाहिए

कलन विधि

  1. कुछ बिंदुओं की जाँच करें x(i)=<a0,a1> समान रूप से कुछ कदम da साथ सीमा पर छितरी हुई

    तो उदाहरण के लिए x(i)=a0+i*da जहाँ i={ 0,1,2,3... }

  2. प्रत्येक x(i) के लिए y=f(x(i)) की दूरी / त्रुटि ee की गणना करें y=f(x(i))

    इसे इस तरह उदाहरण के लिए गणना की जा सकती है: ee=fabs(f(x(i))-y0) लेकिन किसी अन्य मैट्रिक्स का भी उपयोग किया जा सकता है।

  3. न्यूनतम दूरी / त्रुटि ee साथ बिंदु aa=x(i) याद रखें

  4. बंद करो जब x(i)>a1

  5. पुनरावर्ती सटीकता बढ़ाता है

    इसलिए पहले उदाहरण के लिए पाया समाधान के चारों ओर खोज करने के लिए सीमा को सीमित करें:

    a0'=aa-da;
    a1'=aa+da;

    फिर खोज चरण कम करके खोज की सटीकता बढ़ाएँ:

    da'=0.1*da;

    यदि da' बहुत छोटा नहीं है या यदि अधिकतम पुनरावृत्ति गिनती नहीं है, तो # 1 पर जाएं

  6. पाया समाधान aa

यह मेरे मन में है:

बाईं ओर प्रारंभिक खोज सचित्र है (गोलियां # 1, # 2, # 3, # 4 )। दाईं ओर अगली पुनरावर्ती खोज (बुलेट # 5 )। जब तक वांछित सटीकता नहीं हो जाती है, तब तक यह पुनरावर्ती लूप होगा (पुनरावृत्ति की संख्या)। प्रत्येक पुनरावृत्ति 10 गुना सटीकता ( 0.1*da ) बढ़ाती है। ग्रे वर्टिकल लाइनें प्रोबेड x(i) पॉइंट्स को दर्शाती हैं।

यहाँ इसके लिए C ++ स्रोत कोड:

//---------------------------------------------------------------------------
//--- approx ver: 1.01 ------------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _approx_h
#define _approx_h
#include <math.h>
//---------------------------------------------------------------------------
class approx
    {
public:
    double a,aa,a0,a1,da,*e,e0;
    int i,n;
    bool done,stop;

    approx()            { a=0.0; aa=0.0; a0=0.0; a1=1.0; da=0.1; e=NULL; e0=NULL; i=0; n=5; done=true; }
    approx(approx& a)   { *this=a; }
    ~approx()           {}
    approx* operator = (const approx *a) { *this=*a; return this; }
    //approx* operator = (const approx &a) { ...copy... return this; }

    void init(double _a0,double _a1,double _da,int _n,double *_e)
        {
        if (_a0<=_a1) { a0=_a0; a1=_a1; }
        else          { a0=_a1; a1=_a0; }
        da=fabs(_da);
        n =_n ;
        e =_e ;
        e0=-1.0;
        i=0; a=a0; aa=a0;
        done=false; stop=false;
        }
    void step()
        {
        if ((e0<0.0)||(e0>*e)) { e0=*e; aa=a; }         // better solution
        if (stop)                                       // increase accuracy
            {
            i++; if (i>=n) { done=true; a=aa; return; } // final solution
            a0=aa-fabs(da);
            a1=aa+fabs(da);
            a=a0; da*=0.1;
            a0+=da; a1-=da;
            stop=false;
            }
        else{
            a+=da; if (a>a1) { a=a1; stop=true; }       // next point
            }
        }
    };
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

यह इसका उपयोग करने का तरीका है:

approx aa;
double ee,x,y,x0,y0=here_your_known_value;
//            a0,  a1, da,n, ee  
for (aa.init(0.0,10.0,0.1,6,&ee); !aa.done; aa.step())
    {
    x = aa.a;        // this is x(i)
    y = f(x)         // here compute the y value for whatever you want to fit
    ee = fabs(y-y0); // compute error of solution for the approximation search
    }

उपरोक्त for (aa.init(... नाम दिया गया for (aa.init(... हैं। a0,a1 एक अंतराल है जिस पर x(i) की जांच की जाती है, da x(i) और n बीच प्रारंभिक चरण है पुनरावर्ती। इसलिए यदि n=6 और da=0.1 x फिट की अंतिम अधिकतम त्रुटि ~0.1/10^6=0.0000001&ee चर के लिए पॉइंटर है जहां वास्तविक त्रुटि की गणना की जाएगी। मैं सूचक का चयन करता हूं इसलिए वहां नहीं है। इस घोंसले के शिकार जब टकराव।

[टिप्पणियाँ]

इस सन्निकटन खोज को किसी भी आयाम से जोड़ा जा सकता है (लेकिन मोटे तौर पर आपको गति के बारे में सावधान रहने की आवश्यकता है) कुछ उदाहरण देखें

  • सबसे फिट के साथ वक्र को n अंक का अनुमान
  • दोहराया बिंदुओं पर y अंक के साथ वक्र फिटिंग (गैलेक्सी सर्पिल हथियार)
  • ट्रान्सेंडैंटल समीकरण के समाधान की बढ़ती सटीकता
  • C ++ में बिंदुओं के समूह को घेरने वाला न्यूनतम क्षेत्र दीर्घवृत्त ज्ञात करें

गैर-फ़ंक्शन फिट और "सभी" समाधान प्राप्त करने की आवश्यकता के मामले में आप किसी अन्य समाधान की जांच करने के लिए पाए गए समाधान के बाद खोज अंतराल के पुनरावर्ती उपखंड का उपयोग कर सकते हैं। उदाहरण देखें:

  • एक एक्स-कोऑर्डिनेट को देखते हुए, मैं Y को एक बिंदु के लिए कैसे समन्वयित करूं, यह एक बेजियर ओरवे पर टिकी हुई है

आपको किस बारे में पता होना चाहिए?

आपको ध्यान से खोज अंतराल <a0,a1> चयन करना है <a0,a1> इसलिए इसमें समाधान है, लेकिन बहुत चौड़ा नहीं है (या यह धीमा होगा)। इसके अलावा प्रारंभिक चरण da बहुत महत्वपूर्ण है अगर यह बहुत बड़ा है तो आप स्थानीय मिनट / अधिकतम समाधानों को याद कर सकते हैं या यदि बहुत छोटी चीज बहुत धीमी हो जाएगी (विशेषकर नेस्टेड बहुआयामी फिट के लिए)।






approximation