Практикум j практическое примщенше численных методов

&п2	АпЗ
... 0 .
	■ 0	а>12	&13 •	.. й\п
	0	0	^23 •	• • &2п
и =	0	0	0 .	• • а3п
	. 0	0	0 .	.. о

С учетом (5.7) итерационный метод Якоби (5.5) записывается в каноническом виде (5.2) при
в = Д т_к+1 = 1.
Для итерационного метода Зейделя (5.6) имеем
В = D + L, т = 1.
Наиболее естественным обобщением рассматриваемых итерационных мето­дов является использование переменных итерационных параметров. В этом случае мы получим
_тк+1 _ _тк
D- + Ax^k = f, А; = 0,1,..., (5.8)
^тк+1
(D + Lf^K+1 ~^хк + Ах^к = /, А: = 0,1,.... (5.9)
?А:+1
Отметим также метод верхней релаксации
_rfc+i _ _тк
(.D + tL) + Ax^k = f, к = 0,1,.... (5.10)
т
который можно рассматривать как параметрическое обобщение итерацион­ного метода Зейделя.
Запишем стационарный итерационный метод (В_к = В, r_k+i = т в виде
x^k+l = Sx^k + B~^lf, к = 0,1,..., (5.11)
где S = Е — тВ~¹А — матрица перехода. Необходимым и достаточным усло­вием сходимости итерационного метода (5.11) является условие, чтобы спек­тральный радиус матрицы перехода S меньше единицы, т.е. когда все соб­ственные значения матрицы S но модулю меньше единицы.
Двухслойные итерационные методы
Приведем некоторые факты теории итерационных методов при решении за­дачи (5.1) с симметричной вещественной положительно определенной матри­цей А , т.е. когда
А = А*> 0. (5.12)
Метод простой итерации (стационарный итерационный метод) соответствует использованию в (5.2) постоянного итерационного параметра r^+i = т, т.е.
_Тк+1 _ _тк
В + Ах^к = /, А; = 0,1,.... (5.13)
Т
Итерационный метод (5.13) для решения задачи (5.1), (5.12) сходится в Я_л, т.е. ||г|| л —> 0 при к —> оо, если выполнено неравенство
в > ^Т-А. (5.14)
Будем считать, что при
В = В* > 0 (5.15)
и задана априорная информация об операторах В и А в виде двухстороннего операторного неравенства
ъВ <А< 7₂в, Ъ > 0, (5.16)
т
г = т₀


2
7i + 72 ’


(5.17)

.е. операторы В и А энергетически эквивалентны с постоянными энергетиче­ской эквивалентности 7_а, а = 1,2. Тогда итерационный метод (5.13) сходится в Я_я, R = А, В при 0 < т < 2/72 . Оптимальным значением итерационного параметра является
п
К > К₀(е)


\П£
In £>о ’


(5.18)

ри котором для числа итераций Я, необходимых для достижения точности е, справедлива оценка
г
во =


1-£
1+Г


72

де
Заметим, что в (5.18) К₀(е), вообще говоря, нецелое и К — минимальное це­лое, при котором выполнено К > К₀(е). Этот результат указывает путь опти­мизации сходимости итерационного процесса (5.13) за счет выбора оператора В в соответствии с (5.16), т.е. оператор В должен быть близок оператору Л по энергии.
Оптимальный набор итерационных параметров в нестационарном итерацион­ном методе (5.2) для приближенного решения задачи (5.1) при (5.12), (5.15) связан с корнями полиномов Чебышева, поэтому такой итерационный ме­тод называется чебышсвским итерационным методом (методом Ричардсона). Определим множество Мк следующим образом:
М
_к = j-cos
Для итерационных параметров т_к используется формула
П- = —- , ц_кеМ_к, к = 1,2,...,К. (5.19)
1 + воЦк
Чебышевский итерационный метод (5.2), (5.19) сходится в Нц, R = Д В и для числа итераций К, необходимых для достижения точности е, справедли­ва оценка
\
К>К₀(е) =

(5.20)

ni2e~¹)
In Q\
г
Q1


i~e^f2
1+f¹/²’


ъ
ъ'

де
Заметим, что в чебышевском методе (см., (5.19)) расчет итерационных пара­метров осуществляется по заданному общему числу итераций К. Естествен­но, что вырожденный^: случай К = 1 соответствует рассмотренному выше методу простой итерации. Практическая реализация чебышевского итераци­онного метода связана с проблемой вычислительной устойчивости, которая решается специальным упорядочиванием итерационных параметров (выбо­ром ц_к из множества Мк )•
Итерационные методы вариационного типа
Выше рассматривались итерационные методы решения задачи в условиях, когда задана априорная информация об операторах В и А в виде констант (см. (5.16)) энергетической эквивалентности 71 и 72. Через эти постоянные определяются оптимальные значения итерационных параметров (см. (5.17), (5.19)). В итерационных методах вариационного типа, в которых итерацион­ные параметры вычисляются без такой априорной информации.
Обозначая невязку r^k = Ax^k — / и поправку w^k = B~^lr^k, для итерационных параметров при естественном предположении о минимизации погрешности в Нц получим формулу
(
(5.21)


Tfc+1 =
.Rw^k,z^k)
(.Rw^k,w^k) *
Итерационный процесс (5.2) запишется следующим образом х^к+1 = х^к - T_k+iw^k, /с = 0,1,
Конкретизация итерационного метода достигается за счет выбора операто- pa R = R* >0. Этот выбор должен быть подчинен, в частности, условию возможности вычисления итерационных параметров. В формулу (5.21) вхо­дит невычисляемая величина z^k и поэтому простейший выбор R = В здесь не проходит. Вторая отмеченная выше возможность R = А приводит нас к итерационному методу скорейшего спуска, когда
к, г*)
^k+l (Aw^k,w^k)' ⁽ ' ²⁾
Среди других возможностей выбора R отметим случай R! = АВ~¹А — метод минимальных поправок, когда
(
(5.23)


^тк+1
i4iy^fc,iy^fe)
(.B~^lAw^k, Aw^k)
Двухслойный итерационный метод вариационного типа сходится не медлен­нее метода простой итерации, т.е. для числа итераций п, необходимых для достижения точности е, справедлива оценка (5.18).
В вычислительной практике наибольшее распространение получили трсх- слойные итерационные методы вариационного типа. По скорости сходимости они не хуже итерационного метода с чебышевским набором итерационных параметров.
В трехслойном (двухшаговом) итерационном методе новое приближение на­ходится по двум предыдущим. Для реализации метода требуются два началь­ных приближения х°,х^х. Обычно х° задается произвольно, а х¹ находится по двухслойному итерационному методу. Трехслойный метод записывается и следующей канонической форме трехслойного итерационного метода:
Bx^k+l = a_k+l{B - r_k+iA)x^k + (1 - a_k+i)Bx^k~¹ + a_k+1T_k+1ip,
к
(5.24)

= 1,2,...,
Вх¹ = (В — TiA)x° + Ti

где а_к+1 и т_к+1 — итерационные параметры.
В методе сопряженных градиентов итерационные параметры рассчитывают­ся по формулам
(
к = 0,1,...,