Добавлен: 06.02.2019
Просмотров: 4146
Скачиваний: 4
21
B
Ax
t
x
x
D
n
n
n 1
, (1.24)
при n=0,1,2….
Предположим, что задан начальный вектор решения. Тогда метод
(1.24) сходится, если норма вектора
.
x
x
n
n
0
Теорема. Условие сходимости итерационного метода.
Пусть А - симметричная положительно определенная матрица и
выполнено условие D - 0.5tA > 0 (где t > 0). Тогда метод (1.24) сходится.
Следствие 1. Пусть А - симметричная и положительно определенная
матрица с диагональным преобладанием, то есть:
m
j
i
i
|
ij
a
|
|
jj
a
|
1
,
при j=1,2,…,m. Тогда метод Якоби сходится.
Следствие 2. Пусть А - симметричная и положительно определенная
матрица с диагональным преобладанием, тогда метод верхней релаксации
сходится при (0< <2).
Проверяется, при каком - метод достигает заданной точности быстрее.
В частности, при =1 метод верхней релаксации превращается в метод
Зейделя, следовательно, при =1 метод Зейделя сходится.
Теорема. Итерационный метод (1.24) сходится при любом начальном
векторе x
0
тогда и только тогда, когда все собственные значения матрицы
A
tD
E
S
1
по модулю меньше единицы.
22
2 Плохо обусловленные системы линейных алгебраических
уравнений
Дана система линейных алгебраических уравнений
Ах=В. (2.1)
Если система плохо обусловлена, то это значит, что погрешности
коэффициентов матрицы А и правых частей B или же погрешности их
округления сильно искажают решение системы. В качестве примера
рассмотрим систему
.
.
x
.
x
.
.
x
.
x
.
41
2
943
0
991
0
51
2
991
0
03
1
2
1
2
1
Решение этой системы
x
1
1.981
x
2
0.4735.
Оценим влияние погрешности правых частей на результат. Рассмотрим
“возмущенную” систему с правой частью b
*
= (2.505 , 2.415) и решим эту
систему:
x
1
*
2.877
x
2
*
-0.4629.
Относительная погрешность правой части (в) = 0.005/2.51 0.28%
привела к относительной погрешности решения (x
*
) =0.9364/1.981 47.3%.
Погрешность возросла примерно в 237 раз. Число обусловленности
системы (2.1) приблизительно равна 237.
Подобные системы называются плохо обусловленными.
х
1
а) х
1
б) х
1
с)
1)
2)
3)
х
2
х
2
Рисунок 2 - а) система имеет единственное решение;
б) система не имеет решения;
с) система плохо обусловлена.
х
2
23
В случае с) малейшее возмущение системы сильно меняет положение
точки пересечения прямых. Встаёт задача – какими методами можно решать
эти системы.
Для оценки обусловленности системы вводят число обусловленности
M
А
А
А
М
А
1
.
Чем больше M
А
, тем система хуже обусловлена.
Свойства числа обусловленности:
1) М
Е
=1;
2) M
А
1;
3) M
А
min
max
|
/
|
, где
мах
,
min
- соответственно максимальное и
минимальное собственные числа матрицы А;
4) M
АВ
M
А
* M
В
;
5) Число обусловленности матрицы А не меняется при умножении
матрицы на произвольное число
0.
Найдем выражение для полной оценки погрешности решения системы.
Пусть в системе (2.1) возмущены коэффициенты матрицы А и правая часть
В, т.е.
A
A
~
A
δ
,
B
B
~
B
δ
,
x
x
~
x
δ
.
Теорема. Пусть матрица
А
имеет обратную матрицу, и
выполняется условие
1
1
A
A
. Тогда матрица
A
A
А
~
имеет
обратную и справедлива следующая оценка относительной погрешности:
B
B
A
A
A
A
M
M
x
x
A
A
1
.
2.1 Метод регуляризации для решения плохо обусловленных
систем
Рассмотрим систему
Ах=В. (2.1)
Для краткости перепишем эту систему в эквивалентный форме
0
)
B
Ax
,
B
Ax
(
. (2.2)
Для примера рассмотрим систему
24
2
2
1
2
2
1
1
1
x
x
x
x
.
Тогда ее можно представить как
(2х
1
-х
2
-1)
2
+(х
1
-2х
2
-2)
2
=0. (2.2*)
Решение системы (2.2) совпадает с решением системы (2.2*).
Если коэффициенты A или B известны неточно, то решение также
является не точным, поэтому вместо равенства
0
)
,
(
B
Ax
B
Ax
можем
потребовать приближенного выполнения равенства
0
)
,
(
B
Ax
B
Ax
и в
этом виде задача становится не определенной и нужно добавить
дополнительные условия.
В качестве дополнительного условия вводят требование, чтобы
решение как можно меньше отклонялось от заданного х
0
т.е. (х-х
0
, х-х
0
) было
минимальным. Следовательно, приходим к регуляризованной задаче вида
(Ах-B, Ax-B)+ (x-x
0
, x-x
0
)=min, (2.3)
где >0.
Используя свойства скалярного произведения, выражение (2.3)
перепишем в виде
(x,A
T
Ax)-2(x,A
T
B)+(B,B)+ [(x,x)-2(x,x
0
)+(x
0
,x
0
)]=min. (2.4)
Варьируя x в уравнении (2.4), получим уравнение вида
(A
T
А+ E)x=A
T
B+ x
0
. (2.5)
Система (2.5) – система линейных алгебраических уравнений,
эквивалентная системе (2.1). Систему (2.5) решаем с помощью метода Гаусса
или с помощью метода квадратных корней. Решая систему (2.5) найдем
решение, которое зависит от числа .
Выбор управляющего параметра
. Если
=0, то система (2.5)
перейдет в плохо обусловленную систему (2.1).
Если же –велико, то система (2.5) переходит в хорошо обусловленную
систему и решение этой системы может сильно отличаться от решения
системы (2.1).
Оптимальное значение – это такое число, при котором система (2.5)
удовлетворительно обусловлена.
На практике пользуются невязкой вида
B
Ax
r
, и эту невязку
сравнивают по норме с известной погрешностью правых частей
B
и с
влиянием погрешности коэффициентов матрицы
А
.
Если – слишком велико, то
||
||
||
||
B
r
или ||
А
||. Если – мало, то
||
||
||
||
B
r
или ||
А
||.
25
Поэтому проводят серию расчетов, при различных
и в качестве
оптимального значения выбирают то значение
, когда выполнено
следующее условие
A
B
r
.
Для выбора вектора х
0
нужно знать приближенное решение или же,
если приближенное решение трудно определить, то х
0
=0.
2.2 Метод вращения (Гивенса)
Метод Гивенса как и метод Гаусса состоит из прямого и обратного
ходов.
Прямой ход метода. Исключаем неизвестное
х
1
из всех уравнений,
кроме первого. Для исключения
х
1
из 2-го уравнения вычисляют числа
2
21
2
11
11
12
a
a
a
,
2
21
2
11
21
12
a
a
a
,
где и такие, что
1
2
12
2
12
,
0
21
12
11
12
.
Первое уравнение системы заменяем линейной комбинацией первого и
второго уравнений с коэффициентами
12
и
12
,а второе уравнение такой же
комбинацией с
12
и -
12
. В результате получим систему
m
m
mm
m
m
m
m
m
)
(
m
)
(
m
)
(
)
(
m
)
(
m
)
(
)
(
b
x
a
...
x
a
x
a
.
.
.
.
.
.
.
.
.
b
x
a
...
x
a
x
a
b
x
a
...
x
a
b
x
a
...
x
a
x
a
2
2
1
1
3
2
32
1
31
1
2
1
2
2
1
22
1
1
1
1
2
1
12
1
1
11
. (2.6)
Здесь
,
b
b
b
,
b
b
b
,
a
a
a
,
a
a
a
)
(
)
(
j
j
)
(
j
j
j
)
(
j
1
12
2
12
1
2
2
12
1
12
1
1
1
12
2
12
1
2
2
12
1
12
1
1
где j=
m
,
1
.
Преобразование системы (2.1) к системе (2.6) эквивалентно
умножению матрицы A и вектора B слева на матрицу С
12
вида