AOP_Tom2 (1021737), страница 149
Текст из файла (страница 149)
совх, е' в т. д., обычно вычисляются подпрограммами, которые опираются на вычисление определенных полиномов. Поскольку такие полиномы часто вычисляются, желательно найти возможно наиболее быстрый метод вычислений. Произвольные полиномы степени пять и выше можно вычислить, выполнив меньше операций, чем требуется по правилу Горнера, если сначала "адаптировать" коэффициенты ио, им ..., и„. Как будет пояснено ниже, процесс адаптации может включать в себя уйму работы, но предварительное вычисление не является ненужной потерей времени, так как оно должно производиться только один раз, а полинам вычисляется многократно.
Примеры "адаптирования" полиномов для выполнения стандартных функций приводятся в работе В. Я. Пана, СССР Вычисл. матем. н матем. физика 2 (1963), 137 — 146. Простейп|ий случай, для которого адаптация коэффициентов полезна, встречается при использовании полиномов четвертой степени: У (х + об) п(х) (((У + 411)у + 11Х)(х + оз) + с14)об.
(11) Д1я определения а1 теперь требуется решить кубическое уравнение (см. упр. 19). На многих компьютерах количество требуемых формулами (11) операций "запомнить" меньше трех; например, мы, возможно, сумеем вычислить (х + аб), не запоминая х + об. Действительно, большинство современных компьютеров имеет более одного арифметического регистра для вычислсний с плавающей точкой, так что вполне можно обойтись без запоминания. Поскольку различные компьютеры для выполнения арифметических действий предоставляют большие возможности, в этом разделе следует учитывать только арифметические операции, а не операции запоминания и загрузки гумматора, Вычислительные схемы обычно простым способом можно адаптировать к любому конкретному компьютеру так, что понадобится несколько дополнительных операций; с другой стороны, следует помнить, ч:о эти операции могут свести на вет экономию одного или двух улбножений, в особенности если программа компилируется машиной не оптимачьно.
Полипом шестой степени и(х) = ибхб + .. + и,х + иб всегда можно вычислить, используя четыре операции умножения и семь операций сложений, по схеме х = (х + об)1 4 о1, п1 = (х + 172) б + оз~ п(х) = ((ш + х э. о4)1б + йб) об. (12) (П. Е. КппгЬ, САСМ 5 (1962), 595 — 599.) Такая схема позволяет избежать двух из шести умножений, требуемых по правилу Горнера.
Здесь снова необходимо решить кубическое уравнение: так как аб = иб, можно предположить, что иб — — 1. При этом предположении пусть 61 = (и; — 1)/2,,97 — — иб — 711(61 + 1), ()з = из — Адб, Р4 = А — А, А = ит — АРз. Допустим, что 194. -вещественный корень кубического уравнения 2У + (2121 — )7т + 1)у" + (278б — ~47184 — Рз) у + (и1 —,Зтйб) = О. (13) (Это уравнение всегда имеет вещественный корень, так как левая часть полинома стремится к +ос для болыпих положительных значений у и к — оо -для больших отрицательных значений у; оно должно принимать значение "нуль" где-то посере- лине.) Если сейчас определить 777 = 19б +,эбан'7б + 7эб ~ дб = Рз — Об — 777, случае предпочтительней на первом шаге заменить х на ~и4)~7~х, сводя (8) к полиному со старшим коэффипиентом, равным 4-1. Подобное преобразование применимо к полиномам более высоких степеней.
Эта идея предложена Ч. Т. Файком (С. Т. Ейсе) (САСМ 10 (1967), 175 178]: он рассмотрел несколько интересных примеров. Любой полином пятой степени можно вычислить, используя четыре умножения, шесть сложений и одно запоминание согласно правилу и(х) = П(х)х + иб, где П(х) = ибхб + ибхэ + изхт + иэх + и1 вычисляется, квк и в (9).
Кроме того, можно произвести вычисление, выполнив четыре умножения, пять сложений и три запоминания, еггли вычисления осуществлялись по формуле то окончательно получим аз =А-ао, ат = ттв аоаг, ав = дн — дт ат ав = ио 6т0н (14) ао = дг — 2дв, аз = Рт — атаг, Эту процедуру можно пояснить на следующем примере: предположим, нужно вычислить хв + 13хв+ 49хв + 33хз — 61хг — 37х+ 3. Получим ав = 1, бт = 6, дг = 7, Оз = — 9, Рв = — 1, бв = -7 и таким образом придем к кубическому уравнению 2у — 8у + 2у + 12 = О.
(15) Это уравнение имеет корень бв = 2. Находим ()т = — 5, ат — — -7, ттн = -6, ав — — — 27. аз=16, аз=6 ао — — 3, аг = 3, Следовательно, окончательная схема такова: х=(х+3)х — 7, то=(х+3)х+16, и(х) =(то+г+6)то — 27. Благодаря явному совпадению дважды появляющихся величин х + 3 можно найти метод, использующий три умножения и шесть сложений. Другие методы подхода к решению уравнения шестой степени предложены В. Я. Паном (Проблемы кибернетики 5 (1961), 17 — 29]. Один из них требует на одну операцию сложения больше, но включает только рациональные операции на первых шагах; однако кубическое уравнение необходимо решать.
Можно записать процесс решения в следующем виде: г = (х+ао)х+ат, ю = г+х+аг, и(х) = (Из — х+аз)ш+ав)г+ав)ав (16) Для определения а мы снова один раз делим полинам на ив = ав и таким обра- зом приходим к нормированному многочлену и(х). Затем можно проверить, что а =и т3и аг = (ит — аоиг + аоиз — аоид + 2а5)/(из — 2аоив + 5ао). (17) Заметим, что для метода Пана требуется, чтобы делитель в (17) не обращался в нуль. Другими словами, (16) можно использовать только тогда, когда 27изив г— 18ививив + 5из зт- О; (18) в действительности зто значение не может быть таким малым, поскольку ат ста- нет слишком большим. После того как ат будет определено, остальные а можно определить из уравнений бт = 2ао, 63 = аз= (19) из — аобг — атД, г(рз — (ао — 1)рг+ (ао— Рг — (ао 1) — аз — 2ам г — 6в )уг = ив — аобт — ам Вв = иг — аорз — атрг, 1)( г 1)) ав = А — (аз + атИаз+ а1), Мы детально обсуждаем случаи степеней и = 4, 5, б,поскольку такие значения и чаще встречаются в приложениях, Сейчас рассмотрим общую схему вычисления полиномов и-й степени, метод, включающий максимум (и/2) + 2 умножений н п сложений.
Теорема Е. Каждый нолшюм и-й степени (1) сдсйствительнымн коэффяцнентамц и > 3, можно вычнглцть по схеме г ( (ипу+ оо)у+ йо, и четное, й=х+с, ю= в,. (и.у+До: и нечетное, и(х) ( . ((х(ю ог) + дг)(ю ог) + Фг) .. )(ю от) + Рт прн подходящих вещественных параметрах с, оь и )1ы где т = (и/2) — 1. На самом деле можно выбрать этн параметры таким образом, что 13е, = О, (20) Докаэагаельсшво. Сначала рассмотрим условия, при которых о; и ~9 могут быть выбраны в (20) при фиксированном с. Пусть р(х) = и(х — с) = а„х" + а„гх" ~ + + агх+ ае. (21) Покажем, что р(х) имеет вид р, (х)(хг — от) + )3„, для некоторого полинома рг (х) и некоторых констант о„„д .
Если разделить р(х) на хг — о, то остаток З,„будет константой только в том случае, если вспомогательный полинам О(х) = аг +гх~ + агт — 1х ' + + аы (22) сформированный из нечетных коэффициентов р(х), кратен х — оее Наоборот, если д(х) имеет множитель х — о, то р(х) = рг(х)(хг — ат) + щ при определенных константах,9а„которые можно определить посредством деления. Также необходимо, чтобы рг(х) имел вид рг(х)(хг — о,„г)+))ы м и это эквивалентно тому, что д(х)/(х — о ) являетея кратным х — о Е если й,(х) — полинам, соответствующий р1(х), как а(х) соответствует р(х), то о,(х) = а(х)/(х — о ). Продолжая в том же духе, найдем, что параметры оы йы ..., о, й существуют тогда и только тогда, когда й(х) = аг -~-к(х — о1)...(х — о ).
(23) Другими словами, каждый полинам д(х) тождественно равен нулю (и это возможно, только когда и четное) или же д(х) — полинам степени пг, имеющий все вещественные корни. Поразительный факт был обнаружен Дж. Ивом (Л. Еее) (Хигпег. Маг1г. 6 (1964) ,. 17-2Ц: если р(х) имеет по крайней мере и — 1 комплексный корень, все вещественные части которьж не отрицательны илв не положительны, то соответствующий ногином а(х) тождественно равен нулю или имеет все вещественные корни (см. упр, 23).
Поскольку и(х) = О тогда и только тогда, когда р(х + с) = О, необходимо просто выбрать параметр с достаточно большим, чтобы по крайней мере и — 1 корень и(х) = 0 имел вещественные части > -с, и (20) будет применяться всякий раз, как только а„ 1 = и„ г — пси„ ф О.
Можно определить с таким образом, чтобы этн услоння выполнялись, а также чтобы й = О. Первые и корней уравнения и(х) = О определены. Если а+ Ы— корень, имеющий наибольшую или наименьшую вещественную часть, и если 5 ф О, то положим с = — а и о = — 6~, тогда х — о является множителем и(х — с). Если корень с наименьшей или наибольшей вещественной частью вещественный, но корень со второй наименыпей (или второй наибольшей) вещественной частью не вещественный, то применяется такое же преобразование. Если два корня с наименьшими (или наибольшими) вещественными частями вещественны, то их можно выразить в виде а — 6 и а+6 соответственно.
Пусть с = — а и а = 6; снова х — о г, множитель и(х — с). (Однако часто возможны другие значения с: см. упр. 24.) Коэффициент ао 1 будет ненулевым для хотя бы одного из этих вариантов, если только д(х) не будет тождественно равным нулю. 6 Заметим, что этот метод доказательства обычно дает по крайней мере два значения с, переставлять ог, ..., о г можно (т — Ц! способом. Некоторые из этих вариантов, вероятно, дают большую точность, чем остальные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
