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

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

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

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

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

Свойства матрицы H:
# H = HT
# Матрица ортогональная: HT = H&minus;1. Доказательство: найдём HTH: HTH = H2 = (E &minus; 2(vvT)/||v||2)(E &minus; 2(vvT)/||v||2) = E &minus; 2(vvT)/||v||2 &minus; 2(vvT)/||v||2 + 4(vvTvvT)/||v||4 = E &minus; 4(vvT)/||v||2 + 4||v||2(vvT)/||v||4 = E
# '''Утверждение'''. Пусть задан &forall; x = (x1, x2, &hellip;, xm)T. Тогда можно выбрать v так, что Hx = (&minus;&sigma;, 0, &hellip;, 0)T, где &sigma; = ||x|| = (&sum;i = 1mxi2)1/2.
'''Доказательство'''. Пусть v = x + &sigma;z, (1, 0, 0, &hellip;, 0)T. Тогда Hx = x &minus; 2x((x + &sigma;z)(x + &sigma;z)T)/((x + &sigma;z)T(x + &sigma;z)) = x &minus; (x + &sigma;z) & times; 2(x + &sigma;z)Tx/((x + &sigma;z)T(x + &sigma;z)). 
#* Рассмотрим 2(x + &sigma;z)Tx. 2(x + &sigma;z)Tx = 2(||x||2 + &sigma;x1)
#*(x + &sigma;z)T(x + &sigma;z) = ||x||2 + 2&sigma;x1 + &sigma;2 = { &sigma; = ||x|| } = 2(&sigma;2 + &sigma;x1)
#* Hx = x &minus; x &minus; &sigma;2 = (&minus;&sigma;, 0, &hellip;, 0)T

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

Запишем произволтьную матрицу в блочном виде:
{|
 |rowspan="2"|A = (
 |a11
 |ym &minus; 1
 |rowspan="2"|), yij; i, j = 1&hellip;m
 |-
 |xm &minus; 1
 |Am &minus; 1
 |}
* Hxm &minus; 1 = (&minus;||xm &minus; 1||, 0, 0, &hellip;, 0)
* vm &minus; 1 = xm &minus; 1 + ||xm &minus; 1||
Получаем
{|
 |rowspan="2"|U = (
 |1
 |012
 |rowspan="2"|)
 |-
 |021
 |Hm &minus; 1
 |}
* U1 = U1T
** Доказательство:
{|
 |rowspan="2"|U12 = (
 |1
 |012
 |rowspan="2"|) &times; (
 |1
 |012
 |rowspan="2"|) = (
 |1
 |012
 |rowspan="2"|) = diag(1, ..., 1) = E
 |-
 |021
 |Hm &minus; 1
 |021
 |Hm &minus; 1
 |021
 |Hm &minus; 12
 |}
* U1T = U1T

{|
 |rowspan="2"|U1&minus;1A = (
 |1
 |012
 |rowspan="2"|) &times; (
 |a11
 |ym &minus; 1
 |rowspan="2"|) = (
 |a11
 |ym &minus; 1
 |rowspan="2"|)
 |-
 |021
 |Hm &minus; 1
 |xm &minus; 1
 |Am &minus; 1
 |Hm &minus; 1xm &minus; 1
 |Hm &minus; 1Am &minus; 1
 |}
{|
 |rowspan="2"|U1&minus;1AU = (
 |a11
 |ym &minus; 1
 |rowspan="2"|) &times; (
 |1
 |012
 |rowspan="2"|) = (
 |a11
 |ym &minus; 1Hm &minus; 1
 |rowspan="2"|) = C1 = матрица такого вида что первые два элемента в первом столбце не нули, остальные в первом столбце нули, остальные элементы перемешались
 |-
 |Hm &minus; 1xm &minus; 1
 |Hm &minus; 1Am &minus; 1
 |021
 |Hm &minus; 1
 |Hm &minus; 1xm &minus; 1
 |Hm &minus; 1Am &minus; 1Hm &minus; 1
 |}
* Через n &minus; 1 шаг получим почти верхнетреугольную матрицу.
* xm &minus; 2 = (c32(1), c42(1), &hellip;, cm2(1))TU1 = Hm &minus; 2xm &minus; 2 = (&minus;||xm &minus; 2||, 0, &hellip;, 0)T
{|
 |rowspan="4"|U2 = (
 |1
 |0
 |...
 |0
 |rowspan="4"|)
 |-
 |0
 |1
 |...
 |0
 |-
 |colspan="4"|...
 |-
 |0
 |0
 |...
 |Hm &minus; 2
 |}
* U2&minus;1 = U2T = U2
* C2 = (нули в первом столбце кроме первых двух и во втором кроме первых трёх, остальные не нули)
* прошло n &minus 1 итераций...
* C = Um &minus; 1&minus;1Um &minus; 2&minus;1&hellip;U2&minus;1U1&minus;1AU1U2&hellip;Um &minus; 2Um &minus; 1 = (верхняя почти треугольная)
* С = U&minus;1AU

'''Замечание 1.''' &lambda;kA = &lambda;kC, k = 1&hellip;m 
'''Доказательство'''. 
* y = U&minus;1x
* x = Uy
* Ax = &lambda;Ax, x &ne; 0
* U&minus;1Ax = &lambda;AU&minus;1x
* U&minus;1AUy = &lambda;Ay
* Cy = &lambda;Ay
* &lambda;A = &lambda;C

'''Замечание 2'''. Пусть A = AT &rArr; C = CT 
'''Доказательство'''. 
* С = U&minus;1AU
* CT = (U&minus;1AU)T = UTAT(U&minus;1)T = U&minus;1AU = C

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

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

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

Возьмём x = (a11, ..., am1)T. Есть v такое, что H1x = (&minus||x||, 0, 0, ..., 0)T. 
{|
 |rowspan="4"|H1A = (
 |&minus;||x||
 |x
 |...
 |x
 |rowspan="4"|)
 |-
 |0
 |x
 |...
 |x
 |-
 |...
 |-
 |0
 |x
 |...
 |x
 |}

{|
 |rowspan="5"|H2H1A = (
 |x
 |x
 |x
 |...
 |x
 |rowspan="5"|)
 |-
 |0
 |x
 |x
 |...
 |x
 |-
 |0
 |0
 |x
 |...
 |x
 |-
 |...
 |-
 |0
 |0
 |x
 |...
 |x
 |}

* Q = H1H2&hellip;Hm &minus; 1
* Q&minus;1 = Hm &minus; 1&minus;1Hm &minus; 2&minus;1&hellip;H1&minus;1 = Hm &minus; 1THm &minus; 2T&hellip;H1T = (H1H2&hellip;Hm &minus; 1)T = QT
* Q&minus;1A = R
* A = QR

QR-алгоритм — итерационный метод. Пусть есть A (m &times; m). Обозначим A = A0. Тогда мы можем разложить её в виде произведения A0 = Q0R0. В качестве матрицы A1 возьмём R0Q0. Утверждается, что их собственные значения совпадают.
* A1 = Q0&minus;1A0Q0
* A1 = Q1R1
* ...
Предельная матрица сходится (без доказательства).
* Матрица сходится к одному из двух значений:
** Если матрица вещественная, то limk &rarr; &infin; Ak — верхнетреугольная матрица. В этом случае собственные значения лежат на диагонали.
** Если есть комплексные собственные значения, то на диагонали будут клеточки 2&times;2

Оценка количества действий:
* полная — O(m3)
* ВПТФ — O(m2)
* A = AT O(m)
{{Численные Методы}}
{{Lection-stub}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. 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_08_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_12_%D0%BC%D0%B0%D1%80%D1%82%D0%B0%29