Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 51
Текст из файла (страница 51)
Докажите, что если /(ям..., к») »южно вычислить цепочкой отношений полиномов, имеющей щ умножений в цепочке и й делений, то /(хг,..., х„) и все и ее частные производные д/(хм..., х„)/дхь для 1 < й < и можно вычислить единственной цепочкой отношений полиномсе, которая имеет максимум Зт+Ы умножений в цепочке и 24 делений. (Например, любой эффективный метод вычисления определителя матрицы приводит к эффективному методу вычисления всех ее алгебраических дополнений„а значит, и к эффективному методу вычисления обратной матрицы,) 72. (?и48) можно ли определить ранг любого данного тензора (спа) иэд, скажем, полем рациональных чисел за конечное число шагов? 73. (ВМ33) (Я. Моргенсгерн (Я.
Могбепэсегп), 1973.) Докажите, что любая цепочка полиномов двя дискретного преобразования Фурье (37) имеет по крайней мере йим... ш» 13 ш~... гп» сложений-вычитаний, если не существует умножений в цепочке и 1 если каждый параметр умножения является комплексной постоянной с (аз( < 1. Указание. Рассмотрите матрицы линейных преобразований, вычисленных за первые /г шагов. 74.
(ИХ33) (А. Новаки (А. НоэаЫ), 1973.) Большая часть теории, посвященной вычислению полиномов, касается умножения в цепочке, однако умножение нецелочисленных постоянных также может быть весьма важным. Назначение этого упражнения — развизь соответствующую теорию. Скажем, что векторы щ,...,в, действительных чисел Я-эаексимм, если существуют целые числа (йм, ..,к,), такие, что бед(1м,к») = 1 и й~ ог + + й,ю, — полностью целочисленный вектор. Если не существует таких целых чисел (йг,, .., Й,), то векторы ом, о, называются Е-независимыми. а) Докажите, что если столбцы матрицы 1» размера г х э Я-независимы, то существуют столбцы матрицы 1гЦ, где Ц вЂ” любая унимодуляриая матрица размера г х э (матрица из целых чисел с определителем, равным ~1). Ь) Пусть 1г — матрица размера г х э с У-независимыми столбцами.
Докажите, что цепочка полниомов, которая вычисляет элементы г'х, зависящие от хц .,,, х„где х = (хи..., к,), производит по крайней мере э умножений. с) Пусть Ъ' — матрица размера г х 1, имеющая е У-независимых столбцов. Докажите, что цепочка полнномов, которая позволяет вычислить элементы 1'з, зависящие от хм, хи где х = (х и .,,, х~) т, обязательно произжщнт по крайней мере э умножений. г)) Покажите, как вычислить пары значений (х/2+ у, х+ р/3), которые зависят от х и у, используя только одно умножение, несмотря на то, что необходимы два умножения для вычисления пары (я/2+ р, х+ р/2).
° 4.7. ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ Если заданы два степенных ряда 61(Л) = Уо+ У1Л+ Узлэ+ ., Г(л) = 1О+ $1Х+ 1/ЗЛО+ ° ° ° (1) с коэффициентами, принадлежащими некоторому полю, то можно образовывать их сумму, произведение н иногда их отношения., а также получать новые степенные ряды.
Полиномы, очевидно, являются частным случаем степенных рядов, число членов которых конечно. Безусловно, только конечное число членов можно представлять и хранить в компьютере. В таком случае уместно спросить: "Какая арифметика степенных рядов возможна яа компьютерах, и, еслк возможна, чем она отличается от арифметики полнномову". Ответ таков: лмы работаем только с первыми Х коэффициентами степенных рядов, где Х вЂ” параметр, который, в принципе, может быть произвольно большим. Вместо обычной арифметики полиномов мы, по существу, используем арифметику по модулю л~, что часто приводит к различным точкам зрения. К тому же отдельные операции наподобие "обращения" можно выполнять со степенными рядами, но не с полиномами, так как полиномы не замкнуты относительно этих операций" .
Операции со степенными рядами находят много применений в численном анализе, но, возможно, наиболее важным является нахождение аснмптотического разложения (как видно из раздела 1.2.11.3) или вычисление некоторых величин, определяемых производящими функциями. Именно последние, а не арифметика с плавающей точкой, делают их удобными для точного вычисления коэффициентов. Все алгоритмы данного раздела, кроме очевидных исключений, можно выполнять только с использованием рациональных операций. Таким образом, методы из раздела 4.5.1 можно будет применять для получения точных результатов, когда потребуется. Вычисление И'(з) = У(з) * Ъ'(г)., конечно, тривиально, поскольку И;, = [г") И (л) = б'„~ 1'„для и = О, 1, 2, ....
Так же легко вычислить коэффициенты И'(л) = У(л) И(з), воспользовавшись хорошо известным правилом свертки И = ~~',»1»И-О = с'Ок +б'11'-1+ +(' »О. »=О Отношение И'(х) = Г(л)»'Г(л), когда 1о ф О, можно пс»чучить, если поменять местами У и И' в (2). Таким образом, получим правило (3) = (Ул — И О1'л — И'11л-1 — " — И л-1~'»)~~'О. Это рекурреитное соотношение для И'» позволяет легко последовательно вычислить ИО, И1, И'1, ..., ие вводя Ул и Ъ'„до вычисления И„1. Алгоритм с такими свойствами, оперирующий степенными рядами. обычно называют икп»сраки»ивимм (опйпс).
С его помощью можно определить Л коэффициентов И'О, И'1,, И'д не зная заранее У. Значит, можно, в принципе, выполнять алгоритм, как угодно И(х) = 1' х™(1+(1' »»/И )х+К +э/К»)х'+ ") ) (г) =1„;х-(1+(~ „/Ъ )3+(1 „71~ )з'+ -) . Это выражение будет степенным рядом тогда и только тогда, когда ап» вЂ” неотрица» тельное целое число. Из (4) следует, что задачу вычисления произвольных степеней можно свести к случаю, когда 1~~ — — 1, т.
е. к вычислению коэффициентов: И ( ) = (1 + Р,» + Ъэг' + 1гэг' + " )". (5) Очевидно, что И'е = 1 = 1. Естественным методом нахождения коэффициентов выражения (5) является использование бииомиальной теоремы 1.2.9-(19) или (егли а — - положительное целое число) методов из раздела 4.6.3. Но Леонард Эйлер открыл более простой и более эффективный метод получения степеней степенных рядов (1п»гос(исйо 1л Апа)уз1п 1пйнсогош 1 (1748), 376): если И'(з) = Ъ-'(х), то, дифференцируя, получим И'~ + 2Изх+ 314зх~+" = И"(х) = о\г(г)' '1"(г); следовательно, И" (*) ~(х) = аИ'(х) Г(х).
Составив уравнение для коэффициентов при г" ' в (7), получим, что (7) хИ»г -» = а~ (в й)И»1 -ы (8) а это дает удобное правило вычислений, справедливое для всех в > 1: И.=~ Я вЂ” "+1)й — 1)1,И„, = ((а+1 — п)~,И'„, + (2а+2-п)ЬзИ'„т + .-+ пор И'о)~п.
(9) Из ссютношения (9) можно получить простой интерактивный алгоритм для последо- вательного определения И'м Иге,..., используя приблизительно 2п умножений для вычисления и-го коэффициента. Отметим особый случай, когда а = -1; (9) стано. вится частным случаем (3) прн У(х) = Ие = 1- долго, и полностью вычислять степенные ряды, Можно также выполнять интерактивный алгоритм до тех пор, пока не будет соблюдено любое требуемое утловие. (Противоположность "оп1! пе" — "ой)1пе" (" автономный" ).) Если коэффициенты У» и Ъ» — целые, а И'» — не целые, рекуррентное соотношение (3) включает вычкслення с дробями.
Этого можно избежать, если воспользоваться полностью целочисленным подходом, предложенным в упр. 2. Рассмотрим операцию вычисления И'(г) = $'(х)', где о — "произвольная" степень. Например, можно вычислить квадратный корень из И(г) при а = -' или найти И(г) ~ либо даже $"(х)'. Если 1м — первый не равный нулю коэффициент И(л), получаем Аналогичные методы можно использовать для образования /(Р (з)), когда /— любая функция, удовлетворяющая простому дифференциальному уравнению (ск»., например, упр. 4). Для решения дифференциальных уравнений часто используется сравнительно прямой "'метод степенных рядов". Он приводится почти во всех учебниках по дифференциальным уравнениям.
Обращение рядов. Возможно, наиболее интересным преобразованием степенных рядов является обращение рядов. Это преобразование позволяет решить уравнение з = » + рзЗ + рзЗ + 941 + (10) относительно 1, т. е. получить коэффициенты степенного ряда З = -+ Из + И»зз + И»з + (11) Известны особо интересные способы выполнении такого обращения. Можно сказать, что "классический" метод основан на замечательной формуле обращения Лагранжа (Мбто»гез Аса»1.
Яоуа(е дез Яс»евсее ез Вейез-1.еззгез де Вегбл 24 (1766), 25 1-326), устанавливающей, что И»„= — (З"-») (1+ Изс+ Изсз+" )-". л-1 (12) и Например, имеем (1 — З) з = (4 + (4)з+ (~)З~ +, тогда пятый коэффициент, И з, обращения з = » — зз равен (4)/6 = 14. Это проверяется с помощью формулы перечисления бинарных деревьев, приведенной в разделе 2.3.4.4. В соотношении (12), которое имеет простое алгоритмическое доказательство (см. упр.
16), показано, что можно обратить ряд (10), если последовательно вычислять отрицательные степени (1+ 1»з»+ (гз»з+ ") " для и = 1, 2, 3, .... Непосредственное применение этой идеи должно привести к интерактивному алгоритму обращения, который использует около 1» з/2 умножений для вычисления »з' коэффициентов, но соотношение (9) предоставляет возможность работать только с первыми и коэффициентами (1+из»+ гз1~+ ) ", получаемыми интерактивным алгоритмом, которому требуется лишь около А»з/6 умножений.
Алгоритм 1 (Обращенве ппепенного рлда меп»одом Лагранзюа). В этом интерактивном алгоритме (рис. 17) вводится значение Ил из (10) и выводится значение И'„ из (11) для и = 2, 3, 4, ..., А». (Нет необходимости заранее знать точное число А»; алгоритм можно завершип в соответствии с любым критерием.) Ы. [Инициализация.) Присвоить и»- 1, (7е»- 1. (Соотношение (1+ 1гзз+ ЪЪ»з+" )-" = СЪ+ Н»»+ "+ (/.,з"-'+ 0(з") (и) сохраняется на все время работы алгоритма.,' В2. (Ввод Ь'„.) Увеличить и на 1. Если и > А», работа алгоритма завершается, иначе — ввести следующий коэффициент 1»„.
13. (Деление.) Присвоить (»»»- (»з — (74 11'з — " — (»1 1'з — Ц>1»4+1 для й = 1, 2,- и — 2 (в таком порядке); затем присвоить 1 +- 20~ з)»з — ЗГ~ зрз — — (и — 1)(»»У»» 1 — пЦ)1» . (В результате получаем»»'(з), деленное на Г(з)/з, см. (3) и (9).) 1 4. (Вывод И»л.] Вывести (»л 1/и, которое равно И'„, и возвратиться к шагу Е2.
$ Рнс. 17. Алгоритм 1, обращения степенного ряда. Если алгоритм Е применить к примеру г = 1 — 1т, можно вычислить следующее. и Уп (7е (уг б'з (7з Гг И»п 1 1 1 1 г 1 3 О 1 3 б 2 4 0 1 4 10 20 5 5 0 1 5 15 35 70 14 В упр. 8 показано, что небольшая модификация алгоритма Е позвоаит решать значительно более общие задачи, прилагая только чуть больше усилий. Рассмотрим сейчас решение уравнения (14) (71г+(7тз +Пзг + '' г+ гзг + гзг +'' относительно г и получим козффициенты степенного ряда $=И'гя+Изг'+Игзс'+Иа~з'+ - . Уравнение (10) — зто частный случай (14) при Ц = 1, (уз = (уз = = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
