4.10. Методы решения слау с трехдиагональной матрицей Рассмотрим систему трехточечных уравнений

(4.44)

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

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

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

(4.45)

с неопределенными коэффициентами и .

Подставим в уравнение .

Получим . После приведения подобных имеем

. (4.46)

Подставим теперь (4.45) в (4.46) и преобразуем полученное равенство

,

.

Последнее уравнение справедливо для любых , если

,

.

Отсюда получаем рекуррентную формулу для

, , (4.47)

и рекуррентную формулу для определения

, . (4.48)

В обоих случаях предполагается, что .

Если коэффициенты и известны и известно значение , то, двигаясь от к , получим последовательно все . Определим начальные значения для коэффициентов и . Для этого используем первое уравнение системы (4.44) и равенство (4.45) при . Имеем

,

.

Сравнивая эти уравнения, получим

, . (4.49)

Используем теперь для определения значения последнее уравнение системы (4.44) и равенство (4.45) при . В результате получим систему уравнений

,

решая которую находим

. (4.50)

Описанный метод решения систем линейных алгебраических уравнений с трехдиагональной матрицей называется методом правой прогонки. Коэффициенты и называются прогоночными коэффициентами, формулы (4.47)-(4.49) описывают прямой ход метода прогонки, а формулы (4.45) и (4.50) – обратный ход. Для решения системы (4.44) необходимо выполнить операций умножения и деления.

Алгоритм метода правой прогонки будет корректен, если в формулах (4.47) и (4.48) отличны от нуля значения . Кроме того, если все по модулю больше единицы, то может произойти сильное увеличение погрешности, и, если достаточно велико, то полученное реальное решение будет значительно отличаться от искомого решения.

Теорема 4.5 (достаточное условие корректности и устойчивости метода прогонки). Пусть коэффициенты системы (4.1) удовлетворяют условиям , ,

, , , , ,

, (4.51)

, , (4.52)

причем хотя бы в одном из неравенств (4.51) или (4.52) выполняется строгое неравенство, т. е. Матрица системы (4.44) имеет диагональное преобладание. Тогда для метода прогонки имеют место неравенства , , , гарантирующие корректность и устойчивость метода.

Доказательство: Покажем, что из неравенства , и условий теоремы следует, что и .

Пусть , . Тогда

= .

Следовательно, . Кроме того

.

Так как , то неравенства выполняются для всех . Покажем, что . Если , то и . Значит, если одно из неравенств (4.51) или (4.52) является строгим, то обязательно и

.

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

и следует, что

, т. е. , где и

. Так как для всех , то

.

Это означает, что погрешность вычислений не возрастает в процессе решения системы (4.44), т. е. метод прогонки устойчив.

ЛЕКЦИЯ № 16