DENKLEM ÇÖZMEDE 1974'TEN KALMA BİR HIZ SINIRI SONUNDA KANITLANDI

Bir f fonksiyonunun sıfırı nerede kestiğini bulmak için bilgisayar çoğu zaman bir yineleme (iterasyon) çalıştırır: bir x tahminiyle başla, fonksiyona birkaç soru sor, daha iyi bir tahmin hesapla ve tekrarla. Sorular değerlendirmelerdir: f’nin bir noktadaki değeri ya da eğimi (türevi) veya daha yüksek mertebeden bir türevi.

İkiye katlanan basamaklar

Böyle bir yöntemin hızı mertebesiyle ölçülür. Mevcut hata ε ise, p mertebesinden bir yineleme kabaca ε üzeri p kadar bir hata bırakır. Mertebe 2, cevaba yakınken doğru basamak sayısının her adımda ikiye katlanması demektir; mertebe 4 ise dört katına çıkması.

Newton yöntemi her adımda iki değerlendirme harcar — f(x) ve eğimi f′(x) — ve x − f(x)/f′(x) noktasına geçer. Mertebesi 2’dir. Adım başına daha fazla soru sormak daha fazla hız kazandırabilir. Soru, ne kadar kazandırabileceği.

1974’ten kalma bir sanı

1974’te H. T. Kung ve J. F. Traub, Journal of the ACM’de yayımlanan bir makalenin “Sanı 8.1”i (Conjecture 8.1) olarak bir cevap önerdi: adım başına n değerlendirme kullanan belleksiz bir yinelemenin mertebesi en fazla 2ⁿ⁻¹ olabilir. “Belleksiz”, yöntemin mevcut tahmini dışında önceki adımlardan hiçbir şey saklamadığı anlamına gelir.

Sınır daha aşağı çekilemezdi: Kung ve Traub her n ≥ 2 için 2ⁿ⁻¹’e ulaşan “çok noktalı” yöntemleri kendileri kurmuştu — üç değerlendirmeyle mertebe 4, dörtle 8, beşle 16. Eksik olan öbür yarıydı: hiçbir yöntemin daha iyisini yapamayacağının kanıtı. Kısmi sonuçlar sanıyla birlikte ve ondan sonra geldi. Sınır, interpolasyona dayalı yöntemler için, iki değerlendirmeli rasyonel yöntemler için ve çeşitli ek koşullar altında kanıtlandı; yalnızca fonksiyon değerlerini kullanan yöntemler için daha zayıf bir sınır, 2ⁿ, gösterildi. Genel durum açık kaldı.

Algoritmayı kandırmak

Cambridge Üniversitesi Uygulamalı Matematik ve Kuramsal Fizik Bölümü’nden Matthew Colbrook şimdi sanıyı tam olarak kanıtlıyor. Model, algoritmaya karşı bilerek cömert davranıyor. Algoritma, ilerledikçe nerede değerlendirme yapacağını ve hangi türevleri alacağını seçebilir. Cevapları istediği herhangi bir deterministik biçimde işleyebilir; kurallarından hiçbir düzgünlük beklenmez.

Kanıt, algoritmanın kendi determinizmini ona karşı çevirir. Tüm sorularına tıpatıp aynı cevapları veren ama farklı sıfırlara sahip iki fonksiyon kurun. Algoritma ikisi için de aynı tahmini döndürmek zorundadır; dolayısıyla bunlardan birinde en az iki sıfır arasındaki uzaklığın yarısı kadar ıskalar.

Bu tür çiftleri bulmak için Colbrook bir referans fonksiyonunu, derecesi en fazla n olan ve dolayısıyla n + 1 ayarlanabilir katsayısı bulunan küçük bir polinomla hafifçe oynatır. Her değerlendirme bu katsayıların en fazla bir bileşimini sabitler; bu yüzden n sorudan sonra bazı oynamalar algoritma için görünmez kalır. Bu sayım tek başına yetmez: görünmez bir oynama sıfırı ancak çok az kaydırıyor olabilir.

Anahtar araç Wronskiyen (Wronskian): bir polinom ailesinden ve onların türevlerinden kurulan bir determinant. Yeni bir lemma şunu söyler: ailedeki bir polinomun küçük bir diskin içine sıkışmış çok sayıda sıfırı varsa, ailenin Wronskiyeni yakınlarda sıfırlanmak zorundadır. Algoritmaya her zaman sıfırı bu birkaç noktadan uzak duran bir fonksiyonla cevap veren kanıt, sıfırın hareket etme serbestliğini korur.

Üs, bu hesabın sonucunda ortaya çıkar. Sıfırdan ε uzaklıkta başlandığında, olası sıfırlar en az bir sabit çarpı ε’nin bir kuvveti genişliğinde bir aralığa yayılmış halde kalır. Yazarın sözleriyle, “üs ilk gözlemden sonra bir olarak kalır, sonra ikiye katlanır ve n gözlemden sonra 2ⁿ⁻¹ verir.”

Her ölçek için tek bir fonksiyon

Bir güçlük daha kalmıştı. Mertebe tanımı, öndeki sabitin fonksiyona bağlı olmasına izin verir; dolayısıyla her ölçekte farklı bir kötü fonksiyon bulmak hiçbir şey kanıtlamaz. Colbrook bu yüzden düzeltmeleri birbiri ardına ekleyerek tek bir fonksiyon kurar; her düzeltme algoritmanın daha önce sorguladığı her noktada sıfır olur, böylece geçmişteki tüm cevaplar tıpatıp aynı kalır.

Limit bir tam fonksiyon (entire function), yani her yerde, karmaşık sayılar üzerinde bile pürüzsüz bir fonksiyon; eğimi gerçel doğru üzerinde 3/4 ile 5/4 arasında kalır: tek ve iyi huylu bir sıfırı olan, düzenli biçimde yükselen bir eğri. 2ⁿ⁻¹’den büyük her p için yöntem bu fonksiyonda p mertebesine ulaşamaz. Dolayısıyla belleksiz yöntemler için optimal mertebe, n ≥ 2 olduğunda tam olarak 2ⁿ⁻¹’dir. Makale aynı sınırı değerlendirmelerin karmaşık sayılar olduğu durum için de kanıtlıyor.

Hepsini birden sormanın bedeli

Daha keskin bir ifade, değerlendirmelerin gruplar halinde yapıldığı durumu kapsar: bir grubun her sorusu, cevaplarından herhangi biri gelmeden önce seçilir; paralel yöntemlerin durumu budur. ℓ₁, …, ℓₖ boyutlarındaki gruplarla mertebe en fazla ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1) olur. n sorunun hepsini birden sormak mertebeyi n ile sınırlar; onları tek tek sormak 2ⁿ⁻¹’e izin verir. Beş değerlendirmeyle bu, 5’e karşı 16 demektir.

Makine tarafından denetlendi

Sonuçlar, her mantıksal adımı denetleyen bir ispat asistanı olan Lean ile biçimsel olarak doğrulandı. Kod herkese açık ve Palomar kayıt sistemine kaydedilmiş durumda. Yazar, Lean biçimselleştirmesinin ChatGPT 6’nın yardımıyla gerçekleştirildiğini, ardından Lean 4 Comparator ile makalenin teoremlerine karşı denetlendiğini ve her argümanın, içeriğin tüm sorumluluğunu üstlenen yazar tarafından gözden geçirildiğini belirtiyor.

Bu sınır, unutan yöntemlerle ilgilidir. Önceki adımlarını yeniden kullanmasına izin verilen yöntemler başka sınırlara tabidir; bu makale onları ele almıyor.