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

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

Содержание 1 Глава 1. Численные методы линейной алгебры 1.1 Параграф 4. Метод квадратного корня (продолжение) 1.2 Параграф 5. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений 1.2.1 Метод Якоби (МЯ) 1.2.2 Метод Зейделя 1.2.3 Реализация ПТИМ 1.3 Параграф 6. Теоремы о сходимости итерационных методов

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

Параграф 4. Метод квадратного корня (продолжение)

Мы рассматриваем задачу

• Ax = f (1)
• A имеет размер m × m
• |A| ≠ 0
• A = A* ⇔ a_ij = a_ji
• A = S*DS, s_ij > 0 (2)

(DS)_ij — элемент, стоящий в j-м столбце i-й строке,

• (DS)_ij = ∑_{l = 1}^md_ils_lj
• (S*DS)_ij = ∑_{l = 1}^ms_lid_lls_lj = ∑_{l = 1}^{i − 1}s_lid_lls_lj + s_iid_iis_ii + ∑_{l = i + 1}^ms_lid_lls_lj = a_ij

Рассмотрим s_li: s_li = 0, l > i ⇒ 3-е слагаемое равно 0.

• s_iid_iis_ii = a_ij − ∑_{l = 1}^{i − 1}s_lid_lls_lj, i ≤ j (*)

Рассмотрим это соотношение при i = j

• ss = |s|²
• s_ii = a_ii − ∑_{l = 1}^{i − 1}s_lis_lid_ll
• d_ii = sign(a_ii − ∑_{l = 1}^{i − 1}|s_li|²d_ll) (4)
• s_ii = √a_ii − ∑_{l = 1}^{i − 1}|s_li|²d_ll) (5)

из (*): s_ij = ^{a_ij − ∑_{l = 1}i − 1s_lis_lid_ll}/_siidii, i < j (6)

Пока миноры ненулевые, разложение существует и единственно.

Для чего применяется данный алгоритм:

Факторизируем матрицу A и подставляем в уравнение:

S*DS = f

Оно сводится к двум системам, имеющие верхнетреугольный/нижнетреугольный вид и явно находящиеся решения:

• SDy = f (7)
• Sx = y (8)

Сложность — порядка ^m3/₆ умножений и делений + m извлечений корня.

Плюс:

• Количество действий сокращается в два раза

Минусы:

• Только для эрмитовых матриц

Под прямыми методами можем подвести черту.

Теперь встаёт вопрос: если мы можем решать методом Гаусса, то зачем нужны другие методы решения?

1. Точное решение всё равно не получить, ибо погрешности
2. Правые части обычно задаются приближённо и тогда непонятно, зачем точный метод, когда решение всё равно будет приближённое

Параграф 5. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений

Задача:

• Ax = f (1)
• A имеет размер m × m
• |A| ≠ 0

Что значит «решение итерационным методом»?

Обозначим:

• x_iⁿ — i-я ккордината, n-я итерация
• x⁰ — начальное приближение

Далее организуется процесс так, что lim_{n → ∞}xⁿ → x, то есть, в некоторой норме |xⁿ − x| < ε, ε > 0

• n₀(ε) — количество итераций. Эффективность алгоритма оценивается именно по нему. Например, метод Самарского сходится на порядок быстрее других.

Два вопроса, которые рассматриваются при исследовании итерационного метода?

• Будет ли сходиться
• С какой скоростью

Запишем уравнение (1) следующим образом:

∑_{j = 1}^ma_ijx_j = f_i, i = 1, m

Запишем в виде:

∑_{j = 1}^{i − 1}a_ij + a_iix_i + ∑_{j = i + 1}^ma_ijx_j = f_i

Пусть a_ii ≠ 0, x_i = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_j − ∑_{j = i + 1}^{m a_ij}/_aiix_j (2)

Метод Якоби (МЯ)

Навешиваем слева (n + 1)-ю итерацию, а справа — n-ю:

• x_i^{n + 1} = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_jⁿ − ∑_{j = i + 1}^{m a_ij}/_aiix_jⁿ, n ∈ ℕ ∪ {0}
• x⁰ — задано

Плюс:

• Данный метод реализуется достаточно просто

Минус:

• Очень медленная сходимость

Метод Зейделя

• x_i^{n + 1} = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_j^{n + 1} − ∑_{j = i + 1}^{m a_ij}/_aiix_jⁿ, n ∈ ℕ ∪ {0} (3)
• x⁰ — задано

• x₁^{n + 1} = ^f₁/_a11 − ∑_{j = 2}^{m a_1j}/_a11x_jⁿ
• x₂^{n + 1} = ^f₂/_a22 − ^a₂₁/_a22x₁^{n + 1} − ∑_{j = 3}^{m a_1j}/_a22x_jⁿ

Продвигаясь по координате i мы получаем все координаты.

По сложности и сходимости эти два метода одинаковы

R1 = ( 0 … 0 ) ⋱ aij … 0

P = ( a11 … 0 ) ⋱ 0 … amm

R2 = ( 0 … aij ) ⋱ 0 … 0

Ясно, что ∀ A = R₁ + D + R₂

• R₁x + Dx + R₂x = f
• Dx = f − R₁x − R₂x
• x = D⁻¹f − D⁻¹R₁x − D⁻¹R₂x

В таком случае метод Якоби записывается следующим способом: x^{n + 1} = D⁻¹f − D⁻¹R₁xⁿ − D⁻¹R₂xⁿ, n ∈ ℕ ∪ {0}, x⁰ задано

метод Зейдаля: x^{n + 1} = D⁻¹f − D⁻¹R₁x^{n + 1} − D⁻¹R₂xⁿ, n ∈ ℕ ∪ {0}, x⁰ задано

Когда существует D⁻¹? когда a_ii ≠ 0

• (МЯ) Dx^{n + 1} = f − R₁xⁿ − R₂xⁿ
• (МЗ) (D + R₁)x^{n + 1} = f − R₂xⁿ
• (МЯ) D(x^{n + 1} − xⁿ) + ARxⁿ = f
• (МЗ) (D + R₁)(x^{n + 1} − xⁿ) + Axⁿ = f

Из-за разной записи в результате решили прийти к канонической форме. И это ввёл Самарский. Что позволило создать стройную теорию. В последней записи она информативнее.

Двуслойная запись — когда связываются две соседние итерации.

Можно строить многошаговые методы.

Определение. Канонической формой записи двуслойного итерационного метода решения системы (1) называется его запись в виде:

• B_{n + 1} ^{(xn + 1 − xn)}/_{τn + 1} + Axⁿ = f (4)

где

• τ_{n + 1} > 0, n ∈ ℕ ∪ {0}
• x⁰ — задано
• ∃B_{n + 1}⁻¹

Метод явный, если B_{n + 1} = E. Если матрица диагональная, то тоже явный.

Если

• B_{n + 1} = B
• τ_{n + 1} = τ

В этом случае метод стационарный.

Два метода используются очень часто:

• Метод простой итерации (МПИ)
  • (МПИ) (xⁿ⁺¹ − xⁿ)/τ + Axⁿ = f, x⁰ — задано, n ∈ ℕ ∪ {0}, τ > 0
  • Если τ меняется, то это другой метод, для которого Чебышевский набор параметров для него оптимален.
• Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ)
  • A = R₁ + R₂, где R₁ — нижнетреугольная матрица с половиной диагоналиьных элементов, R₂ — верхнетреугольная матрица с половиной диагональных элементов
  • (E + ωR₁)(E + ωR₂)((x^{n + 1} − xⁿ)/τ) + Axⁿ = f (5)
    • n ∈ ℕ ∪ {0}, x⁰ задано, ω > 0, τ > 0
  • Будем говорить хвалебные слова в адрес ПТИМ
  • В данном случае B = (E + ωR₁)(E + ωR₂)

Реализация ПТИМ

Обозначим W_{n + 1} = (E + ωR₂)((x^{n + 1} − xⁿ)/τ)

Невязка: rⁿ = f − Axⁿ

Тогда мы можем переписать ПТИМ следующим образом:

(E + ωR₁)W_{n + 1} = rⁿ (6)

Введём вектор v_{n + 1} = ((x^{n + 1} − xⁿ)/τ)

Тогда (E + ωR₁)v_{n + 1} = W_{n + 1} (7)

x^{n + 1} = xⁿ + τv_{n + 1} (8)

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

• Ax = f (1)
• |A| ≠ 0, (m × m)

По-прежнему решаем систему (1) итерационными методами:

• B (x^{n + 1} − xⁿ)/τ + Axⁿ = f (2)
  • τ_{n + 1} > 0
  • n ∈ ℕ ∪ {0}
  • x⁰ задано
  • ∃A⁻¹, B⁻¹

Введём m-мерное пространство :

• ∀ x ∈ H
  • dim H = m
  • x = (x₁, x₂, ..., x_m)
  • ∀ x, y ∈ H (x, y) = ∑_{i = 1}^mx_iy_i
  • ||x|| = (x, x)^1/₂ = (∑_{i = 1}^m x_i²)^1/₂