Численные Методы, 04 лекция (от 20 февраля)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1469 участника 87.106.188.238 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 03 лекция (от 19 февраля)|Предыдущая лекция]] | [[Численные Методы, 05 лекция (от 27 февраля)|Следующая лекция]] |
- | + | ||
- | + | = Глава 1. Численные методы линейной алгебры = | |
- | + | == Параграф 6. Теоремы о сходимости итерационных методов == | |
+ | === Энергетическая норма === | ||
+ | |||
+ | Пусть есть самосопряжённый положительно определённый оператор D = D* > 0 | ||
+ | |||
+ | Положительно определённый оператор: | ||
+ | Есть пространство x ∈ H. Оператор положительно определённый, если (Dx, x) > 0, ∀ x ≠ 0. | ||
+ | |||
+ | Неотрицательный оператор: (Dx, x) ≥ 0, ∀ x ≠ 0. | ||
+ | |||
+ | Если оператор положительно определённый, то тогда ∃ δ> 0: (Dx, x) ≥δ(x, x) | ||
+ | |||
+ | Теперь мы можем ввести энергетическую норму: ||x||<sub>D</sub> = (Dx,x)<sup><sup>1</sup>/<sub>2</sub></sup> | ||
+ | |||
+ | Переходит в обычную при D = E. | ||
+ | |||
+ | Оказывается, можно ввести положительную определённость для несамосопряжённого вещественного оператора: если H — вещественный, то D > 0: (Dx, x) > 0, x ≠ 0 | ||
+ | |||
+ | Если D = D* > 0, то ∃ D<sup>−1</sup> = (D<sup>−1</sup>)* > 0. Кроме того, ∃ D<sup><sup>1</sup>/<sub>2</sub></sup> = (D<sup><sup>1</sup>/<sub>2</sub></sup>)* > 0, ∃ D<sup>−<sup>1</sup>/<sub>2</sub></sup> = (D<sup>−<sup>1</sup>/<sub>2</sub></sup>)* > 0. | ||
+ | |||
+ | '''Задача'''. H — вещественный, D > 0. Показать, что (<sup>(D + D*)</sup>/<sub>2</sub>x, x) = (Dx, x), <sup>(D + D*)</sup>/<sub>2</sub> > 0 | ||
+ | |||
+ | Для оценки скорости сходимости введём '''вектор погрешности''': v<sup>n</sup> = x<sup>n</sup> − x. | ||
+ | |||
+ | * Ax = f (1) | ||
+ | * ∃ A<sup>−1</sup> (m × m) | ||
+ | * B <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f (2) | ||
+ | * x<sup>n</sup> = v<sup>n</sup> + x | ||
+ | * B (v<sup>n + 1</sup> − v<sup>n</sup>)/τ + Av<sup>n</sup> = 0 (3) | ||
+ | * (v<sup>n + 1</sup> − v<sup>n</sup>)/τ + B<sup>−1</sup>Av<sup>n</sup> = 0 | ||
+ | * v<sup>n+1</sup> = v<sup>n</sup> − τB<sup>−1</sup>Av<sup>n</sup> = (E − τB<sup>−1</sup>A)v<sup>n</sup> | ||
+ | * S = E − τB<sup>−1</sup>A (4) | ||
+ | |||
+ | Мы получили матрицу перехода, и многое от неё зависит, точнее от её спектра. Чем компактнее спектр, тем лучше сходимость. | ||
+ | |||
+ | '''Теорема 1'''. Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S по модулю меньше 1: |λ<sub>k</sub><sup>S</sup>| < 1. | ||
+ | |||
+ | Это означает, что оператор S — сжимающий. | ||
+ | |||
+ | (Доказательство есть в Бахвалове, на лекции не приводилось) | ||
+ | |||
+ | Далее H — вещественное. | ||
+ | |||
+ | '''Теорема 2 (Самарского, о достаточном условии сходимости метода (2))'''. Пусть есть A = A* = A<sup>T</sup> > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0 (5). Тогда (2) сходится при любом начальном приближении в среднеквадратичной норме ||x<sup>n</sup> − x|| = (∑<sub>i = 1</sub><sup>m</sup> (x<sub>i</sub><sup>n</sup> − xi)<sup>2</sup>)<sup><sup>1</sup>/<sub>2</sub></sup> → 0, n → ∞. | ||
+ | |||
+ | <div class="comment">Можно записать условия, которые неконструктивные, которые не проверишь. Проверим: первое условие нормальное, ибо почти всегда матрицы симметрические. На B условие самосопряжённости не накладываем. Таким образом, условия не жёсткие.</div> | ||
+ | |||
+ | '''Идея доказательства''': введём числовую последовательность, докажем её монотонность, огрограниченность, и получим, что в этой норме вектор сходится к 0. | ||
+ | |||
+ | '''Доказательство'''. Введём y<sub>n</sub> = (Av<sup>n</sup>, v<sup>n</sup>) ≥ 0. Найдём y<sub>n + 1</sub> = (Av<sup>n + 1</sup>, v<sup>n + 1</sup>) = (A(E − τB<sup>−1</sup>A)v<sup>n</sup>, (E − τB<sup>−1</sup>A)v<sup>n</sup>) = (Av<sup>n</sup>, v<sup>n</sup>) − τ((AB<sup>−1</sup>Av<sup>n</sup>, v<sup>n</sup>) + (Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) − τ(AB<sup>−1</sup>Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>)) = (*) | ||
+ | |||
+ | (B<sup>−1</sup>Av<sup>n</sup>, Av<sup>n</sup>) = (Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) | ||
+ | |||
+ | (*) = y<sub>n</sub> − τ(2(Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) − τ(AB<sup>−1</sup>Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>)) = y<sub>n</sub> − 2τ((B − 0,5τA)B<sup>−1</sup>Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) | ||
+ | |||
+ | ((B − 0,5τA)B<sup>−1</sup>Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) ≥ 0 ⇒ y<sub>n + 1</sub> ≤ y<sub>n</sub> | ||
+ | |||
+ | Последовательность невозрастающая и, следовательно, имеет предел. | ||
+ | |||
+ | ∃ δ > 0: ((B − 0,5τA)B<sup>−1</sup>Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) ≥ δ||B<sup>−1</sup>Av<sup>n</sup>||<sup>2</sup> (на основании задачи) | ||
+ | |||
+ | (y<sub>n + 1</sub> − y<sub>n</sub>)/τ + 2((B − 0,5τA)B<sup>−1</sup>Av<sup>n</sup>, B<sup>−1</sup>Av<sup>n</sup>) = 0 | ||
+ | |||
+ | В силу задачи можем подставить: | ||
+ | (y<sub>n + 1</sub> − y<sub>n</sub>)/τ + δ||B<sup>−1</sup>Av<sup>n</sup>||<sup>2</sup> ≤ 0 | ||
+ | |||
+ | при n → ∞: | ||
+ | |||
+ | lim ||B<sup>−1</sup>Av<sup>n</sup>|| = 0 | ||
+ | |||
+ | ω<sup>n</sup> = B<sup>−1</sup>Av<sup>n</sup> | ||
+ | |||
+ | v<sup>n</sup> = A<sup>−1</sup>Bω<sup>n</sup> | ||
+ | |||
+ | ||v<sup>n</sup>|| ≤ ||A<sup>−1</sup>B|| ||ω<sup>n</sup>|| | ||
+ | |||
+ | lim<sub>n → ∞</sub> ||v<sup>n</sup>|| = 0 | ||
+ | |||
+ | lim<sub>n → ∞</sub> ||x<sup>n</sup> − x|| = 0 | ||
+ | |||
+ | чтд. | ||
+ | |||
+ | '''Следствие 1'''. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Якоби сходится при любом начальном приближении. | ||
+ | |||
+ | '''Доказательство'''. | ||
+ | * A = R<sub>1</sub> + D + R<sub>2</sub> | ||
+ | * D(x<sup>n + 1</sup> − x<sup>n</sup>) + Ax<sup>n + 1</sup> = f | ||
+ | * τ = 1, B = D, a<sub>ii</sub> ≠ 0 | ||
+ | * D − 0,5A > 0 | ||
+ | * 2D > A | ||
+ | чтд | ||
+ | |||
+ | '''Задача'''. Доказать, что если A = A* > 0 ⇒ a<sub>ii</sub> > 0, i = 1..m | ||
+ | |||
+ | '''Следствие 2'''. Пусть ∃ A = A* > 0, матрица со строгим диагональным преобладанием: a<sub>ii</sub> > ∑<sub>j = 1, j ≠ i</sub><sup>m</sup>|a<sub>ij</sub>|, i =1..m (6) | ||
+ | |||
+ | '''Доказательство'''. | ||
+ | |||
+ | * 2D > A | ||
+ | * (Ax, x) = ∑<sub>i, j = 1</sub><sup>m</sup>a<sub>ij</sub>x<sub>i</sub>x<sub>j</sub> ≤ ∑<sub>i, j = 1</sub><sup>m</sup>|a<sub>ij</sub>| |x<sub>i</sub>| |x<sub>j</sub>| ≤ (ab < a<sup>2</sup> + b<sup>2</sup>) ∑<sub>i, j = 1</sub><sup>m</sup>|a<sub>ij</sub>| |x<sub>i</sub>|<sup>2</sup>/2 + ∑<sub>i, j = 1</sub><sup>m</sup>|a<sub>ij</sub>| |x<sub>j</sub>|<sup>2</sup>/2 = ∑<sub>i, j = 1</sub><sup>m</sup>|a<sub>ij</sub>| |x<sub>i</sub>|<sup>2</sup>/2 + ∑<sub>j, i = 1</sub><sup>m</sup>|a<sub>ji</sub>| |x<sub>i</sub>|<sup>2</sup>/2 = ∑<sub>i, j = 1</sub><sup>m</sup>|a<sub>ij</sub>| |x<sub>i</sub>|<sup>2</sup> = ∑<sub>i, = 1</sub><sup>m</sup>(a<sub>ii</sub> + ∑<sub>j = 1, j ≠ i</sub><sup>m</sup>|a<sub>ij</sub>|) x<sub>i</sub><sup>2</sup> = (**) | ||
+ | |||
+ | 2a<sub>ii</sub> > a<sub>ii</sub> + ∑<sub>j = 1, j ≠ i</sub><sup>m</sup>|a<sub>ij</sub>| | ||
+ | |||
+ | (**) < 2∑<sub>i, = 1</sub><sup>m</sup>a<sub>ii</sub>x<sub>i</sub><sup>2</sup> | ||
+ | |||
+ | (Ax, x) < 2∑<sub>i, = 1</sub><sup>m</sup>a<sub>ii</sub>x<sub>i</sub><sup>2</sup> = 2(Dx, x) ⇒ 2D > A — сходится | ||
+ | |||
+ | чтд. | ||
+ | |||
+ | Метод простой итерации: (x<sup>n + 1</sup>+xn)/τ + Ax<sup>n</sup> = f, x<sup>0</sup> — задано | ||
+ | |||
+ | '''Следствие 3'''. Пусть ∃ A = A* > 0, γ<sub>2</sub> = max<sub>1 ≤ x ≤ m</sub>λ<sub>k</sub><sup>A</sup> > 0. Тогда 0 < τ < 2/γ<sub>2</sub> МПИ сходится при ∀ x<sup>0</sup> | ||
+ | |||
+ | '''Доказательство'''. Условие преобразуется в E − 0,5τA > 0, 1 − 0,5τλ<sub>k</sub><sup>A</sup> > 0, 1 − 0,5τγ<sub>2</sub> > 0, 0 < τ < 2/γ<sub>2</sub>. | ||
+ | |||
+ | {{Численные Методы}} |
Текущая версия
Предыдущая лекция | Следующая лекция
[править] Глава 1. Численные методы линейной алгебры
[править] Параграф 6. Теоремы о сходимости итерационных методов
[править] Энергетическая норма
Пусть есть самосопряжённый положительно определённый оператор D = D* > 0
Положительно определённый оператор: Есть пространство x ∈ H. Оператор положительно определённый, если (Dx, x) > 0, ∀ x ≠ 0.
Неотрицательный оператор: (Dx, x) ≥ 0, ∀ x ≠ 0.
Если оператор положительно определённый, то тогда ∃ δ> 0: (Dx, x) ≥δ(x, x)
Теперь мы можем ввести энергетическую норму: ||x||D = (Dx,x)1/2
Переходит в обычную при D = E.
Оказывается, можно ввести положительную определённость для несамосопряжённого вещественного оператора: если H — вещественный, то D > 0: (Dx, x) > 0, x ≠ 0
Если D = D* > 0, то ∃ D−1 = (D−1)* > 0. Кроме того, ∃ D1/2 = (D1/2)* > 0, ∃ D−1/2 = (D−1/2)* > 0.
Задача. H — вещественный, D > 0. Показать, что ((D + D*)/2x, x) = (Dx, x), (D + D*)/2 > 0
Для оценки скорости сходимости введём вектор погрешности: vn = xn − x.
- Ax = f (1)
- ∃ A−1 (m × m)
- B (xn + 1 − xn)/τ + Axn = f (2)
- xn = vn + x
- B (vn + 1 − vn)/τ + Avn = 0 (3)
- (vn + 1 − vn)/τ + B−1Avn = 0
- vn+1 = vn − τB−1Avn = (E − τB−1A)vn
- S = E − τB−1A (4)
Мы получили матрицу перехода, и многое от неё зависит, точнее от её спектра. Чем компактнее спектр, тем лучше сходимость.
Теорема 1. Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S по модулю меньше 1: |λkS| < 1.
Это означает, что оператор S — сжимающий.
(Доказательство есть в Бахвалове, на лекции не приводилось)
Далее H — вещественное.
Теорема 2 (Самарского, о достаточном условии сходимости метода (2)). Пусть есть A = A* = AT > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0 (5). Тогда (2) сходится при любом начальном приближении в среднеквадратичной норме ||xn − x|| = (∑i = 1m (xin − xi)2)1/2 → 0, n → ∞.
Идея доказательства: введём числовую последовательность, докажем её монотонность, огрограниченность, и получим, что в этой норме вектор сходится к 0.
Доказательство. Введём yn = (Avn, vn) ≥ 0. Найдём yn + 1 = (Avn + 1, vn + 1) = (A(E − τB−1A)vn, (E − τB−1A)vn) = (Avn, vn) − τ((AB−1Avn, vn) + (Avn, B−1Avn) − τ(AB−1Avn, B−1Avn)) = (*)
(B−1Avn, Avn) = (Avn, B−1Avn)
(*) = yn − τ(2(Avn, B−1Avn) − τ(AB−1Avn, B−1Avn)) = yn − 2τ((B − 0,5τA)B−1Avn, B−1Avn)
((B − 0,5τA)B−1Avn, B−1Avn) ≥ 0 ⇒ yn + 1 ≤ yn
Последовательность невозрастающая и, следовательно, имеет предел.
∃ δ > 0: ((B − 0,5τA)B−1Avn, B−1Avn) ≥ δ||B−1Avn||2 (на основании задачи)
(yn + 1 − yn)/τ + 2((B − 0,5τA)B−1Avn, B−1Avn) = 0
В силу задачи можем подставить: (yn + 1 − yn)/τ + δ||B−1Avn||2 ≤ 0
при n → ∞:
lim ||B−1Avn|| = 0
ωn = B−1Avn
vn = A−1Bωn
||vn|| ≤ ||A−1B|| ||ωn||
limn → ∞ ||vn|| = 0
limn → ∞ ||xn − x|| = 0
чтд.
Следствие 1. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Якоби сходится при любом начальном приближении.
Доказательство.
- A = R1 + D + R2
- D(xn + 1 − xn) + Axn + 1 = f
- τ = 1, B = D, aii ≠ 0
- D − 0,5A > 0
- 2D > A
чтд
Задача. Доказать, что если A = A* > 0 ⇒ aii > 0, i = 1..m
Следствие 2. Пусть ∃ A = A* > 0, матрица со строгим диагональным преобладанием: aii > ∑j = 1, j ≠ im|aij|, i =1..m (6)
Доказательство.
- 2D > A
- (Ax, x) = ∑i, j = 1maijxixj ≤ ∑i, j = 1m|aij| |xi| |xj| ≤ (ab < a2 + b2) ∑i, j = 1m|aij| |xi|2/2 + ∑i, j = 1m|aij| |xj|2/2 = ∑i, j = 1m|aij| |xi|2/2 + ∑j, i = 1m|aji| |xi|2/2 = ∑i, j = 1m|aij| |xi|2 = ∑i, = 1m(aii + ∑j = 1, j ≠ im|aij|) xi2 = (**)
2aii > aii + ∑j = 1, j ≠ im|aij|
(**) < 2∑i, = 1maiixi2
(Ax, x) < 2∑i, = 1maiixi2 = 2(Dx, x) ⇒ 2D > A — сходится
чтд.
Метод простой итерации: (xn + 1+xn)/τ + Axn = f, x0 — задано
Следствие 3. Пусть ∃ A = A* > 0, γ2 = max1 ≤ x ≤ mλkA > 0. Тогда 0 < τ < 2/γ2 МПИ сходится при ∀ x0
Доказательство. Условие преобразуется в E − 0,5τA > 0, 1 − 0,5τλkA > 0, 1 − 0,5τγ2 > 0, 0 < τ < 2/γ2.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |