- •Численное решение линейных алгебраических систем (слау)
- •Прямые методы решения слау.
- •Формулы Крамера
- •Метод Гаусса.
- •Системы с диагональным преобладанием.
- •Системы с трехдиагональной матрицей. Метод прогонки.
- •Обусловленность слау.
- •Норма матрицы.
- •Корректность решения слау.
- •Число обусловленности матрицы.
- •Оценка числа обусловленности.
- •Итерационные методы.
- •Построение итерационных последовательностей.
- •Проблема сходимости итерационного процесса.
- •Достаточные условия сходимости итерационного процесса.
- •Метод простой итерации.
- •Неявные итерационные методы. Метод Зейделя.
- •Метод верхней релаксации
Неявные итерационные методы. Метод Зейделя.
Вернемся к общей записи итерационного стационарного процесса в канонической форме .
Рассмотрим произвольную квадратную матрицу:
.
Разложим её на сумму трех матриц
,
где - диагональная часть матрицы , которая содержит элементы, стоящие на главной диагонали:
,
- нижняя треугольная матрица
,
- верхняя треугольная матрица.
.
В классическом методе Зейделя, записанном в канонической форме, полагают
В результате формула принимает вид:
,
или
.
Перейдем от векторной формы записи рекуррентной формулы к построчной:
Уравнения позволяют последовательно рассчитать компоненты вектора - ой итерации подобно тому, как это делалось во время обратного хода в методе Гаусса:
,.
Формула предполагает, что ,. Если матрицаудовлетворяет условиям теоремы Самарского :, то, согласно неравенству , все ее диагональные элементы должны быть строго положительными и, тем самым, не могут обращаться в ноль.
Алгоритм в методе Зейделя прост и удобен для вычислений. Он не требует никаких действий с матрицей . Ранее вычисленные на текущей итерации компонентысразу же участвуют в расчетах наряду с компонентамии, таким образом, не требуют дополнительного резерва памяти, что существенно при решении больших систем.
Сходимость метода Зейделя в случае, когда матрица удовлетворяет условию теоремы Самарского, т.е. является самосопряженной и положительно определенной, будет доказана в следующем разделе. К этому утверждению добавим без доказательства еще один результат: метод Зейделя сходится для любой системы , в которой матрицаобладает свойством диагонального преобладания.
Задача 3.
Рассмотреть систему (см. задачу 2) и построить для нее приближенное решение с помощью метода Зейделя.
В рассматриваемом случае рекуррентные формулы для построения -ой итерации по-ой итерации принимают вид:
Принимая, как и при решении задачи 2, за начальное приближение нулевой вектор, подсчитаем по формулам несколько первых итераций, сопровождая этот процесс подсчетом невязки:
, , ,
, , ,
, , .
Обсудим полученные результаты. Начнем с невязки. Ее вторая компонента все время остается равной нулю, поскольку второе уравнение системы на каждой итерации выполняется, как видно из , точно. Первые компоненты невязки и норма убывают по закону геометрической прогрессии с знаменателем , т.е. гораздо быстрее, чем в методе простой итерации. Хорошая сходимость процесса видна также из прямого сравнения членов итерационной последовательностис точным решением системы.
Метод верхней релаксации
Модифицируем метод Зейделя. С этой целью введем параметр и запишем рекуррентное соотношение в виде
.
В данном случае
, .
При мы возвращаемся к методу Зейделя.
Соотношению можно придать вид
.
Такая форма записи показывает, что параметр влияет на диагональ матрицы.
Для построения алгоритма вычисления очередной итерации нужно разделить в левой части рекуррентной формулы члены, содержащие и, и придать ей форму, аналогичную :
.
Если перейти от векторной записи к записи типа в виде отдельных уравнений, то можно получить для компонент очередной итерации формулы, структурно похожие на :
,.
Исследуем условия сходимости метода верхней релаксации при дополнительном предположении, что матрица удовлетворяет условиям теоремы Самарского . Самосопряженность матрицыозначает, что,. Отсюда следует
.
Составим для рассматриваемого случая матрицу . Согласно
.
Запишем условие ее положительной определенности
.
Второе слагаемое в выражении не дает вклада в квадратичную форму в силу соотношения .
Матрица является, по предположению, положительно определенной. Следовательно, все ее диагональные элементы строго положительны:,. Это означает положительную определенность матрицы :. В результате знак выражения определяется знаком первого множителя, так что достаточное условие для сходимости итерационной последовательности метода верхней релаксации принимает вид:
Метод Зейделя, соответствующий случаю , удовлетворяет этому условию.
Можно поставить вопрос об оптимальном выборе параметра , при котором метод сходится быстрее всего. Теоретическое исследование, на котором мы не будем останавливаться, показывает, что такое значение существует и может быть выражено через наибольшее и наименьшее собственные значение матрицы. Однако на практике его приходится подбирать экспериментально методом проб и ошибок, поскольку найтиис достаточной точностью удается в редких случаях.
Задача 4
Построить приближенное решение системы методом верхней релаксации, полагая .
Выпишем для рассматриваемого случая матрицы и, определяющие итерационный процесс:
,.
С их помощью рекуррентное соотношение , записанное покомпонентно, принимает вид:
Выражая из первого соотношения , из второго, получим окончательные расчетные формулы для компонент очередной итерации:
Примем, как и в предыдущих случаях, за начальное приближение нулевой вектор и сделаем три итерации. При этом для каждой из них подсчитаем невязку , позволяющую следить за сходимостью процесса
, , ,
, , ,
, , .
Поведение невязок, а также сравнение членов итерационной последовательности с точным решением системыпоказывают сходимость процесса, более быструю, чем в методе Зейделя. Выбранное значение параметраоказалось близким к оптимальному.