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

Теорема 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, где Q sQ xa o, 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, Q e(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^{n +1}» рав­ный P (x, a₀, a_ъ..., a_n), т. е. некоторый полином вида Ux^{n +1} + a_nxⁿ +...... +a_гx + a₀, где U e(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^{n +1}:

W (x, a ₀, a ₁,..., a_n)= P (x, a ₀, a ₁,..., a_n) (mod x^{n +1}) (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

Дата добавления: 2014-01-11