§ 3. Решение простейшей краевой сеточной задачи

При численном решении задачи Коши значения решения определяются в последовательных узлах по рекуррентным формулам: в случае краевой сеточной задачи, например (1.3), (1-4), такой возможности нет, поскольку значения решения зависят от граничных условий на обоих концах отрезка интегрирования. Краевую задачу

можно было бы решать следующим способом. Возьмем частное решение неоднородного уравнения

и два линейно независимых решения однородного уравнения . Общее решение неоднородного уравнения запишется в виде

постоянные определяем из граничных условий. Приближения к функциям находим каким-либо численным методом решения задачи Коши, затем определяем и получаем нужное решение.

Экономнее поступить следующим образом. Находим частное решение неоднородного уравнения , удовлетворяющее условию , и частное решение однородного уравнения , удовлетворяющее условию . Общее решение неоднородного уравнения, удовлетворяющее условию , имеет вид значение С определяется из условия .

Метод решения краевой задачи, соответствующий этой схеме, принято называть методом, стрельбы или методом пристрелки. Сеточный аналог этого метода заключается в следующем. Задаемся , произвольными и из уравнений

последовательно определяем . Затем находим С из уравнения и полагаем функция является требуемым решением.

Иногда значения не хранят в процессе вычислений, а после отыскания С находят и затем последовательно определяют из уравнения . Описанный алгоритм формально применим при любых значениях однако для уменьшения влияния вычислительной погрешности разумнее взять .

Рассмотрим модельное уравнение

Решения соответствующего однородного уравнения сильно возрастают (убывают) на рассматриваемом участке, если величина достаточно велика. Таким образом, при величина является параметром, существенно влияющим на характер накопления вычислительной погрешности. Рассмотрим накопление вычислительной погрешности на одном из этапов решения сеточной задачи. Пусть уже найдено значение и далее вычисления проходят по рекуррентной формуле

Получаемые при реальных вычислениях величины связаны равенством

наличие слагаемого в правой части обусловлено округлениями. Вычитая отсюда (4), получим уравнение относительно погрешности :

Рассмотрим следующую модель накопления погрешности: и погрешности в отсутствуют, т. е. . Уравнение (5) можно переписать в виде

(6)

При совокупность соотношений и (6) образует сеточную задачу, аппроксимирующую задачу Коши

Можно проверить, что условия теоремы из § 8.10 выполнены, поэтому решения этих задач будут близки:

Асимптотическое равенство понимается здесь в обычном смысле:

(8)

При умножении си на какой-либо множитель на этот множитель умножится как , так и , поэтому (7) и соответственно (8) справедливы и при , зависящем от h, т. е. в рассматриваемом случае

Рассмотрим числовой пример: тогда и нельзя рассчитывать на получение решения с разумной точностью. Отметим, что значение величины , определившее столь большую величину накопленной вычислительной погрешности, было не очень большим.

При естественной нумерации неизвестных система уравнений (1.3), (1.4) записывается в виде , где матрица А трех-диагональная. Напомним, что матрица называется -диагональной, если при .

Для решения систем уравнений такого вида часто наиболее целесообразно применять метод Гаусса при естественном порядке исключения неизвестных. В случае, когда этот метод применяется для решения систем уравнений, возникающих при аппроксимации краевых задач, его называют методом прогонки.

Приведем конкретные расчетные формулы метода прогонки в случае системы (1.3), (1.4). Представим граничное условие в виде , где . Подставляя в первое уравнение системы (1.3), (1.4)

получаем уравнение, связывающее значения и . Разрешая это уравнение относительно , имеем

где

Подставляя полученное выражение через во второе уравнение системы, получим уравнение, связывающее , и т.д. Пусть уже получено соотношение

подставим выражение уравнение системы (1.3), (1.4):

Разрешая получившееся уравнение

относительно , имеем

здесь

Таким образом, коэффициенты уравнений (10), связывающих последовательные значения , можно определять из рекуррентных соотношений (11) при начальных условиях . Так как известно, то после нахождения всех коэффициентов , можно последовательно определять из соотношений (10). Процесс вычисления коэффициентов принято называть прямым ходом, прогонки, а процесс вычисления неизвестных — обратным ходом прогонки. Последовательность производимых вычислений можно изобразить следующей схемой (на этой схеме означает, что значение используется при вычислении ):

прямой ход прогонки

обратный ход прогонки

Названию «метод прогонки» иногда предлагается следующее объяснение. Уравнение

получено как следствие граничного условия в точке и уравнений системы (1.3), соответствующих точкам . Таким образом, это равенство выполнено для любого решения системы уравнений , удовлетворяющего левому граничному условию; граничное условие в точке «перегоняется» в текущую точку .

Задача 1. Выписать расчетные формулы метода квадратного корня в случае решения рассматриваемой системы. Сравнить трудоемкость этого метода с трудоемкостью метода прогонки.

Применим для решения системы (1.3), (1.4) метод Гаусса при порядке исключения неизвестных . Из первого уравнения выражаем через и подставляем в остальные уравнения. После этого во второе уравнение входят только неизвестные выражаем через и подставляем в остальные уравнения и т.д. Пусть уже выразили через неизвестные и получили соотношения при для единообразия добавим сюда равенства

Подставляя выражения в уравнение

получим

или

где

Таким образом, коэффициенты можно последовательно вычислять по рекуррентным формулам (12). После получения соотношения определяем значение , а затем все по формулам

Вследствие (12) значения удовлетворяют однородному конечно-разностному уравнению (2) и начальным условиям значения — неоднородному конечно-разностному уравнению (1) и начальным условиям . Таким образом, совпадает с в методе стрельбы при определенном выборе начальных условий. Функция удовлетворяет неоднородному конечно-разностному уравнению и левому граничному условию при любых С, причем . Следовательно, решая уравнение , относительно С, мы как раз находим значение , которое отыскивалось в методе стрельбы. Вычисления по формуле (13) соответствуют вычислению значений по формуле . Полученный метод совпадает с методом стрельбы при

Решение системы (1.3), (1.4) описанными выше методами требует арифметических операций; если при решении этой системы обратиться непосредственно к стандартной программе метода Гаусса, то число операций будет порядка это количество операций состоит из содержательных операций метода прогонки и несодержательных операций умножения (деления) нуля на некоторое число, и сложения (вычитания) двух нулей. Таким образом, хотя содержательные операции при решении этой системы методом прогонки и по стандартной программе метода Гаусса одни и те же. использование стандартной программы приводит к существенному увеличению затрат на решение задачи.

Текст программы метода Гаусса может быть преобразован в текст программы метода прогонки, если в преобразованиях над строками и столбцами матрицы изменить начало и конец циклов так, чтобы исключить несодержательные операции.

Рассмотрим теперь случай, когда при имеем граничное условие . В § 1 при его аппроксимации возникло уравнение, связывающее значения ; это уравнение может быть записано в виде

например, простейшую аппроксимацию можно переписать в таком виде при . Далее вычисляем по формулам (11) при и при обратном ходе прогонки по формулам (10). Если при имеем граничное условие , то аналогично (14) имеем уравнение

(15)

Осуществляя прямой ход прогонки, получим равенство

(16)

решая систему (15), (16), находим и затем последовательно вычисляем по формулам (10).

При аппроксимации краевых задач для уравнений высших порядков или для систем дифференциальных уравнений появляются системы уравнений -диагональными матрицами А; матрицу называют -диагональной, если при и при . Для решения таких уравнений также довольно часто бывает целесообразно применять метод Гаусса, алгоритм которого может быть записан аналогично методу прогонки в виде совокупности рекуррентных формул.

Если , то для уменьшения числа арифметических операций целесообразно переобозначить неизвестные и уравнения в обратном порядке, чтобы получить систему с матрицей.

Задача 2. Подсчитать число операций при решении методом Гаусса системы с -диагональной матрицей при .

В ряде случаев -диагональная матрица системы уравнений записывается естественным образом в виде -диагональной матрицы клеточного вида, т. е. —некоторые матрицы такие, что , если или .

Рассмотрим случай системы уравнений

где — векторы размерности . — матрица размерности , и простейшую аппроксимацию

Матрица системы естественным способом записывается в виде (17) с — матрицы размерности же самое время эта матрица является — -диагональной или, что то же самое, — -диагональной. Для решения этой системы может быть применен метод исключения Гаусса в клеточной форме, который аналогично скалярному случаю может быть записан в виде совокупности рекуррентных матричных соотношений типа формул метода прогонки.

Задача 3. Подсчитать число арифметических операций для метода Гаусса в клеточной форме и для общей процедуры метода Гаусса с исключением несодержательных операций в применении к системе уравнений (18).

При решении ряда задач возникают системы уравнений с матрицей А, отличающейся по структуре от -диагоналыюй матрицы наличием ненулевых элементов при , т.е. вблизи левого нижнего и правого верхнего углов матрицы. Для решения таких систем также целесообразно применять метод Гаусса с исключением несодержательных операций. В случае отыскания периодического решения сеточного уравнения (3) этот вариант метода Гаусса называют методом циклической прогонки.

Рассмотрим пример задачи, сводящейся к системе уравнений такого вида. При сглаживании функций методом регуляризации в § 5.3 возникла следующая задача. Дана периодическая функция целочисленного аргумента q; период равен N. Требуется найти периодическую с тем же периодом функцию , удовлетворяющую системе соотношений

Выпишем эти соотношения при . Вследствие условия периодичности заменим значения при и при , входящие в эти соотношения, соответственно на .

В результате этого получится система N уравнений относительно N неизвестных . Элементы матрицы этой системы определяются соотношениями , где

Матрица А симметричная и положительно определенная.

Задача 4. Выписать расчетные формулы этого метода при . Показать, что решение этой системы методом Гаусса с исключением несодержательных операций требует арифметических операций.

Задача 5. Выписать расчетные формулы метода квадратного корня в конкретном случае решения этой системы при . Подсчитать необходимое число арифметических операций.

Выше, когда при рассмотрении метода прогонки выписывались расчетные формулы и подсчитывалось число арифметических действий, был оставлен в стороне вопрос о возможности переполнения процессора ЭВМ, в частности, вследствие деления на нуль. Кроме того, отсутствие переполнения само по себе не гарантирует избавления от большого влияния вычислительной погрешности.

На модельном примере рассмотрим поведение прогоночных коэффициентов при различном знаке . Соотношения

которым удовлетворяют коэффициенты метода прогонки, совпадают с итерационными формулами решения уравнения

Рис. 9.3.1

Рис. 9.3.2

при начальном приближении . Уравнение равносильно квадратному уравнению

его корни

При имеем поэтому . При и h малом подкоренное выражение отрицательно и уравнение (20) не имеет вещественных корней. Совместное расположение графиков и точек изображено на рис. 9.3.1, 9.3.2. Видно, что при значения лежат в пределах (рис. 9.3.1). При не исключено (рис. 9.3.2), что при достаточно больших некоторое значение окажется близким к , тогда следующее значение будет очень большим и может произойти переполнение.

Рассмотрим вопрос о накоплении погрешности при вычислении коэффициентов . Из (19) получаем, что

Следовательно, возмущения в коэффициентах связаны соотношением и при больших происходит также большой рост погрешности. Отмеченные выше обстоятельства приводят к необходимости более детального изучения влияния вычислительной погрешности, по крайней мере при .