Lektsii_VychMat_6-8
.pdf
Замечание. Применение схемы Жордана особенно
удобно, когда требуется решить несколько систем уравнений,
отличающихся лишь правыми частями:
ån ai j × xjl = bil , j=1
i =1,2,...,n , l =1,2,...,m ,
или, в матричной записи:
AX = B,
представляют собой решение системы, правые части которой - элементы столбца l матрицы B .
Нетрудно заметить, что приписав справа к матрице A матрицу B и используя схему Жордана, на месте матрицы A получим единичную матрицу, а на месте матрицы B - искомую матрицу X = A-1B .
где X и B - матрицы из n строк и m столбцов, причём элементы столбца l матрицы X
В частности, если B = E - единичная матрица |
||||
|
||||
|
|
|
|
|
размерности n ´ n , то таким образом легко |
||||
получаем обратную матрицу X = A-1 : |
||||
(A E)¾¾¾¾¾®(E |
A |
). |
||
|
схема Жордана |
-1 |
|
|
|
|
|
|
|
Метод Гаусса с выбором главного элемента.
Анализ влияния погрешностей округления
элемент»), был наибольшим по модулю.
на точность решения, полученного методом Гаусса, показывает, что это влияние можно уменьшить, если на
каждом шаге переставить уравнения так, |
|
чтобы коэффициент |
при xk , на который |
осуществляется деление («главный |
|
Постолбцовый выбор главного элемента можно |
|||
2.2) |
|
|
|
Для i = k ,…, n : |
|
||
произвести, если в вышеприведённом |
|||
алгоритме заменить п. 2 на: |
|
||
2.1) |
Положить z = 0. |
|
|
|
|
|
|
|
Если | aik | > z , положить z = | aik | и m = i . |
||
2.3) |
Если z = 0 , СТОП – «Решения нет». |
||
2.4) |
Если m > k , поменять местами bk |
и bm , а |
|
также akj и amj |
для j = k ,…, n . |
|
|
При этом, очевидно, исключается деление на 0.
Устойчивость алгоритма к вычислительным погрешностям можно ещё усилить, если
на каждом шаге выполнять деление на элемент, наибольший по модулю по всей матрице преобразуемой на данном шаге подсистемы.
Однако такая модификация метода Гаусса, называемая методом главных элементов, применяется довольно редко.
Количество операций в методе Гаусса
Рассмотрим 1-й шаг.
Количество делений 1-ой строки расширенной матрицы равно n.
Затем для каждой из оставшихся n -1 строк производится n умножений и n вычитаний – всего 2 n·(n -1) операций.
Значит, общее количество операций на первом шаге равно n + 2 n·(n -1) = 2 n2 – n .
Нетрудно заметить, что количество операций на втором шаге найдём, заменив в предыдущем выражении n на (n -1) , т.е. оно равно 2 (n -1)2 – (n -1) .
Продолжая таким образом, для шага n |
||
|
|
|
получим: 2·12 – 1 = 1 (одна операция |
||
деления). |
|
|
|
|
|
Итак, всего операций на прямом ходе: |
||
n |
n |
n |
Nпрям. = å2k 2 - k = 2åk 2 -åk . |
||
k =1 |
k =1 |
k =1 |
|
||
С учётом того, что |
|
|
|
||
|
|||||
åk 2 |
|
|
|
||
= n ×(n +1)×(2n +1), |
|||||
n |
|
|
|
|
|
k =1 |
|
n ×(n +1) |
6 |
||
n |
|
|
|
|
|
|
|
|
|
||
åk = |
|
2 |
|
, |
|
k =1 |
|
|
|
|
|
получим:
Nпрям. = n ×(n +16)×(4n -1).
Рассматривая матрицу системы, полученной в результате прямого хода, видим, что для
осуществления обратного хода требуется произвести столько умножений (и столько же вычитаний!), сколько имеется элементов над диагональю матрицы, т.е. количество операций на обратном ходе равно числу всех элементов матрицы, кроме диагональных:
Nобр. = n2 - n = n ×(n -1).