Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 10
Текст из файла (страница 10)
43 Записывая Ф, в виде Ф = (и;„,. — и" (х;)) + (и" (хд + ~;) и учитывая, что согласно (8) выполняется равенство и" (х,)+~,=0, получим ф = и„-,, — и" (х,) . Разложение по формуле Тейлора показывает, что если и'~(х) ограничена, то ~,=0(й') при й- О. По этой причине говорят, что разностная схема (16) имеет второй порядок аппроксимации на решении исходной задачи (8) — (9). Наша ближайшая цель — показать, что схема (16) сходится, т.
е. г; 0 при й-э.О и, более того, имеет второй порядок точности, т. е. г,=О(й'). Воспользуемся возможностью получить решение задачи (38) в явном виде. Уравнение (38) отличается от изученного ранее уравнения (!8) только обозначениями. Поэтому согласно (20) решение задачи (38) представляется в виде х — а) г,'= — '"„'й ~~~~ йф! — 'Я й ~~~ йфн 1'=2,3, ..., л1, (40) а=с 2=1 а=в Ф-1 х г, =й(й — а) '~' й ',~ йфь А=1 ! -1 Из разложения по формуле Тейлора Ф /Р и- .=и (х!)+ — и!~ (т;) Хтй !2 и ограниченности и'т(х) следует, что существует постоянная М,) = О, не зависящая от й и от 1 и такая, что !Чь! ~М,й', 1=1, 2, ..., й! — 1. Поэтому из формулы (40) следует оценка !гс!((М,йт) Г ' й'( '1 +йэ '!' Ь Ь вЂ” а 2 2 т. е.
~ г~ ~ ф (М,й~) ! — (л! — 1) д! + ! (!' — ! ) 1 — . ьн 2 Выражение в квадратных скобках равно 1(И+1 — 2) и оценивается сверху числом 2№. Таким образом, !г ! ((М й2)№йх — М (й а)2йи т. е. ! г,! =0(й') при й-~.0, 1=1, 2, ..., й' — 1. В этом случае говорят, что схема имеет второй порядок точности. Отметим, что приведенный здесь способ исследования сходи- мости, основанный на явном представлении решения разностной задачи, непригоден для более сложных задач. Другие методы исследования сходимостн разностных схем излагаются в части П1.
!. Метод прогонки. Система уравнений (16) представляет собой частный случай систем линейных алгебраических уравнений АУ=1 с трехдиагональной матрицей А=(а„], т. е. с матрицей, все элементы которой, пе лежащие на главной и двух побочных диагоналях, равны нулю (а„=О при !)!+1 н !(! — 1). В общем случае системы линейных алгебраических уравнений с трехднагональной матрицей имеют внд а,у,,— с!у,+Угу;„= — !!, 1=1, 2,, А! — 1, (41) У~=к~У!+!4 Ук =яйе-~+Ум (42) Для численного решения систем с трехдиагональными матрицами применяется метод нрогонкп, который представляет собой вариант метода последовательного исключения неизвестных.
Особенно широкое применение метод прогонки получил при решении систем разностных уравнений, возникающих при аппроксимации краевых задач для дифференциальных уравнений второго порядка. Приведем вывод расчетных формул метода прогонки. Будем искать решение системы (41) в виде у;=а!ь,у!,+!1, „1=0, 1, ..., А! — 1, (43) где а!~„(1,„, — неизвестные пока коэффициенты.
Отсюда найдем у!, ='а;уг]+ !!! = а; (аг„у!~, + ()гм) + б! = = а!аг„уг„ + (а!]!!„ + ])!), ! = 1, 2, , л! Подставляя полученные выражения для у„уг, в уравнение (41), приходим при !'=1, 2,..., л1 — 1 к уравнению (а е,(а а,— с)+У!]у;ь,+(!)ге,(а!а,— с )+а!]3!+!!] =О. Последнее уравнение будет выполнено, если коэффициенты а!~ь б!„выбрать такими, чтобы выражения в квадратных скобках обращались в нуль. А именно, достаточно положить ! ! ! ! ! Соотношения (44) представляют собой нелинейные разпостные уравнения первого порядка. Для их решенвя необходимо задать начальные значения ао ])ь Эти начальные значения находим из требования эквивалентности условия (43) при 1=0, т.
е. условия д,=а,д, +Рь пеРвомУ из УРавнений (42). Таким обРазом, полУчаем а,=мп ~,=ре (45) Нахождение коэффициентов а!+„б!,, по формулам (44), (45) называется прямой прогонкой. После того как прогопочные коэффициенты а!го бы„1=0, 1, ..., А' — 1, найдены, решение системы (41), (42) находится по рекуррентной формуле (43), начиная с 46 /=У вЂ” 1. Для начала счета по этой формуле требуется знать у,, которое определяется из уравнений уя = Х~ун- ~+ Рь ул — ~ = ануя+ [)я и равно (хьря+р,)/(! — х,ан). Нахождение у, по формулам ут — — а;„у;„+ [1; „, /' = У вЂ” 1, /'т' — 2, ..., О, хФя + Рэ ун = 1 — хеин (46) [с,— аа,[) [ [с;[ — [а,[ [а,.[ [ =-» [ [с,[ — [а,[ [ и условий (47) получаем [с; — а,а;["=: [Ь,[)О, т. е.
знаменатели выражении (44) не обращаются в нуль. Более того, [ь,.[ ! 1[= ' <1 ! с! — а1а; ! Следовательно, [а,[<1, 1=1, 2,..., У. Далее, учитывая второе из условий (48) и только что доказанное неравенство [а,[=1, имеем [1 — х,ск.,[3ь! — [х,[ [а [)! — [х,[>О, т. е. не обращается в нуль н знаменатель в выражении для ул. К аналогичному выводу можно прийти и в том случае, когда условия (47), (48) заменяются условиями а;~О, Ь;+О, [с,[) [а,[+ [Ь~[, 1=1, 2, ..., /ч' — 1, (49) (бо) В этом случае из предположения [а,[<1 следует [с,— аа,[=-[[с;[ — [а,[[> [Ь,[, [а л,[<1, 46 яазывается обратной прогонкой.
Ллгорнтм решения системы (41), (42), определяемый по формулам (44) — (46), называется методом прогонки. Г1рнменяются и другие варианты метода прогонки (см. [32[). Метод прогонки можно применять, если знаменатели выражений (44), (46) не обращаются в нуль. Покажем, что для возможности применения метода прогонки достаточно потребовать, чтобы коэффициенты системьг (41), (42) удовлетворяли условиям аРО, ЬМО, [с,[) [а,[+[Ь,[, /=1, 2, ..., йг — 1, (47) [х,[<1, [хг[<! ° (48) Заметим, что числа а„Ь„с„х„х, могут быть комплексными. Сначала докажем по индукции, что прн условиях (47), (48) модули прогоночных коэффициентов аь /=1, ..., У вЂ” 1, не превосходят единицы. Согласно (45), (48) имеем [я,[=[х,[<1. Предположим, что [а;[<1 дла некотоРого 1 н докажем, что [Яь„[<1.
Из оценок т. е. все прогона шые коэффициенты, начиная со второго, по модулю строго меньше единицы. При этом 11 — х,а~))1 — 1х.)1а ('= :=ь 1 — ! а „ ~ ) О. Таким образом при выполнении условий (47), (48) (так же как и условий (49), (50)) система (41) — (42) эквивалентна системе (44) — (46). Поэтому условия (47), (48) (или условия (49), (50)) гарантируют существование и единственность решения системы (41), (42) и возможность нахождения этого решения методом прогонки. Кроме того, доказанные неравенства )а,~ «=1, 1=1, 2, ..., У, обеспечивают устойчивость счета по рекуррентным формулам (46).
Последнее означает, что погрешность, внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам. Действительно, пусть в формуле (46) при 1'=1',+1 вместо уя„вычислена величина уьы=уь,+6;„,. Тогда на следующем шаге вычислений, т. е. пРи 1'=1„, вместо У„= — аь,,рь..+~,„„полУчим величину у,-„=аь,,(уь+,+ба„,)+~;,„и погрешность окажется равной 6!, =у;, — у,, = а;,„бп,„. Отсюда получим, что (б;,( = (а,~,!16,„„,( ~16„.„,~, т.
е. погрешность не возрастает. Отметим, что для разностной краевой задачи (16), записанной в виде У;,— 2У,+У,.„= — Р~ь 1=1, 2, ..., У вЂ” 1, имеем а,=б;=1, с,=-2, х,=х,=-О. Поэтому выполнены условия устойчивости (47), (48) и решение задачи (18) можно отыскивать методом прогонки. ЧАСТЬ И ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ И АНАЛИЗА ГЛАВА 1 ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ В главах 1, 2 рассматриваются численные методы решения систем линейных алгебраических уравнений Ах=(, (1) где А — матРица тМт, х=(хь х„..., х )' — искомый вектоР, 1= =(1„(ь ..., 1 )" — заданный вектор.
Предполагается, что определитель матрицы А отличен от нуля, так что решение х существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А. Из курса алгебры известно, что систему (1) можно решить по крайней мере двумя способами: либо по формулам Крамера, либо методом последовательного исключения неизвестных (методом Гаусса). При больших т первый способ, основанный иа вычислении определителей, требует порядка т! арифметических действий, в то время как метод Гаусса — только О(т') действий. Поэтому метод Гаусса в различных вариантах широко используется при решении па ЭВМ задач линейной алгебры. Методы численного решения системы (1) делятся на две группы: прямые методы и итерационные методы.
В прлмык (нли точных) методах решение к системы (1) находится за конечное число арифметических действий. Примером прямого метода является метод Гаусса. Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы па самом деле пе приводят к точному решению системы (1) и называть их точными можно лишь отвлскаясь от погрешностей округления. Сопоставление различных прямых методов проводится обычно по числу арифметических действий (а еще чаще — по асимптотике при больших т числа арифметических действий), необходимых для получения решения. При прочих равных условиях предпочтение отдается методу с меньшим числом действий. Итерационные методы (нх называют также методами поеледовательньи приближений) состоят в том, что решение х системы (1) находится как предел при и-+.ьо последовательных приближений х'"', где п — помер итерации.
Как правило, за конечное число итераций этот предел не достигается. Обычно задается некоторое ма- 4а ч 1. Метод Гаусса численного решения систем линейных алгебраических уравнений 1. Основная идея метода. В ближайших двух главах рассматриваются численные методы решения системы линейных алгебраических уравнений Ах=(, (1) где А — вещественная квадратная матрица порядка ги, а 1 — заданный н х — искомый векторы, Будем предполагать, что определитель матрицы А отличен от нуля. Тогда для каждого вектора 1 система (1) имеет единственное решение. Запишем систему (1) в развернутом виде амх, + а„,х, + ... + а„„х„, = („ амх, +а„х,+...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
