AOP_Tom2 (1021737), страница 148
Текст из файла (страница 148)
ред.). Мы уже знаем, как его использовать в связи с заменой основания системы счисления в разделе 4.4. Полный процесс требует и умножений и п сложений минус одно сложение для каждого нулевого коэффициента. Кроме того, нет необходимости за|гоминать промежуточные результаты, так как каждая величина, появляющаяся в процессе вычислений, немедленно используется после ее получения. В. Дж. Горнер ( 1т'.
С. Ногпег) предложил это правило в начале 19 века (РЛ!!озо- РЬ!са! ТгапэасНопз, Коуа1 Яос!егу о! Ьопбоп 109 (1819), 308 — 335) в связи с процедурой вычисления корней полинома. Известность последнего метода (см. 3. Ь. Соо1108е, Ма!Бета!!ся оу Сгеас Атагеига (Ох!огг), 1949), глава 15) объясняет то обстоятельство, что имя Горнера связывается с формулой (2), но в действительности Исаак Ньютон использовал такую же идею более чем на 150 лет раньше.
Например, в общеизвестной работе Ве Апа!уэ! рег ~Ег!паг!одея 1пбп!газ, написанной в 1669 году, Ньютон записал у-4х у:+5 х у: — 12 х у:+17 для полинома у4 — 4уэ+буз — 12у+17, что поясняет, почему позже метод приобрел известность как метод Ньютона нахождения корня. Тут ясно видно идею формулы (2), так как он часто обозначал группирование горнзонтальными линиями и двоеточием, а не круглыми скобками. Ньютон использовал эту идею на протяжении нескольких лет в неопубликованных заметках. (См.
ТЬе Ма!Летас!са! Рарегэ оГТзаас 7уея гоп, ей1ес1 Ьу П. Т. 1т'Ь1теэЫе, 1 (1967), 490. 531; 2 (1968), 222.) Независимо метод, эквивалентный правилу Горнера, фактически использовался в 13 веке китайцем Чин Чи Шао (СЬйв СЬш 8Ьао) (см. г'. !л411олтЬ Тбе Пете!оргпепг оТЫагЛетаг!сэ т СИта аш1,!арап (1913), 73 — 77], Предложим несколько обобщений правила Горнера. Сначала рассмотрим вычисление и(х), когда х — комплексное число, в то времи как коэффициенты ил— действительные числа. В частности, когда х = е'о = соэО + г'сйпд, поливом и(г) является, по существу, двумя рядами Фурье (на самом деле — суммами. — — Прим, ред,) (ив+ иг соаО+ +и„соатгО) + г(и, сйпО+ -~-и„ыппО).
Комплексное сложение и умножение, очевидно, может быть сведено к последова- тельности обычных операций над вещественными числами. требует требует требует требует или 1 сложения 2 сложенвй 2 умножений 4 умножений, 2 сложений 3 хмножений. 5 сложений вещественное + комплексное комплексное + комплексное вещественное х комплексное комплексное х комплексное (См. упр. 41. Вычитание рассматривается здесь как эквивалент сложения.) Следовательно, правило Горнера (2) использует каждые 4п — 2 умножений и 3п. — 2 г южений или Зп — 1 умножений и бп — 5 сложений для вычисчения и(г), когда х = х+ ги — комплексное чисоо. В действительности без 2п — 4 сложений можно обойтись, так как каждый раз выполняется умножение на то же чигшо х. Предлагаем альтернативную процедуру вычисления и(х + гу): аг — — и„, 6г =и„ г=х+х, э=х +у; г г, аг=6г г+гаг ы 61 — — и„.— ааг ы 1<1'(и.
(3) и(х) = (...(игр,(г~х + игО,~г)-г)х + )х + ио + ((... (иг( (г, гх~ + игг„~г1 г)х + )х + иг) х (4) В правиле второго порядка используготся и+ 1 умножение и и с юженнй (см. упр. 5), что с этой точки зрения оно не улу гшает правило Горнсра. Но существуют по Тогда легко доказать по индукции, что и(х) = ха„+6„. Эта схема (В1Т 5 (1965), 142:, также см.
С. Соегоге!, АЛХЛг 65 (1958), 34 — 35) требует только 2п + 2 умножений и 2п + 1 сложений, так как она является усовершенствованным правилом Горнера, когда и > 3 Лля рядов Фурье, когда - = е'о, имеем о = 1, так что число умножений уменьшается до и + 1. Отск>да мораль: хороший программист не станет неразборчиво использовать встроенные характеристики комплексной арифметики языков программирования высокого уровни. Рассмотрим процесс деления полинома и(х) на х — хо, используя алгоритм 4.6,10, чтобы получить и(х) = (х — хо)о(х) + г(х), здесь Осй(г) ( 1. В этом соучае г(х) — константа, не зависяпгая от х и и(хо) = О а(хо) э- г = г. Проверка этого процесса деления позволяет обнаружить, что вычисления, по существу, такие же, как и правило Горнера для вычисления и(хо). Подобным образом, если мы делим и(г) на полинам (х — хо)(х — хо) = хг — 2хог + хг + ио, результаг вычисления оказывается эквивалентным (3).
Получаем и(х) = (х — го)(х йо)0(г) + а~х .ь 6п; отсюда и(го) = а„го + 6 . Вообще, если разделить и(х) на г"(х), получится и(х) = ((х)д(х) + г(х), а если г'(хо) = О, то и(хо) = г(хо); это наблюдение приводит к дальнейшим обобщениям пРавила ГоРнеРа. НапРимеР, можно положить )(х) = х- — хог, что даат пРавило Горнера "второго порядка': Производные и замена переменной. Иногда необходимо найти коэффициенты и(х + хо) с заданными постоянной хо и коэффициентами и(х). Например, если и(х) = Зхэ+ 2х — 1, то и(х — 2) = Зхэ — 10х+ 7. Это аналог проблемы преобразования системы счисления, преобразующей основание х в основание х + 2.
По теореме Тейлора новые коэффициенты заданы производными и(х) в точке х = хо, т. е. и(х+ хо) = и(хо) + и (хо)х+ (и"(хо)/2?)хо + + (иУ"У(хо)/и)) х", (7) так что задача эквивалентна вычислению и(х) и всех ее производных. Если записать и(х) = 9(х)(х — хо) + г, то и(х + хо) = д(х+ хо)х + г„.в таком случае г есть постоянный коэффициент и(х+хо) и проблема сводится к нахождению коэффициентов д(х + хо), где д(х) — известный полипом степени и — 1. Таким образом, предлагаем следующий алгоритм. Н1. Присвоить оу ч — и для 0 < у < и.
Н2. Для ус = О, 1, ..., и — 1 (в таком порядке) присвоить оу +- оу + хооз м для у = и — 1, ..., Уо + 1, Ус (в таком порядке). 1 По окончании шага Н2 получим и(х+ хо) = т„х" + . + о, х+но. Эта процедура была главной частью метода Горнера нахождения корней, и когда Уг = О, она является точным правилом (2) нычисления и(хо). Метод Горнера требует (по+и)/2 умножений и (глэ+и)/2 сложений, но заметим, что, если хо — — 1, все умножения опускаются. К счастью, можно свести общую задачу к случаю, когда хо — — 1, введя сравнительно небольшое число умножений и делений.
Б1. Вычислить и запомнить значения хоэ, ..., хо. Я2. Присвоить о ч — иух,', для 0 < у < н. (Сейчас и(х) = и(хох).) ЯЗ. Выполнить щаг Н2, только с хо = 1. (Сейчас о(х) = и(хо(х+1)) = и(хох+хо).) э4. Присвоить о е- о,/хоэ для 0 < у < и. (Сейчас о(х) = и(х + хо) как и требовалось.) 1 Эта идея, предложенная М. Шо (М.
ЯЬалт) и Ж. Ф. Траубом (д. Е. ТгапЬ) [,УАСМ 21 ~ 1974), 161-167), обеспечивает такое же количество сложений и такую же численую л стойчивость, как и метод Горнера, но при этом необходимы только 2п — 1 умножений е и — 1 делений, так как о„= и„. Приблизительно эн этих умножений можно по очереди избежать (см. упр. 6). ' Шо и Трауб отметили, что существует дополнительный способ экономии времении счета, если нужны только несколько первых или последних производных. На|~ чимер, если нужно вычислить только и(х) и и'(х), то для выполнения следующего ь ~горитма потребуется 2п — 1 сложений и около и+ л/2п умножений и/или делений. 111.
Вычислить и запомнить значения хэ, хэ, ..., хл, хзл, где У = (л/н/21. 112. Присвоить о е- и хубу для 0 < у < и, где /(у) = у — 1 — ((и — 1 — у) шог( 21) для О < у < и, а /(н) = й 11З. Присвоить е ч- оу + иучлхэб> для у = и — 1, ..., 1, 0; здесь д(у) = 26 когда п — 1 — у — положительный множитель 21, иначе д(у) = 0 и нет необходимости умножать на х'ОУ. 114. Присвоить ау 4 — ау + и 4.4хгб4 для 4' = и — 1, ..., 2, 1. Теперь ьо/х44о4 = и(х) и а4/х404 = и'(х). $ и(х) = и4х~ + изх + изх + и4х+ иа, и4 ф О.
(8) Эту формулу можно переписать в виде, впервые предложенном Т. С. Мацкиным (Т. Б. Мо4хк4п). у = (х + аа) х + а4, и(х) = ((у + х + ав) у + аз) а4. (9) для соответственно "адаптированных" коэФФициентов ао, ам ам аз. а4. Вычисления по этой схеме включают три операции умножения, пять операций сложения и (на машине с одним сумматором, подобной машине 81Х) одно указание запомнить промежуточный результат у во временном запоминающем устройстве. Па сравнению с правилом Горнера в этой схеме мы заменили умножение сложением и, возможна.
командой запоминания. Даже эта сравнительно малая экономия имеет смысл, если полинам вычисляется часто. (Конечно, если время умножения сравнимо со временем сложения, (9) не дает улучшения: для вычисления обычных полиномов четвертой степени всегда требуется по крайней мере восемь арифметических операций.) Сравнив коэфф4щиенты в (8) и (9), получим формулы для вычисления а,, выраженных через ию ао = 4(из/и4 — 1), аз =  — 2ам м — ит/и4 аа(440 + 1) с"4 и1/и4 аОР~ аз = иа/и4 — а4(а4 -г аэ)., а4 = и4.
(10) Подобная схема вычисления полинома четвертой степени за такое же число шагов, как (9), предлагается в упр. 18; этот альтернативный метод дает в некоторых случаях большую точность, чем (9), хотя он уступает в точности другим. Полиномы, встречающиеся на практике, часто имеют достаточно малый старший коэффициент, поэтому деление на и4 в (10) ведет к неустойчивости. В таком Адаптация коэффициентов. Возвратимся к нашей первоначальной проблеме вычисления заданного полинома и(х) для "случайных" значений т, настолько бьютро, насколько это возможно. Важность данной проблемы отчасти является следствием того факта, что стандартные функции, такие как гйпх.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
