ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4725
Скачиваний: 6
Лекция 9
71
и т.д.
Выбор главного элемента по строке. Перед исключением
x
1
отыскива-
ется
max
j
|a
1j
|· Пусть максимум достигается при j = j
0
. Тогда поменяем
взаимно номера у неизвестных
x
1
и
x
j
0
(максимальный по величине из
коэффициентов 1-го уравнения окажется в позиции
a
11
) и приступим к
процедуре исключения
x
1
, и т.д. Наиболее надежным является метод ис-
ключения с выбором главного элемента по всей матрице коэффициентов
на каждом шаге исключения.
Рассмотренные модификации метода Гаусса позволяют, как правило,
существенно уменьшить неблагоприятное влияние погрешностей округле-
ния на результаты расчета.
Впрочем, в прикладных задачах довольно часто приходится сталки-
ваться с линейными системами, при решении которых можно не забо-
титься о «вредном» воздействии неустранимых погрешностей на решение,
спокойно применяя простейшую схему гауссова исключения (без выбора
главного элемента). Это системы, для матриц которых выполнено условие
диагонального преобладания:
|a
ii
| >
X
j
6=i
|a
ij
| для всех i = 1, n.
Можно показать, что условие диагонального преобладания остается спра-
ведливым после каждого шага исключений в процессе приведения матри-
цы к треугольному виду, т.е.
|a
(k)
ii
| >
n
X
j = k
j
6= i
|a
(k)
ij
| i = k, n
для всех
k = 1, n
− 1. Это означает, что перед каждым исключением оче-
редной неизвестной главный элемент будет находиться в «нужной пози-
ции».
Количество арифметических операций
зависит от вида исходной
матрицы
Лекция 9
72
I. Диагональная матрица.
a
11
0
· · ·
0
0
a
22
· · ·
0
...
... ... ...
0
0
· · · a
nn
x
1
x
2
...
x
n
=
f
1
f
2
...
f
n
,
x
k
= f
k
/a
kk
.
Для вычисления каждой переменной
x
k
,
k = 1, 2, . . . , n требуется одно
деление. Всего потребуется
n операций деления.
II. Треугольная матрица.
a
11
a
12
· · · a
1n
0
a
22
· · · a
2n
...
... ... ...
0
0
· · · a
nn
x
1
x
2
...
x
n
=
f
1
f
2
...
f
n
,
x
n
= f
n
/a
nn
,
x
n
−1
= (f
n
−1
− a
n
−1,n
x
n
)/a
n
−1,n−1
,
Для нахождения
x
n
требуется одно деление. Для вычисления
x
n
−1
требу-
ется 3 операции (1 разность, 1 умножение, 1 деление). Для вычисления
x
n
−2
требуется 5 операций и т.д. Всего потребуется
n
P
k=1
(2k
− 1) = n
2
ариф-
метических операций.
III. В общем случае, когда матрица имеет много ненулевых элементов, по-
требуется прямой и обратный ходы метода Гаусса. Точный расчёт говорит,
что потребуется в общем случае
1
6
n(n
− 1)(4n + 7). Для больших n 10
оценка приближённо равна
1
6
n
· n · 4n =
2
3
n
3
.
1.9.4
Погрешность численного решения СЛАУ
Погрешность входных данных
Оценим неустранимую погрешность решения СЛАУ. Источниками неустра-
нимой погрешности являются не только округления при выполнении ма-
шинных операций, но также ошибки, содержащиеся в исходных данных.
Разберёмся сначала с последними, предполагая, что арифметические опе-
рации выполняются точно.
Итак, пусть вместо системы
Ax = f
(9.2)
Лекция 9
73
решается задача
(A + δA)(x + δx) = f + δf .
(9.3)
Здесь
δA — матрица возмущений, моделирующих ошибки коэффициентов
исходной СЛАУ (9.2),
δf — соответственно возмущения правых частей,
δx — обусловенный этими возмущениями вектор «ошибок», отличающий
решение (9.3) от решения (9.2).
Переписывая (9.3) в виде
Ax + A
· δx + δA · x + δA · δx = f + δf
и вычитая из последнего соотношения (9.2), приходим к системе уравне-
ний
Aδx + δA
· δx = δf − δA · x,
(9.4)
которая описывает зависимость
δx от возмущений (ошибок) исходных
данных.
Далее будем полагать, что возмущения коэффициентов уравнений
δA и
погрешности решения
δx в достаточной мере малы так, что в уравнениях
(9.4) можно пренебречь квадратичными членами
δA
· δx. Тогда интересу-
ющую нас ошибку
δx можно представить в виде
δx
≈ A
−1
(δf
− δA · x).
Вводя в рассмотрение нормы векторов и согласованные с ними нормы
матриц, получим оценку величины погрешности:
kδxk ≈ kA
−1
(δf
− δA · x)k
6
kA
−1
k(kδfk + kδAk · kxk) =
=
kA
−1
k ·
kfk
kδfk
kfk
+
kAk
kδAk
kAk
kxk
.
Учитывая, что
kfk = kAxk
6
kAk · kxk, получаем далее
kδxk
6
kA
−1
k ·
kAk · kxk
kδfk
kfk
+
kAk · kxk
kδAk
kAk
. =
=
kA
−1
k · kAk · kxk
kδfk
kfk
+
kδAk
kAk
.
Лекция 9
74
В итоге оценка для относительной погрешности решения может быть за-
писана в виде
kδxk
kxk
.
µ
A
kδfk
kfk
+
kδAk
kAk
,
(9.5)
где
µ
A
=
kA
−1
k · kAk. Значение µ
A
называется числом обусловленности
матрицы
A. Именно эта величина определяет, насколько сильно погреш-
ности входных данных могут повлиять на решение системы (9.2).
Всегда
µ
A
>
1. В самом деле, имеем E = A
−1
A. Отсюда 1 =
kEk =
kA
−1
A
k
6
kA
−1
k·kAk = µ
A
. Если значение
µ
A
является умеренным (
µ
A
∼
1
÷ 10), ошибки входных данных слабо сказываются на решении; система
(9.2) в этом случае называется хорошо обусловленной. Если
µ
A
велико
(
µ
A
>
10
3
), система (9.2) плохо обусловлена, решение её сильно зависит
от ошибок в правых частях и коэффициентах.
З а м е ч а н и е 1 . Вообще говоря, более точное представление о хорошей
или плохой обусловленности системы должно опираться на требования,
предъявляемые к решению. Если, к примеру, погрешность входных дан-
ных
∼ 10
−6
, а допустимая погрешность решения
∼ 10
−2
, то даже при
µ
∼ 10
4
систему можно считать хорошо обусловленной.
З а м е ч а н и е 2 . Хотелось бы подчеркнуть, что данная свойство (обу-
словленность), выражаемое неравенством (9.5), никак не связано с пред-
полагаемым методом решения системы, а является изначальной характе-
ристикой решаемой задачи.
Пример.
Рассмотрим систему
(
100x
1
+ 99x
2
= 199,
99x
1
+ 98x
2
= 197.
Её решение
x
1
= x
2
= 1.
Изменим теперь слегка её правые части
(
100x
1
+ 99x
2
= 198,99,
99x
1
+ 98x
2
= 197,01.
Решение «искажённой» системы
x
1
≈ 2,97, x
2
≈ 0,99.
Лекция 9
75
Чтобы сопоставить полученные результаты с оценкой
||δx||
||x||
6
µ
A
||δf||
||f||
,
будем пользоваться следующими согласованными нормами для векторов
и матриц
||x||
∞
= max
i
|x
i
|, ||A||
∞
= max
i
X
j
|a
ij
|.
Для рассмотреного примера имеем
f
=
199
197
!
, δf =
−0, 01
0,01
!
,
||f||
∞
= 199,
||δf||
∞
= 0,01.
Относительная погрешность
||δf||
∞
||f||
∞
≈
1
2
· 10
−4
= 0,005%. Это очень малая
величина.
Далее,
||A||
∞
= 199,
det A =
−1, A
−1
=
−98
99
99
−100
!
,
||A
−1
||
∞
= 199,
µ
A
= (199)
2
= 39601
≈ 4 · 10
4
.
Используя оценку, получим относительную погрешность решения
||δx||
∞
||x||
∞
6
4
· 10
4
·
10
−4
2
= 2 = 200%. Это согласуется с результатами решения рассмот-
ренных систем.
Погрешность округления при арифметических операциях
Можно показать, что полученное с помощью компьютера решение x
0
=
x
+ δx СЛАУ, вычисленное методом Гаусса (с той или иной схемой выбора
главного элемента или вообще без выбора), точно удовлетворяет уравне-
ниям с определённым образом возмущёнными коэффициентами
(A + δA)(X + δx) = f .
Для нормы матрицы так называемых эквивалентных возмущений
δA спра-
ведлива оценка вида
kδAk ≈ ng(A)kAkp
−t
.
Здесь
n — порядок системы, p — основание машинной арифметики (как
правило,
p = 2), t — число значащих цифр, учитываемых при выполнении