Метод прогонки

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

Приведем несколько задач, которые приводят к подобным матрицам.

Пример 1. Арбузы.

На прилавке в ряд лежат арбузы, причем вес каждого арбуза, кроме крайних, ровно на 0.1 кг легче, чем полусумма весов двух соседних с ним арбузов. Зная веса крайних арбузов и их количество, найти веса всех арбузов.

Матрица для системы уравнений в этой задаче, при 8 арбузах и весах крайних арбузов 10 и 15.6 кг, будет иметь вид:

Пример 2. Последовательность Фибоначчи.

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

Для К=10 и значениях первого и 10-го члена последовательности 1 и 4 соответственно, получаем систему уравнений с матрицей:

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

В общем случае, система с трехдиагональной матрицей имеет вид:

d₁x₁ + e₁x₂ = b₁
c₂x₁ + d₂x₂ + e₂x₃ = b₂
c₃x₂ + d₃x₃ + e₃x₄ = b₃
.........
c_n-1x_n-2 + d_n-1x_n-1 + e_n-1x_n = b_n-1
c_nx_n-1 + d_nx_n = b_n

Для решения подобных систем разработан чрезвычайно быстрый специальный метод решения, который и носит название «Метод прогонки». Поясним его суть.

Оказывается, что если знать значение второй переменной, то через него легко выразить значения всех остальных переменных, вычисляя их последовательно: первую неизвестную находим из первого уравнения, по первой и второй неизвестной находим значение третьей переменной из второго уравнения, затем по второй и третьей неизвестной находим четвертую и т.д. Поэтому суть метода прогонки заключается в том, что мы обозначаем значение второй неизвестной (через t, например), затем выражаем через нее последовательно все остальные неизвестные. Дойдя до последнего уравнения, мы получаем условие, из которого и находим значение t. Во время второго прохода, зная значение t, мы получаем значение всех неизвестных.

Например, во втором примере, если X₂=t, то X₃=t+1, X₄=2t+1, X₅=3t+2, X₆=5t+3, X₇=8t+5, X₈=13t+8, X₉=21t+13, X₁₀=34t+21=4, откуда t=-0, 5 и получаем последовательность

1 -0, 5 0, 5 0 0, 5 0, 5 1 1, 5 2, 5 4.

Вопрос. При каком значении Х₂ последовательность Фибоначчи, начинающаяся с 1 будет ограничена? (Это важное в математике, искусстве и архитектуре положительное число носит название «золотое сечение»).

Упражнение. Решите методом прогонки систему из первого примера. (Ответ t =10.2).

Обратим внимание на два существенных обстоятельства:

· во-первых, трудоемкость описанного алгоритма решения системы имеет порядок N;

· во-вторых, все неизвестные выражаются через t линейным образом.

Первое соображение подчеркивает важность данного метода для практических расчетов.

Учитывая второе соображение, заведем два массива и , при этом значения переменных будут выражаться через t по формулам: .

По определению, , а из первого уравнения имеем: .

(В случае, если d₁=0, то за переменную t можно взять значение не X₂, а X₁).

Все остальные коэффициенты находятся по рекуррентным формулам, получающимся из уравнения: или откуда при i=2, 3, …, n-1.

Дойдя до конца, мы получаем из последнего уравнения условие для нахождения t:

или , откуда

.

Далее, имея значение t и формулы, по которым все неизвестные через него выражаются, находим все значения неизвестных: при i =1, 2, 3, …, n.

Заметим, что метод прогонки можно применять, если нигде в формулах знаменатели не равны нулю. В частности, если определитель системы равен 0, то есть задача некорректна, то мы не сможем однозначно определить значение t. Это означает, что в последнем уравнении выражение, стоящее в знаменателе, должно обращаться в ноль.

Контрольные вопросы

1. Каково условие применимости метода прогонки в классическом варианте?

2. В чем суть метода прогонки?

3. Какова трудоемкость метода? Сравните количество вычислений с остальными методами решения систем линейных алгебраических уравнений.

4. Как изменится метод, если количество ненулевых диагоналей равно 4? 5?

5. Что будет, если применять метод прогонки для вырожденных систем? Как при выполнении программы следить, не является ли рассматриваемая система вырожденной?

Содержание лабораторной работы.

1. Составьте процедуру чтения из файла матрицы системы и вывода ее на экран. Формат входного текстового файла: в первой строке одно натуральное число N (не более 20) – порядок матрицы. В последующих N строках через пробел расположены по N элементов соответствующей строки, а после них свободный коэффициент данного уравнения.

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

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

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

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

Варианты заданий:

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.
11.	12.
13.	14.
15.	16.
17.	18.