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

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

Версия от 11:05, 9 июня 2010; 85.141.198.204 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

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

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

λm(n) = xn+1(i)/xn(i) = (c1λ1n+1e1(i) + c2λ2n+1e2(i) + ... + cmλmn+1em(i))/(c1λ1ne1(i) + c2λ2ne2(i) + ... + cmλmnem(i)) = cmλmn+1em(i)(1 + … + (c1λ1n+1e1(i))/(cmλmn+1em(i)))/cmλmnem(i)(1 + … + (c1λ1ne1(i))/(cmλmnem(i))) = λm

λm(n) − λm = O(|λm − 1m|)n (n → ∞), (λm(n) → λm), i = 1..m

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

Ясно, что λm(n) = (Axn, xn)/(xn, xn). Так как всё известно то это даёт простой способ вычисления. Рассмотрим некоторые случаи:

  1. A = A*. Тогда гарантированно существует ортонормированный базис {ek}1m, (ei, ej) = δij, Aek = λkek, k = 1..m. Тогда λm(n) = (Axn, xn)/(xn, xn) = (xn + 1, xn)/(xn, xn) = (cm2λm2n + 1 + … + c12λ12n + 1)/(cm2λm2n + … + c12λ12n) = cm2λm2n + 1(1 + … + (c12λ12n + 1)/(cm2λm2n + 1))/cm2λm2n(1 + … + (c12λ12n)/(cm2λm2n)) = λm + O(λm + 1m)2n. То есть для самосопряжённой матрицы сходимость быстрее.
  2. {ek}1m — базис из собственных векторов. λm(n) = (xn + 1, xn)/(xn, xn) = (∑i, j = 1m cicjλin + 1λjn(ei, ej))/(∑i, j = 1m cicjλinλjn(ei, ej)) = (λi2n + 1cm2(em, em) + … + λi2n + 1c12(e1, e1))/(λi2ncm2(em, em) + … + λi2nc12(e1, e1)) = λi2n + 1cm2(em, em)(1 + … + (λi2n + 1c12(e1, e1))/(λi2n + 1cm2(em, em)))/λi2ncm2(em, em)(1 + … + (λi2nc12(e1, e1))/(λi2ncm2(em, em))) = λm + O(λm + 1m)n. Меньше, чем для самосопряжённой матрицы, но оно и понятно.

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

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

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

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


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

  1. ∃ A−1. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
    • Axn + 1 = xn, n = 0, 1, …, x0 — начальное приближение (3) Этот метод неявный. Перепишем его как:
    • xn + 1 = A−1xn (4)
    • xn = (A−1)nx0

Условия:
A) ∃ {ek}1m из СВ
B) |λ12| < 1
C) x0 = c1e1+ … + cmem, c1 ≠ 0

Тогда:

  • xn = c1λ1−ne1+ … + cmλm−nem
  • xn/e1λ1−n = e1 + … + (cm/c1)(λ1m)nem

Задача. Показать, что λ1 = limn → ∞ (xn(i)/xn + 1(i)), i = 1…m

Задача. Показать, что λ1(n) − λ1 = O(λ12).

  • λ1(n) = (xn, n)/(Axn, n)
  • A = A*
  • {ek}1m ОНБ из СВ
  • (ei, ej) = δij
  • λ1n = (xn, n)/(Axn, n) = (xn, n)/(xn + 1, n) = (c12λ1−2n + … + cm2λm−2n)/(c12λ1−2n − 1 + … + cm2λm−2n − 1) = λ1 + O(λ12)2n
    • x0 = c1e1+ … + cmem
    • xn = c1λ1−ne1+ … + cmλm−nem
    • xn + 1 = c1λ1−n − 1e1+ … + cmλm−n − 1em

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

  • (A − αE)xn + 1 = xn (5)
    • n = 0, 1, …, x0 — начальное приближение, α ∈ R
  • ∃ (A − αE)−1
  • xn + 1 = (A − αE)−1xn
  • xn = el
  • 1/|λl − α| = max1 ≤ k ≤ m 1/|λk − α|

Задача. Когда λl = limn → ∞ (α + xn(i)/xn + 1(i))

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

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

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

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

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

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

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

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

  • v = (v1, …, m)T
  • vT = (v1, …, m)
  • vTv = v12 + v22 + … + vm2 = ||v||2

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

v × vT (m × m)

Свойства:

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


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


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

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

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

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

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


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

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