Решение СЛАУ методом простой итерации

Пусть задана система уравнений в виде, в которой диагональные элементы a_ii ¹ 0 (i =1,2,… n). Выразим x₁ через первое уравнение системы, x₂ - через второе уравнение и т.д. В результате получим эквивалентную систему:

Обозначим , где i = 1,2, …,n; j = 1,2, … n.

Тогда систему можно записать в матричной форме как X = b’ + a’X или

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

Зададимся начальным приближением X⁽⁰⁾, например, таким:

- нулевое приближение.

Вычислим значения X⁽¹⁾ первого приближения:

- первое приближение.

Подставим значения X⁽¹⁾ в правую часть уравнения:

- второе приближение,

и т.д., т.е. любое последующее приближение вычисляют по формуле

X^(k+1) = b’ + a’X^(k) (k=0,1, …,n).

Если последовательность приближений X⁽⁰⁾, X⁽¹⁾, …, X^(k) имеет предел , то этот предел и является решением исходной системы. При заданной допустимой погрешности e за критерий окончания итерационного процесса можно принять условие .

Рассмотрим еще раз приведенную систему уравнений.

В сокращенном виде она может быть записана так:

Здесь коэффициенты a и b есть приведенные коэффициенты в системе.

Правая часть определяет отображение F преобразующее точку x=(x₁,x₂,…x_n) n -мерного векторного в точку y=(y₁,y₂,…y_n) того же пространства:

Выбрав начальное приближение можно построить итерационную последовательность точек n - мерного пространства x⁽⁰⁾,x⁽¹⁾…x⁽ⁿ⁾… (аналогично методу простой итерации для скалярного уравнения x=f(x)).

Также аналогично существованию условий сходимости для скалярного уравнения, есть условия сходимости последовательности приближений ик решению систему уравнений.

Кратко вспомним необходимые сведения из мат. анализа:

Определение 1.

Функция r(x,y) – расстояние между x и y будет метрикой, если выполняется:

Определение 2.

Множество с введенной в нем метрикой – метрическое пространство.

Определение 3.

Последовательность точек метрического пространства фундаментальная, если для любого e>0 существует N(e) такое, что для всех n,m>N выполняется r(x_n,x_m)<e.

Определение 4.

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

Пусть F –отображение,

Е – метрическое пространство,

r - метрика,

x,y – точки пространства Е,

Fx, Fy – образы этих точек.

Определение 5.

Отображение F пространства Е в себя называется сжимающим отображением, если существует такое число a, 0<a<1, что для любых двух точек x,yÎЕ выполняется неравенство:

Определение 7.

Если Fx=x, то x неподвижная точка отображения F.

Теорема.

Если F сжимающее отображение, определенное в полном метрическом пространстве, то существует единственная неподвижная точка x, такая что Fx=x. При этом итерационная последовательность, построенная для отображения F с любым начальным приближением x⁽⁰⁾, сходится к x.

Рассмотрим условия, при которых отображение для нашей приведенной системы будет сжимающим. Как следует из определения 6, решение вопроса зависит от способа метризации данного пространства.

Обычно используют одну из следующих метрик:

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

ü В пространстве с метрикой r₁ или с метрикой r₂:

ü В пространстве с метрикой r₃:

Вводя понятие нормы, можно также сформулировать условие сходимости итерационного процесса:

Итерационный процесс для системы X = B’ + А’X сходится к единственному решению при любом выборе начального приближения, если какая-нибудь из норм матрицы меньше единицы.

Рассмотрим три нормы:

1. Норма 1: - максимальная сумма модулей элементов матрицы по строкам;

2. Норма 2: - максимальная сумма модулей элементов матрицы по столбцам;

3. Норма 3: - корень квадратный из суммы квадратов модулей всех элементов матрицы.

В MathCAD’е реализованы встроенные функции, вычисляющие нормы 1, 2 и 3 соответственно: normi(A), norm1(A), norme(A), где A - матрица, для которой вычисляется норма.

Дата добавления: 2014-01-11