Бабенко - Основы численного анализа (947491), страница 10
Текст из файла (страница 10)
3. Пре,вложите бинарный метод вычисления х", основанный на считывании двоичного представления числа п справа налево. Дайте обоснование этого метода, 4. Предложите метод вычисления числа х, основанный на разложении и либо и — 1 на простые множители. Приведите пример такого п < 100, ддя которого этот метод будет эффективнее бинарного. 6. Вычисление многочлена. Рассмотрим задачу о вычислении значения многочлена р(х) .= .—.- а„х" !. а„1хи -' ....~- ае для данного значения аргумента, х. Будем делать вычисления по следующему правилу; подсчитаем последовательность степеней х-,...,х", а затем, найдя произведения а„хи У (~' = О, 1, ..., и — 1).
сложим результаты. На 40 Глава П Пввигавввка задач чивлевггвга авалова это потребуется 2и — 1 умножений и и цложений плюс некоторые дополнительные операции хранения промежуточных результатов и операции выборки. Однако можно тот же результат получить более экономным образом, если воспользоваться схемой 1"орнера методом вычисления значений мпогочлена, указанным И. Ньютоном за 100 лет до У. Горнера. Запись многочлена с помощью вложенных скобок: р(х) = (... ((а„х + - ав л)х, а„я)х+...)х+ ао подсказывает лгетод вычисления; строилг последователыюсть я1, = А, л лх + п„1' = и, и — 1, ..., О, Лаэ л = 0; (14) в итоге полу чаем Ло .—..
р(х). В процессе вычислений будет произведено и умножений, а число сложений на единицу меньше числа ненулевых коэффициентов многочлена. Сам метод не требует дополнительного места для хранения промежуточных результатов. Схеллу Горнера можно применять и для вычисления значений сулллг следующего вида: и Б.(х) — — ~ алрь( ) л:о где функции (рь(х))л и р л(х) =- 0 удовлетворяют линейным разностныла уравнениям второго порядка рлтл(х) + аь(х)рь(х) + Дл(х)рь л(х) = О, 1. = О, 1, ...,и — 1. (16) Соотношениям такого вида удовлетворяют классические ортогональные многочлены, функции Бесселя н другие специальные функции. Схема вычисления значения суммы (15) является непосредственным обобщением схемы (14); строим последовательность Л = аг — о.Л, л — Зго лА ., у = и..
.и — 1,..., О, Литл =- Лвчг = 0 (17) и получаем (18) Я (х) = Аоро. При о. = — х, ~31 = 0 (г' = О, 1, ..., и — 1) получим схему Горнера. Если предварительно вычислены значения о (х) и,'3 (х), то на вычисление Я„(х) потребуется йи умножений и 2и сложений. В частности, для разложений по многочленам Чебышева получаем экономный способ вычисления частных сумм ряда. Чтобы убедиться в справедливости форллулы (18), проведем индукцию по и.
Если и — — 2, то формула (18) очевидна. Покажем, что форлгула (18) верна для Явлл(т), если она верна для Я„(х). Пусть формула (16) верна при й .— — и; тогда Я„ л(х) = ~ ~бтра(х), ь=о 'й4, Примеры лгврипэмвв; аив ив алгоритмов где Ьп = ап — апапэ и Ь„г = ап, — Впала и Ьь = а~., Ь < п, — 2. Построим последовательность Апэ ы ..., Ао по формуле (17), применяя ее при 1' = п г 1, и, ..., О и считая А„~ з = Апэ.з = О. Построим также последовательность Вп, ..., Во, используя для .этого величины Ьп,, Ьо. Тогда Япзл(х) = Лоро(х), а, с другой сгоропы, Апэ~ = а„ьм А„= ап — апапэа = = Ьп = Вп .4п 1 = ап — 1 — ап — гАп — оп 4пээ = Ьп — 1 ап — 1Вп = Вп — 1 и,.
следовательно, А. †-- В,,(п — 1 ) у ) О)., т.е. Ао =-. Во. В заключение этого пункта сделаем несколько замечаний. При вычислении многочленов по схеме Горнера, а также сумм вида (15) мы пользуемся рекуррентными соотношениями. Поэтому возможно, что погрешность, сделанная на некотором шаге в процессе вычислений, может вызвать большую погрешность в окончательном результате.
Стало бытгь необходимо исследовать влияние погрешностей, вносимых на каждом шаге процесса из-за приближенного выполнения операций., на точность окончательного результата (см. гл. 8). Естественно возникает вопрос об оптимальности схемы Горнера, который впервые исследовался в (139].
В качестве одного из результатов укажем, что если некоторый мотод вычисляет значения всех полиномов степени не больше п, то оп содержит но менее п умножений. Таким образом, правило Горнера оптимально в том отношении, что требует минимально возможного числа умножений. Подобным образом, если некоторый метод вычисляет значения произвольного многочлена, он требует не менее а сложений (см. (71). Схема Горнера легко допускает распараллеливание.
Именно, если мы имеем г параллельно работающих процессоров., то можно поступить с.тедующим образом. Пусть и = гт + э (О < в < г), запишем р(х) в виде Н г — 1 ш — 1 р(х) —... ~ х ~~ а„.,~(хг)'+ ~~ х ~~ а„эз(х')э. шв 1 з=о Тогда на 4-и процессоре можно вычислить хо 2,' а,, тв(х")з, если й < в, э=о и хв 2, а, э в(хп)э. если в < а < г — 1. СУмгниРовзнне полУчснных РезУльэ=о татов можно произвести за 1ояо г ~ шагов работы системы, если отвлечься от операций обмена между процессорами.
Таким образом, каждый из процессоров должен выполнить не более, п/т ~ + шах 1(Ь) -1. 2 умножений о<г — 1 и не более п/2' .1. (1ойт г, сложений. Привелем рекуррентную формулу для вычисления значения тригонометрического многочлена, который запишем в видо Ь(х) =- аг + ~ (агн вшух+ агз ~ г сов ух). Строим последователыюсть Аь = — Аььэ -1. 2Аьла совх+аь (Ь = 2п+ + 1, 2п, ..., 1), используя начальные данные Азпеь = Атп.~.э = Атпуз = Глава 1. Посгааповка задач численного анализа = г(галз = О. Тогда т(х) = А> —;- Агвгпх — Азсозх. Если предварительно вычислены ейп х, соя х, 2 сов х, то на вычисление 1(х) требуется 2и - 1 умножений и 4и — 1 сложений.
В частном случае тригонометрических многочленов вида 1(х) —.- ~ ~а> сое(2> — 1)х >=1 для их вычисления строим рекуррентную последовательность Аь = — г(ьлг + 2Аяг > сов 2х + аь (>г = п, и — 1, ..., 1), Ал х = А„е> = О. Тогда т(х) = (А> — А») соях. Если предварительно вычислены совх, 2соэ2х.
то на вычисление 1(х) требуется и, умножений и 2п — 2 сложений. Справедливость прелложен- ных рекуррентных формул (147) читатель может установить, пользуясь методом математической инлукцни. 3 ад а ч и. б. Пусть Я„(х) определяется формулой (15), где функции (рг (т) ) о удовлетворяют рекуррентному соотношени>о рог> (х) --,'- оьорг (т) <-... э. + ел ра — (х) =-. О (1..—.- г, .г-1-1,..., и — 1). Предложите метод вычисления Я»»(х). аналогичный правилу Горнера. б. Пусть коэффициенты многочлена р(х) .=. а х" +...
+ а>х+ а>» вещественные, а х = а+го е С, Найдите схему вычисления р(х), требующую 2п+ 2 умножений и 2п — 1 сложений. в-1 >' =~а>а>~>, 1'=0,1,...,и — 1, >=а (19) где ш = ехр(2ягт/и) первообразный корень и-л степени из 1; тем самым НОД (т, и) = 1. Последовательность (7е, ..., )'„>) будем называть днскрегпныги преобразованпеги Фурье последовательности (аа, ..., п„>). с1>ормула (19) имеет смысл при люоом целом >1 Легко видеть, что она опредечяет периодическую последовательность () ) с периодом и: 7'ла ге >' . Поэтому (19) определяет функцию на Ха па группе классов вычетов по гной и. Мы рассматриваем нанменыпне неотрицательные вычеты, т.е.
> = О, 1,...,и — 1. Это замечание нужно иметь в виду при рассмотрении дискретного щ>еобразования Фурье. Построим обратное преобразование Фурье. Для этого достаточно заметить, что если 1 = О, 1, ..., и — 1, то а>~ в ф 1, когда 1 ф 1ь Поэтому, 7. Быстрое преобразование Фурье. Пусть (ае, ..., а„г) - - заданная последовательность чисел: а, Е С (> = О, 1,..., и — 1). Определим новую последовательность: 'й 4, Пр меры, лгоритмоог оиолиг олгоригимов используя формулу для суммы геометрической прогрессии, получим и — 1 и7'гог 7~ —..
716п., 7-. О (20) и — 1 и,— 1 и — 1 и — 1 и — 1 ,7=О 1=о 1=О 7=О или 1 и — 1 ао= — ~~ (ги7 17, )7=0 1, ..., и.— 1. (21) и 7=О Формулы (19), (21) определяют прямое н обратом!с дискретные тгреобразоеанил Фурье. Отметим, что формула (21) имеет смысл при любом целом Ь и определяет периодическую последовательность периода и, или функцию на л ".
Поэтому, говоря о преобразовании Фурье последовательностей из и чисел, мы будем неявно предполагать, что они определены на классах вычетов группы Х". Сообразно этому будет вычисляться их преобразование Фурье. В векторном виде преобразования (19), .(21) можно записать следующим образом. Пусть а = (ао, ..., аи .1)', 1 =- (уо, ..., 1„1)'. Тогда ) =Га, а=Г (=п Г), (22) где Г = (и7"7Я 1 матрица Вандермонда, а Г матрица, комплекс- Й,,7 =: о но-сопряженная к Г.
Будем рассматривать С" как п-мерное эрмитово пространство: скалярное произведение в нем обозначим, как обычно., через (, ). Вели а, Ь б С", 7" = Га, д = ГЬ, то (У', 9) —... п(а, Ь), лти (Га, ГЬ) =- п(а, Ь). (2) Действительно, и-1 к!=о и — 1 = ~ а1Ь7 ~~~ и7"Р 77 = п~~ а7Ь! = п(а, Ь). !и=О Введем еще некоторые определения. Сеерткой векторов а и Ь назо- ВЕМ таней ВЕКтер С = (СО, ..., Сги — 1) лте зи — 1 и сь —... ~~ а7Ь1. ! .— — ~~ а!Ьи 1, 1=о 1=о (24) где 6!ь символ Кронекера. Умножая (19) на ло го и суммируя по у,. получим Глава 1.
Поеглаповка задач численного анализа причем будем считать, что а! = Ь! = О, если 1 < О или 1 > и. Операцию свертки будем записывать в виде с = а * Ь. Большое неудобство введенной таким образом операции свертки состоит в том,. что а, Ь й С", с Е С2".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
