AOP_Tom2 (1021737), страница 224
Текст из файла (страница 224)
Используя рекурсию, получим коэффициенты /х из элементов Х после 6(4) + 7(") + 2(") умножений и 6(") + 5(") + 2(") сложений-вычитаний. Вычислив только »1ег Л = ( — 1)" /х(0), можно сэкономить 3(") — и+ 1 умножений и (") сложений. Этот свободный от деления метод для вычисления определителя на самом деле совершенно экономный, когда и — умеренная величина; это вариант схемы разложения по алгебраическим дополнениям, когда и ) 4. Если ш — показатель умножения матриц в упр.
66, то такое же приближение приводит к свободному от деления вычислению за О(п ~'~') шагов, поскольку векторы иу'~ для 0 < /г < и можно вычислить за О(М(п)!обп) шагов. Возьмем матрицу, первые 2' строк которой равны иК для О < й < 2, и умножим ее на Кг. Тогда первые -» г! 2' схрок произведения будут равны иг ~ для 2' < Гг < '2'+'. [См. Б. 1.
Вегуош!гз, Хпу. Ргосезэ!пд Веще»э 18 (1984), 147 — 150.[ Конечно, такое "бысхрое" асимптотическое умножение матриц представляет определенный теоретический интерес. Э. Калхофен (Е. Ка!гоГегг) показал, как вычислять определители только с помощью 0(п +'Л/М(п) ) операций сложения, вычитания и умножения [Ргос. Гпи Яушр. Яушб. А!8. Сошр. 17 (1992), 342-349); его чеход представляет интерес даже при М(и) = и . 71. Предположим, что дг — — иг о ьг, ..., д„= и, а о, и / = п»дг + + а,д, + ро, где и» = !г»»дг + + Я»!»-цд» вЂ” г + р», о» = тыдг + .
+ 7»!» цд» г + д», каждый знак "о" является "х" или "/" и каждое р! или дг — попиномом степени < 1 ох кг, ..., х„. Вычислим произвольные величины ш», у», г» для Гг = г, г — 1, ..., 1 следующим образом'. ш» = с»» +Я!и.»!»У»»» + 7ы+ц»к»чг + + Я,»У +7»э„и у»=ш»хе», з»жш»хи», еглид»=и»хи»; у» ж ш»/и», з» = — у» х д», если д» ш и»/о». Затем / = ро + ргу + д[гг + + р,у + Ч,з„где означает производную оо любому из хг...
х„, [Ч'. Ваш' еле! Лг. Яегазвеп, Тйеогейса! Согор. Ясг. 22 (1983), 317 — 330. Родственный меход опубликовал С. Линнаиимаа (Б. Ь!ппшпшаа, ВГТ 16 (1976), 146-160), который применил его к анализу округления ошибок.) Мы сэкономим два умножения в цепочке, если д, = и, х е„так как ш, = и„.
Повторив конструкцию, »южно задать все вторые частные производные с максимум 9т+ 34 умножениями в цепочке и 44 делениями. 72. Существует алгоритм вычисления ранга хензора над алгебраически замкнутыми полями, подобными комплексным числам, так как зто частный случай результатов Альфреда Тарски (А!Веб ТагэЫ, А РесГэ|оп МеебогГ Гог Е!етепгагу.4!ОеЬга ав6 Сеопгеггу, 2пд е»ГОйоп (Вег1е!еу, Са!!Гоггпа: Пинт оГ СаНогша Ргезэ, 1951)). Однако известные методы не делают эти вычисления дейсхвительно осуществимыми, за исключением очень малых тензоров.
Неизвестно, будет ли решена эха проблема над полем рациональных чисел за конечное время. 73. В таких цепочках полиномов от !У переменных определитель любой матрицы размера А' х Х для !»' линейных форм, полученных после ! шагов сложений-вычитаний, равен максимум 2'. И в дискретном преобразовании Фурье матрица последних Х = тг...т„ линейных форм имеет определитель Ю 7, поскольку ее квадрат равен !»' перестановкам Я7г махрицы из упр.
13 [3АСМ 20 (1973), 305-306). 74. (а) Если к = (йц.,.,Г»,) — вектор взаимно простых целых чисел, значит, существует 17/г, так как любой общий делитель злеменхов матрицы ГГГ» делит все элементы /г = Г/ 'Г/Гг. Следовательно, матрица РГ//г не может иметь все целые компоненты. (Ь) Допустим, существует цепочка полиномов для Рк с ! умножениями.
Если ! = О, все элементы матрицы Р должны быть целыми числами, значит, е = О. Иначе пусть Л, = и х Л» или Л, = Л„х Л» — первый шаг умножения. Можно предположить, что Л» = игкг + + и,х, + Я, где и»„..., н, — целые числа, не все равные нулю, и,Я вЂ” постоянные. Найдем унимодулярную матрицу [У» такую, что (пс,..., и,) сг =- (О,..., О, »с), где»с = бс»1(пг,..., и,). (Приведенный перед равенством 4.5.2 — (14) алгоритм безоговорочно определил такую матрицу бс.) Построим новую цепочку полиномов с входными значениями уг,, у, следующим образом: сначала вычислим х = (хс...х.) = 0(уг,...,у.
и — /)/»С), затем продолжим вычисления с предполагаемой цепочкой полииомов для Гх, Когда достигнем шага г цепочки, сюлучим Лс = (и»,..., п,)х+»7 = О, значит, можно просто положить Л» = О, а ие выполнять умножение. Затем вычисляем 1»х и добавляем постоянный вектор шС)/»С к результату, где ш — наиболыпий правый столбец ИУ.
Пусть Ср — з — 1 остальных столбцов 1»»7. Новая цепочка полиномов вычисляет 1'х + шб/»» = И(у(ус,..., у,— », -СС/»С) + ш)г/»С = И'(уг,, у, г) с С вЂ” 1 умножениями. Однако столбцы ИР являются Я-независимыми согласно п, (а); следовательно, с — 1 > з — 1 по индукции по з и получаем с > з. (с) ПУсть хг = О Длк С вЂ” з значений 7', котоРых нет в Я-независимых столбЦах. С помощью любой цепочки для стх вычисляем 1"х' для матрицы 1", применив результаты п.
(Ь). (»1) Лс = х — у, Лг = Л» + Лс, Лг = Аг + х, Ля = (1/6) х Лг, Лг = Ля -С А», Ле = Лг + у (= *+у/5), Лг = Ле — Лс, Лг = Лг+Ля (= х/2+у). Но для (х/2+у, х+у/2] необходимы два умножения, поскольку столбцы ('(г,' ) Я-независимо». (зо»яп»аСоПпуоппас»оп Ргосеяэшу 1 (1978), 125-129.) РАЗДЕЛ 4.7 1. Найдите первый не равный нулю коэффициент С', как в (4), и разделите 0(с) и И(г) иа г (сдвигая коэффициенты на т мест влево).
Отношение будет отененным рядом тогда и только тогда, когда По = . = »7» = О. 2. Имеем Ъ~4 юИ' =соосс„— (Со Иго)(1»оа '1' ) — (Се»И»)((о" 1'-») — — (Роср -»)(со 1»). Тогда можно начать с замены (Уг, 1',) на (1»о»Сс„рог '1',) для 7 > 1, затеи присвоить И'„+- с»„— 2,» о И'»1' ь для и > О и наконец заменить И', на И',/1о+ для / > О. Подобная техника возможна в сочетании с другими алгоритмами данного раздела. 3. Да. Егли а = О, то легко доказать индукцией, что И'» — — И'г — — — — О.
Когда и = 1, найдем, что Иг„= 17 согласно тождеству / С'ьс' — » = Р'»С'о. /с» — (и — к) Л с=! 4. Если И'(г) = ес С" », то И" (г) = Ъ" (г) И'(х), находим СРо = е~» и И'. = ~ — Р»И; — д. я и > 1. с» и ».=1 Если И'(г) = 1и Ст(с), то С» и И'. меняются ролямн. Значит, когда 1о = 1, устанавливается правило: Ио = О и И'„= 1'„+ 2'ь" г'(й/и — 1) 1» Иг„с для и > 1. [Используя упр.
6, коэффициент Иг, для логарифма можно вычислить за 0(п1ой и) операций. Р. П. Врент (В., Р Вгепс) заметил, что ехр(1'(г)) также нежно вычислить асимптотнчески с такой же скорост.ю, применяя метод Ньютона к /(х) = 1пх — У( ). Следовательно, обычное возведение в степень (1 + Сг(г)) = ехр(а 1п(1 + 1'(г))) также можно выполнить за 0(п!оба) операций.
Си. Аласубс Сошрисас!опа) Сашр/ехйу, еебсей Ьу 5. Г. ТгапЬ (Хек" Уогк. Аса»Сеш»с Ргеэе, 1975), 172 176.) 5. Получится начальный степенной ряд. Это можно использовать в качестве критерия алгоритма обращения. 6. ф(х) = х+х(1 — х)»(г)) (см. алгоритм 4.3.5Н). Затеи, когда И»о, ..., И'л с известны, основная идея заключается во вводе 1к,, Сг» -», вычислении (Ио+ . + Ия-»г ) х ~со+ .
+ Ргк — »г ) = 1+ссог + +Ел-»г ' +0(г ' ) и использовании равенства И ь> + ' ' ' + И оя- > з (И о + ' ' ' + ИЪ вЂ” > с )(>>о -!- ' ' ' ч ссл — > х ) -!- 0(х ). (Хшлег. Масй. 22 (1974), 341 — 348; данный алгоритм, по существу, впервые опубликован в рабате М. 8!ете!с!пй, Саа>рпйпй 10 (1972), 153 — 156.) Заметим, что общие затраты на вычисление Х коэффициентов равняются О(Х 1ой Х) арифметическим операциям, если использовать "быстрое" умножение полиномов (см.
упр. 4.6,4-57). 7. И'„= (,")/и, когда и = (гл — 1)/с+ 1; иначе — О (см. упр. 2.3.4.4 — 11). 8. С1. Ввести О> и 1>>, присвоить и с — 1, Гго с — 1/1>>; вывести Ис> = 0>По. С2. Увеличить и на 1. Если и > Х, работа алгоритлса окончена; иначе — ввести И иСю СЗ. Присвоить Пь е- (77>-2", »> (7ь-> 1>>»> )/1 > для !с = О, 1,..., а — 2 (в гаком порядке), затем пРисвоить 0 > с- — 2',с эlсб'„— ь1>/1>. С4. Вывести И'„= 2 „ь > й(7» ьС>/и и возвратиться к шагу С2. (Время работы алгоритма — порядка Х; таким образом, оно увеличилось только относи.з тельно порядка Х .) Зазсечоиае.
Алгоритмы Т и Х определиют И! '(П(х)), алгоритм данного упражнения с! ->! определяет 0(1г> '>(х)), что не одно и то же. Безусловно. все результаты можно получить, выполнив операцию обращения, а затем — композиции (упр. 11), но полезно иметь для каждого случая более прямой алгоритм, 9. и=1 и=2 и=3 и=4 и=5 2 5 14 2 5 14 1 3 9 1 4 1 Т> 1 1 То 1 23 > Тс„ 10. С помощью (9) получаем уП» = х(1+а>х+аох + )'>" = х(1+с>х+сох>+ ) и затем обращаем последние ряды, (См. замечание, следующее после уравнении 1.2.11.3 — (11).) 11.
Присвоить сначала И'о е- По, а затем — (Тсо И'ь) с — ($'ю О) для 1 < Й < Х. После этого для и = 1, 2, ..., Х выполнить следующие операции присвоить сначала И', с — И', ~- П,Т, дли и < 7 < Х, а затем — Т, +- Т» 1>> Ч. + Т 11 длл 7' = Х, Х вЂ” 1,, т> + 1. Здесь вместо Т(з) стоит И(о) . Можно построить ик>исрактпвнмй алгоритм стси пенных рядов для этой задачи, аналогичный алгоритму Т, но потребуется около Х>/2 ячеек для хранения данных. Для выполнения данного упражнения также существует интерактивный алгоритм, которому необходимо только 0(Х) ячеек. можно предположить, что 1'> = 1, если Пс заменить на (7> Г>" и !''ь заменить на 1'>„./1'> для всех й Тогда с помои>ыа аэгоритлса Б можно абра ить И(х) и испольэовать его выходные данные в качестве входных данных в алгоритм упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
