Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 18
Текст из файла (страница 18)
Приравнивая нулю коэффициенты при у и единице, приходим к уравнениям для а и р: а+ Ьаз — а=О, р+ арЬ+ ар — /=О. Эти уравнения дополним начальными данными, используя стандартный прием метода прогонки. Левое краевое условие х(0) =.Ф'О запишем в виде того же самого прогоноч ного соотношения: х(0) = а(0) у(0) + р(0).
Очевидно, следует положить а(0) = О, р(0) = 2' . Итак, получены задачи Коши для а(1) н р(Г). Они могут быть проинтегрированы (например, численно), и можно считать, что функции а(Г) и р(1) у иас уже есть. Перейдем к следующему характерному элементу прогонки— разрешению правого краевого условия. Имея условие у(1) =0 и метод еи««егеииилиьиоИ ш огоики 59! 9! прогоночное соотношение при г = 1: х(1) = а(1)у(1) + р(1), легко находим значение х(1) = р(!).
Наконец, рассмотрим заключительный этап прогонки. Опять-таки отклоним напрашивающийся рецепт: раз мы знаем х(1) и у(1), можно (формально) интегрировать задачу Коши справа налево, Но зта задача так же неустойчива, как и задача Коши, решаемая слева направо. Мы воспользуемся уравнением у = Ьх+ Р. Заменяя х из прогоночного соотношения х = ау+ р, получаем уравнение для у: у= Ьау+ рЬ+ о, у(1) =О. Проинтегрируем задачу справа налево, попутно определяя х(г) = = а(г)у(г) + О(г). Перейдем к анализу метода прогонки, рассматривая для общности краевые условия вида Ах(0) + Ву(0) = С.
В этом случае а(0) = — В/А, р(0) = С/А. РазбеРио 9 ремся в том, действительно ли «большой» параметр (который так н осгался в задаче) уже не страшен и процесс вычислений устойчив. Нам нужны некоторые оценки для а(!). Ограничимся физически наиболее естественными условиями при г = 0: А>0, ВаО, т.е. а(0) >О. Рассмотрим поле направлений а. На плоскосги (1, а) введем кривую (рис. 9) а = О, т.е. а(г) и'Ь(с)7а(г) = О(1). При а = О, очевидно, а > О.
Вьшелим области а > 0 (ниже кривой а(!)) н а < 0 (выше кривой а(г)). Несложный анализ показывает, что 0 ж а(1) ц шах а(!) = О(1). Этого нам достаточно для дальнейшего. Посмотрим, что даег теория численного интегрированна, примененная к уравнению а = — Ьаз+ а. Если бы мы оценивали устойчивость численного интегрирования для этой системы по самой общей теореме, оперирующей с оценкой погрешности типа еес' (где С— константа Липшица правой части, е — локальная погрешность), то картина была бы пессимистической. В самом деле, Сж ~ — (Ьаз)! ж2Ьаж80, ди основы вычнслнтвльнон млтвмлтнкн и все трудности были бы такими же, как и при методе фундаментальных решений.
Но а ( — Ьа + а) = — 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 —  — !Р +а!+ '» ь а ь а Здесь е„— суммарная погрешность, связанная с выполнением операций в правой части формулы. В нее включаются также погрешности машинного представления коэффициентов с„, Ьь,.а„, погрешность выполнения машинных операций и погрешносп округления, связанная с записью Р„а, в памяти в виде Р„'+,.