How Can We Efficiently Approximate Real-Domain Values Using Approximation Search?

How Approximation Search Works

Prologue

This article aims to provide a comprehensive understanding of the inner workings of an approximation search class, designed to approximate values and parameters in the real domain for tasks such as polynomial fitting and equation solving.

Question

How can we approximate values or parameters in the real domain (using double-precision floating-point numbers) for tasks like fitting polynomials, finding parameters in parametric functions, or solving (difficult) equations (such as transcendentals)?

Restrictions

• Real domain (double-precision)
• C language
• Configurable precision of approximation
• Known interval for search
• Fitted value or parameter is not strictly monotonic or may not be a function at all

Approximation Search

Approximation search is analogous to binary search but removes the restriction that the searched function, value, or parameter must be a strictly monotonic function. Despite this relaxation, it maintains the same O(log(n)) complexity.

Algorithm

Consider the following problem:

Given a known function y = f(x) and a desired point y0, we aim to find x0 such that y0 = f(x0).

Known Information

• y = f(x) - input function
• y0 - desired point y value
• a0, a1 - solution x interval range

Unknown:

• x0 - target point x value within the range <a0, a1>

Algorithm Steps:

1. Probe points x(i) = <a0, a1> evenly spaced along the range with some step da.

   • For example: x(i) = a0 i * da, where i = 0, 1, 2, ...

2. For each x(i), compute the distance/error ee between y = f(x(i)) and y0.

   • This error can be calculated using metrics such as ee = fabs(f(x(i)) - y0).
3. Remember the point aa = x(i) with the minimum distance/error ee.
4. Stop when x(i) > a1.

5. Recursively increase accuracy.

   • Restrict the search range to the vicinity of the found solution:

     • a0' = aa - da
     • a1' = aa da

   • Enhance search precision by decreasing the search step:

     • da' = 0.1 * da
   • If da' is not excessively small or if the maximum recursion count has not been reached, return to step 1.
6. The found solution is stored in aa.

Implementation in C

The provided C code demonstrates the implementation of the approximation search algorithm:

#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);
    }
}

The above is the detailed content of How Can We Efficiently Approximate Real-Domain Values Using Approximation Search?. For more information, please follow other related articles on the PHP Chinese website!