А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 6
Текст из файла (страница 6)
•. , где к — номер4.1.Итерационное решение систем линейных уравнений49Основные обозначениях = {х .} = {*\ Х2,. . . ,Х„(А = {aij}ЕD = diag{d| ,d2,...,dn}— n-мерный вектор— матрица с элементами ац— единичная матрица— диагональная матрицаIHI — норма вектора хNI — норма матрицы А— приближенное решение на fc-ойитерацииг* = х* - х — погрешность приближенногорешениег = Axk - f — невязка на fc-ой итерациит,П — итерационные параметрыXитерации.
Значения х* +| определяются по ранее найденным хк, х*" 1 ,....Если при вычислении х* +| используются только значения на предыдущейитерации х*, то итерационный метод называется одношаговым (двухслойным). Соответственно, при использовании хк и хк~х итерационный методназывается двухшаговым (трехслойным).Двухслойный итерационный метод записывается в следующей канонической формеВх* +| - хк+Axk = f,* = 0,1,....(4-2)Для характеристики точности приближенного решения естественно ввести погрешность zk — хк — х. Будем рассматривать сходимостьитерационного метода в энергетическом пространстве Яд, порожденном симметричной и положительно определенной матрицей R. В Ядскалярное произведение и норма есть(у, w)R = (Ry, w),\\y\\R= у/(у,у)я•Итерационный метод сходится в Яд, если \\zk\\R -* 0 при к -* со.В качестве меры сходимости итераций принимают относительную по-Глава 4.
Итерационные методы линейной алгебры50грешность е, так что на K-oPi итерации11**-*ЦЯ<Ф°-*11Л-(4-3)В силу того, что само точное решение х неизвестно, оценка точностиприближенного решения проводится по невязкегк = Ахк - f - Ахк - Ах,которая может быть вычислена непосредственно. Например, итерационный процесс проводится до выполнения оценкиИКФ'Н-(4-4)Использование критерия сходимости (4.4) соответствует выбору R = А* Ав (4.3). Минимальное число итераций, которое гарантирует точность е(выполнение (4.3) или (4.4)), обозначим К{е).При построении итерационного метода мы должны стремиться к минимизации вычислительной работы по нахождению приближенного решения задачи (4.1) с заданной точностью.
Пусть Qk — число арифметических действий для нахождения приближения хк и пусть делаетсяК ^ К(е) итераций. Тогда общие затраты оцениваются величинойк«(*) = £<?*•Применительно к двухслойному итерационному методу (4.2) минимизация Q(e) может достигаться за счет выбора операторов В* и итерационныхпараметров тк+\. Обычно матрицы В* (переобуславливатели) задаютсяиз каких-либо соображений близости к матрице А, а оптимизация итерационного метода (4.2) осуществляется за счет выбора итерационныхпараметров.4.2.
Итерационные алгоритмы решениясистем линейных уравненийРассматриваются традиционные итерационные методы решения системлинейных уравнений — метод Якоби и метод Зейделя. Приведены основные результаты о скорости сходимости итерационных методов при решении задач с вещественной симметричной положительно определенной4.2. Итерационные алгоритмы линейной алгебры51матрицей. Приводится оптимальный выбор постоянных и переменныхитерационных параметров. Второй класс итерационных методов связанс определением итерационных параметров на каждом итерационном шаге из минимума функционалов для невязки — итерационные методывариационного типа.4.2.1.
Классические итерационные методыВ итерационном методе Якоби новое приближение на (к+ 1)-ой итерацииопределяется из условийi-iJ2 а{]х) + o,iX*+l + ^2 aijXkj = f,7=1i = 1,2,..., п.(4.5)j=i+\Тем самым следующее приближение для отдельной компоненты вектораопределяется из соответствующего уравнения системы, когда все другиекомпоненты берутся с предыдущей итерации.Метод Зейделя основан на том, что найденное приближение для компонент вектора сразу же задействуются в вычислениях:J2 ацх)+х + ацх\+х + J2 auxi = / .J=lt = 1,2,..., п.(4.6)7=i+lДля записи итерационных методов (4.5), (4.6) используется следующее разложение матрицы А:(4.7)A = L + D + U.Здесь D = diag{aii,o 2 2,-. ,Onn} — диагональная часть матрицы А, а Lи U — нижняя и верхняя треугольные матрицы с нулевыми элементамина главной диагонали, т.
е.0L=«21000-31a32000ttnlа>п2апз. .. .. .000.0•52Глава 4. Итерационные методы линейной алгебры0 а120 00 0и=0а\з•• •«2п0.«Зп0. .»2з0•O-ln0С учетом (4.7) итерационный метод Якоби (4.5) записывается в каноническом виде (4.2) приВ = D,rk+i = 1.Для итерационного метода Зейделя (4.6) имеемB = D + L,т = 1.Наиболее естественным обобщением рассматриваемых итерационных методов является использование переменных итерационных параметров. В этом случае мы получимж*+1 - хк+ Ax=f,D-fc(4.8)= 0,l,...Тк+1(D + L)**+' - хк+ Axk = f,k=0,l,....(4.9)T*+|Отметим также метод верхней релаксации(D + TL)xk+i~xk+ Ax* = f,к=0,1,...,(4.10)который можно рассматривать как параметрическое обобщение итерационного метода Зейделя.Запишем стационарный итерационный метод (Дь = В, тк+1 = тв виде.*+'5х*+В-1/,* = 0, !,•••>(4.11)где 5 = Е - тВ~{А — матрица перехода.
Необходимым и достаточнымусловием сходимости итерационного метода (4.11) является условие,чтобы спектральный радиус матрицы перехода 5 был меньше единицы,т.е. когда все собственные значения матрицы 5 по модулю меньшеединицы.4.2. Итерационные алгоритмы линейной алгебры534.2.2. Двухслойные итерационные методыПриведем некоторые факты теории итерационных методов при решениизадачи (4.1) с симметричной вещественной положительно определеннойматрицей А , т. е. когдаА = А*>0.(4.12)Метод простой итерации (стационарный итерационный метод) соответствует использованию в (4.2) постоянного итерационного параметраTfc+i = т , т.е.хк+\ _ *В+Axk=f, fc = 0 , l , .
. . .(4.13)тИтерационный метод (4.13) для решения задачи (4.1), (4.12) сходитсяв НА, т.е. ||z|| A —* О при к —» сю, если выполнено неравенствоВ>Т-А.(4.14)Будем считать, чтоВ = В*>0(4.15)и задана априорная информация об операторах В и А в виде двухстороннего операторного неравенства-y,B^A^j2B,7i > 0,(4-16)т. е. операторы В и А энергетически эквивалентны с постоянными энергетической эквивалентности j a , a= 1,2.
Тогда итерационный метод (4.13)сходится в Яд, R = А, В при 0 < т < 2/7г- Оптимальным значениемитерационного параметра является(4.17)т = т0 =7i +72при котором для числа итераций К, необходимых для достижения точности е, справедлива оценкаК^К0(е) = ~ ,in e0(4.18)Глава 4. Итерационные методы линейной алгебры54где1-е1+£7172eo = -r—z, е? = —•Заметим, что в (4.18) К0(е), вообще говоря, нецелое и К — минимальное целое, при котором выполнено К > -Ко(е). Этот результатуказывает путь оптимизации сходимости итерационного процесса (4.13)за счет выбора оператора В в соответствии с (4.16), т.е. оператор Вдолжен быть близок оператору А по энергии.Оптимальный набор итерационных параметров в нестационарномитерационном методе (4.2) для приближенного решения задачи (4.1)при (4.12), (4.15) связан с корнями полиномов Чебышева, поэтому такойитерационный метод называется чебышевским итерационным методом(методом Ричардсона).
Определим множество Мк следующим образом:X* = {-cos(^V), 1=1,2,...,*:}.Для итерационных параметров т* используется формулаrk = ——, fikeMK,k=l,2,...,K.(4.19)1 + ЯфкЧебышевский итерационный метод (4.2), (4.19) сходится в Яд, R = А, Ви для числа итераций К, необходимых для достижения точности е,справедлива оценкаК>К" 00(е)=\с/ - /_/,тет1 '(4.20)где1-С'/2Q\ =72Заметим, что в чебышевском методе (см. (4.19)) расчет итерационных параметров осуществляется по заданному общему числу итераций К.Естественно, что вырожденный случай К = 1 соответствует рассмотренному выше методу простой итерации.
Практическая реализация чебышевского итерационного метода связана с проблемой вычислительнойустойчивости, которая решается специальным упорядочиванием итерационных параметров (выбором ць из множества Мк)-4.2. Итерационные алгоритмы линейной алгебры554.2.3. Итерационные методы вариационного типаВыше рассматривались итерационные методы решения задачи в условиях, когда задана априорная информация об операторах В и А в видеконстант (см. (4.16)) энергетической эквивалентности 7i и 72- Через этипостоянные определяются оптимальные значения итерационных параметров (см.
(4.17), (4.19)). В итерационных методах вариационного типа,в которых итерационные параметры вычисляются без такой априорнойинформации.Обозначая невязку г* = Ахк - / и поправку wk = B~lrk, для итерационных параметров при естественном предположении о минимизациипогрешности в Яд получим формулу(Rw\zk)r=- Хыг^у,4 21ч<- >Итерационный процесс (4.2) запишется следующим образомхк+] = хк - Tk+]wk, fc = 0 , l , . . . .Конкретизация итерационного метода достигается за счет выбораоператора R = R* > 0. Этот выбор должен быть подчинен, в частности,условию возможности вычисления итерационных параметров. В формулу(4.21) входит невычисляемая величина zk и поэтому простейший выборR = В здесь не проходит.
Вторая отмеченная выше возможность R = Априводит нас к итерационному методу скорейшего спуска, когда+(wk,rk)(Awk,wk)Среди других возможностей выбора R отметим случай R = АВ~ХА —метод минимальных поправок, когда_(Awk,wk)~ (B^Awk,AwkYТк+,K}Двухслойный итерационный метод вариационного типа сходитсяне медленнее метода простой итерации, т.е. для числа итераций п,необходимых для достижения точности е, справедлива оценка (4.18).Глава 4.
Итерационные методы линейной алгебры56В вычислительной практике наибольшее распространение получилитрехслойные итерационные методы вариационного типа. По скоростисходимости они не хуже итерационного метода с чебышевским наборомитерационных параметров.В трехслойном (двухшаговом) итерационном методе новое приближение находится по двум предыдущим. Для реализации метода требуютсядва начальных приближения ж0, ж'. Обычно х° задается произвольно, а ж'находится по двухслойному итерационному методу.
Трехслойный методзаписывается в следующей канонической форме трехслойного итерационного метода:Вуш= ак+, (В - тк+1А)ук + (1 - о» + ,)Ву*-' + а* + ,т* +1 р,*=1,2,...,(4.24)0By* = ( В - т , А ) з / + г,^,где а* + | и Tfc+i — итерационные параметры.В методе сопряженных градиентов итерационные параметры рассчитываются по формулам(wk,rk)(Лиг,иг)„(У>*,Гк)7fc+lTk far ',rkk= 1,2,... ,1 v-|') ata, = 1.Этот метод наиболее широко используется в вычислительной практике при решении задач с симметричной положительно определеннойматрицей.4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
