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

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

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

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

Свойства матрицы H:

1. H = H^T
2. Матрица ортогональная: H^T = H⁻¹. Доказательство: найдём H^TH: H^TH = H² = (E − 2(vv^T)/||v||²)(E − 2(vv^T)/||v||²) = E − 2(vv^T)/||v||² − 2(vv^T)/||v||² + 4(vv^Tvv^T)/||v||⁴ = E − 4(vv^T)/||v||² + 4||v||²(vv^T)/||v||⁴ = E
3. Утверждение. Пусть задан ∀ x = (x₁, x₂, …, x_m)^T. Тогда можно выбрать v так, что Hx = (−σ, 0, …, 0)^T, где σ = ||x|| = (∑_{i = 1}^mx_i²)^1/2.

Доказательство. Пусть v = x + σz, (1, 0, 0, …, 0)^T. Тогда Hx = x − 2x((x + σz)(x + σz)^T)/((x + σz)^T(x + σz)) = x − (x + σz) & times; 2(x + σz)^Tx/((x + σz)^T(x + σz)).

1. • Рассмотрим 2(x + σz)^Tx. 2(x + σz)^Tx = 2(||x||² + σx₁)
   • (x + σz)^T(x + σz) = ||x||² + 2σx₁ + σ² = { σ = ||x|| } = 2(σ² + σx₁)
   • Hx = x − x − σ² = (−σ, 0, …, 0)^T

Построение почти треугольной матрицы

Запишем произволтьную матрицу в блочном виде:

• Hx_{m − 1} = (−||x_{m − 1}||, 0, 0, …, 0)
• v_{m − 1} = x_{m − 1} + ||x_{m − 1}||

Получаем

• U₁ = U₁^T
  • Доказательство:

• U₁^T = U₁^T

• Через n − 1 шаг получим почти верхнетреугольную матрицу.
• x_{m − 2} = (c₃₂⁽¹⁾, c₄₂⁽¹⁾, …, c_m2⁽¹⁾)^TU₁ = H_{m − 2}x_{m − 2} = (−||x_{m − 2}||, 0, …, 0)^T

• U₂⁻¹ = U₂^T = U₂
• C₂ = (нули в первом столбце кроме первых двух и во втором кроме первых трёх, остальные не нули)
• прошло n &minus 1 итераций...
• C = U_{m − 1}⁻¹U_{m − 2}⁻¹…U₂⁻¹U₁⁻¹AU₁U₂…U_{m − 2}U_{m − 1} = (верхняя почти треугольная)
• С = U⁻¹AU

Замечание 1. λ_k^A = λ_k^C, k = 1…m
Доказательство.

• y = U⁻¹x
• x = Uy
• Ax = λ^Ax, x ≠ 0
• U⁻¹Ax = λ^AU⁻¹x
• U⁻¹AUy = λ^Ay
• Cy = λ^Ay
• λ^A = λ^C

Замечание 2. Пусть A = A^T ⇒ C = C^T
Доказательство.

• С = U⁻¹AU
• C^T = (U⁻¹AU)^T = U^TA^T(U⁻¹)^T = U⁻¹AU = C

Параграф 11. Понятие о QR-алгоритме решения полной проблемы собственных значений

∀ A = Q × R, Q^&minus1 = Q^T, R — верхнетреугольная матрица (1)

Оказывается, любую матрицу можно представить в виде разложения (1).

Возьмём x = (a11, ..., am1)^T. Есть v такое, что H₁x = (&minus||x||, 0, 0, ..., 0)^T.

• Q = H₁H₂…H_{m − 1}
• Q⁻¹ = H_{m − 1}⁻¹H_{m − 2}⁻¹…H₁⁻¹ = H_{m − 1}^TH_{m − 2}^T…H₁^T = (H₁H₂…H_{m − 1})^T = Q^T
• Q⁻¹A = R
• A = QR

QR-алгоритм — итерационный метод. Пусть есть A (m × m). Обозначим A = A₀. Тогда мы можем разложить её в виде произведения A₀ = Q₀R₀. В качестве матрицы A₁ возьмём R₀Q₀. Утверждается, что их собственные значения совпадают.

• A₁ = Q₀⁻¹A₀Q₀
• A₁ = Q₁R₁
• ...

Предельная матрица сходится (без доказательства).

• Матрица сходится к одному из двух значений:
  • Если матрица вещественная, то lim_{k → ∞} A_k — верхнетреугольная матрица. В этом случае собственные значения лежат на диагонали.
  • Если есть комплексные собственные значения, то на диагонали будут клеточки 2×2

Оценка количества действий:

• полная — O(m³)
• ВПТФ — O(m²)
• A = A^T O(m)