AOP_Tom2 (1021737), страница 219
Текст из файла (страница 219)
35, дополнительное сложение введено для включения более общего случая. Ни одна из этих схем не может вычислить нормированный полинам шестой степени общего вида, поскольку в первом случае это полинам вида (хе + Ах + Вх + С)(хт + Ах + Вх+ 42) + Е, а во втором — вида (х" + 2Ах -ь (Е+ А )х~ + ЕАх+ Р)(х~+ Ах+ С) + Н; оба полинама содержат толька пить независимых параметров. 37. Пусть ре(х) = и х" +п»х" »+ . +во и Ча(х) = х" +с»х" '+ +ее. Для 1 < / ( и разделим р»(х) на нормированный полинам Ч, »(х) и получим рт-т(х) = апЧ»-» (х) + В,Ч,(х). Предположим, .что нормированный полинам Ч,(х) степени и — т' существует и удовлетворяет этому соотношению.
Оно справедливо для почти всек рациональных функций. Пусть рт(х) = Ч„»(х) — хсЧ»(х). Это определение означает, что »)ей(р ) < 1, поэтому можно положить а х» = р (х). Для данной рациональной функции вь»еел» Чт (х) х +Ях+19 х+5 1 рт(х) хе+ 10х+ 29 Зх+ 19 5 ат бт О 1 1 2 2 3 4 значит, п(х)/о(х) = ре(х)/Чо(х) = 1 + 2/(х + 3 + 4/(х + 5)).
Замечание. Обычная рациональная функция установленного вида имеет 2п + 1 "степень свободы" в том смысле, что она, по существу, имеет 2п + 1 независимых параметров. Если расширить понятие цепочки полиномов на понятие цепочки отношений полиномов, которые допускают операции деления так же, как и операции сложения, вычитания и умножения (см, упр, 71), то можно получить следующий результат с незначительными изменениями в доказательствах теорем А и М: цепочка отношений поливанов с Ч шагамн сложений-вычитание имеет максимум Ч+ 1 степеней свободы. А цепочка оглашений полннолюв с тп шагамн умножений-делений имеет максимум 2тп + 1 степеней свободы.
Следовательно, цепочка отношений полиномов, которая вычисляет почти все рациональные функции задшшого вида, должна иметь по крайней мере 2п сложений-вычитаний и и умножений-делений. Метод этого упражнения оптимален. 38. Если и = О, то теорема, несомненно, справедлива, Предположим, что и положительное и что задана цепочка палиномов, которая вычисляет Р(х;не,...,и ), где каждый из параметров а, заменен действительным чиглом. Пусть Л» = Лт х Лв - первое умножение в цепочке, которое включает один из ие, ..., и; такой шаг должен существовать, если учесть значения ранга матрицы А. Без потери общности можно предположить, что Лз л Лт = л, = Л» = Лв = Лв = Лт = Лв = Лв = Л»а = а»+ Ле ат + Ло Л» х Лт ав + Ао +л Л» х Лв »хе + Лв ав ~- Лв Лт х Лв ат + Лв Л» = а» + Л» = ат + л =л х Л» = аз+ Лв = а»+ Лв = Л» х Лт = ав + Лв = ав + л,=л х Л»о =от+ л л Лв л л Лв л, Лв л Лв включают в себя и„; таким образом, Л, имеют вид Ьоие+ .
+Ь„и„+/(х), где Ьа,. ~Ьь— действительные, И„ф О, и /(х) — полинам с действительными коэффициентами. (Ьз и коэффициенты /(х) получены из значений, определяемых а,.) Сейчас заменим шаг з шагам Лг = о к Лз, где а — произвольное действительное числа. (Можно взять о = О. Вообще говоря, а используется здесь только для того, чтобы показать достаточную гибкость доказательства.) Выполним дополнительно следующие шаги: Л = (а — /(х) — Ьоио — — Ь„-,и„-з)(/1з„. Новые шаги включают только операции сложения и умножения (на подходящие новые параметры). Наконец всюду в цепочке заменим Л „г = и„этим новым элементом Л.
В результате получим цепочку, которая вычисляет сг(х; ио, ., и„г) = Р(х; ио,...,и„г, (а — /(х) — Ьоие — ° ° — Ь вЂ” гик-г)/Ьа) и имеет на одно умножение в цепочке меньше. Доказательство будет окончено, если можно показать, что О удовлетворяет предполохгениям. Значение (а — /(х))/Ьа приводит к, возможно, уменьшенному значению га н новому вектору В'. Если Аа, Аг,, А столбцы матрицы А (эти векторы линейно независимы относительно вещественных чисел), соответствующая матрице О новая матрица А' имеет вектор-столбцы Ао — (Ьо/Ь~) А, А„, — (Ь„з/Ь )А плюс, возможно, несколько строк нулей, отвечающих за уменьшение значения т, Эти столбцы, естественно, также линейно независимы. Па инлукции цепочка, которая вычисляет О, имеет по крайней мере и — 1 умножений в цепочке, тогда как начальная цепочка имеет по крайней мере и.
[Пан также показал. что деление не приводит к улучшению правила (см. Проблемы кибернетики 7 (1962), 21-30). Обобщения вычисления нескольких полинамов с несколькими переменными с различного рода предпосылками и без ннх рассмотрены Ш. Виноградом (Я. 1%побгаг), Соппп. Риге апс( Арр!1ег( МагИ. 23 (1970). 165-179).[ 39. ИндУкцией па т. ПУсть шм(х) = хз Ш из зх ю + .
+ ио, ив-г(х) = х + з -з азы-зх + +ао,а=аг+7,Ь=омипусть /(г) = Еь за( 1)гы (*+~)и .ггтзза'Ьз. Следовательно, е„= /(г+ 2) для г > О и бы = /(1). Если б = 0 и а задано, то получим полинам степени т — 1 ат Ь с главным коэффициентом х(иг -з — та) = ш(7з + + 7 — тз ). В неопубликованных заметках Мацкин почти всегда полагал бз = О, выбирая зз таким образом, что основной коэффициент не равен нулю, когда т четное, и равен нулю, когда т нечетное. Тогда можно почти всегда предположить, что Ь вЂ” действительный корень полинома нечетной степени. 40.
Нет; Ш. Виноград (Б %1пабгаг)) нашел метод вычисления всех полинамов степени 13 только с семью (возможно, комплексными) умножениями [Сошгл. Риге апд Арр1гег1 МаЗИ. 25 (1972), 455-457). Л. Ревах (1.. КетаИ) нашла схемы, которые вычисляют почти все полиномы степени п > 9 с [и/2[ + 1 (возможно, комплексными) умножениями [ЯСОМР 4 (1975), 381-392[.
Она также показала, что, когда и = 9, можно достичь [и/2) + 1 умножений, на по крайней мере с п+ 3 шгожениями К слову, достаточно много операций сложения (см. упр. 39), оговорок "почти все" и "возможно, комплексными" исчезли. В. Я Пан ~АТОС 10 (1978), 162-172; НЗМ КезеагсИ Керогз КС7754 (1979)] нашел схемы с [п/2) + 1 комплексными умножениями и минимальным числом и+ 2 + без комплексных сложений для всех нечетных и > 9. Его метод для п = 9 имеет вид о(х) = ((х + а) + В)(х + 7), ге(х) = в(х) + х, Сз(х) (о(х) + аз)(га(х) + е!), Сз(х) = (и(х) + оз)(го(х) + «з), и(х) = (Сг(х) + ч)(Сз(х) — С~(х) + и) + к.
Минимальное число дейсглвиглельимх сложений, необхолимое, когда достигнуто минимальное число действительных умножений, для и > 9 остается неизвестным. 41. а(с+ 4) — (а+ Ь)4+ С(а(с+ 4) + (Ь вЂ” а)с). [Остерегайтесь чистенной неустойчивости. Три умножения необходимы, поскольку в частном случае (71) с р(и) = из + 1 умножение комплексное, Без ограничения на сложение существуют другие возможности. Например, в 1963 году Питером Унгером (Ресег Епбаг) предложена симметри шая формула ас — 64+ г((а+ 6)(с+ 4) — ас — ЬгС). Равенство 4.3.3-(2) похоже на это с 2" в роли !. См.
также работы 1. Ыипго, БТОС 3 (1971), 40 — 44; 8. Ързпобгай, Ь!пеаг А!Зебга алг(!Сз АррбсаБопз 4 (1971), 381 †3.[ Наоборот, если а + Ь = 1 и С = (1 — а)/Ь = 6/(1 + а), то для вычисления произведения (а + Ы)(с+ 4!) = и + зи Оскар Банеман (Озсаг Випешап) предложил алгоритм ью = с — СВ, е = д + Ьге, и = ю — Си" [Х Сошр. РЬуз.
12 (1973), 127-128[. Этим методом, .если а = соэ В и Ь = з!пВ, получаем С = Сап(В/2). Гельмут Альт (Не!зпие А!С) и Ян Ван Ливен (Лап чап Ьееииеп) [Сошриз!пб 27 (1981), 205 — 215[ показали, что необходимо четыре действительных умножения или деления для вычисления 1/(а + Ьз) и достаточно четырех операций для вычисления (с/Ь)а Ь + сг Ь + с(с/6) Ь + с(с/Ь) Шесть операций умножения-деления и три сложения-вычитания необходимо и достаточно для вычисления (а -!- 6з)/(с+ сБ) [Т. Ь!с1ссе!8, 81СОМР 16 (1987). 278 — 311[.
Несмотря на эти нижние грани следует помнить, что нет необходимости выполнять комплексную арифметику в терминах действительной арифметики. Например, при использовании быстрого преобразования Фурье время, необходимое для умножения двух и-значных комплексных чисел, асимптотически равно приблизительно только удвоенному времени умножения двух и-значных действительных чисел. 42.
(а) Пусть я!, ..., я — это йо соответствующие умножениям в цепочке, тогда зг, = Рз, ! х Рз, и и(х) = Рз е и где каждое Р, имеет вид!)з+!Ззех+!3!гяг+ +В „!з!ясбь где г(/) < [з/2) — 1, и каждое СЗз и )Ззь — полинам от а, с целыми коэффициентами. Можно постоянно модифицировать цепочку таким образом (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
