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

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

Глава 1

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

Решаем систему (1), (2):

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

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

Теорема (об оценке скорости сходимости ПТИМ). Пусть A = A* > 0. Пусть существуют такие две константы δ > 0, Δ > 0:

• A ≥ δE, R*₂R₂ ≤ Δ/4 A (2)
• Положим ω = 2/√δΔ, τ = 2/(γ₁ + γ₂), γ₁ = √δ/2 (√δΔ/(√δ+√Δ)); γ₂ = √δΔ/4 (4)
• ||x^{n + 1} − x||_B ≤ ρ ||xⁿ − x||_B (5)
• где B = (E + ωR*₂)(E + ωR₂), ρ = (1 − √η)/(1 + 3√η), η = δ/Δ (6)
  • R*₂ = R₁

Доказательство. Для начала убедимся, что δ ≤ Δ. Лектор напомнит ещё, что значит неравенство (3):

• (Ax, x) ≥ δ(x, x) = δ||x||², x ≠ 0
• (R*₂R₂x, x) = (R₂x, R₂x) = ||R₂x||² ≤ Δ/4 (Ax, x)
• δ||x||² ≤ (Ax, x) = (Ax, x)²/(Ax, x)

Далее, что такое (Ax, x):

• (Ax, x) = ((R₁ + R₂)x, x) = (R₁x, x) + (R₂x, x) = {так как R₁ = R*₂} = (R*₂x, x ) + (R₂x, x) = (x, R₂x) + (R₂x, x) = 2(R₂x, x)

Теперь можно записать, что

• δ||x||² ≤ (Ax, x) = (Ax, x)²/(Ax, x) = 4(R₂x, x)²/(Ax, x)

Воспользуемся неравенством Коши-Буняковского:

• 4(R₂x, x)²/(Ax, x) ≤ (4||R₂x||²||x||²)/(Ax, x) ≤ 4Δ/4 (Ax, x)||x||²/(Ax, x) = Δ||x||²

Из этого следует, что δ ≤ Δ, причём неравенство почти всегда строгое.

Доказательство собственно теоремы:

//Где-то рядом записано: γ₁B ≤ A ≤ γ₂B

Запишем B = E + ωA + ω²R*₂R₂ = (*)

• мы показали, что B ≥ 2ωA
• A ≤ ½ ωB
• γ₂ = 1/2ω
• (*) ≤ 1/δ A + ωA + ω² Δ/4 A = (1/δ + ω + ω²Δ/4)A
• γ₁ = (1/δ + ω + ω²Δ/4)⁻¹
• ||x^{n + 1} − x||_B ≤ ρ ||xⁿ − x||_B
• ρ = (1 − ξ(ω))/(1 + 3ξ(ω)), ξ = γ₁/γ₂
• τ = 2/(γ₁(ω)+γ₂(ω))
• f(ω) = γ₂(ω)/γ₁(ω) = (1/δ + ω + ω²Δ/4)/(2ω) = ½ (1 + 1/δω + ωΔ/4)
• Для максимальной скорости сходимости необходимо найти минимум: f'(ω)=1/2 (Δ/4 − 1/δω²), 1/δω² = Δ/4, ω² = 4/δΔ, ω = 2/√δΔ = ω₀
• f''(ω₀) = 1/δω³ > 0 ⇒ ω₀ — минимум ⇒ максимальная скорость сходимости

Теперь получаем остальное:

• γ₂ = 1/2ω = √δΔ/4
• γ₁ = (1/δ + 2/√δΔ + 4Δ/(δΔ×4)) = 2(1/δ + 1/√δΔ)⁻¹ = ½ ((√δ + √Δ)/(δ√Δ))⁻¹ = √δ/2 (√δΔ/(√δ + √Δ))
• ρ = (1 − ξ)/(1 + ξ)
  • ξ = γ₁/γ₂ = √δ/2 (√δΔ × 4/(√δ + √Δ)√δΔ) = 2√δ/(√δ + √Δ)
  • 1 − ξ = 1 − 2√δ/(√δ + √Δ) = (√δ + √Δ − 2√δ)/(√δ + √Δ) = (√Δ − √δ)/(√δ + √Δ)
  • 1 + ξ = 1 + 2√δ/(√δ + √Δ) = (√Δ − 3√δ)/(√δ + √Δ)
  • ρ = (√Δ − √δ)/(√Δ − 3√δ) = (1 − √η)/(1 + 3√η), η = δ/Δ

чтд

Разные итерационные методы сравниваются по количеству действий для достижения необходимой точности:

• n₀(ε) = [^{ln 1/_ε}/_{ln ¹/ρ}]

Замечание. Большинство задач, которое приходится решать математикам таково, что число η = O(m⁻²) маленькое, ¹/_η ~ O(m²) большое. Посмотрим, сколько потребуется итераций:

• ¹/_ρ = ^{1 + 3√η}/_{1 − √η} ≈ ^{(1 + 3√η)(1 + √η)}/_{1 − η} ≈ 1 + 4√η. Тогда ln ¹/_ρ = 4√η = O(m⁻¹), n₀(ε) = O(m)

Метод простой итерации

Теперь рассмотрим метод простой итерации (метод релаксации):

• ||x^{n + 1} − x|| ≤ ρ ||xⁿ − x||, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2, ξ = η = O(m⁻²)
• 1/ρ = ^{1 + η}/_{1 − η} ≈ (1 + η)² ≈ 1 + 2η
• ln ¹/_ρ ≈ η, n₀(ε) = O(m²)

Параграф 9. Методы решения задач на собственные значения.

Это гигантский совершенно класс задач, очень сложный с точки зрения решения.

Есть совершенно произвольная вещественная матрица A. Нужно найти λ такие, что Ax = λx, x ≠ 0 (1)

• λ — собственные значения
• x — собственные вектора

Замечание. Математики перенормировывают собственные вектора каждый раз. Чтобы ошибки округления не исказили сам подход.

Находим корни характеристического многочлена f(λ) = |A − λE| = 0

Два круга проблем:

• Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
• Полная проблема собственных значений — нужно находить все собственные значения

Всего m значений (с учётом кратности): λ_k, k = 1..m

Вообще говоря, собственные значения комплексные.

Все методы итерационные. Один из самых простых методов — степенной метод.

Степенной метод

x_n — n-я итерация.

Степенной метод — метод, который описывается уравнением 2:

• x_{n + 1} = Ax_n (2)
• n = 0, 1, ..., x₀ — начальное приближение
• x_n = Aⁿx₀ (3)

Условия:

• Предположения относительно матрицы A:
  • Все собственные значения расположены в порядке неубывания модуля: |λ₁| ≤ |λ₂| ≤ |λ₃| ≤ ... ≤ |λ_{m − 1}| < |λ_m|
  • Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {e_k}₁^m — базис из собственных векторов A (Ae_k = λ_ke_k, k = 1..m)
  • Ограничение B: последнее собственное значение не является кратным: |(λ_{m − 1})/(λ_m) < 1
  • Ограничение C: ∀ x = c₁e₁ + ... + c_me_m, c_m ≠ 0

x_n = c₁λ₁ⁿe₁ + c₂λ₂ⁿe₂ + ... + c_mλ_mⁿe_m

x_n/c_mλⁿ_m = (c₁/c_m)(λ₁/λ_m)ⁿe₁ + (c₂/c_m)(λ₂/λ_m)ⁿe₂ + ... + e_m

x_n^{(i) — координата} = c₁λ₁ⁿe₁⁽ⁱ⁾ + c₂λ₂ⁿe₂⁽ⁱ⁾ + ... + c_mλ_mⁿe_m⁽ⁱ⁾ x_n+1⁽ⁱ⁾ = c₁λ₁ⁿ⁺¹e₁⁽ⁱ⁾ + c₂λ₂ⁿ⁺¹e₂⁽ⁱ⁾ + ... + c_mλ_mⁿ⁺¹e_m⁽ⁱ⁾

x_n+1⁽ⁱ⁾/x_n⁽ⁱ⁾ = λ_m⁽ⁿ⁾ = λ_m + O(|λ_{m − 1}/λ_m|)ⁿ