и шесть сложений параметров. Вычисления должны проводиться по одной из двух общих схем:

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

(х + Ах + Вх+ С)(х + Ах +Bx + D)+E,

а во втором - вида

(х* + 2Ах + {Е + А)х + ЕАх + Е){х + Лх + G) + Я; оба полинома содержат только пять независимых параметров.

37. Пусть ро{х) = и„х" + и„-1х"" + • • • + ио и qo{x) = х" + t;„ ix"~ + ••• + dq. Для 1 < j < п разделим pj-i(x) на нормированный полином gj-i(x) и получим Pj-i{x) - Qjgj i(x) + /3jqj{x). Предположим, что нормированный полином qj{x) степени п - j существует и удовлетворяет этому соотношению. Оно справедливо для почти всех рациональных функций. Пусть Pj{x) = gj i(x) - xvqj{x). Это определение означает, что deg(p„) < 1, поэтому можно положить a„+i = рп{х).

Для данной рациональной функции имеем

j aj Pj qj{x) pj(x)

0 x + 8x + 19 x + lOx + 29

1 1 2 x+5 3x + 19

2 3 4 1 5

значит, u{x)lv{x) = po{x)/qo{x) = 1 4- 2/(x 4- 3 + 4/(x 4- 5)).

Замечание. Обычная рациональная функция установленного вида имеет 2п 4- 1 "степень свободы" в том смысле, что она, по существу, имеет 2п + 1 независимых параметров. Если расширить понятие цепочки полиномов на понятие цепочки отношений полиномов, которые допускают операции деления так же, как и операции сложения, вычитания и умножения (см. упр. 71), то можно получить следующий результат с незначительными изменениями в доказательствах теорем А и М: цепочка отношений полиномов с q шагами сложений-вычитаний имеет максимум q + 1 степеней свободы. А цепочка отношений полиномов с т шагами умножений-делений имеет максимум 2т 4- 1 степеней свободы. Следовательно, цепочка отношений полиномов, которая вычисляет почти все рациональные функции заданного вида, должна иметь по крайней мере 2п сложений-вычитаний и п умножений-делений. Метод этого упражнения оптимален.

38. Если п = О, то теорема, несомненно, справедлива. Предположим, что п положительное и что задана цепочка полино.мов, которая вычисляет Р(х; ио,.,,, и„), где каждый из пара.метров aj заменен действительным числом. Пусть А, = Aj х At - первое умножение в цепочке, которое включает один из ио, и„; такой щаг должен существовать, если учесть значения ранга матрицы А. Без потери общности можно предположить, что Aj

включают в себя и„; таким образом, Aj имеют вид houo + • • + hnUn + fix), где ho,... ,hn - действительные, /i„ 5 О, и f{x)-полином с действительными коэффициентами, {hk и коэффициенты /(х) получены из значений, определяемых aj.)

Сейчас заменим шаг i шагом А; = ах Хк, где а - произвольное действительное число. (Можно взять Q = 0. Вообще говоря, а используется здесь только для того, чтобы показать достаточную гибкость доказательства.) Выполним дополнительно следующие шаги:

А = (а - fix) - houo-----h„-iUn-i)/hn-

Новые шаги включают только операции сложения и умножения (на подходящие новые параметры). Наконец всюду в цепочке заменим A-„-i = этим новым элементом А. В результате получим цепочку, которая вычисляет

Qix;uo,... ,«n-i) = Р(х;ио, . ,m„ i, (а - fix) - houo-----h„-iu„-i)/h„)

и имеет на одно умножение в цепочке меньше. Доказательство будет окончено, если можно показать, что Q удовлетворяет предположениям. Значение (а - fix))/h„ приводит к, возможно, уменьшенному значению т и новому вектору В. Если Ло, Ai, А„ - столбцы матрицы А (эти векторы линейно независимы относительно вещественных чисел), соответствующая матрице Q новая матрица А имеет вектор-столбцы

Ао - iho/h„)An, А„-1 - (/i„-i i„)A„

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

[Пан также показал, что деление не приводит к улучшению правила (см. Проблемы кибернетики 7 (1962), 21-30). Обобщения вычисления нескольких полиномов с несколькими переменными с различного рода предпосылками и без них рассмотрены Ш. Виноградом (S. Winograd, Comm. Pure and Applied Math. 23 (1970), 166-179).]

39. Индукцией no m. Пусть wix) = x"" -I- uzm-ix"" + + uq, Wm-iix) = x~ +

V2m~3x~ +----1- DO, a = Ql -I- 7m, 6 = Qm И ПуСТЬ

Следовательно, Vr = /(г + 2) для г > О и Sm = /(1)- Если Jm = О и а задано, то получим полином степени m - 1 от 6 с главным коэффициентом ±(«2m-i - та) = ±(72 Ч- • -I-7т - m7m).

в неопубликованных заметках Моцкин почти всегда полагал Sk = О, выбирая 71b таким образом, что основной коэффициент не равен нулю, когда тп четное, и равен нулю, когда тп нечетное. Тогда можно почти всегда предположить, что Ь - действительный корень полинома нечетной степени.

40. Нет; Ш. Виноград (S. Winograd) нашел метод вычисления всех полиномов степени 13 только с семью (возможно, комплексными) умножениями [Comm. Pure and Applied Math. 25 (1972), 455-457]. Л. Ревах (L. Revah) нашла схемы, которые вычисляют почти все полиномы степени п > 9 с [n/2j + 1 (возможно, комплексными) умножениями [SICOMP 4 (1975), 381-392]. Она также показала, что, когда п = 9, можно достичь [ri/2J + 1 умножений, но по крайней мере с п Ч- 3 сложениями. К слову, достаточно много операций сложения (см. упр. 39), оговорок "почти все" и "возможно, комплексными" исчезли. В. Я. Пан [STOC 10 (1978), 162-172; IBM Researcli Report RC7754 (1979)] нашел схемы с [n/2j + 1 комплексными умножениями и минимальным числом п + 2 + <5п9 комплексных

сложений для всех нечетных п > 9. Его метод для п = 9 имеет вид

v{x) = ((х + af + 0){х + 7), wix) = vix) + х, tiix) = (vix) + Ji)(w(x) + ei), t2{x) = (v{x) + J2)(w(x) + ег), u{x) = {hix) + C)(<2(x) - ti(x) + r,) + K.

МинимЕ1Льное число действительных сложений, необходимое, когда достигнуто минимальное число действительных умножений, для п >9 остается неизвестным.

41. а(с + d) - (а + b}d + i(a{c + d) + (Ь - а)с). [Остерегайтесь численной неустойчивости. Три умножения необходимы, поскольку в частном случае (71) с р{и) = + 1 умножение комплексное. Без ограничения на сложение существуют другие возможности. Например, в 1963 году Питером Унгером (Peter Ungar) предложена симметричная формула ac - bd + i{{a + b){c + d}-ac - bd). Равенство 4.3.3-(2) похоже на это с 2" в роли г. См. также работы I. Munro, STOC 3 (1971), 40-44; S. Winograd, Linear Algebra and its Applications 4 (1971), 381-388.]

Наоборот, если +b = 1 и ( = (1 - а)/Ь = 6/(1 4-a), то для вычисления произведения (а 4- Ы){с + di) = и + iv Оскар Банеман (Oscar Buneman) предложил алгоритм "w = с - td, v = d + bw,u = w- tv" [J. Сотр. Phys. 12 (1973), 127-128]. Этим методом, если a = cos9 и b - sinO, получаем t = tan(/2).

Гельмут Альт (Helmut Alt) и Ян Ван Ливен (Jan van Leeuwen) [Computing 27 (1981), 205-215] показали, что необходимо четыре действительных умножения или деления для вычисления 1/(а 4- Ьг) и достаточно четырех операций для вычисления

а а . {с/Ь)а b + ci ~ Ь + с(с/Ь) \ + с{с/Ь)

Шесть операций умножения-деления и три сложения-вычитания необходимо и достаточно для вычисления (а 4-Ьг)/(с 4-di) [Т. Lickteig, SICOMP 16 (1987), 278-311].

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

42. (а) Пусть т, Пт-это А;, соответствующие умножениям в цепочке, тогда щ = Pii-i X Pii и u(x) = P2m+i, где каждое Pj имеет вид /3j +Pjox + l3jnri +----l-/3jr(j)"r(j), где

< fj/2l - 1, и каждое Д и jSjk-полином от ai с целыми коэффициентами. Можно постоянно модифицировать цепочку таким образом (см. упр. 30), чтобы /3j = О и Pjr{j) = 1 для 1 < j < 2m. Более того, можно предположить, что /Ззо - 0. Множество результатов сейчас имеет максимум m -I-1 4- Е]Л\з- 1) = т 4-1 степеней свободы.

(b) Любая такая цепочка полиномов с максимум m умножениями может походить на одну из рассмотренных в п. (а) форм, но полагаем, что r(j) = fj/2] - 1 для 1 < j < 2m 4-1, и не предполагаем, что /Ззо = О или Pjr(j) = 1 для j > 3. Эта простая каноническая форма включает т -- 2т параметров. Так, как Qj пробегают все целые значения, и так, как мы проходим все цепочки, так и Pk пробегает максимально 2""+2" множеств значений по модулю 2. Следовательно, и множество результатов такое же. Для того чтобы получить все 2" полиномов степени п с 0-1 коэффициентами, должно выполняться т + 2т> п.

(c) Присвоим m ¥- \ \/п\ и вычислим х, х, ..., х"". Пусть и(х) = Mm+i(x)x""" 4- • • 4-«i(x)x" 4-«о(х), где каждое «j(x) -полином степени < m с целыми коэффициентами (значит, его можно вычислить, не увеличивая число умножений). Вычислим и{х) по правилу (2), как полином от х™, с известными коэффициентами. (Используемое число сложений приближенно равно сумме абсолютных значений коэффициентов. Таким образом, данный