AOP_Tom2 (1021737), страница 156
Текст из файла (страница 156)
Ое уапб) и Я. Ван Лиивен (Л чав Ьееинеп).) Покажите, как можно улучшить шаги 81, ..., 84 алгоритма Ша-Трауба (8Ьан-ТгааЬ), вычисляя Джонг Л. С. (3апб, Пенке бусве бе) Ван Лиивен Ж. (чае Ьеепъеп, Юав) Ша М. М. (8Ьан, Магу Магбаге!) Трауб Ж. Ф. (ТганЬ, 1аверЬ Ргебег!сй) только приблизительно -'и степеней хв 7. [М25] Как можно вычислить Но, ..., В, когда (б) имеет значение в(хо+/г?ь) для всех целых ?г? 8.
[М20] Факториальная степень хь определяется таким образом: М (*,] = (х — 1)...(х — й + 1). Объясните, как вычислить и ха+ . -. + гмхт+ ио с максимум и умножениями н 2и — 1 сложениями, начиная с х н и + 3 постоянных и„,..., во, 1, и — 1. 9. [М25) (Г. Дж. Райзер (Н. Л. Нувег).) Покажите, что если Х = (хп) — матрицаразмера и х и, то р-(Х) =',~„(-1)"-" " П ): ь« г<1< Суммирование осуществляется по всем 2" наборам ец ..., е„, независимо равным О или 1.
Подсчитайте количество операций сложения и умножения, требуемых для вычисления рег(Х) по приведенной формуле, 10. [М21] Перманент матрицы Х = (хо) размера и х и можно вычислить следующим образом: начать с и величин хп, хгг, ..., хг . Для 1 < Й < и предположим, что (ь) величин Аьв вычислены для всех подмножеств множества Б, (1, 2,..., и), содержащих ?г элементов, где Аьв = ~ хгп ... хьм суммируется по всем й! перестановкам 11,.1ь элементов множества Я; затем составляются все суммы вида Арене = ) Амвпгггх(ь.ьцх гав Мы получим рег(Х) = А„П „Р Сколько операций сложения и умножения потребуется для этого метода? Сколько ячеек понадобится для временного хранения? 11.
[М45] Существует ли какой-нибудь метод вычисления перманента обычной матрицы размера и х и, использующий менее 2" арифметических операций? 12. [М50] Каково минимальное количество умножений, неебходимых для получения произведения двух матриц размера и х иг Чему равен наименьший показатель ог, такой, что 0(и "') умножений достаточно для всех е > Ог (Найдите хорошие верхнюю и нижнюю грани как для малых, так и для больших и.) 13. [М28] Найдите преобразование, обратное обычному дискретному преобразованию Фурье (37), выразив Е(1г,...,1„) в терминах значений /(вп..., в„). [Указание.
См. уравнение 1. 2,9 — (13) .] ь 14. [НМВВ] (Быстрое иреобравование Фурье.) Покажите, что с помощью схемы . (40) можно вычислить одномерное дискретное преобразование Фурье /(в) = ~ Е(1)ог", ш= ег"Мг, О < в < 2", о<с<в" используя арифметику комплексных чисел.
Оцените число выполняемых арифметических операций. ь 1Б. [БМ28] и-е равностное оганошенпе /(хо, хп..., х„) функции /(х) в и ь 1 различных точках хо, хь..., х определяется формулой /(хо, хм,х„) = (/(хо, хь...,х„-г) — /(хп..., х -г, х„))/(хо — х ) длЯ и > О. Таким обРазом, /(хо,хь...,х„) = 2 " о/(хь)/П 1<„й„(хь — хг) — симметричная функция и+ 1 аргументов. (а) Докажите, что /(хо,...,х ) = /рй(О)/и! для некоторого д, лежащего между ппп(хо,...,х„) и шак(хо,..., х„), если и-я производная 100(х) существует и конечна. [Указание.
Докажите тождество г' г' г'— 1(хо хм,х ) = / 4?41/ Взз.../ Вс„/" (хо(1 — 14) +х4(П вЂ” сз) +. о о о + х -3(с -1 — с ) + х (1 — О)). Эта формула также определяет у(хо,хм...,х„), когда х, не разлнчны.] (Ь) Если дз ж У(х?), покажите, что аз -- 1(хо,..., х,) в интерполяционном полиноме Ньютона (42). 16. [МЯУ] Как можно легко вычислить коэффициенты и~„1(х) = и„х" + +во, если заданы значения хо, хп..., х н па, ам..., п„в интерполяционном полиноме Ньютона (42)? 17. [Мдд] Покажите, что интерполяционная формула (45) сводится к очень простому выражению, включающему биномнальные коэффициенты, когда хь = ха +?45 для О < й < и.
[Указание. См. упр. 1.2.6-48.] 16. [Мдд] Если в схеме четвертой степени (9) сделать замену у= (к+по)х+пм и(х) = ((у — к+аз)у+аз)а4, какие формулы для вычисления со, в терминах иь следует взять вместо (10)? ь 19. [М24] Объясните, как определить адаптированные коэффициенты по, ам ..., по в (11) из коэффициентов ио, ..., им ио и(х), н найдите аз для полинома и(х) = х + бх — 10хз — 50х + 13х + 60.
° 20. [81] Напишите программу двя вычисления паоинома пятой степени согласно схеме (11) для машины ИХХ. Попытайтесь сделать программу настолько эффективной, насколько это возможно, слегка модифицировав (11). Используйте в машине И1Х арифметические операторы с плавающей точкой ГАОО и рИШ., описанные в разделе 4.2.1. 21. [Вд] Найдите два дополнительных способа вычислении полииама хо + 13хо + 49хо + 33хз — 61хз — 3?х+ 3 по схеме (12), используя два корня (15), которые не рассмотрены в разделе 22. [1В] В какой схеме вычисления хо — Зхз + х4 — 2хз + хз — Зх — 1 используется метод Пана (16)? 23.
[НМВВ] (Дж. Нв (Л. Ече).) Пусть 1(з) = а„х" + а„4х" '+. + ао — полипом степени и с действительными коэффициентами, имеющий по крайней мере и — 1 корней с неотрицательной действительной частью. Пусть -з зо д(з) =а з +а -гз + +ао оезх о-4 и-3 1 — 1) мое з 5(з) =а 4з +во зз + . +а1„0 оозз Предположим, что 5(з) не равно тождественно нулю. а) Покажите, что д(з) имеет по крайней мере и — 2 мнимых корней (т. е. корней, действительная часть которых равна нулю) и?4(х) имеет ио крайней мере н-3 мнимых корней.
[Указание. Рассмотрите, сколько раз траектория у(г) обходит начало координат, когда з перемещается по пути, показанному на рис. 16, для достаточно большого радиуса В.] Ь) Докажите, что квадраты корней д(х) = 0 и 5(з) = 0 — все действительные чигла.
Рис. 16. Доказательство теоремы Ива. о 24. (лЩ] найдите значения с и ав, тул, удовлетворяющие условиям теоремы е, для полинома и(х) = (х+ 7)(хл + бх+ 19)(хг + 4х+ б)(х+ 1). Выберите эти значения так, чтобы ,Вг = О. Приведите два различных решения. 25. [М90] Когда конструкция в доказательстве теоремы М применяется к неэффективной цепочке полиномов Лт — — ат+Ле, Лг=-Ле — Ло, Лз =Лт+Лг, Л» =аг х Лз, Лз = Ло — Ла. Лв = ов — Лз, Лт = ат х Лв, Лв = Лт х Лт, Лг = Л, х Л», Лто = ав — Лв, Лсс = Лз — Лсо, как можно !)т, тгг,..., »уэ выразить в терминах от, ..., ов? э 26.
(МЯ!] (а) Получите цепочку палиномов, соответствующих правилу Горнера вычисления палиномов степени и = 3. (Ь) Используя конструкцию из доказательства теоремы Л, выразите кс, кг, хз н полинам в конце цепочки и(х) в терминах Эт, бг, тдз, »9» и х. (г) Покажите, что множество палиномов в конце цепочки, полученное в (Ъ), когда все 0», бг, 0з и ту» независимо принимают все действительные значения, не содержит некоторые элементы множества, полученного в котще цепочки (а). 27. (Мдд] Пусть й — множество, которое включает все строки размерности (и + 1) действительных чисел (9„,...,9»,до), таких, что 9 ~ О.
Докажите, что Я имеет более и. степеней свободы. 28. (НМ90] Покажите, что если уе(ат,...,а,), ..., !»(ат,...,а,)-. полиномы от многих переменных с целыми коэффициентами, то существует ненулевой полинам д(хо,.... х.) с целымн коэффициентами, такой, что д(!е(от,..., о.),, !'.(ат,. -. ,а )) = О для всех действительных ат, ..., а,. (Следовательно, любая цепочка поливанов с в параметрами имеет максимум в степеней свободы.) (Укозоное.
Воспользуйтесь теоремами об "алгебраической зависимости", которые можно найти, например, у Б. Л. Ван дер Вардена (В. Е. тап с(ег ЛЛтаегс)еп, Мос)егл А!яебга, ггагтз1асес( Ьу ггес) В1»пп (Ь(е»т Лтаг)с: 1)пбаг, 1949, раздел 64)). Русский перевод: Ван дер Варден, Соврел»енная алгебра. --.Мс ОГИЗ, 1947.] э 29.
(М90] Пусть все Ят> Нг,..., Н множества строк действительных чисел размерности (и+ 1) имеют максимум с степеней свободы. покажите, что объединение йт О йг 1! О к также имеет максимальное чисто степеней свободы Ь э 30. [Мдд] Докажите, что цепочка полиномов с т, операциями умножения в цепочке и тпр операциями умножения параметров имеет максимальное число степеней свободы, равное 2ш, + тпр + бо,. (Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
