近似搜尋如何有效地找出非單調函數的值和參數？-C++-PHP中文網

近似搜尋如何有效地找出非單調函數的值和參數？

DDD

發布： 2024-12-30 22:54:10

原創

627 人瀏覽過

How Can Approximation Search Efficiently Find Values and Parameters for Non-Monotonic Functions?

函數擬合和方程式求解的近似值和參數

了解近似搜尋的內部工作原理對於解決與擬合多項式、參數函數和超越相關的問題至關重要方程式。即使在處理不嚴格單調的函數時，這種方法也可以讓您有效地估計值和參數。

近似搜尋的工作原理

近似搜尋模仿二分搜尋的概念，但它並不不強加搜尋函數嚴格單調的限制。它的運作原理如下：

探測均勻分佈在已知區間上的樣本點。
計算函數值 f(x) 之間的誤差或距離每個樣本點和一個目標值y0。
辨識誤差最小的樣本點（表示為aa)。
在以 aa 為中心的較窄間隔內重複步驟 1-3 以提高精度。
繼續遞歸，直到達到所需的精確度或達到最大遞迴計數。

主要特點

處理能力非單調函數或不嚴格函數的函數。
提供可靠且有效率的演算法，複雜度為 O(log(n))。
允許使用者定義的精確度和誤差計算。

實作

這是近似值的簡化C 實作search:

class approx {
public:
    void init(double a0, double a1, double da, int n, double *e) {
        a0 = min(a0, a1); a1 = max(a0, a1); // Ensure a0 < a1
        da = abs(da);
        this->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) {
            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
        }
    }
};

登入後複製

使用範例

假設您想要找到x 的值，使得y = f(x) 最接近y0。以下是如何使用 approx 類別：

approx aa;
double ee, x, y, x0, y0 = your_target_value;
for (aa.init(0.0, 10.0, 0.1, 6, &ee); !aa.done; aa.step()) {
    x = aa.a;
    y = f(x);
    ee = abs(y - y0);
}

登入後複製