GIỚI HẠN TỐC ĐỘ TỪ NĂM 1974 CHO VIỆC GIẢI PHƯƠNG TRÌNH, CUỐI CÙNG ĐÃ ĐƯỢC CHỨNG MINH

Để tìm điểm mà một hàm số f cắt qua giá trị không, máy tính thường chạy một phép lặp: bắt đầu từ một giá trị đoán x, đặt cho hàm số vài câu hỏi, tính ra một giá trị đoán tốt hơn, rồi lặp lại. Các câu hỏi đó là những lần tính giá trị (evaluation): giá trị của f tại một điểm nào đó, hoặc của độ dốc của nó (đạo hàm), hoặc của một đạo hàm bậc cao hơn.

Những chữ số tăng gấp đôi

Tốc độ của một phương pháp như vậy được đo bằng bậc hội tụ của nó. Nếu sai số hiện tại là ε, một phép lặp bậc p để lại sai số xấp xỉ ε mũ p. Bậc 2 có nghĩa là, khi đã gần đáp án, số chữ số đúng tăng gấp đôi sau mỗi bước; bậc 4 nghĩa là tăng gấp bốn.

Phương pháp Newton dùng hai lần tính giá trị mỗi bước — f(x) và độ dốc f′(x) — rồi chuyển đến x − f(x)/f′(x). Nó có bậc 2. Đặt nhiều câu hỏi hơn mỗi bước có thể đổi lấy tốc độ cao hơn. Câu hỏi là cao hơn bao nhiêu.

Một phỏng đoán từ năm 1974

Năm 1974, H. T. Kung và J. F. Traub đề xuất một câu trả lời, dưới dạng “Phỏng đoán 8.1” trong một bài báo trên Journal of the ACM: một phép lặp không có bộ nhớ sử dụng n lần tính giá trị mỗi bước có bậc tối đa là 2ⁿ⁻¹. “Không có bộ nhớ” nghĩa là phương pháp không giữ lại gì từ các bước trước ngoài giá trị đoán hiện tại.

Giới hạn này không thể hạ thấp hơn: chính Kung và Traub đã xây dựng các phương pháp “đa điểm” (multipoint) đạt tới 2ⁿ⁻¹ với mọi n ≥ 2 — bậc 4 với ba lần tính giá trị, 8 với bốn lần, 16 với năm lần. Điều còn thiếu là nửa kia: một chứng minh rằng không phương pháp nào có thể làm tốt hơn. Các kết quả từng phần ra đời cùng lúc với phỏng đoán và cả sau đó. Giới hạn được chứng minh cho các phương pháp dựa trên nội suy, cho các phương pháp hữu tỷ với hai lần tính giá trị, và dưới nhiều điều kiện bổ sung khác nhau; với các phương pháp chỉ dùng giá trị của hàm số, một giới hạn yếu hơn, 2ⁿ, đã được thiết lập. Trường hợp tổng quát vẫn bỏ ngỏ.

Đánh lừa thuật toán

Matthew Colbrook, tại Khoa Toán Ứng dụng và Vật lý Lý thuyết của Đại học Cambridge, giờ đây đã chứng minh nó một cách trọn vẹn. Mô hình được cố ý thiết kế rộng rãi với thuật toán. Thuật toán có thể tùy ý chọn nơi tính giá trị, và những đạo hàm nào cần lấy, trong quá trình chạy. Nó có thể xử lý các câu trả lời theo bất kỳ cách tất định nào nó muốn, mà không đòi hỏi các quy tắc của nó phải trơn.

Chứng minh này dùng chính tính tất định của thuật toán để chống lại nó. Hãy xây dựng hai hàm số cho ra đúng cùng những câu trả lời cho mọi câu hỏi của thuật toán nhưng có nghiệm khác nhau. Thuật toán buộc phải trả về cùng một giá trị đoán cho cả hai, nên với một trong hai hàm, nó trượt ít nhất một nửa khoảng cách giữa hai nghiệm.

Để tìm những cặp như vậy, Colbrook làm xê dịch một hàm tham chiếu bằng một đa thức nhỏ có bậc tối đa là n, đa thức này có n + 1 hệ số có thể điều chỉnh. Mỗi lần tính giá trị chỉ cố định được tối đa một tổ hợp của các hệ số đó, nên sau n câu hỏi vẫn còn những phép xê dịch mà thuật toán không thấy được. Riêng phép đếm đó chưa đủ: một phép xê dịch vô hình có thể hầu như không làm nghiệm dịch chuyển.

Công cụ then chốt là định thức Wronski (Wronskian) — một định thức được xây dựng từ một họ đa thức và các đạo hàm của chúng. Một bổ đề mới khẳng định rằng nếu một đa thức trong họ có nhiều nghiệm dồn vào trong một đĩa nhỏ, thì định thức Wronski của họ đó phải triệt tiêu ở gần đấy. Bằng cách luôn trả lời thuật toán bằng một hàm số có nghiệm nằm tránh xa vài điểm này, chứng minh giữ cho nghiệm được tự do dịch chuyển.

Việc tính toán sổ sách cho ra số mũ. Bắt đầu ở khoảng cách ε so với nghiệm, các nghiệm có thể có vẫn trải ra trên một khoảng ít nhất bằng một hằng số nhân với một lũy thừa của ε. Theo lời tác giả, “số mũ vẫn bằng một sau lần quan sát đầu tiên rồi tăng gấp đôi, cho ra 2ⁿ⁻¹ sau n lần quan sát.”

Một hàm số cho mọi thang đo

Vẫn còn một khó khăn. Định nghĩa bậc hội tụ cho phép hằng số đứng trước phụ thuộc vào hàm số, nên một hàm số xấu khác nhau ở mỗi thang đo thì chẳng chứng minh được gì. Vì vậy, Colbrook xây dựng một hàm số duy nhất, thêm vào lần lượt từng hiệu chỉnh, mỗi hiệu chỉnh triệt tiêu tại mọi điểm mà thuật toán đã truy vấn, để mọi câu trả lời trong quá khứ vẫn giữ nguyên hoàn toàn.

Giới hạn thu được là một hàm nguyên (entire function) — trơn ở mọi nơi, kể cả trên tập số phức — có độ dốc luôn nằm giữa 3/4 và 5/4 trên trục thực: một đường cong đi lên đều đặn với một nghiệm hành xử tốt. Với mọi p lớn hơn 2ⁿ⁻¹, phương pháp không đạt được bậc p trên hàm số này. Do đó, bậc tối ưu khi không có bộ nhớ đúng bằng 2ⁿ⁻¹ với n ≥ 2. Bài báo chứng minh cùng giới hạn đó khi các lần tính giá trị là số phức.

Cái giá của việc hỏi tất cả cùng lúc

Một phát biểu chặt hơn bao quát các lần tính giá trị được thực hiện theo nhóm, trong đó mọi câu hỏi của một nhóm được chọn trước khi bất kỳ câu trả lời nào của nhóm đó đến — tình huống của các phương pháp song song. Với các nhóm có kích thước ℓ₁, …, ℓₖ, bậc tối đa là ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Hỏi cả n câu cùng một lúc giới hạn bậc ở n; hỏi từng câu một cho phép đạt 2ⁿ⁻¹. Với năm lần tính giá trị, đó là 5 so với 16.

Được máy kiểm tra

Các kết quả được kiểm chứng hình thức bằng Lean, một trợ lý chứng minh kiểm tra từng bước logic. Mã nguồn được công khai và đăng ký trong kho đăng ký Palomar. Tác giả cho biết việc hình thức hóa bằng Lean được thực hiện với sự hỗ trợ của ChatGPT 6, sau đó được kiểm tra bằng Lean 4 Comparator đối chiếu với các định lý của bài báo, và mọi lập luận đều được tác giả xem xét lại, người chịu hoàn toàn trách nhiệm về nội dung.

Giới hạn này liên quan đến những phương pháp hay quên. Các phương pháp được phép dùng lại các bước trước đó tuân theo những giới hạn khác, mà bài báo này để ngỏ.