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

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

(3.13)

или сокращенно

(3.14)

где .

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

, (3.15)

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

(3.16)

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

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

1) ³ 0,

2) = 0 тогда и только тогда, когда x = y,

3) =,

4) .

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

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

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

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

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

. (3.17)

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

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

Теорема. 3.1. Если F - сжимающее отображение, определенное в

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

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

. (3.18)

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

. (3.19)

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

, (3.20)

, (3.21)

. (3.22)

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

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

, (3.23)

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

, (3.24)

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

. (3.25)

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

. (3.26)

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

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

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

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

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

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

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

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

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

На этом приведение уравнения к виду, пригодному для использования итерационного процесса, завершается.

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

1. Создать файлы Ro1.m, Ro2.m, Ro3.m, содержащие описания функций, возвращающих значение расстояния между точками в соответствующем метрическом пространстве.

% листинг файла Ro1.m

function z=Ro1(x,y)

z=max(abs(x-y));

% листинг файла Ro2.m

function z=Ro2(x,y)

z=sum(abs(x-y));

% листинг файла Ro3.m

function z=Ro3(x,y)

z=norm(x-y);

2. Создать файл Check.m, содержащий описание функции, возвращающей значение коэффициентов a для каждого типа метрик

% листинг файла Check.m

function z=Check(A)

alpha1=sum(abs(A),2);

z(1)=max(alpha1);

alpha2=sum(abs(A),1);

z(2)=max(alpha2);

alpha3=A.^2;

z(3)=sum(sum(alpha3))^0.5;

3. Создать файл LS_Iter.m, содержащий описание функции, возвращающей решение системы линейных уравнений методом простой итерации

% листинг файла LS_Iter.m

function z=LS_Iter(A,b,Ro,alpha,eps)

% аргументы функции

% A - матрица приведенной системы уравнений

% b - вектор столбец свободных членов приведенной системы уравнений

% Ro - имя файла, содержащего функцию, возвращающей значение метрики

% alpha - коэффициент сжимающего отображения в пространстве с

% выбранной метрикой

% eps - переменная, определяющая точность численного решения

delta=eps*(1-alpha)/alpha;

N=size(A,1);

x0=zeros(N,1);

x1=A*x0+b;

Delta=feval(Ro,x0,x1);

while Delta>delta

x0=x1;

x1=A*x0+b;

Delta=feval(Ro,x0,x1);

end;

z=x1;

4. Задать матрицу системы, приведенной к виду, пригодному для метода простой итерации

>>A=[0,-0.6492537,-0.033582;0.5131147,0,-0.2655737;0.2015503,-0.3626184,0]

A =

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