15. (а) Указание вытекает из интегрирования и индукции. Пусть /"() берется по всем значениям, лежащим между А и В включительно, когда в изменяется от min(xo,... ,х„ до тах(хо,... ,х„). Заменяя /" каждой из этих граней в вышеприведенном интеграле, получим Л/п! < /(хо,...,Хп) < В/п!. (Ь) Достаточно доказать это для j = п. Пусть / - интерполяционный полином Ньютона, тогда /" равна постоянной п!а„ [См. The Mathematical Papers of Isaac Newton, edited by D. T. Whiteside, 4 (1971), 36-51 70-73.]

16. Выполнить умножения и сложения (43), как операции над полиномами. (Частный случай, когда хо = xi = • • = х„, рассмотрен в упр. 2. Мы воспользовались этим методом на шаге С8 алгоритма 4.3.ЗТ.)

17. Например, когда п = 5, имеем

Уо byi 101/2 Юуз 5у4 У5

X - хо X - XI X - Х2 X - Хз X - Х4 X - Хз «[5](X) = -

1 5 . 10 10 5 1

Х-Хо X - XI X - Х2 Х-Хз X - Xi X -Хз

независимо от значения h.

18. Qo = {из/и4 + 1), /3 = U2/U4 - Qo(ao - 1), ai = «о/? - U\JU4, 02 = 0 - 2qi, аз =

Uo/U4 - Qi(qi + Q2), 04 = U4.

19. Поскольку Qs-основной коэффициент, можно предположить без потери общности, что и{х) - нормированный полином (т. е. что us = 1). Тогда qo - корень уравнения 40г - 24u4z + (4и4 + 2из)г + («2 - «34) = 0. Это уравнение всегда имеет по крайней мере один действительный корень, а может иметь три. Поскольку Qo определено, получим Q3 = U4 - 4qo, Qi = Из - 4qoQ3 - 6qo, Q2 = Hi - qo(qoQi + 4qoQ3 + 2qiQ3 + Qo), Q4 = И0 - Q3(Qo + aio + 012).

Для заданного полинома решим кубическое уравнение 40г - 120г + 80г = 0; это приведет к трем решениям: (ао, Qi, Q2, аз, а4, аз) = (О, -10,13, 5, -5,1), (1, -20,68,1,11,1), (2,-10,13,-3,27,1).

20. LDA X STA ТЕМР2 FADD =ai= FMUL TEMPI FADD =аз= FMUL TEMP2 FMUL TEMP2 FADD =a4 = STA TEMPI- STA TEMP2 FADD =a2= FMUL =a5= I FADD =ао-аз=

21. г = (x + l)x - 2, и; = (x + 5)г + 9, и(х) = (w + г - 8)и; - 8; or z = (x + 9)x + 26, и; = (x - 3)г + 73, и(х) = {w + z - 2A)w - 12.

22. as = 1, ao = -1, ai = 1, /З1 = -2, P2 = -2, /З3 = -2, /З4 = 1, аз = -4, a2 = 0, Q4 = 4, аз - -2. Образуем г = (x - l)x + 1, и; = г + хи и(х) = ((г - x - 4)и; + A)z - 2. Одно из семи суммирований можно сэкономить, если вычислить и; = х + 1, г = и; - х.

23. (а) Можно применить индукцию по п; результат тривиальный, если п < 2. Если /(0) = О, то результат справедлив для полинома f{z)lz; значит, он выполняется и для f{z). Если f{iy) = О для некоторого действительного у 5 О, то g{±.iy) = h{±iy) = 0. Так как результат справедлив для f{z)/{z+у), он выполняется и для f{z). Следовательно, можно предположить, что f{z) не имеет корней, действительная часть которых равна нулю. Сейчас точное количество обходов от начала координат траекторией равно числу корней f(z) внутри области, которых не больше одного. Когда R большое, траектория f{Re*) для 7г/2 < t < Зж/2 будет обходить начало координат по часовой стрелке приблизительно п/2 раз, так что траектории f{it) для -R < t < R должны обходить начало координат

против часовой стрелки по крайней мере п/2 - 1 раз. Для четного п это означает, что f{it) пересекает мнимую ось по крайней мере п - 2 раз и действительную ось - п - 3 раз. Для п нечетных f{it) пересекает действительную ось по крайней мере п - 2 раз и мнимую ось - п - 3 раз. Это и будут корни g{it) = О и h{it) = О соответственно.

(Ь) Если нет, то д или h должны иметь корни вида а + ЫсафОяЬфО. Но должно подразумеваться существование хотя бы трех других корней, а именно а - Ы и -а ± Ы, тогда как g{z) и h{z) имеют максимум п корней.

24. Корнями и являются -7, -3 ± г, -2 ± г и -1; допустимые значения с равны 2 и 4 (но не 3, так как при с = 3 сумма корней равна нулю). Случай 1, с = 2: р{х) = (х + Ъ){х + 2х + 2)(хЧ1)(х-1) =хЧбхЧбхЧ4хЗ-5х2-2х-10; (х) = &х+Ах-2 = 6(х + 1)(х-). Пусть Q2 = -l,ai = ;pi(x) =х + 6хЧ5х2-2х-10 = (x2 + 6x + f )(x2-i)-:; qq = 6, Ро = Щ, P\ = -Ц. Случай 2, с = 4: аналогично получаем Q2 = 9, qi = -3, qo = -6, Ро = 12, Pi = -26.

25. Pi = Q2, P2 = 2ai, Рз = av, Pa = ao, Ps = Po = 0, /З7 = Qi, Pa = 0, /З9 = 2qi - as.

26. (a) Al = Ql x Ac, A2 = Q2 + Al, A3 = A2 x Ao, A4 = Q3 + A3, A5 = A4 x Ao, Ae = Q4 + As-

(b) Kl = 1 + PlX, K2 = 1 + P2K1X, «3 = 1 + P3K2X, U{x) = P4K3 = Р\Р2РзР4Х + Р2РзР4х +

/З3/З4Х+/З4. (с) Если любой коэффициент равен нулю, то коэффициент при х также должен быть нулем в (Ь), в то время как (а) дает произвольный полином qix + а2Х + Q3X + Q4 степени < 3.

27. Иначе должен существовать ненулевой полином f{qn,--,qi,qo) с целыми коэффициентами, такой, что qn fiqn,.-,q\,qo) = О для всех множеств действительных чисел iqn,--,qo)- Это невозможно, так как легко доказать индукцией по п, что ненулевой полином всегда принимает ненулевые значения. (См. упр. 4.6.1-16. Однако этот результат несправедлив, если рассматривать конечные поля вместо полей действительных чисел.)

28. Неопределенные величины qi, q образуют алгебраический базис для области полиномов Q[qi, ... ,Qs], где Q - поле рациональных чисел. Так как s + 1 больше числа элементов базиса, то полиномы fj{ai,...,as) алгебраически зависимы. Это означает, что существует ненулевой полином д с рациональными коэффициентами, такой, что 5(/o(qi, ... ,Qs),..., /5(01,... ,Qs)) тождественно равен нулю.

29. Пусть заданы jo, ..., jt 6 {0,1,..., n}. Существуют ненулевые полиномы с целыми коэффициентами, такие, что gj{qjo, ,qji) = О Для всех iqn,...,qo) в Rj, 1 < j < т. Поэтому произведение gig2...gm равно нулю для всех (д„,..., 50) в Д1 U • U Rm-

30. Начиная с конструкции в теореме М, докажем, что тпр + (1 - Some) из Рк можно эффективно исключить. Если pi соответствует параметру умножения, то pi = /32t-i х (T2i + P2i). Нужно прибавить cP2i-iP2i к каждому Pj, для которого срг появляется в Tj, и заменить Pii нулем. Это приведет к удалению одного параметра для каждого умножения параметров. Если pi-первое умножение в цепочке, тор; = (7ix + 6i+/32t-i)x (72х + 2 4- P2i), где 71, 72, 01, 2 -полиномы от /?!, ..., P2i-2 с целыми коэффициентами. Здесь dl и в2 может быть "поглощено" P2i-1 и Pii соответственно. Таким образом, можно предположить, что i = 2 = 0. Сейчас добавим cP2i-\P2i к каждому Pj, для которого cpi появляется в Tj; добавим /321-172/71 к /Зг; и положим P2i-\ равным нулю. Множество результатов не изменится после этого удаления P2i-\, кроме величин qi, ..., q, таких, что 71 равно нулю. [Это доказательство, по существу, предложено В. Я. Паном, Успехи мат. наук 21,1 (Январь-февраль, 1966), 103-134.] Последний случай можно рассмотреть, как в доказательстве теоремы А, поскольку полиномы с 71 = О можно вычислить, устраняя /Зг; (как и в первой конструкции, где щ соответствует умножению параметра).

31. В противном случае можно добавить одно умножение параметра в качестве последнего шага и прийти к противоречию теоремы С. (Данное упражнение является улучшенным

вариантом теоремы А в этом частном случае, поскольку существует только п степеней свободы для коэффициентов нормированного полинома степени п.)

32. Al = Ао X Ао, Аз = Qi X Ai, A3 = аг + Аг, А4 = Аз х Ai, А5 = аз + А4. Необходимо по крайней мере три умножения, чтобы вычислить uax* (см. раздел 4.6.3), и по крайней мере два сложения по теореме А.

33. Необходимо иметь п + 1 < 2тс + тр + Jomc и Шс + гПр = (п + 1)/2. Таким образом, не существует умножений параметров. Сейчас первые Ai, главный коэффициент которых (как полиномов от х) не является целым числом, должны быть получены посредством сложения в цепочке и должен существовать по крайней мере п + 1 параметр. Таким образом, должно быть хотя бы п + 1 сложений параметров.

34. Преобразовать данную цепочку шаг за шагом и также определить "содержание" Ci в Ai следующим образом (интуитивно понятно, что Ci-старший коэффициент в Ai). Определим со = 1. (а) Если шаг имеет вид Ai = aj + Хк, заменить его шагом вида Ai = fij + Хк, где /3j = aj/ck, и определить Ci = Ск- (Ь) Если шаг имеет вид Ai = aj - Хк, заменить его шагом Ai = /3j + Хк, где /3j = -Oj/ck, и определить а = -Ск- (с) Если шаг вида Ai = aj х Хк, заменить его шагом Ai = Хк (шаг будет позже удален) и определить Ci = ajCib. (d) Если шаг имеет вид Ai = Aj х Хк, оставить его без изменения и определить

Ci = CjClt.

После того как этот процесс будет завершен, удалить все шаги вида Ai = Afc, заменяя Ai на Хк в каждом последующем шаге, который использует Aj. Затем добавить последний шаг Аг+1 = /3 X Аг, где /3 = Сг- Это и есть требуемая схема, так как легко проверить, что новые Ai-это только старые Ai, деленные на множитель а. f3k-заданные функции от aj; деление на нуль-не проблема, так как, если какое-то Ск = О, должно быть Сг = О (следовательно, коэффициент при х" равен нулю); иначе Аь никогда не приведут к окончательному результату.

35. Так как существует по крайней мере пять шагов параметров, результат тривиален, если не существует хотя бы одного умножения параметров. Рассмотрим метод, в котором три умножения могут образовать u4x*. Мы видим, что должно быть три умножения параметров и два умножения в цепочке, поэтому четыре сложения-вычитания должны быть шгиами параметров и упр. 34 применимо. Сейчас можно предположить, что используются только операции сложения и что имеется цепочка вычисления общего вида нормированного полинома четвертой степени с двумя умножениями в цепочке и четырьмя сложениями параметров. Единственно возможная схема такого вида, которая вычисляет полином четвертой степени, имеет вид

Al = ai + Ао Аг = аг + Ао Аз = Al X Аг А4 = аз + Аз А5 = а4 + Аз Аб = А4 X Аб А? = Q5 + Аб

Фактически эта цепочка имеет на одну операцию сложения больше, чем нужно, но любая корректная схема может быть задана в таком виде, если одни из ак являются функциями от других aj. А? имеет вид {х + Ах + В){х + Ах + С) + D = х* + 2Ах + {Е + А)х + ЕАх + F, где А = ai + Q2, В = ааг + аз, С = а\а2 + at, D = а&, Е - В + С, F = ВС + D. Поскольку они содержат только три независимых параметра, то А? не может представлять нормированный полином четвертой степени общего вида.

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