Бабенко - Основы численного анализа (947491), страница 68
Текст из файла (страница 68)
и1ы рассматриваем заведомо не наилу ппий, но ненасыщаемый метод. При заданной точности в длина таблицы решения будет отличаться от оптимальной на несущественный множитель (1од(1еее)), где константа о будет указана ниже. Используя для приближенного представления решения не частную сумму ряда Фурье, а так называемую сумму Валле — Пуссена, получим оптимальный по порядку метод. Свяжем между собой величины и и с.
Пусть Я„(он и) = — ~ ~ехр(ггех). )ой<а где с = (сы ...., с„)' Е 1", и если и Е 1е, но и ф 11 С 1ю то положим ((оп с) = О. Продолжим периодически эту функцию на все пространство К~. Ясно, что 1(х; С) Е,ут'" (41), и поскольку среднее этой функции по интервалу 1е равно нулю, го ((и; С) Е,УГР (ЛХ). В дальнейшем доказательство протекает как и доказательство неравенства (4.4.12) и поэтому 'Э' 2. Аналггг некоторых виписллмпслъиих глгоритлгов 325 КаК И В Э 1 ГЛ.
3, ПОЛОЖИМ и = (ц, ..., и), 0п(Х) = П 0п(ХС) И ЗаМЕтИМ, 1=1 что 1 Р о'„(х:, и) = — ~ и(ъ)0„(х — О)сН„ 1о откуда, согласно предложению 6 3 1 гл. 3, я.(; 1)~ «!и, ;Л'„, где ˄— (2/я) 1пп + 0(1), В действительности константа Лебега равна Л„= — ~ '0п(х)~11х = — !пи+0(1), 2 /', 4 я 7Г О и поэтому в предыдущем неравенстве константу Лп можно заменить на константу Лп. Оценим уклонение частной суммы оп(х; и) от и(х). Рассмотрим Яп(х; и) как оператор на 0(Т', и обозначим его через оп Ядро оператора 1 — оп содержит все тригонометрические полиномы. принадлежащие подпространсгву 'Х2„1. (Подпространство Тз„о1 введено нами в и.
6 3 1 гл. 3.) По лемме о ядре (предложение 2 3 3 гл. 3) /И(Х) — О'„(Х; И)! < (1-иЛ1„) 1ПЕ ,'И вЂ” р Ретг ъг откуда по теореме 11 э' 1 гл. 3 ~п(х) — 5„(х: и)( < А„(1 — ' Л1„)Мп ~" ~~г, где константа А„, при фиксированном 1 зависит только от г. Пусть е > 0 точность, с которой мы определяем приближенное решение. Выберем минимальное и из условия А,(1,, Л1 )31п ('ъз~ <.г2 (13) и произведем округление коэффициентов Фурье так, чтобы выполнялись условия а — и„< д, м —.- (гм ..., 1г1), и ~ < н, 1' —..
1, 2, ..., й тогда ~й(Х) — И(Х)~ < И(Х) — О'„(Х:, И)- ~ ~г ЕХР(1МХ) < — + ~ )и,)<п (оййп ира Оценим сумму 2, ~м, 2. Легко видеть, что (и,)еп их.е 'гг' г ~ 'ио<г')...~, ' ' 'гио, 2<иг<п 1«, хг п )иг~ и ийо 1 —. 1, 2, ..., й 326 Глава 5. Общис свойства оычислитслъиых алгоритмоо Сделав замену переменных х~ = пСо Ц = 1, 2, ..., !), при ! ) 2 получим .! х',+" +'с )«2<а т,,<а «г'О где С! константа, зависящая только от !.
Если ! = 2, то очевидно, .что иссзелуеыая сумма не превосходит Сз 1и птС. Поэтому, если определить д из условия 5(Срс' ~ + С) = в,!2 (14) (при ! =- 2 нужно С~и~ а заменить на Сз!и а, получим ~й(х) — и(х)( < е. Подсчитаем длину таблицы на входе в алгоритм. Предложение 3. Если ! й,М" (Я1), то 1 ~а„= , '/ 1(х)ехр( — !их)с!х < , (2, )г,/ гв ! < — 'ЛХя' ~'" ( из ' +... з )и~ ~') " . (15) Доклзатильстно. Пусть х = (хм х); рассмотрим ! как функцию переменной хн Заметим, что если 1 с,(х) — — / 1'(хь х) екр( — !и,хг)с(хн 2п,/ то, считая (г) —.— в, имеем (1иг)вс„(т) = — В,"Яхм х) ехр( — !«1х1)с(х1 = 2т ! а- вдю й 1 — ВгД(хп, х) екр( — !«1х1)с!хь 2г — а-.сд«1 Отсюда после замены х| — х~ -' г,с,'и, получим (ги1)'с«с(х) =- — — / О~г~(х.
-'-, х) ехр( — 1и,хг)йхь З 2. Анализ новаторах оичислддгвслъддих ыдгоритлдос 327 Складывая эту формулу с предыдущей, получим 2(дид)'с,„(х) = — ~Р Х(хд, х) — Р', Х(хд +, х)) ехр1 — дидхд)с)хд. Умножив это соотношение на ехр( — дйх), где й = (из,..., ид), и инте- грируя его по х,, ..., хг, получим 2~ид '~а,~ < ЛХ( х,) Так как переменные хд,..., хд равноправны, то отсюда следует, что прп изтО 2(иу )" )а, ! < ЛХя™ . Складывая эти неравенства, получим неравенство (15). 12 Чтобы подсчитать длину таблицы ТХ функции Х, рассмотрим более загрубленное неравенство, чем неравенство (аког), оценивая отдельно Ке ао и!ша: Г ( Ке а,( < — ЛХдг' '-'1(',и, ! — ' ...
+ )к г!) 1с , 1ш а ( < — ЛХдг' "1 1, ид ~, ... + ~ дгд ~) Тогда для того. чтобы записать ао с учетом знаков ддеао, 1ша„доста- точно иметь два слова длиной ЛХ с-1'21' !Оя „+2, дуйб( сд т... - ~ид1) прддчелд дХ2 появился в результате того, что мы запоминаем Ве а„и 1ш а„ с точностью б,гдс2. Поэтому общая длина таблицы не будет превосходить величины И ."-1с1Г ЛХ ~ (1оц „+2) = ~ 1од,+О~ад). дг2б(~дгд ( +... + )ид,') бДдгд ) +... т (ид ) с пв оае В силу монотонности функции 1од(ЛХ/б( ид +... + 1ид1)) получим ЛХ )ойап иг'-0 2'г'-- 1~г с,...гс хо(')-а псб(~ ., ~д)с 0<1 <п 328 Глава б.
Общие саойстса вычислительных алеариеаиаа откуда )(1'Х) < 2 и, ! ! )о8 еХ>!>...с)гб —,0(п ) — С. с,! Х 3Х и б(йд —... + 6>)' 0<с,<и Ъ'нить>вая соотношения (13)., (14), получим, что М»"б = (Ли + -! 1)'п ', и поэтому )(ТХ) < 2~(п' !ой п 0(п !о8 !о8 и). Из условия (13) следует, что и = (йХ/г)ецс+Я'()о8(йХ>ее)) и, стало >Л е-'> быть, (ЪХ)ед з)( М "Д -М'-> ()ой)ой(МЯ)~ 1+О „и е) (16) т.е. мы видим, что предлагаемый алгоритм несколько хуже оптимального и его точность уступает точности оптимального алгоритма, которая дается формулой (11). в ()о8 !Х)' !с+з)Д раз.
Отметим, что множитель ()о8 Ж)' появился пз-за того,. что мы воспользовались приближением с помошьк> частных сумм ряда Фурье, а не более тонким методом. Но множитель (!о8 бу) !с а>Д появился у нас в процессе подсчета длины таблицы и не ясно, как от него избавиться. 3 а д а ч а 1. Существует ли оптимальный алгоритм решения краевой задачи (5) или наличие аи>ожителя (!око')Р ез>Л неизбежно? 5. Временная сложность рассматриваемого алгоритма. Оценим временную сложность рассматриваемого алгоритма, т. е, число операций, необходимых для получения решения.
Если па выходе из алгоритма допускается таблица коэффициентов Фурье, то очевидно, что для временной сложности 'Х(в) будет иметь место оценка 'У(е) = е>~ или 7( ) >< ( — ) (!о8 — ) (18) (необходимое количество операций сложения, умножения и деления). Допустим, что на выходе из алгоритма нам требуется иметь оптимальнук> таблппу ннтерполяционного типа. Из предложения 2 следует, что длина такой таблицы точности к должна бь>ть величиной порядка (ЛХеее)~Д"ез!, а, как следует из результатов 54 гл.
4, число узлов Х>!е - -(ЛХеек)'Х!с+"!. Мы знаем, что таблица представляет собой набор младших разрядов значений й в узлах равномерной сетки с шагом ,— >д 6 = 2х>ее по каждой переменной. Чтобы точность таблицы была равна с, необходимо й(ш) знать с точностью б = с/Сс, где С„-- некоторая Если принять правую часть перавепства (16) за длину >Х таблицы на, входе в алгоритм решения краевой задачи (5), то точность алгоритма будет оцениваться величиной с 4 Ъ|М-4 ез)Д()оа,>Х)1 -Р з)Д (17) 'З' 2. Анализ некоторых выниелигвелыгых илгоритлгов 329 константа, зависящая только от г. У1ы и будем считать, что в предыдурдих формулах в заменено на вС„~, что повлечет за собой увеличение гд окз1 длины исходной таблицы в С,.
' раз. Взяв шаг в виде Ь = хгг2" с подходящим и и замечая, что нам нугкно вычислить й(х) в узлах тг = (~г6,..., Хд6) сетки, мы можем проделать вычисления, используя алгоритм быстрого преобразования Фурье. Единственное, что для этого нужно сделать, выбрать минимально возможное число р так, чтобы было выполнено неравенство 2' ) а.
Эти вычисления потребуют не более 2"+' н1 операций (см. задачу 9 э 4 гл. 1). Отметим, что иа вычисление коэффициентов тригонометрического мпогочлена нужно израсходовать = и' операций. Учитывая, что 2о = п, получим для временной сложности оценку (19) РД -з1 причем множитель (1ой(ЛХггв)) появился из-за того, что мы пользуемся хотя и ненасыщаемым, но не наилучшим методом приближения периодической функции тригонометрическим полиномом. Запомним, что величина (ЛХгге)'Д'+ 11о~(ЛХгге) служит мерой временной сложности оптимального алгоритма решения задачи (5). Для сравнения дадим оценку точности и временной сложности алгоритма, основанного па использовании таблиц интерполяционпого типа.
Эти рассуждения подобны рассуждениям 3 2. Допустим, что на вход в алгоритм подается таблица интерполяционного типа длиной гУ с Жо узлами. Возьмем функцию 1(х: с), построенную при доказательстве предложения 2. Интервалы 1м 1о выберем столь малого размера и лехшщими в 1в, но максимально удаленными друг от друга, чтобы для любых х й Хы у б 1г выполнялось неравенство ((2; х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
