Численные Методы, 03 лекция (от 19 февраля)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1437 участника 85.25.151.22 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 02 лекция (от 13 февраля)|Предыдущая лекция]] | [[Численные Методы, 04 лекция (от 20 февраля)|Следующая лекция]] |
- | + | ||
- | + | = Глава 1. Численные методы линейной алгебры = | |
- | + | == Параграф 4. Метод квадратного корня (продолжение) == | |
+ | |||
+ | Мы рассматриваем задачу | ||
+ | * 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> | ||
+ | |||
+ | {{Численные Методы}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 1. Численные методы линейной алгебры
[править] Параграф 4. Метод квадратного корня (продолжение)
Мы рассматриваем задачу
- Ax = f (1)
- A имеет размер m × m
- |A| ≠ 0
- A = A* ⇔ aij = aji
- A = S*DS, sij > 0 (2)
(DS)ij — элемент, стоящий в j-м столбце i-й строке,
- (DS)ij = ∑l = 1mdilslj
- (S*DS)ij = ∑l = 1mslidllslj = ∑l = 1i − 1slidllslj + siidiisii + ∑l = i + 1mslidllslj = aij
Рассмотрим sli: sli = 0, l > i ⇒ 3-е слагаемое равно 0.
- siidiisii = aij − ∑l = 1i − 1slidllslj, i ≤ j (*)
Рассмотрим это соотношение при i = j
- ss = |s|2
- sii = aii − ∑l = 1i − 1slislidll
- dii = sign(aii − ∑l = 1i − 1|sli|2dll) (4)
- sii = √aii − ∑l = 1i − 1|sli|2dll) (5)
из (*): sij = aij − ∑l = 1i − 1slislidll/siidii, i < j (6)
Пока миноры ненулевые, разложение существует и единственно.
Для чего применяется данный алгоритм:
Факторизируем матрицу A и подставляем в уравнение:
S*DS = f
Оно сводится к двум системам, имеющие верхнетреугольный/нижнетреугольный вид и явно находящиеся решения:
- SDy = f (7)
- Sx = y (8)
Сложность — порядка m3/6 умножений и делений + m извлечений корня.
Плюс:
- Количество действий сокращается в два раза
Минусы:
- Только для эрмитовых матриц
Под прямыми методами можем подвести черту.
Теперь встаёт вопрос: если мы можем решать методом Гаусса, то зачем нужны другие методы решения?
- Точное решение всё равно не получить, ибо погрешности
- Правые части обычно задаются приближённо и тогда непонятно, зачем точный метод, когда решение всё равно будет приближённое
[править] Параграф 5. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений
Задача:
- Ax = f (1)
- A имеет размер m × m
- |A| ≠ 0
Что значит «решение итерационным методом»?
Обозначим:
- xin — i-я ккордината, n-я итерация
- x0 — начальное приближение
Далее организуется процесс так, что limn → ∞xn → x, то есть, в некоторой норме |xn − x| < ε, ε > 0
- n0(ε) — количество итераций. Эффективность алгоритма оценивается именно по нему. Например, метод Самарского сходится на порядок быстрее других.
Два вопроса, которые рассматриваются при исследовании итерационного метода?
- Будет ли сходиться
- С какой скоростью
Запишем уравнение (1) следующим образом:
∑j = 1maijxj = fi, i = 1, m
Запишем в виде:
∑j = 1i − 1aij + aiixi + ∑j = i + 1maijxj = fi
Пусть aii ≠ 0, xi = fi/aii − ∑j = 1i − 1 aij/aiixj − ∑j = i + 1m aij/aiixj (2)
[править] Метод Якоби (МЯ)
Навешиваем слева (n + 1)-ю итерацию, а справа — n-ю:
- xin + 1 = fi/aii − ∑j = 1i − 1 aij/aiixjn − ∑j = i + 1m aij/aiixjn, n ∈ ℕ ∪ {0}
- x0 — задано
Плюс:
- Данный метод реализуется достаточно просто
Минус:
- Очень медленная сходимость
[править] Метод Зейделя
- xin + 1 = fi/aii − ∑j = 1i − 1 aij/aiixjn + 1 − ∑j = i + 1m aij/aiixjn, n ∈ ℕ ∪ {0} (3)
- x0 — задано
- x1n + 1 = f1/a11 − ∑j = 2m a1j/a11xjn
- x2n + 1 = f2/a22 − a21/a22x1n + 1 − ∑j = 3m a1j/a22xjn
Продвигаясь по координате i мы получаем все координаты.
По сложности и сходимости эти два метода одинаковы
|
|
|
Ясно, что ∀ A = R1 + D + R2
- R1x + Dx + R2x = f
- Dx = f − R1x − R2x
- x = D−1f − D−1R1x − D−1R2x
В таком случае метод Якоби записывается следующим способом: xn + 1 = D−1f − D−1R1xn − D−1R2xn, n ∈ ℕ ∪ {0}, x0 задано
метод Зейдаля: xn + 1 = D−1f − D−1R1xn + 1 − D−1R2xn, n ∈ ℕ ∪ {0}, x0 задано
Когда существует D−1? когда aii ≠ 0
- (МЯ) Dxn + 1 = f − R1xn − R2xn
- (МЗ) (D + R1)xn + 1 = f − R2xn
- (МЯ) D(xn + 1 − xn) + ARxn = f
- (МЗ) (D + R1)(xn + 1 − xn) + Axn = f
Из-за разной записи в результате решили прийти к канонической форме. И это ввёл Самарский. Что позволило создать стройную теорию. В последней записи она информативнее.
Двуслойная запись — когда связываются две соседние итерации.
Можно строить многошаговые методы.
Определение. Канонической формой записи двуслойного итерационного метода решения системы (1) называется его запись в виде:
- Bn + 1 (xn + 1 − xn)/τn + 1 + Axn = f (4)
где
- τn + 1 > 0, n ∈ ℕ ∪ {0}
- x0 — задано
- ∃Bn + 1−1
Метод явный, если Bn + 1 = E. Если матрица диагональная, то тоже явный.
Если
- Bn + 1 = B
- τn + 1 = τ
В этом случае метод стационарный.
Два метода используются очень часто:
- Метод простой итерации (МПИ)
- (МПИ) (xn+1 − xn)/τ + Axn = f, x0 — задано, n ∈ ℕ ∪ {0}, τ > 0
- Если τ меняется, то это другой метод, для которого Чебышевский набор параметров для него оптимален.
- Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ)
- A = R1 + R2, где R1 — нижнетреугольная матрица с половиной диагоналиьных элементов, R2 — верхнетреугольная матрица с половиной диагональных элементов
- (E + ωR1)(E + ωR2)((xn + 1 − xn)/τ) + Axn = f (5)
- n ∈ ℕ ∪ {0}, x0 задано, ω > 0, τ > 0
- Будем говорить хвалебные слова в адрес ПТИМ
- В данном случае B = (E + ωR1)(E + ωR2)
[править] Реализация ПТИМ
Обозначим Wn + 1 = (E + ωR2)((xn + 1 − xn)/τ)
Невязка: rn = f − Axn
Тогда мы можем переписать ПТИМ следующим образом:
(E + ωR1)Wn + 1 = rn (6)
Введём вектор vn + 1 = ((xn + 1 − xn)/τ)
Тогда (E + ωR1)vn + 1 = Wn + 1 (7)
xn + 1 = xn + τvn + 1 (8)
[править] Параграф 6. Теоремы о сходимости итерационных методов
- Ax = f (1)
- |A| ≠ 0, (m × m)
По-прежнему решаем систему (1) итерационными методами:
- B (xn + 1 − xn)/τ + Axn = f (2)
- τn + 1 > 0
- n ∈ ℕ ∪ {0}
- x0 задано
- ∃A−1, B−1
Введём m-мерное пространство :
- ∀ x ∈ H
- dim H = m
- x = (x1, x2, ..., xm)
- ∀ x, y ∈ H (x, y) = ∑i = 1mxiyi
- ||x|| = (x, x)1/2 = (∑i = 1m xi2)1/2
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |