Материал: Спецглавы высшей математики. численные методы. Пантелеев И.Н

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

n

max i j 1. (III.24)

1 j n i 1

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

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

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

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

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

3.Проверьте выполнение условий (III.23)—(III.25).

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

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

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

2.34x1 4.21x2 11.61x3 14.41

8.04x1 5.22x2 0.27x3 6.44

3.92x1 7.99x2 8.37x3 55.56

49

1.Возьмите первым уравнением второе, третьим первое, а вторым

—сумму первого и третьего уравнений:

8.04x1 5.22x2 0.27x3 6.44

6.26x1 12.20x2 3.24x3 69.97

2.34x1 4.21x2 11.61x3 14.41

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

x1 0.6492537x2 0.033582x3 0.800995 x2 0.5131147x1 0.2655737x3 5.7352459 x3 0.2015503x1 0.36261864x2 1.2411714

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

1. Создайте файлы Rol.m, Ro2.m, Ro3.m (листинги III.5-III.7),

содержащие описания функций, возвращающих значение расстояния между точками в соответствующем метрическом пространстве.

Листинг III.5. Файл Ro1.m Function z Ro1 x, y

z max abs x y ;

Листинг III.6. Файл Ro2.m Function z Ro2 x, y

z sum abs x y ;

Листинг III.7. Файл Ro3.m

50

Function z Ro3 x, y

z norm x y ;

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

Листинг III.8. Файл Check.m Function z Check A alpha1 sum ads A ,2 ;

z 1 max alpha1 ; alpha2 sum ads A ,1 ; z 2 max alpha2 ; alpha3 A.^2;

z 3 sum sum alpha3 ^0.5;

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

Листинг III.9. Файл LS_Iter.m

Function z LS _ Iter A,b, Ro, alpha,eps

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

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

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

%системы уравнений

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

%значение метрики

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

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

51

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

%решения.

delta esp * 1 aipha / alpha; N size A,1 ;

x0 zeroz 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.Задайте матрицу системы, приведенной к виду, пригодному для метода простой итерации:

» А= [0,-0.6492537,-0.033582,-0.5131147, 0,-0.2655737;0.2015503,-0.3626184,0]

А =

0 -0.6493 -0.0336

0.5131 0 -0.2656

0.2016 -0.3626 0

5. Задайте вектор-столбец свободных членов: » b= [-0.800995;-5.7352459,--1.2411714]

b =

-0.8010 -5.7352 -1.2412

6. Вычислите значения коэффициентов а для каждого метрического пространства:

52

» alpha==Check (А) alpha=

0.7787 1.0119 0.9636

7.Найдите решения системы линейных уравнений:

LS _ Iter A,b, 'Ro1' , ans 1 ,10 ^ 6

ans

2.29304.8155 0.9672

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

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

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

Из (III.27) видно, что в методе простой итерации для получения нового значения вектора решений на i 1 -ом шаге ис-

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

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

53

...........................................

n 1

yn n j y j n n xn n . j 1

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

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

ти системы (III.2) на транспонированную матрицу системы AT , по-

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

Матрица C коэффициентов при неизвестных нормальной системы является симметричной (т.е. aij a ji ,i, j 1,2, , n )

Все элементы, стоящие на главной диагонали матрицы С, положительны: (т.е aij 0,i 1,2, , n ).

Последнее свойство дает возможность “автоматически” приводить нормальную систему (III.29) к виду, пригодному для

54

итерационного процесса Зейделя:

xi aij x j j , i 1,2, , n ,

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

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

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

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

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

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

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

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

Для реализации метода Зейделя в пакете MATLAB необходи-

мо:

55

1.Создать файл Zeidel.m (листингIII.10), содержащий описание функции, выполняющей последовательно: а) приведение системы к нормальному виду; б) приведение нормальной системы к виду, пригодному для итерационного процесса Зейделя; в) реализацию итерационного процесса Зейделя.

Листинг III.10. Файл Zeidel.m function [zl,z2]=Zeidel(A,b,eps) N=size(A,l)

%приведениесистемыкнормальномувиду С=А"А;

D=A'*b,

%приведениесистемыквиду, пригодномудляитерационного

%процессаЗейделя

for i=l:N

D1 i D i / C i,i ; end;

D1 D1' ; транспонированиематрицы. d1 D1;

for _ i 1: N for _ j 1: N if _ i j C1 i, j 0; else

C1 i, j C i, j / C i,i ; end;

end; end;

% решениесистемылинейныхуравненийметодомЗейделя

56

R1 d1;

While _ Flag 0 for _ i 1: N

v C1 i,1: N ; % выделение i-ой строки матрицы

a dot v' , d1 ; % вычисление скалярного произведения d1 i a D1 i ;

end;

R2 d1;

S max ads R2 R1 ; if _ S eps

z1 d1; z2 s; return end;

R1 R2; end;

2.Задать значение коэффициентов при неизвестных исходной системы линейных уравнений и столбец исходных членов.

>>A 1,2,3,4,5;10,9,8,7,6;5,9,11,12,13;20,1,3,17,14;12,10,4,16,15

>>b 10;20;30;40;50

3.Вычислить решение системы линейных уравнений используя функцию zeidel( ).

zeidel A,b,10^ 6

ans

0.0972

1.4325

57

-1.3533 1.6564 0.8947

4.Проверить полученное решение:

A* ans

ans

10,0013

20,0003

29,9995

39,9999

50,0000

3.6. Решение систем линейных уравнений средствами пакета MATLAB

Для решения систем линейных уравнений и связанных с ними матричных операций применяются операторы: сложения (+), вычитания (-), умножения (*), деления (/), деления слева (\), возведение в степень (^), транспонирование (‘), действие которых определяется правилами линейной алгебры.

Для решения системы линейных уравнений вида

Ax b,

где А — матрица коэффициентов при неизвестных, х ~ век- тор-столбец неизвестных, b — вектор-столбец свободных членов, в пакете MATLAB достаточно выполнить следующую команду:

A^ 1*b

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