действительные числа. В частности, когда 2 = е = cos в + zsin, полином u{z) является, по существу, двумя рядами Фурье (на самом деле - суммами. - Прим. ред.)

(«о + «1 COS0-Ь----\-UnCOsne) + г («1 sin 0-1-----\-Un sin пв).

Комплексное сложение и умножение, очевидно, может быть сведено к последовательности обычных операций над вещественными числами.

вещественное + комплексное требует 1 сложения

комплексное + комплексное требует 2 сложений

вещественное х комплексное требует -2 умножений

комплексное х комплексное требует 4 умножений, 2 сложений

или 3 умножений, 5 сложений

(См. упр. 41. Вычитание рассматривается здесь как эквивалент сложения.) Следовательно, правило Горнера (2) использует каждые 4п ~ 2 умножений и Зп - 2 сложений или Зп - 1 умножений и бп - 5 сложений для вычисления u{z), когда z = X + iy - комплексное число. В действительности без 2п - 4 сложений можно обойтись, так как каждый раз выполняется у.множение на то же число z. Предлагаем альтернативную процедуру вычисления и{х -\- iy):

ai=Un, h-Un-i, r = x + x, s = ж-г/;

aj = 6j i + ruj-i, bj = Un-j - suj-i, I < j <n. (3)

Тогда легко доказать по индукции, что u(z) = zun + bn- Эта схема [BIT 5 (1965), 142; также см. G. Goertzel, АММ 65 (1958), 34-35] требует только 2п -ь 2 умножений и 2п + 1 сложений, так как она является усовершенствованным правилом Горнера, когда п > 3. Для рядов Фурье, когда z = е, имеем s = 1, так что число умножений уменьшается до п -- 1. Отсюда мораль: хороший программист не станет неразборчиво использовать встроенные характеристики комплексной арифметики языков программирования высокого уровня.

Рассмотрим процесс деления полинома и{х) на i-iq, используя алгоритм 4.6.ID, чтобы получить и(х) = (х - Хо)5(х) + г(х), Здесь deg(r) < 1. В этом случае г(х)-константа, не зависящая от х и и(хо) - О • q{xo) + г = г. Проверка этого процесса деления позволяет обнаружить, что вычисления, по существу, такие же, как и правило Горнера для вычисления и{хо). Подобным образом, если мы делим u{z) на полином (z - zo){z - So) = 2 - 2жо2 + Xq + Уо, результат вычисления оказывается эквивалентным (3). Получаем u{z) - {z - zo){z - zo)q{z) + dz + b„; отсюда u{zo) = a„2o + bn-

Вообще, если разделить u(x) на /(x), получится u(x) = f{x)q{x) + r(x), a если f{xo) = 0, TO u(xo) = r(xo); это наблюдение приводит к дальнейшим обобщениям правила Горнера. Например, можно положить /(х) = х - Xq, что дает правило Горнера "второго порядка":

и{х) = (... (w2Ln/2Ja; + И2Ln/2J-2)a: + ---)х +uo

+ ((• (w2Гn/2-la; + и2Гn/2l-з)ж + ---)х + щ) х. (4)

В правиле второго порядка используются п+ 1 умножение и п слол<ений (см. упр. 5), что с этой точки зрения оно не улучшает правило Горнера. Но существуют по

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

Если компьютер допускает параллельное вычисление к арифметических операций одновременно, то можно применять правило Горнера "fc-ro порядка" (положив f{x) - х - Xq). Другой привлекательный метод для параллельного вычисления предложил Дж. Эстрин (G. Estrin) [Ргос. Western Joint Computing Conf. 17 (1960), 33-40]; для n = 7 метод Эстрина имеет следующий вид.

Процессор 1 Процессор 2 Процессор 3 Процессор 4 Процессор 5

ai=U7a;--ue bi = UbX + Ui ci=U3X + U2 di=-uiX + uo a2=aix + bi C2=cix + di x*

аз = a2X* + C2

Здесь аз = u{x). Тем не менее интересный анализ В. Ш. Дорна (W. S. Dorn) [IBM J. Res. and Devel. 6 (1962), 239-245] показал, что эти методы в действительности не могут быть улучшением правила второго порядка, если каждая арифметическая операция должна обращаться к памяти, которая сообщается только с одним процессором.

Табулирование значений полинома. Чтобы вычислить полином п-й степени на множестве значений арифметической прогрессии (т. е. и{хо), u{xo+h), u{xo+2h),...), процесс можно свести только к сложению после первых нескольких шагов. Так, если начать с любой последовательности чисел (qq, ui,..., а„) и применить преобразование

ао ао-Ь ai, ai <-ai-Ь аг, a„ i <-a„ i-Ь а„, (5)

получим, что к применений (5) дают

-r = (S)/?i + (l)/?i-M + (2)/.>2 + ---, 0<j<n, где /3j -начальное значение aj и /3j = О для j > п. В частности,

=.r = (J)*.()ft.....(*).„ (в,

представляет собой полином степени п от к. Правильно выбирая Pj, как показано в упр. 7, можно устроить так, что величина ад* будет требуемым значением u{xo + kh) для всех к. Другими словами, каждое выполнение п сложений в (5) будет давать следующее значение данного полинома.

Предостережение. Ошибки округления могут накапливаться после многочисленных повторений (5), и ошибка в Oj приводит к ошибке в коэффициентах х°,...,х вычисляемого полинома. Поэтому значения aj следовало бы "освежить" после большого числа итераций.

Производные и замена переменной. Иногда необходимо найти коэффициенты и{х + Хо) с заданными постоянной Хо и коэффициентами и{х). Например, если и{х) = Zx + 2а; -1, то и{х - 2) = За; - 10а; + 7. Это аналог проблемы преобразования системы счисления, преобразующей основание х в основание а; + 2. По теореме Тейлора новые коэффициенты заданы производными и(а;) в точке а; = а;о, т. е.

и(а; + а;о) = и(а;о) + и(а;о)а; + (и"(а;о)/2!)а;2 + • • • + (u(")(a;o)/n!)a;", (7)

так что задача эквивалентна вычислению и (а;) и всех ее производных.

Если записать и(а;) = q{x){x - Xq) + г, то и(а; + а;о) = q{x + хо)х + г; в таком случае г есть постоянный коэффициент и(а;+а;о) и проблема сводится к нахождению коэффициентов q{x + а;о), где (а;) - известный полином степени п - 1. Таким образом, предлагаем следующий алгоритм.

HI. Присвоить Vj <- Uj для О < < п.

Н2. Для /с = О, 1, ..., п - 1 (в таком порядке) присвоить Vj <- Vj + XqVj+i для j = n - 1, ..., fc + 1, fc (в таком порядке).

По окончании шага Н2 получим и(а; + а;о) = г;„а;"Н-----l-t;ia; + t;o. Эта процедура была

главной частью метода Горнера нахождения корней, и когда fc = О, она является точным правилом (2) вычисления и(а;о).

Метод Горнера требует (п+п)/2 умножений и (п +п)/2 сложений, но заметим, что, если iq = 1, все умножения опускаются. К счастью, можно свести общую задачу к случаю, когда xq - 1, введя сравнительно небольшое число умножений и делений.

51. Вычислить и запомнить значения Xq, ..., Xq.

52. Присвоить Vj <- UjX для О < j <n. (Сейчас v{x) = u(a;oa;).)

53. Выполнить шаг H2, только с а;о = 1. (Сейчас г;(а;) = и(а;о(а;+1)) = и(а;оа; + а;о).)

34. Присвоить Vj <- Vjjxi для О < i < п. (Сейчас v{x) = и{х + хо) как и требовалось.)

Эта идея, предложенная М. Шо (М. Shaw) и Ж. Ф. Траубом (J. F. Traub) [JACM 21 (1974), 161-167], обеспечивает такое же количество сложений и такую же численую \ стойчивость, как и метод Горнера, но при этом необходимы только 2n-1 умножений >! п - 1 делений, так как г;„ = и„. Приблизительно n этих умножений можно по очереди избежать (см. упр. 6).

Шо и Трауб отметили, что существует дополнительный способ экономии вре-м эни счета, если нужны только несколько первых или последних производных. На-поимер, если нужно вычислить только и(а;) и и(а;), то для выполнения следующего <!. [горитма потребуется 2n - 1 сложений и около п + V2n умножений и/или делений.

1.11. Вычислить и запомнить значения а;, х, ..., а;*, а;*, где t = \у/п/2

112. Присвоить Vj <- UjX для О < j <п, где f{j) = t-1- {{п -1 - j) mod 2t) для О < i < n, a /(n) = t.

IKI. Присвоить Vj < Vj + VjixSii для = n - 1, ..., 1, 0; здесь g{i) = 2t, когда n - 1 - i - положительный множитель 2t, иначе g{j) = 0 и нет необходимости умножать на а;*-.