А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (1113878), страница 7
Текст из файла (страница 7)
Покажите, что метод верхней релаксации (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. Спектральные задачи линейной алгебрыОсновные обозначениях = {х • } = {Я|)х 2 ,...,х„} — n-мерный векторА = {ву} — матрица с вещественнымиэлементами ai}£7 — единичная матрицаD = :diag{d,, d 2 , .
. , d n } — диагональная матрицаХи г == 1,2,...,п — собственные значения<Р%, * == 1,2,... ,п — собственные вектора(х,у) = Х/ ,!Л — скалярноепроизведение«=|Тем самым собственные значения А матрицы А являются корнямихарактеристического многочлена n-ой степени (5.2). Задача отыскания собственных значений и собственных векторов матрицы сводитсяк построению характеристического многочлена, отысканию его корнейи последующему нахождению нетривиальных решений уравнения (5.1)для найденных собственных значений.В вычислительной практике рассматривается как полная проблемасобственных значений, когда необходимо найти все собственные значения матрицы А, так и частичная проблема собственных значений, когдаищутся только некоторые собственные значения, например, максимальные (минимальные) по модулю.5.2. Численные методы решения задачна собственные значенияНачнем с приведения некоторых полезных фактов о свойствах собственных значений и собственных векторов квадратной матрицы.
Далеерассматриваются методы решения частичной и полной проблемы собственных значений.5.2. Численные методы решения задач на собственные значения675.2.1. Свойства собственных значенийи собственных векторовКвадратная вещественная матрица порядка п имеет п собственных значений, при этом каждое собственное значение считается столько раз, каковаего кратность как корня характеристического многочлена. Для симметричной матрицы А собственные значения вещественны, а собственныевектора, соответствующие различным собственным значениям, ортогональны, т. е. (ф1, <р*) — О, если г Ф j .Отметим также некоторые свойства собственных значений и собственных векторов для сопряженной матрицы .4*:А*ф = цф.(5.3)Для спектральных задач (5.1), (5.3) имеемAj = /i,-,t=l,2,...,n,(уЛ^') = 0,хфуДве квадратные матрицы А и В одинаковых размеров называютсяподобными, если существует такая невырожденная матрица Р, что А =Р~1ВР.
Подобные матрицы имеют одни и те же собственные значения,так как из (5.1) непосредственно следуетВф = \ф,ф = Р<р.Поэтому вычислительные алгоритмы решения спектральных задач базируются на подобном преобразовании матрицы к матрице В, для которойспектральная задача решается проще. В качестве В естественно выбиратьдиагональную матрицу, причем в данном случае это будетA = diag{A,,A 2 ,...,A„}.Упорядочим собственные значения симметричной матрицы А по возрастанию, т.е. А| < А2 < • •• < А„. Свойства собственных значенийи собственных функций связаны с отношением Релея(Аз* д*^'Отметим,(х,х)например, что для любого ненулевого вектора х справедливы неравенства(Ах,х)А| ^ —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
