8.3. Алгоритм спуска

Это простейший алгоритм поиска полинома для которого где заданное малое число. Строится последовательность полиномов следующим образом. Пусть на шаге уже построен полином Обозначим

Если существует полином такой, что

то, решив задачу одномерной минимизации

положим Этим завершается шаг. Если система неравенств (8.6) не имеет решения, тогда выполняется неравенство

и, значит, искомый полином. В самом деле, предположив, что для разности где полином наилучшего приближения, и для получим

что противоречит предположению о неразрешимости системы (8.6).

Полином удовлетворяющий системе линейных неравенств (8.6), задает "направление спуска" из "точки" для уклонения Направление спуска будет в определенном смысле наилучшим, если выбирается по следующему, более сложному в сравнение с (8.6), правилу

Задача (8.9) есть задача линейного программирования, но с меньшим, нежели (8.5), числом неравенств. Итак, усложненный алгоритм спуска [38] состоит в последовательном выполнении шагов: если на шаге построен полином то на следующем, шаге решается сначала задача (8.9), затем задача (8.7) и полагается Если задача (8.9), а значит, и (8.6), не имеют решения, то выполняется неравенство (8.8) и процесс заканчивается на шаге. Заметим, что уменьшая мы сокращаем количество неравенств в (8.9), но число шагов при этом, вероятно, увеличится.

Этот алгоритм оказался наиболее эффективным при решении прикладных задач.