AOP_Tom2 (1021737), страница 218
Текст из файла (страница 218)
= х„, рассмотрен в упр. 2. Мы воспользовались этим методом на шаге С8 алгоритма 4.3.3Т.) 17. Например, когда и = 5, имеем 10уз Зу, + 5уз 10уг + уо х — хо игз~ (х) 1 Х1 2: Х2 5 10 + 10 5 1 ХЗ Х Х4 Х ХЗ Х Х1 Х Х2 независимо от значения /4 18. ао = 2(из/из + 1), 42 = иг/и4 — ае(ао — 1), аг - -ао/2 — и1/и4, аз = 22 — 2аг, аз = ио/из — аз(аз + аг),аз = и4. 19. Поскольку аз — основной коэффициент, можно предположить без потери общности, что и(х) — нормированный полипом (т. е. что из = 1), Тогда ао — корень уравнения 4022 — 24и422 + (4и4 + 2из)з+ (иг — изиз) = О.
Это уравнение всегда имеет по крайней мере адин действительный корень, а может иметь три. Поскольку ао определено, получим аз = из — 4ао, аг = из — 4аоаз — бао, аг = и1 — ао(аеа, + 4аеаз + 2агаз + ао), 2 з аз = ио — аз(ао + азае + аг). 4 г Для заданного полинома решим кубическое уравнение 40хз — 12022 + 802 = 0; это приведет к трем решениям: (ао, аз, аг, аз,а4, аз) = (О, — 10, 13,5, — 5, 1), (1, — 20,68, 1, 11, 1), (2, -10, 13, -3, 27, 1). 20. ЬОА Х ГА00 аз ВТА ТЕИР1' ГА00 =гзо-аз= ЗТА ТЕИР2 ГИОЬ ТЕИР2 ЕТА ТЕИР2 ГИ01. ТЕИР1 ГА00 аз ГИОЬ аз А ГА00 аг= ГИОЬ ТЕИР2 ГА00 аг 21.
з = (х 4- 1)х — 2, ю = (х + 5)з + 9, и(х) = (и1 + х — 8)ю — 8; ог 2 = (х + 9)х + 26, ш = (х — 3)2 + 73,и(х) = (о2 + х — 24)и1 — 12. 22. аз = 1, ае = - 1,аг = 1, 81 = -2,)22 = -2,13з = -2, 84 = 1,аз = -4, аг = О,аз = 4, аз = — 2. Образуем з = (х — 1)х + 1, ю = з + х и и(х) = ((з — х — 4)зо + 4)з — 2. Одно из семи суммироааннй можно сэкономить, если вычислить ю = х + 1, з = гс — х. 2 23. (а) Можно применить индукцию по и; результат тривиальный, если и < 2.
Если /(0) = О, то результат справедлив для полинома /(2)/з; значит, он выполняется и для /(2). Если /(зу) = 0 для некоторого действительного у ф О, то у(Ыу) = Цхзу) = О. Так как результат справедлив для /(з) /(22 + уз), он выполняется н для /(з). Следовательно, можно предположить, что /(з) не имеет корней, действительная часть которых равна нулю. Сейчас точное количество обходов от начала координат траекторией раино числу корней /(2) внутри области, которых не больше одного.
Когда Я большое, траектория /(Яе") для гг/2 < 2 < Згг/2 будет обходить начало координат по часовой стрелке приблизительно и/2 раз, так что траектории /(В) для -Я < 1 < Я долвгны обходить начало координат против часовой стрелки по крайней мере и/2 — 1 раз. Для четного и это означает, что у(з2) пересекает мнимую ось по крайней мере и — 2 раз и действительную ось — и — 3 раз.
Дкя и нечетных 7" (з2) пересекает действительную ось по крайней мере и — 2 раз и мнимую ось — и — 3 раз. Это и будут корни д(Ы) = 0 и Л(Ы) = 0 соответственно. (Ь) Если нет, то д или Ь должны иметь корни вида а+ Ьг с а 34 0 и Ь ф О. Но должно подразумеваться существование хотя бы трех других корней, а именно а — Ьз и — а х Ьз, тогда как д(з) и Ь(х) имеют максимум и корней. 24.
Корнями и являютсв — 7, — 3 х з, — 2 х з и -1; допустимые значения с равны 2 и 4 (но ке 3, так как при с = 3 сумма корней равна нулю). Случай 1, с = 2: р(х) = (х + 5)(х' + 2х+2)(хг+1)(х — 1) ы хз+бхз+бх +4хз — 5х — 2х — 10; д(х) = бхг+4х-2 = 6(х+1)(х — -'). Пусть аг = -1, сп = з; рг(х) = к~+ бх + 5х — 2х — 10 = (х'+ бх+ 'е)(х — з) — э; ао = 6, ,Зо = ~з, Вз = — з.
Случай 2, с = 4; аналогично получаем пг = 9, сч = -3, ас = -6, у3о = 12, )3г = -26. 26. 13г = пг,,Зг = 2ам 13з = ау, 64 = ае, у3з = )Зз = О, у3г = ап )3з = О, Вз = 2йг — из. 26. (а) Лг = аг х Ла, Лг = аг + Лз, Лз = Лг к Ло, Л4 = пз + Лз, Лз = Лз х Ло, Лз = а4 + Лз. (Ь) кг = 1 + уугх, кг = 1 + )3гк,х, кз = 1 + Озкгх, и(х) = Озкз = уЗпЗгу3зу3зх~ + Ргу)з]3зх + уузуЗзх+)3а (с) Если любой коэффициент равен нулю, то коэффициент при хз также должен быть нулем в (Ь), в то время как (а) дает произвольный полипом агх + пгх + пзх+ пз з степени < 3.
27. Иначе должен существовать ненулевой полипом 7'(д,...,диде) с целыми коэффициентами, такай, что д„. 7"(д,...,дпдо) = 0 для всех множеств действительных чисел (д,...,до). Это невозможно, так как легко доказать индукцией по и, что ненулевой полипом всегда принимает ненулевые значения, (См. упр, 4.6.1 — 16. Однако этот результат несправедлив, если рассматривать конечные поля вместо полей действительных чисел.) 26.
Неопределенные величины и м ..., и, образуют алгебраический базис для области полиномов у.)[ап...,а,]„где у',у — поле рациональных чисел. Так как э+1 больше числа элементов базиса, то полиноиы 73(пп..., и,) алгебраически зависимы. Это означает, что существует ненулевой полипом д с рациональными коэффициентами, такой, что д(Уе(пц,п*),..., ~,(пп...,и,)) тождественно равен нулю.
29. Пусть заданы Зе, ..., у, б (О, 1,..., и). Существуют ненулевые полиномы с целыми коэффициентами, такие, что дг(д„р,...,Зу,) = О длн всех (др,...,до) в Я„1 < у < т. Поэтому произведение д,дг... д,р равно нулю для всех (З„...,до) в В, О ОН 30. Начиная с конструкции в теореме М, докажем, что тр + (1 — бом.) из Вь можно эффективно исключить. Если р, соответствует параметру умножения, то уп = уЗг, г х (Тг .г Ви). Нужно прибавить сбг; г,бг, к каждому у3г, для которого суз, появляется в Ту, и заменить )3г, нулем. Это приведет к удалению одного параметра для каждого умножения параметров. Если д, — первое умножение в цепочке, то уи = ( уз к+ В, + Вг; г ) х (угх+ Вг+ Вг,), где.уп уг, Вп Вг — полиномы от Вп ..., Вгз-г с целыми коэффициентами.
Здесь Вг и Вг может быть "поглощено" 13н г и )3н соответственно. Таким образом, можно предположить, что Вг = Вг = О. Сейчас добавим сууг -гби к каждому )3у, для которого сун появляется в Т,", добавим 33г, г7гууг к 13г и положилз ууг;-г равным нулю. Множество результатов не изменится после этого удаления Вгг и кроме величин оп..., п„таких, что уг равно нулю. [Это доказательство, по существу, предложено В. Я.
Паном, Успехи мат. наук 21, 1 (Январь-февраль, 1966), 103-134.] Последний случай можно рассмотреть, как в доказательстве теоремы А, поскольку полиномы с зг = 0 можно вычислить, устраняя уЗгг (как и в первой конструкции, где ри соответствует умножению параметра). 31. В противном случае можно добавить одно умножение параметра в качестве последнего шага и прийти к противоречию теоремы С. (Данное упражнение является улучшенным вариантам теоремы А в этом частном случае, поскольку существует толька и степеней свободы для коэффициентов нормированнага полинама степени и,) 32. Л1 = Ле х Ло, Лг = а1 х Л1, Лз = аз + Лз, Л4 — — Лз х Л1, Лз = аз + Л4.
Необходимо по крайней мере три умножения, чтобы вычислить азх (см. раздел 4.б.3), и по крайней мере два сложения по теореме А. 33. Необходимо иметь и+ 1 < 2т, + тр + до . н т, + тр — — (и+ 1)г2. Таким образом, не существует умножений параметров. Сейчас первые Л„главньзй коэффициент которых (как полиномов от х) не является целым числом, должны быть получены посредством сложения в цепочке и должен существовать по крайней мере п+ 1 параметр.
Таким образом, должно быть хоти бы и+ 1 свовгений параметров. 34. Преобразовать данную цепочку шаг за шагом и также определить "содержание" с, в Л, следующим образом (интуитивно понятно, что с; — старзпий коэффициент в Л,). Определим со = 1. (а) Если шаг имеет вид Л, = а, + Л», заменить его шагом вида Л, = Д + Л», где Д = аг/с», и определить с; = с». (Ъ) Если шаг имеет вид Л, = а — Л», заменить его шагом Л, = Вз + Л», где 81 = — а /с», и определить с, = -с».
(с) Если шаг вида Л„= аг х Л», заменить его шагом Л; = Л» (шаг будет позже удален) и определить сз = аз с». (4) Если шаг имеет вид Л, = Л, х Л», оставить его без изменения и определить с, =с с». После того как этот процесс будет завершен, удалить все шаги вида Л, = Л», заменяя Л, на Л» в каждом паслепующем шаге, который использует Лз Затем добавить последний шаг Л,»1 = »з х Л„где 11 = с,.
Это и есть требуемая схема, так как легко проверить, что новые Л, — это только старые Л„деленные на множитель сз. Д» — заданные функции от аг; деление на нуль — не проблема, так как, если какое-то с» = О, должно быть с = О (следовательно, коэффициент при х" равен нулю); иначе Л» никогда не приведут к окончательному результату. 35. Так как существует по крайней мере пять шагов параметров> результат тривиален, если не существует хотя бы одного умножения параметров. Рассмотрим метод, в котором три умножения могут образовать н»х'. Зйы видим, что должно быть три умножения параметров и два умножения в цепочке, поэтому четыре сложения-вычитания должны быть шагами параметров и упр. 34 применимо.
Сейчас можно предположить, что используются только операции сложения и что имеется цепочка вычисления общего вида нармнрованнога полинома четвертой степени с двумя умножениями в цепочке и четырьмя сложениями параметров. Единственно возможная схема такого вида, которая вычисляет полинам четвертой степени,имеет вид Л1 — — а1+ Ла Лг = аз + Ло Лз = Л! Х Лг Л =аз+Лз л =а +лз Ле = Лз х Лз Лг = аз + Лз Фактически эта цепочка имеет на одну операцию сложения больше, чем нужна, но любая корректная схема может быть задана в таком виде, если одни из а» являются функциями от других а,.
Лг имеет внд (хз+ Ах+ В)(хз+ Ах+ С)+В = хз+ 2Ахз+(Е+А )хе+ ЕАх+Е, гДе А = а1 + аз, В = азаз + аз, С = азаз + а», В = аз, Е = В + С, г = ВС + »г. Поскольку они содержат только три независимых параметра, то Лг не может представлять нормированный полинам четвертой степени общего вида, ЗО. Как и в решении к упр. 35, можно предположить, что цепочка вычисляет нормированный полинам шестой степени общего вида, используя толька три умножения в цепочке и шесть сложений параметров. Вычисления должны проводиться по одной из двух общих схем: где, как и в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
