Конспект лекций - 3ий поток, лектор - Ионкин (1113828), страница 4

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

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

Пусть H — вещественное пространство, A = A∗ > 0,где A — матрица системы (1), τ > 0 и выполнено матричное неравенство:B − 0.5 τ A > 0(6)Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичной норме при любом начальном приближенииkxn − xk =mXj=1! 12(xnj − xj )2−−−→ 0 ,n→∞∀x0Доказательство: Введем числовую последовательность yn = (AV n , V n ) > 0. Дляначала докажем, что она монотонная. Для этого рассмотрим yn+1 :noyn+1 = (AV n+1 , V n+1 ) = V n+1 = SV n =no= (ASV n , SV n ) = S = (E −τ B −1A) == ( A(E − τ B −1A)V n , (E − τ B −1A)V n ) == (AV n , V n ) − τ (AV n , B −1 AV n ) + (AB −1 AV n , V n ) − τ (AB −1 AV n , B −1 AV n ) = ∗Итак, первое слагаемое по определению есть yn , рассмотрим вторую часть равенства.

Так как пространство H вещественное, то скалярное произведение коммутативно, поэтому(AB −1 AV n , V n ) = (B −1 AV n , A∗ V n ) = (B −1 AV n , AV n ) = (AV n , B −1 AV n )22Тогда получим∗ = yn − τ 2(AV n , B −1 AV n ) − τ (AB −1 AV n , B −1 AV n ) =no= (a, b) − α(c, b) = (a − αc, b) = y n − 2τ (B − 0.5τ A)B −1 AV n , B −1 AV nТаким образом мы получили тождествоyn+1 − yn+ 2 (B − 0.5τ A)B −1 AV n , B −1 AV n = 0,τв котором оператор (B − 0.5τ A) положительный по условию, а следовательно и всескалярное произведение неотрицательно:(B − 0.5τ A)B −1 AV n , B −1 AV n > 0Отсюда следует, чтоyn+1 6 yn ,что и означает монотонность последовательности yn .А значит, согласно теореме Вейерштрасса, у последовательности существует предел y:∃ lim yn = yn→∞Мы доказали, что введенная числовая последовательность yn является монотонной и ограниченной снизу, а значит, имеет предел.

Первая часть теоремы доказана.Чтобы приступить ко второй части доказательства, нам понадобится доказатьсвойство положительно определенного линейного оператора, которое сформулируемв виде задачи.Задача. Пусть H — вещественное пространство, C — положительный линейныйоператор. Доказать, что ∃ δ, такое что:(Cx, x) > δkxk2Итак, воспользовавшись данным свойством, можем сказать, что существует такая константа δ, что(B − 0.5τ A)B −1 AV n , B −1 AV n ) > δ kB −1 AV n k2Теперь, вспомнив ранее полученное тождество, можем записатьyn+1 − ynyn+1 − yn+ 2δ kB −1 AV n k2 6+ 2 (B − 0.5τ A)B −1 AV n , B −1 AV n = 0ττОбозначим для удобстваW n = B −1 AV n(7)23Отсюда видно, что если устремить n к бесконечности, то норма вектора W nустремится к нулюlim kW n k = 0n→∞А теперь выразим погрешность через введенный нами вектор.

Для этого домножим равенство (7) слева сначала на B, затем на A−1V n = A−1 BW nТак как норма произведения операторов не превосходит произведения их норм,то, оценив погрешность, получим, что она стремится к нулю при n стремящемся кбесконечностиkV n k 6 kA−1 Bk·kW n k −−−→ 0n→∞Так как нигде в доказательстве на начальное приближение мы не опирались, тооно произвольное. Следовательно! 21mXkV n k = kxn − xk =(xnj − xj )2−−−→ 0 , ∀x0n→∞j=1Следствие 1. Пусть A = A∗ > 0.Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении, если выполнено операторное неравенство2D > A,где A = R1 + D + R2 ,D = diag(a11 , a22 , .

. . , ann ).Доказательство: Положим, B = D и τ = 1. Тогда перепишем уравнение (2) в видеD(xn+1 + xn ) + Axn = fПо теореме Самарского метод сходится, еслиB − 0.5τ A > 0или в нашем случаеD − 0.5A > 0,а это выполняется в силу условия. Следовательно, метод Якоби сходится.Следствие 2. Пусть самосопряженная положительно определенная матрицаA = A∗ > 0 является матрицей со строгим диагональным преобладаниемaii >mX|aji |(8)j=1i6=jТогда метод Якоби сходится при любом начальном приближении в среднеквадратичной норме.24Доказательство: Покажем, что если есть строгое диагональное преобладание, товерно матричное неравенство2D > A,которое доказывает сходимость метода (согласно следствию 1). Рассмотрим квадратичную форму (Ax, x):mm1X1X2(Ax, x) =|aij |·|xi | +|aij |·|xj |2 =aij xi xj 6|aij |·|xi |·|xj | 622i,j=1i,j=1i,j=1i,j=1mXmXmmnoX1X2|aij |·|xi | )·2 =|aij |·|xi |2= aij = aji = (2 i,j=1i,j=1Выделим отдельно суммирование по индексу i:(Ax, x) 6mXx2ii=1mmmo XX nXaii +|aij | <2aii x2i = (2Dx, x).|aij | < aii <j=1i6=jj=1i6=ji=1Таким образом, мы получили, что(Ax, x) < (2Dx, x),откуда следует, что2D > AСледовательно выполняется условие следствия 1, и итерационный метод Якобисходится при любом начальном приближении.Задача.

Пусть A = A∗ > 0.Доказать, что aii > 0, i = 1, m.Следствие 3. Пусть A = A∗ > 0.Тогда метод Зейделя сходится в среднеквадратичной норме при любом начальном приближении.Доказательство: По определению метода Зейделя имеем:τ = 1,B = D + R1 .Исходя из условия теоремы Самарского, для того, чтобы сходился метод Зейделя, достаточно выполнения неравенстваB − 0.5τ A > 0.Докажем это.25Распишем матрицы A и B:1D + R1 − (R1 + D + R2 ) > 02⇓D + R1 − R2 > 0⇓(D + R1 − R2 )x, x > 0⇓0 < (Dx, x) + (R1 x, x) − (R2 x, x) = (Dx, x) + (R1 x, x) − (R1∗ x, x) = (Dx, x)Откуда получаем, что(Dx, x) > 0А мы уже знаем, что если матрица самосопряженная и положительно определенная, то все ее диагональные элементы больше нуля.

Следовательно, матрица Dтоже является положительно определенной, откуда следует верность неравенства.Следствие 4. Пусть A = A∗ , > 0. Рассмотрим метод простой итерации:xn+1 − xn+ Ax = 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)xn+1 − xnB+ Axn = f ,τ(2)Решаем итерационным методом:26где τ > 0, ∃B −1 , n = 1, 2, 3, . . .

, начально приближение x0 — задано.Введем погрешность V n = xn − x. Тогда из (2) получаем:V n+1 − V n+ AV n = 0 ,τгде τ > 0, n = 1, 2, 3, . . . , начально приближение V 0 = x0 − x — задано.Поставим задачу получения оценки вида:BkV n+1 k 6 ρkV n k ,(3)(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 − xk11Из свойства транзитивности неравенств получим: ρn 6 ε ⇒ nln > ln . Тогдаρε11проделав число итераций n0 (ε) = ln / lnбудет верна оценка n > n0 (ε), где ε —ερ1точность приближения, ln — скорость сходимости.ρВведем вещественное линейное пространство H , размерность которого равна m.

Внем вводим скалярное произведение∀x, y ∈ H (x, y) =mXxi y ii=1и среднеквадратичную норму:vu mpuXxi 2kxk = (x, x) = ti=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)27Доказательство:Замечание.

Рассмотрим правую часть операторного неравенства (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):1B21V n+1 − V n+ B − 2 AV n = 0τ1Введем вектор z n = B 2 V n .

Чтобы получить (6), достаточно получитьkz n+1 k 6 ρkz n k(7)11Это верно в силу самосопряженности оператора 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ττττ28Откуда следует, что 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 и верноkxk2 =равенство Парсевля :mPi=1ci 2 — сумма коэффициентов Фурье.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 =mX(n)(ck sk )2k=1И по доказанному выше, получаем:kz n+1 k2 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 + γ2j11−ξ, ξ=где ρ =1+ξj21+ρ1−ρДоказательство: Если= γ2 и= γ1 — условия соответствуют теореме.ττВычитая и складывая ,получим :(2= γ1 + γ2γ2 − γ1τ⇒ρ=2ργ1 + γ2= γ2 − γ1τТак как γ2 6= 0γ1γ2ρ=γ11+γ21−и полагаяξ=γ1, получаем условия следствия.γ229Следствие 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)где A — матрица размера (m × m), |A| =6 0.Матрица A имеет структуру A = R1 + R2 , где0.5a110...00 a210.5a22 . . .00 R1 =  ..........

 , ..... am1am2 . . . am−1,m 0.5amm0.5a110. . . 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квадратичной норме.30Доказательство: Из самой формулировки теоремы видно, что необходимо использовать теорему Самарского. Из того, что 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∗ .

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

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