Добавлен: 06.02.2019
Просмотров: 4147
Скачиваний: 4
16
Особенности.
1) Под квадратным корнем может получиться отрицательное число,
следовательно в программе необходимо предусмотреть использование
правил действия с комплексными числами.
2) Возможно переполнение - если угловые элементы близки к нулю.
1.2 Итерационные методы решений систем алгебраических
уравнений
Итерационные методы обычно применяются для решения систем
большой размерности и они требуют приведения исходной системы к
специальному виду.
Суть итерационных методов заключается в том, что решение х системы
(1.1) находится как предел последовательности
x(n)
n
lim
.
Так как за конечное число итераций предел не может быть достигнут,
то задаётся малое число - точность, и последовательные приближения
вычисляют до тех пор, пока не будет выполнено неравенство
1
n
n
x
x
,
где n=n( ) – функция , х - норма вектора.
Прямые методы рассчитаны для решения систем, если её порядок не
больше 100, иначе используются итерационные методы.
1.2.1 Метод Якоби (простых итераций)
Исходную систему
Ах=В (1.11)
преобразуем к виду:
,
a
b
x
a
a
x
a
a
x
ii
i
j
m
i
j
ii
ij
i
j
j
ii
ij
i
1
1
1
(1.12)
где i=1,2,...,m; a
ii
0.
Первая сумма равна нулю, если верхний предел суммирования меньше
нижнего.
17
Так (1.12) при i=1 имеет вид
.
a
b
x
a
a
x
j
m
j
j
11
1
2
11
1
1
По методу Якоби (метод простых итераций)
1
n
i
x
(n+1 приближение х
i
)
ищем по формуле
.
a
b
x
a
a
x
a
a
x
i
j
m
i
j
ii
i
n
j
ii
ij
n
j
ii
ij
n
i
1
1
1
1
(1.13)
где n – номер итерации (0,1,…,); i=
m
,
1
.
Итерационный процесс (1.13) начинается с начальных значений
0
i
x
,
которые в общем случае задаются произвольно, но предпочтительнее, если за
0
i
x
взять свободные члены исходной системы.
Условие окончания счета:
n
i
x
n
i
x
i
max
1
,
где i=
m
,
1
.
1.2.2 Метод Зейделя
Система (1.11) преобразуется к виду (1.12) и организуем итерационную
процедуру, где неизвестные х
i
на n+1 шаге определяются по формулам
.
a
b
x
a
a
x
a
a
x
i
j
m
i
j
ii
i
n
j
ii
ij
n
j
ii
ij
n
i
1
1
1
1
1
(1.14)
Например,
,
a
b
x
a
a
x
n
j
m
j
j
n
i
11
1
2
11
1
1
(1.15)
,
x
a
a
a
b
x
a
a
x
n
n
j
m
j
j
n
1
1
22
21
22
2
3
22
2
1
2
(1.16)
и так далее.
18
Итерационные процессы (1.13) и (1.14) сходятся, если норма матрицы А
(А - матрица коэффициентов при неизвестных в правой части систем (1.13) и
(1.14)) удовлетворяет условию:
1
А
.
1.2.3 Матричная запись методов Якоби и Зейделя
Исходную матрицу системы (1.11) представим в виде суммы трёх
матриц
A=A
1
+D+A
2
,
где D - диагональная матрица;
D =diаg[а
11
а
22
…а
mm
];
A
1
- нижняя треугольная матрица;
A
2
- верхняя треугольная матрица.
Пример: Дана матрица размерности (3 3):
А
а
а
а
а
а
а
а
а
а
33
22
11
23
13
12
32
31
21
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
.
А
1
А
2
D
Тогда исходную систему (1.11) можно записать в виде
x=-D
-1
A
1
x – D
-1
A
2
x+D
-1
b.
Тогда метод Якоби можно записать в виде:
B
D
x
A
D
x
A
D
x
n
n
n
1
2
1
1
1
1
или
b
x
)
A
A
(
Dх
n
n
2
1
1
. (1.17)
В матричной форме метод Зейделя будет выглядеть:
b
1
D
n
x
2
A
1
D
1
n
x
1
A
1
D
1
n
x
или
19
b
х
А
х
)
А
D
(
n
n
2
1
1
. (1.18)
Преобразуем формулы (1.17) и (1.18):
b
n
Ах
)
n
x
n
D(х
1
, (1.19)
b
Ax
)
x
)(х
А
(D
n
n
1
n
1
. (1.20)
Из (1.19) и (1.20) видно, что если итерационный метод сходится, то он
сходится к точному решению. Иногда при решении задач большой
размерности, в итерационные методы вводятся числовые параметры, которые
могут зависеть от номера итерации.
Пример для метода Якоби.
B
Ax
t
x
х
D
n
1
n
n
n 1
,
где t – числовой параметр.
Возникают вопросы:
1) При каких значениях t сходимость будет наиболее быстрой?
2) При каких значениях t метод сходится?
На примере двух методов просматривается вывод о том, что одни и те же
методы можно записывать несколькими способами. Поэтому вводят
каноническую (стандартную) форму записи:
B
Ax
t
x
x
D
n
1
n
n
n
n
1
1
. (1.21)
Формула (1.21) получена путем объединения (1.19) и (1.20).
Матрица D
n+1
здесь задает тот или иной метод. Если существует
обратная матрица к этой матрице, то из последней системы мы можем найти
все неизвестные.
1. Метод (1.21) – явный, если матрица D
n
совпадает с единичной
матрицей и неявный - в противном случае.
2. Метод (1.21) – стационарный, если матрица D
n+1
= D, и параметр t не
зависит от номера итерации и нестационарный - в противном случае.
1.2.4 Метод Ричардсона
Явный метод с переменным параметром t:
20
B
Ax
t
x
x
n
n
n
n
1
1
, (1.21а)
называется методом Ричардсона.
1.2.5 Метод верхней релаксации (обобщённый метод Зейделя)
B
Ax
w
x
x
)
wA
D
(
n
n
n 1
1
, (1.21б)
где - числовой параметр.
Если матрица А - симметричная и положительно определена, то
последний метод сходится при (0 < < 2). Последнюю формулу запишем в
следующем виде:
B
wD
x
)
A
wD
E
)
w
((
x
)
A
wD
E
(
n
n
1
2
1
1
1
1
1
, (1.22)
где Е - единичная матрица.
Тогда для вычисления неизвестных х
i
(i=
m
,
1
) можно записать
итерационную процедуру в виде:
1
1
1
1
1
)
1
(
i
j
m
i
j
ii
i
n
j
ii
ij
n
i
n
j
ii
ij
n
i
a
b
w
x
a
a
w
x
w
x
a
a
w
x
. (1.23)
Например, для х
1
это будет такое выражение:
m
j
n
j
j
n
n
a
b
w
x
a
a
w
x
)
w
(
x
2
11
1
11
1
1
1
1
1
.
1.2.6 Сходимость итерационных методов
Рассмотрим систему
Ax=B,
где А - невырожденная действительная матрица.
Для решения системы рассмотрим одношаговый стационарный метод