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

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

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

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

λ_m⁽ⁿ⁾ = x_n+1⁽ⁱ⁾/x_n⁽ⁱ⁾ = (c₁λ₁ⁿ⁺¹e₁⁽ⁱ⁾ + c₂λ₂ⁿ⁺¹e₂⁽ⁱ⁾ + ... + c_mλ_mⁿ⁺¹e_m⁽ⁱ⁾)/(c₁λ₁ⁿe₁⁽ⁱ⁾ + c₂λ₂ⁿe₂⁽ⁱ⁾ + ... + c_mλ_mⁿe_m⁽ⁱ⁾) = c_mλ_mⁿ⁺¹e_m⁽ⁱ⁾(1 + … + (c₁λ₁ⁿ⁺¹e₁⁽ⁱ⁾)/(c_mλ_mⁿ⁺¹e_m⁽ⁱ⁾))/c_mλ_mⁿe_m⁽ⁱ⁾(1 + … + (c₁λ₁ⁿe₁⁽ⁱ⁾)/(c_mλ_mⁿe_m⁽ⁱ⁾)) = λ_m

λ_m⁽ⁿ⁾ − λ_m = O(|λ_{m − 1}/λ_m|)ⁿ (n → ∞), (λ_m⁽ⁿ⁾ → λ_m), i = 1..m

Точность достигнута, когда изменения по каждой координате в пределах погрешности.

Ясно, что λ_m⁽ⁿ⁾ = (Ax_n, x_n)/(x_n, x_n). Так как всё известно то это даёт простой способ вычисления. Рассмотрим некоторые случаи:

1. A = A*. Тогда гарантированно существует ортонормированный базис {e_k}₁^m, (e_i, e_j) = δ_ij, Ae_k = λ_ke_k, k = 1..m. Тогда λ_m⁽ⁿ⁾ = (Ax_n, x_n)/(x_n, x_n) = (x_{n + 1}, x_n)/(x_n, x_n) = (c_m²λ_{m2n + 1} + … + c₁²λ_{12n + 1})/(c_m²λ_m2n + … + c₁²λ_12n) = c_m²λ_{m2n + 1}(1 + … + (c₁²λ_{12n + 1})/(c_m²λ_{m2n + 1}))/c_m²λ_m2n(1 + … + (c₁²λ_12n)/(c_m²λ_m2n)) = λ_m + O(λ_{m + 1}/λ_m)²ⁿ. То есть для самосопряжённой матрицы сходимость быстрее.
2. {e_k}₁^m — базис из собственных векторов. λ_m⁽ⁿ⁾ = (x_{n + 1}, x_n)/(x_n, x_n) = (∑_{i, j = 1}^m c_ic_jλ_i^{n + 1}λ_jⁿ(e_i, e_j))/(∑_{i, j = 1}^m c_ic_jλ_iⁿλ_jⁿ(e_i, e_j)) = (λ_i^{2n + 1}c_m²(e_m, e_m) + … + λ_i^{2n + 1}c₁²(e₁, e₁))/(λ_i²ⁿc_m²(e_m, e_m) + … + λ_i²ⁿc₁²(e₁, e₁)) = λ_i^{2n + 1}c_m²(e_m, e_m)(1 + … + (λ_i^{2n + 1}c₁²(e₁, e₁))/(λ_i^{2n + 1}c_m²(e_m, e_m)))/λ_i²ⁿc_m²(e_m, e_m)(1 + … + (λ_i²ⁿc₁²(e₁, e₁))/(λ_i²ⁿc_m²(e_m, e_m))) = λ_m + O(λ_{m + 1}/λ_m)ⁿ. Меньше, чем для самосопряжённой матрицы, но оно и понятно.

Итог. что мы доказали: степенной метод, если для матрицы выполнены условия (A, B, C), имеет смысл.

Замечание. Матрица A вещественная, но собственные значения могут быть и вещественные, и комплексные. Принципиальным является момент: вектор тоже комплексный.

Сейчас лектор покажет, что если у нас есть СЗ λ = λ₀ + iλ₁, то СВ надо искать в виде μ = μ₀ + iμ₁, μ₀, μ₁ — вещественные:

• A(μ₀ + iμ₁) = (λ₀ + iλ₁)(μ₀ + iμ₁)
• Aμ₀ = λ₀μ₀ − λ₁μ₁
• Aμ₁ = λ₁μ₀ + λ₀μ₁
• μ₁ = 0, λ₁ ≠ 0, μ₀ = Θ → μ == Θ

[править] Метод обратных итераций

1. ∃ A⁻¹. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
   • Ax_{n + 1} = x_n, n = 0, 1, …, x₀ — начальное приближение (3) Этот метод неявный. Перепишем его как:
   • x_{n + 1} = A⁻¹x_n (4)
   • x_n = (A⁻¹)ⁿx₀

Условия:
A) ∃ {e_k}₁^m из СВ
B) |λ₁/λ₂| < 1
C) x₀ = c₁e₁+ … + c_me_m, c₁ ≠ 0

Тогда:

• x_n = c₁λ₁⁻ⁿe₁+ … + c_mλ_m⁻ⁿe_m
• x_n/e₁λ₁⁻ⁿ = e₁ + … + (c_m/c₁)(λ₁/λ_m)ⁿe_m

Задача. Показать, что λ₁ = lim_{n → ∞} (x_n⁽ⁱ⁾/x_{n + 1}⁽ⁱ⁾), i = 1…m

Задача. Показать, что λ₁⁽ⁿ⁾ − λ₁ = O(λ₁/λ₂).

• λ₁⁽ⁿ⁾ = (x_n, _n)/(Ax_n, _n)
• A = A*
• {e_k}₁^m ОНБ из СВ
• (e_i, e_j) = δ_ij
• λ₁ⁿ = (x_n, _n)/(Ax_n, _n) = (x_n, _n)/(x_{n + 1}, _n) = (c₁²λ₁⁻²ⁿ + … + c_m²λ_m⁻²ⁿ)/(c₁²λ₁^{−2n − 1} + … + c_m²λ_m^{−2n − 1}) = λ₁ + O(λ₁/λ₂)²ⁿ
  • x₀ = c₁e₁+ … + c_me_m
  • x_n = c₁λ₁⁻ⁿe₁+ … + c_mλ_m⁻ⁿe_m
  • x_{n + 1} = c₁λ₁^{−n − 1}e₁+ … + c_mλ_m^{−n − 1}e_m

[править] Метод обратных итераций со сдвигом

• (A − αE)x_{n + 1} = x_n (5)
  • n = 0, 1, …, x₀ — начальное приближение, α ∈ R
• ∃ (A − αE)⁻¹
• x_{n + 1} = (A − αE)⁻¹x_n
• x_n = e_l
• 1/|λ_l − α| = max_{1 ≤ k ≤ m} 1/|λ_k − α|

Задача. Когда λ_l = lim_{n → ∞} (α + x_n⁽ⁱ⁾/x_{n + 1}⁽ⁱ⁾)

[править] Параграф 10. Приведение матрицы к почти треугольной форме (к верхней почти треугольной форме — ВПТФ)

В чём идея полного решения проблемы, как получить весь спектр. Конечно, мы будем её по-другому решать, когда будем решать систему нелинейных уравнений. Получим характеристический многочлен и будем потихонечку находить. В чём заключается проблема нахождения итерационным методом, в чём идея? Теперь есть матрица A, на которую мы не накладываем никаких ограничений:

• Ax = λx, x == o(1), A (m × m)

Хорошо известно, что если бы матрицу удалось свести к треугольному (диагональному) виду, то числа на диагонали — собственные значения. И если удастся свести к ним, сохраняя спектр, то всё хорошо. Но сводить будем не произвольными преобразованиями, а преобразованиями подобия. И этими преобразованиями подобия C = Q⁻¹AQ (2) сводить матрицу к предельной. Если мы сумеем к такой матрице C, свести, то спектр будет найден. Такая задача не решается аналитически, только приближённо, и мы рассмотрим QR-алгоритм, который позволяет это делать.

Теперь отметим такой факт: если сделать преобразование подобия с помощью ортогональной матрицы, то сохранится не только спектр, но и симметрия.

Что такое верхняя почти треугольная форма: эта форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.

Заметьте, что если у нас была симметричная, и преобразование делаем ортогональной, то получим трёхдиагональную матрицу, а для неё ещё на порядок снижается количество действий.

Матрица ортогональна, если Q⁻¹ = Q*.

• v = (v₁, …, _m)^T
• v^T = (v₁, …, _m)
• v^Tv = v₁² + v₂² + … + v_m² = ||v||²

Определение. Преобразование элементарных отражений (Преобразование Хаусхолдера). Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E − 2 vv^T/||v||² (3)

Свойства:

• Матрица является симметричной: H = H^T