|
С1 т Х т = У и
+ • • • +
<*№
+ . . . + а‘% = Z'1',
(
5
)
аых
«-т2Л2+
“Ь
йт/Х/
+
О'тт.Хп
= / !
и»
Здесь обозначено
aij
—
Q-Ц
Ci/&iu
/I1'
У
1^4 у
Матрица системы (5) имеет вид
'1
С12
С
1
т
0
а {1)
а22
а(1)
w2
т
0
а {1)
u/n2
.
а(1)
• * ц/лт
(
6
)
.Матрицы такой структуры принято обозначать так:
1
X .... X
0
X .... X
0
X ..•. X
где крестиками обозначены ненулевые элементы. В системе (5) не
известное х, содержится только в первом уравнении, поэтому в
дальнейшем достаточно иметь дело с укороченной системой урав
нений
flM*2 + . . . +
d^Xj
+ . . . +
а^тХт.
=
ail)x
ит2л2
+
+
Omi*
~f"
Q/nniXm ’
.fW
-
m •
(
7
)
Тем самым мы осуществили первый шаг метода Гаусса. Если
,аМфО,
то из системы (7) совершенно аналогично можно исклю
чить неизвестное х2 и прийти к системе, эквивалентной (2) и имею
щей матрицу следующей структуры:
1 X X . ..
X "
0 1
X . . .
X
0 0
X . . .
X
0 0
X . . .
х _
При этом первое уравнение системы (5) остается без изменения.
50
Исключая таким же образом неизвестные
х3, xt, . . . , хт,
придем
окончательно к системе уравнений вида
xi
ci
2x2
+ • • • +
с1тхт
—
уъ
Х
2
I • ■
• "1'
С2тХт
У
21
х т
—1
“1“
Ст—
1
, т х т — У
-
1
,
эквивалентной исходной системе (2).
Матрица этой системы
хт
—
Утп
|
с =
—1
C12
•
C\m
0 1
• c2,m-i
C2m
0 0
1
0 0
• • •
0
1
(
8
)
(9>
содержит нули всюду ниже главной диагонали. Матрицы такого
вида называются
верхними треугольными матрицами. Нижней тре
угольной
называется такая матрица, у которой равны нулю все
элементы, расположенные выше главной диагонали.
Получение системы (8) составляет
прямой ход метода Гаусса.
Обратный ход
заключается в нахождении неизвестных
хи х2, . ■
.,
х
„,
из системы (8). Поскольку матрица системы имеет треугольный:
вид, можно последовательно, начиная с
хт,
найти все неизвестные.
Действительно,
хт = ут,
хт _,
и т. д. Общие формулы.'
обратного хода имеют вид
x i = y i—
2
Ciixh i = m —
1........ 1,
х.п = ут.
(10)
/=г
+1
2.
Расчетные формулы. При реализации на ЭВМ прямого хода
метода Гаусса нет необходимости действовать с переменными
Xi, х2,
. . . ,
хт.
Достаточно указать алгоритм, согласно которому ис
ходная матрица
А
преобразуется к треугольному виду (9), и ука
зать соответствующее преобразование правых частей системы. По
лучим эти общие формулы. Пусть осуществлены первые
k
— 1 ша
гов, т. е. уже исключены переменные
х и х2,
. . . ,
xh~i.
Тогда имеем
систему
Х 1
~Т
C l2X 2
~f" • • • ~Г
CykX k
+
С1 т х т
—
У и
Х2~^~
• • ■ +
C2kXk
+ . . . +
С2тХт.
=
Угл
x k—
\
Ck—
i,kx k
Ск-\,тх т — Ук- i »
..
+ C & 1)xm = f t 1\
I
п
_f<*-D
• • Т"
и т т
Лт
■
— / т
atk 1)xk
+ .
U-mk xk
+
(И)
51
Рассмотрим 6-е уравнение этой системы
п{к~1)у,Л.
Л-п{к~1К
U-kk
Jt* —
f—
. . . “Г
а к т Х , п =
f k
и предположим, что
а£-1) =£
0. Поделив обе части этого уравнения на
йй-11» получим
%h
"b^/t.ft+i-^A+i “Ь
l/ht
(12)
где
Ckj=
,
j
= 6 + 1, 6 + 2, . . .
< “L)
f t *
Ук —
----- .
akk
, m,
Далее, умножим, уравнение (12) па
и вычтем полученное со
отношение из t'-ro уравнения системы (11), где t' = 6 + 1, 6 + 2, . . . ,
т.
В результате последняя группа уравнений системы (11) примет вид
X k
+
Ck,k+lx k + l
+ ■
• • +
CkmXm — У к
,
йй+1,£+1^>6+1 “Ь • • • "Ь
Gk+i,m Xm = = :f k + it
где
л < +
у
_
1
_
4
-
п {к)
у
— f (&)
“ т ,я + 1 Л/г+1
1
• • • “Т"
и т т Л т
— /
т
»
afi = at r i) ~ аТк1)сЫ'
Г / = 6 + 1 , 6 + 2, . . . .
т,
f?' = f t * ~ a t % , i
= 6 + 1, 6 + 2, . . . ,
т.
Таким образом, в прямом ходе метода Гаусса коэффициенты
уравнений преобразуются по следующему правилу:
a f , = a ki,
6, /' = 1, 2, . .
т,
Сц —
—
-j
-— , / = 6 + 1, 6 + 2,
. . . , т,
6 = 1 , 2 .......
т,
(13)
л(к—
1)
akk
of' — atj~*
(14)
i,
/' = 6+1, 6 + 2, . . . ,
m,
6 = 1, 2, . . . ,
m—
1.
Вычисление правых частей системы (8) осуществляется по фор
мулам
/10, = /ь
=
Л = 1, 2
........
т,
(15)
f t ]
=
/ f ' 1’
-
4 ' V / - 6 + 1, 6 + 2
------
т.
(16)
Коэффициенты
Сц
и правые части
y h i=
1, 2, . . . ,
т, j — i+1,
/ + 2, ...
52
. . . , m, хранятся в памяти ЭВМ и используются при осуществлении
обратного хода по формулам (10).
Основным ограничением метода является предположение о
том, что все элементы
на которые проводится деление, от
личны от нуля. Число
называется
ведущим элементом на k -м
шаге исключения.
Даже если какой-то ведущий элемент не равен
нулю, а просто близок к нему, в процессе вычислений может проис
ходить сильное накопление погрешностей. Выход из этой ситуации
состоит в том, что в качестве ведущего элемента выбирается не
ДиТ1',
а другое число (т. е. на
k-м
шаге исключается не
xk,
а дру
гое переменное
xh j=£k).
Наиболее последовательно такая страте
гия выбора ведущих элементов осуществлена в методе Гаусса с вы
бором главного элемента (см. § 3).
3. Подсчет числа действий. Подсчитаем число арифметических
действий, необходимых для решения системы (2) с помощью мето
да Гаусса. Поскольку выполнение операций умножения и деления
на ЭВМ требует гораздо больше времени, чем выполнение сложе
ния и вычитания, ограничимся подсчетом числа умножений и де
лений. Читатель по аналогии может самостоятельно найти требуе
мое число действий сложения и вычитания.
1. Вычисление коэффициентов
ckj, k = \,
2, .. .,
m, j = k + l ,
k + 2,
. . . ,
m,
по формулам (13) требует
S ( « - * ) = 1 + 2 + . . . + ( m - l ) = - - ^ P ^
h=i
делении.
2. Вычисление всех коэффициентов
af)
по формулам (14) тре
бует
У
(m —
k f
= I2 + 22 + . . . + (т — I)2 = (- — ^-т(— — -
6
умножений.
Таким образом, вычисление ненулевых элементов сч треуголь
ной матрицы
С
требует
Do'stlaringiz bilan baham: |
