ПРЕДЕЛ СКОРОСТИ РЕШЕНИЯ УРАВНЕНИЙ 1974 ГОДА НАКОНЕЦ ДОКАЗАН

Чтобы найти, где функция f пересекает ноль, компьютер часто запускает итерацию: начать с догадки x, задать функции несколько вопросов, вычислить лучшую догадку и повторить. Эти вопросы — вычисления значений: значение f в некоторой точке, или её наклона (производной), или производной более высокого порядка.

Цифры, которые удваиваются

Скорость такого метода измеряют его порядком. Если текущая ошибка равна ε, итерация порядка p оставляет ошибку примерно ε в степени p. Порядок 2 означает, что вблизи ответа число верных цифр на каждом шаге удваивается; порядок 4 — что оно учетверяется.

Метод Ньютона тратит два вычисления на шаг — f(x) и её наклон f′(x) — и переходит к x − f(x)/f′(x). Его порядок равен 2. Если задавать больше вопросов за шаг, можно выиграть в скорости. Вопрос в том, сколько именно.

Гипотеза 1974 года

В 1974 году Х. Т. Кунг (H. T. Kung) и Дж. Ф. Трауб (J. F. Traub) предложили ответ — как «Гипотезу 8.1» в статье в Journal of the ACM: итерация без памяти, использующая n вычислений на шаг, имеет порядок не выше 2ⁿ⁻¹. «Без памяти» означает, что метод не сохраняет ничего от предыдущих шагов, кроме текущей догадки.

Понизить эту границу было нельзя: Кунг и Трауб сами построили «многоточечные» методы, достигающие 2ⁿ⁻¹ для каждого n ≥ 2, — порядок 4 при трёх вычислениях, 8 — при четырёх, 16 — при пяти. Не хватало второй половины: доказательства того, что ни один метод не может справиться лучше. Частичные результаты появлялись как вместе с гипотезой, так и после неё. Граница была доказана для методов, основанных на интерполяции, для рациональных методов с двумя вычислениями и при различных дополнительных условиях; для методов, использующих только значения функции, была установлена более слабая граница, 2ⁿ. Общий случай оставался открытым.

Как обмануть алгоритм

Мэтью Колбрук (Matthew Colbrook) с факультета прикладной математики и теоретической физики Кембриджского университета теперь доказывает её полностью. Модель намеренно щедра к алгоритму. Он может по ходу дела выбирать, где вычислять значения и какие производные брать. Он может обрабатывать ответы любым детерминированным способом, каким пожелает, и от его правил не требуется никакой гладкости.

Доказательство обращает детерминированность алгоритма против него самого. Построим две функции, которые дают в точности одинаковые ответы на все его вопросы, но имеют разные нули. Алгоритм обязан вернуть для обеих одну и ту же догадку, поэтому на одной из них он промахивается по меньшей мере на половину расстояния между двумя нулями.

Чтобы найти такие пары, Колбрук слегка подталкивает опорную функцию, добавляя небольшой многочлен степени не выше n, у которого n + 1 настраиваемых коэффициентов. Каждое вычисление фиксирует не больше одной их комбинации, так что после n вопросов некоторые подталкивания остаются невидимыми для алгоритма. Одного этого подсчёта недостаточно: невидимое подталкивание может почти не сдвинуть ноль.

Ключевой инструмент — вронскиан (определитель Вронского): определитель, построенный из семейства многочленов и их производных. Новая лемма утверждает, что если у многочлена из семейства много нулей, собранных в маленьком круге, то вронскиан семейства должен обращаться в ноль поблизости. Всегда отвечая алгоритму функцией, ноль которой держится в стороне от этих немногих точек, доказательство оставляет ноль свободным для перемещения.

Показатель степени получается из подсчёта. Если начать на расстоянии ε от нуля, возможные нули остаются разбросанными по интервалу, ширина которого не меньше константы, умноженной на некоторую степень ε. По словам автора, «показатель остаётся равным единице после первого наблюдения, а затем удваивается, давая 2ⁿ⁻¹ после n наблюдений».

Одна функция для всех масштабов

Оставалась одна трудность. Определение порядка позволяет константе перед степенью зависеть от функции, поэтому разные плохие функции на каждом масштабе ничего не доказывают. Так что Колбрук строит одну-единственную функцию, добавляя поправки одну за другой, причём каждая обращается в ноль во всех точках, которые алгоритм уже запросил, так что все прошлые ответы остаются в точности теми же.

Предел — целая функция, гладкая всюду, даже на комплексных числах, наклон которой на вещественной прямой остаётся между 3/4 и 5/4: равномерно поднимающаяся кривая с одним «хорошо ведущим себя» нулём. Для любого p больше 2ⁿ⁻¹ метод на ней не достигает порядка p. Следовательно, оптимальный порядок без памяти равен в точности 2ⁿ⁻¹ при n ≥ 2. Статья доказывает ту же границу и для случая, когда значения вычисляются в комплексных числах.

Цена вопросов, заданных разом

Более точное утверждение охватывает вычисления, выполняемые группами, где каждый вопрос группы выбирается до того, как придёт хотя бы один из её ответов, — это ситуация параллельных методов. При группах размеров ℓ₁, …, ℓₖ порядок не превышает ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Если задать все n вопросов разом, порядок ограничен n; если задавать их по одному, возможно 2ⁿ⁻¹. При пяти вычислениях это 5 против 16.

Проверено машиной

Результаты формально верифицированы в Lean — системе автоматической проверки доказательств, которая проверяет каждый логический шаг. Код открыт и зарегистрирован в реестре Palomar. Автор указывает, что формализация в Lean выполнена с помощью ChatGPT 6, затем проверена с помощью Lean 4 Comparator на соответствие теоремам статьи и что каждое рассуждение просмотрено автором, несущим полную ответственность за содержание.

Предел касается методов, которые забывают. Методы, которым разрешено повторно использовать свои предыдущие шаги, подчиняются другим границам, которые эта статья оставляет в стороне.