Численные Методы, 08 лекция (от 12 марта)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1446 участника 82.83.93.232 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 07 лекция (от 06 марта)|Предыдущая лекция]] | [[Численные Методы, 09 лекция (от 13 марта)|Следующая лекция]] |
- | + | ||
- | + | = Глава 1. Численные методы линейной алгебры = | |
- | + | == Параграф 10. Приведение матрицы к почти треугольной форме (к верхней почти треугольной форме — ВПТФ) == | |
+ | |||
+ | Свойства матрицы H: | ||
+ | # H = H<sup>T</sup> | ||
+ | # Матрица ортогональная: H<sup>T</sup> = H<sup>−1</sup>. Доказательство: найдём H<sup>T</sup>H: H<sup>T</sup>H = H<sup>2</sup> = (E − 2(vv<sup>T</sup>)/||v||<sup>2</sup>)(E − 2(vv<sup>T</sup>)/||v||<sup>2</sup>) = E − 2(vv<sup>T</sup>)/||v||<sup>2</sup> − 2(vv<sup>T</sup>)/||v||<sup>2</sup> + 4(vv<sup>T</sup>vv<sup>T</sup>)/||v||<sup>4</sup> = E − 4(vv<sup>T</sup>)/||v||<sup>2</sup> + 4||v||<sup>2</sup>(vv<sup>T</sup>)/||v||<sup>4</sup> = E | ||
+ | # '''Утверждение'''. Пусть задан ∀ x = (x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>)<sup>T</sup>. Тогда можно выбрать v так, что Hx = (−σ, 0, …, 0)<sup>T</sup>, где σ = ||x|| = (∑<sub>i = 1</sub><sup>m</sup>x<sub>i</sub><sup>2</sup>)<sup>1/2</sup>. | ||
+ | '''Доказательство'''. Пусть v = x + σz, (1, 0, 0, …, 0)<sup>T</sup>. Тогда Hx = x − 2x((x + σz)(x + σz)<sup>T</sup>)/((x + σz)<sup>T</sup>(x + σz)) = x − (x + σz) & times; 2(x + σz)<sup>T</sup>x/((x + σz)<sup>T</sup>(x + σz)). | ||
+ | #* Рассмотрим 2(x + σz)<sup>T</sup>x. 2(x + σz)<sup>T</sup>x = 2(||x||<sup>2</sup> + σx<sub>1</sub>) | ||
+ | #*(x + σz)<sup>T</sup>(x + σz) = ||x||<sup>2</sup> + 2σx<sub>1</sub> + σ<sup>2</sup> = { σ = ||x|| } = 2(σ<sup>2</sup> + σx<sub>1</sub>) | ||
+ | #* Hx = x − x − σ<sup>2</sup> = (−σ, 0, …, 0)<sup>T</sup> | ||
+ | |||
+ | === Построение почти треугольной матрицы === | ||
+ | |||
+ | Запишем произволтьную матрицу в блочном виде: | ||
+ | {| | ||
+ | |rowspan="2"|A = ( | ||
+ | |a11 | ||
+ | |y<sub>m − 1</sub> | ||
+ | |rowspan="2"|), y<sub>ij</sub>; i, j = 1…m | ||
+ | |- | ||
+ | |x<sub>m − 1</sub> | ||
+ | |A<sub>m − 1</sub> | ||
+ | |} | ||
+ | * Hx<sub>m − 1</sub> = (−||x<sub>m − 1</sub>||, 0, 0, …, 0) | ||
+ | * v<sub>m − 1</sub> = x<sub>m − 1</sub> + ||x<sub>m − 1</sub>|| | ||
+ | Получаем | ||
+ | {| | ||
+ | |rowspan="2"|U = ( | ||
+ | |1 | ||
+ | |0<sub>12</sub> | ||
+ | |rowspan="2"|) | ||
+ | |- | ||
+ | |0<sub>21</sub> | ||
+ | |H<sub>m − 1</sub> | ||
+ | |} | ||
+ | * U<sub>1</sub> = U<sub>1</sub><sup>T</sup> | ||
+ | ** Доказательство: | ||
+ | {| | ||
+ | |rowspan="2"|U<sub>1</sub><sup>2</sup> = ( | ||
+ | |1 | ||
+ | |0<sub>12</sub> | ||
+ | |rowspan="2"|) × ( | ||
+ | |1 | ||
+ | |0<sub>12</sub> | ||
+ | |rowspan="2"|) = ( | ||
+ | |1 | ||
+ | |0<sub>12</sub> | ||
+ | |rowspan="2"|) = diag(1, ..., 1) = E | ||
+ | |- | ||
+ | |0<sub>21</sub> | ||
+ | |H<sub>m − 1</sub> | ||
+ | |0<sub>21</sub> | ||
+ | |H<sub>m − 1</sub> | ||
+ | |0<sub>21</sub> | ||
+ | |H<sub>m − 1</sub><sup>2</sup> | ||
+ | |} | ||
+ | * U<sub>1</sub><sup>T</sup> = U<sub>1</sub><sup>T</sup> | ||
+ | |||
+ | {| | ||
+ | |rowspan="2"|U<sub>1</sub><sup>−1</sup>A = ( | ||
+ | |1 | ||
+ | |0<sub>12</sub> | ||
+ | |rowspan="2"|) × ( | ||
+ | |a11 | ||
+ | |y<sub>m − 1</sub> | ||
+ | |rowspan="2"|) = ( | ||
+ | |a11 | ||
+ | |y<sub>m − 1</sub> | ||
+ | |rowspan="2"|) | ||
+ | |- | ||
+ | |0<sub>21</sub> | ||
+ | |H<sub>m − 1</sub> | ||
+ | |x<sub>m − 1</sub> | ||
+ | |A<sub>m − 1</sub> | ||
+ | |H<sub>m − 1</sub>x<sub>m − 1</sub> | ||
+ | |H<sub>m − 1</sub>A<sub>m − 1</sub> | ||
+ | |} | ||
+ | {| | ||
+ | |rowspan="2"|U<sub>1</sub><sup>−1</sup>AU = ( | ||
+ | |a11 | ||
+ | |y<sub>m − 1</sub> | ||
+ | |rowspan="2"|) × ( | ||
+ | |1 | ||
+ | |0<sub>12</sub> | ||
+ | |rowspan="2"|) = ( | ||
+ | |a11 | ||
+ | |y<sub>m − 1</sub>H<sub>m − 1</sub> | ||
+ | |rowspan="2"|) = C<sub>1</sub> = матрица такого вида что первые два элемента в первом столбце не нули, остальные в первом столбце нули, остальные элементы перемешались | ||
+ | |- | ||
+ | |H<sub>m − 1</sub>x<sub>m − 1</sub> | ||
+ | |H<sub>m − 1</sub>A<sub>m − 1</sub> | ||
+ | |0<sub>21</sub> | ||
+ | |H<sub>m − 1</sub> | ||
+ | |H<sub>m − 1</sub>x<sub>m − 1</sub> | ||
+ | |H<sub>m − 1</sub>A<sub>m − 1</sub>H<sub>m − 1</sub> | ||
+ | |} | ||
+ | * Через n − 1 шаг получим почти верхнетреугольную матрицу. | ||
+ | * x<sub>m − 2</sub> = (c<sub>32</sub><sup>(1)</sup>, c<sub>42</sub><sup>(1)</sup>, …, c<sub>m2</sub><sup>(1)</sup>)<sup>T</sup>U<sub>1</sub> = H<sub>m − 2</sub>x<sub>m − 2</sub> = (−||x<sub>m − 2</sub>||, 0, …, 0)<sup>T</sup> | ||
+ | {| | ||
+ | |rowspan="4"|U<sub>2</sub> = ( | ||
+ | |1 | ||
+ | |0 | ||
+ | |... | ||
+ | |0 | ||
+ | |rowspan="4"|) | ||
+ | |- | ||
+ | |0 | ||
+ | |1 | ||
+ | |... | ||
+ | |0 | ||
+ | |- | ||
+ | |colspan="4"|... | ||
+ | |- | ||
+ | |0 | ||
+ | |0 | ||
+ | |... | ||
+ | |H<sub>m − 2</sub> | ||
+ | |} | ||
+ | * U<sub>2</sub><sup>−1</sup> = U<sub>2</sub><sup>T</sup> = U<sub>2</sub> | ||
+ | * C<sub>2</sub> = (нули в первом столбце кроме первых двух и во втором кроме первых трёх, остальные не нули) | ||
+ | * прошло n &minus 1 итераций... | ||
+ | * C = U<sub>m − 1</sub><sup>−1</sup>U<sub>m − 2</sub><sup>−1</sup>…U<sub>2</sub><sup>−1</sup>U<sub>1</sub><sup>−1</sup>AU<sub>1</sub>U<sub>2</sub>…U<sub>m − 2</sub>U<sub>m − 1</sub> = (верхняя почти треугольная) | ||
+ | * С = U<sup>−1</sup>AU | ||
+ | |||
+ | '''Замечание 1.''' λ<sub>k</sub><sup>A</sup> = λ<sub>k</sub><sup>C</sup>, k = 1…m<br /> | ||
+ | '''Доказательство'''. | ||
+ | * y = U<sup>−1</sup>x | ||
+ | * x = Uy | ||
+ | * Ax = λ<sup>A</sup>x, x ≠ 0 | ||
+ | * U<sup>−1</sup>Ax = λ<sup>A</sup>U<sup>−1</sup>x | ||
+ | * U<sup>−1</sup>AUy = λ<sup>A</sup>y | ||
+ | * Cy = λ<sup>A</sup>y | ||
+ | * λ<sup>A</sup> = λ<sup>C</sup> | ||
+ | |||
+ | '''Замечание 2'''. Пусть A = A<sup>T</sup> ⇒ C = C<sup>T</sup><br /> | ||
+ | '''Доказательство'''. | ||
+ | * С = U<sup>−1</sup>AU | ||
+ | * C<sup>T</sup> = (U<sup>−1</sup>AU)<sup>T</sup> = U<sup>T</sup>A<sup>T</sup>(U<sup>−1</sup>)<sup>T</sup> = U<sup>−1</sup>AU = C | ||
+ | |||
+ | == Параграф 11. Понятие о QR-алгоритме решения полной проблемы собственных значений == | ||
+ | |||
+ | ∀ A = Q × R, Q<sup>&minus1</sup> = Q<sup>T</sup>, R — верхнетреугольная матрица (1) | ||
+ | |||
+ | Оказывается, любую матрицу можно представить в виде разложения (1). | ||
+ | |||
+ | Возьмём x = (a11, ..., am1)<sup>T</sup>. Есть v такое, что H<sub>1</sub>x = (&minus||x||, 0, 0, ..., 0)<sup>T</sup>. | ||
+ | {| | ||
+ | |rowspan="4"|H<sub>1</sub>A = ( | ||
+ | |−||x|| | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |rowspan="4"|) | ||
+ | |- | ||
+ | |0 | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |- | ||
+ | |... | ||
+ | |- | ||
+ | |0 | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |} | ||
+ | |||
+ | {| | ||
+ | |rowspan="5"|H<sub>2</sub>H<sub>1</sub>A = ( | ||
+ | |x | ||
+ | |x | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |rowspan="5"|) | ||
+ | |- | ||
+ | |0 | ||
+ | |x | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |- | ||
+ | |0 | ||
+ | |0 | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |- | ||
+ | |... | ||
+ | |- | ||
+ | |0 | ||
+ | |0 | ||
+ | |x | ||
+ | |... | ||
+ | |x | ||
+ | |} | ||
+ | |||
+ | * Q = H<sub>1</sub>H<sub>2</sub>…H<sub>m − 1</sub> | ||
+ | * Q<sup>−1</sup> = H<sub>m − 1</sub><sup>−1</sup>H<sub>m − 2</sub><sup>−1</sup>…H<sub>1</sub><sup>−1</sup> = H<sub>m − 1</sub><sup>T</sup>H<sub>m − 2</sub><sup>T</sup>…H<sub>1</sub><sup>T</sup> = (H<sub>1</sub>H<sub>2</sub>…H<sub>m − 1</sub>)<sup>T</sup> = Q<sup>T</sup> | ||
+ | * Q<sup>−1</sup>A = R | ||
+ | * A = QR | ||
+ | |||
+ | QR-алгоритм — итерационный метод. Пусть есть A (m × m). Обозначим A = A<sub>0</sub>. Тогда мы можем разложить её в виде произведения A<sub>0</sub> = Q<sub>0</sub>R<sub>0</sub>. В качестве матрицы A<sub>1</sub> возьмём R<sub>0</sub>Q<sub>0</sub>. Утверждается, что их собственные значения совпадают. | ||
+ | * A<sub>1</sub> = Q<sub>0</sub><sup>−1</sup>A<sub>0</sub>Q<sub>0</sub> | ||
+ | * A<sub>1</sub> = Q<sub>1</sub>R<sub>1</sub> | ||
+ | * ... | ||
+ | Предельная матрица сходится (без доказательства). | ||
+ | * Матрица сходится к одному из двух значений: | ||
+ | ** Если матрица вещественная, то lim<sub>k → ∞</sub> A<sub>k</sub> — верхнетреугольная матрица. В этом случае собственные значения лежат на диагонали. | ||
+ | ** Если есть комплексные собственные значения, то на диагонали будут клеточки 2×2 | ||
+ | |||
+ | Оценка количества действий: | ||
+ | * полная — O(m<sup>3</sup>) | ||
+ | * ВПТФ — O(m<sup>2</sup>) | ||
+ | * A = A<sup>T</sup> O(m) | ||
+ | {{Численные Методы}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 1. Численные методы линейной алгебры
[править] Параграф 10. Приведение матрицы к почти треугольной форме (к верхней почти треугольной форме — ВПТФ)
Свойства матрицы H:
- H = HT
- Матрица ортогональная: 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
- Утверждение. Пусть задан ∀ 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
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |