BATAS KECEPATAN DARI 1974 UNTUK MENYELESAIKAN PERSAMAAN, AKHIRNYA TERBUKTI

Untuk menemukan titik tempat sebuah fungsi f memotong nol, komputer sering menjalankan sebuah iterasi: mulai dari tebakan x, ajukan beberapa pertanyaan kepada fungsi itu, hitung tebakan yang lebih baik, lalu ulangi. Pertanyaan-pertanyaan itu adalah evaluasi: nilai f di suatu titik, atau nilai kemiringannya (turunan), atau turunan yang lebih tinggi.

Digit yang berlipat dua

Kecepatan metode semacam itu diukur dengan orde-nya. Jika galat saat ini adalah ε, iterasi berorde p menyisakan galat kira-kira ε pangkat p. Orde 2 berarti bahwa, di dekat jawaban, jumlah digit yang benar berlipat dua pada setiap langkah; orde 4 berarti berlipat empat.

Metode Newton menghabiskan dua evaluasi per langkah — f(x) dan kemiringannya f′(x) — lalu berpindah ke x − f(x)/f′(x). Metode ini berorde 2. Mengajukan lebih banyak pertanyaan per langkah dapat menghasilkan kecepatan lebih tinggi. Pertanyaannya, seberapa tinggi.

Sebuah dugaan dari 1974

Pada 1974, H. T. Kung dan J. F. Traub mengajukan sebuah jawaban, sebagai “Conjecture 8.1” dalam sebuah makalah di Journal of the ACM: iterasi tanpa memori yang memakai n evaluasi per langkah memiliki orde paling tinggi 2ⁿ⁻¹. “Tanpa memori” berarti metode itu tidak menyimpan apa pun dari langkah-langkah sebelumnya kecuali tebakannya saat ini.

Batas itu tidak dapat diturunkan: Kung dan Traub sendiri telah membangun metode “multititik” yang mencapai 2ⁿ⁻¹ untuk setiap n ≥ 2 — orde 4 dengan tiga evaluasi, 8 dengan empat, 16 dengan lima. Yang belum ada adalah separuh lainnya: bukti bahwa tidak ada metode yang dapat berbuat lebih baik. Hasil-hasil parsial muncul bersamaan dengan dugaan itu dan sesudahnya. Batas itu dibuktikan untuk metode berbasis interpolasi, untuk metode rasional dengan dua evaluasi, dan dengan berbagai syarat tambahan; untuk metode yang hanya memakai nilai fungsi, batas yang lebih lemah, 2ⁿ, berhasil ditetapkan. Kasus umumnya tetap terbuka.

Mengelabui algoritma

Matthew Colbrook, di Department of Applied Mathematics and Theoretical Physics, University of Cambridge, kini membuktikannya secara utuh. Modelnya sengaja dibuat murah hati terhadap algoritma. Algoritma boleh memilih tempat mengevaluasi, dan turunan mana yang diambil, seiring berjalannya proses. Algoritma boleh mengolah jawaban dengan cara deterministik apa pun yang dikehendakinya, tanpa syarat kemulusan pada aturan-aturannya.

Bukti itu membalikkan determinisme algoritma itu sendiri untuk melawannya. Bangun dua fungsi yang memberikan jawaban yang persis sama untuk semua pertanyaannya tetapi memiliki titik nol yang berbeda. Algoritma harus mengembalikan tebakan yang sama untuk keduanya, sehingga pada salah satunya tebakan itu meleset paling sedikit separuh jarak antara kedua titik nol.

Untuk menemukan pasangan semacam itu, Colbrook menggeser sedikit sebuah fungsi acuan dengan polinomial kecil berderajat paling tinggi n, yang memiliki n + 1 koefisien yang dapat disesuaikan. Setiap evaluasi mengunci paling banyak satu kombinasi koefisien itu, sehingga setelah n pertanyaan, sebagian pergeseran tetap tidak terlihat oleh algoritma. Hitungan itu saja belum cukup: sebuah pergeseran yang tak terlihat mungkin nyaris tidak memindahkan titik nol.

Alat kuncinya adalah Wronskian — sebuah determinan yang dibangun dari sekeluarga polinomial dan turunan-turunannya. Sebuah lema baru menyatakan bahwa jika sebuah polinomial dari keluarga itu memiliki banyak titik nol yang berdesakan dalam sebuah cakram kecil, Wronskian keluarga itu harus bernilai nol di dekatnya. Dengan selalu menjawab algoritma menggunakan fungsi yang titik nolnya menjauhi beberapa titik itu, bukti tersebut menjaga titik nol tetap bebas bergerak.

Pencatatan yang cermat menghasilkan eksponennya. Bermula pada jarak ε dari titik nol, titik-titik nol yang mungkin tetap tersebar pada rentang paling sedikit sebesar suatu konstanta dikali suatu pangkat ε. Menurut kata-kata penulis, “eksponennya tetap satu setelah pengamatan pertama lalu berlipat dua, menghasilkan 2ⁿ⁻¹ setelah n pengamatan.”

Satu fungsi untuk setiap skala

Satu kesulitan masih tersisa. Definisi orde membolehkan konstanta di depannya bergantung pada fungsi, sehingga fungsi buruk yang berbeda pada setiap skala tidak membuktikan apa-apa. Karena itu, Colbrook membangun satu fungsi tunggal, dengan menambahkan koreksi satu demi satu, masing-masing bernilai nol di setiap titik yang sudah ditanyakan algoritma, sehingga semua jawaban sebelumnya tetap persis sama.

Limitnya adalah sebuah fungsi seluruh (entire function) — mulus di mana-mana, bahkan pada bilangan kompleks — yang kemiringannya tetap di antara 3/4 dan 5/4 pada garis bilangan real: kurva yang naik dengan mantap dengan satu titik nol yang berperilaku baik. Untuk setiap p di atas 2ⁿ⁻¹, metode itu gagal mencapai orde p pada fungsi tersebut. Karena itu, orde optimal tanpa memori tepat 2ⁿ⁻¹ untuk n ≥ 2. Makalah itu membuktikan batas yang sama ketika evaluasinya berupa bilangan kompleks.

Harga bertanya sekaligus

Pernyataan yang lebih tajam mencakup evaluasi yang dilakukan dalam kelompok, ketika setiap pertanyaan dalam satu kelompok dipilih sebelum satu pun jawabannya tiba — situasi metode paralel. Dengan kelompok berukuran ℓ₁, …, ℓₖ, ordenya paling tinggi ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Mengajukan kesemua n pertanyaan sekaligus membatasi orde pada n; mengajukannya satu per satu memungkinkan 2ⁿ⁻¹. Dengan lima evaluasi, itu berarti 5 berbanding 16.

Diperiksa oleh mesin

Hasil-hasil itu diverifikasi secara formal dalam Lean, sebuah asisten pembuktian yang memeriksa setiap langkah logis. Kodenya terbuka untuk umum dan terdaftar di registri Palomar. Penulis menyatakan bahwa formalisasi Lean dikerjakan dengan bantuan ChatGPT 6, lalu diperiksa dengan Lean 4 Comparator terhadap teorema-teorema dalam makalah, dan bahwa setiap argumen telah ditinjau oleh penulis, yang memikul tanggung jawab penuh atas isinya.

Batas itu berlaku bagi metode yang melupakan. Metode yang boleh memakai kembali langkah-langkah sebelumnya mematuhi batas-batas lain, yang dikesampingkan oleh makalah ini.