Новые многофункциональные материалы и нанотехнологии

60
A =












nn
n
n
n
n
a
a
a
a
a
a
a
a
a
...
...
...
2 1
2 22 21 1
12 11


(4.2)
Свободные члены и корни представляются столбцами или n- мерными векторами b и x. Тогда систему (4.1) можно записать более кратко в матричном представлении:
A
⋅⋅⋅⋅ x = b

(4.3)
В линейной алгебре доказана следующая теорема: если детерминант
(определитель) матрицы A не равен нулю, то система уравнений (4.1) имеет единственное решение. Т.е. при det A
≠ 0 существует только один набор чисел x
i
(i = 1, 2, ..., n), который обращает в тождество систему
(4.1). Следовательно, если мы ищем единственное решение системы уравнений (4.1), то прежде чем ее решать, необходимо убедиться, что детерминант матрицы коэффициентов при неизвестных не равен нулю.
Способам вычисления детерминантов посвящена глава 5.
Многочисленные способы решения системы линейных уравнений принято подразделять на две группы: прямые методы и итерационные.
Прямые методы позволяют найти решение с помощью определенного конечного количества операций. В итерационных методах решение ищется как предел последовательных приближений, где число итераций зависит от задаваемой погрешности корней. В §§4.1 – 4.4 рассмотрены простейшие прямые методы, итерационным методам посвящен §4.5.
Предположим, что условие det A
≠ 0 для системы (4.1) выполнено.
Тогда, согласно известной теореме матричной алгебры, для матрицы A существует обратная матрица A
−−−−1
, для которой справедливы равенства:
A
⋅⋅⋅⋅
A
−−−−1
=
A
−−−−1
⋅⋅⋅⋅ A = E,
(4.4)
где E
− единичная матрица размера n × n.
Умножим слева обе части уравнения (4.3) на обратную матрицу A
−−−−1
Принимая во внимание (4.4), получим:
x = A
−−−−1
⋅⋅⋅⋅ b.

(4.5)

61
Таким образом, умножение обратной матрицы A
−−−−1
на вектор
(столбец) свободных членов b дает единственное решение: вектор корней x исходной системы (4.1). С точки зрения математики проблема решена.
Однако получение обратной матрицы в явном виде сопряжено с практическими трудностями. С ростом числа n требуемый объем вычислений резко возрастает. Заметим, что умножение матрицы на вектор представляет собой простую задачу, легко решаемую программным путем.
Задаче вычисления обратной матрицы посвящена глава 6. Далее в настоящей главе рассматриваются элементарные методы решения систем линейных уравнений, не требующие вычисления обратной матрицы.

§ 4.2. Метод Крамера
Известно, что обратную матрицу можно представить в виде отношения:
A
−−−−1
= A
*
/
∆,

(4.6) где A
*

−−−− матрица союзная исходной A , т.е. транспонированная матрица алгебраических дополнений,
∆ −−−− детерминант матрицы A.
Подставим (4.6) в уравнение (4.5) и умножим матрицу A
*
слева на столбец свободных членов b. В результате получим новый n-мерный вектор, компоненты которого
∆
i
выражаются следующими суммами:
∆
i
=
∑
=
⋅
n
j
j
ji
b
A
1
,

(4.7) где A
ij

−−−− алгебраические дополнения элементов a
ij
матрицы (4.2).
Можно доказать, что каждая величина
∆
i
(i = 1, 2, ..., n) равна детерминанту матрицы, которая получается из исходной A заменой i-го столбца на столбец свободных членов b:

62














+
−
+
−
+
−
nn
i
n
n
i
n
n
n
i
i
n
i
i
a
a
b
a
a
a
a
b
a
a
a
a
b
a
a
...
...
...
...
...
...
1
,
1
,
1 2
1
,
2 2
1
,
2 21 1
1
,
1 1
1
,
1 11

(4.8)
Для доказательства достаточно непосредственно вычислить детерминант матрицы (4.8) известным методом разложения по минорам
i
-го столбца, который описан в главе 5.
Следовательно, деление каждого числа
∆
i
на детерминант
∆ матрицы
(4.2) даст нам значение i-го корня исходной системы (4.1):
x
i
=
∆
i
/
∆ , i =1, 2, ..., n.
(4.9)
Описанная процедура вычисления корней системы линейных уравнений называется методом Крамера. В этом методе решение системы (4.1) полностью сводится к вычислению детерминантов, способы расчета которых подробно изложены в следующей главе.
Следует заметить, что в тех случаях, когда детерминант
∆ близок к нулю, метод Крамера может дать большую ошибку в значениях найденных корней, что непосредственно следует из формулы (4.9).
Конечно, погрешность вычисления корня существенно зависит и от величины соответствующего детерминанта
∆
i
, стоящего в числителе формулы (4.9). Системы уравнений (4.1), у которых детерминант матрицы коэффициентов при неизвестных близок к нулю, требуют для своего решения специальных методов, которые не включены в настоящее учебное пособие.
Важнейшим недостатком алгоритма Крамера является большое количество необходимых арифметических операций. Из формул (4.9) ясно, что для решения данной системы (4.1) приходится вычислять
(n+1) детерминантов, каждый порядка n. Рациональные методы расчета детерминантов рассматриваются в следующей главе. Пока заметим, что для вычисления детерминанта n-го порядка способом разложения по минорам требуется произвести n!
⋅(n – 1) умножений и примерно столько же делений. Следовательно, при решении системы линейных уравнений 40-го порядка методом Крамера придется выполнить
41
⋅40!⋅39 умножений и сложений. Так как 40! ≈ 8⋅10 47
, то можно оценить, что при использовании самых быстродействующих компьютеров необходимое время решения во много раз превышает

63 время существования нашей Вселенной. Кроме того, при выполнении процессором большого количества операций накапливается значительная погрешность результата, так как в каждой операции над реальными числами проводится округление.
При решении систем линейных уравнений для n = 2 и n = 3 метод
Крамера легко реализуется и без использования компьютера. Для больших значений n целесообразно применять более эффективные методы.

§ 4.3. Метод Гаусса
Метод Гаусса отличается сравнительно малым объемом вычислений и простотой алгоритма, что позволяет легко его программировать. Этот метод заключается, в сущности, в последовательном исключении неизвестных.
Процедура вычисления корней системы линейных уравнений состоит из двух частей: прямого хода и обратного хода.
Прямой ход состоит из отдельных шагов.
Первый шаг. Выбирается ведущий элемент
− коэффициент при неизвестном x
1
. Это может быть любой коэффициент a
i
1
(i = 1, ..., n) не равный нулю. Напомним, что первый индекс у коэффициента a
ij
означает номер уравнения в системе, второй индекс
− номер неизвестного, на которое умножается данный коэффициент a
ij
. Порядок расположения уравнений в системе (4.1) не существенен. Поэтому, переставляя уравнения, всегда можно ведущим сделать элемент a
11
Очевидно, что все коэффициенты a
i
1
(i = 1, ..., n) не могут равняться нулю. Равенство нулю всех a
i
1
(i = 1, ..., n) означает наличие в матрице A нулевого столбца и равенство нулю детерминанта матрицы. В этом случае единственное решение системы отсутствует.
Уравнение с ведущим элементом делится на коэффициент a
11
≠ 0 и приобретает вид:
x
1
+
∑
=
n
j
j
j
x
a
a
2 11 1
=
11 1
a
b

(4.10)
Теперь уравнение (4.10) умножается на коэффициент a
21
и вычитается из 2-го уравнения исходной системы (4.1). Слагаемое, содержащее x
1
, исчезает из 2-го уравнения.

64
Затем уравнение
(4.10) последовательно умножается на коэффициенты a
i
1
(где i = 3, ..., n) и вычитается из соответствующего i- го уравнения исходной системы. В каждом уравнении член, содержащий x
1
, исчезнет. В результате, кроме уравнения (4.10), мы получим систему из n
−

1 уравнений, которая содержит n
−

1 неизвестных x
i
(i = 2, ... n):
∑
=
⋅
n
j
j
ij
x
a
2
)
1
(
=
)
1
(
i
b
,
i
= 2, ..., n.
(4.11)
В системе уравнений (4.11) введены обозначения
11 1
1
)
1
(
a
a
a
a
a
j
i
ij
ij
−
=
,
11 1
1
)
1
(
a
b
a
b
b
i
i
i
−
=
, i,j = 2, ..., n.
(4.12)
Второй шаг прямого хода выполняется аналогично. В системе уравнений (4.11) выбирается ведущий элемент
)
1
(
2
i
a
≠ 0 (i = 2, ..., n) при
x
2
. При необходимости меняется порядок уравнений в системе (4.11), и ведущим становится
)
1
(
22
a
. Сначала первое уравнение системы (4.11) делится на ведущий элемент
)
1
(
22
a
:
x
2
+
∑
=
n
j
j
j
x
a
a
3
)
1
(
22
)
1
(
2
=
)
1
(
22
)
1
(
2
a
b

(4.13)
Затем уравнение
(4.13) последовательно умножается на коэффициенты
)
1
(
2
i
a
(i = 3, ..., n) и вычитается из соответствующего i-го уравнения системы (9). В результате из всех уравнений исчезают члены с x
2
. Получим новую систему из n
− 2 уравнений, которая содержит n −
2 неизвестных x
i
(i = 3, ..., n):
∑
=
⋅
n
j
j
ij
x
a
3
)
2
(
=
)
2
(
i
b
,
i
= 3, ..., n.
(4.14)
В системе (4.14) введены новые обозначения:

65
)
1
(
22
)
1
(
2
)
1
(
2
)
1
(
)
2
(
a
a
a
a
a
j
i
ij
ij
−
=
,
)
1
(
22
)
1
(
2
)
1
(
2
)
1
(
)
2
(
a
b
a
b
b
i
i
i
−
=
, i,j = 3, ..., n. (4.15)
Продолжение процедуры последовательного исключения неизвестных приведет к тому, что после (n
−

1)-го шага прямого хода получится линейное уравнение, содержащее только одно неизвестное:
)
1
(
−
n
nn
a
⋅
x
n
=
)
1
(
−
n
n
b

(4.16)
Таким образом, исходная система уравнений приведена к эквивалентной (т.е. имеющей те же корни), имеющей треугольную матрицу коэффициентов при неизвестных. При этом были преобразованы и свободные члены.
Заметим, что коэффициенты при неизвестных и свободные члены преобразовывались по идентичным рекуррентным формулам. Поэтому целесообразно предварительно построить расширенную матрицу размером n
× (n + 1), присоединив справа к квадратной матрице коэффициентов при неизвестных (n + 1)-й столбец свободных членов.
Тогда элементы расширенной матрицы с
ij
( i = 1, ..., n, j = 1, …, (n + 1)) будут преобразовываться по рекуррентному закону:
)
(k
ij
с
=
)
1
(
−
k
ij
с
−
)
1
(
−
k
ik
c
)
1
(
)
1
(
−
−
k
kk
k
kj
c
c
,
(4.17) где k – порядковый номер шага прямого хода.
После преобразования коэффициентов при неизвестных и свободных членов реализуется обратный ход.
На первом шаге обратного хода из уравнения (4.16) сразу вычисляется n-й корень системы (4.1):
x
n
=
)
1
(
)
1
(
−
−
n
nn
n
n
a
b

(4.18)
В предпоследнем (n – 2)-м шаге прямого хода было получено уравнение

66
x
n
−
1
+
)
2
(
1
,
1
)
2
(
,
1
−
−
−
−
−
n
n
n
n
n
n
a
a
⋅x
n
=
)
2
(
1
−
−
n
n
b

(4.19)
Второй шаг обратного хода заключается в подстановке (4.18) в (4.19) и вычислении корня x
n
−
1
Далее последовательно используются уравнения, полученные ранее на каждом шаге прямого хода. На предпоследнем шаге обратного хода вычисляется x
2
с помощью уравнения (4.13). Значения корней x
i
(i = 3,
..., n) уже получены в предыдущих шагах. На последнем (n-м) шаге вычисляется x
1
с помощью уравнения (4.10).
Таким образом, исходная система линейных уравнений (4.1) полностью решена.
Примечание. В линейной алгебре доказано, что если det A
≠ 0, то на каждом шаге прямого хода найдется хотя бы один ведущий коэффициент, не равный нулю. Следовательно, можно специально не вычислять предварительно детерминант матрицы коэффициентов при неизвестных. Если на каком-либо шаге прямого хода не найдется ненулевой ведущий коэффициент, то это значит, что det A = 0 и система не имеет единственного решения.
Полезно сравнить количество вычислений, необходимых для решения системы линейных уравнений (4.1) методом Крамера и методом Гаусса, т.е. сравнить эффективности двух рассмотренных методов.
Если детерминанты вычислять методом разложения по минорам (см. главу 5), то для расчета одного детерминанта n-го порядка приходится совершать количество операций умножения и деления, равное (n – 1)×
×(n
2
+n+3) / 3. Это значит, что для решения системы из n линейных уравнений методом Крамера необходимо выполнить (n + 1) (n – 1) (n
2
+
n
+ 3) / 3 + n операций умножения и деления. Иначе говоря, число требуемых операций имеет порядок
∼ n
4
Можно вычислить, что при решении системы линейных уравнений
n
-го порядка методом Гаусса в прямом ходе выполняется n (n+1) (n+2) /
3 операций умножения и деления и столько же операций вычитания.
При обратном ходе выполняется n (n
− 1) / 2 операций умножения и деления и столько же операций вычитания. Следовательно, общее количество арифметических действий при решении системы линейных уравнений n-го порядка методом Гаусса имеет порядок
∼ n
3

67
Таким образом, количество арифметических операций при решении системы линейных уравнений в методе Гаусса на порядок меньше, чем в методе Крамера. Это значит, что уже при n
≥ 4 целесообразно использовать метод Гаусса.
Проиллюстрируем метод Гаусса примером, причем для экономии места ограничимся системой из трех уравнений.
Пример 1. Дана следующая система уравнений:
2x
1
+ 2x
2
+ 4x
3
= 18,
2x
1
− x
2
+ 3x
3
= 9,
3x
1
− x
2
+ 2x
3
= 7.
Возьмем в качестве первого ведущего коэффициента a
11
= 2.
Поделим на него первое уравнение. Затем исключим x
1
из второго и третьего уравнений вычитанием преобразованного первого, домноженного на 2 и 3 соответственно. В результате первого шага прямого хода система принимает вид:
x
1
+ x
2
+ 2x
3
= 9,
− 3x
2
− x
3
=
− 9,
− 4x
2
− 4x
3
=
− 20.
Второй шаг начинается с деления второго уравнения на
)
1
(
22
a
=
− 3.
Затем исключается x
2
из третьего уравнения сложением его с преобразованным вторым, умноженным на 4. Второй (и последний в данном примере) шаг прямого хода заканчивается получением треугольной матрицы коэффициентов при неизвестных:
x
1
+ x
2
+ 2x
3
= 9,
x
2
+ (1/3) x
3
= 3,
− (8/3) x
3
=
− 8.
Обратный ход начинается с вычисления x
3
из последнего уравнения преобразованной системы: x
3
= 3. Подставив полученное значение x
3
во второе уравнение, получаем x
2
= 2. Наконец, подстановка значений x
3 и
x
2
в первое уравнение дает x
1
=1.
Подставив найденные значения корней в исходную систему, убеждаемся в правильности найденного решения.

68
§ 4.4. Уточнение корней и число обусловленности
Погрешность, накапливающаяся при вычислениях, приводит к тому, что любой метод (Гаусса, Крамера и т.д.) дает не точное, а приближенное значение корней решаемой системы линейных уравнений.
Сначала рассмотрим случай, когда исходные данные: коэффициенты матрицы А и свободные члены имеют достаточную точность (например, все значащие цифры являются верными, а погрешность не превышает единицы младшего разряда). В этом случае необходимо оценить погрешность, которая накапливается в процессе выполнения алгоритма.
Для этого после решения системы следует полученные значения корней подставить в исходную систему (4.1) и вычислить левые части уравнений. Если они совпадут с соответствующими свободными членами (в пределах допустимых погрешностей), то решение можно полагать удовлетворительным. Если же наблюдается значимое расхождение, то необходимо применить более точный метод решения системы уравнений (4.1) или использовать процедуру уточнения корней.
Обозначим через x вектор точных значений корней, x
(1)
– вектор приближенных значений корней, полученных в ходе решения. Тогда точное решение можно представить в виде:
x = x
(1)
+
δδδδ,

(4.20) где
δδδδ – вектор погрешностей. Каждая компонента вектора δδδδ
представляет собой разность между точным значением i-го корня и его приближенным значением
δ
i
= x
i
–
)
1
(
i
x
(i = 1, …, n).
(4.21)
Подставляя (4.20) в исходную систему (4.3), получим новую систему линейных уравнений:
A
⋅⋅⋅⋅ δδδδ = εεεε ,



(4.22) где вектор
εεεε называется невязкой приближенного решения
εεεε = b −−−− A ⋅⋅⋅⋅ x
(1)

(4.23)

69
Процедура уточнения корней заключается в следующих операциях.
Полученные приближенные значения корней x
(1)
подставляются в (4.23) и вычисляются компоненты вектора невязок
εεεε. Далее решается система уравнений (4.22), которая содержит исходную матрицу коэффициентов при неизвестных (4.2), а в качестве свободных членов используются вычисленные невязки (4.22). Решение системы проводится любым доступным способом, например тем же методом Гаусса. Результатом решения являются значения поправок (4.21) к приближенным значениям корней

Скачать 0.96 Mb.

Поделитесь с Вашими друзьями: