Конспект лекций - 3ий поток, лектор - Ионкин (1113828), страница 5
Текст из файла (страница 5)
Откуда получаем, что скалярноепроизведение (C ∗ Cx, x) = (Cx, Cx) ≥ 0. Из этой оценки можем записать, чтоB ≥ 2ωA, а учитывая B − 0.5τ A > 0, получим, что B > 2ωA > 0.5τ A.Из этого получаем оценку2ω > 0.5τ =⇒ w >τ4Значит при выполнении этого условия, справедлива теорема Самарского.Теорема 5 (об оценки скорости сходимости ПТИМ). Путь A = A∗ > 0, пусть∃ δ > 0, ∆ > 0, такие что выполняется операторные неравенства:A > δE, R2 R2∗ <Aδ422, гдеПоложим ω = √ , τ =γ1 + γ2δ∆√√δ ∆δ∆√ , γ2 =γ1 = √42( δ + ∆)(3)(4)Тогда для ПТИМ (2) имеет место оценка в энергетической норме BkV n+1 kB 6 ρkV n kB ,где√1− ν√ ,ρ=1+3 νη=δ,∆(5)(6)B = (E + ωR2∗ )(E + ωR2 )Доказательство: Для сходимости необходимо, чтобы ρ была меньше единицы, адля этого необходимо, чтобы η была меньше единицы, в противном случае оценка(5) теряет общий смысл.
Откуда получаем, что должно выполняться:δ 6 ∆.Убедимся в этом.31Из условия (5) получим, чтоkxn+1 − xkB 6 ρ(ω)kxn − xkB ,гдеρ(ω) =1 − ξ(ω)γ1 (ω), ξ(ω) =.1 + ξωγ2 (ω)Из (3) видно, что(Ax, x) > δ(x, x) = δkxk2 ,∆(R2∗ R2 x, x) 6 (Ax, x).4∆А так как (R2∗ R2 x, x) = (R2 x, R2 x) = kR2 xk2 , то kR2 xk2 ≤ (Ax, x). Противоре4чий не возникает, так как A положительно определена.Поскольку A = R1 + R2 , то с учетом того, что мы работаем в вещественномпространстве, получим что(Ax, x) = (R2∗ , x) + (R2 x, x) = 2(R2 x, x).Таким образом,δkxk2 6 (Ax, x) =(Ax, x)24(R2 x, x)2=(Ax, x)(Ax, x)Теперь воспользуемся неравенством Коши-Буняковского:∆4 (Ax, x)4(R2 x, x)2≤ 4kxk2 = ∆kxk2 .(Ax, x)(Ax, x)Откуда получаем, что δ ≤ ∆. Исходя из следствия (1) §7, будем подбирать параметр ω такой, чтобы минимизировать ρ(ω).ρ2 (ω)Рассмотрим функцию f (ω) =.ρ1 (ω)1Из теоремы(1) B ≥ 2ωA, следовательно A 6B.2ω1.Откуда ясно, что γ2 (ω) =2ωТак как,1∆1ω2∆B = E + ωA + ω 2 R2∗ R2 6 A + ωA + ω 2 A = ( + ω +)A.δ4δ4−11ω2∆Получаем, что γ1 (ω) =+ω+.
Перейдем к минимизации ρ(ω). Онаδ4достигает минимум, тогда достигает минимум функции f (ω) :1∆+ ω + w211∆δ4f (ω) ==1++ ω .2ω2δ∆432Найдем производную:1f (ω) =20∆1− 24δω.∆14= 2 . И отсюда ω0 = ω = √ .4δωδ∆1 2f 00 (ω) =>02 δω 2Поскольку f 00 (ω) > 0, то при ω = ω0 достигается минимум f (ω), следовательнои ρ(ω). Подставляя найденное ω в γ2 (ω) получим, что√δ∆.γ2 (ω) =4Видно, что f 0 (ω) = 0 приТеперь вычислим γ1 (ω) и ρ(ω):√√δδ∆√√ ,γ1 (ω) ===∆ 212 δ+ ∆∆ 412+ω+ ω+√+δ4δ4 δ∆δ∆√2 δγ1 (ω)√ ,=√ξ(ω) =γ2 (ω)δ+ ∆rδ√1−1− ηδ1 − ξ(ω)∆r = {η = } ==ρ(ω) =√ .1 + ξ(ω)∆1+3 ηδ1+3∆11n0 (ε) = ln /ln— число итераций, необходимое для достижения точности ε.ερВ реальных задачах часто η = O(m−2 ).Теперь посчитаем, сколько необходимо итераций, чтобы получить решение с точ1ностью ε, для этого оценим величину :ρ√√√1+3 η(1 + 3 η)(1 + η1√=≈ 1 + 4 η.√ =ρ1− η1−η111 √1Тогда ln ≈ η.
Итак, получим, что n0 (ε) ≈ √ = O(m).ρηДля сравнения рассмотрим метод простой итерации(МПИ):xn+1 − xn+ Axn = f, τ > 0, n = 0, 1, 2, 3, . . .τИз следствия 2 §7 справедлива оценка скорости сходимостиkxn+1 − xk 6 ρkxn − xk,33где1−εγ1A, ε = , γ1 = min λAk , γ2 = max λk .kk1+εγ2Здесь ξ = η, а η = O(m−2 ).Найдем число итераций.ρ=11+ξ(1 + η)2==≈ 1 + 2η.ρ1−ξ(1 − η)211Тогда ln ≈ η, следовательно n0 (ε) ≈ = O(m2 ).ρη§9 Методы решения задач на собственные значенияПусть A — произвольная матрица размера (m × m). Рассмотрим задачу на собственные значения матрицы A: найти такие λ и нетривиальные x, удовлетворяющиеAx = λx, x 6= 0.(1)где λ называется собственным значением, а x — собственным вектором.Для нахождения собственных значений матрицы А необходимо решить характеристическое уравнение f (λ) = |A − λE| = 0 — многочлен от λ степени m.
При m > 5задача не разрешима в общем случае.Различают две проблемы собственных значений:1. Частичная проблема собственных значений. Требуется найти некоторое подмножество спектра матрицы A (как правило, минимальное и максимальное помодулю собственные значения).2. Полная проблема собственных значений. Требуется найти весь спектрматрицы A.Степенной методЭто итерационный метод решения частичной проблемы собственных значений.Обозначим xn — n-я итерация С.В., x0 — начальное приближение.xn+1 = Axn ,(1)где n = 0, 1, 2 .
. . , x0 - задано.Рассматривая формулу (1) как рекуррентную, получим:xn = An x0(2)Теперь сделаем допущения при доказательстве. Докажем, что степенной методбудет давать вектор, сходящийся при n → ∞ по направлению к вектору, отвечающему максимальному по модулю собственному значению. Упорядочим собственныезначения в порядке невозрастания модулей.|λ1 | 6 |λ2 | 6 . .
. 6 |λm |34Для доказательства сходимости степенного метода сделаем следующие предположения:1. Пусть у матрицы A есть базис из собственных векторов (не обязательно ортонормированный):{ei }m ,илиAei = λi ei ,ei 6= 0(3)Следовательно, любое начальное приближение можно представить в виде разложения по этому базису:x0 = c1 e1 + c2 e2 + . . . + cm em2. Пусть в представлении начального приближения cm 6= 0 −1 <13.
Пусть λmλm Утверждение 2. Пусть для матрицы A выполнены условия 1, 2 и 3, тогда степенной метод сходится по направлению к собственному вектору, отвечающемумаксимальному собственному значению:xn −→ em ,n→∞Доказательство: Из формулы (2) следует:xn = c1 λn1 e1 + c2 λn2 e2 + . . . + cm λnm emДалее поделим обе части на λnm cm 6= 0: nλnm−1 cm−1c1 λ 1xn= em +em−1 + . .
. +e1 =cm λnmcm λnmcm λ mn ncm−1 λm−1c1 λ1= em +em−1 + . . . +e1cmλmcm λ mλiУстремим n к бесконечности. Ясно, что тогда все отношения, видабудутλmравны нулю, откуда получим, чтоxn −→ emпо направлению,n→∞Степенной метод позволяет найти максимальное по модулю собственное значение.Докажем, чтоλ(n)m− λm = Oλm−1λmn35Возьмем две соседние итерации:(i)(i)nnn (i)x(i)n = c1 λ1 e1 + c2 λ2 e2 + . .
. + cm λm em(i)(i)(i)(i)xn+1 = c1 λn+1e1 + c2 λn+1e2 + . . . + cm λn+112m emПоделим их друг на друга:(i)λ(n)mxn+1(i)(i)(i)c1 λn+1e1 + c2 λn+1e2 + . . . + cm λn+112m em=(i)(i)(i)c1 λn1 e1 + c2 λn2 e2 + . . . + cm λnm emn+1 (i) n+1 (i) e1(i)cm−1λm−1emc1λ1n+1λm cm em 1 + cm(i) + . . . + cm(i)λmλmemem==n (i) n (i) e1(i)λm−1cm−1emλ1c1nλm cm em 1 + cm(i) + .
. . + cm(i)λmλmememnnoλm−1n.= поделим числитель и знаменатель на λm = λm +λm=(i)=xnОткуда получаем:λ(n)mили− λm = Oλm−1λmn(i)xn+1= λm , ∀i = 1, m(i)xnТаким образом доказано, что для любой матрицы, удовлетворяющей условиям1, 2 и 3, степенной метод сходится. Этот же метод позволяет найти максимальное помодулю собственное значение.Но это не единственный способ нахождения максимального по модулю собственного значения с использованием этого метода. Покажем, что его можно найти издругих соображений, причем, если взять самосопряженную матрицу, то сходимостьметода будет более быстрой.limn→∞Утверждение 3. Максимальное по модулю собственное значение может бытьнайдено следующим образом:(Axn , xn )(n)λm=(4)(xn , xn )Доказательство:Рассмотрим задачу для двух видов базисов из собственных векторов: ортонормированного и не ортонормированного.Случай первый.ПустьA = A∗ .ТогдаAek = λk ek ,ek 6= 0,∀k = 1, m.Причем, {ei }m1 — ортонормированный базис из собственных векторов, то есть(ei , ej ) = δij .
Тогда36λ(n)m2n+1oc2m λ2n+1+ c2m−1 λm−1+ . . . + c21 λ12n+1 n(xn+1 , xn )m= воспользуемся условием 1 ===2 2n2n2(xn , xn )c2m λ2nm + cm−1 λm−1 + . . . + c1 λ12 2n+1 2 2n+1 cm−1λm−1λ12n+1 2λm cm 1 + cm+ . . . + ccm1λmλmλm−1 2n== λm + O()2 2n 2 2n λmcm−1λm−1c1λ12n2λm cm 1 + cm+ . . . + cmλmλm⇓λ(n)m− λm = Oλm−1λm2nВторой случай.Пусть {ei }m1 — базис из собственных векторов (не ортонормированных).mP(n)λm==(Axn , xn )=(xn , xn )ci cj λn+1λnj (ei , ej )ii,j=1mP=ci cj λni λnj (ei , ej )i,j=12n+1 2n+1 nλm cm (em , em ) + λm λm−1 cm−1 cm (em−1 , em ) + . . .
+ c21 λ2n+1(e1 , e1 )1n2 2n2n2nλm cm (em , em ) + λm λm−1 cm−1 cm (em−1 , em ) + . . . + c1 λ1 (e1 , e1 )=λm−1 n cm−1 (em−1 , em−1 )λ1c1 (e1 , e1 )) ()+ . . . + ( )2n+1 ( )2λmcm(em , em )λmcm (em , em )λ1 2n c1 2 (e1 , e1 )λm−1 n cm−1 (em−1 , em−1 )) ()+ ... + ( ) ( )1+(λmcm(em , em )λmcm (em , em )1+(= λmТогдаλ(n)m(xn+1 , xn )== λm + O(xn , xn )λm−1λmnЗамечание. Покажем, что если матрица A вещественная, а собственные значения комплексные, то собственный вектор, отвечающий этому собственному значению, должен быть комплексным:λ = λ0 + iλ1 ,λ1 6= 0.Тогда в качестве начального приближения нужно брать комплексный вектор.Пусть x = µ0 + iµ1 — собственный вектор, где µ0 , µ1 — вещественные.
Покажем, что µ1 6= 0:Ax = λx, x 6= 0⇓A(µ0 + iµ1 ) = (λ0 + iλ1 )(µ0 + iµ1 ) = λ0 µ0 − λ1 µ1 + i(λ1 µ0 + λ0 µ1 )37Пусть µ1 = 0, тогдаAµ1 = λ1 µ0 + λ0 µ1 =⇒ µ0 = 0 =⇒ x ≡ 0.Получили противоречие, а значит µ1 6= 0.Метод обратных итерацийМетод заключается в нахождении минимального по модулю собственного значения.Изначально нужно наложить ограничения на матрицу. Рассмотрим матрицу, длякоторой существует обратная. Тогда организуем итерационный метод по следующейформулеAxn+1 = xn ,(5)где n = 0, 1, 2, .
. . , x0 — выбираем.Метод, задаваемый формулой (5) — неявный. Так как ∃A−1 , тоxn+1 = A−1 xn(6)Таким образом метод превратился в степенной, но для матрицы A−1 .Мы знаем, что у невырожденной матрицы собственные значения связаны с собственными значениями обратной матрицы как обратные числа. А собственные вектора у прямой и обратной матрицы совпадают.λAk−1=1,λAkk = 1, m,|λ1 | 6 |λ2 | 6 · · · 6 |λm |, λk = λAkПусть выполнены условия:1.
{ei }m1— базис из собственных векторов2. x0 = c1 e1 + c2 e2 + · · · + cm em , 3. λλ21 < 1где c1 6= 0Так как1ek , ek 6= 0, ∀k = 1, m ,λkто, записав вектор x0 по базису, применим A−1 :A−1 ek =−1 nxn = (A ) x0 =mX−n−nck λ−nk ek = c1 λ1 e1 + . . . + cm λm emk=1xnc2−n = e1 +c1c1 λ1⇓n nλ1cm λ1e2 + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
