м |
|
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 03 лекция (от 19 февраля)|Предыдущая лекция]] | [[Численные Методы, 05 лекция (от 27 февраля)|Следующая лекция]]
| + | == 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. |
| - | == Параграф 6. Теоремы о сходимости итерационных методов ==
| + | Dig yourself a grave - you will need it. |
| - | === Энергетическая норма ===
| + | |
| - | | + | |
| - | Пусть есть самосопряжённый положительно определённый оператор 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>.
| + | |
| - | | + | |
| - | {{Численные Методы}}
| + | |
We at EbaumsWorld consider you as disgrace of human race.
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
Dig yourself a grave - you will need it.
