D4. Присвоить Vj <- Vj + VjlX для j = n - 1, ..., 2, 1. Теперь vo/x° = u{x) и vi/xfW =u{x). I

Адаптация коэффициентов. Возвратимся к нашей первоначальной проблеме вычисления заданного полинома и{х) для "случайных" значений х настолько быстро, насколько это возможно. Важность данной проблемы отчасти является следствием того факта, что стандартные функции, такие как sinx, cosx, и т. д., обычно вычисляются подпрограммами, которые опираются на вычисление определенных полиномов. Поскольку такие полиномы часто вычисляются, желательно найти возможно наиболее быстрый метод вычислений.

Произвольные полиномы степени пять и выше можно вычислить, выполнив меньше операций, чем требуется по правилу Горнера, если сначала "адаптировать" коэффициенты uq, Ui, ..., u„. Как будет пояснено ниже, процесс адаптации может включать в себя уйму работы, но предварительное вычисление не является ненужной потерей времени, так как оно должно производиться только один раз, а полином вычисляется многократно. Примеры "адаптирования" полиномов для выполнения стандартных функций приводятся в работе В. Я. Пана, СССР Вычисл. матем. и матем. физика 2 (1963), 137-146.

Простейший случай, для которого адаптация коэффициентов полезна, встречается при использовании полиномов четвертой степени:

и{х) = Uix + изх + U2X + uix + Uo, щфО. (8)

Эту формулу можно переписать в виде, впервые предложенном Т. С. Моцкиным (Т. S. Motzkin),

у = {х + ао)х + а1, и{х) = {(у + х + а2)у + аз)а4, (9)

для соответственно "адаптированных" коэффициентов «о, Qi, а2, аз, 04. Вычисления по этой схеме включают три операции умножения, пять операций сложения и (на машине с одним сумматором, подобной машине MIX) одно указание запомнить промежуточный результат у во временном запоминаюшем устройстве. По сравнению с правилом Горнера в этой схеме мы заменили умножение сложением и, возможно, командой запоминания. Даже эта сравнительно малая экономия имеет смысл, если полином вычисляется часто. (Конечно, если время умножения сравнимо со временем сложения, (9) не дает улучшения: для вычисления обычных полиномов четвертой степени всегда требуется по крайней мере восемь арифметических операций.)

Сравнив коэффициенты в (8) и (9), получим формулы для вычисления aj, выраженных через Uk.

Qo = (гз/"4 - 1), /3 = m2/u4-Qo(Qo + 1), Qi = u1/u4 - Qo, Q2=/3-2qi, аз =Uo/ui-ai(ai+02), 04=4- (10)

Подобная схема вычисления полинома четвертой степени за такое же число шагов, как (9), предлагается в упр. 18; этот альтернативный метод дает в некоторых случаях большую точность, чем (9), хотя он уступает в точности другим.

Полиномы, встречаюшиеся на практике, часто имеют достаточно малый старший коэффициент, поэтому деление на u4 в (10) ведет к неустойчивости. В таком

случае предпочтительней на первом шаге заменить х на u4/a;, сводя (8) к полиному со старшим коэффициентом, равным ±1. Подобное преобразование применимо к полиномам более высоких степеней. Эта идея предложена Ч. Т. Файком (С. Т. Fike) [САСМ 10 (1967), 175-178]; он рассмотрел несколько интересных примеров.

Любой полином пятой степени можно вычислить, используя четыре умножения, шесть сложений и одно запоминание согласно правилу и{х) = U{x)x + щ, где U{x) = U5x + UiX + изх + U2X + ui вычисляется, как и в (9). Кроме того, можно произвести вычисление, выполнив четыре умножения, пять сложений и три запоминания, если вычисления осушествлялись по формуле

у = {х+ао), и{х) = {{{у + а1)у + а2){х + аз) + а4)а5. (И)

Для определения aj теперь требуется решить кубическое уравнение (см. упр. 19).

На многих компьютерах количество требуемых формулами (11) операций "запомнить" меньше трех; например, мы, возможно, сумеем вычислить [х + Qo), не запоминая х + ао- Действительно, большинство современных компьютеров имеет более одного арифметического регистра для вычислений с плаваюшей точкой, так что вполне можно обойтись без запоминания. Поскольку различные компьютеры для выполнения арифметических действий предоставляют большие возможности, в этом разделе следует учитывать только арифметические операции, а не операции запоминания и загрузки сумматора. Вычислительные схемы обычно простым способом можно адаптировать к любому конкретному компьютеру так, что понадобится несколько дополнительных операций; с другой стороны, следует помнить, 410 гти операции могут свести на нет экономию одного или двух умножений, в особенности если программа компилируется машиной не оптималшно.

Полином шестой степени и{х) = щх -I- • • -I- uix + щ всегда можно вычислить, используя четыре операции умножения и семь операций сложений, по схеме

Z = (х + ао)х + ai, W = {х + a2)z + аз,

и{х) = {{w + Z +a4)w+ а5)аб- (12)

[D. Е. Knuth, САСМ 5 (1962), 595-599.] Такая схема позволяет избежать двух из шести умножений, требуемых по правилу Горнера. Здесь снова необходимо решить кубическое уравнение: так как а = ue, можно предположить, что - 1. При этом предположении пусть

А=("5-1)/2, /32 =U4-i(l +1),

Pz=U3-pip2, /34=/3i-2, Pb=U2-plp3-

Допустим, что /Зб-вешественный корень кубического уравнения

22/ + (2А - /32 + 1)2/2 + (2/35 - /З2/З4 - /Зз)2/ + («i - = 0. (13)

(Это уравнение всегда имеет вешественный корень, так как левая часть полинома стремится к -Ьоо для больших положительных значений 2/ и к - оо-для больших отрицательных значений у; оно должно принимать значение "нуль" где-то посередине.) Если сейчас определить

/37 = /3б+/34/3б+/35, /38 = /Зз -/Зб -/З7,

то окончательно получим

ао = /З2 - 2/Зб, аг = /?! - ао, ai = /Зе - аоаг,

a3=/37-aia2, а4 =/Зе -/З7 - «5 = "о -/Зт/в (14)

Эту процедуру можно пояснить на следующем примере: предположим, нужно вычислить + 13х + 49а;* + ЗЗа; - 61х - 37х + 3. Получим ае = 1, /З1 = 6, /З2 = 7, /За = -9, /З4 = -1, /З5 = -7 и таким образом придем к кубическому уравнению

2уЗ gy2 + 2у+12 = 0. (15)

Это уравнение имеет корень /Зе - 2. Находим

/З7 = -5, /38 = -6, ао =3, аг = 3, ai = -7, аз = 16, а4 = 6, as = -27.

Следовательно, окончательная схема такова:

г = (а;--3)а;-7, w = {х + 3)z + 16, и{х) = (w + z + 6)w - 27.

Благодаря явному совпадению дважды появляющихся величин а; -Ь 3 можно найти метод, использующий три умножения и шесть сложений.

Другие методы подхода к решению уравнения шестой степени предложены В. Я. Паном [Проблемы кибернетики 5 (1961), 17-29]. Один из них требует на одну операцию сложения больше, но включает только рациональные операции на первых шагах; однако кубическое уравнение необходимо решать. Можно записать процесс решения в следующем виде:

г = (а; + ао)а; + ai, w = z + x + a2,

и{х) = {{{z - X + аз)ю + a4)z + 05)0. (16)

Для определения aj мы снова один раз делим полином на uq = а и таким образом приходим к нормированному многочлену и{х). Затем можно проверить, что «о = И5/З и

ai = (ui - аоиг + alus - aoU4 + 2ао)/(из - 2aoU4 + 5al). (17)

Заметим, что для метода Пана требуется, чтобы делитель в (17) не обращался в нуль. Другими словами, (16) можно использовать только тогда, когда

27u3ui - I8U6U5U4 + 5ul ф 0; (18)

в действительности это значение не может быть таким малым, поскольку а\ станет слишком большим. После того как а\ будет определено, остальные Qj можно определить из уравнений

/З1 = 2ао, /З2 = "4 - ao/3i - ol\,

/З3 = U3 - ао/Зг - ai/3i, /З4 = иг - аоРз - ai/Зг,

аз = (/Зз - (ао - 1)/Зг + (ао - 1){а1 - 1)) - аг,

аг = /Зг - (ац - 1) - аз - 2ai, а4 = /З4 - (аг + ai)(a3 + ai),

a5 = uo-ai/34. (19)