Релаксационный метод решения систем линейных уравнений

Формируя матрицу B различным образом и задавая различные значения итерационного параметра, можно получать одношаговые итерационные методы самого разного вида. В зависимости от выбора этих параметров мы будем получать методы, которые будут обладать различной скоростью сходимости, т.е. заданная точность будет достигаться за разное число итераций.

Одним из наиболее распространенных одношаговых итерационных методов является метод верхних релаксаций^*, который имеет следующий вид

,

(1.21)

где w>0 - заданный числовой параметр. Этот параметр выбирается таким образом, чтобы на каждом шаге итерационного процесса уменьшалась величина, характеризующая близость полученного решения к искомому решению системы.

Для получения расчетных формул (1.21) перепишем в виде

,

(1.22)

или в покомпонентной записи получим

.

(1.23)

Приведем несколько  строк покомпонентной записи

,	(1.24)
,	(1.25)
	(1.26)

   и т.д.

Практика применения итерационных методов показала, что  эти методы приводят к правильному  решению для систем с матрицей А имеющей специальный вид. Приведем ряд теорем о сходимости итерационных методов. Доказательства этих теорем приводятся в книге [1].

Рассмотрим итерационные методы с  постоянным итерационным параметром, записанные в виде

.

(1.27)

 

Теорема 1.

Пусть А - симметричная положительно определенная матрица, t>0 и пусть выполнено неравенство В-0,5tА>0. Тогда итерационный метод (1.27) сходится.

Следствие 1.

Пусть А - симметричная положительно определенная матрица с диагональным преобладанием, т.е.

(1.28)

Тогда метод Якоби  сходится.

Следствие 2.

Пусть А - симметричная положительно определенная матрица. Тогда метод верхних релаксаций сходится при условии 0<w<2. В частности, метод Зейделя сходится (w=1).

Теорема 2.

Итерационный метод (1.27) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы по модулю меньше единицы.

Теорема 3.

Пусть А и В - симметричные положительно определенные матрицы, для которых справедливы неравенства , где g₁,g₂ - положительные постоянные, g₁>g₂. При итерационный метод (1.27) сходится и для погрешности справедливы оценки

, i=0,1,...,

(1.29)

где

	(1.30)
,	(1.31)
,	(1.32)
.	(1.33)

 

Следствие 1.

Если  А^Т=А>0, то для метода простой итерации

(1.34)

при

(1.35)

справедлива оценка

,

(1.36)

где

	(1.37)
	(1.38)

 

Следствие 2.

Для симметричной матрицы А и

(1.39)

справедливо равенство 

,

(1.40)

где ,. В приложениях часто встречаются задачи с плохо обусловленной матрицей  А, когда отношение велико. В этом случае число r₀ близко к единице, и метод простой итерации сходится медленно.

Оценим число итераций n₀(e), которое требуется для достижения заданной точности e в случае малых x, т.е. для получения оценки

.

(1.41)

 Из условия  получаем, что

,

(1.42)

и при малых x имеем

.

(1.43)

Заметим, что в качестве критерия сходимости итерационного  метода может использоваться невязка, которая получается при подстановке  найденного решения в систему (1.1).

 

 

Метод верхних релаксаций.

 

Среди явных одношаговых  итерационных методов наибольшее распространение получил метод верхних релаксаций (1.21). Это связано с тем, что метод верхних релаксаций содержит свободный параметр w, изменяя который можно получать различную скорость сходимости итерационного процесса.

Наиболее эффективно этот метод применяется при решении множества близких алгебраических систем линейных уравнений. На первом этапе проводится решение одной из систем с различными значениями итерационного параметра w и из анализа скорости сходимости итерационного процесса выбирается оптимальное значение этого параметра. Затем все остальные системы решаются с выбранным значением w.

Еще одно достоинство  итерационного метода верхних релаксаций состоит в том, что при его  реализации на ЭВМ алгоритм вычислений имеет простой вид и позволяет использовать всего один массив для неизвестного вектора.

Основная вычислительная формула имеет вид

(1.44)

В выражение (1.44) и входят одинаковым образом, следовательно, при вычислениях они могут записываться в один и тот же массив. При реализации метода верхних релаксаций используется следующая форма записи алгоритма вычислений 

.

(1.45)

Действительно, при последовательном нахождении элемента (i+1 итерации) на каждом шаге будут использоваться найденные ранее значения, которые при k<j соответствуют i +1 итерации, а при k>j - i итерации.

Современная вычислительная техника позволяет проводить  исследование устойчивости и сходимости итерационного метода в зависимости от параметров задачи. Например, можно проводить исследование влияния повышения точности решения задачи на число необходимых итераций, исследование влияния начального приближения, изменения коэффициентов матрицы А и правых частей системы.

 

 

1.2. Вычислительные  погрешности метода

верхних релаксаций.

 

Один из основных вопросов применения итерационных методов связан с корректностью выбора точности метода e.

Анализируя вычислительные погрешности выражения (1.45), получим оценку наименьшего значения точности метода верхних релаксаций.

Очевидно, что искомая  погрешность вычислений будет определяться погрешностью задания коэффициентов  исходной системы и погрешностью округления.

Запишем разность двух итерационных приближений решения и оценим её минимальное значение

(1.46)

Пусть коэффициенты и f_i заданы с некоторой относительной погрешностью . Предположим, что итерационный метод сходится, и невязка

(1.47)

бывает с ростом номера итерации k, т.е. . Оценка абсолютной погрешности правой части выражения (10) может быть представлена в следующем виде

,

(1.48)

здесь .- модуль минимального значения диагонального элемента .Отсюда следует, что задаваемая погрешность метода .

 

 

Метод релаксации - итерационный метод решения систем линейных алгебраических уравнений.

Система линейных уравнений

приводится к виду

где ,

Находятся невязки  :

Выбирается начальное  приближение  . На каждом шаге необходимо обратить в ноль максимальную невязку: 

.

Ответ находится по формуле:  .

 

2. ПРАКТИЧЕСКА ЧАСТЬ.

1. РАЗБОР МЕТОДА РЕЛАКСАЦИЙ В СИСТЕМАХ ЛИНЕЙНЫХ УРАВНЕНИЙ НА ПРИМЕРЕ.

 

ТЕСТОВЫЙ  ПРИМЕР № 1: решить методом релаксаций данную систему

(2.1)

Вычисления производить  с точностью до двух знаков после  запятой.

РЕШЕНИЕ: Приводим систему(4) к виду, удобному для решения методом  релаксации

(2.2)

Задаем начальные приближения  корней нулевыми значениями

(2.3)

Находим значения невязок

Далее, решаем

    

Результаты подставляем  в таблицу №1

	0	0,60	0	0,70	0	0,80
		0,16		0,16	0,80	-0,80
		0,76		0,86		0
		0,17	0,86	-0,86		0,09
		0,93		0		0,09
	0,93	-0,93		0,09		0,09
		0		0,09	0,18	0,18
		0,04		0,04		-0,18
		0,04	0,13	0,13		0
		0,03		-0,13		0,01
	0,07	0,07		0		0,01
		-0,07		0,01		0,01
		0		0,01	0,02	0,02
		0		0		-0,02
		0
		0	0,01	0,01		0
		0		-0,01		0
		0		0		0
	1,00		1,00		1,00