Бабенко - Основы численного анализа (947491), страница 124
Текст из файла (страница 124)
г' и О, то временная сложность определяется числом операций, потребных для решения систеьпя разностных уравнений, н в эзом сзучае юпоритмы Йа н Йя просто несопоставимы, так как в первом случае временная сложность оценивается как О( Я' ), а во второля случае — как О(с 1 ), Поэтому, сравнивая между собой сложность алгоритзяов решения однородной задачи н неоднородной задачи, мы видим, как резко отличается однородная задача от неоднородной.
Это же различие наблюдаеття я в случае краевых задач для частных производных. Легко понять, что использованный прием дискретизации краевой задачи переносится н на общий случай произвольной системы, а также на случай существенно большей гладкости правой части. Однако мы не будем приводить соответствующих выкладок, а изложим виже метод построения алгоритмов без насыщения, которые одинаково хорошо работаяот как в случае малой гладкости,так н в случае большой гладкости правой части. 10*. Найдите главные члены асимптотики временной с.ложности алгоритмов йа и йя: 'з(йя; с) = Аге 1 + о(сщ") (1 = О, 1), где А, зависит от о и ш.
Замечанию Зная постоянные А, можно будет вынести более точное суждение об эффективности этих алгоритмов. 64ы видели, что довольно легко построить дискретизацию, для которой дефектное число неположительно. Однако в нашем построении существеннуюю роль играло то, что мы имели дело с обыкновенными дифференциальными уравнениями. Как получить подобные результаты для уравнений с частными производными, неясно. 606 Глава О. Численное ресаеиие краееесх задач 8 4. О решении краевых задач методом конечных элементов 1. Проекционные методы. В ~ 1 гл.
1 на примере краевой задачи (1.1.3) мы рассмотрели один из проекционных методов — метод Бубнова-. Галеркина. Для удобства читателя вновь рассмотрим формальную сторону проекционных методов. Пусть С гильбертово пространство и А отображение, А; Рл — С, не обязательно линейное, Рл область определения А, Рл с С. Рассмотрим вопрос о приближенном решении уравнения Ах =- у: здесь у е У с Ял, У некоторый компакт, а х е Х, где компакт Х является полным прообразом компакта У. Будем искать приближенное решение х„нашего уравнения как элемент некоторого и-мерного линейного подпростраяства Х,а с С. Естественно, мы предполагаем, что Рл плотно в С и Е" с Рл.
Пусть !хм ..., х„) .—. базис в Х,а; тогда х, .— -- Л, С х, и если подставить х, в уравнение, то получим, а -1 вообще говоря, Ах, — у ф О. Мы называли невязкой элемент р = Ах. — у е С. Чтобы свести задачу к конечномерной, .накладывают те либо иные условия малости на невязку. Так, в методе Петрова (схс. [87], где дало обоснование метода в одном частном случае) выбирают некоторое подпространство ЛХ" с С и требуют, чтобы проекция невязки р на это подпространство, была равна нулю. Если )ем ..., е ) базис в ЛХа., то последнее требование равносильно выполнению условий (Ах„— у, .) —...
О, Х вЂ” -- 1, 2,, пч где (, ) — скалярное произведение в С. Егши А линейный оператор, то последнюю систему можно записать в виде (Ахо еа)~, = 1у, е ), с = 1, 2, ..., и. е=1 Основным, наиболее неформальным моментом в данной теории является выбор подпространств Х" и ЛХ" и базисов в них, с тем чтобы получить наиболее эффективный алгоритм.
Проблемы, которые здесь возникают, обсуждались в гл. 1, Подчеркнем, что при обосновании проекционных методов важно не столько получить формальные доказательства сходимостн метода, сколько связать выбор подпространств Х." и ЛХ" с емкостными характеристиками компактов Х и У. Если ЛХ" — — Х", то получаем очень популярный в настоящее время метод Бубнова — Гаперкина. Детализируем наши рассуждения, когда А не произвольный оператор, а гамосопряженный неотрицательный оператор. Сначала рассмотрим конкретный случай краевой задачи, немного более общей, чем задача, изучаемая в предыдущих параграфах. Дальнейшие рассуждения опираются на фундаментальный факт о том, что решение данной краевой задачи эквивалентно некоторой экстремальной задаче, и поэтому з 4.
О не~ионин краевых задач методом конечных алел~аюпов 607 — — ~р(х) — ~ +у(х)у =-з'(х), хе ]О, 1, у(0) =. у(1) =-О. (1) Е1етрудно увидеть, что решение уравнения (1) является стационарной точкой функционала !(и) = д~,р(х)[и'(х)]~+у(х)и (х) — 21(х)и(х)]сйх, (2) о рассматриваемого на Н = И",(О, 1). Соболевские пространства опредео лены в 32 гл.2. В данном случае под И''2(0., 1) понимается замыкание пространства Св1]0, 1] функций с компактным носителем на (О, 1). В самом леле, 'Фп 6 Й 7(у -: ') †- 1(у) †' 2 'у(х)у'(х) ''(х) + Ч(х)у(х)н(х)— е — 1(х)е(х)]1 ~ (, ), (3) где (и, н): Н х Н о К - симметричная билинейная форма: (и, и) = ~,'р(х)и (х)е (х) + у(а:)и(х)г(х)]е1х. в (4) Интегрируя по частям в интеграле, стоящем в правой части (3), и ис- пользуя граничное условие н(0) = п(1) = О, в силу (1) получим 1 ]р(х)у'(х)е'(з:) + а(х)у(х)п(х) -.
((х)н(х)] е1х =- о 1 — (е — ") +яр — у] зи= а о Допустим, что форма (, ) положительно определена. Для этого достаточно потребовать, чтобы р(х), у(х) > О, р(х). у(х) > О, Тогда стационарная точка функционала 1 будет точкой абсолютного минимума. В самом деле, на основании (3) имеем 1(и) = 1(у) -~- (и — у, и — у), (б) можно проговодить дискретизацию этой последней задачи.
Реализация проекционного метода в этой ситуации приводит к методу Ритца. Итак, рассмотрим следующую краевую задачу 608 Глава О. Численное рсшснис крассах задач откуда 1(и) > 1(у), если и ф у. Поэтому вместо того., чтобы решать задачу (1), можно решать задачу (6) Е(и) — 1п1, и, следовательно, при приближенном решении вместо того, чтобы производить дискретизацию задачи (1), можно дискретизировать задачу (6). А это в свою очередь может привести к иным классам алгоритмов численного решения краевой эада.ли. 2.
Задача, эквивалентнаи экстремальной задаче. В предыдущих рассуждениях мы нигде не пользовались спецификой уравнения (1) и спецвфическим видом функционала (2). Поэтому предыдущие рассуждения носят общий характер. Пусть Н - вещественное гильбертово пространство, (и, и): Н х Н вЂ” ~ К -- симметрическая, положительно определенная билинейная форма: (и, и) = (и, и), (и, и) > О при и ф. О.
Рассмотрим функционал Е(и) = (ль и) — 2:р(и), где ум Н вЂ” ~ В. -- линейный функционал. Рассмотрим задачу (6) и следу- ющую задачу: найти и 6 Н такое, что (7) (и, и) —:р(лл) = О чулл е Н. Предложение 1. Ел.ли одна из задач (6),(7) ллмссзп рсшсниееч тв и второл задача имеет тв зюс самос решение. Решение каждой иэ задач единственно. Если у — решение одной из задач, то имсвт место (5). Доказлгйльствсь Пусть у решение задачи (6).
Имеем очевидное соотношение Е(у и) =1(у) -ьс((у, и)+(и, у) — 2у(и)) — 'в (и, и). (8) Отсюда в силу произвольности в из неравенства 1(у -~ ви) > 1(у) вытекает (7); если имеет место (7), то из (8) вытекает (6). Единственность решения задачи (7) очевидна. В самом деле, елши 1лл и уа два решения задачи (7), то очевидно, что (ул — у, и) —..— О лулл и 1Х, откуда ул = уз, сз 3. Обобщенное решение. Приведем в общем виде конструкцию функционала 1 и гильбертова пространства Н.
Пусть нам дано гильбертово пространство С со скалярным произведением (, ) и в нем симх|етрический оператор А с областью оллределения Рл, плотной в С. Потребуем, чтобы Уи и Рл (Аи, и) > С~~и(~ . Превратим Рл в предгильбертово пространство., введя новое скалярное произведение (и, и) = (Аи, и). э 4. О резаении краевых задач методом конечных олелзешаоо 609 Элементарно проверяется, что билинейная форма (, ): 1ул х Рд — э зс является скалярным произведением. В самоы деле, она линейна по каждому аргументу, симметрична и (и, и) > С~ и, з, (10) и поэтому равенство (и, и) = 0 влечет и =- О. Из неравенства (10) слеЦУет, что последовательность 1иа), фУндаментальнаЯ по ноРме (( )) —-- = ( . )Но будет фундаментальной и в С. Вообще говоря, 13л в норме (( )) может быть неполным пространством.
Поэтому стандаргной процедурой добавления идеальных элементов пополним 1зл до гильбертова пространства Н, причем, несложно доказать, что 1Ул будет плотным в Н. Кроме того, неравенство (10) будет выполняться для любого элемента и е Н. Мы не привалим конгтрукнии пополнения предгильбертова пространства. Читатель с конструкцией пополнения уже встречаося, хотя бы в теории иррациональных чисел.
Применительно к метрическим пространствам с этой конструкцией можно познакомиться по учебнику [64). Рассмотрим задачу на ыинимум 1(и) —.. (и, и) — 2(1, и) э знГ. Если и с Н, то по неравенствам Буняковского — Шварца и (10) имеем ((1, и)~ ~ (' 1,";и',: < С ~~, )~((и)). (12) Поэтому (1', и) — линейный функционал в Н, и по теореме Рисса су.ще- ствует такой элеыент ио б Н что для любого элемента и Е. Н Но тогда 1(и) — (и,и) — 2(ио.,и) †..(и, и) — 2(ио, и) -~ (ио, ио)— — (ио,ио) =- (и — ао, и — ио) — (ио, ио) и, стало быть, зп1 1(и) = — (ао, ио), аЕН и абсолютный минимум квадратичного функционала 1(и) достигается на элементе ио. Отсюда, согласно предложению 1, будет выполняться соотношение (7), которое в данном случае примет внд (ио, и) -.
(1, и) =- 0 Чзз Е П. Элемент ио называется обобщенным решением или с.лабмм решением уравнения Аи = 1. (14) 610 Глава э. Численное решение крассах задач Если ио Е Рл, то, учитывая определение скалярного произведения (, .), получим, что ио будет решением уравнения (14) —. так называемым классическим решением. Заметим, что обобщенное решение единственно и непрерывно зависит от правой части 7'. В самом деле, полагая в (13) и = ио и используя неравенство ('1 2), получим (15) ((ио)) < С ';У,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
