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

Для решения систем алгебраических уравнений, которые могут быть представлены в виде (31), разработан специальный метод, называемый методом прогонки. Решение системы (31) ищется в виде

yi =αi yi+1 +βi	(i = 0,1,...,n −1)	(32)
где αi и βi - неизвестные прогоночные коэффициенты.
Запишем это уравнение для i=0:
y0 =α0 y1	+ β0	(33)

Приведём первое уравнение системы (31) к виду (32):

	y0	=	B0	y1 +	−f0	(34)
			C0		C0

Сравнивая уравнения (33) и (34) получим

α0 =	B0	;	β0 = −	f 0	.	(35)
	C 0
				C 0

Рассматривая остальные уравнения системы (31) получим общие рекуррентные формулы для коэффициентов αi и βi.

αi	=		Bi	; βi =	βi	−1 Ai − f i	(i =1,2,.., n).	(36)
		C i	−αi −1 Ai		C i
						−αi −1 Ai

Запишем систему уравнений, состоящую из последнего уравнения системы (31) и уравнения (32) для i = n-1.

An yn−1 − C n yn = fn ,

yn−1 = αn−1 yn + βn−1 (37)

Решая систему (37) находим выражение для yn:

yn =	An βn−1 − fn	= βn .	(38)
	Cn − Anαn−1

Определив значение βn, по формулам (32) находим в обратном порядке решение системы (31):

y I − 1 = α i − 1 y i + β i − 1 ( i = n , n − 1 , ..., 1 )

(39)

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

11

-Y 0	+Y 1
Y 0	-2Y 1	-Y
	Y 1	-Y
		Y2

2

2+Y 3

-2Y 3 -Y

Y 3 -Y

4

4

=-2

=1

=-5

=3

=-5

Матрица А для этой системы имеет следующий вид

-1	1	0	0	0		-2
1	-2	-1	0	0		1
0	1	-1	1	0		-5
0	0	1	-2	-1		3
0	0	0	1	-1		-5

Прямой ход метода прогонки

С0=1; B0=1; f0=-2

α0

=

B0

= 1

=1;

β0

= −

f0

= −

−2

= 2.

C 0

1

C 0

1

αi

=

Bi

; βi

=

βi−1 Ai

− f i

(i =1,2,.., n).

C i

−αi −1 Ai

C i −αi −1 Ai

Реализация метода прогонки в среде программы MS Excel Постановка задачи

Рассмотрим процедуру применения этой методики для решения конкретной краевой задачи. Определим конкретную форму уравнения

(1), задав формулы для вычисления его коэффициентов:

p( x ) =	−2			; q( x ) =	−12	;	f ( x ) =	3x +1		.	(40)
	2x +	1			2				2
					( 2x +1)			( 2x +1)
и граничные условия
x0 = 2, xk =6 , y( 2 ) =Y0 = 4							и y( 6 ) =Yk		= 8.		(41)

Запишем рассматриваемый пример при n равном 5. Таким образом, число узлов сетки равно 6, а формат системы соответствует

(30).

Как уже отмечено выше, в рассматриваемом нами случае системы (30), если следовать традиционной записи, использованной в (31), значение А0 = 0, С0 =-1, а значение В0 =0. Аналогично для последнего уравнения имеем значение Аn = 0 и Сn =-1, Вn =0.

12

Рассмотрим последовательность шагов решения на примере уравнения (20) с учетом (32), (33), приведенных выше.

Для того чтобы обеспечить в дальнейшем наглядность и понятность вычислений, заполним таблицу значениями функций p(x), q(x) и f(x), вычисленными в узловых точках при n=5. Для определения значения h выполним на листе Excel следующие операции (рис.6.3):

▬в ячейки А1, С1, Е1 и G1 введём комментарии: 'Х0=', 'Хk=', 'n=' и 'h=',

▬в ячейку В1 введем значение аргумента Х0 равное 2,

▬в ячейку D1 введем значение аргумента Хk равное 6,

▬в ячейку F1 введем значение аргумента n равное 5,

▬в ячейку H1 введем формулу "=(D1-B1)/F1"2, определяющую значение шага между узлами формируемой сетки как

h = xk −n x0 .

Рис. 6.3

▬ В ячейках второй строки таблицы оформим заголовок таблицы так, как это показано на рис. 6.3.

Определив основные параметры таблицы, заполним столбцы значениями в соответствии с заголовком таблицы, показанным на рис. 6.3. Для этого выполним следующие действия:

1.В ячейки А3:А8 введём индексы строк. Для этого в ячейку А3 введём цифру 0 – индекс первого узла. Переводим УМ3 в правый нижний угол ячейки А3, ФЛКМ и, зафиксировав клавишу Ctrl, протянем УМ от ячейки А3 до ячейки А8.

2.В ячейку B3 вводим ссылку на ячейку с начальным значением

аргумента Х0: "=В1". Значение ссылки формируется, если

2) Формулы вводятся в ячейки таблиц, начиная с символа “=” (равно). Двойные кавычки использованы в тексте для выделения формулы. Вводить их в ячейки таблицы не нужно.

3) Терминология и сокращения, используемые в тексте методических указаний, приведены в начальном разделе методических указаний к первой лабораторной работе:[5].

13

подвести УМ к ячейке, на которую делается ссылка и сделать

ЩЛК.

3.Заполняем ячейки столбца В, выполняя вычисление значений аргумента х в соответствии с формулой

xi+1 = xi + h ( i =0,1, ... , n −1 ).

Для этого в ячейку B4 вводим формулу "=В3+$H$1", которую протягиваем до ячейки B8, в которой достигается значение равное значению xn = Хk. (Для формирования абсолютной ссылки на ячейку Н1 после ЩЛК по ячейке Н1 следует нажать функциональную клавишу F4).

4.В ячейках от C3 до C8 вычисляем значения вспомогательной

функции 1/(2 хi + 1), входящей в знаменатели функций p(x), q(x) и f(x). Вводим в C3 формулу "=1/(2*B3+1)" и протягиваем эту формулу до ячейки C8;

Рис. 6.4.

5.В ячейки D3, E3 и F3 записываем формулы, соответствующие (32), для вычисления значений функций p(x), q(x) и f(x). Запись этих формул при вводе их в ячейки таблицы имеет следующий вид: "=- 2*C3", "= -12*C3*C3" и "=(3*B3+1)*C3*C3" соответственно.

При протягивании этих формул по столбцам D, Е и F до восьмой строки таблица заполняется так, как показано на рис. 6.4.

6.Далее начинаем заполнение столбцов G, H, I и J значениями

коэффициентов Ai, Ci, Bi и Fi в соответствии с форматом системы уравнений (30). В ячейки G3, H3, I3 записываем значения,

определяемые форматом первого уравнения системы (30): A0=0, C0=-1, В0=0. В ячейку J3 записываем ссылку на ячейку J1, в которой записано начальное значение F0=Y0: "=J1".

14

7.В ячейки G8, H8, I8 записываем значения, определяемые

конечными условиями A5=0, C5=-1, В5=0. В ячейку J8 записываем ссылку на ячейку L1, в которой записано начальное значение

Fk= F5 = Yk :"=L1".

8.Далее заполняем столбцы G, H, I и J значениями коэффициентов

Ai , Ci , Bi и Fi. В ячейку G4 вводим формулу "=1-D4*$H$1/2", соответствующую формуле

A i =1 − p(x i ) h2

для вычисления коэффициента A1. После чего протягиваем эту формулу до ячейки G7.

9.Аналогично в ячейку Н4 вводим формулу для вычисления

коэффициента С1: "2-Е4*$H$1*$H$1", а в ячейку I4 вводим формулу для вычисления коэффициента B1B : "1+D4*$H$1/2",

реализуя соответствующие формулы

C i	= 2	− q(x i ) h 2; B i =1+ p(x i )	h
			2

Протягиваем эти формулы до ячеек Н7 и I7.

10.В ячейках столбца J формируем вектор правых частей системы

уравнений (30). В ячейку J4 вводим формулу “=F4*$H$1*$H$1”, соответствующую формуле Fi = fih2. Протягиваем эту формулу до ячейки J7. В результате получаем таблицу, показанную на рис. 6.5. Следует отметить, что в столбцах G, H, I и J этой таблицы записаны элементы матрицы, решаемой системы уравнений (30).

Рис. 6.5.

11.Используя вычисленные значения коэффициентов Ai, Ci, Bi и Fi, находим в соответствии с формулами (37) и (38) значения

коэффициентов αi и βi. В ячейку K3 запишем формулу для вычисления α0 : "=I3/H3", а в ячейку L3 формулу для вычисления β0.: "=-J3/H3". И далее в ячейки K4 и L4 вводим формулы, соответствующие (38), для вычисления коэффициентов

15