근사 검색을 사용하여 실제 영역 값을 효율적으로 근사할 수 있는 방법은 무엇입니까?

근사 검색 작동 방식

프롤로그

이 글은 작업에 대한 실제 도메인의 값과 매개변수를 근사화하도록 설계된 근사 검색 클래스의 내부 작동 예를 들어 다항식 피팅 및 방정식 풀이 등이 있습니다.

질문

작업에 대해 실제 영역(이중 정밀도 부동 소수점 숫자 사용)의 값이나 매개변수를 어떻게 근사화할 수 있습니까? 다항식 피팅, 파라메트릭 함수에서 매개변수 찾기, (어려운) 방정식 풀기(예: 초월)?

제한

• 실제 도메인(배정밀도)
• C 언어
• 구성 가능한 근사 정밀도
• 알려진 간격 검색
• 적합값이나 매개변수가 단조롭지 않거나 전혀 함수가 아닐 수 있습니다

근사 검색

근사 검색은 유사합니다. 이진 검색을 수행하지만 검색된 함수, 값 또는 매개변수가 엄격하게 단조로운 함수여야 한다는 제한을 제거합니다. 이러한 완화에도 불구하고 동일한 O(log(n)) 복잡성을 유지합니다.

알고리즘

다음 문제를 고려하세요.

알려진 주어진 함수 y = f(x)와 원하는 점 y0을 사용하면 y0 =이 되도록 x0을 찾는 것이 목표입니다. f(x0).

알려진 정보

• y = f(x) - 입력 함수
• y0 - 원하는 점 y 값
• a0, a1 - 해 x 간격 범위

알 수 없음:

• x0 - 목표 지점 x 범위

알고리즘 단계:

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' = 아아 - da
     • a1' = aa da
   • 검색 단계를 줄여 검색 정밀도 향상:
     da' = 0.1 * 다
   다'가 아니면 너무 작거나 최대 반복 횟수에 도달하지 않은 경우
   • 1 단계로 돌아갑니다.
6. 발견된 솔루션은 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!