ВУЗ:
Составители:
52
a
i1
x
1
+a
i2
x
2
+…+a
iN
x
N
=f
i
, i=2, 3,…, N. (4)
Умножим уравнение (3) на a
i1
, где i – любое из чисел 2, 3,…, N, и вычтем полученное
уравнение из I-го уравнения (4):
(a
i2
-a
i1
b
12
)x
2
+…+(a
iN
-a
i1
b
1N
)x
N
=f
i
-a
i1
ϕ
1
, i=2, 3,…, N.
Вводя обозначения
,,
11
)1(
11
)1(
ϕ
iiijiijij
affbaaa −=−= i, j=2, 3,…, N, (5)
перепишем полученную систему уравнений (эквивалентную системе (1)) в виде
x
1
+b
12
x
2
+…+b
1N
x
N
=
ϕ
1
,
,...
)1()1(
2
)1(
2 iNiNi
fxaxa =++ i=2, 3,…, N.
Первый столбец матрицы этой системы состоит из нулей, кроме первого элемента, равного
единице при i=j=1.
Второй шаг состоит в исключении x
2
из системы
....
..................................
,...
)1()1(
2
)1(
2
)1(
2
)1(
22
)1(
22
NNNNN
NN
fxaxa
fxaxa
=++
=++
(6)
Для этого разделим первое уравнение на
)1(
22
a :
x
2
+b
23
x
3
+…+b
2N
x
N
=
ϕ
2
,
,,...,3,/,/
)1(
22
)1(
22
)1(
22
)1(
22
Njaabaf
jj
===
ϕ
умножим его затем на (-
)1(
2i
a ) и сложим с уравнением
.,...,4,3,...
)1()1(
3
)1(
32
)1(
2
Nifxaxaxa
iNiNii
==+++
В результате получим систему
x
2
+b
23
x
3
+…+b
2N
x
N
=
ϕ
2
, (7)
.,...,4,3
,,
,...
2
)1(
2
)1()2(
2
)1(
2
)1()2(
)2()2(
3
)2(
3
Ni
affbaaa
fxaxa
iiijiijij
iNiNi
=
−=−=
=++
ϕ
(8)
Для x
3
, x
4
,…, x
N
имеем систему (N-2)-го порядка, аналогичную системе (6) (N-1)-го порядка
для x
2
, x
3
,…, x
N
.
Продолжая рассуждения, после (N-1)-го шага (т.е. после исключения x
1
, x
2
,…, x
N-1
) получим
,
)1()1( −−
=
N
NN
N
NN
fxa
или x
N
=
ϕ
N
,
./
)1()1( −−
=
N
NN
N
NN
af
ϕ
(9)
В итоге приходим к системе (2) с верхней треугольной матрицей:
.
,
..........................................
,...
,...
1,11
223232
113132121
NN
NNNNN
NN
NN
x
xbx
xbxbx
xbxbxbx
ϕ
ϕ
ϕ
ϕ
=
=+
=+++
=++++
−−−
(10)
Обратный ход метода Гаусса состоит в определении всех x
i
из системы (10) с верхней
треугольной матрицей. Нетрудно показать, что изложенный выше метод Гаусса можно применять
в том случае, когда все главные миноры матрицы отличны от нуля.
Подсчитаем число умножений и делений в методе Гаусса. Рассмотрим сначала прямой
ход. На первом шаге требуется Q
1
=N
2
делений и умножений, второй шаг требует Q
2
=(N-1)
2
действий и т.д. Всего надо сделать N шагов прямого хода, затратив на это
∑∑
==
++==+−
N
k
N
s
NNNskN
11
22
6/)12)(1()1(
умножений и делений. Для обратного хода,
очевидно, нужно сделать N(N-1)/2 умножений. Таким образом, для решения системы уравнений
(1) требуется Q=N(N
2
+3N-1)/3 умножений и делений. Примерно столько же потребуется
сложений.
Рассмотрим в качестве примера систему трех уравнений
52
ai1x1+ai2x2+…+aiNxN=fi, i=2, 3,…, N. (4)
Умножим уравнение (3) на ai1, где i – любое из чисел 2, 3,…, N, и вычтем полученное
уравнение из I-го уравнения (4):
(ai2-ai1b12)x2+…+(aiN-ai1b1N)xN=fi-ai1ϕ1, i=2, 3,…, N.
Вводя обозначения
aij(1) = aij − ai1b1 j , f i (1) = f i − ai1ϕ1 , i, j=2, 3,…, N, (5)
перепишем полученную систему уравнений (эквивалентную системе (1)) в виде
x1+b12x2+…+b1NxN=ϕ1,
ai 2 x2 + ... + aiN(1) x N = f i (1) , i=2, 3,…, N.
(1)
Первый столбец матрицы этой системы состоит из нулей, кроме первого элемента, равного
единице при i=j=1.
Второй шаг состоит в исключении x2 из системы
(1)
a22 x2 + ... + a2(1N) x N = f 2(1) ,
.................................. (6)
a x + ... + a
(1)
N2 2
(1)
NN xN = f (1)
N .
(1)
Для этого разделим первое уравнение на a 22 :
x2+b23x3+…+b2NxN=ϕ2,
ϕ 2 = f 2(1) / a 22
(1)
, b2 j = a 2(1j) / a 22
(1)
, j = 3,..., N ,
умножим его затем на (- ai(21) ) и сложим с уравнением
ai(21) x2 + ai(31) x3 + ... + aiN(1) x N = f i (1) , i = 3,4,..., N .
В результате получим систему
x2+b23x3+…+b2NxN=ϕ2, (7)
ai(32) x3 + ... + aiN( 2 ) x N = f i ( 2) ,
aij( 2) = aij(1) − ai(21) b2 j , f i ( 2 ) = f i (1) − ai(21)ϕ 2 , (8)
i = 3,4,..., N .
Для x3, x4,…, xN имеем систему (N-2)-го порядка, аналогичную системе (6) (N-1)-го порядка
для x2, x3,…, xN.
Продолжая рассуждения, после (N-1)-го шага (т.е. после исключения x1, x2,…, xN-1) получим
( N −1)
a NN x N = f N( N −1) , или xN=ϕN, ϕ N = f N( N −1) / a NN
( N −1)
. (9)
В итоге приходим к системе (2) с верхней треугольной матрицей:
x1 + b12 x2 + b13 x3 + ... + b1N x N = ϕ1 ,
x2 + b23 x3 + ... + b2 N x N = ϕ 2 ,
.......................................... (10)
x N −1 + bN −1, N x N = ϕ N −1 ,
xN = ϕ N .
Обратный ход метода Гаусса состоит в определении всех xi из системы (10) с верхней
треугольной матрицей. Нетрудно показать, что изложенный выше метод Гаусса можно применять
в том случае, когда все главные миноры матрицы отличны от нуля.
Подсчитаем число умножений и делений в методе Гаусса. Рассмотрим сначала прямой
ход. На первом шаге требуется Q1=N2 делений и умножений, второй шаг требует Q2=(N-1)2
действий и т.д. Всего надо сделать N шагов прямого хода, затратив на это
∑ ( N − k + 1) 2 = ∑s =1 s 2 = N ( N + 1)(2 N + 1) / 6 умножений и делений. Для обратного хода,
N N
k =1
очевидно, нужно сделать N(N-1)/2 умножений. Таким образом, для решения системы уравнений
(1) требуется Q=N(N2+3N-1)/3 умножений и делений. Примерно столько же потребуется
сложений.
Рассмотрим в качестве примера систему трех уравнений
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
