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

Кафедра информатики и вычислительной математики

КУРСОВАЯ РАБОТА

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

Выполнил

студент IV курса

дневного отделения

факультета МФИ

Белоусов А.А.

Проверил

преподаватель:

Голикова Е.И.

Содержани

Содержание 2

Введение 3

Метод итераций 5

Описание метода 5

Сходимость метода 8

Метод Зейделе 10

Описание метода 10

Сходимость метода. 13

Другая форма метода Зейделя 15

Практическая часть 18

Листинг №1(метод простой итерации) 18

Листинг №2(метод Зейделя) 20

Заключение 23

Список используемой литературы 24

Введение

Способы решения линейных систем уравнений разделяют в на 2 группы.

Первые, точные методы представляющие собой конечные алгорифмы для вычисления корней системы (таковыми например, являются правило Крамера, метод Гаусса, метод главных элементов, метод квадратных корней и др.).

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

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

При использовании итерационных процессов, сверх того, добавляется погрешность метода.

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

Сейчас разберем несколько определений которые будем использовать в этой работе.

Система линейных уравнений с n неизвестными (или, линейная система) в линейной алгебре — это система уравнений вида

(1)

Здесь — неизвестные, которые надо определить. — коэффициенты системы — и — свободные члены — предполагаются известными. Индексы коэффициентов () системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Система (1) называется однородной, если все её свободные члены равны нулю (), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) — совокупность n чисел , таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества.

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у нее нет ни одного решения.

Совместная система вида (1) может иметь одно или более решений.

Решения и совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

= соответственно

Совместная система вида (1) называется определенной, если она имеет единственное решение; если же у нее есть хотя бы два различных решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой.

Метод итераций

Описание метода

При большем числе неизвестных Линейная система (ЛС впоследствии) схема метода Гаусса, дающая точное приближение, становиться весьма сложной.

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

Пусть дана ЛС

Введя в рассмотрение матрицы

(1)

Систему 1 коротко можно записать в виде матричного уравнения

(1’)

Предполагая, что диагональные коэффициенты

Разрешим первое уравнение первое уравнение системы (1) относительно , второе относительно и т. д. Тогда получим эквивалентную систему

(2)

где при

и при

введя матрицы

и

Систему (2) можем записать в матричной форме

(2’)

Систему (2) будем решать методом последовательных приближений. За нулевое приближение принимаем, например столбец свободных членов т.е.

Далее строим матрицы столбцы

Первое приближение

Второе приближение

Вообще говоря, любое (k+1)-е приближение вычисляется по формуле:

(3)

Если последовательность приближений

Имеет придел

То этот придел является решением системы (2). В самом деле, переходя к приделу в равенстве (3) будем иметь:

или

т.е. предельный вектор x является решением системы (2’), а следовательно, и системы (1).

Напишем формулы приближений в развернутом виде

Заметим, что иногда систему (1) выгоднее приводить к виду (2), так чтобы коэффициенты не были равны нулю.

Вообще имея систему:

можно положить

где . Тогда данная система эквивалентна приведенной системе

где

при

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

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

Пример:

Решить систему

методом итераций

Здесь диагональные элементы, >> чем недиагональные

Приведем эту систему к нормальному вид

В матричной форме можно записать:

За нулевое приближение принимаем свободное приближение

K
0	2	3	5
1	1.92	3.19	5.04
2	1.9094	3.1944	5.0446
3	1.90923	3.1945	5.04485

Замечание: при применении метода простой итерации нет необходимости брать за нулевое приближение столбец свободных членов. Как будет доказано ниже, сходимость процесса зависит от свойств матрицы .

Сходимость метода

Теперь докажем сходимость процесса итерации, для этого надо доказать сходимость .

Выясним условия сходимости последовательности

Т е о р е м а 1. Для того чтобы последовательность приближений сходилась достаточно, чтобы все собственные значения матрицы B были по модулю меньше единицы:

. (3)

Д о к а з а т е л ь с т в о. Найдем значение любого выражения через

(4)

Отсюда и из условия теоремы с учетом свойств опеделителя матрицы сразу следует что при и

,

Откуда .

Что касается необходимости условия , то ответ на вопрос дает

Т е о р е м а 2. Если требовать, чтобы последовательность сходилась к при любом начальном приближении , то условие (3) является необходимым

Д о к а з а т е л ь с т в о. Пусть для всякого начального приближения будет . Имеем

.

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

Применение теорем 1 и 2 требует знания границ собственных значений матрицы В; нахождение их часто является нелегкой задачей. Укажем более простые, но только достаточные признаки сходимости.

Т е о р е м а 3. Для того чтобы последовательность приближений в методе простой итерации сходилась, достаточно, чтобы какая-либо норма матрицы В была меньше единицы.

Доказательство. Если , то все собственные значения матрицы В по модулю меньше единицы, и по теореме 1 последовательность сходится.

Непосредственным следствием теоремы (3) и равенств определяющих кубическую и октаэдрическую норму матрицы, является

Т е о р е м а 4. Последовательность в методе простой итерации сходится, если для матрицы В выполняется одно из неравенств:

1. 

2. 

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

Т е о р е м а 5. Если какая-либо норма матрицы В, согласованная с рассматриваемой нормой вектора , меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации:

. (5)

Д о к а з а т е л ь с т в о. Для выше дано выражение (4), и так как, то

Поэтому

(6)

и, стало быть,

.

Часто за принимают вектор b. В этом случае оценка (5) немного упростится; подставляя =b в (6) получим

.

Метод Зейделе

Описание метода

Метод Зейделя применяют в двух видоизменениях. Рассмотрим сначала случай канонической формы системы для метода итерации

(1)

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

(2)

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

О принципах выбора порядка уравнений будет говориться ниже, а сейчас предположим, что для перехода от приближения к следующему —нами выбран какой-то порядок привлечения уравнений для подстановок. Изменяя, если необходимо, нумерацию уравнений и неизвестных, можно считать, что уравнения для подстановок берутся в порядке роста их номеров. Для каждого шага от приближения k до k+1 порядок привлечения уравнений может быть своим, и должны быть выполнены свои изменения нумерации и перестановки, что влечет за собой свое изменение матрицы В системы и свободного вектора b. Чтобы отметить это, обозначим матрицу В для рассматриваемого, шага и свободный вектор . В этих обозначениях итерация в методе Зейделя выполняется в следующем порядке:

(3)

После нахождения вектора устанавливают поря­док подстановок в уравнения значений (i = 1, ..., п) и переходят к вычислению вектора и т. д.

Приведем теперь пример принципа, на основании которого можно устанавливать порядок привлечения уравнений для подстановок (i = 1,...,п). Можно пытаться в первую очередь улучшить ту составляющую решения, которая найдена наименее точно, чтобы при нахождении всех других составляющих употреблять улучшенное ее значение. О точности можно было бы судить по вектору погрешности, , но так как вектор точного решения неизвестен, то в вычисле­ниях заменяют другим вектором, по которому можно, хотя бы неполно, судить о погрешности . Чаще всего для этой цели пользуются вектором поправки на по­следнем шаге , где . Ве­личины поправок составляющих нумеруют в порядке убывания их абсолютных значений, и в том же порядке вычисляют составляющие следующего приближения : сначала ту составляющую, которая отвечает наибольшей по модулю поправке, и т. д.

Пример:

Приведем эту систему к удобному для итерации

В качестве нулевых приближений корней возьмем

Применяя последовательно процесс решения методом Зейделя

Результаты вычисления корней приведены в Таблице ниже с точностью до 4-х знаков

i
0	1.2000	0.0000	0.0000
1	1.2000	1.0600	0.9480
2	0.9992	1.0054	0.9991
3	0.9996	1.0001	1.0001
4	1.0000	1.0000	1.0000
5	1.0000	1.0000	1.0000

Точные значения: ; ;

Сходимость метода.

Остановимся более подробно на стационарном ме­тоде Зейделя; когда при итерациях порядок уравнений сохраняется, матрица В будет одинаковой на всех ша­гах и составляющие следующего приближения нахо­дятся при всяком k по правилу (3).

Разложим матрицу В на сумму двух матриц Н и F, где

.

Тогда равенства (2) можно записать в форме матрич­ного равенства

откуда следует, что, а так как определитель матрицы

равен единице и она имеет обратную, то равенство (3) равносильно

. (4)

Поэтому стационарный метод Зейделя равносилен ме­тоду простой итерации, примененному к системе

.

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

Этот признак может быть высказан в форме, не тре­бующей обращения Е — Н. Если воспользоваться тем, что , то можно написать систему равенств

Поэтому верна

Теорема 1. Для того чтобы стационарный метод Зейделя сходился при любом начальном векторе при­ближения необходимо и достаточно, чтобы все корни уравнения

были по модулю меньше единицы.

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

Л е м м а 1. Если в матрице диагональные элементы доминируют по строкам или по столбцам, т. е. если

или

то определитель матрицы А отличен от нуля.

Д о к а з а т е л ь с т в о. Для определенности предпо­ложим, что имеет место доминирование по строкам. Достаточно показать, что однородная система

Ах = 0 (6)

имеет только нулевое решение.

Допустим противоположное и будем считать, что си­стема имеет ненулевое решение , Среди составляющих решения выберем наибольшую по модулю;

Положим и оценим снизу левую часть уравнения номера i системы.(6):

гак как и по условию

леммы. Этот результат противоречит тому, что есть решение системы, и доказывает неверность допущения.

Т е о р е м а 2. Для сходимости стационарного метода Зейделя (4) достаточно, чтобы выполнялось какое-либо одно из условий:

(7)

Или

(8)

Д о к а з а т е л ь с т в о. Достаточность первого и вто­рого условий проверяется аналогично, и можно ограни­читься рассмотрением только первого условия.

Нужно показать, что при выполнении условия (7) нее корни уравнения (5) будут по модулю меньше еди­ницы. Будем считать, что , и рассмотрим сумму модулей недиагональных элементов строки номера i матрицы:

Таким образом, диагональные элементы матрицы доминируют по строкам, и на основании леммы 1 определитель этой матрицы отличен от нуля, а значение , для которого , не может быть корнем уравнения (6). Корни этого уравнения все по мо­дулю меньше единицы, и по теореме 1 стационарный метод Зейделя сходится.

Другая форма метода Зейделя

В ней требуется предварительное преобразование системы Ах =b к виду, в котором все диагональные коэффициенты от­личны от нуля. Такое приведение стремятся выполнить, если это возможно, так, чтобы диагональные коэффи­циенты были наибольшими или даже доминирующими в соответствующих уравнениях.

Мы ограничимся описанием только стационарного процесса. Пусть взято какое-либо исходное приближение к решению системы. Приближе­ние номера k+ 1 находят по приближению номера k с помощью системы соотношений

(9)

Если разложить матрицу А на сумму двух матриц

и

то равенства (9) можно записать в матричном виде

Bx^k+l + Cx^k=b,

или

Поэтому ясно, что метод Зейделя в форме (9) рав­носилен методу простых итераций, примененному к си­стеме в каноническом виде:

Для сходимости метода при любом векторе b необ­ходимо и достаточно, как следует из теорем 2 и 3,

чтобы все собственные значения матрицы, т. е. все корни уравнения , были по мо­дулю меньше единицы. Это условие можно упростить и высказать в форме, не требующей обращения матрицы В. В самом деле,

,

и можно формулировать следующую теорему.

Т е о р е м а 3. Для того чтобы процесс Зейделя, определяемый равенствами (9), сходился при любых свободных членах необходимо и до­статочно, чтобы корни уравнения

все были меньше единицы по модулю.

Практическая часть

Здесь рассматриваются алгоритмы описанных выше методов с описанием.

Все программы написаны в среде Turbo Pascal.

Листинг №1(метод простой итерации)

program iter;

var A: array [1..4,1..4] of real;

b,x,otv: array [1..4] of real;

i,j,n: byte;

eps: real;

pr: boolean;

begin

write('razmer matrix n=');

readln(n);

for i:=1 to n do {Ввод данных}

for j:=1 to n do

begin

write('A[',i,',',j,']=');

readln(A[i,j]);

end;

for i:=1 to n do

if a[i,i]=0 then begin

writeln('oshibka vvoda'); {проверка чтобы на диагонали не было

exit; нулевых коэффициэнтов}

end;

for i:=1 to n do

begin

write('b[',i,']=');

readln(b[i]);

end;

for i:=1 to n do

begin

for j:=1 to n do

begin

if i=j then continue; {Выражаем x1,x2,x3…из системы}

a[i,j]:=-a[i,j]/a[i,i];

end;

b[i]:=b[i]/a[i,i];

a[i,i]:=0;

end;

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j]:4:2,' ');

writeln(b[i]:4:2);

end;

for i:=1 to n do

x[i]:=0;

write('tochnost='); {Вводим точность}

readln(eps);

repeat

for i:=1 to n do

begin

for j:=1 to n do

otv[i]:=otv[i]+a[i,j]*x[j]; {алгоритм решения}

otv[i]:=otv[i]+b[i];

end;

for i:=1 to n do

if abs(otv[i]-x[i])

for i:=1 to n do

begin

x[i]:=otv[i];

otv[i]:=0;

end;

until pr;

for i:=1 to n do

writeln(x[i]); {Вывод результата}

end.

Контрольный тест

Размер матрицы

4

Введите точность вычислений

0.000001

Введите расширенную матрицу системы

A 1 2 3 4 b

1 4.1 0.1 0.2 0.2 21.14

2 0.3 5.3 0.9 -0.1 -17.82

3 0.2 0.3 3.2 0.2 9.02

4 0.1 0.1 0.2 -9.1 17.08

Результат вычислений по методу простой итерации

5.1999999341E+00

-4.2000000396E+00

2.9999996021E+00

-1.7999999492E+00

Листинг №2(метод Зейделя)

program seidel;

var A: array [1..4,1..4] of real;

b,x,otv: array [1..4] of real;

i,j,n: byte;

eps,s1,s2: real;

pr: boolean;

begin

write('razmer matrix n=');

readln(n);

for i:=1 to n do

for j:=1 to n do {Ввод данных}

begin

write('A[',i,',',j,']=');

readln(A[i,j]);

end;

for i:=1 to n do

if a[i,i]=0 then begin

writeln('oshibka vvoda'); {Проверка на сходимость}

exit;

end;

for i:=1 to n do

begin

write('b[',i,']=');

readln(b[i]);

end;

for i:=1 to n do

begin

for j:=1 to n do

begin

if i=j then continue;

a[i,j]:=-a[i,j]/a[i,i]; {Выражение аргументов}

end;

b[i]:=b[i]/a[i,i];

a[i,i]:=0;

end;

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j]:4:2,' ');

writeln(b[i]:4:2);

end;

for i:=1 to n do

begin

x[i]:=b[i];

otv[i]:=b[i];

end;

write('tochnost=');

readln(eps);

repeat

for i:=1 to n do

begin

s1 := 0;

s2 := 0;

For j := 1 to i - 1 do

s1 := s1 + a[i, j] * x[j]; {алгоритм решения}

For j := i to n do

s2 := s2 + a[i, j] * x[j];

x[i]:=s1+s2+b[i];

end;

for i:=1 to n do

if abs(otv[i]-x[i])

else begin

pr:=false;

break;

end;

for i:=1 to n do

otv[i]:=x[i];

until pr;

for i:=1 to n do

writeln(x[i]); {Вывод результата}

end.

Контрольный тест

Размер матрицы

4

Введите точность вычислений

0.000001

Введите расширенную матрицу системы

A 1 2 3 4 b

1 4.1 0.1 0.2 0.2 21.14

2 0.3 5.3 0.9 -0.1 -17.82

3 0.2 0.3 3.2 0.2 9.02

4 0.1 0.1 0.2 -9.1 17.08

Результат вычислений по методу Зейделя

5.2000000061E+00

-4.2000000026E+00

2.9999999999E+00

-1.8000000000E+00

Заключение

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

Число операций, требующихся для решения, зависит не только от порядка системы, но также от выбора метода вычислений. Поясним это примером. Предположим, что дана система п уравнений с п неизвестными и с оп­ределителем, отличным от нуля. По теореме Крамера система имеет единственное решение. В этой теореме указывается явное выражение для значений неизвестных в виде отношения двух определителей порядка я, при этом число различных определителей в отношениях

равно .

Пусть для нахождения решения мы хотим воспользо­ваться теоремой Крамера, при этом детерминанты будем вычислять по их обычному определению, как сумму со знаками произведений элементов по одному из каждой строки и каждого столбца. Легко можно под­считать, что для нахождения решения нужно будет приблизительно п^гп умножений и делений. Уже при п = 20 это число приблизительно равно 10²¹ и являете настолько большим, что становится ясной невозможность решать указанным путем на современных машинах систему даже двадцати уравнений.

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

Список используемой литературы

1. Вычислительные методы, том I. В.И. Крылов, В.В. Бобков, П.И. Монастырный. - М., Наука, 1976. - 303 с.

2. Калиткин Н.Н. Численные методы - М., Наука 1978. - 512 с.

3. http://ru.wikipedia.org/wiki/СЛАУ

4. http://www.exponenta.ru/educat/systemat/hanova/equation/linear/linear2.asp