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

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

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

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

Содержание

Глава 1

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

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

  • 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. Пусть существуют такие две константы δ > 0, Δ > 0:

  • A ≥ δE, R*2R2 ≤ Δ/4 A (2)
  • Положим ω = 2/√δΔ, τ = 2/(γ1 + γ2), γ1 = √δ/2 (√δΔ/(√δ+√Δ)); γ2 = √δΔ/4 (4)
  • ||xn + 1 − x||B ≤ ρ ||xn − x||B (5)
  • где B = (E + ωR*2)(E + ωR2), ρ = (1 − √η)/(1 + 3√η), η = δ/Δ (6)
    • R*2 = R1

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

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

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

  • (Ax, x) = ((R1 + R2)x, x) = (R1x, x) + (R2x, x) = {так как R1 = R*2} = (R*2x, x ) + (R2x, x) = (x, R2x) + (R2x, x) = 2(R2x, x)

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

  • δ||x||2 ≤ (Ax, x) = (Ax, x)2/(Ax, x) = 4(R2x, x)2/(Ax, x)

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

  • 4(R2x, x)2/(Ax, x) ≤ (4||R2x||2||x||2)/(Ax, x) ≤ 4Δ/4 (Ax, x)||x||2/(Ax, x) = Δ||x||2

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

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

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

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

  • мы показали, что B ≥ 2ωA
  • A ≤ ½ ωB
  • γ2 = 1/2ω
  • (*) ≤ 1/δ A + ωA + ω2 Δ/4 A = (1/δ + ω + ω2Δ/4)A
  • γ1 = (1/δ + ω + ω2Δ/4)−1
  • ||xn + 1 − x||B ≤ ρ ||xn − x||B
  • ρ = (1 − ξ(ω))/(1 + 3ξ(ω)), ξ = γ12
  • τ = 2/(γ1(ω)+γ2(ω))
  • f(ω) = γ2(ω)/γ1(ω) = (1/δ + ω + ω2Δ/4)/(2ω) = ½ (1 + 1/δω + ωΔ/4)
  • Для максимальной скорости сходимости необходимо найти минимум: f'(ω)=1/2 (Δ/4 − 1/δω2), 1/δω2 = Δ/4, ω2 = 4/δΔ, ω = 2/√δΔ = ω0
  • f''(ω0) = 1/δω3 > 0 ⇒ ω0 — минимум ⇒ максимальная скорость сходимости

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

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

чтд

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

  • n0(ε) = [ln 1/ε/ln 1/ρ]

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

  • 1/ρ = 1 + 3√η/1 − √η(1 + 3√η)(1 + √η)/1 − η ≈ 1 + 4√η. Тогда ln 1/ρ = 4√η = O(m−1), n0(ε) = O(m)

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

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

  • ||xn + 1 − x|| ≤ ρ ||xn − x||, ρ = 1 − ξ/1 + ξ, ξ = γ1/γ2, ξ = η = O(m−2)
  • 1/ρ = 1 + η/1 − η ≈ (1 + η)2 ≈ 1 + 2η
  • ln 1/ρ ≈ η, n0(ε) = O(m2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • xn + 1 = Axn (2)
  • n = 0, 1, ..., x0 — начальное приближение
  • xn = Anx0 (3)

Условия:

  • Предположения относительно матрицы A:
    • Все собственные значения расположены в порядке неубывания модуля: |λ1| ≤ |λ2| ≤ |λ3| ≤ ... ≤ |λm − 1| < |λm|
    • Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {ek}1m — базис из собственных векторов A (Aek = λkek, k = 1..m)
    • Ограничение B: последнее собственное значение не является кратным: |(λm − 1)/(λm) < 1
    • Ограничение C: ∀ x = c1e1 + ... + cmem, cm ≠ 0

xn = c1λ1ne1 + c2λ2ne2 + ... + cmλmnem

xn/cmλnm = (c1/cm)(λ1m)ne1 + (c2/cm)(λ2m)ne2 + ... + em

xn(i) — координата = c1λ1ne1(i) + c2λ2ne2(i) + ... + cmλmnem(i) xn+1(i) = c1λ1n+1e1(i) + c2λ2n+1e2(i) + ... + cmλmn+1em(i)

xn+1(i)/xn(i) = λm(n) = λm + O(|λm − 1m|)n


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


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

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

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

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

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


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы