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

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

Перейти к: навигация, поиск

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

Содержание

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

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

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

  1. H = HT
  2. Матрица ортогональная: HT = H−1. Доказательство: найдём HTH: HTH = H2 = (E − 2(vvT)/||v||2)(E − 2(vvT)/||v||2) = E − 2(vvT)/||v||2 − 2(vvT)/||v||2 + 4(vvTvvT)/||v||4 = E − 4(vvT)/||v||2 + 4||v||2(vvT)/||v||4 = E
  3. Утверждение. Пусть задан ∀ x = (x1, x2, …, xm)T. Тогда можно выбрать v так, что Hx = (−σ, 0, …, 0)T, где σ = ||x|| = (∑i = 1mxi2)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)).

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

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

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

A = ( a11 ym − 1 ), yij; i, j = 1…m
xm − 1 Am − 1
  • Hxm − 1 = (−||xm − 1||, 0, 0, …, 0)
  • vm − 1 = xm − 1 + ||xm − 1||

Получаем

U = ( 1 012 )
021 Hm − 1
  • U1 = U1T
    • Доказательство:
U12 = ( 1 012 ) × ( 1 012 ) = ( 1 012 ) = diag(1, ..., 1) = E
021 Hm − 1 021 Hm − 1 021 Hm − 12
  • U1T = U1T
U1−1A = ( 1 012 ) × ( a11 ym − 1 ) = ( a11 ym − 1 )
021 Hm − 1 xm − 1 Am − 1 Hm − 1xm − 1 Hm − 1Am − 1
U1−1AU = ( a11 ym − 1 ) × ( 1 012 ) = ( a11 ym − 1Hm − 1 ) = C1 = матрица такого вида что первые два элемента в первом столбце не нули, остальные в первом столбце нули, остальные элементы перемешались
Hm − 1xm − 1 Hm − 1Am − 1 021 Hm − 1 Hm − 1xm − 1 Hm − 1Am − 1Hm − 1
  • Через n − 1 шаг получим почти верхнетреугольную матрицу.
  • xm − 2 = (c32(1), c42(1), …, cm2(1))TU1 = Hm − 2xm − 2 = (−||xm − 2||, 0, …, 0)T
U2 = ( 1 0 ... 0 )
0 1 ... 0
...
0 0 ... Hm − 2
  • U2−1 = U2T = U2
  • C2 = (нули в первом столбце кроме первых двух и во втором кроме первых трёх, остальные не нули)
  • прошло n &minus 1 итераций...
  • C = Um − 1−1Um − 2−1…U2−1U1−1AU1U2…Um − 2Um − 1 = (верхняя почти треугольная)
  • С = U−1AU

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

  • y = U−1x
  • x = Uy
  • Ax = λAx, x ≠ 0
  • U−1Ax = λAU−1x
  • U−1AUy = λAy
  • Cy = λAy
  • λA = λC

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

  • С = U−1AU
  • CT = (U−1AU)T = UTAT(U−1)T = U−1AU = C

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

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

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

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

H1A = ( x x ... x )
0 x ... x
...
0 x ... x
H2H1A = ( x x x ... x )
0 x x ... x
0 0 x ... x
...
0 0 x ... x
  • Q = H1H2…Hm − 1
  • Q−1 = Hm − 1−1Hm − 2−1…H1−1 = Hm − 1THm − 2T…H1T = (H1H2…Hm − 1)T = QT
  • Q−1A = R
  • A = QR

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

  • A1 = Q0−1A0Q0
  • A1 = Q1R1
  • ...

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

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

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

  • полная — O(m3)
  • ВПТФ — O(m2)
  • A = AT O(m)


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


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

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

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

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

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


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

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