Bagaimanakah Kita Boleh Mengira Nilai Domain Sebenar Dengan Cekap Menggunakan Carian Penghampiran?

Cara Penghampiran Carian Berfungsi

Prolog

Artikel ini bertujuan untuk memberikan pemahaman yang menyeluruh tentang kerja dalaman kelas carian anggaran, direka bentuk untuk menganggarkan nilai dan parameter dalam domain sebenar untuk tugasan seperti sebagai pemasangan polinomial dan penyelesaian persamaan.

Soalan

Bagaimanakah kita boleh menganggarkan nilai atau parameter dalam domain sebenar (menggunakan nombor titik terapung berketepatan dua) untuk tugasan seperti menyesuaikan polinomial, mencari parameter dalam fungsi parametrik, atau menyelesaikan persamaan (sukar) (seperti transendental)?

Sekatan

• Domain sebenar (double-precision)
• Bahasa C
• Ketepatan anggaran yang boleh dikonfigurasikan
• Selang yang diketahui untuk carian
• Nilai atau parameter yang dipasang tidak sepenuhnya monotonik atau mungkin bukan fungsi sama sekali

Carian Anggaran

Carian anggaran adalah analog kepada carian binari tetapi mengalih keluar sekatan bahawa fungsi, nilai atau parameter yang dicari mestilah fungsi monotonik yang ketat. Walaupun kelonggaran ini, ia mengekalkan kerumitan O(log(n)) yang sama.

Algoritma

Pertimbangkan masalah berikut:

Memandangkan diketahui fungsi y = f(x) dan titik y0 yang diingini, kami bertujuan untuk mencari x0 supaya y0 = f(x0).

Maklumat Diketahui

• y = f(x) - fungsi input
• y0 - nilai titik y yang dikehendaki
• a0, a1 - penyelesaian x selang julat

Tidak diketahui:

• x0 - nilai titik sasaran x dalam julat

Algoritma Langkah:

1. Mata probe x(i) = jarak sama rata di sepanjang julat dengan beberapa langkah da.

   • Contohnya: x(i) = a0 i * da, dengan i = 0, 1, 2, ...

2. Untuk setiap x(i), hitung jarak/ralat ee antara y = f(x(i)) dan y0.

   • Ralat ini boleh dikira menggunakan metrik seperti ee = fabs(f(x(i)) - y0).
3. Ingat titik aa = x(i) dengan jarak/ralat minimum ee.
4. Berhenti apabila x(i) > a1.

5. Tingkatkan ketepatan secara rekursif.

   • Hadkan julat carian pada sekitar penyelesaian yang ditemui:

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

   • Tingkatkan ketepatan carian dengan mengurangkan langkah carian:

     • da' = 0.1 * da
   • Jika da' tidak terlalu kecil atau jika kiraan rekursi maksimum belum dicapai, kembali ke langkah 1.
6. Penyelesaian yang ditemui disimpan dalam aa.

Pelaksanaan dalam C

Kod C yang disediakan menunjukkan pelaksanaan algoritma carian anggaran:

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

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mengira Nilai Domain Sebenar Dengan Cekap Menggunakan Carian Penghampiran?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!