§ 7. О форме записи многочлена

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

После практического и теоретического анализа возникшей ситуации удалось установить причину происходящего.

Для определенности будем говорить о приближении функции на отрезке .

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

Сформулируем соответствующие утверждения более строго. Предположим, что существует последовательность многочленов

удовлетворяющих условию

( - не обязательно многочлены наилучшего равномерного приближения); предположим также, что коэффициенты этих многочленов растут не очень сильно:

Обозначим через открытую область, ограниченную дугами, из любой точки которых отрезок виден под углом . Известна

Теорема. Пусть последовательность многочленов удовлетворяет соотношениям (1), (2). Тогда функция может быть аналитически продолжена в открытую область комплексного переменного .

Примечание. Если вместо условия (1) имеем условие , то можно показать, что при любом .

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

являющаяся следствием этих погрешностей, может превзойти величину

Чтобы качественно представить характер влияния этой погрешности, будем считать, что число , входящее в условия (1), (2), и число t велики. Пусть функция аналитична в некоторой области , и не аналитична ни в какой области при . Пусть выбирается из соотношения . Возьмем произвольное . Если предположить, что для всех выполняется неравенство , то, согласно выше сформулированной теореме, будет аналитична в соответствующей области при и получается противоречие с предположением о свойствах функции . Таким образом, будут встречаться сколь угодно большие , для которых . Следовательно, при неблагоприятном стечении обстоятельств погрешность от округления значений может оказаться больше, чем . В то же время нельзя рассчитывать на оценку погрешности, лучшую, чем (1). Для суммарной погрешности, получающейся от замены на и от погрешностей в коэффициентах многочлена, мы не можем предложить оценки лучшей, чем . Уравнение для точки экстремума функции имеет вид

Отсюда следует, что . Подставив это значение в выражение для , получим

Таким образом, при вычислениях на ЭВМ с разрядами нельзя надеяться на получение более точных приближений к значениям функции, чем с разрядами. Например, для функции нижней гранью , при которой аналитична в области , будет соответствующее значение . Таким образом, на ЭВМ с 60 двоичными разрядами мы в лучшем случае можем рассчитывать на получение приближений к значениям функции примерно с 20 верными двоичными разрядами.

Если производная не существует в некоторой внутренней точке отрезка при не очень большом , то согласно примечанию к теореме имеет место еще большая потеря точности результата.

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

Эти обстоятельства побуждают к отысканию иных простых форм записи и вычисления значений многочленов.

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

Имеем

поэтому

Воспользуемся неравенством Коши—Буняковского

Отсюда заключаем, что

Если , то

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

Конечно, не обязательно представлять многочлены, приближающие функцию, в виде линейной комбинации (3) многочленов Чебышева. В зависимости от конкретной обстановки иногда удобнее представлять многочлен как линейную комбинацию многочленов какой-либо другой ортогональной системы, например многочленов Лежандра. (Мы рассмотрели систему многочленов Чебышева вследствие наибольшей простоты рекуррентных соотношений для вычисления их значений.)

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

Пусть в обычной форме этот многочлен записывается в виде и погрешность порядка является допустимой. Тогда имеет смысл воспользоваться схемой Горнера

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

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

При необходимости вычислить находим , затем последовательно находим по рекуррентной формуле . Известно, что вычислительная погрешность такого алгоритма есть

Задача 2. Проверить, что действительно .