Численные Методы, 04 лекция (от 20 февраля)

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

Версия от 17:59, 21 июня 2007; Esyr01 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Глава 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/2

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

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

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

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

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

  • Ax = f (1)
  • ∃ A−1 (m × m)
  • B (xn + 1 − xn)/τ + Axn = f (2)
  • xn = vn + x
  • B (vn + 1 − vn)/τ + Avn = 0 (3)
  • (vn + 1 − vn)/τ + B−1Avn = 0
  • vn+1 = vn − τB−1Avn = (E − τB−1A)vn
  • S = E − τB−1A (4)

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

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

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

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

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

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

Можно записать условия, которые неконструктивные, которые не проверишь. Проверим: первое условие нормальное, ибо почти всегда матрицы симметрические. На B условие самосопряжённости не накладываем. Таким образом, условия не жёсткие.

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

Доказательство. Введём yn = (Avn, vn) ≥ 0. Найдём yn + 1 = (Avn + 1, vn + 1) = (A(E − τB−1A)vn, (E − τB−1A)vn) = (Avn, vn) − τ((AB−1Avn, vn) + (Avn, B−1Avn) − τ(AB−1Avn, B−1Avn)) = (*)

(B−1Avn, Avn) = (Avn, B−1Avn)

(*) = yn − τ(2(Avn, B−1Avn) − τ(AB−1Avn, B−1Avn)) = yn − 2τ((B − 0,5τA)B−1Avn, B−1Avn)

((B − 0,5τA)B−1Avn, B−1Avn) ≥ 0 ⇒ yn + 1 ≤ yn

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

∃ δ > 0: ((B − 0,5τA)B−1Avn, B−1Avn) ≥ δ||B−1Avn||2 (на основании задачи)

(yn + 1 − yn)/τ + 2((B − 0,5τA)B−1Avn, B−1Avn) = 0

В силу задачи можем подставить: (yn + 1 − yn)/τ + δ||B−1Avn||2 ≤ 0

при n → ∞:

lim ||B−1Avn|| = 0

ωn = B−1Avn

vn = A−1n

||vn|| ≤ ||A−1B|| ||ωn||

limn → ∞ ||vn|| = 0

limn → ∞ ||xn − x|| = 0

чтд.

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

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

  • A = R1 + D + R2
  • D(xn + 1 − xn) + Axn + 1 = f
  • τ = 1, B = D, aii ≠ 0
  • D − 0,5A > 0
  • 2D > A

чтд

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

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

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

  • 2D > A
  • (Ax, x) = ∑i, j = 1maijxixj ≤ ∑i, j = 1m|aij| |xi| |xj| ≤ (ab < a2 + b2) ∑i, j = 1m|aij| |xi|2/2 + ∑i, j = 1m|aij| |xj|2/2 = ∑i, j = 1m|aij| |xi|2/2 + ∑j, i = 1m|aji| |xi|2/2 = ∑i, j = 1m|aij| |xi|2 = ∑i, = 1m(aii + ∑j = 1, j ≠ im|aij|) xi2 = (**)

2aii > aii + ∑j = 1, j ≠ im|aij|

(**) < 2∑i, = 1maiixi2

(Ax, x) < 2∑i, = 1maiixi2 = 2(Dx, x) ⇒ 2D > A — сходится

чтд.

Метод простой итерации: (xn + 1+xn)/τ + Axn = f, x0 — задано

Следствие 3. Пусть ∃ A = A* > 0, γ2 = max1 ≤ x ≤ mλkA > 0. Тогда 0 < τ < 2/γ2 МПИ сходится при ∀ x0

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


Численные Методы


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22


Календарь

Февраль
пн
12 19
вт
13 20 27
Март
пн
05 12 19 26
вт
06 13 20 27
Апрель
пн
02 09 16 23 29
вт
03 10 17 24

Дополнительная информация

Содержание курса | Задачи на лекциях

Материалы к экзамену

Вопросы по курсу | Определения


Эта статья является конспектом лекции.
Личные инструменты
Разделы