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

Текущая версия

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

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

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

[править] Энергетическая норма

Пусть есть самосопряжённый положительно определённый оператор D = D* > 0

Положительно определённый оператор: Есть пространство x ∈ H. Оператор положительно определённый, если (Dx, x) > 0, ∀ x ≠ 0.

Неотрицательный оператор: (Dx, x) ≥ 0, ∀ x ≠ 0.

Если оператор положительно определённый, то тогда ∃ δ> 0: (Dx, x) ≥δ(x, x)

Теперь мы можем ввести энергетическую норму: ||x||_D = (Dx,x)^1/₂

Переходит в обычную при D = E.

Оказывается, можно ввести положительную определённость для несамосопряжённого вещественного оператора: если H — вещественный, то D > 0: (Dx, x) > 0, x ≠ 0

Если D = D* > 0, то ∃ D⁻¹ = (D⁻¹)* > 0. Кроме того, ∃ D^1/₂ = (D^1/₂)* > 0, ∃ D^−1/₂ = (D^−1/₂)* > 0.

Задача. H — вещественный, D > 0. Показать, что (^(D + D*)/₂x, x) = (Dx, x), ^(D + D*)/₂ > 0

Для оценки скорости сходимости введём вектор погрешности: vⁿ = xⁿ − x.

• Ax = f (1)
• ∃ A⁻¹ (m × m)
• B ^{(xn + 1 − xn)}/_τ + Axⁿ = f (2)
• xⁿ = vⁿ + x
• B (v^n + 1 − vⁿ)/τ + Avⁿ = 0 (3)
• (v^n + 1 − vⁿ)/τ + B⁻¹Avⁿ = 0
• vⁿ⁺¹ = vⁿ − τB⁻¹Avⁿ = (E − τB⁻¹A)vⁿ
• S = E − τB⁻¹A (4)

Мы получили матрицу перехода, и многое от неё зависит, точнее от её спектра. Чем компактнее спектр, тем лучше сходимость.

Теорема 1. Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S по модулю меньше 1: |λ_k^S| < 1.

Это означает, что оператор S — сжимающий.

(Доказательство есть в Бахвалове, на лекции не приводилось)

Далее H — вещественное.

Теорема 2 (Самарского, о достаточном условии сходимости метода (2)). Пусть есть A = A* = A^T > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0 (5). Тогда (2) сходится при любом начальном приближении в среднеквадратичной норме ||xⁿ − x|| = (∑_{i = 1}^m (x_iⁿ − xi)²)^1/₂ → 0, n → ∞.

Идея доказательства: введём числовую последовательность, докажем её монотонность, огрограниченность, и получим, что в этой норме вектор сходится к 0.

Доказательство. Введём y_n = (Avⁿ, vⁿ) ≥ 0. Найдём y_n + 1 = (Av^n + 1, v^n + 1) = (A(E − τB⁻¹A)vⁿ, (E − τB⁻¹A)vⁿ) = (Avⁿ, vⁿ) − τ((AB⁻¹Avⁿ, vⁿ) + (Avⁿ, B⁻¹Avⁿ) − τ(AB⁻¹Avⁿ, B⁻¹Avⁿ)) = (*)

(B⁻¹Avⁿ, Avⁿ) = (Avⁿ, B⁻¹Avⁿ)

(*) = y_n − τ(2(Avⁿ, B⁻¹Avⁿ) − τ(AB⁻¹Avⁿ, B⁻¹Avⁿ)) = y_n − 2τ((B − 0,5τA)B⁻¹Avⁿ, B⁻¹Avⁿ)

((B − 0,5τA)B⁻¹Avⁿ, B⁻¹Avⁿ) ≥ 0 ⇒ y_n + 1 ≤ y_n

Последовательность невозрастающая и, следовательно, имеет предел.

∃ δ > 0: ((B − 0,5τA)B⁻¹Avⁿ, B⁻¹Avⁿ) ≥ δ||B⁻¹Avⁿ||² (на основании задачи)

(y_n + 1 − y_n)/τ + 2((B − 0,5τA)B⁻¹Avⁿ, B⁻¹Avⁿ) = 0

В силу задачи можем подставить: (y_n + 1 − y_n)/τ + δ||B⁻¹Avⁿ||² ≤ 0

при n → ∞:

lim ||B⁻¹Avⁿ|| = 0

ωⁿ = B⁻¹Avⁿ

vⁿ = A⁻¹Bωⁿ

||vⁿ|| ≤ ||A⁻¹B|| ||ωⁿ||

lim_{n → ∞} ||vⁿ|| = 0

lim_{n → ∞} ||xⁿ − x|| = 0

чтд.

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

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

• A = R₁ + D + R₂
• D(x^n + 1 − xⁿ) + Ax^n + 1 = f
• τ = 1, B = D, a_ii ≠ 0
• D − 0,5A > 0
• 2D > A

чтд

Задача. Доказать, что если A = A* > 0 ⇒ a_ii > 0, i = 1..m

Следствие 2. Пусть ∃ A = A* > 0, матрица со строгим диагональным преобладанием: a_ii > ∑_{j = 1, j ≠ i}^m|a_ij|, i =1..m (6)

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

• 2D > A
• (Ax, x) = ∑_{i, j = 1}^ma_ijx_ix_j ≤ ∑_{i, j = 1}^m|a_ij| |x_i| |x_j| ≤ (ab < a² + b²) ∑_{i, j = 1}^m|a_ij| |x_i|²/2 + ∑_{i, j = 1}^m|a_ij| |x_j|²/2 = ∑_{i, j = 1}^m|a_ij| |x_i|²/2 + ∑_{j, i = 1}^m|a_ji| |x_i|²/2 = ∑_{i, j = 1}^m|a_ij| |x_i|² = ∑_{i, = 1}^m(a_ii + ∑_{j = 1, j ≠ i}^m|a_ij|) x_i² = (**)

2a_ii > a_ii + ∑_{j = 1, j ≠ i}^m|a_ij|

(**) < 2∑_{i, = 1}^ma_iix_i²

(Ax, x) < 2∑_{i, = 1}^ma_iix_i² = 2(Dx, x) ⇒ 2D > A — сходится

чтд.

Метод простой итерации: (x^{n + 1}+xn)/τ + Axⁿ = f, x⁰ — задано

Следствие 3. Пусть ∃ A = A* > 0, γ₂ = max_{1 ≤ x ≤ m}λ_k^A > 0. Тогда 0 < τ < 2/γ₂ МПИ сходится при ∀ x⁰

Доказательство. Условие преобразуется в E − 0,5τA > 0, 1 − 0,5τλ_k^A > 0, 1 − 0,5τγ₂ > 0, 0 < τ < 2/γ₂.