AOP_Tom2 (1021737), страница 223
Текст из файла (страница 223)
Если Мв(и) < В, та Лу»в(и») < В» для всех Ь и требуемая формула справедлива, так как М(и") < (" +г)В» согласно упр. 61, (Ь). В бесконечном поле остается лснажитель !об Х. [Этот результат получен в 1979 году Вини (Всп!) и Шенхаге (БсЬопЬабе).] 64. Имеем 2»(7»(и) + 2 „д,,»(и)) = и~2,< хи у„»зс, + 0(из), где 7»(и) = (х»( + и х»гНуг»+и уы)зы+(хм+и х»з)уз»((1+и)з»» — и(вы+вы+г»з)) — х»с(уз»+уз»)(в»>+ вш + з»з) и д,»(и) = (х»с + и~х>г)(у㻠— иус,)(г»> — из>») + (х»> + изх>з)(уы + иун)з»к [Лучшая верхняя грань, известная для >асс>с(Т(З,З,З)), равна 23 (слс.
ответ к упр. 12). Грань ранга Т(2, 2, 2) остается неизвестной.] 65. Полинам в Указании имеет вид из 2',.<" >2 " с(х,д>в,> + Ли12>Е) + 0(из). ПУсть Х;> и 1!<> не определены для 1 < с < т и 1 < у' < и. Присвоим также Хы = 1', = О, Л з = 2' с с Х>, у< = — 2'>". < У> Такизс образом, с помощью та+ 1 умножений полинамов в области неопределенности можно вычислить х,у, для каждого с и у. а также в.
с<=> 2 => Х>1и = в: ',',' к";:с' Л,>16. [ЯСОМР 10 (1981), 434-455. В этой классической статье Шенхаге среди прочих результатов получил результаты упр. 64, бб и 67, (>).] 66. (а) Пусть св = йп!п(„с !обМ[и)>!об и па лемме Т ы > 2. Для всех с > О существует Х с Лу(Х) < Х в'. Из доводов упр. 63, (с) следует, чта !об Лб(и)/!об и < ы + 2с для всех достаточно больпсих Х. (Ь) Это непосредственно следует из упр. 63, (с[). (с) Пусть г = тасс(с(<), 9 = (исив) >~, С> = (МХ5)' >~.
Пусть задано в > О, тогда существует целая постоянная с„такая, что ЛХ(р) < с,р в' для всех положительных целых р. Для каждого целого Ь > О получим <» = <2> (»]Т(т»м»»,и»Х» ~,в~Я» ) и гап>с(<~) < с.». Пусть заданы Ь и >с и пусть р = [[»]><( '+'>].
Тогда согласно упр. 63, (Ь) гапЦТ(рт М,рп Х,рв Б )) < гап1с(М(р)Т(т М,и Х,в В )) < гану(с (")Т(. "М»-' и'Х'-" '8"-в)) <щг » и из и. (Ь) следует, что »»-»»» — »»»-»»»-с <3 Так как р > ( ) /2, получим »»(э> ) ~О~ с < ~ (2 ) "Я" » < 2'"<( ~'>2 (" — ") >>сс/(»с> Поэтому (9+9)" < (6+1)2'">< ч'>2 с,гь для всех Ь. Следовательно, мы должны получить 4+ О < 2'д ч'>г для всех е > О. («) Пусть в упр.
66 и> = и = 4, и заметим, что 1бо'э! + Ое'зз .р 17. 67. (а) Матрица (<<, >« ! ><м.») размера и!и х рлпз имеет ранг и!и, потому что она является матрицей перестановок, когда ограничены тп строк, для которых Й = Ь' = 1. (ь) ((<6>!'),<1!>), по существу, является (<,Оь>) <э(!',.<,1>) плюс и!а+ еп' дополнительных нулевых столбцов.
[Аналогично получаем ((! 4Ь !'),< 1,>) = (<,<>Ю) б> (<[< .>),зля прямых произведений.) (с) Пусть Р— диагональная матрица с<!аб(<<1,...,«), такая, что АРВ! = О. Из леммы Т известно, что гапЬ(.4) = т и гапй(В) = и, отсюда гапй(АР) = и> и гап«(РВ ) = и. Беэ потери общности можно предположить, что первые т столбцов матрицы А линейно независимы. Так как столбцы В принадлежат пустому пространству АР, т можно также предположить, что последние и столбцов матрицы В линейно независимы.
Запишем матрипу А в виде разбиения (А! Аз Аз), где А< — матрица размера рл х и> (и невырожденная), А! — размера и! х д и Аз — -размера ш х и. Разобьем Р так, что .4Р = (А!Р> АгР> А!Р!) Тогда существует матрица И' = (14>! 70) размера <! х г, такая, что АРИ!т = О, т. е. И''! = — Рз А!тА, т Р, '. Аналогично можно записать В = (В< Вз Вз) и найти РРВ~ = О, когда И = (ОХРз) — матрица размера !> х г с 1'з = -Р1В!тВ Р! '. Заметим, что <7РЪ'т = Р!. Таким образом, утверждение указания более или менее установлено (в конце концов, зто было всего лишь указание).
Сейчас положим, что Ан(п) = а,< для 1 < 1 < 1и, А< ч,>1(и) = ип!1<1<ры>6 В>1(и) = Ь,> для 1 < > < и, В<„ч,>1(п) = и!1<и> См(и) = и!сы для 1 < >с < р, С[„е<>,(и) = 1<1. Следовательно, 2 1" 1 А<(и)В!1(и)Сы(и) = и!<и! + 0(и!), если >с < з, и и [! > т][у ) и], если Ь = в + 1. [При этом доказательстве не будет необходимости в предположении, что ! невырожденная относительно С.] (11) Рассмотрим следующую реализацию т(рп, 1, и) с г = тп+ 1; а,> = [[</и] = ! — 1], ь!1 = [<шо«и = 1], ь<„>! = [<=(! — 1)п+ >], если ! < тп; о,„= 1, ь>, = — 1, с<„>, — — О.
Она допускает улучи!ение с <<1 = 1 для 1 < ! < г. (е) Идея состоит в нахождении допускающей улучшение реализации Т(п>, п, з). Предположим, что (.4,В, с) — реализация длиной г. пусть заданы произвольные целые а1, ..., и, »1, ..., >Зр. Расширим А, В и С, определяя А<,! ><„.<р> — и,[> =р], ВО! ><„.1.„> = >3! [» =э], С<ы >«,.1> = О лли 1 < р < и.
Пусть 1<1 = 2„.. ! 2 „", и, >у!с<!о>1 для ! < т и <(1 = — 1, в других случаях получим ~ ~'А<!1,><В<>ь.>1!21 = ) ~п, Д ) А<„><В<!ь ><С<ы >1 — ) п,[~'=р]>ум[у =р[ 1=1 , =!ь=! 1=1 р=! = [2=!'] з,бм — [7=.>ч]п,д! =О. Значит, такое расширение допускает улучшение, если й!... !2, >Е О, Но !21... 6, — полиномы от (п<,...,и, >э<,, Ц,), не равные тождественно нулю, так как без потери общности можно предположить, что не все столбцы матрицы С равны нулю.
Следовательно, будет работать несколько наборов и! и >з,. (!) Если М(п) = и ', то шшучим М(п") = и" ', отсюда гап><(Т(п",п,п ) Ю Т(1,п — и (2п — 1),1)) < и" + и". Из упр. 66, (с) следует неравенство п~ + (п~ — 2п™ + и") >~ < и" + и" для всех Ь. Значит, ы = 2, однако зто противоречит существованию нижней грани 2п~ — 1 (см. ответ к упр. 12). (8) Пусть /(и) и д(и) — полиномы, такие, что элементы И/(и) и И'д(и) являются полиномами. Затем снова определим АЬ+ !1 — и щ1/(о)/4,+, В! +»!1 = 14 ш119(о)/р, Сы = и сы, эт1 4+1 »+44-2 где /(и)д(и) = ро'+О(и'+ ).
значит 2',", Ао(и)В 1(и)см(и) равна и +'+ !412+0(и~4»+ ), если Ь < э, и~+'~~[1 > т]]2 > п], если Ь = э + 1. (Замечание. Следовательно, результат (е) имеет место для любого поля, если гап!42 заменить гап)1, так как можно выбрать оь и 84 полнномами вида 1+ 0(и).] (Ь) Пусть строка р матрицы С приписывается компоненте Т(1,16,1), Основным является то, что 2',1»1 а,1(в)Ь 1(и)ср1(п) равна нулю (не просто О(в~+')) для всех 1 н !', оставшихся после удаления. Кроме того, с 1(и) Эе 0 для всех !.
Данные свойства справедливы для конструкций пп. (с) и (8), и они также остаются справедливыми для прямых произведений. (!) Доказательство просто обобщается для полиномов с двумя и со многнмн переменными. (!) Из п. (Ь) следует неравенство 81»12 + 2(36 72) + 34 1~ < 100, поэтому »4 < 2.52. Возведение в квадрат дает гап14(Т(81, 1,81) Ю 4Т(27,4,27) Ю 2Т(9,34,9) Я 4Т(9,16,9) й4 4Т(3, 136, 3) 49 Т(1, 3334, 1)) < 10000, что дает ы < 2.4999. Успех1 Продолжаем возводить в квадрат и получаем все лучшую и лучшую грань, которая быстро сходится к значению 2.497723729083....
Если начать с Т(4,1,4) 4в Т(1,9,1), а ие с Т(3,1,3) й4 Т(1,4,1), то предельной гранью будет значение 2.51096309.... (С помощью подобного ловкого приема получим 24 < 2.496 (см. В/СОМР 11 (1982), 472-492) .] 68. Т. М. Вари (Т. М. Чвг!) показал, что необходимо и — 1 умножений, доказывая, что и умножений необходимы для вычисления хэ -4- + хэ (Согпе!! Сошрпгег Яаепсе Каросс 120 (1972)]. Ч. Панду Ранган (С. Рап4!о Напбап) показал, что если вычислять такие полиномы, как 81В1+- .
+Т -1В -1, ГдЕ Е, н В, — линейные комбинации хь, то необходимо хотя бы и — 2 сложений для образования Тн и В4 (Х А)бог!!Ьшя 4 (1983), 282 — 288]. Но его нижняя грань, очевндно,не относится ко всем цепочкам полиномов. 69. Пусть уц = х,1 — (1 =Я. Примените рекурсивную конструкцию (31) к матрице 7 + У, используя арифметику степенных рядов от пэ переменных уц и игнорируя все члены общей степени > и. Каждый элемент Ь матрицы представлен как сумма Ье + Ь1 + + Ь», где Ьь — ЗначвннЕ ОднОрадногО пОлиноМа СтЕпени Ь. Затем каждый шаг сложения приводит к и + 1 сложению и каждый шаг умножения приводит к ж -и умножениям и рэ -и 1 2 г сложениям.
Кроме того, каждое деление — это величина вида 1 + Ь1 + + Ь„, так как все деления в рекуррентной конструкции — это деления на 1, когда уц — полностью равны нулю; поэтому деление является незначительно более простым, чем умножение (см. 4.7-(3), где !'о = 1). Так как мы останавливаемся, когда размер определителя становится равным 2х 2, нет необходимости вычитать 1 из ум, когда 1 > и-2. Оказывается, если избавиться от избыточных вычиш1ений, этот метод потребует 20(") +8(") + 12 (") — 4(") +бп — 4 умножений и 20( ) + 8(4) + 4(") + 24(") — и сложений, т. е. эпэ — О(п4) операций. Подобный метод можно использовать для исключения деления во многих других случаях (см.
Сгейе 264 (1973), 184-202). (Однако в следующем упражнении строится конструкция, которая даже быстрее схемы без делений для определителей.) 70. Положим, что А = й — х, В = — и, С = — н и Р = 37 — У в указанном равенстве, затем вычислим определитель обеих частей, используя то, что 1/Х + 1 /Аэ + Уе/Лэ + . обратная к Р как формальный степенной ряд от 1/й, Следует вычислить п1'~о только для 0 < Ь < и — 2, так как известно, что /х(Л) — полипом степени и. Таким образом, необходимо всего пэ+ О(п1) умножений и не + О(п1) сложений для перехода от степени и — 1 к степени и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
