Решение систем линейных уравнений

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

x = β + α x ,

(2.10)

α

α

K α

x

α

11

12

1n

1

1

α 21

α 22

K α 2n

x2

α 2

где α =

K

K

K K

,

x = K

,

β = K

.

α n1

α n2

α n

K α nn

xn

Предположим, что известно грубое приближенное решение этой системы, обозначим его x 0 . Пусть это будет, например, столбец сво-

бодных членов x0 = β . Подставив это нулевое приближение в (2.10), вычислим новые значения

x1 = β + α x0 .

(2.11)

Это есть первая итерация. Далее x0 заменяется на x1 и вычисляется следующее приближение, и так далее: k-ое приближение будет вычисляться по формуле:

xk = β + α xk −1

(2.12)

или в развернутом виде для системы (2.12) из n уравнений с n неизвестными ( aii ≠ 0 для всех i = 1, ..., n ) k-ое приближение будет задаваться формулой:

	n
xik = β i + ∑α i, j x kj −1 ,		(i = 1, K, n ; k = 1, 2,K) . ,
	j =1
Вообще	говоря, если	последовательность приближений
x0 , x1, x 2 ,K, x k	имеет предел

x = lim x k , k →∞

то этот предел и есть решение системы.

41

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

На практике итерационный процесс прекращают, когда выполняется условие:

max xik − xik −1 < ε ,

где определяется максимальное значение разности для всех i, а ε –заданная точность.

Условие сходимости метода итераций: модули диагональных коэффициентов матрицы A для каждого уравнения системы должны быть больше суммы модулей всех остальных коэффициентов, не считая свободных членов, т.е.

n

aii > ∑ aij для i = 1, 2, K, n

j =1 (i ≠ j )

или по-другому

max i

	n
	∑			aij
	j=1
(i≠ j)							< 1.
		aii

На рис. 2.5 представлен блок проверки неравенства нулю диагональных элементов и блок проверки условия сходимости метода итераций для данной системы. На рис. 2.6 – блок подсчета коэффициентов βi и αij преобразованной системы (2.10). На рис. 2.7 – блок на-

хождения неизвестных системы (2.12), а значит и исходной системы

(2.7).

42

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

Рис. 2.5 – Блок «Проверка неравенства нулю диагональных элементов» и блок «Проверка условия сходимости»

43

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

Рис. 2.6 – Блок «Подсчет коэффициентов βi и αij »

44

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

Рис. 2.7. Блок «Нахождение решения системы»

45

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

2.4.МЕТОД ПРОГОНКИ

Метод прогонки применяется для решения систем линейных

уравнений с трехдиагональными матрицами вида:

a11x1 +			a12 x2
a	21	x +	a	22	x	2	+	a	23	x
		1								3
			a32 x2 + a33x3 + a34 x4
										K
										ann−1xn−1 + ann xn

=b1

=b2

=b3 (2.13)

=bn

Матрица A этой системы имеет вид:

a		a	0	0	0
	11	12
a21		a22	a23	0	0
A =	0	a32	a33	a34	0		(2.14)
			K
	0	0	0	ann−1
					ann

Из первого уравнения системы (2.13) вычислим x1:

x = α		x		+ β		, где	α		= −	a12	,	β		=	b1	.
	1		2		1			1					1
1										a11					a11

Подставим полученное выражение для x1 во второе уравнение системы (2.13), найдем x2

x2 = α 2 x3 + β 2 , α 2 = −	a23	, β 2	=	b2 − a21β 1	.
	a22 + a21α 1
				a22 + a21α 1

46

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

Выполняя последовательно эти действия, на i-ом шаге получим:

	x i = α i xi+1 + β i , α i = −	a i,i+1	,	β i =	bi − ai, i−1	β i−1	(2.15)
		a i,i + a i, i−1α i−1			a i,i + a i,i−1α i−1

Если в последнее уравнение системы (2.13) подставить xn-1, вычисленное по формулам (2.15), то можно получить уравнение для вычисления xn.

	an,n−1	(α n−1 xn + β n−1 ) + an,n xn = bn , xn =	bn − an,n−1	β n−1	.
			an,n−1α n−1 + an,n

Значения остальных неизвестных легко находятся по формулам (2.15). Метод прогонки является двухпроходным. На прямом проходе вычисляются коэффициенты αi и βi , а на обратном неизвестные xi.

На рис. 2.8 представлена блок-схема алгоритма метода прогон-

ки.

47

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

Рис. 2.8. Блок-схема метода прогонки

48

Составители: БикмеевА.Т., КарчевскаяМ.П., КузьминаЕ.А., РамбургерО.Л..

2.5.РЕКОМЕНДАЦИИ ПО ВЫБОРУ МЕТОДА РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

Для практических вычислений и прямые и итерационные методы имеют свои преимущества и недостатки.

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

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

49