Навигация
3. Метод прогонки
Метод прогонки представляет собой простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами коэффициентов следующего вида
(8)
Системы такого вида часто возникают при решении различных инженерных задач, например, при интерполяции функций сплайнами.
Преобразуем первое уравнение системы (8) к виду x1 = a1x2 + b1, где
a1 = -с1 / b1 и b1 = -d1 / b1. Подставим полученное для x1 выражение во второе уравнение системы (8)
a2(a1x2 + b1) + b2x2 + c2x3 = d2.
Представим это уравнение в виде x2 = a2x3 + b2, где a2 = -с2 / (b2 + a2a1) и b2 = (d2 - a2b1) / (b2 + a2a1). Полученное для x2 выражение подставим в третье уравнение системы (8) и т.д.
На i-м шаге (1 < i < n) процесса i-е уравнение системы принимает вид
xi = aixi+1 + bi, (9)
где ai = -сi / (bi + aiai-1) и bi = (di - aibi-1) / (bi + aiai-1).
На последнем n-м шаге подстановка в последнее уравнение системы (8) выражения xn-1 = an-1xn + bn-1 дает уравнение an(an-1xn + bn-1) + bnxn = dn, из которого можно определить значение xn = bn = (dn – anbn-1) / (bn + anan-1).
Значения остальных неизвестных xi (i = n-1, n-2, ..., 1) легко вычисляются по формуле (9).
Таким образом, алгоритм прогонки, подобно методу Гаусса, включает два этапа – прямой ход (прямая прогонка) и обратный ход (обратная прогонка).
Прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов
ai (i = 
) и bi (i = 
).
При i = 1 эти коэффициенты вычисляются по формулам:
a1 = -с1 / g1; b1 = -d1 / g1; g1 = b1.
Для i = 
используются следующие рекуррентные формулы:
ai = -сi / gi; bi = (di - aibi-1) / gi; gi = bi + aiai-1.
Прямая прогонка завершается при i = n:
bn = (dn – anbn-1) / gn; gn = bn + anan-1.
Обратный ход метода прогонки позволяет вычислить значения неизвестных. Сначала полагают xn = bn. Затем в обратном порядке по формуле (9) определяют значения неизвестных xn-1, xn-2, ..., x1.
Свойства метода прогонки. Трудоемкость метода прогонки оценивается примерно как 8n арифметических операций, что существенно меньше метода Гаусса. Существование решения системы (8) и его единственность гарантируются при выполнении достаточных условий, задаваемых следующей теоремой.
Теорема [2]. Пусть коэффициенты системы (8) удовлетворяют следующим неравенствам
ïbkï³ïakï+ïckï; ïbkï>ïakï; k = , где a1 = 0; bn = 0. Тогда gi ¹ 0 и ïaiï£
1 для всех i =
Заметим, что при всех gi ¹ 0 вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей не обратится в нуль). Одновременно все коэффициенты ai, такие, что ïaiï£ 1, обеспечивают устойчивость по входным данным этапа обратной прогонки по формуле (9).
Похожие работы
... . При этом собственно нахождение обратной матрицы – процесс достаточно трудоемкий и его программирование вряд ли можно назвать элементарной задачей. Поэтому на практике чаще применяют численные методы решения систем линейных уравнений. К численным методам решения систем линейных уравнений относят такие как: метод Гаусса, метод Крамера, итеративные методы. В методе Гаусса, например, работают над ...
... 35437 x4=0.58554 5 x1=1.3179137 x2=-1.59467 x3=0.35371 x4=0.58462 6 x1=1.3181515 x2=-1.59506 x3=0.35455 x4=0.58557 5. Сравнительный анализ различных методов численного дифференцирования и интегрирования 5.1 Методы численного дифференцирования 5.1.1 Описание метода Предположим, что в окрестности точки xiфункция F (x) дифференцируема достаточное число раз. ...
... на языке Turbo Pascal 7.0 для решении систем линейных алгебраических уравнений, используя метод простой итерации. 1.2 Математическая формулировка задачи Пусть А – невырожденная матрица и нужно решить систему где диагональные элементы матрицы А ненулевые. 1.3 Обзор существующих численных методов решения задачи Метод Гаусса В методе Гаусса матрица СЛАУ с помощью равносильных ...
... числа). Далее по формулам (2) последовательно находятся xn-1 , xn-2 ,…, x1 при i=n-1, n-2,...,1 соответственно. Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки, сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов δi, λiпо формулам (3) при i=1,2,…,n (прямая прогонка) и затем неизвестных xi по ...
0 комментариев