Основные итерационные методы
3. ОСНОВНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ
3.1. Введение
При решении СЛАУ
(3.1)
с невырожденной матрицей задают начальное приближение и в дальнейшем определяют векторы ,,… которые при сходятся к точному решению системы (3.1) . Очевидный двухслойный стационарный итерационный процесс Ричардсона (1910) имеет вид
(3.2)
Если в (3.2) вместо приближений подставить точное решение, т.е. положить , то получим тождество. Это естественное требование к итерационным методам называется согласованностью.
Естественным обобщением процесса Ричардсона представляется метод
(3.3)
Рекомендуемые материалы
Здесь ‑ невырожденная матрица (матрица расщепления), ‑ матрица перехода (или матрица шага). Легко видеть, что метод (3.3) является согласованным: смежная система уравнений
(3.4)
при невырожденной матрице обращается в тождество при . В самом деле,
.
Зачем нужна матрица расщепления ? Она призвана ускорить сходимость итераций. Выберем . Тогда из (3.3) получим
т.е. процесс дает точное решение за одну итерацию. Правда, найти эту итерацию так же трудно, как решить исходную задачу, т.к. необходимо обращать матрицу . Поэтому при конструировании итерационных методов стараются выбирать матрицу расщепления «похожей» на матрицу исходной системы, но легко обратимой.
Если векторы представляют собой последовательность приближений, вычисленных по методу (3.3), то из свойства его согласованности следует
1. Если для некоторого , то для всех
2. Если последовательность сходится к некоторому вектору , то .
Необходимое и достаточное условие сходимости итерационного процесса (3.3) имеет вид
(3.5)
Обозначим через вектор ошибки (погрешности) метода на шаге , . Подставим это выражение в (3.3) и получим
откуда при условии согласованности следует
.
С помощью формулы (2.15) из этого равенства получаем оценку того, насколько уменьшилась норма ошибки за итераций: . Здесь , как и раньше, указывает на одну из введенных выше норм. Ясно, что чем меньше норма оператора перехода, тем скорее уменьшится ошибка и быстрее будет сходимость приближений к точному решению.
Средней скоростью сходимости итерационного метода (3.3) за шагов называется величина
(3.6)
которая зависит от вида нормы. Знак минус выбран для того, чтобы числитель был положителен при . Видим, что чем меньше , тем больше скорость сходимости . Если переписать формулу (3.6) в виде и устремить , то при получим т.н. асимптотическую скорость сходимости
, (3.7)
которая уже не зависит от вида нормы. С помощью формул (3.6), (3.7) можно оценить количество итераций, за которое погрешность уменьшается в раз. Как отмечалось выше, , поэтому из (3.6) получаем
. (3.8)
При больших из (3.8) следует приближенная формула, не зависящая от :
. (3.9)
Итерационный метод
(3.10)
является симметризуемым, если для некоторой невырожденной матрицы матрица является симметричной и положительно определенной. Такая матрица называется матрицей симметризации.
Что называют дискретным случайным вектором. Сформулируйте и докажите утверждение о виде функции распределения дискретного случайного вектора - лекция, которая пользуется популярностью у тех, кто читал эту лекцию.
Если метод (3.10) является симметризуемым, то
1. СЗ матрицы действительны;
2. ;
3. Множество СВ матрицы содержит в себе базис векторного пространства.
Заметим, что этих свойств недостаточно для сходимости метода (3.10), поскольку для этого надо чтобы , а свойство (2) гарантирует лишь .
Для метода (3.3) . Если обе матрицы симметричны и положительно определены, то в качестве матрицы симметризации можно взять . Кроме того, если представить в виде разложения , то такая матрица тоже является матрицей симметризации для .