Метод прогонки является частным случаем метода Гаусса и применяется для решения систем линейных уравнений с трёхдиагональной матрицей. Такая система, в частности, получается при построении кубического интерполяционного сплайна. Но давайте разберемся подробнее с задачами из физики, приводящими к такой конфигурации, и со способами решения...
Почему появилась необходимость решать СЛАУ с 3х-диагональными матрицами
Такие матрицы часто называют ленточными, потому что похожи на ленту, проходящую через диагональ :) Но, соблюдая математическую строгость, будем называть её трехдиагональной матрицей или матрицей Якоби. Во всех местах, кроме главной диагонали и двух соседних с ней, стоят нули.
Системы линейных алгебраических уравнений (СЛАУ) с такими матрицами встречаются при решении многих задач математической физики.
Теория разностных методов решения дифференциальных уравнений в настоящее время является обширной и самостоятельной областью вычислительной математики. Она включает развитый аппарат априорных оценок разностных решений, анализа устойчивости и сходимости, оценок погрешностей, а также специальные алгоритмы решения разностных уравнений. В то же время значительная часть таких результатов описывается в терминах матричных или векторных операций и опирается на исследования линейной алгебры.
Системы разностных уравнений являются прекрасным примером приложения теории матриц, и в значительной степени — именно трехдиагональных. В свою очередь, многочисленные актуальные задачи физики, приводящие к разностным схемам, оказались толчком для проведения новых интенсивных исследований по линейной алгебре.
По теории разностных методов есть специальная литература, например, фундаментальные монографии Марчука и Самарского.
Где такие матрицы встречаются в физике
Задачи, включающие в себя трехдиагональные системы линейных алгебраических уравнений (СЛАУ) в качестве основных или вспомогательных компонент, можно разделить на несколько типов:
1. Одномерные краевые задачи для дифференциальных уравнений второго порядка (задача Дирихле для уравнения Пуассона, задача Неймана, смешанная краевая задача);
2. Параболические задачи с одной пространственной переменной (одномерная задача нестационарной теплопроводности или диффузии );
3. Решение многомерных эллиптических и параболических уравнений (задача Дирихле для уравнения Пуассона в двумерной граничной области);
4. Решение локально-нелинейных одномерных задач (двухфазная задача Стефана);
5. Еще одним примером краевой задачи с применением трехдиагональной матрицы может служить задача Штурма-Лиувилля, заключающаяся в отыскании нетривиальных решений однородного уравнения на некотором отрезке. В свою очередь, эта задача служит постоянным источником новых идей для спектральной теории операторов и смежных вопросов анализа.
6. Применение трехдиагональных систем не ограничивается задачами математической физики, они встречаются в алгоритмах сплайновых аппроксимаций, а так же в задачах линейной алгебры, для решения проблемы собственных значений матриц общего вида.
Сами по себе матрицы общего вида применяются практически во всех областях как вычислительной математики, так и в инженерных задачах. Например, при решении задач на прочность и жесткость конструкций формируется глобальная матрица жесткости системы, в тепловых задачах матрица имеет смысл теплового сопротивления, матрицы также применяются при решении задач оптимизации и т. д. Существует целый ряд методов по сведению матриц к разряженному виду при переходе к компьютерному решению различных задач. Матрицы обычно принимают симметричный вид и нередко трехдиагональный.
Теория для программирования метода прогонки
Для решения трехдиагональных СЛАУ часто применяют метод прогонки. Основным его преимуществом является экономичность, т. е. то, что этот метод максимально использует структуру исходной системы. Недостатком метода является то, что с каждой итерацией накапливается ошибка округления.
Каноническая запись системы уравнений имеет вид:
Матрица системы записывается в виде:
Основные условия корректности данных для правильного решения:
Как было указано выше, основным недостатком данного метода является его способность лавинообразно накапливать ошибку, поэтому актуальны методы исследования устойчивости метода прогонки. Если вы внимательно посмотрите на дальнейшие выражения для коэффициентов прогонки, то поймете условие, которое написано под пунктом 2 (см ниже). Основным методом анализа устойчивости метода прогонки является условие диагонального преобладания. Здесь нужно обратить внимание на знаменатели в дробных выражениях коэффициентов прогонки. Если знаменатели будут близки к нулю, то метод прогонки может оказаться неустойчивым. Условие диагонального преобладания является достаточным условием для устойчивости прогонки, но не является необходимым. Условие диагонального преобладания написано под пунктом 2.
Так как в большинстве языков программирования нумерация индексов начинается с 0, а не с 1, то эту корректировку также следует принять во внимание (!).
Начальные условия:
В силу того, что не во всех строчках матрицы имеется по 3 числа, а коэффициенты являются рекуррентными соотношениями, выражаются через соседние коэффициенты и зависят от граничных значений, то нам нужно принять во внимание следующие граничные условия (ГУ) для рекуррентных соотношений:
Метод прогонки состоит из двух этапов: прямой ход (определение прогоночных коэффициентов Uk, Vk), обратный ход (вычисление неизвестных Xk).
Практическая схема применения метода прогонки:
1. Ввод трехдиагональной матрицы a[n][n] и столбца свободных коэффициентов b[n]. Учет и инициализация граничных условий.
2. Прямой ход – формирование прогоночных коэффициентов
(с 0-го по (n-1)-й):
3. Обратный ход – вычисление n-го корня: Xn = Un и остальных корней
4. Вывод результата в виде вектор решений X[n].
И на последок, приведу пример того, как можно запрограммировать данный алгоритм на языке Python (без использования сторонних библиотек для численных методов).
Код реализации решения СЛАУ методом прогонки на Python
[ https://pastebin.com/tgSg2nMM ]
Друзья, если Вам нравятся подобные разборы задач, то поддержите эту статью активностью (лайк, комментарий, репост в социальные сети). Вам не сложно, а мне приятно и мотивирует писать дальше :)
Ещё полезные статьи по теме:
1. Что такое численные методы и почему они упрощают жизнь? Разбор на простом примере
2. Метод Якоби: решение СЛАУ методом итерации
3. Численные методы: составление обратной зависимости x(y) для сложных зависимостей y(x)
4. Какие книги читать по численным методам?
5. Разбираем циклы в Python на простых примерах. Какой цикл быстрее?
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram