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

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

Версия от 18:12, 3 февраля 2008; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

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

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

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

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

  • метод Зейделя: (D + R1)(xn + 1 − xn)/τ + Axn = f
  • B − 0,5τA > 0, τ = 1
  • D + R1 = B, τ = 1
  • D + R1 > 1/2 (R1 + D + R2)
  • 2D + 2R1 > R1 + D + R2
  • D + R1 − R2 > 0
  • ((D + R1 − R2)x, x) > 0
  • (Dx, x) + (R1x, x) − (R2x, x) > 0 ⇒ (Dx, x) > 0
  • R1 = R2*
  • R2 = R1*
  • aii > 0, i = 1, m
  • (R1x, x) = (x, R1*x) = (xR2, x) = (R2x, x)

чтд

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

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

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

  • ||vn + 1|| ≤ ρ||vn||, 0 < ρ < 1 (4)

то ||vn|| ≤ ρn||v0|| → 0 при n → ∞

  • ||xn − x|| ≤ ρn||x0 − x||
  • ||xn − x|| ≤ ε||x0 − x||
  • ρn ≤ ε
  • 1/ε ≤ (1/ρ)n
  • n ln 1/ρ ≥ ln 1/ε
  • n ≥ n0(ε) = [ln 1/ε/ln 1/ρ]

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

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

  • ∀ x, y ∈ H (x, y) = ∑i = 1mxiyi
  • ||x|| = (∑i = 1m xi2)1/2

Пусть B = B* > 0

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

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

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

Тогда итерационный метод (2) сходится к решению СЛАУ (1) и имеет место оценка ||vn + 1||B ≤ ρ||vn|| (6)

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

  • A ≤ 1 + ρ/τB
  • A < 2/τB
  • B − 0,5τA > 0

Оценки:

  • B (vn + 1 − vn)/τ + Avn = 0 (*)
  • ∃ B½, B−½, B½ = (B½)* > 0

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

  • B½ (vn + 1 − vn)/τ + B−½Avn = 0
  • zn = B½vn
  • vn = B−½zn
  • zn + 1 − zn/τ + B−½AB−½zn = 0
  • zn + 1 = zn & minus; τB−½AB−½zn = (E − τB−½AB−½)zn = Szn
    • S = E − τB−½AB−½ (7)
  • ||zn||2 = (zn, zn) = (B½vn, B½vn) = (Bvn, vn) = ||vn||B

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

  • S* = E − τB−½AB−½
Равенство Парсиваля

Пусть D = D* > 0, ∃ ортонормированный базис из собственных векторов x = ∑k = 1mckek.

Тогда равенство Парсиваля есть ||x||2 = ∑k = 1mck2
  1. Покажем, что все собственные значения матрицы S по модулю не превосходят ρ
    Пусть sk — собственное значение, k = 1, m
    • (E − τB−½AB−½)x = skx, x ≠ 0
    Домножим на B½ слева:
    • (B½ − τAB−½)x = skB½x
    • y = B−½x
    • x = B½)y
    • (B − τA)y = skBy
    • τAy = (1 − sk)By
    • Ay = (1 − sk)/τBy
    Применим оценку (5):
    • 1 − ρ/τ(By, y) ≤ (Ay, y) = (1 − sk)/τBy ≤ 1 + ρ/τ(By, y)
    • (By, y) ≥ 0
    • 1 − ρ ≤ 1 − sk ≤ 1 + ρ ⇒ |sk| < ρ, k = 1, m
  2. S = S*
    • {ek} — ортонормированный базис из собственных векторов S
    • Sek = skek? k = 1, m
    • zn = ∑k = 1mck(n)ek
    • zn + 1 = Szn = ∑k = 1mskck(n)ek
    • ||zn + 1||2 = ∑k = 1msk2(ck(n))2
    • ||zn + 1||2 ≤ ρ2k = 1m(ck(n))2 = ρ2||zn||2
    • ||zn + 1|| ≤ ρ||zn||
    • ||vn + 1||B ≤ ρ||vn||B

чтд

Следствие 1.

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

Тогда

  • τ = τ0 = 2/γ1 + γ2, ρ = 1 − ξ/1 + ξ, ξ = γ1/γ2
«Ионкин всегда доказывает условие исходя из следствия». Ильдар.
«Ионкин всегда доказывает условие исходя из следствия». Ильдар.

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

  • 1 − ρ/τ = γ1
  • 1 + ρ/τ = γ2
  • 2/τ = γ1 + γ2
  • τ = 2/γ1 + γ2
  • γ1 − γ2 = /τ = ρ(γ1 + γ2)
  • ρ = γ1 − γ2/γ1 + γ2 = 1 − γ1/γ2/1 + γ1/γ2 = 1 − ξ/1 + ξ

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

  • γ1 = min1 ≤ k ≤ m λkA, > 0 в силу положительной определённости
  • γ2 = max1 ≤ k ≤ m λkA

Тогда МПИ (xn+1 − xn)/τ + Axn = f, где τ = 2/γ1 + γ2, ρ = 1 − ξ/1 + ξ, ξ = γ1/γ2 — сходится, имеет место оценка ||xn − x|| ≤ ρ||xn − x||

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

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

  • Ax = f (1)
  • |A| ≠ 0, A ∈ ℝm × m
  • A = R1 + R2,
R1 = ( a11/2 aij )
0 amm/2
R2 = ( a11/2 0 )
aij amm/2
  • (E + ωR1)(E + ωR2)(xn+1 − xn)/τ + Axn = f, ω, τ > 0, n ∈ ℕ ∪ {0}, x0 — задано

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

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

  • R1 = R2* (так как A = A*)
  • B = (E + ωR2*)(E + ωR2) = E + ω(R1 + R2) + ω2R2*R2 = E + ωA + ω2R2*R2
  • (E − ωR2*)(E − ωR2) = E − ωA + ω2R2*R2
  • B = (E − ωR2*)(E − ωR2) + 2ωA
  • ((E − ωR2*)(E − ωR2)x, x) = ((E − ωR2*)x, (E − ωR2)x) ≥ 0
  • B ≥ 2ωA
  • B − 2ωA ≥ 0

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

  • B − 0,5τ > 0

чтд


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


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

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

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

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

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


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