Численные методы. Соснин (2005) (1160462), страница 3
Текст из файла (страница 3)
Пусть B = D + ωA1 , τ = ω, A — симметрическая положительно определенная матрица и ω ∈ [0; 2], тогда метод релаксации является сходящимся для любого начального приближения.14Глава 1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙДоказательство. Проверим выполнение достаточного условия сходимости стационарного одношагового итерационного метода (теорема 1.1):B−τA > 0,2подставив формулы для B и τ из условия теоремы. Таким образом, для доказательства теоремыдостаточно показать, что2D + 2ωA1 − ωA > 0(1.14)Представим матрицу A в виде (1.13), тогда:hAx, xi = hA1 x, xi + hDx, xi + x, AT2 x = { x, AT2 x = hA1 x, xi} == hDx, xi + 2 hA1 x, xi .Теперь перепишем (1.14):h(2D + 2ωA1 − ωA)x, xi > 0.Подставим сюда разложение матрицы A и раскроем скобки:2 hDx, xi + 2ω hA1 x, xi − 2ω hA1 x, xi − ω hDx, xi > 0.В результате получаем:(2 − ω) hDx, xi > 0,где hDx, xi > 0 в силу того, что hAx, xi > 0 и примечания к определению положительно определеннойматрицы, а множитель (2 − ω) больше нуля в силу условия теоремы.Утверждение 1.3 (необходимое и достаточное условие сходимости метода простой итерации).
Пустьматрица A — симметрическая положительно определенная, а параметр τ больше нуля. Тогда для2сходимости метода простой итерации необходимо и достаточно, чтобы τ <, где λ(A) —λmax (A)3некоторое собственное значение матрицы A.Доказательство. Достаточность.
Пусть, согласно требованию теоремы,τ<2λmax (A).Тогда это верно для любого собственного значения матрицы A :τ<2λ(A)⇐⇒1−τλ(A) > 02⇐⇒λ(E −τA) > 0.2Это значит, что все собственные значения матрицы E − τ2 A положительны, то есть она положительно определена. Так как B = E, то по теореме 1.1 метод простой итерации является сходящимся.Необходимость.
Возьмем в качестве начального приближения x0 = x + µ, где µ — собственныйвектор A :Aµ = λmax (A)µ.Рассмотрим наш итерационный процесс:xk+1 − xk+ Axk = f.τ(1.15)3 Далее такое обозначение будет использовано для собственных значений других матриц; иногда (например, в неравенствах) оно может обозначать весь спектр.1.3. СХОДИМОСТЬ ОДНОШАГОВЫХ СТАЦИОНАРНЫХ МЕТОДОВ15Заменим xk на погрешность решения z k : z k = xk − x, где x — точное решение. Тогда для погрешности получим такое выражение:z k+1 − z k+ Az k = 0τ=⇒z k+1 = (E − τ A)z k∀k.Выразим z k через предыдущие значения:z k = (E − τ A)z k−1 = .
. . = (E − τ A)k z 0 .Заметим, что z 0 = µ :(E − τ A)k µ = (E − τ A)k−1 (µ − τ Aµ) = (E − τ A)k−1 (1 − τ λmax (A))µ = . . . = (1 − τ λmax (A))k µ.Таким образом:z k = (1 − τ λmax (A))k µ.Посчитаем норму z k :||z k || = |1 − τ λmax (A)|k ||µ||.k→∞Так как итерационный процесс сходится ( ||z k || −→ 0 ), то |1−τ λmax (A)| < 1. Раскрыв знак модуля,получим:21 − τ λmax (A) < 1;.=⇒ 0 < τ <1 − τ λmax (A) > −1.λmax (A)Утверждение доказано.Сходимость стационарных методовТеперь установим необходимое и достаточное условие сходимости для стационарных одношаговых итерационных методов. Для этого перейдем в итерационном процессеBxk+1 − xk+ Axk = fτBz k+1 − z k+ Az k = 0.τ(1.16)к погрешности z k = xk − x :Отсюда получим формулу z k+1 = (E − τ B −1 A)z k , и обозначим S = E − τ B −1 A.
Матрица Sназывается матрицей перехода. Теперь выражение для z k+1 выглядит так:z k+1 = Sz k .(1.17)Теорема 1.2 (Критерий сходимости одношагового стационарного итерационного метода). Итерационный метод (1.16) сходится для любого начального приближения x0 тогда и только тогда, когдадля всех собственных значений λ(S) выполнено |λ(S)| < 1.Доказательство.
Необходимость. Пусть µ — собственный вектор S, соответствующий собственномузначению λ(S). Рассмотрим вектор начального приближения x0 = µ + x, тогда z 0 = x0 − x = µ.Все погрешности связаны соотношением (1.17). Выразим из него z kz k = Sz k−1 = S 2 z k−2 = . . . = S k z 0 ,где z 0 = µ, тогдаz k = S k µ = S k−1 λ(S)µ = . . .
= λk (S)µ.16Глава 1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙВ силу сходимости верно, чтоk→∞||z k || −→ 0=⇒k→∞||λk (S)µ|| −→ 0=⇒k→∞|λ(S)|k ||µ|| −→ 0.Отсюда следует, что |λ(S)| < 1.Достаточность. Пусть матрица S — матрица простой структуры, причем |λ(S)| < 1. Из этогоследует, что существуют собственные вектора, образующие ортонормированный базис {ξi }ni=1 .nXПусть z 0 =ci ξi — разложение z 0 по базису. Тогда получим следующее выражение для погрешности:i=1zk = S k z0 = S knXci ξi = S k−1i=1nXci Sξi = S k−1i=1nXci λi ξi = . . . =nXi=1ci λki ξi .i=1Рассмотрим норму погрешности: nnnX XXk→∞ci λki ξi 6|ci | · |λi |k ||ξi || 6 {ρ = max |λi (S)| < 1} 6 ρk|ci | · ||ξi || −→ 0,||z k || = ii=1в силу того чтоnXi=1i=1|ci | · ||ξi || ограничено.i=1Примечание.1. При доказательстве достаточности предполагалась, что матрица S — матрица простой структуры.
Теорема верна и без этого предположения, которое сделали для упрощения доказательства.2. На первый взгляд кажется, что область применения этого утверждения широка, но на практике найти весь спектр матрицы перехода непросто (иногда сложнее, чем решить системупрямым методом).Пусть для погрешности итерационного метода справедливо неравенство:||xk − x|| 6 q k ||x0 − x||,где q ∈ (0, 1).(1.18)Определение. Итерационный метод, погрешность итерационного приближения которого удовлетворяет (1.18), сходится со скоростью геометрической прогрессии со знаменателем q.Потребуем, взяв ε > 0, чтобы q k < ε. Тогда для погрешности итерационного метода будет выполнена оценка:||xk − x|| < ε||x0 − x||.1А это означает, что к k-й итерации погрешность начального приближения уменьшится враз.εТаким образом, число итераций, необходимых для достижения требуемой точности ε, будет&'ln 1εk > k0 (ε) =.ln 1qОпределение.
Число ln 1q называется скоростью сходимости итерационного метода.Примечание. Вообще говоря, число q из вышеприведенных неравенств определяется неоднозначно.Для формальности можно считать, что это минимальное из всех q, удовлетворяющих (1.18).1.4. ОЦЕНКА ПОГРЕШНОСТИ ОДНОШАГОВЫХ СТАЦИОНАРНЫХ МЕТОДОВ1.417Оценка погрешности одношаговых стационарных методовДалее мы будем активно использовать матричные неравенства, например A > B. Оно означает, чтодля всех x hAx, xi > hBx, xi .Введем норму вектора x, порожденную симметричной положительно определенной матрицей A :p||x||A = hAx, xi.Теорема 1.3 (Оценка погрешности стационарных одношаговых итерационных методов).
Пусть матрицы A, B симметричны и положительно определены, и существуют такие положительные константы γ1 , γ2 , чтоγ1 B 6 A 6 γ2 B.(1.19)Тогда итерационный метод, задаваемый уравнениемBxk+1 − xk+ Axk = f,τгде τ =2,γ1 + γ2(1.20)сходится для любого начального приближения x0 со скоростью геометрической прогрессии:||xk − x||A 6 q k ||x0 − x||A ,где q =1−ξγ1, ξ= .1+ξγ2Доказательство. Перейдем от приближений xk к погрешности на k-й итерации: z k = xk − x. Какуже было показано, уравнение (1.20) можно переписать так:Bz k+1 − z k+ Az k = 0,τи из него следует, чтоz k+1 = Sz k ,S = E − τ B −1 A.(1.21)Теперь установим справедливость такого неравенства:||z k+1 ||A 6 q||z k ||A .(1.22)1Известно, что для матрицы A = AT > 0 существует такая матрица, обозначаемая A 2 , что11(A )2 = A, причем A 2 = (A 2 )T > 0.Домножим (1.21) слева на эту матрицу:1211A 2 z k+1 = A 2 Sz k11⇐⇒1111A 2 z k+1 = A 2 SA− 2 A 2 z k .1Обозначив ω k = A 2 z k и S = A 2 SA− 2 , получим, чтоω k+1 = Sω k .111111Заметим, что S = A 2 SA− 2 = A 2 (E − τ B −1 A)A− 2 = E − τ A 2 B −1 A 2 .11Обозначив C = A 2 B −1 A 2 , получим, чтоS = E − τ C.(1.23)Легко проверить, что матрицы C и S будут симметричны, а C — еще и положительно определена(это понадобится нам чуть позже).Теперь преобразуем ||z k ||A :rDqE rD 1E q111kkkkk||z ||A = hAz , z i =A2 A2 z , z =A 2 z k , A 2 z k = hω k , ω k i = ||ω k ||.18Глава 1.
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙТаким образом, от доказательства неравенства (1.22) можно перейти к доказательству того, что||ω k+1 || 6 q||ω k ||.(1.24)Преобразуем ω k+1 :E D 2||ω k+1 ||2 = ω k+1 , ω k+1 = Sω k , Sω k = S ω k , ω k .2Теперь будем искать такие q, что S 6 q 2 E — как видно из последних преобразований, этого будетдостаточно для доказательства (1.24).2Итак, предположим, что S 6 q 2 E. Тогда, по свойству симметричных матриц, и в силу того, чтоC положительно определена, это эквивалентно тому, что−qE 6 S 6 qE ⇐⇒ {подставим (1.23)} ⇐⇒ −qE 6 E − τ C 6 qE ⇐⇒τ C 6 (1 + q)E;τ E 6 (1 + q)C −1 ;−1⇐⇒⇐⇒ {домножим на C } ⇐⇒τ C > (1 − q)E.τ E > (1 − q)C −1 .Из этой системы вытекает такое двойное неравенство:1 − q −11 + q −1C 6E6C .ττ1111Из того, что C = A 2 B −1 A 2 , следует, что C −1 = A− 2 BA− 2 . Таким образом, предыдущее двойноенеравенство эквивалентно такому:111 − q −11 + q −1A 2 BA− 2 6 E 6A 2 BA− 2 .ττ1Умножив его слева и справа на A 2 , получим1+q1−qB6A6B.ττ(1.25)Очень похоже на одно из условий теоремы.
Покажем, что1−q= γ1 ,τ1+q= γ2 .τ(1.26)Действительно:11 − γγ22 −γ(γ2 + γ1 ) − (γ2 − γ1 )1−q+γ1=== γ1 ;2τ2γ2 +γ111 + γγ22 −γ1+q(γ2 + γ1 ) + (γ2 − γ1 )+γ1=== γ2 .2τ2γ2 +γ1Итак, мы показали, что неравенство ||z k+1 ||A 6 q||z k ||A эквивалентно матричному неравенствуγ1 B 6 A 6 γ2 B из условия теоремы.Таким образом, показано, что ||z k+1 ||A 6 q||z k ||A для любого k. Тогда, переходя к более раннимчленам последовательности, получим:||z k ||A 6 q||z k−1 ||A 6 . . . 6 q k ||z 0 ||.Из этого напрямую следует, что||xk − x||A 6 q k ||x0 − x||A .Теорема доказана.1.4. ОЦЕНКА ПОГРЕШНОСТИ ОДНОШАГОВЫХ СТАЦИОНАРНЫХ МЕТОДОВ19Замечание 1. В случае, когда ξ мало, можно получить такую оценку для скорости сходимости:11+ξ2ξln = ln= ln 1 +≈ 2ξ.q1−ξ1−ξЗамечание 2. Из теоремы 1.3 следует, что выбор чисел γ1 , γ2 напрямую влияет на скорость сходимости. Для выяснения их возможных значений рассмотрим произвольный собственный вектор µматрицы B −1 A :B −1 Aµ = λ(B −1 A)µ.Это эквивалентно тому, что Aµ = λ(B −1 A)Bµ (мы просто домножили на B ).
Как известно, неравенствоγ1 B 6 A 6 γ2 B(1.27)означает, что γ1 hBx, xi 6 hAx, xi 6 γ2 hBx, xi для любого x. Положим x = µ и преобразуем этодвойное неравенство:γ1 hBµ, µi 6 hAµ, µi 6 γ2 hBµ, µi ⇐⇒⇐⇒ γ1 hBµ, µi 6 λ(B −1 A) hBµ, µi 6 γ2 hBµ, µi =⇒=⇒ γ1 6 λ(B −1 A) 6 γ2 .Так как собственный вектор мы выбирали произвольно, то получаем, чтоγ1 6 λmin (B −1 A),γ2 > λmax (B −1 A).Таким образом, наиболее точными константами, с которыми выполняется неравенство (1.27), являются константыγ1 = λmin (B −1 A), γ2 = λmax (B −1 A).В этом случае параметрτопт =2λmin (B −1 A) + λmax (B −1 A)называется оптимальным итерационным параметром.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
