我們如何使用近似搜尋有效地近似實域值？

近似搜尋的工作原理

序言

本文旨在提供近似搜尋類的內部工作原理，旨在近似任務實域中的值和參數例如多項式擬合和方程式求解。

問題

我們如何近似任務的實域中的值或參數（使用雙精度浮點數）例如擬合多項式、在參數函數中查找參數或解（困難）方程式（例如超越數）？

限制

• 實數域（雙精確度）
• C語言
• 可配置的近似精度
• 已知間隔搜尋
• 擬合值或參數不是嚴格單調的或根本不是函數

近似搜索

近似搜索是類似的到二分搜索，但刪除了搜索函數、值或參數必須是嚴格單調函數的限制。儘管有這種放鬆，它仍保持相同的 O(log(n)) 複雜度。

演算法

考慮以下問題：

給定一個已知的函數y = f(x) 和所需的點y0，我們的目標是找到x0 使得y0 = f(x0).

已知資訊

• y = f(x) - 輸入函數
• y0 - 期望點y 值
• a0, a1 - 解 x區間範圍

未知：

• x0 - 範圍

演算法步驟：

1. 探測點x(i) = 沿著範圍均勻間隔一些步長da。

   例如：x(i) = a0 i * da，其中i = 0, 1, 2, ...

2. 對於每個x(i)，計算y = 之間的距離/誤差ee f(x(i)) 和y0。

   可以使用 ee = fabs(f(x(i)) - y0) 等指標來計算此誤差。
3. 記住距離/誤差最小的點 aa = x(i) ee.
4. 當 x(i) >時停止a1.

5. 遞歸提高準確率。

   • 將搜尋範圍限制在找到的解附近：
     a0' = aa - da
     • a1' = aa da
   • 透過減少搜尋步長來提高搜尋精確度：
     da' = 0.1 * da
     da' = 0.1 * da
   • 如果da' 不是過小或未達到最大遞迴計數，則傳回步驟
   1
   。
找到的解儲存在 aa 中。

C 中的實作

提供的C程式碼示範了近似搜尋演算法的實作：

#include "approx.h"
int main() {
    // Initialize the approx object with parameters
    approx aa;
    aa.init(0.0, 10.0, 0.1, 6, &ee);

    // Loop until a solution is found
    for (; !aa.done; aa.step()) {
        // Retrieve current x
        x = aa.a;

        // Compute y
        y = f(x);

        // Compute error
        ee = fabs(y - y0);
    }
}

以上是我們如何使用近似搜尋有效地近似實域值？的詳細內容。更多資訊請關注PHP中文網其他相關文章！