Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 40
Текст из файла (страница 40)
упр. 5), что с этой точки зрения оно не улучшает правило Горнера. Но существуют по Тогда легко доказать по индукции, что и(г) = га»+ Ь„. Эта схема [В1Т 5 (1965), 142; также см. О. Ооегсге!, АЫЫ 65 (1958), 34 — 35) требует только 2п -л 2 умножений и 2п+ 1 сложений, так как она является усовершенствованным правилом Горнера, когда и > 3.
Для рядов Фурье, когда г = есо, имеем г = 1, так что число умножений уменыпается до п+ 1. Отсюда мораль: хороший программист не станет неразборчиво использовать встроенные характеристики комплексной арифметики языков программирования высокого уровня. Расслютрим процесс деления полинома и(х) на х-хо, используя алгоритм 4 610, чтобьс получить и(х) = (х — хо)у(х) + г(х), здесь с)ек(г) < 1. В этом с»сучае г(х) — константа, не зависящая от х и и(хо) = О у(хо) + г = ю Проверка этого процесса деления позволяет обнаружить, что вычисления, по существу, такие же, как и правило Горнера для вычисления и(хо). Подобным образом, если мы делим и(г) на полинам (г — го)(г — го) = гг — 2хог + хог + уо», результат вычисления оказывается эквивалентным (3).
Получаем и(г) = (г — го)(г — го)у(г) + а г + Ь»' отсюда и(го) = а„го + Ь„. Вообще, если разделить и(х) на /(х). получится и(х) = /'(х)у(х) + г(х), а если /(хо) = О. то и(хо) = г(хо): это наблюдснио приводит к дальнейшим обобщениям правила Горнера. Например, можно положить /(х) = х» — хго, что дает правило Горнера "второго порядка": крайней мере два обстоятельства, в которых (4) полезно: если необходимо вычислить и(х) и и(-х) и этот подход дает и(-х) только с помощью одной дополнительной операции сложения, два значения можно пачучить почти так же легко, как и одно.
Кроме того, если компъютер позволяет выполнять параллельные вычисления, то имеется возможность обе строки (4) вычислять независимо, так что экономится около половины времени счета. Если компьютер допускает параллельное вычисление Й арифметических операций одновременно, то можно применять правило Горнера "й-го порядка" (положив З (х) = хз — хсз). ДРУГой пРивлекательный метод ДлЯ паРаллельного вычислении предложил Дж. Эстрнн (6.
Езйбп) (Ргос. Иеззегп Лошз Созпрпззпй Сопс 17 (1960), 33-40); для и = 7 метод Эстрина имеет следующий вид, Процессор 1 Процессор 2 Процессор 3 Процессор 4 Процессор 5 5з = мах + из з(з = изх+ ис а~ = игх + из аз =пзх +йз з аз ы азх +сз сз = изх+ из сз = сзх +дз Табулированне значений полиноыа. Чтобы вычислить полинам и-й степени на множестве значений арифметической прогрессии (т.
е. и(хэ), и(хе+ Ь), и(хе+ 26),...), процесс можно снести только к сложению после первых нескольких шагов. Так, если начать с любой последовательности чисел (аэ,ам...,а„) и применить пре- образование ас +" аэ+ ам аз +- аз + аз, ..., ап-г +- ае-1 + ае* получим, что й применений (5) дают Сз(Ь)р+(й)бз+(й)р 2+0(У<и где Рз — начальное значение ад н Рд = 0 длЯ У > и. В частности, представляет собой полинам степени и от Й. Правильно выбирая Рз, как показано в упр.
7, можно устроить так, что величина аэ будет требуемым значением и(хо+96) И) для всех х. Другими словами, каждое выполнение н сложений в (5) будет давать следующее значение данного полинома. Предостережение. Ошибки округления могут накапливаться после многочисленных повторений (5), и ошибка в а приводит к ошибке в коэффициентах хс,.... хз вычисляемого полинома. Поэтому значения аз следовало бы "освежить" после большого числа итераций. Здесь аз = и(х). Тем не менее интересный анализ В. Ш.
Дорна (уг', Я, 0огп) (1ВМ Х Вез. апг( Пете1. 6 (1962), 239-245) показал, что эти методы в действительности не могут быть улучшением правила второго порядка, если каждая арифметическая операция должна обращаться к памяти, которая сообщается только с одним процессором. Производные н замена переменной. Иногда необходимо найти коэффициенты и(х + хе) с заданными постоянной хе и коэффициентами п(х). Например, если и(х) = Зх~+ 2х — 1, то и(х -2) = Зх~ -10х+ 7. Это аналог проблемы преобразования системы счисления, преобразующей основание х в основание х + 2.
По теореме Тейлора новые коэффициенты заданы производными и(х) в точке х = хе, т. е. и(х+ ха) = п(хо) + и (хе)х+ (и '(ха)/2!) х + ° ° ° + (и " (хо)/и!) х", (7) так что задача эквивалентна вычислению п(х) и всех ее производных, Если записать п(х) = о(х)(х — хе) + г, то и(х + хе) = й(х + хэ)х + г; в таком случае г есть постоянный коэффициент и(я+хе) и проблема сводится к нахождению коэффициентов д(х+ хэ), где д(х) — известный полипом степени и — 1. Таким образом, предлагаем следующий алгоритм. Н1. Присвоить с, +- и, для 0 < 1' < и. Н2.
Для и = О, 1, ..., и — 1 (в таком порядке) присвоить су ч- сз + хест+г для 7' = п — 1, ..., х+ 1, Й (в таком порядке). ! Поокончании шага Н2 получим и(х+хэ) = с„х" + . +с1х+ье. Эта процелурабыла главной частью метода Горнера нахождения корней, и когда и = О, она является точным правилом (2) вычисления п(хэ). Метод Горнера требует (пэ+ и)/2 умножений и (из+ и)/2 сложений, но заметим, что, если хе — — 1, все умножения опускаются. К счастью, можно свести общую задачу к случаю, когда хе = 1, введя сравнительно небольшое число умножений и делений.
81 Вычислить и запомнить значения хе~ ° ° ~ хе ° Я2. присвоить ет ь — и х,', для 0 < у < и. (сейчас э(х) = п(хэх).) БЗ. Выполнить шаг Н2, только с хэ —— 1. (Сейчас с(х) = п(хе(х+1)) = и(хсх+хе).) ъ4, Присвоить еэ < — г)/хээ для 0 < 7' < и. (Сейчас э(х) = п(х+ хе) как и требовалось.) $ ' 1та идея, предложенная М.
Шо (М. тазг) и Ж. Ф. Траубом (Л, Г. ТгапЬ) (дАСМ 21 (1974), 161-167), обеспечивает такое же количество сложений и такую же численую ~ сто йчивость, как н метод Горяера, но при этом необходимы только 2п — 1 умножений е и — 1 делений, так как с„= и„. Приблизительно -'и этих умножений можно по очереди избежать (см. упр, 6). ' Шо и Трауб отметили, что существует дополнительный способ зкономии врем эни счета, если нужны только несколько первых или последних производных. Нап ъимер, если нужно вычислить только п(х) и и'(х), то для выполнении следующего ~ и оритма потребуется 2и — 1 сложений и около и+ ь/2п пумножений и/или делений.
! 11. Вычислить и запомнить значения хэ, хэ, ..., х', хт', где $ = ~З/и/21. 112. ПРисвоить гу +- и х7® длЯ 0 < 1 < и, где /Ц) = 1 — 1 — ((и — 1 — 7) шог) 21) дли О <,у < и, а /(и) = Ф, 1! 3. Присвоить эз +- с„+ и +1хэ® для у = и — 1, ..., 1, 0; здесь д(7) = 21, когда и — 1 — у — положительный множитель 21, иначе д(у) = 0 и нет необходимости умножать на хэ®. 114.
Присвоить и е- и + и +~хзО1 для у = п — 1, ..., 2, 1. Теперь ие/ягоде~ = и(х) и и~/хгй) = и'(х). 1 и(х) =изх +изхз+изхз+и1х+ив.. из 10. Эту формулу можно переписать в виде, впервые предложенном Т. С. мацкиным (Т. 8. МоззЫп), у=(х+ое)х+а,, и(х) = ((у+х+оз)й+оз)ов, (9) для соответственно "'адаптированных" коэффициентов ое, аы ат, аз, азь Вычисления по этой схеме включают три операции умножения, пять операций сложения и (на машине с одним сумматором, подобной машине И11) одно указание запомнить промежуточный результат 9 во временном запоминающем устройстве.
По сравнению с правилом Горнера в этой схеме мы заменили умножение сложением и, возможно, командой запоминания. Даже эта сравнительно малая экономия имеет смысл, если полинам вычисляется часто. (Конечно, если время умножения сравнимо со временем сложения, (9) не дает улучшения: для вычисления обычных полиномов четвертой степени всегда требуется зю крайней мере восемь арифметических операций.) Сравнив коэффициенты в (8) и (9), получим формулы для вычисления а„, выраженных через иш ао = (из/из — 1), оз = /1 — 2ам Ф = иг/из — ое(по+ 1), о1 = из/из пои: оз = ие/и4 о1(а1 + оз) а4 — из (10) Подобная схема вычисления полинома четвертой степени за такое же число шагов, как (9), предлагается в упр. 18; этот альтернативный метод дает в некоторых случаях большую точность, чем (9), хотя он уступает в точности другим.
Полиномы, встречающиеся па практике, часто имеют достаточно малый старший коэффициент, поэтому деление на и4 в (10) ведет к неустойчивости. В таком Адаптация коэффициентов. Возвратимся к нашей первоначальной проблеме вычисления заданного палинома и(х) для "случайных" значений х настолько быстро, насколько это возможно. Важность данной проблемы отчасти является следствием того факта, что стандартные функции, такие как Йпх, совх, е' и т. д...
обычно вычисляются подпрограммами, которые опираются на вычисление определенных полиномов. Поскольку такие полиномы часто вычисляются, желательно найти возможно наиболее быстрый метод вычислений. Произвольные полиномы степени пять и выше можно вычислить, выполнив меньше операций, чем требуется по правилу Горнера, если сначала "адаптировать" коэффициенты ие, им ..., и„. Как будет паяснено ниже, процесс адаптации может включать в себя уйму работы, но предварительное вычисление не является ненужной потерей времени, так как оно должно производиться талька один раз, а полинам вычисляется многократно.
Примеры "адаптиравания" полиномов для выполнения стандартных функций приводятся в работе В. Я. Пана. СССР Вычясл. матея. и матем, физика 2 (1963), 137-146. Простейший скучай, для которого адаптация коэффициентов полезна, встречается прн использовании полиномов четвертой степени: случае предпочтительней на первом шаге заменить х на )иь('7" х, сводя (8) к папиному со старшим коэффициентом, равным *1. Подобное преобразование применимо к полиномам более высоких степеней. Эта идея предложена Ч.
Т. Файком (С, Т. Гйе) (САСЛХ 16 (1967), 175-178): он рассмотрел несколько интересных примеров. Любой полинам пятой степени можно вычислить, используя четыре умножения, шесть сложений н одно запоминание согласно правилу и(х) = П(х)х + ие, где У(х) = иьхь + иьхз + изхз + изх + из вычигляется, как и в (9). Кроме того, можно произвести вычисление, выполнив четыре умножения, пять сложений и три запоминания, если вычисления огушествлялись по формуле р = (х+аэ) и(х) = (((у+аз)у+аз)(х+аз)+аь)аь (11) Для определения а, теперь требуется решить кубическое уравнение (см. упр. 19). На многих компьютерах количество требуемых формулами (11) операций "запомнить" меньше трех; например, мы, возможно, сумеем вычислить (х+ ае), не 3 запоминая х + ае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
