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