Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 41
Текст из файла (страница 41)
Действительно, большинство современных компьютеров имеет более одного арифметического регистра для вычислений с плавающей точкой, так что вполне можно обойтись без запоминания. Поскольку различные компьютеры для выполнения арифметических действий предоставляют большие возможности, в этом разделе следует учитывать талька арифметические операции, а не операции запоминания и загрузки сумматора.
Вычнгшительные схемы обычно простым способом можно адаптировать к любому конкретному компьютеру так, что понадобится несколько дополнительных операций: с другой стороны, следует помнить, ч.з .ти операции могут свести на нет экономию одного или двух умножений, в особенности если программа компилируется мапзиной не оптимально. Полинам шестой степени и(х) = ивхь + . + изх + ис всегда можно вычислить, используя четыре операции умножения и семь операций сложений, по схеме з=(х+аэ)х+аы ш=(х+аз)в+аз; и(х) = ((ш+ в+ аз)и+аь)ав (О. Е. КшпЬ, САСМ 5 (1962), 696 — 699.) Такая схема позволяет избежать двух из шести умножений, требуемых по правилу Горнера.
Здесь снова необходимо решить кубическое уравнение: так как аь = ив, можно предположить, что иь = 1. При этом предположении пусть Д = (иь — 1)/2, бз — — иь — бз()7з + 1), Фз = из — рздз, А = дз — А, Фь = из — 6здз- Допустим, что ььь — вещественный корень кубического уравнения 2Уз + (24з — рз + 1) Рз + (аз — Эзбь — Уз) Р + (ив — 9збь) .= О. (13) (Это уравнение всегда имеет вещественный корень, так как левая часть полинома стремится к +ос для больших положительных значений р и к — оо — для больших отрицательных значений у; оно должно принимать значение "нуль'" где-то посередине.) Если сейчас определить дт= 4+бьдв+дь, дв =Фз Фь Фт то окончательно получим ае = Рг — 2Фз, аз = А — ао а1 = Рз аеаз1 аз = Фг — агат, аз = дз — дг — ам аз = ио — Ртов.
(14) Эту процедуру можно пояснить на следующем примере: предположим, нужно вычислить хе+ 13хз + 49х4 + 33хз — 61хг — 37х+ 3. Получим ае = 1, )7г = 6, фз = 7, Фз = -9, бз = — 1, )7з = -7 и таким образом придем к кубическому уравнению 2„з З,г + 2, + 12 (15) Это уравнение имеет корень |3» = 2. Находим дз = -6, а1= — 7, аз=16, аз=6, аз=-27. а =3, аз=3, Следовательно, окончательная схема такова: з = (к+ 3)х — 7, ге = (х+ 3)с+ 16, и(х) = (ш+с+ 6)гс — 27. Благодаря явному совпадению дважды появляющихся величин х + 3 можно найти метод, использующий три умножения и шесть аюжений.
Другие методы подхода к решению уравнения шестой степени предложены В. Я. Паном (Проблемы кибернетики 5 (1961), 17-29). Один из них требует на одну операцию сложения больше, но включает только рациональные операции на первых шагах; однако кубическое уравнение необходимо решать. Можно записать процесс решения в следующем виде: - = (т+ае)к+ам гс = э+я+аз, и(х) = (((з — х + аз) и + аз) г+ аз) аз (16) Для определения а мы снова один раз делим полинам на из = аз и таким образом приходим к нормированному многочлену и(х). Затем можно проверить, что ае = из~3 и аг = (иг — аеиг + азиз — аои4 + 2аоИиз — 2аеиз + 5ае).
(17) Заметим, что для метода Пана требуется, чтобы делитель в (17) не обращался в нуль. Другими словами, (16) можно испольэовать только тогда, когда 27изиз — 18изизиз + 5из 14 0; в действительности это значение не может быть таким малым, поскольку а| ста- нет слишком большим. После того как а1 будет определено, остальные а можно определить из уравнений А= дз аз аг = аз = (19) 2ае ~ из-ае,зг-аФм ~1 (Фз — (ао — 1) 6г + (ао— ,Уг — (ае г— 1) — аз — 2ам ио — азиз.
~уг = из — аеА -ам А =из — аоФз -агбг, 1) (аег — 1)) — аы аз дз (аг + аг)(аз + аг) Мы детально обсуждаем случаи степеней п = 4, 5, 6, поскольку такие значения и чаще встречаются в приложениях. Сейчас рассмотрим общую схему вычисления полиномов и-й степени, метод, включающий максимум (и/2) + 2 умножений н и сложений. Теорема Е. Каждый полинам и-й степени (1) с действительным н коэффициентами„ и > 3, можно вычнслнть по схеме у=х+с, ю=у; х=~ ((и„у+ае)у+ бе, и четное, ( ичу+ Фо, и нечетное, и(х) = (...
((х(ю — а~) + б~)(ш — аз) +,9з)...)(ю — ам) + б,„(20) при подходящих вещественных параметрах с, аь н /1ь, где т = (и/2) — 1. На самом деле можно выбрать зтп параметры таким образом, что,В = О. Докеаетельсчпео. Сначала рассмотрим условия, при которых ау и бз могут быть выбраны в (20) при фиксированном с. Пусть р(х) = и(х — с) = о„х" + о„~х" ~ + ° + а~ х + ао.
Покажем, что р(х) имеет вид р,(х)(хз — а,„) + б для некоторого полинома р~ (х) и некоторых констант ам, б,„. Если разделить р(х) на хт — а,„, то остаток б,„будет константой только в том случае, если вспомогательный полипом ч(х) =аз +~х +ае ~х + . +ею (22) сформированный из нечетных коэффициентов р(х), кратен х — а . Наоборот, если д(х) имеет множитель х — а„„то р(х) = р~(х)(хт — а ) +,д при определенных константах б„„которые можно определить посредством деления. Также необходимо„чтобы р~(х) имел видрт(х)(х~ — а ~)+ д м и это эквивалентно тому, что у(х)/(х — а„,) является кратным х — а„, Ы если ш (х) — полипом, соответствующий р~(х), как у(х) соответствует р(х), то д~(х) = д(х)/(х — а„,).
Продолжая в том же духе, найдем, что параметры аы Д, ..., а,,9 существуют тогда и только тогда, когда д(х) = аз +~(х — а~) ... (х — а ). Другими словами, каждый полинам у(х) тождественно равен нулю (и зто возможно, только когда и четное) или же у(х) — полипом степени т, имеющий все вещественные корни. Поразительный факт был обнаружен Дж. Ивом (3. Ече) (Метет.
Май. 6 (1964), 17-21): если р(х) имеет по крайней мере п — 1 комплексный корень, есе вещественные части которых не отрицательны нлн не положительны, то соответствующий полипом д(х) тождественно равен нулю илн имеет все вещественные корми (см. упр. 23). Поскольку и(х) = 0 тогда и только тогда, когда р(х + с) = О, необходимо просто выбрать параметр с достаточно большим, чтобы по крайней мере п — 1 корень и(х) = 0 имел вещественные части > -с, и (20) будет применяться всякий раз, как только а„~ = и„~ — пои„ф О. Можно определить с таким образом, чтобы эти условия выполнялись, а также чтобы о' = О. Первые и корней уравнения и(х) = 0 определены.
Если а+ Ж— корень, имеющий наибольшую или наименьшую вещественную часть, и если Ь ф О, то положим с = -а и а,„= -Ьэ; тогда хэ — а, является множителем и(х — с), Если корень с наименыпей или наибольшей вещественной частью вещественный, но корень со второй наименьшей (или второй наибольшей) вещественной частью не вещественный, то применяется такое же преобразование, Если два корня с наименьшими (или наибольшими) вещественными частями вещественны, то их можно выразить в виде а-Ь и а+5 соответственно.
Пусть с = -о и а = Ь; снова х -а э множитель и(х — с). (Однако часто возможны другие значения с; см. упр, 24.) Коэффициент а„-~ будет ненулевым для хотя бы одного нз этих вариантов, если только 4(х) не будет тождественно равным нулю. 1 Заметим, что этот метод доказательства обычно дает по крайней мере два значения с, переставлять аы, а„, ~ можно (т — 1)! способом, Некоторые из этих вариантов, вероятно, дают большую точность, чем остальные. Вопросы, связанные с точностью, конечно, не возникают при работе с целыми числами по модулю т, а не с действительными числами. Схема (9) работает при и = 4, когда т н 2и4 — взаимно простые числа, а (16) работает прн п = 6, когда т — взаимно простое число с био и знаменателем (17). В упр. 44 показано, что и/2+ О(1оя п) умножений и О(н) сложений достаточно для любого нормированного полинома и-й степени по любому модулю т.
вЦепочкн полнномов (полнноынальные цепочки). Рассмотрим вопросы оптимальности. Каковы наилучшие схемы вычисления полиномов различных степеней, выраженные в терминах минимального возможного числа арифметических операций? Этот вопрос впервые проанализировали А. М. Островский для случая, когда коэффициенты предварительно не адаптируются (опубликовано в Ясийел 1п МасЬешапсэ шк( МесЬахисв Ргыепсес( го В. гоп Мнев (Хезг Ъог1с: Асадеппс Ргееэ, 1954), 49-48), и Т. С, Мацкин (Т. Я. МосхЫп) — для адаптированных коэффициентов [см, Ви11. Атег. МаСЬ.
Яос, 61 (1955), 163). Для исследования этого вопроса можно распространить понятие алднтивной цепочки из раздела 4.6.3 на понятие цепочки полииомов. Цепочка поликанов — это последовательность вида (24) х=ле, Л1, ...„Л„=и(х), где и(х) — некоторый полинам от х и для 1 < г' < г либо Л; = (хЛ ) о Лю О < у, Ь < 1, (25) либоЛ;=а оЛы О<Ь<1. Здесь символ "о" означает какую-либо из трех операций ("+", "—" или "х'), а ау — так называемый параметр. Шаги первого вида называются шагами цепочки, а шаги второго вида — шагами параметра.
Будем предполагать, что на каждом шаге параметра аз используются разные параметры; если существует е шагов параметра, то они должны включать аы аэ, ..., а, в таком порядке. Следоввжльно, полипом и(х) в конце цепочки имеет вид (26) и(х) = д„х" + + 9~х + оо где о„, ..., В, ое — полиномы от ам аэ, ..., а, с целыми коэффициентами. Будем интерпретировать параметры ам аз, ..., а„как действительные числа, и, следо- Лв ж Лг —— Лз = Ль+зв = Лг+зв = Лз+з~ = аз+ Ла Лг хЛ1 ог хЛ, (27) а1+гв+ Лз аг+г +Лз 1<г<я/2. Лв+зв х Лг+зв Здесь (и/2) + 2 умножений и и сложений, (и/2) + 1 шагов цепочки и п + 1 шагов параметра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
