Математика Лекции и примеры решения задач Физический смысл дифференциала. Производная сложной функции Раскрытие неопределенностей Ряды Фурье Преобразование Фурье Двойной интеграл Векторная алгебра

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

Запишем исходную систему (3.4) в следующем виде:

  

 


 (3.13)или сокращенно

  (3.14)

где i= l,2,...n.

Правая часть (3.14) определяет отображение F

  (3.15)

   


преобразующее точку   n-мернего векторного пространства в точку того же пространства. Используя систему (3.4) и выбрав начальную точку

 можно построить итерационную последовательность точек n-мерного пространства (аналогично методу простой итерации для скалярного уравнения x = f(x));

 (3.16)

Оказывается, что при определенных условиях последовательность (3.16) сходится и ее предел является решением системы (3.13). Предваряя обсуж­дение данных условий, напомним необходимые сведения из математическо­го анализа.

Определение 3.4. Функцию (x,y), определяющую расстояние между точками x и у множества X, называют метрикой, если выполнены следующие условия:

1.. (x,y) ≥0.

(x,y) = 0 тогда и только тогда, когда x = у.

(x,y) =(y.x).

(x,z)≤ (x,y)+ (y,z).

Определение 3.5. Множество с введенной в нем метрикой  становится метрическим пространством.

Определение 3.6. Последовательность точек метрического пространства называется фундаментальной, если для любого ε>0 существует такое число Ν(ε), что для всех m, n > N выполняется неравенство (хт,х„)<ε

Определение 3.7. Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Пусть F — отображение, действующее в метрическом пространстве E с метрикой , x и у — точки пространства E, a Fx, Fy — образы этих точек.

Определение 3.8. Отображение F пространства E в себя называется сжимающим отображением, если существует такое число (0, 1), что для любых двух точек x, у выполняется неравенство

(Fx,Fy)≤α∙(x,y). (3.17)

Определение 3.9. Точка x называется неподвижной точкой отображения F, если Fx = x.

Аналогично одномерному случаю можно доказать теорему о достаточном условии сходимости итерационного процесса в n-мерном пространстве. (Доказательство теоремы приводится практически во всех учебниках, по­священных численным, методам, например,[1].)

Теорема. 3.1. Если F- сжимающее отображение, определенное в полном метрическом пространстве, то существует единственная неподвижная точка x, такая что x = Fx. При этом итерационная последовательность, построенная для отображения F с любым начальным членом x(0), сходится к x.

B ходе доказательства данной теоремы показывается, что

 (3.18)

Приняв k-oe приближение за нулевое, из (3.18) получаем полезное для приложений неравенство:

  (3.19)

Рассмотрим условия, при которых отображение (3.15) будет сжимающим. Как следует из определения (3.17), решение данного вопроса зависит от способа метризации данного пространства. Обычно при решении систем линейных уравнений используют одну из следующих метрик:

   (3.20)

  (3.21)

  (3.22)

Для того чтобы отображение F, заданное в метрическом пространстве уравнениями (3.15), было сжимающим, достаточно выполнения одного из следующих условий:

1. B пространстве с метрикой р1:


2. В пространстве с метрикой р2:

3. B пространстве с метрикой р3:

  < 1. (3.25)

Для установления момента прекращения итераций при достижении заданной точности может быть использована, например, формула, следующая из (3.19):

  (3.26)

Алгоритм решения системы методом итераций реализуется следующим образом:

Приведите систему (3.4) к виду с преобладающими диагональными коэффициентами.

Разделите каждое уравнение на соответствующий диагональный коэффициент.

3.. Проверьте выполнение условий (3.23) - (3.25).

Выберите метрику, для которой выполняется условие сходимости итерационного процесса.

Реализуйте итерационный процесс (обычно за начальное приближение берется столбец свободных членов).

Пример 3.1 Преобразование системы уравнений к виду пригодному для итерационного процесса.

   


1. Возьмите первым уравнением второе, третьим первое, а вторым - сумму первого и третьего уравнений:

Подпись:

2. Разделите каждое уравнение на диагональный коэффициент и выразите из каждого уравнения диагональное неизвестное:

   


3.5. Метод Зейделя

Подпись: 				 							(3.27)Напомним, что при решении системы линейных уравнений вычислительные формулы имеют вид:

где i = 1,2,...n.

Из (3.27) видно, что в методе простой итерации для получения нового значения вектора решений на

(i + 1)-ом шаге используются значения переменных, полученные на предыдущем шаге.

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении, значения переменной yi, учитываются уже найденные значения

 


 (3.28)

Достаточные условия сходимости итерационного процесса (3.23) - (3.25) также являются достаточным условиями сходимости метода Зейделя.

Существует возможность автоматического преобразования исходной системы к виду, обеспечивающему сходимость итерационного процесса метода Зейделя. Для этого умножим левую и правую части системы (3.2) на транспонированную матрицу системы АT, получим равносильную систему

C·X=D, (3.29)

где C =ATA, D=ATb

Система (3.29) называется нормальной системой уравнений. Нормальные системы уравнений обладают рядом свойств, среди которых можно выделить следующие:

матрица C коэффициентов при неизвестных нормальной системы является симметрической (т.е.

все элементы, стоящие на главной диагонали матрицы C, положительны
(т. е. >0, ).

Последнее свойство дает возможность "автоматически" приводить нормальную систему (3.29) к виду, пригодному для итерационного процесса Зейделя:

Подпись: 				 					(3.30)

Подпись: 			 						(3.31)где

Подпись: 				 . 							(3.32)

и

Целесообразность приведения системы к нормальному виду и использования метода Зейделя вытекает из следующей теоремы:

Теорема 3.2. Итерационный процесс метода Зейделя для приведенной системы (3.30), эквивалентной нормальной системе (3.29), всегда сходится к единственному решению этой системы при любом выборе начального приближения [2].

Таким образом, решение произвольной системы линейных уравнений вида (3.1) методом Зейделя реализуется в соответствие со следующим алгоритмом:

Ввод матрицы A коэффициентов исходной системы и вектор столбца свободных членов.

Приведение системы к нормальной умножением обеих частей систем на транспонированную матрицу AT.

3. Приведение нормальной системы к виду, пригодному для итерационного процесса Зейделя(3.30), (3.31).

4.  Задание требуемой точности решения.

5. Циклическое выполнение итерационного процесса до достижения требуемой точности.


Практикум по теме «Тройной интеграл»