CM_FAQ2 (Шпоры)
Описание файла
Файл "CM_FAQ2" внутри архива находится в папке "Шпоры". Документ из архива "Шпоры", который расположен в категории "". Всё это находится в предмете "численные методы" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "CM_FAQ2"
Текст из документа "CM_FAQ2"
-
FAQ: Численные Методы, часть II
-
Системы линейных алгебраических уравнений: итерационные методы
-
4. Примеры и канонический вид итерационных методов решения СЛАУ.
См. [2], стр. 175.
Итерационный метод называется одношаговым, если на каждой итерации требуется результат лишь одной предыдущей итерации. Каноническая форма:
. (4.1)
На каждой итерации в общем случае решается уравнение относительно хn+1. Если B=E, метод назывется явным:
. (4.2)
Если B,t - постоянные величины, метод называется стационарным.
Метод простой итерации. Для проведения итераций система приводится к виду x=Bx+c. Выбирается начальное приближение x0, а далее проводятся вычисления по следующей схеме: xn+1=Bxn+c.
Представим матрицу А в виде A=A1+D+A2, где D=diag[a11,....,amm] - диагональ матрицы А, A1 и A2 - соответственно нижнетреугольная и верхнетреугольная подматрицы.
Простейший вариант методо простой итерации - метод Якоби. В этом методе производится исключение переменной xi из i-го уравнения исходной системы. Метод Якоби имеет следующую каноническую форму:
D(xn+1 - xn) + Axn = f. (4.3)
Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного (k+1)-ого приближения к i-ой переменной используют уже найденные (k+1)-ые приближения к переменным 1,...,i-1.
Каноническая форма метода Зейделя:
(D+A1)(xn+1 - xn) + Axn = f, (4.4)
Пусть B1 и B2 - соотвественно нижняя и верхняя треугольные части матрицы B. Тогда расчетные формулы метода Зейделя можно записать в следующем виде: xn+1=B1xn+1+B2xn +c.
Обобщением метода Зейделя является метод верхней релаксации:
, (4.5)
где w - заданный числовой параметр. При w=1 - это метод Зейделя.
-
5. Теорема о сходимости двухслойных итерационных методов.
Погрешность метода (4.2) на n-й итерации характеризуется вектором невязки zn=xn-x, который, очевидно, удовлетворяет однородному уравнению
. (5.1)
Теорема 5.1 (достаточное условие сходимости). Пусть А - симметрическая положительно определенная матрица и - положительно определенная матрица. Тогда при любом выборе начального приближения итерационная последовательность, определенная канонической формой (4.1), сходится к решению системы Ах=b.
-
6. Достаточные условия сходимости методов Якоби, Зейделя, релаксации.
См. [8, стр. 86].
Будем говорить, что А - матрица с диагональным преобладанием, если каждый диагональный элемент больше суммы абсолютных величин остальных элементов в соответствующей строке:
(6.1)
Применим теорему 5.1 к конкретным итерационным методам:
Утверждение 6.1. Пусть А - симметричная положительная матрица с диагональным преобладанием. Тогда метод Якоби (4.3) сходится.
Утверждение 6.2. Пусть А - симметричная положительная матрица. Тогда метод верхней релаксации (4.5) сходится при 0<w<2. В часности, метод Зейделя (w=1) сходится.
-
7. Теорема об оценке скорости сходимости итерационных методов и следствия из этой теоремы.
См. [8, стр. 95].
Если для погрешности итерационного метода верна оценка
||zn|| Ј qn ||zo||, (7.1)
то говорят, что метод сходится со скоростью геометрической прогрессии со знаменателем q.
Будем рассматривать только стационарные итерационные методы вида
. (7.2)
Пусть для двух симметричных матриц А и В неравенство А і В означает, что (Ax,x) і (Bx,x) для любых векторов x. Для симметричной положительно определенной матрицы D введем обозначение .
Теорема 7.1. Пусть А и B - симметричные положительно определенные матрицы, для которых справедливы матричные неравенства
g1B £ A £ g2B, (7.3)
где g2 > g1 > 0. При значении параметра
(7.4)
итерационный метод (7.2) сходится и для погрешности справедливы оценки
, (7.5)
, (7.6)
где
(7.7).
Утверждение 7.2 (следствие 1). Если А - симметричная положительно определенная матрица, а g1 и g2 - соотвественно минимальное и максимальное собственные значения этой матрицы, то для метода простой итерации
, (7.8)
в котором параметр t выбирается по формуле (7.4), справедлива оценка
, (7.9)
где величина знаменателя r определяется из (7.7).
Утверждение 7.3 (следствие 2). Для симметричной матрицы А, минимальное и максимальное собственные значения равны соответственно g1 и g2, и параметра t, выбираемого по формуле (7.4), справедливо равенство
, (7.10)
где величина r определяется формулой (7.7).
-
8. Попеременно-треугольный итерационный метод. Реализация метода. Теорема о сходимости.
См. [8, стр. 394].
Пусть дано матричное уравнение вида
Ax = f , (8.1)
с симметричной положительно определеной матрицей А порядка m. Построим верхнетреугольную матрицу R[rij] следующим образом:
. (8.2)
Очевидно, матрицу А можно представить в виде суммы A=R+R*.
Попеременно-треугольный итерационный метод относится к неявным стационарным методам вида (7.2), где матрица B имеет следующий конкретный вид (w>0 - числовой параметр) :
B = (E+wR*) (E+wR). (8.3)
Вычисления по этому методу сводятся к решению на каждой итерации двух систем с треугольными матрицами.
-
9. Теорема об оценке скорости сходимости попеременно-треугольного итерационного метода.
См. [8, стр. 397]
Теорема 9.1. В обозначениях пункта 8, предположим, что существуют положительные постоянные d и D, при которых выполнены неравенства
A ³ dE, 4RR* £ DA. (9.1)
Введем также обозначения
. (9.2)
Если параметры w и t попеременно-треугольного итерационного метода выбираются следующим образом:
, (9.3)
то этот метод сходится, причем для погрешности справедлива оценка
, (9.4)
где
. (9.5)