Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Г
ЛАВА 
6. Н
ЕКОТОРЫЕ ЧИСЛЕННЫЕ МЕТОДЫ
 
6.1. Р
ЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ 
Г
АУССА
 
Во многих прикладных задачах возникает необходимость решения сис-
тем линейных алгебраических уравнений вида: 
,
Ax
f
=
(6.1) 
где А – матрица m
×m, x = (x
1
, x
2
,…, x
m
)
T
– искомый вектор, f = (f
1
, f
2
,…, f
m
)
T
 – 
заданный вектор. Предполагается, что определитель матрицы А отличен от 
нуля, так что решение x существует и единственно. Для большинства вычис-
лительных задач характерным является большой порядок матрицы А.
Методы численного решения системы линейных алгебраических урав-
нений делятся на две группы: прямые методы и итерационные методы. Ите-
рационные методы состоят в том, что решение x системы находится как пре-
дел при n 
→ ∞ последовательных приближений x
(n)
, где n – номер итерации. 
Обычно задается малое число 
0
ε > и вычисления проводятся до тех пор, 
пока не будет выполнена оценка 
( )
n
x
x
ε
− < . 
(6.2) 
Число итераций n является функцией точности n = n(
ε). Многие итера-
ционные методы предназначены для матриц специального вида (трехдиаго-
нальные, симметричные, ленточные, большие разреженные и т. д.). 
Наиболее известными прямыми способами решения системы (6.1) яв-
ляются метод Крамера, основанный на вычислении определителей, и метод 
Гаусса, основанный на последовательном исключении неизвестных. При 
больших m первый способ требует порядка m! арифметических действий, а 
второй – только О(m
3
) действий. Поэтому метод Гаусса широко используется 
при численном решении задач линейной алгебры. Прямые методы не пред-
полагают, что матрица А имеет какой-либо специальный вид и ее порядок не 
превышает 100. 
Запишем систему (6.1) в развернутом виде 
11 1
12 2
1
1
,
m m
a x
a x
a x
f
+
+…
=
 
21 1
22 2
2
2
,
m m
a x
a x
a x
f
+
+…
=
(6.3) 
…
1 1
2 2
.
m
m
mm m
m
a x
a x
a x
f
+
+…
=
 
 
 
21 / 23

---

206 
Метод Гаусса решения системы (6.3) состоит в последовательном ис-
ключении неизвестных x
1
, x
2
,…, x
m
из этой системы. Предположим, что 
a
11
 ≠ 0. Поделив первое уравнение на a
11
, получим 
1
12 2
1
1
m m
x
c x
c x
y
+
+…+
= , 
(6.4) 
где 
1
1
1
1
11
11
, 2, , ;
j
j
a
f
c
j
m y
a
a
=
= …
=
. 
(6.5) 
Рассмотрим теперь оставшиеся уравнения системы (6.3): 
1 1
2 2
,
2,3, ,