Оптимальность схемы Горнера

Теорема D.l.Пусть n— произвольное неотрицательное целое чис­ло. Не существует алгоритма, который, используя только сложение, вычитание и умножение, позволяет вычислять значение

a_nxⁿ + ... + a₁x + a₀ (D.l)

по числам x,a₀,a₁,...,a_n так, что количество сложений илиумноже-ний всегда оказывается меньше n.

В терминах нижних границ это утверждение можно, очевидно, переформулировать следующим образом.

Пусть З⁶ — класс алгоритмов, вычисляющих значение (D.1) с помо­щью операций сложения, вычитания и умножения. Будем рассматри­вать число n как размер входа x,a₀,a₁,...,a_n. Тогда n является ниж­ней границей как аддитивной сложности (измеряемой числом сложе­ний и вычитаний в худшем случае), так и мультипликативной слож­ности (измеряемой числом умножений в худшем случае) алгоритмов класса З⁶.

Несколько предварительных соглашений и замечаний. Во-первых, будем для определенности считать, что все коэффициенты полино­ма, а также значение x принадлежат полю рациональных чисел Q, хотя достаточно было бы потребовать, например, чтобы они принад­лежали произвольному бесконечному полю. Во-вторых, ограничимся операциями сложения и умножения; позднее мы покажем, что при­влечение вычитаний не является существенным. В-третьих, заметим, что любой алгоритм, который использует только операции сложения и умножения и который вычисляет значение произвольного полино­ма фиксированной степени n по заданному x, можно записать в виде линейной (неветвящейся) программы, одной и той же для всех по­линомов степени n (так как в используемом наборе операций нет операций сравнения). В качестве программных переменных мы бу­дем использовать p с тем или иным целым индексом. Шагом про-

Приложение D

граммы является некоторое присваивание. Подготовительный раздел программы содержит присваивания

P-n-1:=an; ...; P-1:=a0; Р0:=^х (D.2)

и, возможно, ряд присваиваний вида р_к:= ..., к<-п - 1, с конкрет­ными числами в правой части (т. е. можно запасти константы, нуж­ные в вычислениях). Вычислительный раздел программы состоит из присваиваний вида

_Pi:=p_k, k<i, (D.3)

и

Pi:=Pk<>P, Kl<i, ое {+,■}. (D.4)

Значение индекса в левой части будем считать номером шага, пред­полагая, что все используемые в программе значения индекса за­полняют целиком некоторый отрезок множества целых чисел. Шаг вида (D.4) будем называть аддитивным или мультипликативным в зависимости от вида о (+ или •). Шаг вида (D.3) будем называть нейтральным. Каждую программу такого вида, вычисляющую значе­ние (D.1) и обладающую тем свойством, что, не меняя ее вычисли­тельного раздела, а лишь варьируя правые части в (D.2), мы можем получать значения любых полиномов степени п в любых точках, мы назовем п-программой.

Наша цель состоит в доказательстве того, что каким бы ни бы­ло неотрицательное целое п, любая n-программа содержит не ме­нее п аддитивных и не менее п мультипликативных шагов.

Если в n-программе изменить шаги с номерами 0, -1,..., -п - 1, подставляя в правые части присваиваний (D.2) вместо чисел х, а₀, а₁, ...,а_п их буквенные обозначения, и интерпретировать +, • в вы­числительном разделе как знаки полиномиальных операций, то в ре­зультате выполнения n-программы значениями P1,p₂, ... будут поли­номы (т.е. буквенные выражения, «картинки»). В частности, будет построен полином а_пх^п + ... + а₁х + а₀, причем а_п, ...,а₁,а₀ и х яв­ляются переменными этого полинома (степень по х которого рав­на п, а степень, например, по а_п равна 1). При таком подходе каждая n-программа вычисления значения полинома превращается в про­грамму построения полинома

Р(х, а₀, а₁,...,а_п) = а_пх^п +... + а₁х + а₀ е Q[x, а₀, а₁, ..., а_п] (D.5)

с помощью операций сложения и умножения, исходя из переменных х,а₀,а₁,...,а_п. Программу обсуждаемого вида, содержащую в под-

Оптимальность схемы Горнера

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

Лемма D.I.Пусть n^О, S — формальная n-программа, t — поло­жительное целое, не превосходящее наибольшего значения индекса пе­ременной p в S. Пусть среди шагов S с номерами 1,2,..., t нет ад­дитивных, в которых по крайней мере один операнд правой части зависит от a_n (имеет положительную степень по a_n как полином от x, a₀, a_ъ..., a_n). Тогда после выполнения S каждый из полиномов pi,p2,---,pt либо не зависит от a_n, либо кратен a_n (может быть записан в виде a_nQ, где QsQxao,a,...,a_n]).

Доказательство. Индукция по t. Для t = 1 утверждение очевидно.

Пусть t > 1 и утверждение леммы верно для 1, 2,..., t - 1. Для шага с номером t имеется три возможности:

pt:=pk> pt:=pk+pl> pt'-=pk'ph

k,l^t-l. При осуществлении первой возможности требуемое непо­
средственно следует из предположения индукции. При второй воз­
можности из сказанного в условии леммы относительно аддитивных
шагов следует, что p_t не зависит от a_n. При третьей возможности
любой из полиномов p_k, p_l может быть либо кратным a_n, либо не
зависеть от an; в обоих случаях получаем то, что нам нужно. □

Лемма D.2.Каждая формальная n-программа S, n^О, построения полинома P вида (D.5) содержит не менее n аддитивных шагов.

Доказательство. Индукция по n.

Для n = Оутверждение очевидно.

Пусть n > 0 и утверждение леммы верно для 0,1,..., n - 1. Предпо­ложим, что S содержит менее n аддитивных шагов. Ясно, что в S име­ется по крайней мере один аддитивный шаг такой, что по крайней мере один из его операндов зависит от a_n. В силу леммы D.1 первый такой шаг будет иметь по крайней мере один операнд, являющийся кратным a_n полиномом. Пусть этот шаг имеет вид p_i :=p_k + p_l , и зна­чением p_k (именно этот операнд мы берем только для определенно­сти) является полином a_nQ, Qe(Q)[x,a₀, a_ъ ...,an]. Если в S заменить шаг p-_n-! :=a_n на p _-n-х :=0, а шаг p_i :=p_k + p_l —на p_i :=p_l, то, оче­видно, получится формальная (n- 1)-программа построения полино-

Приложение D

ма a_n-_гxⁿ +... + a_гx + a₀, содержащая менее чем n - 1 аддитивных
шагов. Противоречие. П

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

Во-первых, мы будем рассматривать формальные n-программы, которые строят полином, возможно лишь «по модулю xⁿ⁺¹» рав­ный P(x, a₀, a_ъ ..., a_n), т. е. некоторый полином вида Uxⁿ⁺¹ + a_nxⁿ + ... ... +a_гx + a₀, где Ue(Q>[x, a₀, a_г,...,a_n], и при этом конкретный вид U может быть любым, и он нас не будет интересовать. Мы согласны, та­ким образом, получить любой полином W(.x,a₀,a_ъ ..., a_n) такой, что разность W{x, a₀, a_ъ ..., a_n) -P{x, a₀, a_ъ ...,a_n) делится на xⁿ⁺¹:

W(x,a₀,a₁,...,a_n)=P(x,a₀,a₁,...,a_n) (mod xⁿ⁺¹) (D.6)

(этим мы фактически расширяем понятие формальной n-програм­мы). Во-вторых, мы будем исследовать число существенно мульти­пликативных шагов, т.е. таких шагов вида p_i :=p_k -p_l , для которых k,l ^ -n - 1; последнее означает, что операнды таких шагов не явля­ются заранее запасенными константами. Ясно, что если для постро­ения любого полинома W(x, a₀, a_ъ ..., an), удовлетворяющего (D.6), не существует формальной n-программы, содержащей менее n суще­ственно мультипликативных шагов, то, в частности, не существует и формальной n-программы для построения P(x, a₀, a_ъ ...,a_n), содер­жащей менее n мультипликативных шагов.

Лемма D.3.Пусть n^О, S — формальная n-программа, t— поло­жительное целое, не превосходящее наибольшего значения индекса пе­ременной p в S. Пусть среди шагов S с номерами 1, 2,..., t нет суще­ственно мультипликативных, в которых по крайней мере один опе­ранд правой части зависит от a_n. Тогда после выполнения S каждый из полиномов p\,p2,---,pt либо не зависит от a_n, либо имеет вид ca_n + Q, где c е Q \ {0} и полином Q не зависит от a_n.

Доказательство аналогично доказательству леммы D.I. □

Лемма D.4.Каждая формальная n-программа S построения како­го-либо W, удовлетворяющего (D.6) при P = a_nxⁿ + ... + a_гx + a₀, со­держит не менее n существенно мультипликативных шагов.

Доказательство. Индукция по n. Для n = 0 утверждение очевидно.

Пусть n > 0 и утверждение леммы верно для 0,1,..., n - 1. Пусть S — формальная n-программа построения некоторого полинома

Оптимальность схемы Горнера

У/{х,а₀,а_ъ...а_п), удовлетворяющего (D.6). Предположим, что в S меньше чем п существенно мультипликативных шагов. Покажем, что в таком случае можно построить формальную (п- 1)-программу, в которой меньше чем п - 1 существенно мультипликативных шагов, и тем самым получить противоречие с предположением индукции.

В силу леммы D.3 формальная n-программа S содержит по край­ней мере один существенно мультипликативный шаг, по крайней мере один из операндов которого зависит от а_п. Пусть

Pi :=Рк 'Pi (D.7)

будет самым первым таким шагом, и пусть значением р_к явля­ется полином вида са_п + Q(x, а₀,а_г, ...,а_п-_г), с Ф 0. Тогда удале­ние из S всех шагов с номерами, большими i - 1, и замена шага р_-п-х := а_п шагом р_-п-х := 0 дает программу S'', получающую поли­ном 0_{х,а₀,а_ъ...,а_п-_г) в качестве значения переменной _Рк. Пусть т—наименьшее значение индекса переменной р, встречающееся в S'. Добавим к S' шаг _Рт-_г := с', где с' = -1/с, и шаг _Pi :=_Рт-_г ■ _Рк, который, заметим, не является существенно мультипликативным. Получаемая

программа строит полином -Q(x, а₀, а_г,..., а_п-₁); существенно муль­типликативных шагов в ней на единицу меньше, чем среди шагов с номерами 1, 2,..., i в S. Обозначим эту программу через S".

Дальнейшие преобразования программы S имеют целью получе­ние такой программы, которая содержит не более п - 1 существенно мультипликативных шагов и при этом находит некоторый полином, по модулю х^п равный а_п-_гх^п-г + ... + а_гх + а₀. Мы видим, что если бы значением р-_п-х было не а_п, а тот полином, который строится с помощью S", то i-й шаг S привел бы к присваиванию перемен­ной р; значения 0, а после окончания выполнения всех шагов мы бы получили

W = W{x, а₀, а_ъ ..., а_п-_ъ c'Q{x, а₀, а_ъ ..., a_n-i)).

В силу (D.6) подстановка a_n = c'Q{x,a₀,a₁, ...,a_n-₁) в W даст нам

W = Р{х, а₀, а_ъ ...,а_п-_ъ c'Q{x, a₀, а_ъ ..., а_п-_г)) +

+ U\x,a₀,a₁,...,a_n-₁)xⁿ⁺¹.

Принимая во внимание равенство Р = а_пх^п +... +а_гх + а₀, получаем W'eQ[x,a₀₎a₁,...a„-₁] и

W^/ = a„-₁xⁿ-¹ + ...+a₁x + a₀ (mod х").

Отбросим предварительный раздел формальной n-программы S и запишем шаги ее вычислительного раздела вслед за S", преобразуя

Приложение D

эти шаги следующим образом:

(a) если шаг не является шагом (D.7) или существенно мультипли­кативным шагом вида p_t := p_r • p_s, t ^ k, то увеличиваем на i индекс в левой части и увеличиваем на i каждый из положительных индек­сов в правой части (неположительные индексы не изменяются);

(b) в правых частях всюду заменяем p-_n-х на p_i;

(c) каждый существенно мультипликативный шаг вида p_t :=p_r-p_s, t^k, заменяем нейтральным шагом p_t+i :=p_t;

(d) шаг (D.7) заменяем нейтральным шагом p_2i :=p-n-i.

Прибегая к замене (c), мы пользуемся независимостью от a_n полино­
мов, являющихся значениями p_r и p_s, это позволяет не дублировать
существенно мультипликативные шаги, содержащиеся в S"; заверша­
ющая замена (d) приводит нас к формальной (n - 1)-программе по­
строения W', имеющей менее n - 1 существенно мультипликативных
шагов. □

В силу сказанного ранее, из лемм D.2, D.4 следует теорема D.1^г.

Заметим, что замена каждого вычитания сложением с дополни­тельным домножением второго операнда на -1 не меняет числа су­щественно мультипликативных шагов. Поэтому доказательство тео­ремы D.1 сохраняет силу при рассмотрении сложения и вычитания в качестве аддитивных операций.

Известен алгоритм, который для вычисления значения произволь­ного полинома n-й степени требует n сложений и n умножений, это алгоритм («схема») Горнера:

a_nxⁿ + a_n-_гxⁿ-^г + ...+a₁x + a₀ = {... {a_nx + a_n-_г)x + ... + a_г)x + a₀.

Таким образом, мы получили следующий результат:

Если рассматривать n в качестве размера входа

x,a₀,a₁, ...,a_n,

то как по числу сложений, так и по числу умножений схема Горнера является оптимальным в худшем случае алгоритмом вычисления зна­чения a_nxⁿ +... + a_гx + a₀ с помощью операций сложения и умножения.

Разумеется, полиномы какого-либо частного вида, как, например, xⁿ, могут вычисляться с меньшими затратами.

¹ В 1962 г. В.Я. Пан доказал утверждение теоремы D.1 в несколько более общей фор­ме— см., например, [19, разд. 4.6.4, упр. 38]. Главные идеи доказательства, приведен­ного выше в этом приложении, взяты из [57].

Приложение E