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

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

Таблица 7.6.1. Сравнение числа неполных частных и бисекций, необходимых для получения требуемой точности

Прежде всего определим число бисекций и неполных частных соответственно, необходимых для каждого рассматриваемого метода, чтобы аппроксимировать корень с заданной точностью. В

предположении, что исходный полином имеет только один положительный корень, мы можем взять как исходный интервал для метода бисекций. Кроме того, для метода цепных дробей мы предполагаем худший из возможных случаев, т.е. каждое неполное частное равно 1; в этом случае мы имеем где есть элемент последовательности Фибоначчи. Из табл. 7.6.1 видно, что при сделанных предположениях для аппроксимации корня с одной и той же точностью бисекций требуется больше, чем вычислений неполных частных.

Таблица 7.6.2. Времена вычислений (в секундах) аппроксимации всех вещественных корней полиномов Чебышева )

В табл. 7.6.2 показаны времена вычислений, требующиеся для аппроксимации вещественных корней полиномов Чебышёва с использованием методов бисекций и цепных дробей. Все времена даны в секундах. Мы сравниваем три версии метода цепных дробей: версии, которые используют (1) правило Коши, (2) теорему 7.5.1 с бисекциями и (3) предварительную обработку. В версии (3) мы предполагаем, что список неполных частных задается как входной. Таким образом, мы не тратим время на вычисление функций floor. (Результаты версии 3 отражают оптимальное время аппроксимации вещественного корня с использованием метода цепных дробей.) Различие между версиями, использующими

Таблица 7.6.3. Аппроксимации вещественных корней полиномов Чебышёва степеней

(см. скан)

Таблица 7.6.3 (продолжение)

теорему 7.5.1 с бисекциями и предварительную обработку, отражает время, затрачиваемое на вычисление функций floor. Мы напоминаем читателю, что для того, чтобы получить функцию floor для некоторого корня, нужно несколько раз применить правило Коши.

Эти результаты показывают, что версия, использующая теорему 7.5.1 с бисекциями, существенно лучше версии, использующей правило Коши. С другой стороны, сравнивая ее с результатами версии, использующей предварительную обработку, мы замечаем, что еще имеется место для усовершенствования.

В качестве иллюстрации алгоритма аппроксимации в табл. 7.6.3 мы приводим список неполных частных с аппроксимирующими интервалами для каждого корня полиномов Чебышёва степеней ). Поскольку полиномы Чебышёва симметричны, мы рассматриваем только положительные корни. полиномов нечетной степени мы опускаем корень

Отметим, что последняя цифра и списке отделений (неполных частных) и первая цифра в списке аппроксимаций (неполных частных) составляют одно и то же неполное частное.