7.4. Эмпирическое сравнение двух методов отделения вещественных корней

В разд. 7.2 и 7.3 мы подробно обсуждали два классических способа, метод бисекций Штурма и метод цепных дробей 1978 г., отделения вещественных корней полиномиальных уравнений с целыми коэффициентами. Ниже мы приводим две таблицы, показывающие наблюденные времена вычислений для двух классов полиномов при использовании этих методов. Все времена даны в секундах и были получены с использованием системы компьютерной алгебры на модель 165. Каждый из полиномов в табл. 7.4.1 был получен путем перемножения соответствующего числа линейных сомножителей. Все коэффициенты полиномов в табл. 7.4.2 были ненулевыми, каждый коэффициент состоял из 10 десятичных цифр, коэффициенты были заданы случайным образом.

Полиномы в табл. 7.4.2 — те же, что были использованы Коллинзом [в (Rice, 1979)] и Коллинзом и Лоосом (Collins, Loos, 1976) для тестирования метода Коллинза-Акритаса и методов, основанных на дифференцировании; см. также исторические замечания 1 и 7. Поэтому нетрудно убедиться в преимуществе метода цепных

Таблица 7.4.1. Полиномы со случайно заданными в интервале (0,103) корнями

Таблица 7.4.2. Полиномы со случайно заданными коэффициентами

Таблица 7.4.3. Сравнение различных методов для полиномов из табл. 7.4.2

дробей 1978 г. (ACF1978) простым сравнением отношений времен различных методов к соответствующим временам, полученным

при использовании метода Штурма. Мы приводим эти отношения в табл. 7.4.3. [См. также (Mignotte, 1976).]