некоторого в, лежащего между min(xo,..., х„) и тах(хо,..., если п-я производная существует и конечна. [Указание. Докажите тождество

/(Х0,Х1,...,Х„) = [ dtl [ dt2... [ "~dtnf\xoil-tl) + Xl{tl-t2) + Jo Jo Jo

+ Xn-litn-1 -tn)+ Xn{tn - 0)).

Эта формула также определяет /(жо, xi,..., когда Xj не различны.] (Ь) Если гц = f[xj), покажите, что aj = f{xo,... ,Xj) в интерполяционном полиноме Ньютона (42).

16. [М22] Как можно легко вычислить коэффициенты Щп]{х) = UnX-i-----huo, если заданы значения Хо, XI, ..., Xn-i, ао, ai, ..., q„ в интерполяционном полиноме Ньютона (42)?

17. [М20] Покажите, что интерполяционная формула (45) сводится к очень простому выражению, включающему биномиальные коэффициенты, когда Xk = хо + kh для О < к<п. [Указание. См. упр. 1.2.6-48.]

18. [М20] Если в схеме четвертой степени (9) сделать замену

у = {x + ao)x + ai, и{х) = {{у - х + а2)у + аз)а4,

какие формулы для вычисления aj в терминах Uk следует взять вместо (10)?

► 19. [М24] Объясните, как определить адаптированные коэффициенты Qo, Qi, Qs в (11) из коэффициентов us, щ, uo и{х), и найдите Oj для полинома и{х) = х + Ьх - 10х - 50х -Ь 13х -Ь 60.

► 20. [21\ Напишите программу для вычисления полинома пятой степени согласно схеме (11) для машины MIX. Попытайтесь сделать программу настолько эффективной, насколько это возможно, слегка модифицировав (11). Используйте в машине MIX арифметические операторы с плавающей точкой FADD и FMUL, описанные в разделе 4.2.1.

21. [20\ Найдите два дополнительных способа вычисления полинома -Ь 13х* -)- 49х* -Ь ЗЗх - 61х - 37а; -f- 3 по схеме (12), используя два корня (15), которые не рассмотрены в разделе.

22. [18\ В какой схеме вычисления - Зх* -- х - 2х 4- х - Зх - 1 используется метод Пана (16)?

23. [НМ30\ (Дж. Ив (J. Eve).) Пусть /(г) = а„г" -Ьо„ 1г"~ -Ь • -Ь Оо - полином степени п с действительными коэффициентами, имеющий по крайней мере п - 1 корней с неотрицательной действительной частью. Пусть

9{z) = а„2" + а„ 22"-= + • • • + а„ ,„od 2г" =, h{z) = a„ iz"- + a„ 3z"- + • • • + a(„ i) „,od2г""

Предположим, что h{z) не равно тождественно нулю.

a) Покажите, что g{z) имеет по крайней мере п -2 мнимых корней (т. е. корней, действительная часть которых равна нулю) и h{z) имеет по крайней мере п-3 мнимых корней. [Указание. Рассмотрите, сколько раз траектория /(г) обходит начало координат, когда Z перемещается по пути, показанному на рис. 16, для достаточно большого радиуса Д.]

b) Докажите, что квадраты корней g{z) = О и h{z) = О-все действительные числа.

Рис. 16. Доказательство теоремы Ива.

► 24. [М24] Найдите значения с и ак, Рк, удовлетворяющие условиям теоремы Е, для полинома и{х) - {х + 7){х + 6х + 10)(х + 4х + 5){х + 1). Выберите эти значения так, чтобы /Зг = 0. Приведите два различных решения.

25. [М20] Когда конструкция в доказательстве теоремы М применяется к неэффективной цепочке полиномов

Xl = ai + Ло, Лг = -Ло - Ло, Лз = Ai -Ь Ai, л4 = аг х Лз,

As = Ло - Ло, Ае = лв ~ As, л7 = ay X Лб, As = л7 х л7,

Лэ = Al X л4, Л10 = as - л9, All = Лз - Лю,

как можно /З1, /Зг, ..., /з9 выразить в терминах ai, ..., as?

► 26. [Afi] (а) Получите цепочку полиномов, соответствующих правилу Горнера вычисления полиномов степени п = 3. (Ь) Используя конструкцию из доказательства теоремы А, выразите ki, кг, кз и полином в конце цепочки и{х) в терминах /3i, /Зг, /Зз, /з4 и х. (с) Покажите, что множество полиномов в конце цепочки, полученное в (Ь), когда все /3i, /Зг, /з3 и /з4 независимо принимают все действительные значения, не содержит некоторые элементы множества, полученного в конце цепочки (а).

27. [М22] Пусть R - множество, которое включает все строки размерности (п + 1) действительных чисел (Яп, ,qi,qo), таких, что qn # 0. Докажите, что R имеет более п степеней свободы.

28. [НМ20] Покажите, что если /o(ai,... ,as), fsiai, ,аз)-полиномы от многих переменных с целыми коэффициентами, то существует ненулевой полином д{хо, ,Xs) с целыми коэффициентами, такой, что p(/o(ai,... ,as),... ,/s(ai,... ,as)) = О для всех действительных ai, ..., Qs- (Следовательно, любая цепочка полиномов с s параметрами имеет максимум s степеней свободы.) [Указание. Воспользуйтесь теоремами об "алгебраической зависимости", которые можно найти, например, у Б. Л. Ван дер Вардена (В. L. van der Waerden, Modern Algebra, translated by Fred Blum (New York: Ungar, 1949, раздел 64)). Русский перевод: Ван дер Варден, Современная алгебра. - М.: ОГИЗ, 1947.]

► 29. [М20] Пусть все Ri, R2, , Rm множества строк действительных чисел размерности {п + 1) имеют максимум t степеней свободы. Покажите, что объединение Л1 U Лг U • • • U Лт также имеет максимальное число степеней свободы t.

► 30. [ЛГЙ<?] Докажите, что цепочка полиномов с гпс операциями умножения в цепочке и Шр операциями умножения параметров имеет максимальное число степеней свободы, равное 2тс + гпр + 5отс- [Указание. Обобщение теоремы М показывает, что первое умножение в цепочке и каждое умножение параметров может, по существу, вводить только один новый параметр в множество результатов.]

31. [М23] Докажите, что цепочка полиномов, допускающая вычисление всех нормированных полиномов степени п, имеет по крайней мере [n/2j умножений и п сложений-вычитаний.

32. [М24] Найдите цепочку полиномов минимальной возможной длины, которая может вычислить все полиномы вида u4x* + u2x + ио. Докажите, что эта цепочка минимальна.

► 33. [М25] Пусть п > 3 нечетное. Докажите, что цепочка полиномов с [п/2\ + 1 шагами умножений не может вычислить все полиномы степени п, если она не имеет хотя бы п + 2 шага сложения-умножения. [Указание. См. упр. 30.]

34. [М26] Пусть Ло, Al, Лг-цепочка полиномов, в которой все шаги сложений и вычитаний - шаги параметра и среди которых имеется по крайней мере один параметр умножения. Предположим, что эта схема имеет тп умножений и к = г - т сложений-вычитаний и что вычисление полинома по цепочке имеет максимальную степень п. Докажите, что все полиномы, вычисляемые по этой цепочке, коэффициенты которых при х" не равны нулю, могут быть вычислены по другой цепочке, которая имеет максимум т умножений, максимум к сложений и не имеет вычитаний. Кроме того, последний шаг новой цепочки должен быть только умножением параметра.

► 35. [М25] Покажите, что любая цепочка полиномов, которая вычисляет полином общего вида четвертой степени, используя три умножения, должна иметь по крайней мере пять сложений-вычитаний. [Указание. Предположите, что существует только четыре сложения-вычитания, и покажите, что применимо упр. 34, поэтому схема должна быть частного вида, который не представляет все полиномы четвертой степени.]

36. [М27] Продолжая предыдущее упражнение, покажите, что любая цепочка полиномов, которая вычисляет обычный полином седьмой степени и использует только четыре умножения, должна иметь по крайней мере семь сложений-вычитаний.

37. [М21] (Т. С. Моцкин (Т. S. Motzkin).) Покажите, что "почти все" рациональные функции вида

{UnX + Un-lx"-~ + + u1x + ио)/{х" + Vn-ix"~ + + VlX + Vq)

с коэффициентами из поля S можно вычислить, воспользовавшись схемой

«1 + I3l/{x + а2+ Р2/{Х -Ь • • • -Ь РпЦх -Ь Qn+l) ))

для соответствующих aj, /3j из S. (Эта схема цепных дробей имеет п делений и 2п сложений; под "почти всеми" рациональными функциями понимаются все функции, за исключением тех, коэффициенты которых удовлетворяют некоторым нетривиальным полиномиальным уравнениям.) Определите и/3j для рациональной функции (а;-Ь 10а;--29)/(а;-Ь 8x4-19).

► 38. [НМ32] (В. Я. Пан, 1962.) Назначение данного упражнения-доказать, что правило Горнера действительно оптимально, если предварительно не адаптировать коэффициент. Необходимо произвести п умножений и п сложений для вычисления Unx" + - + uix+uo, если заданы переменные Un, , щ, ио, х и произвольные постоянные. Рассмотрим цепочки, такие, как раньше, но так, что Un, , ui, ио, х являются переменными. Например, можно сказать, что A-j-i = Uj, Ло = х. Чтобы показать, что правило Горнера наилучшее, удобно доказать более общую теорему. Пусть А = (atj), 0<i<m, 0<j< п, - действительная матрица размера {т+1) х {п + 1) и ранга п-Ь 1 и пусть В = {Ьо, . ,Ьш) -действительный вектор. Докажите, что любая цепочка, полиномов, которая вычисляет

Р{х; ио,..., Un) = (а.оио Н-----V UinUn + bi)x,

включает по крайней мере п умножений в цепочке. (Заметим, что это не только означает, что рассматривается несколько фиксированных цепочек, параметры Oj которых- определенные значения, зависящие от А и В. Это означает, что и цепочка, и значения