ВУЗ:
Составители:
57
итерации и практически не зависит от ранее выполненных вычислений. Таким
образом, итерационные методы являются особенно полезными в случае
большого числа уравнений, а также плохо обусловленных систем. Следует
отметить, что при этом сходимость итераций может быть очень медленной;
поэтому ищутся эффективные пути её ускорения.
Итерационные методы могут использоваться для уточнения решений,
по
лученных с помощью прямых методов. Такие смешанные алгоритмы обычно
довольно эффективны, особенно для плохо обусловленных систем.
Наиболее распространёнными среди прямых методов являются метод
исключения Гаусса и его модификации.
4.1. Метод Гаусса
Пусть линейное алгебраическое уравнение имеет вид:
А
⋅
x=b, (4.1)
где
А – вещественная квадратная матрица порядка n, b – заданный вектор, х –
искомый вектор. Если матрица
А неособенная, то есть определитель матрицы
отличен от нуля, тогда для каждого вектора
b система (4.1) имеет единственное
решение.
Запишем систему (4.1) в развёрнутом виде:
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.2)
a
n1
x
1
+a
n2
x
2
+…+a
nn
x
n
=b
n
Метод Гаусса основан на приведении матрицы к треугольному виду, что
достигается последовательным исключением неизвестных х
1
, х
2
, …, х
n
из данной
системы. Метод состоит из двух этапов – прямого и обратного хода.
Прямой ход. Предположим, что а
11
не равно нулю. Поделив первое уравнение
на а
11
получим:
x
1
+ c
12
x
2
+…+ c
1n
x
n
= y
1
, (4.3)
где
11
1
1
a
a
c
j
j
=
, j=2,…, n,
11
1
1
a
b
y =
.
Рассмотрим теперь оставшиеся уравнения системы (4.2):
a
i1
x
1
+ a
i2
x
2
+…+ a
in
x
n
= b
i
, i=2,3,…,n. (4.4)
Умножим (4.3) на а
i1
и вычтем полученное уравнение из i-го уравнения
системы (4.4). В результате получим следующую систему уравнений:
1112121
yxcxcxcx
nnjj
=
+++
+
K
,
)1(
2
)1(
2
)1(
22
)1(
22
yxcxcxc
nnjj
=++++ KK
,
………………………………………. (4.5)
)1()1()1(
2
)1(
2 nnnnjnjn
yxcxcxc =++++ KK
.
58
Здесь обозначено:
11
)1(
ijijij
acaa −=
,
11
)1(
iji
aybb −=
, i,j=2,3,…,n. (4.6)
Матрица системы (4.5) имеет вид:
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
)1()1(
2
)1(
2
)1(
22
112
0
0
1
nnn
n
n
cc
cc
cc
K
KKKKKK
K
K
. (4.7)
Исключая таким же образом неизвестные х
2
, х
3
,…,х
n
, придём окончательно к
системе уравнений вида:
x
1
+c
12
x
2
+…+c
1n
x
n
= y
1
,
x
2
+…+c
2n
x
n
= y
2
,
……………………… (4.8)
x
n-1
+…+c
n-1
x
n
= y
n-1
,
x
n
= y
n
,
эквивалентной исходной системе (4.2).
Матрица этой системы имеет треугольный вид. На этом заканчивается
прямой ход метода Гаусса.
Заметим, что в процессе исключения неизвестных приходится выполнять
операции деления на коэффициенты а
11
, а
22
и т. д. Поэтому они должны быть
отличными от нуля; в противном случае необходимо соответственным образом
переставить уравнения системы. Перестановка уравнений должна быть
предусмотрена в вычислительном алгоритме при его реализации на ЭВМ.
Обратный ход. Он заключается в нахождении неизвестных х
1
, х
2
, …, х
n
из
системы (4.8). Поскольку матрица системы имеет треугольный вид, можно
последовательно, начиная с х
n
, найти все неизвестные. Общие формулы
обратного хода имеют вид:
∑
+=
−=
n
ij
jijii
xcyx
1
, i = n-1,…,1, x
n
= y
n
. (4.9)
На рис. 35 приведена блок-схема решения методом Гаусса системы n
линейных уравнений вида (4.2). При вводе коэффициентов системы (4.2) должна
быть сформирована расширенная матрица коэффициентов А размерностью
n+1×n, в n+1 столбец которой записываются правые части коэффициентов b
i
(i=1,…,n). Левая часть блок-схемы соответствует прямому ходу. Поясним смысл
используемых переменных: ε - малая положительная величина (10
-5
÷10
-7
),
Р=
0, если все коэффициенты столбца i матрицы А равны нулю
номеру строки, в которой стоит первый, отличный от нуля
коэффициент в i-ом столбце;
итерации и практически не зависит от ранее выполненных вычислений. Таким Здесь обозначено:
образом, итерационные методы являются особенно полезными в случае aij(1) = aij − c1 j a i1 ,
bi(1) = b j − y1 ai1 , i,j=2,3, ,n. (4.6)
большого числа уравнений, а также плохо обусловленных систем. Следует
Матрица системы (4.5) имеет вид:
отметить, что при этом сходимость итераций может быть очень медленной;
поэтому ищутся эффективные пути её ускорения. ⎡ 1 c12 K c1n ⎤
Итерационные методы могут использоваться для уточнения решений, ⎢ 0 c (1) K c (1) ⎥
полученных с помощью прямых методов. Такие смешанные алгоритмы обычно ⎢ 22 2n ⎥. (4.7)
довольно эффективны, особенно для плохо обусловленных систем. ⎢ KKKKKK ⎥
Наиболее распространёнными среди прямых методов являются метод
⎢ (1) (1) ⎥
⎣ 0 cn 2 K cnn ⎦
исключения Гаусса и его модификации.
Исключая таким же образом неизвестные х2, х3, ,хn, придём окончательно к
системе уравнений вида:
4.1. Метод Гаусса x1+c12x2+ +c1nxn = y1,
Пусть линейное алгебраическое уравнение имеет вид: x2+ +c2nxn = y2,
А⋅x=b, (4.1) (4.8)
где А вещественная квадратная матрица порядка n, b заданный вектор, х xn-1+ +cn-1xn = yn-1,
искомый вектор. Если матрица А неособенная, то есть определитель матрицы xn = yn,
отличен от нуля, тогда для каждого вектора b система (4.1) имеет единственное эквивалентной исходной системе (4.2).
решение. Матрица этой системы имеет треугольный вид. На этом заканчивается
Запишем систему (4.1) в развёрнутом виде: прямой ход метода Гаусса.
a11x1+a12x2+ +a1nxn=b1 Заметим, что в процессе исключения неизвестных приходится выполнять
a21x1+a22x2+ +a1nxn=b2 операции деления на коэффициенты а11, а22 и т. д. Поэтому они должны быть
(4.2) отличными от нуля; в противном случае необходимо соответственным образом
an1x1+an2x2+ +annxn=bn переставить уравнения системы. Перестановка уравнений должна быть
Метод Гаусса основан на приведении матрицы к треугольному виду, что предусмотрена в вычислительном алгоритме при его реализации на ЭВМ.
достигается последовательным исключением неизвестных х1, х2, , хn из данной Обратный ход. Он заключается в нахождении неизвестных х1, х2, , хn из
системы. Метод состоит из двух этапов прямого и обратного хода. системы (4.8). Поскольку матрица системы имеет треугольный вид, можно
Прямой ход. Предположим, что а11 не равно нулю. Поделив первое уравнение последовательно, начиная с хn, найти все неизвестные. Общие формулы
на а11 получим: обратного хода имеют вид:
n
x1 + c12x2 + + c1nxn = y1 , (4.3) xi = yi − ∑cij x j , i = n-1, ,1, x n = yn . (4.9)
j =i+1
a1 j b На рис. 35 приведена блок-схема решения методом Гаусса системы n
где c1 j = , j=2, , n, y1 = 1 .
a 11 a 11 линейных уравнений вида (4.2). При вводе коэффициентов системы (4.2) должна
Рассмотрим теперь оставшиеся уравнения системы (4.2): быть сформирована расширенная матрица коэффициентов А размерностью
ai1x1 + ai2x 2+ + ainxn = bi, i=2,3, ,n. (4.4) n+1×n, в n+1 столбец которой записываются правые части коэффициентов b i
Умножим (4.3) на аi1 и вычтем полученное уравнение из i-го уравнения (i=1, ,n). Левая часть блок-схемы соответствует прямому ходу. Поясним смысл
системы (4.4). В результате получим следующую систему уравнений: используемых переменных: ε - малая положительная величина (10-5÷10-7),
x1 + c12 x2 + K + c1 j x j + c1n xn = y1 , 0, если все коэффициенты столбца i матрицы А равны нулю
Р= номеру строки, в которой стоит первый, отличный от нуля
(1)
c22 x2 + K + c2(1j) x j + K + c2(1n) xn = y2(1) , коэффициент в i-ом столбце;
. (4.5)
c x +K+ c xj +K+ c x = y .
(1)
n2 2
(1)
nj
(1)
nn n
(1)
n
57 58
Страницы
- « первая
- ‹ предыдущая
- …
- 27
- 28
- 29
- 30
- 31
- …
- следующая ›
- последняя »
