Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 33
Текст из файла (страница 33)
Задача интсрполи1ювання г)зункции многочленом по узлам Г 20 — 1'! х = соэ ! я — — ~ - нулям ыногочлсна Чебьппева Т',„(х) — после такой 2т,l замены сводится к задаче имгерполираеаиия функции ((гоэ0) при поью- 21 — 1 щи тригонометрического многочлгиа ~ а соя(11) по узлам 1 = гг ' 2т г-е образу!ощип равномерную сетку. З 4. Быстрое преобразование Фурье Осуществление прямого и обратном! г!некратных преобргхюваний Фурье Уе... Хн.-!) гг (Ае,..., Аь-!) лвляется сосшвной частью решения многих задач. Р(епосредсгеенное осуществление этих преобразований по формулам (3.4), (2.7) требует Г)()г'г) арифметических операций. Рассмотрнл! вопрос о возможности сокращения этого числа.
Для определенности речь пойдет о вычислении коэффициентов Аг по заданным значениям функции. Идея поп!росии» алгоритмов Гли!трохи пргоГуизоеакпл Фурье опирается па то, что при согтавном 1г' в глагаемых правой части (3.7) можно «ыдглить группы, которые входят в выражения различных коэффициентов Ае. Вычисляя каждую !руину только един раз, можно знлчитгльно сократись число операций. Рассмотрим сначала случай 1г' = ргрз; р!, Рз ф 1. Представим д, 1, лежащие в пределах О < Фу < 77, в виде д = рл +гг!Оз, у =-уз -~-рту!, где О < Ф, в < р!, О < дю уз < рг.
имгом цепочку соглиопгшги!г и†! Аг — — А(йм йз) = — ~ у!ехр! — 2х! — г =- .ггУ ) йг ' '( 1У)' г=е (И Е р!Оз)(уз + рзу!) ~ ехр ( — 2ш л=е гг=е Р!7гз Из равенства (и! +ргйз)(уз +рх!!) пуз угсл ргрг Ж р! Глава 4. Приближение Фуакпий м смежные вопросы и предыдущего соотно!пения получим А!ды дз) =- — ~ А )!д1, 12) ехр -2я! — ' 1! !!=а 2д )' где Р! — ! 1, =-о Непосредственное вычисление всех А!!)!д1,22) требует О!р1~122) арифм! тичоских операций, а последующее вычисление А!д1, дз) -еще 0 (р!р~з) операций. Поэтому ври рг, рз = О!в!2!) общее число операций гюс!авит 01!у~у~).
Точно так же при 1д = р!... р, строится алгоритм вычи1левия совокупности значений Ае, для которого общее число операций но превосхщ!ит сг!102! в- ° ° ° з- р,), здесь с — постоянная, ие зависящая от )д. Вьшип!ем соответствующие расчетные формулы лля наибопес употребительного внучая р1 = ° = р, =- 2.
Представим числа д, У в вида д= ) дь2 ', ) = ),:бег- !2в' где да!ге! „, = О, 1. Величину д12 ' представим в виде ( в =1 =1 Ь=1 !де в — целое, равное сумме всех глагвемых вида дь!пв! ж21! ' " 2, у ко- торых йз-п1-г — 2 > О. Очевидно, что ехр( — 2х1 — ! = ехр) — 2и1) — -в)(, поэтому Н-1 А!дг,...,дг) =Ае — — — ~у!ехр! — 2и1 — ! =- !=о 1 1 1 — .11 и;В-;В,.-.. --„- )--В(В- --)--) г,=о п=о -1 В=1 177 ! 4. Быстрое преобразование Фурье После перегруппировки слагаемых имеем г .=-,П-.(- ': П--). э,=о ь=г г ( г — г х — ~» ехр ~ — 2я!1„ 12г " 2 дядя ' х ) 2 э,,=о я=-г (г х .. х — ~ ехр( — 2ягуг2 дг)урээг',-гы. эщ 'гг э,=:о Это соотношение можно запиг'ать в виде послодовательноети рекуррепт- ных еоотношенпй А (дг,..., дм; у,ьег,..., 12) = ( ) — ехр~-2я1,2 Я') дг„2ь г А(гь г»(дг,..., д г; 1,,,,1,), 2 э,„=е г=1 ш=1,,г, где (о( (о) А("1(дг,..., д,) = А(дг,..., д,).
Переход от кажной совокупности А(м г) к сопокушвегн А1м) требугы 0(17) арифметических и логичесних операций; есего заких шагов г, по- этомУ общее число опеРаций имеет по»ыдок 0()дг) = 0()гг'!ойзЖ). Вью нелепее прн оомопги совокупностей А!"'1 даог меиыпее накопление еычислнтюгьиой погрешности по сравнению с формулами (3.7).
Определенные удобства нмегочтя также при вычислении эяспоненэ; входящих я расчотные формулы. Прн вы гиглении аеличиа А1ь'1 испозьзукгтгя эначеяня <хр(-2я!12 "*), г = О, 1,..., 2"' — 1. В честности, прн пг = 1 величина еяр(-г11) принимает энпгения +1 или -1. Для вычисления значений А1ь'ьг» потребуются еще значения ехр( — 2т!12 1 ь'!) при нечетных у, удоелепгоргпощнх нерапенстэу О < У < 2"'+г. Их можно эычислиэь через уже вычисленные до этого величины, е чытнссти, при поьющи сгютаопгений (т > 2) ехр(-2я1' 2 ~ + ехр( — 2я! — 2 ехр(-2нц2 Г""+г») = 2гш(я2 ') где, я свою очередь, Г'1 соэ(гг2 *) = (( — (1+соя(гг2' * )) при т > 1. Глав» 4.
Прнблилгение функций н гмежные вопросы 178 В ряде случаев удается еще уменьшить число операций. Один из таких случаев уцомннался еьгвм: дана вещественная функция Пг) = я(сочг), известная е то.щах Гг = гг(21 — 1) /(2йг); тр.*буегся нанти коэффициенты ивтерпопяпионного миогочлсна Аз соэ 11. з =е Другой случай: прн четном Ж ладаны значения функции н1т- 1 Аз мп 2чу1 е точках г = 1/ю, о < 1 < гг/2: нУжно опРеделнть коэффициенты Ам Задача 1. Найти коэффициенты с произведения двух многочлснов А азхз А Ьз.сз = ) с/хз. Показать, что,пля их нахождения дгхтаточно 0(дг!обэ/У) операций. З 5. Наилучшее равномерное приближение Если норыа в линейном норззироеаином пространстве определяет<я не через скалярное произведение, то наипкдеггие элемента наилучшего приближения существенно усложняю<я.
Рассмотрим типичную задачу, встречающуюся, в частности, прп составлении стзццартных програым вычнгления функций. Пусть Л вЂ” -пространство глраничонвых вещественных ~рунюпзй, определенных на отрезке (о, Ь) вещественной оси, с нормой ((Л(= '1 )/( П. 1" б Ищется наилучшее приближение вида (/„(х) = ) а,х'. Согласно теореме из 21 существует элеыент авилу нцего приближения, т.е.
ьпюгочлеи 1'„1~(х) такой, что Е„(/) = ))/ — Ь/'„)) < ))/ — (;~.)) при любом многочлене ()п(х) степени и. Такой мвогочлеи („~~(х) называют ммогочленом неплучгпеео раеноме/итого гзриблпэхенпл. Далее будут установлены необходиыые и достаточные условия того, чгобы многочлен 179 О 5. Ншглучшее равномерное прибчижение являлся многочленоы наилучшего равномерного приближения для непре- рывной функции.
Теорема Валле-Пуссена. ~рсгаь сртестерюог и + 2 то ~ки хо < . - < х„чг стрегна [а, 6] гпакие, иао в1бп[1(х,) — Сд (хг)] (-1)' = сопвь, т. е. при перегпдг от отчая хг к точке хиы величина 1"(х) — Оя(х) меняет знак. Тогда Е (Х) >1 = и ~Х(х) — Юя(х)~. =о., ш Докагательгтео. В случае р = О утверждение теоремы очевидно. Пус"га д > О. Предположим противное, т.е. гго для многочлсиа иаилу'пшто приближении С) (х) ]]Оо ((] Е( )< Иыеем ий (."г (' ) — Сг,',(г:)) = г(р ((Ю.(х) — г"(х)) — М,',( ) — У( ))).
В ючквк г„первое слагаеысо прежклодит по модулю егоров, поэтому г1бгг(Ю (х ) Ю. (х )) = г(цп(с) (х,) — Лгл)). следовательно, миогочлов Оя(х) — Ц~(х) степени и меняет знак гг-~-1 рвз. Получили противоречие. Теорема г1ебышева. '1тоби миогоюжи О„(х) бьш миоггчлеиом иаилр ь щего ргвигм ейного приблилссиия иепргрггеггой Огрикции 1(г), иеобходиио и дгктшао шо срщеспгеованил иа [а, б] по крайней мере и+2 точек хо « ° .
хя~-3 таких что Х(гз) — Ю.(Х,) = (-1)* У вЂ” Юя][, где г = О,..., гг-~-1, и = 1 (ели о = -1) одновременно длл всех й Точки хо,..., х„ьм удовлетворяияцие у(шовияьг теоремы, принязп называть то асами чебишееского альтериаиса. Докагатгльспгео.
Датааточиость. Обозначим через 1. величину Яь((. Применяя (1), имеем А = р < Ея(1), яо Е„(1) < ]]1' — 1) [] = 1 вследствие определения величины Ея((). Следовательно, Е (1") = Ь и данный многочлен является многочленом наилучшего равномерного приближения. Необходимость. Пусть данный многочлеп Сг„(х) является многочленом наилучшего равномерного приближения. Обозначим через рг нижнюю гРань точек х и [а, Р], в кстоРык ]1(х) — Яь(х)[ = Ц из опРеДеления Ь следует существование такой точки.
Вследствие непрерывности гг(х) Оя(х) имеем [у(рг) — Ю (рг)] = О. дая определенности далее рассматРиваем слУчай, когда Х(нг) — б) (Рг) = +1. Обозначим чеРез Рг нижнюю Глава 4. 11риближеияе Функций и смежнме вопросы 1ОО грань всех точек х е (рн Ь), в которых 1(х) — Г»„(х) = — Гь последовательно черш уьы обозначил~ нижнюю грань точек «Е (рг, Ь), в которых ((х) — 12„(х) = ( — 1)"1,... Вследствие непрерывности 1(х) — Ци(х) при всех Ь имеем 1(рьм) — 4» (Рьтг) =- ( — 1)ьб. ПРодолжаем этот пРоцосг. до значения р,„= Ь илн у такого, *по [1(х) — 1]„(х)] < В при у,„< х < Ь Р«ли т > и,-~-2, то утверждение теоремы выполнено. Пре1п»оложиьц по оказалось т < п + 2. Вследствие непрерывности 1"(х) — С„(х), при любом Ь (1 < /с < н»] можно указать точку «ь ~ «акую, ЧтО [1(Х) — Г»и(Х)) < Ь Пря»Ь- ~ < Х < ум ПсппжнМ»а = а.
«,„= Ь. СО«Лаппо проведепаыьг выше построениим, на отрезках [», м»,], г = 1,..., т, имглггсн точки, в чзстноств точки рь где 1(х) — Г]а(х) = (.-1)' ~Ь, и нег точек, где 1(х) — Ци(х) = ( — Ц*Ь. Положим и рассмотрим поведение разности 1"(х) — 1],",(х) = 1"(х) — 4]„(х) — г]е(х) на отрезках [» ы» ]. Для примера обратимся к отрезку [»е, «,]. На [»е, »~) имеем о(х) > О, поэтому У(') --()".(х] < Ь вЂ” В («) < б. Кроме того, на этом отрезке выпшпшется неравенство 1(х) — ()„(х) > — б; поэтому при достаточно малы« Н, например при пбв Ях] — 0„(х) + 1.[ »1 < А = — ' ]а ~] пыл ]о(х)[ на [»е, »~) имеем ((х) — 12„(х) > — П В то же времи ]Х(«) — 1]"( )] = []'( ) — 1) ( ~)] < В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
