Федоренко Р.П. Введение в вычислительную физику (1185915), страница 19
Текст из файла (страница 19)
Но а ( — Ьа + а) = — 2Ьа < О, аа т.е. мы получили устойчивое решение, для которого специальная теорема о точности численного интегрирования не содержит экспоненциального множителя, и для шага т достаточно иметь только соотношение т — „(Ьп~)«к1, т.е. 30 т«в-1.
Итак, нас выручает устойчивость искомого решения а(1). В задаче для р та же самая ситуация: ф-ЬаД+ ар+У) = — Ьа- — 40, а т.е. мы имеем дело с интегрированием устойчивой задачи. Наконец, обратная прогонка. Ее уравнение имеет вид у««Ьау+ (ВЬ+ <р), (Ьау) = Ьп 40 > О. Эта задача неустойчива вправо и, соответственно, устойчива влево.
Но ведь нам нужно интегрировать ее именно справа-налево! И здесь все в порядке, несмотря на присутствие болыпого параметра. Заметим, что прогонку можно осуществить в обратном направлении — решая уравнение для а справа-налево. В этом случае (см. рис. 9) траектория а(с) «притягиваетсяь к кривой а = — т/3(~ЛТа7г) (п(а) < О) и интегрируется устойчивая влево задача. 5 $0. Прогонка в рвзностной задаче И)турма-Лнувнппи Рассмотрим классическую краевую задачу Штурма — Лиувилля: — р(с)~» + д(г) — »+ «(г)х(с) = У(г), с краевыми условиями общего вида: ах+рх=у, 1=0, ах+рх=ум г=Т Начнем с построения разностной схемы, т.е.
разностной аппроксимации задачи, Введем сетку, для простоты равномерную: (г„3„"„в, г„= лт, т =Туй, Ф-в»1, и счетные величины х„, и =О, 1, ..., К. пгогонкА а гизностной задача штл ми-литвнлля Ь 1о1 Построим разностное уравнение, аппроксимирующее дифференциальное: ! х„+ ! — х„ х„-х„!1 х»+! х«-! Рп!!!з ! Рп-Пз ! ~ + ип т! + !пхн Уп~ где рп+пя — — Р(!п + т/2), !1п = д(1„) н т.д.
Это уравнение можно написать только при л = 1, 2, ..., М- 1 (во внутренних узлах сетки). Для дальнейшего уравнениям удобно придать стандартную форму: апхп , — Ьпх, + с„х„.!! = !г„, где а„Ь„, сп, о'„— так называемые локальные коэффициенты схемы. Имеем для них выражения 1 1 и = Р и ! п-!!2 х и' Ь„ = ап + с„ — гп, о1„ = /„. Примем довольно естественные с физической точки зрения условия Р > О, г И О и отметим важное соотношение Ь„> ап + сп.
Аппроксимируем левое краевое условие: х,— хв а — '~+рх =у, и запишем его в стандартной форме: а и Ьвхв + свх! в"в' ЬО 1' св ' !'О Ради простоты ограничимся физически наиболее естественными условиями а > О, р < О; следовательно Ь„> св, Аппрокснмируем правое краевое условие: и и — ! я! т + р!хи= 7! и запишем его в стандартной форме: онхи, — Ь„х„= Ыи.
Итак, мы получили специальную, но очень распространенную в приложениях систему линейных алгебраических уравнений: — Ьохо + с! х! = Ыв> а„х, — Ьпхп + с„хп+, = а!п, л = 1, 2, ..., А! — 1, аихи ! — Ьихи !ги. !ч.г основы вычислительной млтвыдтики Матрица системы имеет так называемую трехднагональную (якобиеву) форму: Π— Ь . с о . о а — Ь с ! ! ! аз — Ьв с„ а», — Ь» е» а„— Ь, О Такие матрицы часто появляются прн аппроксимации дифференциальных уравнений разностными.
Их специфика — большой порядок (л!= Т т) и огромное число нулей (так как операторы дифференцирования являются операторами локального типа: значение производной функции в какой-то точке зависит только от значений функции в сколь упздно малой окрестности этой точки). Большую роль в вычислительной математике играют так называемые экономные методы решения подобных систем уравнений. Это такие методы, в которых количество операций пропорционально первой степени числа неизвестных, т.е.
в данном случае О(М). Напомним, что если бы мы просто сослались на то, что получена система линейных алгебраических уравнений, которую можно решать любой стандартной программой, дело было бы довольно скверным. В общем случае решение системы гт' алгебраических уравнений с !» неизвестными требует О(Ь!з) операций и О(Ь!т) ячеек памяти.
Для систем уравнений с якобневой матрицей был разработан специальный метод лрогонки, требующий О(г!!) операций и О(Ь!) ячеек памяти. Этот метод был разработан почти одновременно в нескольких местах учеными, занимавшимися в сущности одной и той же проблемой. Она была связана с закрытыми работами, поэтому публикации последовали спустя годы после того, как была придумана и весьма эффективно применена прогонка.
Алгоритм прогонки. Решение ищется в форме лрогононного соотношения.' х„, = Р„к„+ Д„л = 1, 2, ..., А!, где Р„, Ą— неизвестные пока лрогоночные коэффициенты. Нетрудно видеть, что, определив Р„, Д„, мы в сущности приведем систему с трехдиагональной матрицей к системе с двухдиагональной мат рицей. 95 ПРОГОНКА В РАЗИООТИОЙ ЗАДАЧЕ ШТУРМА-ЛИУВИЛЛЯ З Г01 Алгоритм начинается с того, что левое краевое условие записывается в форме прогоночного соотношения: «О (с /ЬО) «Г с( /ЬО т,е. Р, = с /Ьа ДГ = -ПГОIЬ0 (отметим, что Р, < 1), Далее следует процесс Прямой лрогомки: последователъно (по рекуррентиым формулам) вычисляются Р, Яз, затем Рз, Дз, и т.д, вплоть до Р», Д». Выведем эти рекуррентные формулы. Пусть прогоночные коэффициенты Р„, Д„уже вычислены. Подставляя х„, = Р„х„+ Д„в л-е уравнение а„х„ , — Ь„х„ + с„х„+, = Г(„,получаем а„(Р„х„+ Д„) — Ь„х„+ с„«„Р, = ГГ'„.
Соотношение между х„и х„+, представим в форме прогоночного со- отношения, т.е. разрешим его относительно х„: с„а„Ц„- И„ ХЛ Б — алРл Л+ Г Бл - алР„' Оно примет стандартный Ьид х„= Р„РГ«„+Г + Д„л„если положить аЦ -ГГ л л л ~л+Г Ь вЂ” аР ' л л с„ ИГ Ь Р «„Г=Р„«„+Д„, И=И,М вЂ” 1,...,1. Исследование устойчивости прогонки. Проведем исследование вычислительной устойчивости прогонки, т.е. покажем, что погрешности вычислений, связанные с конечной разрядностью машинных 'чисел (погрешности округления), и погрешности, связанные с машинной реализацией арифметических операций, накапливаются в такой мере, что это ие приводит к существенным погрешностям в результате.
Это и есть рекуррентные формулы прямой прогонки. По ним вычисляем Р„, Д„вплоть до Р„, Д». (Для атой цели мы последний раз можем исполъзовать стандартное трехчленное уравнение с номером Аà — 1.) Имея ненсполъзованное пока правое краевое условие (М-е уравнение) а»х», — Ь»х» асс(» и протопочное соотношение х», = = Р„х„+ Д», можно найти величину х» (разрешение правого краевого условия). Неизвесгные х„последователъно определяются справа-налево по формулам (обратная прогонка) (ч.
! ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ Рассмотрим сначааа процесс прямой прогонки коэффициента Р„. Введем величины Р„, вычисленные по формулам прогонки Р„= с„/(܄— О„Р„) в идеальной арифметике, т.е, без погрешностей округления и погрешностей в выполнении операций. Реальные расчеты на ЭВМ дают Р'„' = Р„+ Ь„, где ܄— погрешность предшествующих получению Р„вычислений. Предположим, что ܄— малая погрешность (такова она, во всяком случае, иа начальном этапе прогонки) и проанализируем процесс ее эволюции, записывая соотношение между Ь„и Ь„+, в виде а Ра+~+ ба+1 —  — !Р +а!+ '» ь а ь а Здесь е„— суммарная погрешность, связанная с выполнением операций в правой части формулы. В нее включаются также погрешности машинного представления коэффициентов с„, Ьь,.а„, погрешность выполнения машинных операций и погрешносп округления, связанная с записью Р„а, в памяти в виде Р„'+,.
Последняя погрешность очень мала н зависит от разрядности представления чисел в ЭВМ. Таким образом, погрешность Ь„+, есть следствие двух погрешностей: наследственной погрешности Ь„, в которой суммируются погрешности предшествующих вычислений, и локальной погрешности е„, для которой нетрудно указать хорошую оценку через погрешности с„, Ь„и т.д. Воспользуемся тем, что )Ь„! ~сР„, н применим линейный анализ, пренебрегая величинами 0(ЬВ). Используя обычное исчисление дифференциалов, получаем DŽ— О„Р„1Ь а Р >2 а Из этого соотношения следует формула Ь„(Р„) Ь„+е„, и О, 1, ...,Ж 1.
Заметим, что число шагов, выполняемых по рекуррентной формуле, достаточно велико (порядка ТУт), и нас будет интересовать асимптотическое поведение погрешности (при М = тут- ). Сначала получим важные для анализа свойства прогоночных коэффициентов. Л ем ма !. При значениях Ь„> а„+ са и Р, с 1 для всех и имеем О~Р„~1. пгогонкА в глзностноя эадлчв штагма-лятвнлля 97 з га1 В самом деле, если 0 и Р„и 1, то с„ с„ ю-'а. а а» с„ З„- а„л„а„+ с„— а„г„с„+ а„н - Р„1 Разумеется была использована положительность локальных коэффициентов а„, Ь„, с„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
