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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

[[Численные Методы, 06 лекция (от 05 марта)|Предыдущая лекция]] | [[Численные Методы, 08 лекция (от 12 марта)|Следующая лекция]]

= Глава 1. Численные методы линейной алгебры =
== Параграф 9. Методы решения задач на собственные значения ==
&lambda;m(n) = xn+1(i)/xn(i) = (c1&lambda;1n+1e1(i) + c2&lambda;2n+1e2(i) + ... + cm&lambda;mn+1em(i))/(c1&lambda;1ne1(i) + c2&lambda;2ne2(i) + ... + cm&lambda;mnem(i)) = cm&lambda;mn+1em(i)(1 + &hellip; + (c1&lambda;1n+1e1(i))/(cm&lambda;mn+1em(i)))/cm&lambda;mnem(i)(1 + &hellip; + (c1&lambda;1ne1(i))/(cm&lambda;mnem(i))) = &lambda;m

&lambda;m(n) &minus; &lambda;m = O(|&lambda;m &minus; 1/&lambda;m|)n (n &rarr; &infin;), (&lambda;m(n) &rarr; &lambda;m), i = 1..m

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

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

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

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

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

Сейчас лектор покажет, что если у нас есть СЗ &lambda; = &lambda;0 + i&lambda;1, то СВ надо искать в виде &mu; = &mu;0 + i&mu;1, &mu;0, &mu;1 — вещественные:
* A(&mu;0 + i&mu;1) = (&lambda;0 + i&lambda;1)(&mu;0 + i&mu;1)
* A&mu;0 = &lambda;0&mu;0 &minus; &lambda;1&mu;1
* A&mu;1 = &lambda;1&mu;0 + &lambda;0&mu;1
* &mu;1 = 0, &lambda;1 &ne; 0, &mu;0 = &Theta; &rarr; &mu; == &Theta;

=== Метод обратных итераций ===

# &exist; A&minus;1. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
#* Axn + 1 = xn, n = 0, 1, &hellip;, x0 — начальное приближение (3) Этот метод неявный. Перепишем его как:
#* xn + 1 = A&minus;1xn (4)
#* xn = (A&minus;1)nxn

Условия: 
A) &exist; {ek}1m из СВ 
B) |&lambda;1/&lambda;2| < 1 
C) x0 = c1e1+ &hellip; + cmem, c1 &ne; 0

Тогда:
* xn = c1&lambda;1&minus;ne1+ &hellip; + cm&lambda;m&minus;nem
* xn/e1&lambda;1&minus;n = e1 + &hellip; + (cm/c1)(&lambda;1/&lambda;m)nem

'''Задача'''. Показать, что &lambda;1 = limn &rarr; &infin; (xn(i)/xn + 1(i)), i = 1&hellip;m

'''Задача'''. Показать, что &lambda;1(n) &minus; &lambda;1 = O(&lambda;1/&lambda;2).

* &lambda;1(n) = (xn, n)/(Axn, n)
* A = A*
* {ek}1m ОНБ из СВ
* (ei, ej) = &delta;ij
* &lambda;1n = (xn, n)/(Axn, n) = (xn, n)/(xn + 1, n) = (c12&lambda;1&minus;2n + &hellip; + cm2&lambda;m&minus;2n)/(c12&lambda;1&minus;2n &minus; 1 + &hellip; + cm2&lambda;m&minus;2n &minus; 1) = &lambda;1 + O(&lambda;1/&lambda;2)2n
** x0 = c1e1+ &hellip; + cmem
** xn = c1&lambda;1&minus;ne1+ &hellip; + cm&lambda;m&minus;nem
** xn + 1 = c1&lambda;1&minus;n &minus; 1e1+ &hellip; + cm&lambda;m&minus;n &minus; 1em

=== Метод обратных итераций со сдвигом ===

* (A &minus; &alpha;E)xn + 1 = xn (5)
** n = 0, 1, &hellip;, x0 — начальное приближение, &alpha; &isin; R
* &exist; (A &minus; &alpha;E)&minus;1
* xn + 1 = (A &minus; &alpha;E)&minus;1xn
* xn = el
* 1/|&lambda;l &minus; &alpha;| = max1 &le; k &le; m 1/|&lambda;k &minus; &alpha;|

'''Задача'''. Когда &lambda;l = limn &rarr; &infin; (&alpha; + xn(i)/xn + 1(i))

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

В чём идея полного решения проблемы, как получить весь спектр. Конечно, мы будем её по-другому решать, когда будем решать систему нелинейных уравнений. Получим характеристический многочлен и будем потихонечку находить. В чём заключается проблема нахождения итерационным методом, в чём идея? Теперь есть матрица A, на которую мы не накладываем никаких ограничений:
* Ax = &lambda;x, x == o(1), A (m &times; m)
Хорошо известно, что если бы матрицу удалось свести к треугольному (диагональному) виду, то числа на диагонали — собственные значения. И если удастся свести к ним, сохраняя спектр, то всё хорошо. Но сводить будем не произвольными преобразованиями, а преобразованиями подобия. И этими преобразованиями подобия C = Q&minus;1AQ (2) сводить матрицу к предельной. Если мы сумеем к такой матрице C, свести, то спектр будет найден. Такая задача не решается аналитически, только приближённо, и мы рассмотрим QR-алгоритм, который позволяет это делать.

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

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

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

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

* v = (v1, &hellip;, m)T
* vT = (v1, &hellip;, m)
* vTv = v12 + v22 + &hellip; + vm2 = ||v||2

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

{|
 |colspan="4"|v &times; vT
 |(m &times; m)
 |}

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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B%2C_07_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_06_%D0%BC%D0%B0%D1%80%D1%82%D0%B0%29

@@ Строка 31: / Строка 31: @@
 #* Ax<sub>n + 1</sub> = x<sub>n</sub>, n = 0, 1, &hellip;, x<sub>0</sub> — начальное приближение (3) Этот метод неявный. Перепишем его как:
 #* x<sub>n + 1</sub> = A<sup>&minus;1</sup>x<sub>n</sub> (4)
-#* x<sub>n</sub> = (A<sup>&minus;1</sup>)<sup>n</sup>x<sub>0</sub>
+#* x<sub>n</sub> = (A<sup>&minus;1</sup>)<sup>n</sup>x<sub>n</sub>
 Условия:<br />

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты