AOP_Tom2 (1021737), страница 159
Текст из файла (страница 159)
Ь) Пусть У вЂ” матрица размера г х «с Я-независимымн столбцами. Докажите, что цепочка полнномов, которая вычисляет элементы «'я, зависящие от хм..., х„где х = (хм..., с,), производит по крайней мере э умножений. т с) Пусть У вЂ” матрица размера г х й имеющая з л-независимых столбцов. Докажите, что цепочка полиномов, которая позволяет вычислить элементы Ух, зависящие от см..., кь где х = (хм..., х~), обязательно производит по крайней мере з умножений. т З) Покажите, как вычислить пары значений (х/2+ у, я+ у/3), которые зависят от х и у, используя только одно умножение, несмотря на то, что необходимы два умножения для вычисления пары (х/2 + у, х + 9/2).
в4.7. ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ ЕСЛИ ЗАДАНЫ Даа СтЕпЕнНЫХ РЯДа с (л) = ГО + Г!х + Гэл + ' ' '. 1 (л) = !О + г!х + гэх + ' ' ' (1) с коэффициентами, принадлежащими некоторому полю, то можно образовывать их сумму, произведение и иногда их отношения, а также получать новые степенные ряды. Полиномы, очевидно, являются частным случаем степенных рядов, чигло членов которых конечно. Безусловно, только конечное число членов можно представлять и хранить в компьютере. В таком случае уместно спросить: "Какая арифметика степенных рядов возможна на компьютерах, и, если возможна, чем она отлвчается от арифметики полиномов?". Ответ таков: имы работаем только с первыми !т' коэффициентами степенных рядов, где Х вЂ” параметр, который, в принципе, может быть произвольно большим.
Вместо обычной арифметики полиномов мы, по существу, используем арифметику по модулю л~, что часто приводит к различным точкам зрения. К тому же отдельные операции наподобие "обращения" можно выполнять со степенными рядами, но не с полиномами, так как полиномы не замкнуты относительно этих операций". Операции со степенными рядами находит много применений в численном анализе, но, возможно, наиболее важным является нахождение асимптотического разложения (как видно из раздела 1.2.11.3) или вычисление некоторых величин, определяемых производящими функциями. Именно последние, а не арифметика с плавающей точкой, делают нх удобными лля точного вычисления коэффициентов.
Все алгоритмы данного раздела, кроме очевидных исключений, можно выполнять только с использованием рациональнь!х операций. Таким образом, методы из раздела 4.5.1 можно будет применять для получения точных результатов, когда потребуется. Вычисление И'(х) = У(г) х 1Г(г), конечно, тривиально, поскольку И'и = [хи) И'(г) = б!„* Г„для и = О, 1, 2, .... Так же легко вычислить коэффициенты И'(л) = 1!(э) 1'(л), воспользовавшись хорошо известным правилом свертки (2) И'и = ~~~ (!ь~'и-ь = (10~'и + 1!! Ии-! + "+ 1!и~'О.
э=о Отношение И'(х) = 1!(э)/1Г(г), когда !'и ф О, можно получить, если поменять местами Г н И' в (2). Таким образом, получим правило = (и„— И;1„— И",1и, —" — И„,1,У1.. (3) Это рекуррентное соотношение длн И'ь позволяет легко последовательно вычислить И'с, И!!, И'ы ..., не вводя 5!„и Ъи до вычисления И!и !. Алгоритм с такими свойствами, оперирующий степенными ридами, обычно называют инп!ерактивнмм (опйпс). С его помощью можно определить Х коэффициентов Ищ И'!, ..., И!А! не зная заранее Х.
Значит, можно, в принципе, выполнять алгоритм, как угодно долго, и полностью вычислять степенные ряды, Можно также выполнять интерактивный алгоритм до тех пор, пока не будет соблюдено любое требуемое условие. (Противоположность "оп1ше" — "о(йшеь ("автономный").) Если коэффициенты (7ь и Уь — целые, а И'ь — не целые, рекуррентное соотношение (3) включает вычисления с дробями. Этого можно избежать, если воспользоваться полностью целочисленным подходом, предложенным в упр. 2.
Рассмотрим операцию вычисления И'(г) = У(х), где а — "произвольная" степень. Например, можно вычислить квадратный корень из У(х) прн о = -', илн найти У(л) ьэ либо даже У(л)'. Если У вЂ” первый не равный нулю коэффициент У(л), получаем У(л) = У г (1+ (1Т +1/У )в+ (У э/1,„)хэ + ..), У(в) = У л (1+ (У,„<.~/У )г+ (У~,~.г/У )х~ + ' ') (4) Это выражение будет степенным рядом тогда и только тогда, когда ош — неотрица- тельное целое число.
Из (4) следует, что задачу вычисления произвольных степеней можно свести к случаю, когда Ус = 1, т. е. к вычислению коэффициентов: И (х) = (1 -~- У1х + Уэх + 1'эх + ' ' ' ) (5) И~ + 2И~тх+ ЗИ'эх~+ . = Иг'(э) = оУ(г)~ ~У'(г); (6) следовательно, И"(х)У(г) = о1У(г)У'(л). Составив уравнение для коэффициентов при х" ' в (7), получим, что н в ЕжУв-ь = ОЕ(я — й)И'1'--., а=о т=в (8) а это дает удобное правило вычислений, справедливое для всех и > 1: = ((а+1 — п)1~И~„, + (2а+2 — п)УэИ~„т+ . + паУ Ие)/а. (9) Из соотношения (9) можно получить простой интерактивный алгоритм для последо- вательного определения Иы И'э, ..., используя приблизительно 2п умножений для вычисления и-го коэффициента. Отметим особый случай, когда о = — 1; (9) стано- вится частным случаем (3) прн с7(в) = Ув = 1.
Очевидно, что И'о = 1 = 1. Естественным методом нахождения коэффициентов выражения (5) является использование бнномнальной теоремы 1.2 9-(19) нли (если а -- положительное целое число) методов из раздела 4.6.3. Но Леонард Эйлер открыл более простой и более эффективный метод получения степеней степенных рядов [1псгойнлбо ш Апа(уяп 1пйпйогпш 1 (1748), 176]; если 1У(х) = У(х), то, дифференцируя, получим Аналогичные методы можно использовать для образования /(Ъ'(г)), когда /— любая функция, удовлетворяюшая простому дифференциальному уравнению (см., например, упр.
4). Для решения дифференциальных уравнений часто используется сравнительно прямой "метод степенных рядов". Он приводится почти во всех учебниках по дифференциальным уравнениям. Обращение рядов. Возможно, наиболее интересным преобразованием степенных рядов является обращение рядов. Это преобразование позволяет решить уравнение г= !+Ъз! + Ъз! +Ъ4! + (10) относительно 1, т.
е, получить коэффициенты степенного ряда ! = г+ ЪЪ22 + ЪЪзг + ЪЪ42 + ' Известны особо интересные способы выполнения такого обращения. Можно сказать, что "классический" метод основан на замечательной формуле обращения Лагранжа [Мето!геа Асад, Кора!е с!ез Бс!епсез е! Ве!!ез-йезггез де Вег!ш 24 (1768), 251-326], устанавливающей, что И;, = — [!" '](1+ Ъ'2!+ Ъ'з!2+ ) 1 (12) и например, имеем (1 — !) з = (4) + (4)! + (4)! +, тогда пятый коэффициент, И'з, обращения г = ! — !2 равен („)/5 = 14. Это проверяется с помощью формулы перечисления бинарных деревьев, приведенной в разделе 2.3.4,4.
В соотношении (12), которое имеет простое алгоритмическое доказательство (см. упр. 16), показано, что можно обратить ряд (10), если последовательно вычислять отрицательные степени (1+ Ъзг+ Ъз!2+ ° ) " для п = 1, 2, 3, .... Непосредственное применение этой идеи должно привести к интерактивному алгоритму обращения, который использует около Хз/2 умножений для вычисления Ж коэффициентов, но соотношение (9) предоставляет возможность работать только с первыми и коэффициентами (1+ ъзе+ ъз!2+ ..
) ", получаемыми интерактивным алгоритмом, которому требуется лишь около 2Уз/6 умножений. Алгоритм Ь (Обращение степенного ряда мепзодом Лагранжа). В этом интерактивном алгоритме (рис. 17) вводится значение Ъп из (10) и выводится значение Иг„ из (11) для и = 2, 3, 4, ..., Ж. (Нет необходимости заранее знать точное число 2У; алгоритм можно завершить в соответствии с любым критерием.) Ы. [Инициализации.] Присвоить и 4- 1, Оо 4 — 1.
(Соотношение (1+ Ъз!+Ъзг~+ ) "= Но+О»!+ ° . + Г„»!" '+0(!и) (13) сохраняется на все время работы алгоритма.) Ь2. [Ввод Ъ'„.] Увеличить п на 1. Если и > Х, работа алгоритма завершается, иначе — ввести следующий коэффициент 12„. ? 3. [Деление.] Присвоить Г» 4 — Г» — О»»Ъ2 — — О»Ъ» — (/аЪ»4.з для !с = 1, 2, ..., и — 2 (в таком порядке); затем присвоить Са-2 4- -2Оа-2Ъ2 — Мà — зЪз — . — (и — 1)Г»Ъ'„2 — п7/о)са- (В результате получаем Цг), деленное на Ъ'(г)/г, см.
(3) и (9).) 1 4. [Вывод И'„.] Вывести Г„»/и, которое равно И'„, и возвратиться к шагу Ь2. ! Рис. 17. Алгоритм 1. обращения стеленного ряда. Если алгоритм Е применить к примеру г = 4 — гг, можно вычислить следующее. (7о (7! Гг Гз Г~ И „ 1 1 1 1 2 -1 1 2 1 3 0 1 3 б 2 4 0 1 4 10 20 5 5 0 1 5 15 35 70 14 В упр.
8 показано, что небольшая модификация алгоритма Е позволит решать зна- чительно более общие задачи, прилагая только чуть больше усилий. Рассмотрим сейчас решение уравнения (14) Г42+Ггг +Гзг + = г+ !'24 + гзг + относительно г и получим коэффициенты степенного ряда +И; 2+И~ 3+Иг 4+... (15) Уравнение (10) — зто частный случай (14) при П! = 1, Гг — — Гз = - — — О. Если (7! ф О, можно предположить, что (7! —— 1, заменив г на ((7!2), но мы рассмотрим общее уравнение (14), поскольку 47! может равняться нулю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
