2024
.pdfЦелью первого шага является исключение неизвестного x1 из уравнений с номерами 2,3,...,n. Для этого определяются коэффициенты
i1 |
|
ai1 |
, |
i 2,3,...,n, |
a11 0, |
|
|||||
|
|
a11 |
|
|
на которые надо последовательно умножить первое уравнение и сложить его с i-ми уравнениями системы. Это позволит обратить в ноль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему
|
|
a11x1 a12 x2 |
... a1n |
xn b1, |
|||||||||||||
|
|
|
|
|
|
a(221) x2 ... a(21n) |
xn |
b(21), |
|||||||||
|
|
|
|
|
|
... |
|
|
|
|
... ... |
|
|
... |
|
||
|
|
|
|
|
|
a(n12) x2 ... a(nn1) |
xn b(n1), |
||||||||||
в |
которой a |
(1) |
и |
|
|
b |
(1) |
|
(i, j 2, 3,..., n ) |
вычисляются по |
|||||||
|
|
ij |
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
формулам |
(1) |
|
|
|
|
|
|
|
|
|
|
b(1) |
|
|
|
|
|
|
a |
a |
ij |
|
i1 |
a |
1j |
, |
b |
i |
|
b . |
|||||
|
|
ij |
|
|
|
|
|
|
i |
|
|
i1 1 |
|||||
|
На втором шаге производится исключение неизвестного |
||||||||||||||||
x2 |
из уравнений |
|
|
с |
|
|
номерами |
i 3,4,...,n . Для этого |
|||||||||
определяются коэффициенты |
|
|
|
|
|
||||||||||||
|
|
|
|
|
a |
(1) |
|
|
|
|
|
|
|
|
|
|
|
|
i2 |
|
|
|
i2 |
|
, |
|
|
|
i 3,...,n, |
|
a22 0, |
||||
|
|
a |
(1) |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
22 |
|
|
|
|
|
|
|
|
|
|
|
на которые умножается второе уравнение и поочередно складывается с уравнениями с номерами i 3,...,n для
получения в них нулевых коэффициентов при x2 .
Таким образом, на произвольном k-м шаге необходимо последовательно умножить k-е уравнение на коэффициенты
(k 1)
ik aik(k 1) , i k 1,...,n, akk 0,
akk
и сложить полученные равенства с уравнениями с номерами i k 1,...,n.
11
После (n 1) -го шага исключения получим систему уравнений
a11x1 a12 x2 a13 |
x3 |
... a1n xn |
b1, |
|
a(221) x2 a(231) |
x3 |
... a(21n) xn |
b(21), |
|
a33(2) x3 ... a3(2n)xn |
b(22), |
|||
... |
|
... |
... |
... |
|
|
|
a(nnn 1)xn bn(n 1), |
матрица A(n 1) которой является верхней треугольной. Обратный ход метода Гаусса заключается в
последовательном вычислении неизвестных. Из последнего
уравнения |
находится |
значения |
xn . |
Подставляя |
xn в |
предпоследнее уравнение, получим |
xn 1. Осуществляя |
||||
обратную |
подстановку, |
далее |
последовательно |
находим |
xn 2,xn 3,...,x1. Вычисления неизвестных здесь проводятся по формулам
xn |
bn(n 1) |
ann(n 1) , |
|
|
xk |
bk(k 1) |
a(kk,k1)1xk 1 ... a(kkn 1)xn |
akk(k 1) , |
k n 1,...,1. |
Замечания к методу Гаусса:
-необходимо выполнение требования неравенства нулю элементов, расположенных на главной диагонали;
-если на главной диагонали оказываются элементы, близкие к нулю, то при делении на них возможен неконтролируемый рост погрешности.
Пример. Решить методом Гаусса систему уравнений.
2x1 5x2 4x3 30,x1 3x2 2x3 150,2x1 10x2 9x3 110.
Прямой ход. На первом шаге определим коэффициенты, на которые надо умножить второе и третье уравнения, чтобы исключить из них неизвестную x1:
12
21 |
|
1 |
, |
31 1. |
|
||||
|
2 |
|
|
Умножим первое уравнение на 21 и 31:
x1 |
|
5 |
x2 2x |
3 15, |
|
2 |
|||||
|
|
|
|
2x1 5x2 4x3 30
исложим их со вторым и третьим уравнением, соответственно. Получим систему
2x1 5x2 4x3 30,
|
1 |
x |
|
135, |
|
|
2 |
||||
2 |
|||||
|
|
80. |
|||
|
5x2 5x3 |
На втором шаге исключим неизвестную x2 из третьего уравнения. Для этого умножим второе уравнение на величину
5
32 1 10
2
и сложим его с последним уравнением системы:
2x1 5x2 4x3 30,
|
1 |
x |
|
135, |
|
|
2 |
||||
2 |
|||||
|
|
|
5x3 1270.
Таким образом, в результате выполнения прямого хода получили верхнюю треугольную матрицу коэффициентов системы уравнений.
Обратный ход. Из последнего уравнения получим
x3 1270 254. 5
Подставим найденное значение во второе уравнение и найдем из него x2
13
x2 |
|
135 0 ( 152) |
270. |
|||
|
|
1 |
|
|||
|
|
|
2 |
|
|
|
Подставим x2 |
и x3 |
в первое уравнение: |
x1 30 4 ( 254) 5 270 152. 2
Вычисления по методу Гаусса можно проводить с помощью метода прямоугольника.
Пусть в матрице S i-я строка и k-й столбец являются ведущими и на их пересечении стоит ведущий элемент sik :
... ... ... ... |
... |
||||
|
sik |
... |
sim |
|
|
... |
... |
||||
... ... ... ... |
... |
|
|||
|
sjk |
|
sjm |
|
|
... |
... |
... |
|||
|
|
|
|
... |
|
... ... ... ... |
|
Тогда пересчет элементов матрицы в соответствии с правилом прямоугольника выполняется по следующей схеме:
sjm |
sik sjm |
sjk |
sim |
, j,m 1,...,n, |
j i, m k, |
|
sik |
|
|||
|
|
|
|
|
т.е. для пересчета элементов, расположенных ниже ведущей строки, необходимо построить прямоугольник, одной вершиной которого является ведущий элемент sik , а другой – пересчитываемый элемент sjm , и произвести вычисления по
предлагаемой формуле.
Пример. Решим систему из предыдущего примера, используя для приведения матрицы к треугольному виду метод прямоугольников. Для этого сведем данные в табл. 1.
14
|
|
|
|
Таблица 1 |
||
|
|
|
|
|
|
|
Номер шага |
A1 |
A2 |
A3 |
|
B |
|
|
2 |
5 |
4 |
|
30 |
|
Исходная система |
1 |
3 |
2 |
|
150 |
|
|
2 |
10 |
9 |
|
110 |
|
|
2 |
5 |
4 |
|
30 |
|
1-й шаг прямого хода |
0 |
1/2 |
0 |
|
135 |
|
|
0 |
5 |
5 |
|
80 |
|
|
2 |
5 |
4 |
|
30 |
|
2-й шаг прямого хода |
0 |
1/2 |
0 |
|
135 |
|
|
0 |
0 |
5 |
|
-1270 |
|
На первом шаге |
ведущим |
элементов |
будет a11. |
Перепишем ведущую (первую) строку без изменения. Под ведущим элементов можно сразу записать нули. Выполним пересчет элементов второй и третьей строк:
|
a |
(1) |
|
a11 |
a22 a21 |
a12 |
|
|
|
|
2 3 1 5 |
|
1 |
, |
||||||||||||||
|
22 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
a11 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
2 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
a(1) |
|
a11 |
a23 a21 |
a13 |
|
|
|
|
|
2 2 1 4 |
|
|
0, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
23 |
|
|
|
|
|
|
|
a11 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
b |
(1) |
a11 b2 a21 |
b1 |
|
|
|
2 150 1 30 |
|
135, |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
2 |
|
|
|
|
|
|
|
|
a11 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
a |
(1) |
|
a11 |
a32 a31 a12 |
|
|
|
2 10 2 5 |
5, |
||||||||||||||||||
|
32 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
a11 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
a(1) |
|
a11 |
a33 a31 |
a13 |
|
|
|
|
2 9 2 4 |
|
|
5, |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
33 |
|
|
|
|
|
|
|
a11 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
b(1) |
a11 b3 a31 |
b1 |
|
2 110 2 30 |
|
80. |
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
3 |
|
|
|
|
|
|
|
|
a11 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15
В таблице первого шага отметим ведущий элемент для второго (a22) и перепишем первые две строки без изменения. Выполним пересчет оставшихся элементов:
|
|
|
|
|
|
|
a |
(1) |
|
(1) |
(1) |
a |
(1) |
|
|
|
1 |
|
5 5 0 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
2 |
|||||||||||||||||
|
|
a |
(2) |
|
22 |
a33 |
a |
32 |
23 |
|
|
|
|
|
|
|
|
|
5, |
|||||||||
|
|
33 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|||||||||
|
|
|
|
|
|
|
|
a(221) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
a |
(1) |
|
|
(1) |
a |
(1) |
(1) |
|
|
|
80 |
5 135 |
||||||||||||
|
|
|
|
|
|
|
|
2 |
||||||||||||||||||||
b |
(2) |
|
22 |
b3 |
|
32 b2 |
|
|
|
|
|
|
|
|
|
|
|
1270. |
||||||||||
3 |
|
|
|
a |
(221) |
|
|
|
|
|
|
|
1 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом мы получили матрицу коэффициентов, приведенную к треугольному виду.
1.2.4. Метод Гаусса с выбором главного элемента
Для устранения недостатков метода Гаусса разработан метод Гаусса с выбором главного элемента. Целью метода является уменьшение возможного влияния погрешности вычислений за счет размещения на каждом k-м шаге на позиции akk (k 1,...,n ) такого коэффициента aij , который
будет максимальным по модулю в уравнениях с номерами i k,...,n ( j 1,...,n ). Это достигается за счет перестановок строк и столбцов.
Пример. Переставим строки и столбцы в системе из предыдущего примера таким образом, чтобы на месте элемента a11 располагался максимальный по модулю коэффициент:
10x2 2x1 9x3 110,3x2 x1 2x3 150,5x2 2x1 4x3 30.
16
После первого шага получим:
|
|
|
|
|
|
|
|
|
|
|
|
10x2 |
2x1 9 x3 |
110, |
|||||||||
|
2 |
|
|
7 |
|
|
|
|
|||
|
x |
|
|
x |
|
117, |
|||||
|
|
|
|
|
|
|
|
||||
5 |
10 |
|
|||||||||
|
|
1 |
|
3 |
|
||||||
|
|
|
x1 |
|
1 |
|
x |
3 |
25. |
||
|
|
|
2 |
|
|||||||
|
|
|
|
|
|
|
|
|
На втором шаге снова переставим уравнения таким образом, чтобы на месте a22 находился максимальный по модулю коэффициент из второго и третьего уравнений:
|
|
|
|
|
|
|
|
|
|
|
|
10x2 |
9x3 |
|
2x1 110, |
||||||||
|
|
7 |
|
|
|
|
2 |
|
|||
|
|
|
x |
|
|
x1 117, |
|||||
|
|
|
|
|
3 |
|
|||||
10 |
5 |
||||||||||
|
|
|
|
|
|
||||||
|
|
|
1 |
|
x |
3 |
|
|
x1 25. |
||
|
2 |
|
|
||||||||
|
|
|
|
|
|
|
|
Исключим неизвестную x3 из третьего уравнения:
|
|
9x |
|
|
|
2x |
110, |
||||
10x |
2 |
3 |
|
||||||||
|
7 |
|
|
|
1 |
|
|||||
|
|
x |
|
|
2 |
x1 |
117, |
||||
|
|
|
3 |
|
|||||||
10 |
5 |
||||||||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
5 |
x1 |
25. |
|
|
|
|
|
|
|
|
|
7 |
|||
|
|
|
|
|
|
|
|
|
|
Выполняя обратные подстановки, получим:
|
117 |
2 ( 152) |
|
|
||||
|
|
|
|
|
|
|||
x1 152, |
x3 |
|
|
5 |
|
254, |
||
|
|
7 |
|
|
||||
|
|
|
|
|
||||
|
10 |
|
|
|
||||
|
|
|
|
|
|
|
x2 110 2 ( 152) 9 ( 254) 270. 10
17
1.2.5. Применение метода Гаусса для вычисления определителей и обратных матриц
Поскольку в результате прямого хода метода Гаусса получается верхняя треугольная матрица, то ее определитель может быть вычислен по формуле
n
A( 1)s aii ,
i1
где s – число перестановок строк матрицы A при ее преобразовании к треугольному виду.
Пример. Применим указанную формулу для вычисления определителей матриц, полученных по классическому методу Гаусса и по методу Гаусса с выбором главного элемента с учетом выполненных перестановок строк
|
|
|
|
2 |
5 |
4 |
|
0 |
|
|
1 |
|
|
|
|
|
|||
|
|
1) A |
0 |
1 2 |
0 |
( 1) |
2 |
5 5, |
|||||||||||
|
|
|
2 |
||||||||||||||||
|
|
|
|
0 |
0 |
5 |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
10 |
9 |
|
2 |
|
1 |
|
|
|
7 |
|
|
5 |
|
||||
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
2) A |
|
0 |
7 10 |
|
2 5 |
|
( 1) 10 |
|
|
|
|
|
5. |
||||||
|
|
|
|
7 |
|||||||||||||||
|
|
0 |
0 |
|
5 7 |
|
|
|
|
|
|
10 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод Гаусса применяется и для нахождения обратной матрицы. Для этого запишем равенство AA 1 E в виде
a |
11 |
a |
12 |
... |
a |
1n |
|
|
x |
11 |
x |
12 |
... |
x |
1n |
|
|
1 |
0 |
... |
0 |
|
|
... |
|
|
|
|
|
... |
|
|
|
|
1 |
... |
|
||||||
a21 |
a22 |
a2n |
|
x |
21 |
x22 |
x2n |
|
0 |
0 |
|||||||||||
|
|
|
|
... |
... |
|
|
|
|
|
... |
... |
|
|
... |
... |
|
||||
|
|
|
|
|
|
|
|
||||||||||||||
... ... |
|
|
... ... |
|
|
... |
... |
||||||||||||||
|
|
an2 |
... |
|
|
|
|
|
|
xn2 |
... |
|
|
|
|
|
0 |
... |
|
||
an1 |
ann |
|
xn1 |
xnn |
|
0 |
1 |
где xij - элементы матрицы A 1.
Таким образом, вычисление обратной матрицы можно свести к решению следующей системы уравнений с одинаковой матрицей коэффициентов и несколькими правыми частями:
18
AX1 E1, |
AX2 E2, ..., |
AXn En, |
где Xi и Ei - i-ые столбцы матриц A 1 |
и E, соответственно, |
|
i 1,...,n. |
|
|
Метод Гаусса позволяет производить поиск решения всех n систем одновременно.
Пример. Для заданной матрицы найти обратную
2 |
5 |
4 |
|
|
|
|
3 |
2 |
|
A 1 |
. |
|||
|
2 |
10 |
9 |
|
|
|
Для вычисления обратной матрицы составим табл. 2. Пересчет элементов матриц проведем с помощью метода прямоугольника.
Таблица 2
Номер шага |
A1 |
A2 |
A3 |
E1 |
E2 |
E3 |
|
|
2 |
5 |
4 |
1 |
0 |
0 |
|
Исходная система |
1 |
3 |
2 |
0 |
1 |
0 |
|
|
2 |
10 |
9 |
0 |
0 |
1 |
|
1-й шаг прямого |
2 |
5 |
4 |
1/2 |
0 |
0 |
|
0 |
1/2 |
0 |
-1/2 |
1 |
0 |
||
хода |
|||||||
0 |
5 |
5 |
-1 |
0 |
1 |
||
|
|||||||
2-й шаг прямого |
2 |
5 |
4 |
1/2 |
0 |
0 |
|
0 |
1/2 |
0 |
-1/2 |
1 |
0 |
||
хода |
|||||||
0 |
0 |
5 |
4 |
-10 |
1 |
||
|
На обратном ходу метода Гаусса определим значения неизвестных:
x31 |
|
2 |
, |
x32 2, |
x33 |
|
1 |
, |
|
|
|||||||
|
5 |
|
|
|
5 |
|
||
x21 1, |
x22 2, |
x23 0, |
19
x11 |
|
7 |
, |
x12 1, |
x13 |
|
2 |
. |
|
|
|||||||
|
5 |
|
|
|
5 |
|
Запишем найденные значения в матрицу:
|
|
1.4 |
1 |
0.4 |
||
A 1 |
|
|
1 |
2 |
|
|
|
0 . |
|||||
|
|
|
|
|
|
|
|
|
|
0.8 |
2 |
0.2 |
|
|
|
|
|
1.2.6. Метод Холецкого (метод квадратных корней)
Метод квадратных корней предназначен для решения систем уравнений с симметричной положительно определенной матрицей A.
В основе метода лежит алгоритм построения специального LU-разложения матрицы А, в результате чего она приводится к виду
|
|
l |
0 |
... |
0 |
|
|
|
11 |
l22 |
|
|
|
T |
L |
l21 |
... |
0 |
|
|
A LL , |
|
|
|
|
. |
|
|
|
... |
... |
... |
... |
|
|
|
|
ln2 |
... |
|
|
|
|
ln1 |
lnn |
Если такое разложение матрицы A получено, то решение исходной системы уравнений сводится к последовательному решению двух систем с треугольными матрицами:
LY B,
AX Y.
Найдем элементы матрицы L. Для этого вычислим
элементы матрицы LLT и приравняем их соответствующим элементам матрицы А. В результате получим систему уравнений:
20