Бабенко - Основы численного анализа (947491), страница 123
Текст из файла (страница 123)
корректность обратного хода. Если матрица Р не постоянна, но при каждом т собственные значения Р(л) удовлетворяют неравенствам (38) и полупросты, то следует ожидать, что паши выводы останутся в силе. Вид (39) нормнрующих матрип вовсе не единственный, Можно на каждом шаго (или через несколько шагов) применять к матрице А процесс Сонина — Шмидта ортогонализации строк.
В наших предположениях этот процесс не приведет к большой потере точности,которая наблюдается при его реализации. Мы довольно подробно рассмотрели разностный метод численного решения, краевой задачи (хотя мы и остановились лишь на одном способе замены дифференциальной задачи разностной, читатель теперь может сам без труда построить множество друтих дискретизаций). В процессе исследования разностного метода были обнаружены его большие недостатки, и прежде всего его насыщаемость и отличие от нуля дефектного числа.
Последнее обстоятельство говорит за то,что вопрос об оптимальности разностных методов требует более углубленного исследования. В свете сказанного возникает вопрос: а стоит ли пользоваться в практической работе при организации численного метода решения краевой задачи изложенными вылив методами дискретизапииу На этот во- 600 Глава О. Численное решение крвсомх задач прас ответ можно дать вполне определенный. В практической работе почти всегда решающим обстоятельством являются простота и технологичность численного метода. Поэтому часто приходится жертвовать, хотя и экономичными, по более сложными методами и предпочитать простые в обращении и достаточно падежные методы.
Следовательно, в арсенале у вычислителя должны быть самые различные методы, а пе только оптимальные по некоторому набору параметров. Т. Дискретизация с использованием интегральных представлений. Приведем еще один вариант дискретизации задачи (1.1)., (1.2), ограничившись случаем простейших граничных условий у(0) = О, у(1) .— —.
О. В этом случае мы получаем дискретную задачу с нулевым дефектным числом. Введем при о > 0 ядро 1'(6 — ~х~),1(о+1),;х~ < 6, Легко проверяется, что при д' —. 1, 2, ..., и — 1 6 Ь у» =-6 / К»(», 6)уи(х +»)й. В этой формуле мы воспользовались обозначениями и. 1. Исключая уи с помощью уравнения (1.1), получим 6 'Ьву, » .—.- — Г + 6 ~ / Кз(», 6)д(х, +»)у(х, — , '») й, где ЕЧ = 6 ~ ( К»(», 6) Е(х, +») д».
Пусть и(х) = д(х)у(х): по формуле 1'о»1лора и(хэ и») = и(:гд) -'»и'(хэ) — /(» — С)ииК вЂ” хдМ о Учитывая четность ядра К1(», 6) и очевидное равенство К,(», 6) й —.... 6"-, получим К1(», 6)и(х, +») й = 6'и(х,)+ ~ Е»1(», 6)й /(» — Ой(хд+~)дб. 602 Глава О. Числезпим ре1иеииз крисамх задач На компакте У соотношение (44) уже может быть неточным, что повлечет за собой изменение дефектного числа алгоритма.
Эффективность алгоритма решения краевой задачи, основанного на соотношениях (42), (43). будет всецело определяться алгоритмом вычисления интегралов Х р (Напомним, что эффективность алгоритма в конечном счете определяется его временной сложностью, т.е. числом операций 'Х(в), потребных дпя того, чтобы получить резпение с погрешностью, не превьппающей в), Если в качестве таблицы правой части уравнения (1 1) берется таблица интерполяционного типа, то для вычисления интегралов Г будут использоваться квадратурные формулы, и мы получим заведомо неоптимальный алгоритм в том смысле, как он был определен в гл. дг, В той же главе в З 1 даны оценки временной сложности алгоритлюв решения краевой задачи для уравнения Пуассона.
Естественно, что и в рассматриваемой краевой задаче для обыкновенного дифференциального уравнения мы получнм ту же картину в вопросе о влиянии вида таблицы, с помощью которой задается правая часть, на временную сложность алгоритма. Чтобы подкрепить высказанные соображения конкретными вычислениями, рассмотрим случай, когда яа (О, Ц Х е 1лр(а, ЛХ) (см. гл.2 э 2). Ограниченно компактное множество функций. принадлежащих классу 11р(о, ЛХ), обозначим через П (ЛХ). Пусть вначале 0 < о < 1. Заметим, что в силу нашего предположения уи ~ 1лр(о, ЛХ~), гле ЛХ~ некоторая константа, зависящая от ЛХ, Д,з, )у),, )у') В самом деле, из уравнения (1.1) следует, что уи(х+ д) — уи(х) .— —.
--Х(х.:; б) + Х(х) -. и(х + б) — и(х). Но и(т+ д) — и(х) = (у(х+ д) — у(х))у(х 4 б) + 0(х)(у(х+ д) — у(х))., и поэтому по теореме о конечном приращении и(х+ б) — и(х) .— -- бд'(х й 0б)у(х Е д) 1 п(х)бу'(х 4 0,б), где ;'0 < 1, 0з < 1. Отсюда в силу (1.7) и(х+б) — и(х)) < )д, [ у',,)у,„+)гХ) „'у", ' < А;д) ~)у, + у'), ))Х', . Поэтому )уи(х+ д) — уи(х)) < ЛХ)б.:~ -~-А,б) ()0,,:~ -~-)д')~) ) Х)~ < <)д ~ЛХ~. Обозначим через .Х интеграл в формуле (40)„подставляя ии = диу+ — ' 20'у'+ ууи и заменяя уи на уу — Х, получим Х = ~ КзЫ 6)((у (х +б) 4ч (х +О)у(х +О+ — ь -' 2а'(хз + б)у'(хз + б) — у(хз + ЮХ'(хз †, б)) К.
603 г 3, 0 решении краевых заОач матоОом прозаики Отсюда Ьа 7 — — — ((Оо( ) -'4'(хз))уз — 41Л+М(х,)у'(х,)~+О(Ь' ). По формуле (2.4) у'(хз) —... Уг=' — ':„— "'= — ' + 0(6,'уо~, ), и поэтому 4 Подставляя полученное выражение в (40), придем к соотношению 1 — г г, ~ ~ .
/ ~ и '-~ Уз- з + Чу(Уз-1 Уз — з) Уз + (й + Ч ) Уз— Ьг .— -- гу -' — д,~, + В,, г = 1, 2, ..., и -. 1, (45) 12 гдс Ч, — — Я (хз), Уо —. Уо(хз)., а Лз = 0(пг' ), причем константа в О зависит от ЛХ, 'ЬЬ, 'и от нормы производных гЬ Отбрасывая в (45) остаточный член аппроксимации Лм получим искомую приближенную систему — Ь гз г+ — 4(з з — г)-~4 — — (У +О)~г — г и г 12 1 з г ~ з 12 Ьг = Р— ' — д,уз+В,, у — -- 1, 2, ..., и — 1. (46) Для системы (46), (43) выполнены условия предложения 3 гб гл.3, и, следовательно, (47) шах~ — у(ху)~ < Сй а = Сп з Дадим оценку погрешности приблвжснпого решения.
По соточной функции з': у — ~ го, х =- (-о, ..., ги) построим функпию и 6 С(0, Ц, принимая в качестве оператора восстановления квадратичный лагранжев сплайн 7,(хн х). Тогда из неравенства (47) вытекает, что ,'у — Е(: х)', < < Сбг+а, и, значит, погрешность приближенного решения х будет удовлетворять неравенству ) < С вЂ” г — а Однако предыдущее неравенство прямо не следует из теоремы 1 г 4 гл. 3 либо предложения 1 г 6 гл.3.
Х!ы предлагаем читателю самостоятельно решить задачу, из которой вытекает нужное неравенство. 3 а д а ч а 7. Пусть а й Нг (ЬХ: а, Ь). гле О < о < 1. На ,'и, Ь,' оводом узлы зб .= а+ 15 (Ь =- (Ь вЂ” а)и ', 4 = 1, 2, ..., и,) и по этим узлам построим лагранжсв сплайн 5, квадратичный на каждом частичном интервале и принимающий в узле х, значение у: Цхм и) = у (г = О, 1, ..., и). Докажите, что 'р -- Л(; и) < С Л1Ьг~ — Лошак~го(х ) -- н.~, где Лг — константа Лебега интерполяции, а С зависит только от ои 604 Глаза з. Численное ре1аеиие краевых задач УкА3Ание.
Прнменнте предложение 1 З б гл. 3 к функции ра (х), где эза (х) — среднее функции эх Среднее постройте так, чтобы выполнялись неравенсева (,о — |ра~ ( СЛ16 ~" > (Эеа ! ( С1ЛХ6 Выше мы показали, что если Х =- Н (М), то 1' С Н з а(Л4з), и, следовательно, Ьа, з(1') < Сзп '. Поэтому дефектное число предлагаемой аппроксимации не сйзеаышает О. Нетрудно убедиться, что дефектное число равно О. Временная сложность алгоритма численного решения краевой задачи, основанного на уравнениях (46), определяется сложностью вычисления интегралов Ео Если правая часть )' задана таблицей., то для вычисления интегралов Ез можно использовать формулу прямоугольников в следующем виде.
На отрезке х — 6, х, + Ь) введем узлы х ь =. х + +йб (б = 6Л' ', 6 = — Ж, — Х 1, ..., Л') и будем задавать функцию )' в узлах хзь. 1(вадратурная формула будет иметь вид (48) причем интегралы от функции Кз могут быть вычислены точно. Погрешность этой квадратурной формулы, как легко видеть, оценивается величиной Мб 6 ~ ~ КД, 6) М =- ЛХб". Отсюда получается условие на шаг б: ба м 6аэ, т.
е, б =- 6зтв~а. Теперь несложно получить опенку временной сложности рассматриваемого алгоритма. ПУсть компакт Х = (1 Е Н„: 1(0) < Л'). Обозначим чеРез 21з алгоритм приближенного решения задачи (1.1), (1г2). На вход в алгоритм будет подаваться таблица функции (', правые части уравнений (46) будем вычислять по формуле (48), решать систему (46) будем методом прогонки. Сложностью вычисления функции Ч и ее производных, фигурирующих в уравнении, мы пренебрежем, но учтем сложность составления таблицы функции з".
Ясно, зто основное время будет затрачено на вычисление правых частей системы (46), т.е. на вычисление интегралов. Через ие обозначим сложность (число операций) вычисления значения функции 1 в узле. Если таблицей функции 1 служит набор ее значений в узлах, то будем считать, что ш = О, пренебрегая тем самым временем выборки из таблицы. 'Таким образом, для вычнг юния интегралов Е потребуется =. (и — 1)26(ш+1),'б-О(п(ш-1)) операций или = 6 ' э~ах(ш+ + 1) операций.
Как мы видели, на решение системы (46) нужно затратить = и = 6 ~ операций, и, таким образом, для временной сложности 33. О рсшенпи краеамк за0ач мста0аж прагаятп 606 алгоритма йя получаем оценку а(йя, ) ( Сп6 Я ~га(ия+ 1), причем погрешность с и величина шага 6 связаны соотношением с =- 6~ а. Итак, 'У(йг, 'с) ( Сге ~~" (и. —. 1). (49) 3 а д а ч и. 8. Покажите, что 'з(йя, 'г) > Сзе 'Я (ия+ 1). Если в уравнениях (42) Г~ заменить на Дя, то получим систему (6), но при этом величина погрешности будет не больше М6" .(-О(6~). Вычысленяяя по формулам (6) потребуют (и — 1)ш + Сп операций; пяюкольку теперь погрешность е ж 6, го временная сложность этого нового алгоритма йа, отличающегося от алгоритма й я только тем, что теперь будут использованы уравнения (6) я будет удовлетворять неравенству з(ЯЙа; е) ( Сяс (ш 6 1), и по порядку величины эта оценка такая же, как и оценка (49).
Таким образом, грубо говоря, оба юягоритаяа равноценны, но, используя алгоритм, основанный на уравнениях (6), получаем нзбыточвуяо таблицу приближенного решения и сталкиваемся со всеми теми недостатками, о которых говорилось в 37 гл.3. 9. Покажите, что если 1 6 11' (я11; О, 1), то разностная задача (46), (43) аппраксимирует на решении дифференциальную задачу (1.1), (1г2) с погрешностью О(6Я). Если в задаче (1.1),(1.2) правая часть такая, что интегралы Гя вычисляются легко, а так будет, например, когда уравнение однородно,т.с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
