Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437), страница 4
Текст из файла (страница 4)
Следовательно, матрица D тоже является положительноопределенной, откуда следует верность неравенства.26Следствие 4. Пусть A = A∗ , A > 0. Рассмотрим метод простой итерации:xn+1 − xn+ Axn = fτ2, γ2 = max λAk по всем k, то метод сходится вγ2среднеквадратичной норме при любом начальном приближении.Тогда если выберем τ 0 < τ <Доказательство: Достаточное условие сходимости: B − 0.5τ A > 0. СледовательноE − 0.5τ A > 0 и 1 − 0.5τ λAk > 0. Откуда получаем исходное условие на τ с учетомτ >0§7 Оценка скорости сходимости итерационных методовРассматриваем систему уравнений c квадратной матрицей порядка m:Ax = f , |A| =6 0(1)Решаем итерационным методом:Bxn+1 − xn+ Axn = f ,τ(2)где τ > 0, ∃B −1 , n = 1, 2, 3, . .
. , начально приближение x0 — задано.Введем погрешность V n = xn − x. Тогда из (2) получаем:BV n+1 − V n+ AV n = 0 ,τ(3)где τ > 0, n = 1, 2, 3, . . . , начально приближение V 0 = x0 − x — задано.Поставим задачу получения оценки вида:kV n+1 k 6 ρkV n k ,(4)где n = 1, 2, 3, . . . , ρ ∈ (0, 1) и рассматриваемая норма пока не фиксирована.Применив эту оценку как рекуррентную, получим: kV n k 6 ρn kV 0 k и при n → ∞— ρn → 0 ⇒ норма погрешности kV n k → 0. Значит имеет место сходимость. Болеебыстрая сходимость будет при ρ близко к нулю. ρ называется константой затуханияпогрешности.Если удастся получить данную оценку (4), то можно будет посчитать количествоитераций исходя из нужной точности:kxn − xk 6 εkx0 − xkkxn − xk 6 ρn kx0 − xk2711Из свойства транзитивности неравенств получим: ρn 6 ε ⇒ nln > ln . Тогдаρε11будет верна оценка n > n0 (ε), где ε —проделав число итераций n0 (ε) = ln / lnερ1точность приближения, ln — скорость сходимости.ρВведем вещественное линейное пространство H , размерность которого равна m.
Внем вводим скалярное произведение∀x, y ∈ H (x, y) =mXxi y ii=1и среднеквадратичную норму:vu mpuXkxk = (x, x) = txi 2i=1Остальные нормы энергетические:∀B = B ∗ , B > 0 kxkB =p(Bx, x)Теорема 3 (об оценке скорости сходимости). Пусть даны матрицы A = A∗ , A > 0и B = B ∗ , B > 0, ∃ρ ∈ (0, 1) такое , что выполнено операторное неравенство:1+ρ1−ρB6A6Bττ(5)Тогда итерационный метод (2) решения системы (1) сходится и имеет местоаприорная оценка:kV n+1 kB 6 ρkV n kB n = 1, 2, 3, . . .(6)Доказательство:Замечание.
Рассмотрим правую часть операторного неравенства (5) : A 61+ρB. Откуда получаем B − 0.5τ A > 0 при ρ = 1. Значит сходимость будетτпри любом начальном приближении к среднеквадратичной норме. Оценку (6) можно получить и в норме оператора A.√√ ∗ √11 ∗1Если B = B ∗ , B > 0 , то тогда ∃ B = ( B) , B > 0 и B − 2 = (B − 2 ) , B − 2 >10. Применим B − 2 к (3):1V n+1 − V nB+ B − 2 AV n = 0τ121Введем вектор z n = B 2 V n . Чтобы получить (6), достаточно получитьkz n+1 k 6 ρkz n k(7)2811Это верно в силу самосопряженности оператора B : kz n k2 = (z n , z n ) = (B 2 V n , B 2 V n ) =(BV n , V n ) = kV n kB1Подставим V n = B − 2 z n в полученное выше:11z n+1 − z n+ B − 2 AB − 2 z n = 0τ11и выразим z n+1 через z n : z n+1 = z n − τ B − 2 AB − 2 z n = Sz n ,где11S = E − τ B − 2 AB − 2(8)— матрица перехода от n-й итерации к (n + 1)-й итерации вектора z.Докажем ,что все собственные значения матрицы S не превосходят по модулюρ , Sek = sk ek , k = 1, .
. . , m, ek 6≡ 0, sk — собственные значения матрицы S.Покажем, что S = S ∗ :111111S ∗ = (E − τ B − 2 AB − 2 )∗ = E ∗ − τ (B − 2 )∗ A∗ (B − 2 )∗ = E − τ B − 2 AB − 2 = SПокажем , что |sk | 6 ρ:11(E − τ B − 2 AB − 2 )ek = sk ek , ek 6= 0, k = 1, . . . , m11111Подействуем оператором B 2 слева : (B 2 −τ AB − 2 )ek = sk B 2 ek . Обозначая B − 2 ek = y, перепишем задачу в виде: (B − τ A)y = sk By.1 − skτ Ay = (1 − sk )By или Ay =ByτСвяжем полученное с условием (5) :(Ay, y) =1 − sk1−ρ1 − sk1+ρ(By, y) ,(By, y) 6(By, y) 6(By, y), (By, y) > 0ττττОткуда следует, что 1 − ρ 6 1 − sk 6 1 + ρ и |sk | 6 ρ ∀k = 1, m. Значит все значенияспектра матрицы S не превосходят по модулю ρ.Замечание.
Если D = D∗ , то существует ортонормированныйбазис из собствен(0, если k 6= l;ных векторов: Dek = dk ek , ∀k = 1, m, (ek , el ) = δkl =1, если k = l.mPТогда любой вектор x ∈ H разложим по базису однозначно: x =ci ei и верноравенство Парсеваля :2kxk =mPi=12ci — сумма коэффициентов Фурье.i=1Найдем оценку для z n+1 .mmmPPP(n)(n)(n)z n+1 = Sz n ⇒ z n =ck ek ⇒ z n+1 =ck Sek =ck sk ek .k=1k=1k=1Согласно равенству Парсеваля:kzn+1 2k =mXk=1(n)(ck sk )229И по доказанному выше, получаем:kzn+1 2k 6ρ2mX(n)(ck )2 = ρ2 kz n k2 ⇒ kz n+1 k 6 ρkz n kk=1Следствие 1.
Пусть A = A∗ , A > 0, B = B ∗ , B > 0, и ∃γ2 > γ1 > 0 : γ1 B < A <2, то выполняется оценка (6) kV n+1 kB 6 ρkV n kB ,γ2 B. Тогда если τ = τ0 =γ1 + γ21−ξγ1где ρ =, ξ=1+ξγ21−ρ1+ρ= γ2 и= γ1 — условия соответствуют теореме.Доказательство: ЕслиττВычитая и складывая ,получим :(2= γ1 + γ2γ2 − γ1τ⇒ρ=2ργ1 + γ2= γ2 − γ1τТак как γ2 6= 0γ1γ2ρ=γ11+γ21−и полагаяξ=γ1, получаем условия следствия.γ2Следствие 2. Для метода простой итерацииxn+1 − xn+ Axn = f , n = 1, 2, 3, . .
. , x0 — заданоτAПусть A = A∗ , A > 0 и γ1 = min(λAk ) , а γ2 = max(λk ) , ∀k = 1, m. Тогда если21−ξγ1τ=, то kV n+1 k 6 ρkV n k , положив ρ =, ξ=γ2 + γ11+ξγ2Доказательство: Воспользуемся следствием 1: операторное неравенство перейдетв γ1 E 6 A 6 γ2 E. Далее аналогично следствию 1 (при B = E).§8 Исследование сходимости попеременно треугольного итерационного методаРассмотрим матричное уравнение видаAx = f,(1)30где A — матрица размера (m × m), |A| =6 0.Матрица A имеет структуру A = R1 + R2 , где0.5a110...00 a210.5a22 .
. .00 R1 = .......... , ..... am1am2 . . . am−1,m 0.5amm0.5a11a12. . . a1,m−1a1m 00.5a22 . . . a2,m−1a2m R2 = .......... ..... 00...00.5ammТогда ПТИМ записывается в виде:(E + ωR1 )(E + ωR2 )xn+1 − xn+ Axn = f,τ(2)где n = 0, 1, 2, 3, . . . , τ > 0, ω > 0, x0 - задано.(τ и ω — итерационные параметры,а x0 — начальное условие)Метод неявный, так как B = (E + ωR1 )(E + ωR2 ).Теорема 4 (о достаточных условиях сходимости ПТИМ). Пусть A = A∗ > 0, w >τ, тогда итерационный метод (2), решение задачи (1), сходится при ∀x0 в средне4квадратичной норме.Доказательство: Из самой формулировки теоремы видно, что необходимо использовать теорему Самарского.
Из того, что R1 = R2∗ получаемB = (E+ωR2∗ )(E+ωR2 ) = E+ω(R2∗ +R2 )+w2 R2∗ R2 = {A = R2∗ +R2 } = E+ωA+ω 2 R2∗ R2А с другой стороны, мы можем записать B так:B = (E − ωR2∗ )(E − ωR2 ) + 2ωAТеперь осталось показать, что (E − ωR2∗ )(E − ωR2 ) неотрицательная величина,и тогда мы по теореме Самарсокого сможем связать B и A.Обозначим E − ωR2 = C =⇒ C ∗ = E − ωR2∗ . Откуда получаем, что скалярноепроизведение (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Значит при выполнении этого условия, справедлива теорема Самарского.31Теорема 5 (об оценкe скорости сходимости ПТИМ).
Путь A = A∗ > 0, пусть∃ δ > 0, ∆ > 0, такие что выполняется операторные неравенства:A > δE, R2∗ R2 6∆A422Положим ω = √ , τ =, гдеγ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 ∆.Убедимся в этом.Из условия (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, x) + (R2 x, x) = 2(R2 x, x).32Таким образом,δkxk2 6 (Ax, x) =(Ax, x)24(R2 x, x)2=(Ax, x)(Ax, x)Теперь воспользуемся неравенством Коши-Буняковского:∆4 (Ax, x)4(R2 x, x)26 4kxk2 = ∆kxk2 .(Ax, x)(Ax, x)Откуда получаем, что δ 6 ∆.
Исходя из следствия (1) §7, будем подбирать параметрγ2 (ω)ω такой, чтобы минимизировать ρ(ω). Рассмотрим функцию f (ω) =. Из ранееγ1 (ω)1B. Откуда ясно, что γ2 (ω) =доказанной теоремы B > 2ωA, следовательно A 62ω1.2ωТак как,1∆1ω2∆B = E + ωA + ω 2 R2∗ R2 6 A + ωA + ω 2 A = ( + ω +)A.δ4δ4−11ω2∆Получаем, что γ1 (ω) =+ω+. Перейдем к минимизации ρ(ω). Онаδ4достигает минимум, тогда достигает минимум функции f (ω) :∆1+ ω + ω21∆1δ4=+ ω .1+f (ω) =2ω2δω4Найдем производную:1f (ω) =20∆1− 24δω.12∆= 2 . И отсюда ω0 = ω = √ .4δωδ∆12f 00 (ω) =>02 δω 3Поскольку f 00 (ω) > 0, то при ω = ω0 достигается минимум f (ω), следовательнои ρ(ω).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
