r:=a[i,k];

for j:=k to n+1 do a[i,j]:=a[i,j]-a[k,j]*r;

end;

end;

Обратный ход метода Гаусса (вычисление вектора значений переменных) может выглядеть так:

if s<>0 then

for i:=n downto 1 do begin s:=a[i,n+1];

for j:=i+1 to n do s:=s-a[i,j]*x[j]; x[i]:=s;

end;

Остаётся только вывести результат и сделать проверку.

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

Он является модификацией метода Гаусса для частного случая разреженных систем – системы уравнений с трехдиагональной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а также при численном решении краевых задач для диф-

ференциальных уравнений.
Запишем систему уравнений в виде
b1x1 + c1x2 = d1 ;
a2x1 + b2x2 + c2x3 = d2 ;
a3x2 + b3x3 + c3x4 = d3 ;	(8.3)
……………………………….

an-1xn-2+bn-1xn-1+cn-1xn = dn-1 ;

anxn-1 + bnxn = dn. .

На главной диагонали матрицы этой системы стоят элементы

b1, b2,...,bn, над ней – элементы c1, c2,..., cn-1, под ней – элементы a2,a3,an. При этом обычно все коэффициенты bi не равны нулю.

Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в том, что каждое неизвестное xi выражается через xi+1 с помощью прогоночных коэффициентов ai, bi:

xi=ai-xi+1+bi, i=1, 2,..., n – 1.	(8.4)
Из первого уравнения системы (8.3) найдем	x1=(–c1/b1) x2 + d1/b1.

С другой стороны, по формуле (8.4) x1=a1x2+b1.

67

Приравнивая коэффициенты в обоих выражениях для x1,получаем

a1= – c1/b1, b1=d1/b1. (8.5)

Из второго уравнения системы (8.3) выразим x2 через x3, заменяя x1 по формуле (8.4):

	a2(a1x2 + b1) + b2x2 + c2x3 = d2.
	Отсюда найдем x2 = (– c2x3 + d2 – a2b1) / (a2a1 + b2),
или	x2=a2x3 + b2 ;
	a2= – c2/e2 ;
	b2=(d2 – a2b1)/e2 ;
	e2=a2a1+b2 .
	Аналогично можно вычислить прогоночные коэффициенты для
любого номера i:
	ai = – ci/ei , bi=(di – aibi-1)/ei ;	(8.6)
	ei = aiai-1 + bi , i = 2, 3,..., n – 1 .
	Обратная прогонка состоит в последовательном вычислении неиз-

вестных xi. Сначала нужно найти xn . Для этого воспользуемся выражением (8.4) при i = n – 1 и последним уравнением системы (8.3). Запишем их:

xn-1 = an-1xn+bn-1 ; anxn-1+bnxn= dn .

Отсюда, исключая xn-1, находим xn = (dn – anbn-1)/(bn+anan-1). Далее, используя формулы (8.4) и выражения для прогоночных

коэффициентов (8.5), (8.6), последовательно вычисляем все неизвестные xn-1, xn-2, ..., x1.

8.4. Итерационные методы

Итерационные методы используют последовательные приближения (итерации, итерационные циклы), в процессе вычисления по которым образуется последовательность значений X0, X1,...,XS,..., сходящаяся к некоторому пределу XP, т. е.

lim XS=XP,

S→ ∞

где каждое последующее значение XS определяется через предыдущее XS -1 (S – номер итерации).

К таким методам относятся метод Якоби (метод простой итерации, или метод одновременных смещений), метод Зейделя (ГауссаЗейделя, или метод последовательных смещений), метод верхней релаксации.

Итерации начинаются с задания начального приближенного решения X0, которое может быть получено из физических или других разумных соображений. Чем ближе исходное приближение X0 к решению

68