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


Download 1.85 Mb.
Pdf ko'rish
bet107/111
Sana19.11.2023
Hajmi1.85 Mb.
#1786905
TuriУчебное пособие
1   ...   103   104   105   106   107   108   109   110   111
Bog'liq
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев

i
i
im m
i
a x
a x
a x
f
i
m
+
+…+
=
=

. (6.6) 
Умножим (6.4) на a
i1
и вычтем полученное уравнение из i-го уравнения 
системы (6.6), i=2,…,m. В результате получим следующую систему уравне-
ний: 
1
12 2
12
1
1
j
m m
x
c x
c x
c x
y
+
+…+
+ …+
=
,
( )
( )
( )
( )
1
1
1
1
22
2
2
2
2
2
j
m m
a x
a x
a x
f
+…+
+…+
=
,
.
…………………………
,
( )
( )
( )
( )
1
1
1
1
2 2
2
.
m
mj
mm m
m
a x
a x
a x
f
+…+
+…+
=
(6.7) 
Здесь введены обозначения: 
( )
( )
1
1
1
1
1
1
, ,
,
2,3, ,
ij
ij
j i
i
i
i
a
a
c a
f
f
y a
i j
m
=

= −
=

.
(6.8) 
Матрица системы (6.7) имеет вид: 
( )
( )
( )
( )
1
12
1
1
2
22
1
1
2
1
0
0
m
m
m
mm
c
c
a
a
a
a
















   


Для матриц такой структуры принято следующее обозначение: 
1
0
0
×
×




×
×






×
×






   


где символами × обозначены ненулевые элементы. В системе (6.7) 
неизвестное x
1
содержится только в первом уравнении, поэтому в 
дальнейшем достаточно иметь дело с укороченной системой уравнений 
22 / 23


207 
( )
( )
( )
( )
1
1
1
1
22
2
2
2
2
2
j
m m
a x
a x
a x
f
+…+
+…+
=

.
…………………………
,
(6.9) 
( )
( )
( )
( )
1
1
1
1
2 2
2
m
mj
mm m
m
a x
a x
a x
f
+…+
+…+
=

Тем самым мы осуществили первый шаг метода Гаусса. Если 
( )
1
22
0
a


то из системы (6.9) совершенно аналогично можно исключить неизвестное x
2
и прийти к системе, эквивалентной (2) и имеющей матрицу следующей 
структуры: 
1
,
0 1
,
0
0
.
×
×
×
×


   

При этом первое уравнение системы (6.7) остается без изменения. 
Аналогичным образом выполняется исключение неизвестных x
3
, x
4
,…, 
x
m
. В результате система уравнений приводится к виду: 
1
12 2
12
1
1
j
m m
x
c x
c x
c x
y
+
+…+
+ …+
=
,
2
2
2
2
j
j
m m
x
c x
c x
y
+…+
+ …+
=
,
.
…………………………
,
1
1,
1
m
m
m m
m
x
c
x
y



+
=
,
.
m
m
x
y
=
Матрица этой системы
(
6.10) 
1
12
2
1
0
1
0
0
1
m
m
c
c
c
C






= 









   


(6.11) 
содержит нули в элементах, расположенных под главной диагональю. Мат-
рицы такого вида называются верхними треугольными матрицами. 
Получение системы (8) составляет прямой ход метода Гаусса. Обрат-
ный ход заключается в нахождении неизвестных x
1
,x
2
,…,x
m
из системы (8). 
Поскольку матрица имеет треугольный вид, можно последовательно, начиная 
с x
m
, найти все неизвестные. Общие формулы обратного хода имеют вид 
1
, 1, ,1,
m
i
i
ij
j
m
m
j i
x
y
c x i m
x
y
= +
= −
= − …
=


(6.12) 
23 / 23


208 
При реализации в программе прямого хода метода Гаусса нет необхо-
димости работать с переменными x
1
, x
2
, …, x
m
. Достаточно указать алгоритм, 
согласно которому исходная матрица А преобразуется к треугольному виду 
(6.11), и указать соответствующие преобразования правых частей системы. 
Получим эти общие формулы. Пусть реализованы первые k-1 шагов, т.е. уже 
исключены переменные x
1
,x
2
,…,x
k-1
. Тогда имеем систему 
1
12 2
1
1
1
k k
m m
x
c x
c x
c x
y
+
+…+
+ …+
=
,
2
2
2
2
k k
m m
x
c x
c x
y
+…+
+ …+
=
,
.
…………………………
,
1
1,
1,
1
k
k
k k
k
m m
k
x
c
x
c
x
y




+
+ …+
=
,
( )
( )
( )
1
1
1
,
,
k
k
k
k k
k
k m
m
k
a
x
a
x
f



+ …+
=
,
.
…………………………
,
( )
( )
( )
1
1
1
,
,
.
k
k
k
m k
k
m m
m
m
a
x
a
x
f



+ …+
=
(6.13
)
Рассмотрим k-е уравнение этой системы: 
( )
( )
( )
1
1
1
,
,
.
k
k
k
k k
k
k m
m
k
a
x
a
x
f



+ …+
=
Предположим, что 
( )
1
,
0
k
k k
a


. Поделив обе части этого уравнения на 
( )
1
,
k
k k
a

, получим 
,
1
,
k
k k
k
k m m
k
x
c
x
c x
y
+
+
+…+
=

(6.14) 
где 
( )
( )
1
1
, 1,
2, ,
k
kj
kj
k
kk
a
c
j k
k
m
a


=
= +
+ …

( )
( )
1
1
k
k
k
k
kk
f
y
a


=

Далее необходимо умножить уравнение (6.14) на 
( )
1
k
ik
a

и вычесть полу-
ченное соотношение из i-го уравнения системы (6.13), где i=k+1,k+2,…,m. В 
результате последняя группа уравнений системы (6.13) примет вид: 
,
1
,
k
k k
k
k m m
k
x
c
x
c x
y
+
+
+…+
=
,
( )
( )
( )
1,
1
1
1,
k
k
k
k
k
k
k
m m
k
a
x
a
x
f
+
+
+
+
+ …+
=
.
…………………………
,
1 / 23


209 
( )
( )
( )
,
1
1
,
,
k
k
k
m k
k
m m m
m
a
x
a
x
f
+
+
+ …+
=
где 
( )
( )
( )
1
1
, ,
1,
2, , ,
k
k
k
ij
ij
ik
kj
a
a
a
c
i j k
k
m


=

= +
+ …
( )
( )
( )
1
1
, 1,
2,...
k
k
k
i
i
ik
k
f
f
a
y i k
k
m


=

= +
+
.
Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений 
преобразуются по следующему правилу: 
( )
0
, ,
1, 2, ,
kj
kj
a
a
k j
m
=
=
… , 
( )
( )
1
1
, 1,
2, , ,
1, 2, ,
k
kj
kj
k
kk
a
c
j k
k
m k
m
a


=
= +
+ …
=


(6.15) 
( )
( )
( )
1
1
, ,
1,
2, , ,
1, 2, ,
1
k
k
k
ij
ij
ik
kj
a
a
a
c
i j k
k
m k
m


=

= +
+ …
=
… − . 
Вычисление правых частей системы (6.10) осуществляются по форму-
лам: 
( )
( )
( )
1
0
1
, ,
1, 2, , ,
k
k
k
k
k
k
kk
f
f
f
y
k
m
a


=
=
=

(6.16) 
( )
( )
( )
1
1
, 1,
2,...
k
k
k
i
i
ik
k
f
f
a
y i k
k
m


=

= +
+
. (6.17) 
Коэффициенты c
ij
и правые части y
i
, i=1,2,..m, j=i+1,i+2,…, m, хранятся 
в памяти и используются при осуществлении обратного хода по формулам 
(6.12). 
Очевидно, что при выполнении прямого хода важным является предпо-
ложение о том, что все элементы 
( )
1
k
kk
a

отличны от нуля. Число 
( )
1
k
kk
a

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

k
kk
a
а другоечисло

В листинге 6.1 представлен метод Gauss(), который получает матрицу А 
и столбец свободных членов В и реализует прямой и обратных ход метода 
Гаусса. 

Download 1.85 Mb.

Do'stlaringiz bilan baham:
1   ...   103   104   105   106   107   108   109   110   111




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling