3237
.pdfСледующий шаг округления приводим при малом ведущем элементе ( 0.001) . Чтобы исключить x3 из третьего
уравнения, второе уравнение надо умножить на 2500. При умножении получим число 15002.5, которое нужно округлить до 5 разрядов. В результате третье уравнение получаем в виде:
15005x3 |
15004 . Откуда x3 |
15004 |
|
0.99993. Из второго и |
||||||||||||
|
|
|
|
|
||||||||||||
15005 |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
первого уравнений найдем: |
|
|
|
|
|
|
|
|
|
|||||||
x2 |
6 |
0.99993 |
6.001 |
0.0015 |
1.5 |
; |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
0.001 |
|
|
0.001 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
x1 |
7 |
( |
1.5) 7 |
0.35 . |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вычисления проводились с усечением до 5 разрядов по |
||||||||||||||||
аналогии |
с |
процессом |
|
|
вычислений |
на |
ЭВМ: |
|||||||||
( 0.35; |
1.5; 0.099993) вместо |
(0; 11;) . |
|
|
|
|
|
Такая большая неточность результатов объясняется малой величиной ведущего элемента. Чтобы в этом убедиться,
переставим уравнения системы: |
|
|
|
|
|
|
|
|
|||||||
|
|
10x1 |
|
7x2 |
|
|
|
7 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
2.5x2 |
|
5x3 |
2.5 |
|
0.0004. |
|
|
||||
|
|
|
|
0.001x2 |
6x3 |
6.001 |
|
|
|
|
|||||
Теперь |
|
получим |
|
третье |
уравнение |
в |
виде: |
||||||||
6.002x3 |
6.002 , т.е. |
x3 1. |
Из второго и третьего уравнений |
||||||||||||
находим: |
x2 |
2.5 5 1 |
1 и |
x1 |
7 |
7 ( 1) |
|
0 . |
Т.е., в |
||||||
|
|
|
|
|
|
|
|
||||||||
2.5 |
|
|
|
|
10 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
результате перестановки уравнений (выборе наибольшего по модулю из оставшихся в данном столбце элементов) погрешность решения в рамках данной точности исчезла.
Погрешность решения систем линейных уравнений методом Гаусса.
Запишем систему в матричном виде:
60
|
|
|
A x |
B . |
|
|
|
|
Ее решение имеет вид: |
x |
A 1B . Однако полученное по |
||||||
методу |
Гаусса |
решение |
x* |
отличается |
от данного из-за |
|||
погрешностей округления. |
|
|
|
|
|
|||
Имеются |
две общепринятые меры, |
характеризующие |
||||||
степень |
отклонения, |
полученного |
решения |
от точного, |
||||
погрешность |
и невязка |
: |
x |
x* |
и |
B Ax* - |
разность между левой и правой частями уравнений, после подстановки в них решения.
Можно показать, что если одна из этих величин равна 0 , то и другая должна равняться нулю. Однако из малости одной
не следует малость другой. При |
0 обычно |
0 , но |
обратное утверждение справедливо не всегда. |
|
|
В частности, для плохо обусловленных систем при |
0 |
|
погрешность решения м.б. большой. |
Однако если система не |
является плохо обусловленной, контроль точности решения осуществляется с помощью невязки.
3.3. Определитель и обратная матрица
Непосредственное нахождение определителя высокого порядка требует очень большого объема вычислений. Так, определитель n -го порядка обычно вводится как сумма элементов вида: a1. ,a2. ,..., an. , где пропущенные индексы
нужно заполнить произвольной перестановкой чисел 1,2,..., n . Т.о., определитель равен сумме n ! слагаемых, каждое из которых является произведением n элементов. Поэтому при вычислении определителя порядка n (без специальных правил)
требуется |
(n |
|
1) n! |
умножений |
и |
( n! 1 ) сложений, т.е. |
|||
общее |
число |
арифметических |
операций |
равно |
|||||
N n n! 1 |
n n!. |
|
|
|
|
|
|
||
Оценим |
N (см. таблицу 12): |
|
|
|
|
||||
|
|
|
|
|
|
Таблица 12 |
|
||
|
|
|
n |
3 |
10 |
|
20 |
|
|
|
|
|
N |
17 |
3.6 10 |
7 |
19 |
|
|
|
|
|
|
|
|
5 10 |
|
|
61
Если принять быстродействие в 100000 операций в
секунду, то для n |
10 потребуется около 6 мин., а при n 20 |
|||
- около 1.4 104 часов, |
т.е. свыше 5 109 суток или примерно |
|||
107 лет. |
|
|
||
Вместе с |
тем |
легко вычисляется определитель |
||
треугольной |
матрицы: он равен произведению ее |
|||
диагональных элементов. |
||||
Для приведения матрицы к треугольному виду м.б. |
||||
применен метод |
исключения, т.е. прямой ход метода Гаусса. |
|||
|
|
|
|
|
В процессе исключения элементов величина определителя не меняется. Знак определителя меняется на противоположный при перестановке его столбцов или строк. Поэтому
|
n |
|
det A |
ak k . |
|
|
k 1 |
|
Здесь диагональные |
элементы |
ak k берутся из |
преобразованной (а не исходной) матрицы. Знак зависит от того, четной или нечетной была суммарная перестановка строк (или столбцов) матрицы при ее приведении к треугольному виду.
Этим методом можно вычислять определители 100 -го и более высоких порядков.
Вычисление обратной матрицы A 1 . Обозначим элементы
обратной матрицы |
A 1 через |
|
zij . Тогда соотношение |
|||
AA 1 |
E можно записать в виде: |
|
|
|||
|
n |
|
1, |
i |
j, |
|
|
aik zk j ij , |
|
i, j 1,2,..., n . (3.4) |
|||
|
ij |
0, |
i |
j, |
||
k |
1 |
|
|
|||
|
|
|
|
|
Отсюда следует, что для нахождения одного столбца обратной матрицы надо решить линейную систему с матрицей A . Так, для элементов j - го столбца z1 j , z 2 j ,..., z nj надо
решить систему
62
a11 z1 j |
a12 z2 j |
... |
a1n znj |
0 |
|
.......... .......... .......... .......... .......... .. |
|
||||
a j1z1 j |
a j 2 z2 j |
... |
a jn znj |
1 |
(3.5) |
.......... .......... .......... .......... .......... .. |
|
||||
an1z1 j |
an2 z2 j |
... |
ann znj |
0. |
|
Следовательно, для обращения матрицы нужно n раз |
|||||
решить систему уравнений данного вида |
при j |
1,2,..., n . Так |
как матрица системы не меняется, то исключение неизвестных при использовании метода Гаусса (прямой ход) проводится только один раз. Для каждой системы делается только один раз обратный ход после некоторых преобразований с использованием правых частей систем вида (3.5).
Оценки показывают, что это весьма экономичный способ обращения матрицы. Он требует примерно лишь в три раза больше действий, чем при решении одной системы уравнений.
Метод прогонки. Он является модификацией метода Гаусса для частного случая разреженных систем - системы с трехдиагональной матрицей. Такие системы встречаются часто при решении некоторых инженерных задач, при интерполировании, при решении краевых задач для дифференциальных уравнений второго порядка.
Такие системы записывают в каноническом виде:
b1x1 |
c1x2 |
|
|
|
d1 |
|
|
a2 x1 |
b2 x2 |
c2 x3 |
|
|
d2 |
|
|
|
a3 x2 |
b3 x3 |
c3 x4 |
|
d3 |
(3.6) |
|
.......... .......... .......... .......... .......... .......... ....... |
|||||||
|
|||||||
|
an 1xn 2 |
bn 1xn 1 |
cn 1xn |
dn 1 |
|
||
|
|
|
an xn 1 |
bn xn |
dn . |
|
63
При |
этом a1 cn 0 . |
На главной диагонали матрицы |
|
этой системы элементы |
b1 , |
b2 ,..., bn , над ней - элементы c1 , |
|
c2 ,..., cn 1 , под ней - элементы |
a1 , a2 ,..., an . При этом обычно |
||
все коэффициенты bi |
0 . |
|
|
Метод прогонки состоит из двух этапов - прямой |
|||
прогонки |
(аналога прямого хода в методе Гаусса) и обратной |
прогонки (аналога обратного хода метода Гаусса).
Прямая прогонка состоит в том, что каждое неизвестное
xi выражается |
через |
|
xi |
1 |
|
|
с |
|
помощью |
прогоночных |
||||||||||||||||
коэффициентов Ai |
|
и |
Bi : |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
xi |
|
Ai xi 1 |
|
Bi |
|
( i 1,2,..., n |
|
1 ). |
|
|
(3.7) |
||||||||||||||
Из первого уравнения системы (3.6) найдем |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
x |
|
|
c1 |
x |
2 |
|
d1 |
. |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
1 |
|
|
b1 |
|
b1 |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
С другой стороны, |
по формуле (3.7) |
x1 |
A1x2 |
B2 . |
||||||||||||||||||||||
Приравнивая коэффициенты в обоих выражениях |
для |
x1 , |
||||||||||||||||||||||||
получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
|
|
c1 |
; |
|
|
B |
|
|
d1 |
. |
|
|
|
|
(3.8) |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
1 |
|
b1 |
|
|
|
|
1 |
|
|
b1 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Из второго уравнения системы (3.6) выразим |
x2 |
через |
||||||||||||||||||||||||
x3 , заменяя x1 |
|
по формуле (3.7): |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
a2 ( A1x2 B1) b2 x2 |
|
c2 x3 |
d2 . |
|
|
|||||||||||||||||
Отсюда |
x2 |
|
|
c2 x3 |
|
d2 |
|
|
a2 B1 |
|
или |
x2 |
A2 x3 |
B2 ; |
||||||||||||
|
|
|
a2 A1 |
b2 |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
A |
|
c2 |
|
; B |
2 |
|
d2 |
a2 B1 |
; |
l |
2 |
|
|
a |
2 |
A b . |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
2 |
|
l2 |
|
|
|
|
l2 |
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогично можно вычислить прогоночные коэффициенты для любого номера i :
64
A |
ci |
; B |
|
|
di |
ai Bi |
1 |
; |
l |
i |
a |
A |
1 |
b |
; i |
2,3,..., n |
1.(3.9) |
|||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||
i |
|
i |
|
|
li |
|
|
|
|
i i |
i |
|
|
|
|
|
|
|
|
|
||||||
|
li |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Обратная прогонка состоит в последовательном |
||||||||||||||||||||||||||
вычислении неизвестных x . Сначала нужно |
найти xn . Для |
|||||||||||||||||||||||||
этого воспользуемся (3.7) при i |
n |
1 |
и |
последним |
||||||||||||||||||||||
уравнением системы (3.6): xn 1 |
An 1xn |
|
Bn 1 . |
|
|
|
|
|
|
|
|
|||||||||||||||
Отсюда, |
|
|
|
исключая |
|
|
|
|
xn 1 , |
|
|
находим |
||||||||||||||
an ( An |
1xn |
Bn |
1) |
|
bn xn |
dn |
|
|
|
|
|
|
|
|
|
|
|
или |
||||||||
an ( An |
1xn |
Bn |
1) |
|
dn |
bn xn . Тогда |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
xn |
|
d n |
an Bn 1 |
. |
|
|
|
|
|
|
(3.10) |
|||||||||
|
|
|
|
|
|
|
bn |
an An 1 |
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Далее, |
используя |
формулы |
|
(3.7) |
и |
выражения |
для |
|||||||||||||||||||
прогоночных |
коэффициентов (3.8) |
|
и |
(3.9), последовательно |
||||||||||||||||||||||
вычисляем все неизвестные |
|
xn 1 , xn 2 ,...., x1 . |
|
|
|
|
|
|
|
|
||||||||||||||||
Можно показать, что при выполнении условия |
||||||||||||||||||||||||||
преобладания |
диагональных |
элементов: |
|
bi |
|
ai |
|
ci |
|
, |
||||||||||||||||
|
|
|
|
|||||||||||||||||||||||
причем |
хотя бы для одного значения |
i |
имеет место строгое |
|||||||||||||||||||||||
неравенство, деления на нуль в (3.9) |
не возникает |
и |
система |
(3.6) имеет единственное решение. Приведенное условие преобладания диагональных элементов обеспечивает также устойчивость метода прогонки относительно погрешностей округления. Это позволяет использовать метод прогонки для решения больших систем уравнений.
Данное условие устойчивости является достаточным, но не необходимым.
Пример. Решить систему уравнений
2x1 |
2x2 |
|
|
1 |
x1 |
x2 |
0.5x3 |
0 |
|
|
x2 |
3x3 |
x4 |
2 |
|
|
x3 |
2x4 |
2. |
65
Решение. Матрица этой системы имеет вид:
|
2 |
2 |
0 |
0 |
|
1 |
1 |
0.5 |
0 |
A |
0 |
1 |
3 |
1 . |
|
0 |
0 |
1 |
2 |
Найдем |
A1 |
c1 |
1; |
B1 |
|
d1 |
|
1 |
(по 3.8). |
b1 |
|
b1 |
2 |
||||||
|
|
|
|
|
|
||||
Вычисляем остальные прогоночные |
|
коэффициенты по |
|||||||
формулам (3.9) |
с точностью до 5 |
знаков после запятой: |
A2 |
|
c2 |
|
|
|
|
c2 |
|
|
|
|
|
|
0.5 |
|
|
|
0.25000 |
; |
|
|||||
|
l2 |
|
|
a2 A1 |
b2 |
|
|
1 ( 1) 1 |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
B2 |
d2 |
a2 B1 |
|
|
0 |
( |
1) |
0.5 |
|
0.25000; |
|
|
|
|
|||||||||||
a2 A1 |
b1 |
1 ( |
1) |
|
1 |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
A3 |
|
|
c3 |
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
0.363636 |
; |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
a3 A2 |
|
b3 |
|
|
1 0.25 |
( |
3) |
2.75 |
|
|
||||||||||||
B3 |
|
d3 |
a3 B2 |
|
|
2 |
1 0.25 |
|
|
|
1.75 |
|
|
0.63636. |
|
||||||||||
|
a3 A2 |
b3 |
1 0.25 |
( |
3) |
|
|
2.75 |
|
||||||||||||||||
|
|
|
|
|
|
|
|
Для начала обратного хода находим x4 по формуле (3.10)
x4 |
d4 |
a4 B3 |
|
2 |
1 |
( |
0.63636) |
1.61111. |
|
b4 |
a4 A3 |
2 |
1 |
( |
0.36364) |
||||
|
|
Далее по формуле (3.7) находим остальные неизвестные, используя найденные прогоночные коэффициенты:
x3 |
A3 x4 |
B3 |
0.36364 1.61111 |
0.63636 |
1.22222; |
|
x2 |
A2 x3 |
B2 |
0.25 ( 1.22222) |
0.25 |
0.05555; |
|
x1 |
A1x2 |
B1 |
1.0000 ( 0.05555) 0.50000 |
0.55555. |
66
Другие методы (прямые). Имеется много других прямых методов решения задач линейной алгебры.
1.Метод оптимального исключения удобен при построчном введении матрицы в оперативную память. При этом экономится объем памяти, но сильно увеличивается время расчета за счет обращений к внешней памяти.
2.Метод квадратного корня используется, если матрица системы симметрична.
3.Метод Жордана имеет ту же скорость, что и метод Гаусса. При решении систем он не дает никаких преимуществ. Но при обращении матрицы требует меньшей оперативной памяти.
4.Клеточные методы могут использоваться для решения больших систем, когда матрица и вектор правых частей целиком не помещаются в оперативной памяти.
Эти и другие методы решения систем линейных уравнений подробно описаны в специальной литературе по линейной алгебре.
Для решения хорошо обусловленных линейных систем общего вида метод Гаусса является одним из лучших.
3.4. Итерационные методы
Прямые методы дают решение в виде точных формул через коэффициенты системы (правило Крамера, метод Гаусса и его разновидности и др.). Однако точное решение здесь м.б. получено при двух условиях:
1.Коэффициенты системы имеют точные значения;
2.Вычисления выполняются с бесконечным числом разрядов.
На практике оба этих условия обычно не выполняются. Поэтому неизбежны ошибки округления даже при использовании точных методов. Причем оценка погрешностей может быть затруднительной.
67
Прямым методам свойственны и |
“собственные” |
недостатки: |
|
1)Как правило, они требуют хранения в оперативной памяти ЭВМ всей матрицы, что при больших ее размерах ( n ) требует много места в памяти;
2)Прямые методы обычно не учитывают структуру матрицы - при большом числе нулевых элементов в разряженных матрицах (клеточных, ленточных) эти элементы занимают место в памяти машины и над ними выполняются операции;
3)Накапливание погрешностей в процессе решения, так как вычисления на любом этапе используют результат предыдущих операций.
В связи с этим прямые методы используют для сравнительно небольших систем ( n 200 ) с плотно заполненной матрицей и не близким к нулю определителем.
Итерационные методы используют некоторое начальное приближение. Затем с помощью соответствующего алгоритма проводится один цикл вычислений - итерация. В результате получается новое приближение. Итерации повторяют до получения решения с заданной точностью.
Достоинства:
1)Итерационные методы требуют хранения в памяти машины не всей матрицы, а лишь нескольких ее строк.
2)Погрешности окончательных результатов в этих методах не накапливаются, так как точность вычислений в каждой итерации определяется лишь результатами предыдущей итерации и практически не зависит от ранее выполненных вычислений.
Недостаток: скорость сходимости итераций может быть очень малой.
Часто используют смешанные методы, применяя итерационные методы для уточнения результатов, полученных прямыми методами.
68
|
Метод |
простых |
|
|
итераций |
для линейных |
систем. |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Рассмотрим систему: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
a11 x1 |
|
a12 x2 |
.... |
|
|
|
|
a1n xn |
|
|
|
b1 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
a21 x1 |
|
a22 x2 |
.... |
|
|
|
a2n xn |
|
|
|
b2 |
|
|
|
|
|
|
|
|
|
(3.11) |
||||||||||||
.......... .......... .......... .......... .......... |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
an1x1 |
|
an2 x2 |
.... |
|
|
|
ann xn |
|
|
|
bn . |
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
Разделим первое уравнение в (3.11) на a11 , второе на a22 |
||||||||||||||||||||||||||||||||||
и т.д. Получим: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
x |
|
a12 |
x |
2 |
a13 |
|
x |
3 |
... |
|
a1n |
x |
n |
|
b1 |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
1 |
a11 |
|
a11 |
|
|
a11 |
|
a11 |
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
x |
2 |
|
a21 |
|
x |
|
|
a23 |
|
x |
3 |
... |
|
|
a2n |
x |
n |
|
|
b2 |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
a22 |
1 |
|
|
a22 |
|
|
|
|
a22 |
|
|
|
a22 |
|
|
|
(3.12) |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
.......... .......... .......... .......... .......... .......... ....... |
|
|
|
|
|
||||||||||||||||||||||||||||||
|
x |
n |
|
an1 |
x |
|
|
an2 |
x |
2 |
... |
|
|
|
ann 1 |
x |
n 1 |
|
bn |
. |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
ann |
1 |
|
|
ann |
|
|
|
|
|
|
ann |
|
|
ann |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
Замечание. |
|
Выделение в 1-ом |
|
уравнении x1 , во 2-ом - |
x2 и т.д. не всегда будет самым удачным. Иногда желательно
делить на возможно большие по модулю коэффициенты. При этом прибегают к перенумерации переменных.
Пусть с помощью некоторого прямого метода вычислены приближенные значения неизвестных x10 , x20 ,..., xn0 . Часто в
качестве нулевого приближения берут столбец из свободных членов. Далее последовательно получаются приближения (в матричной форме):
X (1) |
A X (0) |
B |
X (2) |
A X (1) |
B |
...................................... |
|
(3.13) |
X ( k ) |
A X (k 1) |
B |
69