А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 7
Текст из файла (страница 7)
УпражненияПриведены упражнения, которые иллюстрируют теоретические результаты по итерационному решению систем линейных алгебраических уравнений.Упражнение 4.1. Пусть в матрице А в уравнения (4.1) для элементов имеетместо неравенство4.3. Упражнения57Ф»\ > Yl KI, * = 1.2,...,п,(4.25)где О < q < 1. Тогда итерационный метод Зейделя сходится и для погрешности справедлива оценкаkV L^9 \\zMMkz = x -x,i= max \x,\.Решение. Из (4.6) для погрешности на новой итерации имеем оценкуfc'*'KlU**'!.Е + И1»ЕVа,(4.26)Принимая во внимание (4.25), получим<<?о„0-|Й>С учетом этого (4.26) даетi-ikt+,EfehHL(.-Efel)-+li<IU* lj=iч"J=I«•">Пусть максимум |z* +l | достигается при г = т , тогда (4.27) приводитк неравенствуm-lJM-ii'-Е^Отсюда и следует доказываемая оценка для погрешности.Упражнение 4.2.
Покажите, что метод верхней релаксации (4.10) при решении задачи (4.1) с симметричной положительно определенной матрицей Асходится при 0 < т < 2.Решение. Достаточно проверить выполнение неравенства (4.14). С учетомсимметрии (U = L') имеем(Ах,х) = (Dx,x)+2(Lx,x)58Глава 4. Итерационные методы линейной алгебрыи поэтому(Вх,х) -Т-(Ах,х) = (l - I )(Dx,x).В силу положительной определенности матрицы А имеем D > 0 и поэтому неравенство (4.14) при отмеченных ограничениях на итерационныйпараметр выполнено.Упражнение 4.3.
Пусть А = А">0,неравенстваЪВ^А^ЪВ,В = В*>0иС= Л | / 2 В _ 1 Л 1 / 2 . ТогдацЕ^С^ъЕ(4.28)эквивалентны.Решение. Положим у = С'' 2 х, v — А~^2у и при постоянной 7 рассмотрим выражение(Сх, х) - -у(х, х) = (у, у) - 7(С"' у, у) == (У,У) ~ j{A-,/2AA~U2y,y)= (Av,v) - -y(Bv,v).Следовательно матрицы (С - уЕ) и (А - -уВ) имеют одинаковые знаки.Полагая 7 = 7i и 7 = 72» получим эквивалентность двухстороннихоператорных неравенств (4.28).Упражнение 4.4. Пусть в итерационном методе (4.13) А — симметричнаяи положительно определенная матрица и выполнено неравенствоВ~ \А >Ц-^-Я'^-'Л(4.29)с постоянной Q £ (0,1). Тогда итерационный метод сходится и для погрешности справедлива оценкаI** 1 1 A*tW\\A--* 11 - 0<«•»)Решение. Неравенство (4.30) эквивалентно выполнению матричного неравенстваQ2A>S*AS,S =E-TB~1A,594.3.
Упражненият.е.тА((ВТ1+ В~1)А> (1 - о2)А +Т2А(В*У1АВ-1А.Это матричное неравенство останется в силе после умножения его справана матрицу G = А~]В, а слева на G* = В*А~1:т(В + В*)^(\-д2)В*А~хВ + т2А.Последнее неравенство совпадает с (4.29). При д € (0,1) неравенство (4.30) обеспечивает сходимость итерационного метода (4.13).Упражнение 4.5. ПустьА = А\+А2= А* > 0 ,А*2 = А, = -D + L.В попеременно-треугольном методе переобуславливатель В задается в видеB = (G + wA])G-i(G+wA2),(4.31)где G = G* > 0. При априорной информацииA^6G,6>0,A|G"'vl2^-A(4.32)укажите оптимальный выбор параметра ш.Решение. Прежде всего покажем, что матрица В — положительно определена и симметрична.
В самом деле(Вх,у)=((G+u>Ai)G~l{G + uA2)x,y)l= ((G + uA2)x,G~ (G=+ wA2)y) =l= (x,(G + uAi)G~ (G + шА2)у),(Bx,x)=((G+uA2)x,G~](G+ u)A2)x) = \\(G + wA2)x\\2G.„т. е. В = В* > 0.Скорость сходимости итерационного метода (4.13) в условиях (4.12),(4.15) определяется постоянными 7 ь 72 в (4.16). В попеременно-треугольном методе (4.31) имеемВ = G + ш{А\ + А2) + w2A]G~>A2 = (G - uAx)G~\G- шА2) + 2шАГлава 4.
Итерационные методы линейной алгебры60и поэтому172 = г - .2шВ > 2шА,Для оценки матрицы В сверху привлекается априорная информация (4.32):т_i1/B = G + u>A + w2A>Gи>бД\*А2^-[\+ш6+——)А.Тем самым•yt=6Gl\+uj6+-—J.Скорость сходимости будет наибольшей (см. (4.18), (4.20)) при максимальном £(ш) = 7i/72- Максимум £(ш) достигается при2О) = 0>о :Д<5Упражнение 4.6. Получите выражения для итерационного метода (4.2)с В — В' > 0 для решения задачи (4.1) с матрицей А > 0 из условияминимума поправки в Нв.Решение.
Для погрешности итерационного метода имеем однородноеуравнение*+i _*+ Azk=Q,Вk = Q, l , . . . .т/fc+iАналогично записывается и уравнение для поправкиwk+] - wkВi.+ Aw = 0 , fc = 0 , l , . . . .Tk+\Отсюда для нормы поправки на новой итерации получим\\Bwk+l \\2В_, = \\w™ \\2В = (B-\Bwk-rk+i Awk),(Bwk - r t + 1 Awk)) == (Bto*, w*) - 2т*+, (A wk, wk) + T2(B' ' Awk, te*).Дифференцируя это выражение по тк+\, находим для определения итерационных параметров в методе минимальных поправок формулу (4.23).4.4. Задачи614.4. ЗадачиЗадача 4.1. Докажите сходимость метода Якоби при решении задачи (4.1)с матрицей А, для элементов которой выполнены одно из следующихусловийЕп£< 1,Oil»=1,2,...,п,< 1, j = 1,2,...,п,Е Е (2?) <»•Задача 4.2.
Исследуйте сходимость итерационного метода Зейделя, когдап4Wjj\> Еla,'jl ^ = 1,2,...,п,где 0 < q < 1 (диагональное преобладание по столбцам).Задача 4.3. Установите следующие свойства положительно определенныхматриц:• если А > 0, то матрица А — невырожденная и А~х > 0;• если А, В > 0, то для любых неотрицательных чисел a, f), не равныхнулю одновременно, имеем а А + /ЗВ > 0;• для симметричной вещественной (эрмитовой) положительно определенной матрицы А существует единственная эрмитова положительно определенная матрица S такая, что S2 = А. Матрица Sназывается квадратным корнем из матрицы А и обозначается А1'2.Задача 4.4. Покажите эквивалентность матричных неравенств:А ^ 0, В*АВ ^ 0,Глава 4.
Итерационные методы линейной алгебры62если А= А* к В — невырожденная матрица иаА^/ЗВ,аВ-]>рА~\если А — А* > О, В = В* > 0, а и /3 - любые действительные числа.Задача 4.5. Покажите, что итерационный метод (4.13) при В = Е для задачи (4.1) с А > О сходится при всех т, удовлетворяющих неравенствуг < 2/114Задача 4.6. Пусть S = Е - тС и выполнены условияС = С*,ЪЕ^С^ъЕ,ъ >0.Тогда )|s|| < 1 при 0 < т < 2/72 и нижняя грань нормы операторадостигается при2т— го — , »71+72причемinf||S|| = p ? - T o C | | =1+**72Задача 4.7. Пусть А и В — симметричные положительно определенныематрицы. Тогда неравенстваттс g > 0 необходимы и достаточны для того, чтобы для задачиВ+ Az* = 0, fc = 0,l,.-твыполнялась оценкаt+,lk LMHL * = o,i,.,..Задача 4.8. Получите оценку числа итераций попеременно-треугольногоитерационного метода (4.31), (4.32) при выборе чебышевского набораитерационных параметров вида4.4.
Задачи63Задача 4.9. Определите область значений итерационного параметра в методе минимальных невязок (В = Е) при решении задачи (4.1) с матрицейА = аЕ + К, где К — кососимметричная (К = -К*) матрица, а а > 0.Задача 4.10. Докажите, что в итерационном методе сопряженных градиентов выполнены следующие свойства ортогональности для погрешностей на различных итерациях( G * V ) = 0,j = 0 , 1 , . . . , * — 1,i = 1,2,... ,гдеG = A,/2B-lA,/2,sk =Ai/2zk.Задача 4.11. При реализации трехслойного итерационного процесса(4.24) используется следующее представление для нового приближенияyk+l = ашукгде wk = B~]rk.формул+ (1 - аш)ук-]-ak+iTk+lwktРассмотрите возможность использования расчетных2/*+1 = у" + XkPk,к = 0,1,...,рк = wk + цкрк~\к = 1,2,...,P° = w°.Задача 4.12.
ПустьS(w) = (Е +ША)~\Е- шА),А = А* > 0.Докажите, чтоinf||S(«)|| = | | S M | |где161 + vT64Глава 4. Итерационные методы линейной алгебрыЗадача 4.13. ПустьА — А\ -г л 2 ,— Аа]AQ6аЕ < А» < АаЕ,«5а > 0 ,а = 1,2.Рассмотрите условия сходимости итерационного метода (итерационныйметод переменных направлений)хк+\/г_ хк(E + TAI)+Ax* = f,(4.33)к+\ _{Е+ TAl) *fc+l/2? — + Ах^п=,ти выберите оптимальный итерационный параметр т.Задача 4.14.
Покажите, что при А > О, В = В* > 0 » выполнениинеравенства(В' Ах, Ах) <ii{Ax,x)итерационный метод (4.13) сходится при г < 2/7гЗадача 4.15. В условиях предыдущей задачи и при дополнительном условииА ^у,В,7i > Овыберите оптимальное значение итерационного параметра т.Задача 4.16. Рассмотрите итерационный метод (4.33) для решения задачи (4.1) приА = А\ + А2,Аа > 6аЕ,\\Аах\\7 ^ Аа(Аах,х),6а>0,а = 1,2.Глава 5Спектральные задачилинейной алгебрыВажной и трудной задачей линейной алгебры является нахождение собственных значений и собственных векторов матриц.Рассматриваются проблема устойчивости собственных значенийпо отношению к малым возмущениям элементов матрицы.
Дляприближенного нахождения отдельных собственных значений широко используется степенной метод в различных модификациях.Для решения полной проблемы для симметричных матриц применяется итерационный метод Якоби и фД-алгоритм.5.1. Собственные значенияи собственные вектора матрицРассматриваются проблемы нахождения собственных значений и собственных векторов квадратной вещественной матрицы А. Собственнымчислом называется число А такое, что для некоторого ненулевого вектора(собственного вектора) <р имеет место равенствоAip = \tp.(5.1)Собственные вектора определены с точностью до числового множителя.Множество всех собственных значений матрицы А называется спектромматрицы А.С учетом того, что ищется нетривиальное решение уравнения (5.1), тоdet (А - ХЕ) = 0.(5.2)66Глава 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
