ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.04.2021
Просмотров: 156
Скачиваний: 1
1.
Решение систем линейных уравнений
1.1.
Основные понятия
Система
n
линейных алгебраических уравнений имеет вид:
a
11
x
1
+
a
12
x
2
+
...
+
a
1
n
x
n
=
b
1
,
a
21
x
1
+
a
22
x
2
+
...
+
a
2
n
x
n
=
b
2
,
.....................................
(1)
a
n
1
x
1
+
a
n
2
x
2
+
...
+
a
nn
x
n
=
b
n
.
Совокупность коэффициентов этой системы образует квадратную мат-
рицу
n
×
n
:
a
11
a
12
... a
1
n
a
21
a
22
... a
2
n
. . . . . . . . . . . . . . . .
a
n
1
a
n
2
... a
nn
(2)
В векторно-матричном виде система (1) запишется в виде
A
x
=
b
(3)
где
x
и
b
– вектор-столбцы неизвестных и правых частей.
Иногда системы уравнений имеют некоторые специальные виды мат-
риц:
– симметричная матрица
a
ij
=
a
ji
,
– треугольная матрица с равными нулю элементами, расположенными
ниже или выше диагонали,
– клеточная матрица,
– ленточная матрица (пример – трехдиагональная),
– единичная матрица.
Определителем матрицы
A n
-го порядка называется число
D
, равное
D
=
detA
=
a
11
a
12
... a
1
n
a
21
a
22
... a
2
n
. . . . . . . . . . . . . . . .
a
n
1
a
n
2
... a
nn
=
X
(
−
1)
k
a
1
α
a
2
β
...a
nω
,
(4)
где индексы
α
,
β
,...,
ω
пробегают все возможные
n
!
перестановок номеров
1
,
2
, ..., n
,
k
– число инверсий (обмен двух соседних индексов местами) в
данной перестановке.
Необходимым и достаточным условием существования единственного
решения системы линейных уравнений является
D
6
= 0
. В случае, если
D
= 0
– матрица называется вырожденной, система может не иметь
решений, или иметь их бесконечное множество.
Для иллюстрации рассмотрим систему двух уравнений
a
1
x
+
b
1
y
=
c
1
,
(5)
a
2
x
+
b
2
y
=
c
2
.
(6)
Если изобразить каждое уравнение графически, то возможны три
случая:
1) прямые пересекаются, т.е.
a
1
a
2
6
=
b
1
b
2
,
2) прямые параллельны, т.е.
a
1
a
2
=
b
1
b
2
6
=
c
1
c
2
,
3) прямые совпадают, т.е.
a
1
a
2
=
b
1
b
2
=
c
1
c
2
.
Определитель нашей системы имеет вид
D
=
a
1
b
1
a
2
b
2
.
В практических вычислениях из-за округлений редко удается полу-
чить точное равенство определителя нулю. При
D
≈
0
прямые могут
оказаться почти параллельными, и координаты точки пересечения мо-
гут быть весьма чувствительными к малым изменениям коэффициентов
системы. То есть малые погрешности вычислений или исходных данных
могут привести к существенным погрешностям в решении. В этом случае
система уравнений называется плохо обусловленной.
1.2.
Методы решения линейных систем
Методы решения линейных систем делятся на два класса:
1)
точные (прямые) методы
, которые представляют из себя конечные
алгоритмы для вычисления корней системы; примеры: правило Крамера,
метод Гаусса, метод главных элементов, метод квадратных корней и др.
2)
итерационные методы
, позволяющие получать корни системы с
2
заданной точностью путем сходящихся бесконечных процессов, примеры:
метод итераций, метод Гаусса – Зейделя, метод релаксации и т.д.
Точные методы используют конечные формулы для вычисления неиз-
вестных.
Плюсы:
– решение получается после заранее известного числа операций,
– универсальность и простота метода.
Минусы:
– в памяти машины должна находиться вся матрица, поэтому при боль-
ших матрицах это требует большого объема памяти.
– накопление ошибок округления, поскольку на любом этапе использу-
ются все предыдущие результаты. Поэтому даже точные методы на са-
мом деле являются приближенными, при этом затруднительно оценить
погрешность.
Итерационные методы – методы последовательного приближения. Суть
состоит в задании начального приближения и последовательности опе-
раций, после выполнения которой будут получаться следующие прибли-
жения.
Плюсы:
– нет необходимости хранить в памяти машины всю матрицу,
– нет накопления погрешностей, поскольку точность вычисления в каж-
дой итерации определяется лишь результатом предыдущей итерации.
Минусы:
– эффективность существенно зависит от удачного выбора начального
приближения и быстроты сходимости метода.
1.3.
Точные (прямые) методы
1. Формулы Крамера.
Для системы
n
линейных уравнений с
n
неизвестными
A
x
=
b
(7)
с невырожденной матрицей
A
∆ = det
A
6
= 0
единственное решение находится умножением (7) слева на матрицу
A
−
1
,
т.е.
A
−
1
A
x
=
A
−
1
b
⇒
x
=
A
−
1
b
.
3
В курсе линейной алгебры показывается, что для неизвестных справед-
ливы формулы (Крамера)
x
1
=
∆
1
∆
,
x
2
=
∆
2
∆
,
...,
x
n
=
∆
n
∆
,
(8)
где
∆
i
– определители, получающиеся из определителя системы
∆
заме-
ной его
i
-го столбца столбцом свободных членов
b
.
Например, для системы
a
11
x
+
a
12
y
=
b
1
,
a
21
x
+
a
22
y
=
b
2
неизвестные записываются следующим образом:
x
= ∆
1
/
∆
,
y
= ∆
2
/
∆
,
(9)
где
∆ =
a
11
a
12
a
21
a
22
,
∆
1
=
b
1
a
12
b
2
a
22
,
∆
2
=
a
11
b
1
a
21
b
2
.
Таким образом
, решение системы из
n
уравнений с
n
неизвестными
сводится к вычислению
n
+ 1
определителя порядка
n
. Т.к. вычисление
определителей большого порядка требует выполнения большого объема
арифметических операций, то применение данного метода ограничено.
2. Метод Гаусса.
Алгоритм последовательного исключения неизвестных носит назва-
ние метода Гаусса. В основе метода лежит приведение матрицы системы
к треугольному виду. Этого можно достичь, последовательно исключая
неизвестные из уравнений:
– с помощью первого уравнения исключаем
x
1
из второго и всех после-
дующих уравнений системы;
– с помощью второго уравнения исключаем
x
2
из третьего и всех после-
дующих уравнений системы;
...
– продолжаем до тех пор, пока в левой части последнего (
n
-го) уравнения
не останется одно слагаемое с
x
n
. В результате матрица будет приведе-
на к треугольному виду. Данный процесс носит название прямого хода
метода Гаусса.
Далее, решая последнее уравнение, находим
x
n
и подставляем его в
предыдущее уравнение. Затем решаем его, находим
x
n
−
1
и т.д. В этом
состоит обратный ход метода Гаусса.
4
Рассмотрим систему:
a
11
x
1
+
a
12
x
2
+
a
13
x
3
=
b
1
,
a
21
x
1
+
a
22
x
2
+
a
23
x
3
=
b
2
,
a
31
x
1
+
a
32
x
2
+
a
33
x
3
=
b
3
.
Для того, чтобы исключить
x
1
из второго уравнения, прибавим к нему
первое, умноженное на
−
a
21
a
11
.
Далее, умножим первое уравнение на
−
a
31
a
11
и сложим с третьим. В результате у нас получится система уравнений
a
11
x
1
+
a
12
x
2
+
a
13
x
3
=
b
1
,
a
0
22
x
2
+
a
0
23
x
3
=
b
0
2
,
a
0
32
x
2
+
a
0
33
x
3
=
b
0
3
,
где
a
0
ij
=
a
ij
−
a
i
1
a
11
a
1
j
,
i, j
= 2
,
3
,
(10)
b
0
i
=
b
i
−
a
i
1
a
11
b
1
,
i
= 2
,
3
.
(11)
Далее исключаем из третьего уравнения
x
2
. Для этого надо умножить
второе уравнение на
−
a
0
32
a
0
22
и сложить с третьим. В результате
a
11
x
1
+
a
12
x
2
+
a
13
x
3
=
b
1
,
a
0
22
x
2
+
a
0
23
x
3
=
b
0
2
,
a
00
33
x
3
=
b
00
3
,
где
a
00
ij
=
a
0
ij
−
a
0
i
2
a
0
22
a
0
2
j
,
i, j
= 3
,
b
00
i
=
b
0
i
−
a
0
i
2
a
0
22
b
0
2
,
i
= 3
.
Далее начинается обратный ход метода.
В процессе исключения неизвестных необходимо выполнять опера-
цию деления на коэффициенты
a
11
,
a
0
22
(ведущие элементы). Они должны
быть отличны от нуля. Если это не так, то необходимо соответствующим
образом переставить уравнения системы, что должно быть предусмотре-
но в вычислительном алгоритме.
Модификацией метода Гаусса является схема с выбором ведущего
элемента. В ней требование неравенства нулю диагональных элементов
5