Бабенко - Основы численного анализа (947491), страница 69
Текст из файла (страница 69)
— х) > 2~Д2; х„— у)~, (20) где х„центр интервала 1П в силу предложения 1 всегда можно добиться. чтобы последнее неравенство выполнялось. В формуле (10) положим и — 1 .—. 2ЛХв, и пусть внутренность частичного интервала, в котором лежит эпрр е1... не содержит узлов таблипы, когда Х = 1, 2,..., М. Функцию й, определим как при доказательстве предложения 2 э 7 гл.
3, но только с тем отличием, что теперь возьмем ьо(х) = П(3 '). 1=1 Положим и Š—',г~'м (ж), ж Е 1'м Хб(о:) н О, .х Е 1в 1 (1г О 1з). б... ззо Глава 5. Обигие свойстаа вичислительных аагорагпмов Функции Хг(х) и Хв(х) = 0 входят в коипакт ге" и имеют одну и ту же таблицу интерполяционного тигга. Значит, алгоритм численного решения задачи (5) даст один и тот же выход. Пусть и,(х) .- решение задачи (5) с правой частью Хг(х). Тогда в силу неравенства (20) 1 ~ г М = , , / Хг(4)С(2; х.
— 4)д4~ > г >, / Хг(ф)~(2: х„-- 5)д5 —, / ~Хг(~)~(2; х, — 5) дб > 1 1 (2п)г,/ ' ' (2.т)' / гг > шш с(2; х' -- с) / Хг(~)д~ .- шах~((2: х' -- с) ~ х 4сгг г 4егв г', 1 Х 1,,„1 Х х, /, :Хг (~) !дц > — гшп С(2; х'" — ц), / Хг ®д~, откуда 5 ~иг(х.)! > пг1п~(2: х. — С) гЛХ / ф,®д~. фец ' й(2п)' гг Принимая во внимание вид функции ф„(х), имеем /1г.,(х)дх=(-") / р(х)дх=СоЯ гг !иг(х„)~ > СгЛХМо ' > СгЛХХ Поэтому, если е — точность алгоритма, то те.и же рассуждением, что и в п. 2, получим оценку е > — СгЛХЛг "г~. 1 2 (21) Сформулируем полученные результаты в виде следующей теоремы. Теорема 2. Пусть Х и ду'" (ЛХ). Если на вход в алгоритм решения задачи (5) подиепгся таблица коэффициентов Фурье правой части длиньг гу, то существуют, илгоритмьг, позволяющие получить решение, с точностью е ( СЛХЖ <а+г1Хг(!озйр)!" а!'г.
Временная слоэгсность такого алгоритма, если на его выход подается оптимальния пгаблица, удовлетворяегп неравенству 'х(е) 4 ( — ) (1о — ). Поскольку 6 = Лрг г', ЛХ > Жо, то 'иг(х,)~ > Сгд, а учитывая, что теперь ггго -- (ЛХг'5) г ~1Хг 5 получигг неравенство 'Э' 2. Лналиг некоторых вычислшпвльпых алгоритмов ЗЗ1 Если на вход в алгоритм подается таблица длиной ЛХ интаерполяционного типа, то для ега точности г справедлива оценка . > СЛХМ а врсмвнпая сложность удовлетворяет неравенству 'л(г) > С(ЛХХг)~Х'. 3 а д а ч в 2. Покажите, как нужно видоизменить формулу (12), чтобы получились первые две оценки теоремы 2. Проделанные вычисления наводят на мысль о том, что справедлив следующий эвристический принцип: алгоритмы для решен я краевых задач, оптимальные аа числу операций содержатся в классе аптичальньгх алгоритмов.
Этим принципом можно пользоваться при исследовании конкретных алгоритмов, оправдывая его конкретными вычислениями. 6. Использование оптимальных таблиц. Рассмотрим чисто практический вопрос о том, как следует решать задачу (5), если правая часть задана с помощью оптимальной таблицы. Иногда применяют следующий способ: заменяют задачу разностной, а затем применяют алгоритм быстрого преобразования Фурье, Этот способ не выдерживает критики, поскольку переход к разностной задаче делает алгоритм пасыщаемым. При 1 = 2 правильный способ состоит в следующем: пользуясь соответствукгщей квадратурной формулой, нужно вычислить коэффициенты Фурье функции Х(х) с точностью б, а затем воспользоваться формулой (12).
При этом обнаруживается преимущество такого подхода, когда правая часть Х(х) задана сравнительно простой формулой и вычисление ее коэффициентов Фурье возможно ор|анизовать с малыми затратами. В общем случае нужно применить квадратурную формулу 1 а = „ / Х(х) ехр( — 1их)дх = (2т)а,/ Уи и — 1 2к 2г 2кг', = Р" ~ ~Х( — Лм — йг) ехР( — — (Р1Л, + майа)) +0(МР с), Р ' Р Р гоги=а (22) Здесь одной и той же буквой С' мы обозначаем, вообще говоря, различные константы., не зависящие ни от Ж, пи от в, Докязлткльстно.
Первое и второе неравенства мы установили в менее сильной форме (17), (19) с логарифмическими множителями. Поэтому формально они не доказаны. Однако мы отмечалн, что этот дефект легко исправить, перейдя от частных сумм ряда Фурье к суммам типа Валле — Пуссена, Последнее неравенство теоремы вытекает из следующего замечания. Длина о' таблицы интгрполяционного типа и точность алгоритма связаны неравенством (21).
Ясно, что число операций при отыскании решения не может быть меньше Сс1ч', ибо каждый бит информации на входе должен использоваться в алгоритме. Поскольку ЛХ >:„(1/2) С2ЛХ/е~, то отсюда следует последнее неравенство теоремы. П 332 Гласа 5. Общие саабстаи аычис,литсльиых алеаригамаа которую мы приводим без доказательства. В одномерном счучае (1 = 1) зта формула исследована в п. 4 з 2 гл. б. Двумерный интеграл., рассматриваемый как повторный, сводится к одномерным. Данная формула с указанным остаточным членом справедлива при условии, что ~пу < Р,е2 (» = 1, 2).
Если с погрешность приближенного решения, то, определив и и д из соотношений (13), (14), мы должны потребовать, чтобы остаточный член в формуле (23) не превосходил д, что в силу (14) при 1 = 2 дает ЛХ 10К(ЛХеев) ) Н" '=(" ' Нам нужны коэффициенты и, такие, что ы ( < и (~ = 1, 2). Из соотно- шения (13) мы получаем, что г Л'Хт Хй и м — 1ой — ) =( ') Е Сравнивая последние два соотношения.
видим. что заведомо будут иметь место условия, при которых справедлива формула (22). Считая, что Р = 2', применим алгоритм быстрого преобразования Фурье для вычисления коэффициентов Фурье, на что потребуется 4Р 1о„Р операций. Сравнивая величины Р и ~г, видим, что число операций, которые нужно истратить, чтобы найти приближенное решение, определяется в основном счетом коэффициентов Фурье. Вычисления по формуле (12) дают малый вклад во временнук~ сложность алгоритма. Поэтому В лучших алгоритмах, использующих разностные схемы, получаем оцен- ку (при г = 2) ЛХ ЛХ ~(е) —.4 — 1оа —. Предлагаемый способ решения задачи (5), если пренебречь несущественными логарифмическими множителями, скорее всего, оптимальный среди алгоритмов этого класса как по точности, так и по числу операций, и, что исключительно важно, этот способ без насыщения.
Поэтому в том случае, когда мы не обладаем достоверной информацией о гладкости правой части, целесообразно пользоваться этим алгоритмом 1г1. 3 а д а ч а 3. Постройте алгоритм без насышения решения задачи (б), в котором на входе задается оптимальная таблица интерполяцнонного типа и который пригоден дчя любого й Этот алгоритм должен иметь временную сложность 'г(е) ~ ( — ) (1ой — ) где о — некоторая константа. (Нам представляется, что эта задача не совсем тривнюеьпа. Автору такого рода алгоритмы ве известны.) ° С 3.
Рсшсиис иското1вих искоррсктимх задач Развиваемый в данной главе подход к исследованию вопросов об оптимальности алгоритмов читателю полезно сравнить с подходами, предлагпощимися в ряде работ С.Л. Соболева и Н, С. Бахвалова. В работе [100) вопросы эффективности исследуются применительно к задаче численного интегрирования; в обзоре (24) рассматрива|отся вопросы эффективности применительно к широкому кругу задач численного анализа. Цикл работ по вопросам эффективности численных алгоритмов выполнен Н.С.Бахваловым. В работе (25] читатель может найти обзор результатов этого автора с соответствующими библиографическими указаниями, 3 3.
Решение некоторых некорректных задач 1. Задача Коши для уравнения Лапласа. Все краевые задачи делят на корректные и некорректные. В подтверждение такого деления выдвигаются следующие три требования, которым должно удовлетворять респепие краевой задачи; 1) оно должно существовать: 2) должно быть однозначно определенным; 3) должно непрерывно зависеть от данных задачи. Последнее требование на первый взгляд представляется естественным, но оно сформулировано наименее четко, поскольку не указана топология, в которой должна эта непрерывность соблюдаться.
Обычно принято рассматривать целый ряд типичных примеров, на которых демонстрируется выполниъюсть этих требований и производится классификация краевых задач. Рассмотрим уравнение Лапласа в области ЕУ с гладкой границей д11: Ьи .—. О, х .=. (х., у) Е Т1, и задачу Дирихле для него: Хорошо известно, что эта задача разрешима при л|обых непрерывных граничных условиях и что решение единственно, и в топологии пространств С(то, для решения и С~ВТУ) для граничных условий имеет место непрерывная зависимость от граничных условий, поскольку имеет место принцип максимума: шах,и/ < шах,ф П ' дп Читатель, вероятно, знает, что аналогичная картина имеет место и в общем случае краевых задач для эллиптических уравнений и систем с тем единственным исключением, что иногда должно выполняться конечное число условий разрешимости задачи, когда однородная задача имеет нетривиальные решения.
Так, например, будет, когда рассматриваем задачу Неймана для уравнения Лапласа. Вместо неравенства (1) имеет место аналогичное неравенство, но, вообще говоря, в иных топологиях для решения и граничных условий. Такого рода неравенства получаются на основании теоремы Банахв о замкнутом графике (см, теорему 12 334 Глава 5. Общие свойство вычислитсльиых алгоритмоо э 1 гл. 2). Таким образом, обширные классы краевых задач для эллиптических уравнений и систем в силу сделанного деления слелует назвать корректнигми краевыми оадачами.
Пгимнр. В противовес задаче Дирихле для уравнения Лапласа выдвигается задача Коши. А именно, пусть рассматривается решение уравнения "!апласа в прямоугольнике В = (х, у: 0 < х < 2т, 0 < у < г1), периодическое по х и такое,что и(х, 0) †-- )'(х), ии(х, О) =- д(т), 0 <~ х < 2к, (2) где 1г д заданные 2к-пеРиодические фУнкции (мы РассматРиваем 2к-периодический случай ради простоты). Ясно, что решение этой задачи существует не всегда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
