| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 02 лекция (от 13 февраля)|Предыдущая лекция]] | [[Численные Методы, 04 лекция (от 20 февраля)|Следующая лекция]]
| + | == 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. |
| - | == Параграф 4. Метод квадратного корня (продолжение) ==
| + | Dig yourself a grave - you will need it. |
| - | | + | |
| - | Мы рассматриваем задачу
| + | |
| - | * Ax = f (1)
| + | |
| - | * A имеет размер m × m
| + | |
| - | * |A| ≠ 0
| + | |
| - | * A = A* ⇔ a<sub>ij</sub> = <span style="border-top:solid 1px">a<sub>ji</sub></span>
| + | |
| - | * A = S*DS, s<sub>ij</sub> > 0 (2)
| + | |
| - | | + | |
| - | (DS)<sub>ij</sub> — элемент, стоящий в j-м столбце i-й строке,
| + | |
| - | * (DS)<sub>ij</sub> = ∑<sub>l = 1</sub><sup>m</sup>d<sub>il</sub>s<sub>lj</sub>
| + | |
| - | * (S*DS)<sub>ij</sub> = ∑<sub>l = 1</sub><sup>m</sup><span style="border-top:solid 1px">s<sub>li</sub></span>d<sub>ll</sub>s<sub>lj</sub> = ∑<sub>l = 1</sub><sup>i − 1</sup><span style="border-top:solid 1px">s<sub>li</sub></span>d<sub>ll</sub>s<sub>lj</sub> + <span style="border-top:solid 1px">s<sub>ii</sub></span>d<sub>ii</sub>s<sub>ii</sub> + ∑<sub>l = i + 1</sub><sup>m</sup><span style="border-top:solid 1px">s<sub>li</sub></span>d<sub>ll</sub>s<sub>lj</sub> = a<sub>ij</sub>
| + | |
| - | | + | |
| - | Рассмотрим <span style="border-top:solid 1px">s<sub>li</sub></span>: <span style="border-top:solid 1px">s<sub>li</sub></span> = 0, l > i ⇒ 3-е слагаемое равно 0.
| + | |
| - | | + | |
| - | * <span style="border-top:solid 1px">s<sub>ii</sub></span>d<sub>ii</sub>s<sub>ii</sub> = a<sub>ij</sub> − ∑<sub>l = 1</sub><sup>i − 1</sup><span style="border-top:solid 1px">s<sub>li</sub></span>d<sub>ll</sub>s<sub>lj</sub>, i ≤ j (*)
| + | |
| - | | + | |
| - | Рассмотрим это соотношение при i = j
| + | |
| - | * s<span style="border-top:solid 1px">s</span> = |s|<sup>2</sup>
| + | |
| - | * <span style="border-top:solid 1px">s<sub>ii</sub></span> = a<sub>ii</sub> − ∑<sub>l = 1</sub><sup>i − 1</sup><span style="border-top:solid 1px">s<sub>li</sub></span>s<sub>li</sub>d<sub>ll</sub>
| + | |
| - | * d<sub>ii</sub> = sign(a<sub>ii</sub> − ∑<sub>l = 1</sub><sup>i − 1</sup>|s<sub>li</sub>|<sup>2</sup>d<sub>ll</sub>) (4)
| + | |
| - | * s<sub>ii</sub> = √<span style="border-top:solid 1px">a<sub>ii</sub> − ∑<sub>l = 1</sub><sup>i − 1</sup>|s<sub>li</sub>|<sup>2</sup>d<sub>ll</sub>)</span> (5)
| + | |
| - | | + | |
| - | из (*): s<sub>ij</sub> = <sup>a<sub>ij</sub> − ∑<sub>l = 1</sub><sup>i − 1</sup><span style="border-top:solid 1px">s<sub>li</sub></span>s<sub>li</sub>d<sub>ll</sub></sup>/<sub><span style="border-top:solid 1px">s<sub>ii</sub></span>d<sub>ii</sub></sub>, i < j (6)
| + | |
| - | | + | |
| - | Пока миноры ненулевые, разложение существует и единственно.
| + | |
| - | | + | |
| - | Для чего применяется данный алгоритм:
| + | |
| - | | + | |
| - | Факторизируем матрицу A и подставляем в уравнение:
| + | |
| - | | + | |
| - | S*DS = f
| + | |
| - | | + | |
| - | Оно сводится к двум системам, имеющие верхнетреугольный/нижнетреугольный вид и явно находящиеся решения:
| + | |
| - | * SDy = f (7)
| + | |
| - | * Sx = y (8)
| + | |
| - | | + | |
| - | Сложность — порядка <sup>m<sup>3</sup></sup>/<sub>6</sub> умножений и делений + m извлечений корня.
| + | |
| - | | + | |
| - | Плюс:
| + | |
| - | * Количество действий сокращается в два раза
| + | |
| - | Минусы:
| + | |
| - | * Только для эрмитовых матриц
| + | |
| - | | + | |
| - | Под прямыми методами можем подвести черту.
| + | |
| - | | + | |
| - | Теперь встаёт вопрос: если мы можем решать методом Гаусса, то зачем нужны другие методы решения?
| + | |
| - | # Точное решение всё равно не получить, ибо погрешности
| + | |
| - | # Правые части обычно задаются приближённо и тогда непонятно, зачем точный метод, когда решение всё равно будет приближённое
| + | |
| - | | + | |
| - | == Параграф 5. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений ==
| + | |
| - | | + | |
| - | Задача:
| + | |
| - | * Ax = f (1)
| + | |
| - | * A имеет размер m × m
| + | |
| - | * |A| ≠ 0
| + | |
| - | | + | |
| - | Что значит «решение итерационным методом»?
| + | |
| - | | + | |
| - | Обозначим:
| + | |
| - | * x<sub>i</sub><sup>n</sup> — i-я ккордината, n-я итерация
| + | |
| - | * x<sup>0</sup> — начальное приближение
| + | |
| - | | + | |
| - | Далее организуется процесс так, что lim<sub>n → ∞</sub>x<sup>n</sup> → x, то есть, в некоторой норме |x<sup>n</sup> − x| < ε, ε > 0
| + | |
| - | | + | |
| - | * n<sub>0</sub>(ε) — количество итераций. Эффективность алгоритма оценивается именно по нему. Например, метод Самарского сходится на порядок быстрее других.
| + | |
| - | | + | |
| - | Два вопроса, которые рассматриваются при исследовании итерационного метода?
| + | |
| - | * Будет ли сходиться
| + | |
| - | * С какой скоростью
| + | |
| - | | + | |
| - | Запишем уравнение (1) следующим образом:
| + | |
| - | | + | |
| - | ∑<sub>j = 1</sub><sup>m</sup>a<sub>ij</sub>x<sub>j</sub> = f<sub>i</sub>, i = <span style="border-top:solid 1px">1, m</span>
| + | |
| - | | + | |
| - | Запишем в виде:
| + | |
| - | | + | |
| - | ∑<sub>j = 1</sub><sup>i − 1</sup>a<sub>ij</sub> + a<sub>ii</sub>x<sub>i</sub> + ∑<sub>j = i + 1</sub><sup>m</sup>a<sub>ij</sub>x<sub>j</sub> = f<sub>i</sub>
| + | |
| - | | + | |
| - | Пусть a<sub>ii</sub> ≠ 0, x<sub>i</sub> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> − ∑<sub>j = 1</sub><sup>i − 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub> − ∑<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub> (2)
| + | |
| - | | + | |
| - | === Метод Якоби (МЯ) ===
| + | |
| - | | + | |
| - | Навешиваем слева (n + 1)-ю итерацию, а справа — n-ю:
| + | |
| - | | + | |
| - | * x<sub>i</sub><sup>n + 1</sup> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> − ∑<sub>j = 1</sub><sup>i − 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup> − ∑<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup>, n ∈ ℕ ∪ {0}
| + | |
| - | * x<sup>0</sup> — задано
| + | |
| - | | + | |
| - | Плюс:
| + | |
| - | * Данный метод реализуется достаточно просто
| + | |
| - | Минус:
| + | |
| - | * Очень медленная сходимость
| + | |
| - | <div class="comment">Что такое «очень», для математика, конечно, не очень</div>
| + | |
| - | | + | |
| - | === Метод Зейделя ===
| + | |
| - | * x<sub>i</sub><sup>n + 1</sup> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> − ∑<sub>j = 1</sub><sup>i − 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n + 1</sup> − ∑<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup>, n ∈ ℕ ∪ {0} (3)
| + | |
| - | * x<sup>0</sup> — задано
| + | |
| - | | + | |
| - | * x<sub>1</sub><sup>n + 1</sup> = <sup>f<sub>1</sub></sup>/<sub>a<sub>11</sub></sub> − ∑<sub>j = 2</sub><sup>m</sup> <sup>a<sub>1j</sub></sup>/<sub>a<sub>11</sub></sub>x<sub>j</sub><sup>n</sup>
| + | |
| - | * x<sub>2</sub><sup>n + 1</sup> = <sup>f<sub>2</sub></sup>/<sub>a<sub>22</sub></sub> − <sup>a<sub>21</sub></sup>/<sub>a<sub>22</sub></sub>x<sub>1</sub><sup>n + 1</sup> − ∑<sub>j = 3</sub><sup>m</sup> <sup>a<sub>1j</sub></sup>/<sub>a<sub>22</sub></sub>x<sub>j</sub><sup>n</sup>
| + | |
| - | | + | |
| - | Продвигаясь по координате i мы получаем все координаты.
| + | |
| - | | + | |
| - | По сложности и сходимости эти два метода одинаковы
| + | |
| - | | + | |
| - | {|style="text-align:center"
| + | |
| - | |
| + | |
| - | {|
| + | |
| - | |rowspan = "3"|R<sub>1</sub> = (
| + | |
| - | |0
| + | |
| - | |…
| + | |
| - | |0
| + | |
| - | |rowspan = "3"|)
| + | |
| - | |-
| + | |
| - | |colspan="3"|⋱
| + | |
| - | |-
| + | |
| - | |a<sub>ij</sub>
| + | |
| - | |…
| + | |
| - | |0
| + | |
| - | |}
| + | |
| - | |
| + | |
| - | {|
| + | |
| - | |rowspan = "3"|P = (
| + | |
| - | |a<sub>11</sub>
| + | |
| - | |…
| + | |
| - | |0
| + | |
| - | |rowspan = "3"|)
| + | |
| - | |-
| + | |
| - | |colspan="3"|⋱
| + | |
| - | |-
| + | |
| - | |0
| + | |
| - | |…
| + | |
| - | |a<sub>mm</sub>
| + | |
| - | |}
| + | |
| - | |
| + | |
| - | {|
| + | |
| - | |rowspan = "3"|R<sub>2</sub> = (
| + | |
| - | |0
| + | |
| - | |…
| + | |
| - | |a<sub>ij</sub>
| + | |
| - | |rowspan = "3"|)
| + | |
| - | |-
| + | |
| - | |colspan="3"|⋱
| + | |
| - | |-
| + | |
| - | |0
| + | |
| - | |…
| + | |
| - | |0
| + | |
| - | |}
| + | |
| - | |}
| + | |
| - | <!-- педедыв -->
| + | |
| - | | + | |
| - | <!-- проведена первая перепись -->
| + | |
| - | | + | |
| - | Ясно, что ∀ A = R<sub>1</sub> + D + R<sub>2</sub>
| + | |
| - | | + | |
| - | * R<sub>1</sub>x + Dx + R<sub>2</sub>x = f
| + | |
| - | * Dx = f − R<sub>1</sub>x − R<sub>2</sub>x
| + | |
| - | * x = D<sup>−1</sup>f − D<sup>−1</sup>R<sub>1</sub>x − D<sup>−1</sup>R<sub>2</sub>x
| + | |
| - | | + | |
| - | В таком случае метод Якоби записывается следующим способом:
| + | |
| - | x<sup>n + 1</sup> = D<sup>−1</sup>f − D<sup>−1</sup>R<sub>1</sub>x<sup>n</sup> − D<sup>−1</sup>R<sub>2</sub>x<sup>n</sup>, n ∈ ℕ ∪ {0}, x<sup>0</sup> задано
| + | |
| - | | + | |
| - | метод Зейдаля: x<sup>n + 1</sup> = D<sup>−1</sup>f − D<sup>−1</sup>R<sub>1</sub>x<sup>n + 1</sup> − D<sup>−1</sup>R<sub>2</sub>x<sup>n</sup>, n ∈ ℕ ∪ {0}, x<sup>0</sup> задано
| + | |
| - | | + | |
| - | Когда существует D<sup>−1</sup>? когда a<sub>ii</sub> ≠ 0
| + | |
| - | | + | |
| - | * (МЯ) Dx<sup>n + 1</sup> = f − R<sub>1</sub>x<sup>n</sup> − R<sub>2</sub>x<sup>n</sup>
| + | |
| - | * (МЗ) (D + R<sub>1</sub>)x<sup>n + 1</sup> = f − R<sub>2</sub>x<sup>n</sup>
| + | |
| - | * (МЯ) D(x<sup>n + 1</sup> − x<sup>n</sup>) + ARx<sup>n</sup> = f
| + | |
| - | * (МЗ) (D + R<sub>1</sub>)(x<sup>n + 1</sup> − x<sup>n</sup>) + Ax<sup>n</sup> = f
| + | |
| - | | + | |
| - | Из-за разной записи в результате решили прийти к канонической форме. И это ввёл Самарский. Что позволило создать стройную теорию. В последней записи она информативнее.
| + | |
| - | | + | |
| - | '''Двуслойная запись''' — когда связываются две соседние итерации.
| + | |
| - | | + | |
| - | Можно строить многошаговые методы.
| + | |
| - | | + | |
| - | '''Определение'''. Канонической формой записи двуслойного итерационного метода решения системы (1) называется его запись в виде:
| + | |
| - | * B<sub>n + 1</sub> <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ<sub>n + 1</sub></sub> + Ax<sup>n</sup> = f (4)
| + | |
| - | где
| + | |
| - | * τ<sub>n + 1</sub> > 0, n ∈ ℕ ∪ {0}
| + | |
| - | * x<sup>0</sup> — задано
| + | |
| - | * ∃B<sub>n + 1</sub><sup>−1</sup>
| + | |
| - | | + | |
| - | Метод явный, если B<sub>n + 1</sub> = E. Если матрица диагональная, то тоже явный.
| + | |
| - | | + | |
| - | Если
| + | |
| - | * B<sub>n + 1</sub> = B
| + | |
| - | * τ<sub>n + 1</sub> = τ
| + | |
| - | В этом случае метод стационарный.
| + | |
| - | | + | |
| - | Два метода используются очень часто:
| + | |
| - | * Метод простой итерации (МПИ)
| + | |
| - | ** (МПИ) (x<sup>n+1</sup> − x<sup>n</sup>)/τ + Ax<sup>n</sup> = f, x<sup>0</sup> — задано, n ∈ ℕ ∪ {0}, τ > 0
| + | |
| - | ** Если τ меняется, то это другой метод, для которого Чебышевский набор параметров для него оптимален.
| + | |
| - | * Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ)
| + | |
| - | ** A = R<sub>1</sub> + R<sub>2</sub>, где R<sub>1</sub> — нижнетреугольная матрица с половиной диагоналиьных элементов, R<sub>2</sub> — верхнетреугольная матрица с половиной диагональных элементов
| + | |
| - | ** (E + ωR<sub>1</sub>)(E + ωR<sub>2</sub>)((x<sup>n + 1</sup> − x<sup>n</sup>)/τ) + Ax<sup>n</sup> = f (5)
| + | |
| - | *** n ∈ ℕ ∪ {0}, x<sup>0</sup> задано, ω > 0, τ > 0
| + | |
| - | ** Будем говорить хвалебные слова в адрес ПТИМ
| + | |
| - | ** В данном случае B = (E + ωR<sub>1</sub>)(E + ωR<sub>2</sub>)
| + | |
| - | | + | |
| - | <div class="comment">То, что метод неявный, стало явно видно</div>
| + | |
| - | | + | |
| - | === Реализация ПТИМ ===
| + | |
| - | | + | |
| - | Обозначим W<sub>n + 1</sub> = (E + ωR<sub>2</sub>)((x<sup>n + 1</sup> − x<sup>n</sup>)/τ)
| + | |
| - | | + | |
| - | Невязка: r<sup>n</sup> = f − Ax<sup>n</sup>
| + | |
| - | | + | |
| - | Тогда мы можем переписать ПТИМ следующим образом:
| + | |
| - | | + | |
| - | (E + ωR<sub>1</sub>)W<sub>n + 1</sub> = r<sup>n</sup> (6)
| + | |
| - | | + | |
| - | Введём вектор v<sub>n + 1</sub> = ((x<sup>n + 1</sup> − x<sup>n</sup>)/τ)
| + | |
| - | | + | |
| - | Тогда (E + ωR<sub>1</sub>)v<sub>n + 1</sub> = W<sub>n + 1</sub> (7)
| + | |
| - | | + | |
| - | x<sup>n + 1</sup> = x<sup>n</sup> + τv<sub>n + 1</sub> (8)
| + | |
| - | | + | |
| - | == Параграф 6. Теоремы о сходимости итерационных методов ==
| + | |
| - | | + | |
| - | * Ax = f (1)
| + | |
| - | * |A| ≠ 0, (m × m)
| + | |
| - | | + | |
| - | По-прежнему решаем систему (1) итерационными методами:
| + | |
| - | | + | |
| - | * B (x<sup>n + 1</sup> − x<sup>n</sup>)/τ + Ax<sup>n</sup> = f (2)
| + | |
| - | ** τ<sub>n + 1</sub> > 0
| + | |
| - | ** n ∈ ℕ ∪ {0}
| + | |
| - | ** x<sup>0</sup> задано
| + | |
| - | ** ∃A<sup>−1</sup>, B<sup>−1</sup>
| + | |
| - | | + | |
| - | Введём m-мерное пространство :
| + | |
| - | * ∀ x ∈ H
| + | |
| - | ** dim H = m
| + | |
| - | ** x = (x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>m</sub>)
| + | |
| - | ** ∀ x, y ∈ H (x, y) = ∑<sub>i = 1</sub><sup>m</sup>x<sub>i</sub>y<sub>i</sub>
| + | |
| - | ** ||x|| = (x, x)<sup><sup>1</sup>/<sub>2</sub></sup> = (∑<sub>i = 1</sub><sup>m</sup> x<sub>i</sub><sup>2</sup>)<sup><sup>1</sup>/<sub>2</sub></sup>
| + | |
| - | | + | |
| - | {{Численные Методы}}
| + | |
