| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 06 лекция (от 05 марта)|Предыдущая лекция]] | [[Численные Методы, 08 лекция (от 12 марта)|Следующая лекция]]
| + | == From Ebaums Inc to MurkLoar. == |
| - | | + | We at EbaumsWorld consider you as disgrace of human race. |
| - | = Глава 1. Численные методы линейной алгебры = | + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
| - | == Параграф 9. Методы решения задач на собственные значения ==
| + | Dig yourself a grave - you will need it. |
| - | λ<sub>m</sub><sup>(n)</sup> = x<sub>n+1</sub><sup>(i)</sup>/x<sub>n</sub><sup>(i)</sup> = (c<sub>1</sub>λ<sub>1</sub><sup>n+1</sup>e<sub>1</sub><sup>(i)</sup> + c<sub>2</sub>λ<sub>2</sub><sup>n+1</sup>e<sub>2</sub><sup>(i)</sup> + ... + c<sub>m</sub>λ<sub>m</sub><sup>n+1</sup>e<sub>m</sub><sup>(i)</sup>)/(c<sub>1</sub>λ<sub>1</sub><sup>n</sup>e<sub>1</sub><sup>(i)</sup> + c<sub>2</sub>λ<sub>2</sub><sup>n</sup>e<sub>2</sub><sup>(i)</sup> + ... + c<sub>m</sub>λ<sub>m</sub><sup>n</sup>e<sub>m</sub><sup>(i)</sup>) = c<sub>m</sub>λ<sub>m</sub><sup>n+1</sup>e<sub>m</sub><sup>(i)</sup>(1 + … + (c<sub>1</sub>λ<sub>1</sub><sup>n+1</sup>e<sub>1</sub><sup>(i)</sup>)/(c<sub>m</sub>λ<sub>m</sub><sup>n+1</sup>e<sub>m</sub><sup>(i)</sup>))/c<sub>m</sub>λ<sub>m</sub><sup>n</sup>e<sub>m</sub><sup>(i)</sup>(1 + … + (c<sub>1</sub>λ<sub>1</sub><sup>n</sup>e<sub>1</sub><sup>(i)</sup>)/(c<sub>m</sub>λ<sub>m</sub><sup>n</sup>e<sub>m</sub><sup>(i)</sup>)) = λ<sub>m</sub>
| + | |
| - | | + | |
| - | λ<sub>m</sub><sup>(n)</sup> − λ<sub>m</sub> = O(|λ<sub>m − 1</sub>/λ<sub>m</sub>|)<sup>n</sup> (n → ∞), (λ<sub>m</sub><sup>(n)</sup> → λ<sub>m</sub>), i = 1..m
| + | |
| - | | + | |
| - | Точность достигнута, когда изменения по каждой координате в пределах погрешности.
| + | |
| - | | + | |
| - | Ясно, что λ<sub>m</sub><sup>(n)</sup> = (Ax<sub>n</sub>, x<sub>n</sub>)/(x<sub>n</sub>, x<sub>n</sub>). Так как всё известно то это даёт простой способ вычисления. Рассмотрим некоторые случаи:
| + | |
| - | | + | |
| - | # A = A*. Тогда гарантированно существует ортонормированный базис {e<sub>k</sub>}<sub>1</sub><sup>m</sup>, (e<sub>i</sub>, e<sub>j</sub>) = δ<sub>ij</sub>, Ae<sub>k</sub> = λ<sub>k</sub>e<sub>k</sub>, k = 1..m. Тогда λ<sub>m</sub><sup>(n)</sup> = (Ax<sub>n</sub>, x<sub>n</sub>)/(x<sub>n</sub>, x<sub>n</sub>) = (x<sub>n + 1</sub>, x<sub>n</sub>)/(x<sub>n</sub>, x<sub>n</sub>) = (c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sub>2n + 1</sub> + … + c<sub>1</sub><sup>2</sup>λ<sub>1</sub><sub>2n + 1</sub>)/(c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sub>2n</sub> + … + c<sub>1</sub><sup>2</sup>λ<sub>1</sub><sub>2n</sub>) = c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sub>2n + 1</sub>(1 + … + (c<sub>1</sub><sup>2</sup>λ<sub>1</sub><sub>2n + 1</sub>)/(c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sub>2n + 1</sub>))/c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sub>2n</sub>(1 + … + (c<sub>1</sub><sup>2</sup>λ<sub>1</sub><sub>2n</sub>)/(c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sub>2n</sub>)) = λ<sub>m</sub> + O(λ<sub>m + 1</sub>/λ<sub>m</sub>)<sup>2n</sup>. То есть для самосопряжённой матрицы сходимость быстрее.
| + | |
| - | # {e<sub>k</sub>}<sub>1</sub><sup>m</sup> — базис из собственных векторов. λ<sub>m</sub><sup>(n)</sup> = (x<sub>n + 1</sub>, x<sub>n</sub>)/(x<sub>n</sub>, x<sub>n</sub>) = (∑<sub>i, j = 1</sub><sup>m</sup> c<sub>i</sub>c<sub>j</sub>λ<sub>i</sub><sup>n + 1</sup>λ<sub>j</sub><sup>n</sup>(e<sub>i</sub>, e<sub>j</sub>))/(∑<sub>i, j = 1</sub><sup>m</sup> c<sub>i</sub>c<sub>j</sub>λ<sub>i</sub><sup>n</sup>λ<sub>j</sub><sup>n</sup>(e<sub>i</sub>, e<sub>j</sub>)) = (λ<sub>i</sub><sup>2n + 1</sup>c<sub>m</sub><sup>2</sup>(e<sub>m</sub>, e<sub>m</sub>) + … + λ<sub>i</sub><sup>2n + 1</sup>c<sub>1</sub><sup>2</sup>(e<sub>1</sub>, e<sub>1</sub>))/(λ<sub>i</sub><sup>2n</sup>c<sub>m</sub><sup>2</sup>(e<sub>m</sub>, e<sub>m</sub>) + … + λ<sub>i</sub><sup>2n</sup>c<sub>1</sub><sup>2</sup>(e<sub>1</sub>, e<sub>1</sub>)) = λ<sub>i</sub><sup>2n + 1</sup>c<sub>m</sub><sup>2</sup>(e<sub>m</sub>, e<sub>m</sub>)(1 + … + (λ<sub>i</sub><sup>2n + 1</sup>c<sub>1</sub><sup>2</sup>(e<sub>1</sub>, e<sub>1</sub>))/(λ<sub>i</sub><sup>2n + 1</sup>c<sub>m</sub><sup>2</sup>(e<sub>m</sub>, e<sub>m</sub>)))/λ<sub>i</sub><sup>2n</sup>c<sub>m</sub><sup>2</sup>(e<sub>m</sub>, e<sub>m</sub>)(1 + … + (λ<sub>i</sub><sup>2n</sup>c<sub>1</sub><sup>2</sup>(e<sub>1</sub>, e<sub>1</sub>))/(λ<sub>i</sub><sup>2n</sup>c<sub>m</sub><sup>2</sup>(e<sub>m</sub>, e<sub>m</sub>))) = λ<sub>m</sub> + O(λ<sub>m + 1</sub>/λ<sub>m</sub>)<sup>n</sup>. Меньше, чем для самосопряжённой матрицы, но оно и понятно.
| + | |
| - | | + | |
| - | Итог. что мы доказали: степенной метод, если для матрицы выполнены условия (A, B, C), имеет смысл.
| + | |
| - | | + | |
| - | Замечание. Матрица A вещественная, но собственные значения могут быть и вещественные, и комплексные. Принципиальным является момент: вектор тоже комплексный.
| + | |
| - | | + | |
| - | Сейчас лектор покажет, что если у нас есть СЗ λ = λ<sub>0</sub> + iλ<sub>1</sub>, то СВ надо искать в виде μ = μ<sub>0</sub> + iμ<sub>1</sub>, μ<sub>0</sub>, μ<sub>1</sub> — вещественные:
| + | |
| - | * A(μ<sub>0</sub> + iμ<sub>1</sub>) = (λ<sub>0</sub> + iλ<sub>1</sub>)(μ<sub>0</sub> + iμ<sub>1</sub>)
| + | |
| - | * Aμ<sub>0</sub> = λ<sub>0</sub>μ<sub>0</sub> − λ<sub>1</sub>μ<sub>1</sub>
| + | |
| - | * Aμ<sub>1</sub> = λ<sub>1</sub>μ<sub>0</sub> + λ<sub>0</sub>μ<sub>1</sub>
| + | |
| - | * μ<sub>1</sub> = 0, λ<sub>1</sub> ≠ 0, μ<sub>0</sub> = Θ → μ == Θ
| + | |
| - | | + | |
| - | <!-- педедыв -->
| + | |
| - | | + | |
| - | === Метод обратных итераций ===
| + | |
| - | | + | |
| - | # ∃ A<sup>−1</sup>. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
| + | |
| - | #* Ax<sub>n + 1</sub> = x<sub>n</sub>, n = 0, 1, …, x<sub>0</sub> — начальное приближение (3) Этот метод неявный. Перепишем его как:
| + | |
| - | #* x<sub>n + 1</sub> = A<sup>−1</sup>x<sub>n</sub> (4)
| + | |
| - | #* x<sub>n</sub> = (A<sup>−1</sup>)<sup>n</sup>x<sub>0</sub>
| + | |
| - | | + | |
| - | Условия:<br />
| + | |
| - | A) ∃ {e<sub>k</sub>}<sub>1</sub><sup>m</sup> из СВ<br />
| + | |
| - | B) |λ<sub>1</sub>/λ<sub>2</sub>| < 1<br />
| + | |
| - | C) x<sub>0</sub> = c<sub>1</sub>e<sub>1</sub>+ … + c<sub>m</sub>e<sub>m</sub>, c<sub>1</sub> ≠ 0
| + | |
| - | | + | |
| - | Тогда:
| + | |
| - | * x<sub>n</sub> = c<sub>1</sub>λ<sub>1</sub><sup>−n</sup>e<sub>1</sub>+ … + c<sub>m</sub>λ<sub>m</sub><sup>−n</sup>e<sub>m</sub>
| + | |
| - | * x<sub>n</sub>/e<sub>1</sub>λ<sub>1</sub><sup>−n</sup> = e<sub>1</sub> + … + (c<sub>m</sub>/c<sub>1</sub>)(λ<sub>1</sub>/λ<sub>m</sub>)<sup>n</sup>e<sub>m</sub>
| + | |
| - | | + | |
| - | '''Задача'''. Показать, что λ<sub>1</sub> = lim<sub>n → ∞</sub> (x<sub>n</sub><sup>(i)</sup>/x<sub>n + 1</sub><sup>(i)</sup>), i = 1…m
| + | |
| - | | + | |
| - | '''Задача'''. Показать, что λ<sub>1</sub><sup>(n)</sup> − λ<sub>1</sub> = O(λ<sub>1</sub>/λ<sub>2</sub>).
| + | |
| - | | + | |
| - | * λ<sub>1</sub><sup>(n)</sup> = (x<sub>n</sub>, <sub>n</sub>)/(Ax<sub>n</sub>, <sub>n</sub>)
| + | |
| - | * A = A*
| + | |
| - | * {e<sub>k</sub>}<sub>1</sub><sup>m</sup> ОНБ из СВ
| + | |
| - | * (e<sub>i</sub>, e<sub>j</sub>) = δ<sub>ij</sub>
| + | |
| - | * λ<sub>1</sub><sup>n</sup> = (x<sub>n</sub>, <sub>n</sub>)/(Ax<sub>n</sub>, <sub>n</sub>) = (x<sub>n</sub>, <sub>n</sub>)/(x<sub>n + 1</sub>, <sub>n</sub>) = (c<sub>1</sub><sup>2</sup>λ<sub>1</sub><sup>−2n</sup> + … + c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sup>−2n</sup>)/(c<sub>1</sub><sup>2</sup>λ<sub>1</sub><sup>−2n − 1</sup> + … + c<sub>m</sub><sup>2</sup>λ<sub>m</sub><sup>−2n − 1</sup>) = λ<sub>1</sub> + O(λ<sub>1</sub>/λ<sub>2</sub>)<sup>2n</sup>
| + | |
| - | ** x<sub>0</sub> = c<sub>1</sub>e<sub>1</sub>+ … + c<sub>m</sub>e<sub>m</sub>
| + | |
| - | ** x<sub>n</sub> = c<sub>1</sub>λ<sub>1</sub><sup>−n</sup>e<sub>1</sub>+ … + c<sub>m</sub>λ<sub>m</sub><sup>−n</sup>e<sub>m</sub>
| + | |
| - | ** x<sub>n + 1</sub> = c<sub>1</sub>λ<sub>1</sub><sup>−n − 1</sup>e<sub>1</sub>+ … + c<sub>m</sub>λ<sub>m</sub><sup>−n − 1</sup>e<sub>m</sub>
| + | |
| - | | + | |
| - | === Метод обратных итераций со сдвигом ===
| + | |
| - | | + | |
| - | * (A − αE)x<sub>n + 1</sub> = x<sub>n</sub> (5)
| + | |
| - | ** n = 0, 1, …, x<sub>0</sub> — начальное приближение, α ∈ R
| + | |
| - | * ∃ (A − αE)<sup>−1</sup>
| + | |
| - | * x<sub>n + 1</sub> = (A − αE)<sup>−1</sup>x<sub>n</sub>
| + | |
| - | * x<sub>n</sub> = e<sub>l</sub>
| + | |
| - | * 1/|λ<sub>l</sub> − α| = max<sub>1 ≤ k ≤ m</sub> 1/|λ<sub>k</sub> − α|
| + | |
| - | | + | |
| - | '''Задача'''. Когда λ<sub>l</sub> = lim<sub>n → ∞</sub> (α + x<sub>n</sub><sup>(i)</sup>/x<sub>n + 1</sub><sup>(i)</sup>)
| + | |
| - | | + | |
| - | == Параграф 10. Приведение матрицы к почти треугольной форме (к верхней почти треугольной форме — ВПТФ) ==
| + | |
| - | | + | |
| - | В чём идея полного решения проблемы, как получить весь спектр. Конечно, мы будем её по-другому решать, когда будем решать систему нелинейных уравнений. Получим характеристический многочлен и будем потихонечку находить. В чём заключается проблема нахождения итерационным методом, в чём идея? Теперь есть матрица A, на которую мы не накладываем никаких ограничений:
| + | |
| - | * Ax = λx, x == o(1), A (m × m)
| + | |
| - | Хорошо известно, что если бы матрицу удалось свести к треугольному (диагональному) виду, то числа на диагонали — собственные значения. И если удастся свести к ним, сохраняя спектр, то всё хорошо. Но сводить будем не произвольными преобразованиями, а преобразованиями подобия. И этими преобразованиями подобия C = Q<sup>−1</sup>AQ (2) сводить матрицу к предельной. Если мы сумеем к такой матрице C, свести, то спектр будет найден. Такая задача не решается аналитически, только приближённо, и мы рассмотрим QR-алгоритм, который позволяет это делать.
| + | |
| - | | + | |
| - | Теперь отметим такой факт: если сделать преобразование подобия с помощью ортогональной матрицы, то сохранится не только спектр, но и симметрия.
| + | |
| - | | + | |
| - | Что такое верхняя почти треугольная форма: эта форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.
| + | |
| - | | + | |
| - | Заметьте, что если у нас была симметричная, и преобразование делаем ортогональной, то получим трёхдиагональную матрицу, а для неё ещё на порядок снижается количество действий.
| + | |
| - | | + | |
| - | Матрица ортогональна, если Q<sup>−1</sup> = Q*.
| + | |
| - | | + | |
| - | * v = (v<sub>1</sub>, …, <sub>m</sub>)<sup>T</sup>
| + | |
| - | * v<sup>T</sup> = (v<sub>1</sub>, …, <sub>m</sub>)
| + | |
| - | * v<sup>T</sup>v = v<sub>1</sub><sup>2</sup> + v<sub>2</sub><sup>2</sup> + … + v<sub>m</sub><sup>2</sup> = ||v||<sup>2</sup>
| + | |
| - | | + | |
| - | '''Определение'''. Преобразование элементарных отражений (Преобразование Хаусхолдера).
| + | |
| - | Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E − 2 vv<sup>T</sup>/||v||<sup>2</sup> (3)
| + | |
| - | | + | |
| - | {|
| + | |
| - | |colspan="4"|v × v<sup>T</sup>
| + | |
| - | |(m × m)
| + | |
| - | |}
| + | |
| - | | + | |
| - | Свойства:
| + | |
| - | * Матрица является симметричной: H = H<sup>T</sup>
| + | |
| - | | + | |
| - | {{Численные Методы}}
| + | |
| - | {{Lection-stub}}
| + | |
