Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Содержание 1 Глава 1. Численные методы линейной алгебры 1.1 Параграф 6. Теоремы о сходимости итерационных методов 1.2 Параграф 7. Оценка скорости сходимости итерационных методов 1.3 Параграф 8. Исследование сходимости ПТИМ

Глава 1. Численные методы линейной алгебры

Параграф 6. Теоремы о сходимости итерационных методов

Следствие 4. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме.

Доказательство.

• метод Зейделя: (D + R₁)^{(xn + 1 − xn)}/_τ + Axⁿ = f
• B − 0,5τA > 0, τ = 1
• D + R₁ = B, τ = 1
• D + R₁ > ¹/₂ (R₁ + D + R₂)
• 2D + 2R₁ > R₁ + D + R₂
• D + R₁ − R₂ > 0
• ((D + R₁ − R₂)x, x) > 0
• (Dx, x) + (R₁x, x) − (R₂x, x) > 0 ⇒ (Dx, x) > 0
• R₁ = R₂*
• R₂ = R₁*
• a_ii > 0, i = 1, m
• (R₁x, x) = (x, R₁*x) = (xR₂, x) = (R₂x, x)

чтд

Параграф 7. Оценка скорости сходимости итерационных методов

• Ax = f (1)
• |A| ≠ 0, A ∈ ℝ^{m × m}
• B ^{(xn + 1 − xn)}/_τ + Axⁿ = f, n ∈ ℕ ∪ {0} (2)
• x⁰ задано
• vⁿ = xⁿ − x — погрешность
• B ^{(vn + 1 − vn)}/_τ + Avⁿ = 0, n ∈ ℕ ∪ {0} (3)
• v⁰ = x⁰ − x

Если в какой-либо норме удаётся получить оценку вида

• ||v^{n + 1}|| ≤ ρ||vⁿ||, 0 < ρ < 1 (4)

то ||vⁿ|| ≤ ρⁿ||v⁰|| → 0 при n → ∞

• ||xⁿ − x|| ≤ ρⁿ||x⁰ − x||
• ||xⁿ − x|| ≤ ε||x⁰ − x||
• ρⁿ ≤ ε
• ¹/_ε ≤ (¹/_ρ)ⁿ
• n ln ¹/_ρ ≥ ln ¹/_ε
• n ≥ n₀(ε) = [^{ln 1/_ε}/_{ln ¹/ρ}]

ln ¹/_ρ — скорость сходимости итерационного метода

Пусть H — вещественное пространство, dim H = m

• ∀ x, y ∈ H (x, y) = ∑_{i = 1}^mx_iy_i
• ||x|| = (∑_{i = 1}^m x_i²)^1/₂

Пусть B = B* > 0

Энергетическая норма ||x||_B = (Bx,x)^1/₂

Теорема 4 (об оценке скорости сходимости итерационного метода). Пусть

• A = A* > 0
• B = B* > 0
• 0 < ρ < 1
• ^{1 − ρ}/_τB ≤ A ≤ ^{1 + ρ}/_τB (5)

Тогда итерационный метод (2) сходится к решению СЛАУ (1) и имеет место оценка ||v^{n + 1}||_B ≤ ρ||vⁿ|| (6)

Доказательство. Сходимость:

• A ≤ ^{1 + ρ}/_τB
• A < ²/_τB
• B − 0,5τA > 0

Оценки:

• B ^{(vn + 1 − vn)}/_τ + Avⁿ = 0 (*)
• ∃ B^½, B^−½, B^½ = (B^½)* > 0

умножим (*) на B^−½ слева:

• B^{½ (vn + 1 − vn)}/_τ + B^−½Avⁿ = 0
• zⁿ = B^½vⁿ
• vⁿ = B^−½zⁿ
• ^{zn + 1 − zn}/_τ + B^−½AB^−½zⁿ = 0
• z^{n + 1} = zⁿ & minus; τB^−½AB^−½zⁿ = (E − τB^−½AB^−½)zⁿ = Szⁿ
  • S = E − τB^−½AB^−½ (7)
• ||zⁿ||² = (zⁿ, zⁿ) = (B^½vⁿ, B^½vⁿ) = (Bvⁿ, vⁿ) = ||vⁿ||_B

Покажем, что S — самосопряжённая:

• S* = E − τB^−½AB^−½

1. Покажем, что все собственные значения матрицы S по модулю не превосходят ρ

   Пусть s_k — собственное значение, k = 1, m

   • (E − τB^−½AB^−½)x = s_kx, x ≠ 0

   Домножим на B^½ слева:

   • (B^½ − τAB^−½)x = s_kB^½x
   • y = B^−½x
   • x = B^½)y
   • (B − τA)y = s_kBy
   • τAy = (1 − s_k)By
   • Ay = ^{(1 − s_k)}/_τBy

   Применим оценку (5):

   • ^{1 − ρ}/_τ(By, y) ≤ (Ay, y) = ^{(1 − s_k)}/_τBy ≤ ^{1 + ρ}/_τ(By, y)
   • (By, y) ≥ 0
   • 1 − ρ ≤ 1 − s_k ≤ 1 + ρ ⇒ |s_k| < ρ, k = 1, m

2. S = S*

   • {e_k} — ортонормированный базис из собственных векторов S
   • S_ek = s_ke_k? k = 1, m
   • zⁿ = ∑_k = 1^mc_k⁽ⁿ⁾e_k
   • z^n + 1 = Szⁿ = ∑_k = 1^ms_kc_k⁽ⁿ⁾e_k
   • ||z^n + 1||² = ∑_k = 1^ms_k²(c_k⁽ⁿ⁾)²
   • ||z^n + 1||² ≤ ρ²∑_k = 1^m(c_k⁽ⁿ⁾)² = ρ²||zⁿ||²
   • ||z^n + 1|| ≤ ρ||zⁿ||
   • ||v^n + 1||_B ≤ ρ||vⁿ||_B

чтд

Следствие 1.

• A = A* > 0
• B = B* > 0
• 0 < ρ < 1
• ∃ γ₁ > 0, γ₂ > 0: γ₁B ≤ A ≤ γ₂B (8)

Тогда

• τ = τ₀ = ²/_{γ1 + γ2}, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2

Доказательство:

• ^{1 − ρ}/_τ = γ₁
• ^{1 + ρ}/_τ = γ₂
• ²/_τ = γ₁ + γ₂
• τ = ²/_{γ1 + γ2}
• γ₁ − γ₂ = ^2ρ/_τ = ρ(γ₁ + γ₂)
• ρ = ^{γ₁ − γ₂}/_{γ1 + γ2} = ^{1 − γ₁/_γ2}/_{1 + ^γ1/γ2} = ^{1 − ξ}/_{1 + ξ}

Следствие 2. Пусть A = a* > 0,

• γ₁ = min_{1 ≤ k ≤ m} λ_k^A, > 0 в силу положительной определённости
• γ₂ = max_{1 ≤ k ≤ m} λ_k^A

Тогда МПИ (xⁿ⁺¹ − xⁿ)/τ + Axⁿ = f, где τ = ²/_{γ1 + γ2}, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2 — сходится, имеет место оценка ||xⁿ − x|| ≤ ρ||xⁿ − x||

Доказательство. аналогично Следствию 1.

Параграф 8. Исследование сходимости ПТИМ

• Ax = f (1)
• |A| ≠ 0, A ∈ ℝ^{m × m}
• A = R₁ + R₂,

R1 = ( a11/2 … aij ) ⋱ 0 … amm/2

R2 = ( a11/2 … 0 ) ⋱ aij … amm/2

• (E + ωR₁)(E + ωR₂)^{(xn+1 − xn)}/_τ + Axⁿ = f, ω, τ > 0, n ∈ ℕ ∪ {0}, x⁰ — задано

Теорема (о сходимости ПТИМ). Пусть A = A* > 0, ω > ^τ/₄. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.

Доказательство.

• R₁ = R₂* (так как A = A*)
• B = (E + ωR₂*)(E + ωR₂) = E + ω(R₁ + R₂) + ω²R₂*R₂ = E + ωA + ω²R₂*R₂
• (E − ωR₂*)(E − ωR₂) = E − ωA + ω²R₂*R₂
• B = (E − ωR₂*)(E − ωR₂) + 2ωA
• ((E − ωR₂*)(E − ωR₂)x, x) = ((E − ωR₂*)x, (E − ωR₂)x) ≥ 0
• B ≥ 2ωA
• B − 2ωA ≥ 0

так как ω > ^τ/₄, то 2ω > 0,5τ

• B − 0,5τ > 0

чтд