Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Подставляя найденное ω в γ2 (ω) получим, что√δ∆γ2 (ω) =.4Видно, что f 0 (ω) = 0 приТеперь вычислим γ1 (ω) и ρ(ω):√√δδ∆√√ ,γ1 (ω) ===1∆ 22 δ+ ∆∆ 421+ω+ ω+√+δ4δ4 δ∆δ∆1133√2 δγ1 (ω)√ ,=√ξ(ω) =γ2 (ω)δ+ ∆rδ√1−1− η1 − ξ(ω)δ∆r = η=ρ(ω) ===√ .1 + ξ(ω)∆1+3 ηδ1+3∆11— число итераций, необходимое для достижения точности ε.n0 (ε) = ln /lnερВ реальных задачах часто η = O(m−2 ).Теперь посчитаем, сколько необходимо итераций, чтобы получить решение с точ1ностью ε, для этого оценим величину :ρ√√√1+3 η(1 + 3 η)(1 + η)1√=≈ 1 + 4 η.√ =ρ1− η1−η1 √1Тогда ln ≈ η.

Итак, получим, что n0 (ε) ≈ √ = O(m).ρηДля сравнения рассмотрим метод простой итерации(МПИ):xn+1 − xn+ Axn = f, τ > 0, n = 0, 1, 2, 3, . . .τИз следствия 2 §7 справедлива оценка скорости сходимостиkxn+1 − xk 6 ρkxn − xk,гдеρ=γ11−ξA, ξ = , γ1 = min λAk , γ2 = max λk .kk1+ξγ2Здесь ξ = η, а η = O(m−2 ).Найдем число итераций.1+ξ1 + η21==≈ 1 + 2η.ρ1−ξ1 − η211Тогда ln ≈ η, следовательно n0 (ε) ≈ = O(m2 ).ρη§9 Методы решения задач на собственные значенияПусть A — произвольная матрица размера (m × m). Рассмотрим задачу на собственные значения матрицы A: найти такие λ и нетривиальные x, удовлетворяющиеAx = λx, x 6= 0.(1)34где λ называется собственным значением, а 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 |Для доказательства сходимости степенного метода сделаем следующие предположения:1. Пусть у матрицы A есть базис из собственных векторов (не обязательно ортонормированный):{ei }m ,илиAei = λi ei ,ei 6= 0(3)Следовательно, любое начальное приближение можно представить в виде разложения по этому базису:x0 = c1 e1 + c2 e2 + . . . + cm em2. Пусть в представлении начального приближения cm 6= 0353.

Пусть λm−1 λm < 1Утверждение. Пусть для матрицы 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−1xnc1 λ 1e1 == em +em−1 + . . . +cm λnmcm λnmcm λ mn ncm−1 λm−1c1 λ1= em +em−1 + .

. . +e1cmλmcm λ mλiбудутУстремим n к бесконечности. Ясно, что тогда все отношения, видаλmравны нулю, откуда получим, чтоxn −→ emn→∞по направлению,Степенной метод позволяет найти максимальное по модулю собственное значение.Докажем, чтоλ(n)m− λm = Oλm−1λmnВозьмем две соседние итерации:(i)(i)nn (i)nx(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)(i)(i)c1 λn1 e1 + c2 λn2 e2 + . . . + cm λnm emn+1 (i) n+1 (i) em−1e1(i)λm−1cm−1c1λ1n+1λm cm em 1 + cm(i) + . .

. + cm(i)λmλmemem==n (i) n (i)ee(i)cλcλm−1m−1m−1111λnm cm em 1 + cm(i) + . . . + cm(i)λmλmememnnoλm−1n= поделим числитель и знаменатель на λm = λm + O.λm=(i)xn=(i)e2 + . . . + cm λn+1c1 λn+1e1 + c2 λn+112m em36Откуда получаем:λ(n)mили− λm = Oλm−1λmn(i)xn+1= λm , ∀i = 1, m(i)xnТаким образом доказано, что для любой матрицы, удовлетворяющей условиям1, 2 и 3, степенной метод сходится. Этот же метод позволяет найти максимальное помодулю собственное значение.Но это не единственный способ нахождения максимального по модулю собственного значения с использованием этого метода. Покажем, что его можно найти издругих соображений, причем, если взять самосопряженную матрицу, то сходимостьметода будет более быстрой.limn→∞Утверждение. Максимальное по модулю собственное значение может быть найдено следующим образом:(Axn , xn )(n)(4)λm=(xn , xn )Доказательство:Рассмотрим задачу для двух видов базисов из собственных векторов: ортонормированного и не ортонормированного.Случай первый.ПустьA = A∗ .ТогдаAek = λk ek ,ek 6= 0,∀k = 1, m.Причем, {ei }m1 — ортонормированный базис из собственных векторов, то есть(ei , ej ) = δij .

Тогдаλ(n)m2n+1oc2m λ2n+1+ c2m−1 λm−1+ . . . + c21 λ12n+1 n(xn+1 , xn )m= воспользуемся условием 1 ===22n2 2n(xn , xn )c2m λ2nm + cm−1 λm−1 + . . . + c1 λ12 2n+1 2 2n+1 cm−1λm−1λ12n+1 22nλ m cm 1 + c m+ . . . + ccm1λmλmλm−1= λ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 — базис из собственных векторов (не ортонормированных).37mP(n)λm==1+= λm(Axn , xn )=(xn , xn )ci cj λn+1λnj (ei , ej )ii,j=1mP=ci cj λni λnj (ei , ej )i,j=1n+1 n2n+1 2(e1 , e1 )λm cm (em , em ) + λm λm−1 cm−1 cm (em−1 , em ) + . .

. + c21 λ2n+11=2 2nn2n2nλm cm (em , em ) + λm λm−1 cm−1 cm (em−1 , em ) + . . . + c1 λ1 (e1 , e1 )n+1 2n+1 2λm−1cm−1 (em−1 , em−1 )λ1c1(e1 , e1 )+ ... +λmcm(em , em )λmcm(em , em )n 2n 2λm−1cm−1 (em−1 , em−1 )λ1c1(e1 , e1 )1++ ... +λmcm(em , em )λmcm(em , em )Тогдаλ(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 )Пусть µ1 = 0, тогдаAµ1 = λ1 µ0 + λ0 µ1 =⇒ µ0 = 0 =⇒ x ≡ 0.Получили противоречие, а значит µ1 6= 0.Метод обратных итерацийМетод заключается в нахождении минимального по модулю собственного значения.Изначально нужно наложить ограничения на матрицу. Рассмотрим матрицу, длякоторой существует обратная. Тогда организуем итерационный метод по следующейформулеAxn+1 = xn ,(5)38где n = 0, 1, 2, .

. . , x0 — выбираем.Метод, задаваемый формулой (5) — неявный. Так как ∃A−1 , тоxn+1 = A−1 xn(6)Таким образом метод превратился в степенной, но для матрицы A−1 .Мы знаем, что у невырожденной матрицы собственные значения связаны с собственными значениями обратной матрицы как обратные числа. А собственные вектора у прямой и обратной матрицы совпадают.λAk−1=1,λAk|λ1 | 6 |λ2 | 6 · · · 6 |λm |, λk = λAkk = 1, m,Пусть выполнены условия: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=1c2xn−n = e1 +c1c1 λ1⇓n nλ1cm λ1e2 + . . . +emλ2c1 λ mПолучим, чтоxn −→ e1 , n → ∞ n(i)λ1xn(n)(n)Задача. Доказать, что λ1 − λ1 = O, где λ1 = (i) , i = 1, mλ2xn+1(i)(i)Решение: Выпишем выражения для xn и xn+1 :(i)(i)−n−n−n (i)x(i)n = c1 λ1 e1 + c2 λ2 e2 + · · · + cm λm em(i)(i)(i)e(i)xn+1 = c1 λ−n−1e1 + c2 λ2−n−1 e2 + · · · + cm λ−n−1mm1Теперь поделим (1) на (2):−n−n !(i) cm em λmλ21++ ··· +(i)(i)λ1λ1c1 e 1c1 e1−n−1−n−1 ! =(i) (i) c2 e 2λ2cm e m λ m1++ ··· +(i)(i)λ1λ1c1 e 1c1 e 1(i)(i)c1 λ−n1 e1(i)xn(i)xn+1=(i)c1 λ−n−1e11c2 e 2(1)(2)39= λ1 + Oλ1λ2n= λn1Что и требовалось показать.Задача.

Характеристики

Список файлов лекций