ВУЗ:
Составители:
77
Знак определителя меняется на противоположный при перестановке его
столбцов или строк. Следовательно, значение определителя после приведения
матрицы А к треугольному виду вычисляется по формуле:
∏
=
⋅=
n
k
kk
auA
1
det
, (4.26)
где u =
а
kk
– диагональные элементы преобразованной матрицы.
Этот метод позволяет вычислять определители 100-го и большего порядков.
Блок-схема данного метода приведена на рис. 40.
4.7. Метод итераций
Этот метод позволяет уточнить решение, полученное с помощью прямого
метода.
Найдём решение системы линейных уравнений:
a
11
x
1
+a
12
x
2
+…+a
1n
x
n
=b
1
a
21
x
1
+a
22
x
2
+…+a
1n
x
n
=b
2
…………………………… (4.27)
a
n1
x
1
+a
n2
x
2
+…+a
nn
x
n
=b
n
Пусть с помощью некоторого прямого метода вычислены приближённые
значения неизвестных
)0()0(
2
)0(
1
,,,
n
xxx K
. Подставляя это решение в левые части
системы (4.27), получаем векторные значения
)0(
i
b , отличные от
i
b (i=1,2,…,n):
)0()0()0(
22
)0(
11
)0(
2
)0(
2
)0(
222
)0(
121
)0(
1
)0(
1
)0(
212
)0(
111
,
,
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
=+++
=+++
=+++
K
KKKKKKKKKKKKKKK
K
K
(4.28)
Введём обозначения:
)0(
i
ξ
- погрешности значений неизвестных,
)0(
i
r
- невязки, т.е.
)0()0(
iii
xx −=
ξ
,
)0()0(
iii
bbr −=
, i=1,2,…,n. (4.29)
Вычитая каждое уравнение системы (4.28) из соответствующего уравнения
системы (4.27), с учётом обозначений (4.29) получаем:
+1, если число перестановок четное;
-1, если число перестановок нечетное.
78
.
,
,
)0()0()0(
22
)0(
11
)0(
2
)0(
2
)0(
222
)0(
121
)0(
1
)0(
1
)0(
212
)0(
111
nnnnnn
nn
nn
raaa
raaa
raaa
=+++
=+++
=+++
ξξξ
ξξξ
ξξξ
K
KKKKKKKKKKKKKKK
K
K
(4.30)
Решая эту систему, находим значения погрешностей
)0(
i
ξ
, которые
используем в качестве поправок к решению. Следующие приближения
неизвестных имеют вид:
)0(
1
)0(
1
)1(
1
ξ
+= xx
,
)0(
2
)0(
2
)1(
2
ξ
+= xx
, …,
)0()0()1(
nnn
xx
ξ
+=
.
Таким же способом можно найти новые поправки к решению
)1(
i
ξ
и
следующие приближения переменных
)1()1()2(
iii
xx
ξ
+=
и т.д., пока все очередные
значения погрешностей (поправок)
i
ξ
не станут достаточно малыми.
Заметим, что для нахождения очередного приближения, т.е. на каждой
итерации, решаются системы уравнений вида (4.30) с одной и той же матрицей,
являющейся матрицей исходной системы (4.27) при разных правых частях. Это
позволяет строить экономичные алгоритмы. Например, при использовании
метода Гаусса сокращается объём вычислений на этапе прямого хода.
Решение системы уравнений с помощью рассмот
ренного метода, а также при
использовании других итерационных методов сводится к следующему. Вводятся
исходные данные, например коэффициенты уравнений и допустимое значение
погрешности. Необходимо также задать начальные приближения значений
неизвестных. Они либо вводятся в ЭВМ, либо вычисляются каким-либо
способом (в частности, путём решения системы уравнений с помощью прямого
метода). Затем организуется циклический вычислительный п
роцесс, условием
окончания которого является
1
max
≤≤
≤
ij
i
εξ
, (4.31)
где ε- заданная малая положительная величина (точность).
Для предотвращения непроизводительных затрат машинного времени в
алгоритм вводят счётчик числа итераций и при достижении им некоторого
заданного значения счет прекращают.
Блок-схема метода итераций приведена на рис. 41, фигурирующая в
алгоритме переменная р имеет следующий смысл, если р=0, то производится
приведение матрицы А к треугольному виду и оп
ределяются коэффициенты
преобразования правых частей системы уравнений.
Знак определителя меняется на противоположный при перестановке его a11ξ1( 0 ) + a12ξ 2( 0 ) + K + a1nξ n( 0 ) = r1( 0) ,
столбцов или строк. Следовательно, значение определителя после приведения
матрицы А к треугольному виду вычисляется по формуле: a21ξ1( 0 ) + a22ξ 2( 0 ) + K + a2 nξ n( 0 ) = r2( 0 ) , (4.30)
KKKKKKKKKKKKKKK
n
det A = u ⋅ ∏ a kk , (4.26) an1ξ1( 0 ) + an 2ξ 2( 0 ) + K + annξ n( 0 ) = rn( 0 ) .
k =1
+1, если число перестановок четное; Решая эту систему, находим значения погрешностей ξ i( 0) , которые
где u=
-1, если число перестановок нечетное. используем в качестве поправок к решению. Следующие приближения
неизвестных имеют вид:
аkk диагональные элементы преобразованной матрицы.
Этот метод позволяет вычислять определители 100-го и большего порядков. x 1(1 ) = x 1( 0 ) + ξ 1( 0 ) , x2(1) = x2( 0 ) + ξ 2( 0 ) , , x n(1 ) = x n( 0 ) + ξ n( 0 ) .
Блок-схема данного метода приведена на рис. 40. Таким же способом можно найти новые поправки к решению ξ i(1) и
следующие приближения переменных xi( 2 ) = xi(1) + ξ i(1) и т.д., пока все очередные
4.7. Метод итераций значения погрешностей (поправок) ξi не станут достаточно малыми.
Этот метод позволяет уточнить решение, полученное с помощью прямого Заметим, что для нахождения очередного приближения, т.е. на каждой
метода. итерации, решаются системы уравнений вида (4.30) с одной и той же матрицей,
Найдём решение системы линейных уравнений: являющейся матрицей исходной системы (4.27) при разных правых частях. Это
a11x1+a12x2+ +a1nxn=b1 позволяет строить экономичные алгоритмы. Например, при использовании
a21x1+a22x2+ +a1nxn=b2 метода Гаусса сокращается объём вычислений на этапе прямого хода.
(4.27) Решение системы уравнений с помощью рассмотренного метода, а также при
an1x1+an2x2+ +annxn=bn использовании других итерационных методов сводится к следующему. Вводятся
Пусть с помощью некоторого прямого метода вычислены приближённые исходные данные, например коэффициенты уравнений и допустимое значение
значения неизвестных x1( 0 ) , x 2( 0 ) , K , x n( 0 ) . Подставляя это решение в левые части погрешности. Необходимо также задать начальные приближения значений
неизвестных. Они либо вводятся в ЭВМ, либо вычисляются каким-либо
(0)
системы (4.27), получаем векторные значения bi , отличные от bi (i=1,2, ,n): способом (в частности, путём решения системы уравнений с помощью прямого
метода). Затем организуется циклический вычислительный процесс, условием
a x (0)
+ a12 x (0)
+K+ a x (0)
= b1( 0 ) ,
11 1 2 1n n
окончания которого является
a x (0)
+ a 22 x (0)
+K+ a x (0)
= b2( 0 ) , (4.28)
21 1 2 2n n
max ξ i ≤ ε , (4.31)
K K K K K K K K K K K KK K K j ≤ i ≤1
a n1 x1( 0 ) + a n 2 x 2( 0 ) + K + a nn x n( 0 ) = bn( 0 ) где ε- заданная малая положительная величина (точность).
Для предотвращения непроизводительных затрат машинного времени в
Введём обозначения: алгоритм вводят счётчик числа итераций и при достижении им некоторого
ξ i( 0 ) - погрешности значений неизвестных, заданного значения счет прекращают.
Блок-схема метода итераций приведена на рис. 41, фигурирующая в
ri( 0) - невязки, т.е. алгоритме переменная р имеет следующий смысл, если р=0, то производится
приведение матрицы А к треугольному виду и определяются коэффициенты
ξ i( 0 ) = x i − x i( 0 ) , ri ( 0 ) = bi − bi( 0 ) , i=1,2, ,n. (4.29) преобразования правых частей системы уравнений.
Вычитая каждое уравнение системы (4.28) из соответствующего уравнения
системы (4.27), с учётом обозначений (4.29) получаем:
77 78
