AOP_Tom2 (1021737), страница 160
Текст из файла (страница 160)
Алгоритм Т (Обобщенное обращение степенями рядов). В этом интерактивном алгоритме вводятся значения Г„н Ъ'„нз (14) и выводится значение И'„из (15) для и = 1, 2, 3, ..., гУ. При вычислениях используется вспомогательная матрица Т „, 1 < пз < и < Х. Т1. (Инициализация.] Присвоить и 4- 1. Занесем два первых введенных значения (а именно — С!! и Г!) в Тг, и К! соответственно. (должио выполняться равенство У! — — 1.) Т2. (Вывод И~„.] Вывести значение Т4„, которое равно И~„. ТЗ.
(Ввод Г„, 1'„.] Увеличить и на 1. Если и > Аг, алгоритм заканчивает работу, иначе — запоминает два следующих введенных значения (а именно — Г„и 1~„) в Тго и 1' . Т4. ]Умножение.] Присвоить 2жо 4 Тг!2)ч-! и — 1 + ТггТт-г,п-г + ' ' ' + ~1,л — ~пз-42тп-гзо-! и Т,„4- Тг„— Ъ' Т „для 2 < т < п. [После этого шага дли 1 < пг < и получим (16) =Хттг +Тп п~ч-гг +'''+Т пг +0(г ) Легко проверить (16) иидукцией по т ) 2 и, когда гп = 1, получить 17„ Тщ + ИгТго + .
+ Ъ'„Топ согласно (14) и (16).) Возвратиться к шагу Т2. Соотношение (16) объясняет механизм этого алгоритма, предложенного Генри К. Тэчером (мл.) (Непгу С. ТЬасЬег, дг.) [САСЛХ 9 (1966), 10-1Ц. Время счета алгоритма, по существу, такое же, как и у алгоритма Ь, но требуется значительно больший объем памити для хранения данных. Пример работы алгоритма приведен в упр. 9. Другой подход к обращению степенных рядов предложен в работе Н. Р.
Вгепг апд Н. Т. Кппй, дАСЛХ 25 (1978), 581-595. Он основан на том факте, что стандартные итерационные процедуры, которые используются для нахождения корней уравнений с действительными числами, можно также применять к уравнениям для степенных рядов. В частности, можно рассмотреть метод Ньютона для приближенного вычисления действительного числа 1, такого, что у(1) = О, а заданная функция 7 хорошо ведет себя в окрестности н если х является хорошим приближением к 1, то ф(х) = х — /(х)/~'(х) будет даже лучшим приближением.
Записав х = 1+ е, получим ~(х) = ~(1) + су'(1) + 0(сг), ~'(х) = ~'(1) + 0(с); следовательно, ф(х) = 1+ с [О + сУ~(1) + 0(с~))/[~ (1) + 0(с)) = 1+ 0(с ). Применим зту идею к степенным рядам. Пусть 7(х) = У(х) — Цг), где (7 н г' — степенные ряды из (14). Найдем степенной ряд 1 от г, такой, что у(г) = О. Пусть х = И'1 г+ . + И'„|г" ' = г+ 0(г") — -"приближение" к 1 порядка и, тогда ф(х) = х — у(х)/7'(х) будет приближением порядка 2п, поскольку дли этих 7" и 1 выполняются предположения метода Ньютона.
Другими словами, можно воспользоваться следующей процедурой. Алгоритм М (Обобщенное обращение степенного ряда методом Ньютона). Данный "полиинтерактивный" алгоритм вводит значения У„и Ъ'„согласно (14) для 2" < и < 2~+' и выводит значения И'„согласно (15) дли 2ь < и < 2ь ', получая ответы группами по 2ь значений одновременно для й = О, 1, 2, ..., К. Х1. [Инициализация.[ Присвоить Х с — 1. (Получим Х = 2".) Ввести первые коэффициенты (7~ и Ъ) Я = 1) и присвоить И'г + — Уы Я2. [Вывод.) Вывести И'„для Х < п < 2Х.
МЗ. [Ввод.) Присвоить Х < — 2%. Если Х ) 2к, алгоритм закончил работу, иначе ввести значения (7„и И для Х < п < 2Х. 1ч4. [Шаг Ньютона.] Воспользуемся алгоритмом для композиции степенных рядов (см. упр. 11), чтобы вычислить коэффициенты Я и Н (О < у < Х) степенного ряда (71г+ ° ° + (англ гг г (И'гг+... + Иип 1г — ) — Ног~ + В1 г т + + Н,ч 1ггл ~ + 0(гг~), У(И1г+ + Им 1гж 1) = ЮО+ агг+ + ач !гм 1+ О(г ч), где У(х) = х+ Уэх +.
и У'(х) = 1+ 2Уэх+ .. Затеи возьмем И'л,..., Иэк в качестве коэффициентов степенного ряда — И' . И' ~ ' О( ) — м+'''+ эю — гх + и возвратимся к шагу ч2. 1 Время работы данного алгоритма при получении Л = 2~ коэффициентов равно Т(Ы), где Т(2%) = Т(Х) + (время на выполнение шага 1'4) + 0(Аг). (17) Прямые алгоритмы для композиции и деления на шаге Х4 имеют порядка Хэ шагов, значит, алгоритм Х работает медленнее алгоритма Т. Тем не менее Брент (Вгепг) и Кунг (Кппб) нашли метод, которым требуемая композиция степенных рядов выполняется с помощью 0(Х 1ояАГ)э~э арифметических операций (в упр, б приведен алгоритм для деления, работающий еще быстрее). Таким образом, в (17) показано, что обращение степенных рядов можно выполнить только с помогцью 0(Х 1оя уэ)э~э операций, когда Х -> сс.
(С другой стороны, константа пропорциональности такова, что Аг должно быть действительно большим, прежде чем алгоритмы Б и Т перестанут относиться к "быстродействующим" методам.) Истиорическал справка. Ж. Н. Брамхел (3. К. Вгапйа!1) и М. А. Чаппл (М. А. Старр!е) впервые опубликовали метод обращения степенных рядов, требующий 0(дг~) операций, в САСМ 4 (19б1), 317 — 318, 503. Это, по существу, автономный алгоритм, эквивалентный методу, который приведен в упр.
16, с таким же временем счета, как у алгоритмов 1 и Т. С(х) = И'(иУ(х)). Легко видеть, что (7(Г(х)) = 1У(иэУ(г)) и вообще (7("1( ) = И'(и"У( )) (19) (20) для всех целых и. Следовательно, имеем простое выражение для и-й итерации Г("), которую можно вычислить приблизительно с одинаковыми затратами труда Итерация рядов. Чтобы изучить поведение итеративного процесса х„е- у(х„г), следует изучить и-кратную композицию данной функции у саму с собой, т. е. х„= 7(у(...у(хо)...)).
Определим у(е)(х) = х и у(")(х) = 7(~~" ')(з)) так, что .(("'")( ) = ~(-1(~1"1( )) (16) для всех целых гп, и ) О. Во многих случаях обозначение у(")(х) имеет смысл и для отрицательных целых п. Если 7'М и 7(-") — взаимно обратные функции, а именно — х = ~(ь)(~~-")(х)), и если обратные функции определены единственным образом, то (18) справедливо для всех целых гп и и. Обращение рядов — это, по существу, операция нахождения обратного степенного ряда 7'( И(х), Например, соотношения (10) и (11) устанавливают, что г = У(И'(г)) и 1 = Иг(1~(1)); таким образом, И~ = У~ '). Предположим, что заданы два степенных ряда, У(х) = х + 1~эхэ + и 1У(х) = х+ И'эх +, таких, что И' = У( г).
Пусть и — любая не равная нулю постоянная. Рассмотрим функцию для всех и. Кроме того, можно даже воспользоваться (20), чтобы определить П(") для нецелых значений и. Например, "полуитерация" 17('~э~ — это такая функция, что (/('М (П('дб(»)) = Г(»). (Существуют две такие функции И'7»), полученные в результате использования э/и и — ь/и в качестве значения и'7» в (20).) Мы получили простые соотношении в (20), которые, начиная с Р и и, определяют Г Но на практике обычно применяется другой метод: начиная с некоторой заданной функции Г найти такие Г и и, чтобы выполнялось (19), т. е.
чтобы 1 (и( )) = пИ( ). (21) ОФ~ + П» = ггЛ ~~ Иэ+ 2ь'г(/э('» + 7/э = с'~ гз О," 1э4 + 3(/, Гг гз + 2 сч Гз г» + П» 1» + ьэ = ('~ 14 и т. д. Ясно, что не су~цествует решения, когда бгг —— 0 (кроме тривиального случая, когда П» —— (/з = = 0), но существует единственное решение, если Г~ не является корнем из единицы.
Можно предположить, что произойдет что-нибудь забавное, когда Г," = 1, так как из (20) видно, что (/(")(») = », если функция Шредера в этом случае существует. Предположим на минуту, что О~ не равно нулю и не равно корню из единицы. Тогда функция Шредера существует и возникает следующий вопрос: "Как ее вычислить, не прилагая слишком много усилий?". Следующая процедура предложена Р. П.
Брентом (В.. Р. Вгепс) и Ж. Ф. Траубом (3. Р. ТгапЬ). Уравнение (21) приводит к подобной подзадаче, но более сложного вида. Таким образом, мы поставили более общую задачу, подзадача которой имеет такой же вид. Попытаемся найти И(») = Ъо + Ъ~» +... + 1я г»" ', такое, что 1 ((/(»)) = И ( ) 1»( ) + 3( ) + О( "), (22) где Г(»), И'(»), о(») и и заданы, и — степень двойки и 17(0) = О. Для и = 1 просто положим 1»а — — Я(0)/(1 — И'(0)) с Ъо = 1, если 5(0) = О и И'(0) = 1. Кроме того, возможен переход от п к 2п: сначала найдем /7(»), такое, что )/(Г(»)) = И:(») И(») + Я(») — »пЛ(») + О(»211) (23) затем вычислим И ( ) = И ( )( /17(»)) +О( )„о( ) = гс( )( /о'( )) + 0( ) и найдем Г(») = Ъ'„+ 1'„л»+ .. + 1»»„г»" ', такое, что 12((7( )) = И (») 1'( ) + й( ) + О( ").
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
