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