Численные Методы, 07 лекция (от 06 марта)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1321 участника 216.224.124.124 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 06 лекция (от 05 марта)|Предыдущая лекция]] | [[Численные Методы, 08 лекция (от 12 марта)|Следующая лекция]] |
- | + | ||
- | + | = Глава 1. Численные методы линейной алгебры = | |
- | + | == Параграф 9. Методы решения задач на собственные значения == | |
+ | λ<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>n</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}} |
Версия 18:12, 3 февраля 2008
Предыдущая лекция | Следующая лекция
Содержание |
Глава 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 − 1/λm|)n (n → ∞), (λm(n) → λm), i = 1..m
Точность достигнута, когда изменения по каждой координате в пределах погрешности.
Ясно, что λm(n) = (Axn, xn)/(xn, xn). Так как всё известно то это даёт простой способ вычисления. Рассмотрим некоторые случаи:
- 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 + 1/λm)2n. То есть для самосопряжённой матрицы сходимость быстрее.
- {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 + 1/λm)n. Меньше, чем для самосопряжённой матрицы, но оно и понятно.
Итог. что мы доказали: степенной метод, если для матрицы выполнены условия (A, B, C), имеет смысл.
Замечание. Матрица A вещественная, но собственные значения могут быть и вещественные, и комплексные. Принципиальным является момент: вектор тоже комплексный.
Сейчас лектор покажет, что если у нас есть СЗ λ = λ0 + iλ1, то СВ надо искать в виде μ = μ0 + iμ1, μ0, μ1 — вещественные:
- A(μ0 + iμ1) = (λ0 + iλ1)(μ0 + iμ1)
- Aμ0 = λ0μ0 − λ1μ1
- Aμ1 = λ1μ0 + λ0μ1
- μ1 = 0, λ1 ≠ 0, μ0 = Θ → μ == Θ
Метод обратных итераций
- ∃ A−1. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
- Axn + 1 = xn, n = 0, 1, …, x0 — начальное приближение (3) Этот метод неявный. Перепишем его как:
- xn + 1 = A−1xn (4)
- xn = (A−1)nxn
Условия:
A) ∃ {ek}1m из СВ
B) |λ1/λ2| < 1
C) x0 = c1e1+ … + cmem, c1 ≠ 0
Тогда:
- xn = c1λ1−ne1+ … + cmλm−nem
- xn/e1λ1−n = e1 + … + (cm/c1)(λ1/λm)nem
Задача. Показать, что λ1 = limn → ∞ (xn(i)/xn + 1(i)), i = 1…m
Задача. Показать, что λ1(n) − λ1 = O(λ1/λ2).
- λ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(λ1/λ2)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
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |