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