А.А. Самарский - Введение в численные методы (1113832), страница 21
Текст из файла (страница 21)
е. решения уравнения х' = а илп /(х) = х' — а =О. Применяя формулу (15), получим 1/ ат — 2 (х„+ — ~, л Пусть а=2. Выбирая ха =1, найдем х, 1,5, х, -"* 1,417, х, = 1,414, ..., т. е. итерации сходятся очень быстро. Оценим скорость сходпмости итераций. Лредполо ким, что существует вещественный корень х* уравнения (1).
Рассмотрим некоторую окрестность корня: е = (х — бю х*+ б,), б, > 0 Будем считать, что функция (17) дважды дифференцируе- )34 гл, пь Равнение лчгевгхичвсиих гглв!п5пий ма в й, п ее вторая ирои:июдиая ограничена; !гр" (х)! «2й/, (18) где г/ ) 0 — постоянная. Разложим ср(,т) в строку Тейлора в окрестности х = х*: <р(х) =- ~р(х*) + ~р'(х*) (х — хг) .р ™ (х ха)г $ =. х* — ', 0(х — х*), 0 0(1.
(19) Вычисляя затехг и замечая, что ср (х*) = 0 прп / (х*) Ф О, получим ср (х„) = юр (х") + ", ~р" (Б). (20) Для погрегпностп г„„=х„+, — х* получим формулу: г„.„= х,+т — х* — -- ~р (х„) — ~р (та) =- — (х, — х~)'-гр" (с), т г —:г = 2 й (ь) г ° Отсюда и пз (20) следует ) г„:,)(дг, (21) Ооозначая в, = р,'г„), получаем г„, «» г',,(» г„, ('...:6, »(... » «г1 » «гз, и, следовательно, )г; (( — (Ч(=О()г"' ' Ч (22) /)тсюда видно, что птерац|пг (15) сходятся к корню ха ири и —, если г/~г,) < 1 плп (г,! )х„— х*! ( 1/д, (23) т. е. начальное приблигиеняе находится в окрестности Л~ = (х* — 1/д, ха + 1/о) с 6, = 1/о корня х = х* уравпеяия (1).
В атом случае метод Ньютона, как принято говорить, сходится с квадратичной скоростью (метод простой итерацяи сходится со скоростью геометрической прогрессии). Условие окончания итераций )г„) ~ е)г,), как следует нз(22), или (г„) «())г,!)га ' )г,), выполнено, если я«~я,(е), $ ь Рвшнние нелпнвпныд угавненггп 136 где и (е) =- ~1п(1+ 1п — 1)п — )~1п 2~, (24) 1! 1 Очевидно, что если начальное приближение находится в малой окрестности х*, то и все последующие итерации останутся в этой окрестности Ье В самом деле, пусть 'Ог, — х*~ ~ 6„ причем дб, ( 1. Тогда будем иметь Ог, — х*) ~ д!х, — х* Р ~ дб,'( б;„ ~х, — хе! ~ д~х, — .тар ( .=.-.
дб,„ - 6, и т. д„ так что !х. — х~~ ( 6, для любого л-1,2,... В а и е ч а и п я, 1. й!ы не останавливаемся на доказательстве существования корня х = х*. 2. Квадратичную сходнмость метода Ньютона можно установить и ирп более слабых ограпиченияк на !(х): ! 1'(х) ) ~ М, > О, 11'" (х) ~ =. М: для всех х ю Л,, (25) 1!спользуя (15) и (16), получим для погрешности г.е, = == х„„, — х* выражение (ь) зт 2~'( ) пз которого в силу условий (25) следует неравенство !ю,~,! -г)!з.!', д=М.П2М,), которое совпадает с (21) (различие только в д), Дальней- шие рассуждения зтриводят к (22), (23) п (24).
3, Непрерывный метод Ньютона. Решение уравнения Лх) = 0 можно рассматривать как предел прп ! — ре- шения задачи 1(оши: — ", +7(х) =О, х)0, х (0) = и„(26) если этот предел существует, Обозначим через х=х(1) решение задачи Коши, через хе — решение уравнения !(х) = О. Для пи разности з(1) =- х(1) — хч имеем — „, + (1(х) — 1(хе)) = —, + ~'($) з, 6 =- х + Ог, О =6<1, д + а(1) г=- О, 1>0, г(0) = им а(1) = ~'($). Ото!ода видно, что Ь(1)~ - 0 прп 1- », если )'(х))О. 13З ГЛ ПЬ РЕШЕНИЕ АЧГЕВРАИЧЕСКИХ УРАВНЕНИЙ Для ре1пения уравнения (26) надо воспользоваться каким-либо явным методом. Быстрота сходлмостл х1)) к х, зависит только от величины производной )(х).
4. Метод секущих. Вычисление производной )'(х„) в методе Ньютона мов'ет оказаться трудоемким. Если за- Ф менить )~ разностным отпошением (,)„— 1„,Их„— х„,), то мы получим итерационный метод секущих (хп хл-1) ~ (хи) ) ("):,'(.. ",) Метод снкущих сходится медленнее метода Ньютона, однако в (27) вычисляется только функция, а в (15) надо находить п функцию и ее производную. Поэтому объем вычислений на каждой итерации в методе секущих, вообще говоря, меньше, Глава (Ъ' РАЗИОСТНЫЕ МЕТОДЫ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ ДЛЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЫ1ЫХ УРАВНЕНИИ 5 1. Основные понятия теории разностиых схем Упивероальным численным методом решения дпффереициальныл уравнений является метод конечных разностей. Прежде чем переходить к его азложенпю, необтодимо ввести основные понятия теории разностнык схем — аппроксимацию, устойчивость и слодимость, 1.
Простейшие разностные операторы. Для получения вместо дифференциального уравнения разностного уравнения необходимо: — заменить область непрерывного изменения аргументов дискретным множеством точек (сеткой); — заменить (аппроксимировать па сетке) дифференциальное уравнение разностным уравнением. Вопрос о численном решении дифференциального уравнения сводится к вопросу о решении разностнык уравнений, В предыдущих главах мы уже рассматрпвалл прлыеры сеток: 1) равномерная сетка на отрезке 0 «х «1 с шагом Ь; множество узлов юз = (х, - ()т ( О, 1, 2, ..., А', Ь = 1/Л); х, =О, х, =1 - гранпчные узлы; еь,=(х, =()ц (= 1,2,...
..., М вЂ” П вЂ” множество внутренних узлов; 2) неравномерная сетка: отрезок 0 «х «1 разбивается на )т' частей произвольнызш точками х, «х, « ...«хз,; 6;=х,— х;,— шаг сетки; л гзь .= (х;, ( = 0,1,, Ж, х, = О, хл =- 1), ~, Ь; = 1, ~.=1 геа =- (хь 0((<Х); 3) сетка на отрезке 0 «( «Т; ы, =(г„= пт, и =О, 1,... ... лм лгт Г). Вместо фуикцнп непрерывного аргумента (например, иа отрезке 0 -х< 1) рассматривается фупкцшг р(х,) = у, дискретного аргумента х„где х,— узел сетки ыз, или аргумента ( — номера узла, Эта функция называется сс- (Зя гл !т Рлзностнык нето ты для кг левых зздх1 точной. Любую сеточную функцию у(х,) = у; можно представить в виде вектора (У», У», ° ° Уз-» Уь).
Поэтому множество сеточных функций образует копсчномерное пространство П, в данном случае размерности (Л'+ '1). Обычно рассматривается семейство се~он (ы»), зависящих от шага как от параметра. Поэтому и сеточные функции у = у,(х) зависят от шага как от параметра (или от )т), если сетка ы, равномерна. Если сетка неравномерна, то под Ь понимается вектор Ь = (Ь„Ь,,, Ьк).
Естественно поэтому снабдить пространство сеточных функций индексом Ь п писать Нь В пространстве»»», можно ввести норму» зы Укажем простейшие виды пори: ~У1~ = а (у( ) ~ л !»у~~~ =,(у )' кеяь ее»ен Дифференциальный оператор заменяется разпогтным оператором, действующям в пространстве сеточных функций. Пусть С вЂ” область евклидова пространства »т'" (р =- 1, 2, 3) с границей Г. Напр»»т»ер, 6 — интервал О <х < 1. à — точки х=О, х=1: 6 — прямоугольник О<х, -1,, О < х, < 1„х = (хо х») ю С (р 2), Г состоит из отрезков прямых х,=О, х; = 1,, х, = О, х, =1, п т. д, Пусть задан линейнып дифференциальный оператор»., действующий на функцию и(х), хи С.
Введем на 6 С О Г сетку еы п будем рассматривать сеточную функцшо и»,(х), х»н о»,. Зат»еяпм Г.о в точке х,»н ы, ливенкой комбинацией значений и»(х) сеточной функции на некотором множестве узлов сетки, которое назовем»иаблоном (» ли)» = Х а»»иь (х,)» х» ен»оь (С), (1) х не» й где ау — коэффкцпенты, о» вЂ” шаблон, а,»н ы . Такая замена».и на Геи называется аппрокеил»ауией на сетке дифференциального оператора е.
разностпым оператором Еы или рааноетной аппрокеила»)ией оператора Г,. Изучение разностных аппроксимаций Е, оператора й обычно проводится сначала локально, т. е. в любой фиксированной точке сетки, Построение Г; надо начи- з ь основныв понятия твогии глзяостных схим )зв пать с выбора шаблона о(х), т. е. множества узлов, соседних с узлом хж юь, в которых значения сеточной функции и,(х) могут быть использованы при написании выражения для Х, Рассмотрям яесколько примеров построения ь'ь. Йа 1!ример (, Первая производная: Хг= — =- г'(х).
Возьльель три узла (х — Ь, х, х+ Ь). Можно воспользоваться любым пз выражений Хли = ' „' ' = г» (шаблон (х, х+ Ь)); г )» -'; )ь) — е (») ь ( ь) — и(» — А'ь Хл г = ' = ь:„- (шаблон (х — Ь, х)); 'лг =-, = — г» (шаблон (х — Ь, х + Ь)). гп. г(»+)ь) — г(* Л) 2л Часто применяются названия: ел»и = ь„— правая, Хл и— левая ьли =- и,. =- —. (ь л г + Хл г) — ценгралънап х разностпые производные. На трехточечноль шаблоне (х — Ь, х, х+ Ь) можно определить разностный оператор Х л 'и =.
ог» + (1 — о) г-, где о — действительный параметр, Таким образом, существует бесконечное мноясество разностных аппроксимаций первой производной па трехточечном шаблоне. ХХогреимьоегью аппрокеигвации оператора Л опораторьм Еь называют разность ь(; = Е„г — Ель, Говорят, что Ел имеет тай ьго)тдок аппроксинации в точке х, если ьр(х) = Х.г(х) — Х,г(х) =- 0(Ь") плп ~ ь)(х) / ~ МЬ, где М = сопел ) О ве аависит от Ь, пь > О.
Пспользуя формулу Тейлора г(хп: Ь) = г(х)~Ы(х)+ л г (х) ~ —,и (х) — ',,~ г (х)+ 0(Ь'), $4О ГЛ. Ш. РАЗНОСТНЫЕ МЕТОДЫ ДЛЯ КРАЕВЬТК ЗАДАЧ яетрудио получить оценки г„— г' =- 0 (й), г- — г' = 0 (й), г, — г' =- 0 (йт), х р(х) ТС<и Г 0~~ Т ) й ( йх) Н Р Пример 2. Вторая производная: (г.= — = г" (х). Их Возьмем тот же трехточечный шаблон, что и з примере т, и напишем разпостный оператор т лг (х) Р (х+ Ь) — 2Р (х) -~ Р (х — А) Замечая, что г(х + й) = г (х) + йгх, г(х — й) = г (х) — й~%, преобразуем Ьхг(х): Рх (х) — Р- (х) Р ~х -'; Ь) — Р- (х) Äà (Х) х х х „. (Х) (2) Пользуясь формулой Тейлора для г(х~ й), натодттм ~;=Т,ьг Г,г= — ";, "(х)-;-0(й).=0(й'), т. е.
Гх имеет второй порядок аппроксимации. Обычно требуется оценка погрешности аппроксимации на сетке, т. е. в некоторой сеточной норме ))А. Говорят, что Ц ямеет т-йт порядок аппроксимации на сетке, если )~Гхг, — (Г г),~~, = 0(й"'). 2, Разностная схема.
Обычно дифференциальное уравнение Ьи )(х) решается с некоторыми дополнителшгыми условиями — начальными (задачи Коши), краевымп (краевая аадача), либо и с начальными, и с краевымп условиями. Эти дополнительные условия при переходе к разностным уравнениям надо также аппроксимировать.
Пусть задана некоторая область С с границей Г и пусть ищется решение и=и(х), х<й0, линейного дифференциального уравнения Х,и=)(х), хабиб, (3) с дополнительным условием на границе: а(х) = р(х), х ы Г. 3 с ОснОВные понятия теОРии Рззностных схем (4( Введем в области 6 6+Г сетку оь-о>~+ум алыми, '(з<ю Г, и поставим в соответствие задаче (3), (4) разиостпую задачу с линейным оператором Е, вида (1): Е,у, = ф,(х), х ы юз, у,(х) = м,(х), х ы у,. (5) Функции у,(х), ср~(х), т,(х) зависят от гаага Ь сетки. МЕНЯЯ Ь, ПОЛУЧаЕМ ПОСЛЕДОВатЕЛЬНОСтИ (УА (фз), (Рь). Таким образом,, мы рассматриваем ке одну разпостную задачу, а семейство задач, завигягцее от параметра Ь. Ото семейство задач называется разностной схемой, Пример 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
