Дипломная работа на тему Метод Зейделя

Введение

Решение систем линейных алгебраических уравнений - одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности - нелинейных)задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.

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

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

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

1.Глава. Модификация метода простых итераций

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

Модификацией метода простых итераций Якоби можно считать метод Зейделя.

В методе Якоби на (k+1)-ой итерации значения x, i = 1, 2, …, n. вычисляются подстановкой в правую часть (3.27) вычисленных на предыдущей итерации значений x. В методе Зейделя при вычислении xиспользуются значения x, x, x, уже найденные на (k+1)-ой итерации, а не x, x, …, x, как в методе Якоби, т.е. (k + 1)-е приближение строится следующим образом:

x = b12 x + b13 x + … + b1,n-1 x + b1n x + c1

x = b21 x + b23 x + … + b2,n-1 x + b2n x + c2

x= b31 x + b32 x + … + b3,n-1 x + b3n x + c3 (3.36)

x= bn1 x + bn2 x x + bn3 x x+ … + bn,n-1 x + c.n

Формулы (3.36) являются расчетными формулами метода Зейделя.

Введем нижнюю и верхнюю треугольные матрицы:

0 0 0 … 0 0 b12 b13 … b1n

b21 0 0 … 0 0 0 b23 … b2n

B1 = b31 b32 0 … 0 и B2 = 0 0 0 … b3n .

bn1 bn2 bn3 …0 0 0 0 … 0

Матричная запись расчетных формул (3.36) имеет вид:

xk+1= B1xk+1+ B2xk+ c. (3.37)

так как B = B1+ B2, точное решение x* исходной системы удовлетворяет равенству:

x*= B1x*+ B2x*+ c. (3.38)

1.2.Сходимость метода Зейделя.

Достаточным условием сходимости метода Зейделя является выполнение неравенства:

b = max |bij|,< 1, i, j = 1, 2, …, n. (3.39)

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

Если выполнено условие (3.39), то справедлива следующая апостериорная оценка погрешности:

max|x - x| Ј max|x- x| i = 1, 2, …, n, (3.40)

где b - максимальный элемент матрицы B, b2 - максимальный элемент матрицы B2.

Правую часть оценки (3.40) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.37) итерационный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство:

max|x- x| < e, i = 1, 2, …, n. (3.41)

Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство

max|x- x| < e1, i = 1, 2, …, n. (3.42)

где e1 = e.

Если выполняется условие b Ј , то можно пользоваться более простым критерием окончания:

max|x- x| < e, i = 1, 2, …, n. (3.43)

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

Пример 3.6.

Применим метод Зейделя для решения системы уравнений (3.33) из примера 3.5. Первые шаги полностью совпадают с процедурой решения по методу Якоби, а именно: система приводится к виду (3.34), затем в качестве начального приближения выбираются элементы столбца свободных членов (3.35). Проведем теперь итерации методом Зейделя.

При k = 1

x = - 0.0574x - 0.1005x - 0.0431x + 1.0383 = 0.7512

При вычислении xиспользуем уже полученное значение x:

x = -0.0566 x - 0.0708x - 0.1179x + 1.2953 = 0.9674

При вычислении x используем уже полученные значения x и x:

x = -0.1061 x - 0.0758 x - 0.0657x + 1.4525 = 1.1977

При вычислении x используем уже полученные значения x, x, x:

x = -0.0280 x - 0.0779 x - 0.0405x x + 1.5489 = 1.4037

Аналогичным образом проведем вычисления при k = 2 и k = 3. Получим:

при k = 2

x= 0.8019, x= 0.9996, x= 1.9996, x= 1.4000.

при k = 3

x= 0.80006, x= 1.00002, x= 1.19999, x= 1.40000.

Известны точные значения переменных:

x1 = 0.8, x2 = 1.0, x3 = 1.2, x4 = 1.4.

Сравнение с примером 3.5 показывает, что метод Зейделя сходится быстрее и дает более точный результат.

1.3. Сравнение прямых и итерационных методов

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

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

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

2 глава. Приближение функций

2.1 Постановка задачи

Задача приближения (аппроксимации) функций заключается в том, чтобы для данной функции построить другую, отличную от нее функцию, значения которой достаточно близки к значениям данной функции. Такая задача возникает на практике достаточно часто. Укажем наиболее типичные случаи.

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

2. Функция задана аналитически, но ее вычисление по формуле затруднительно.

При решении задачи поиска приближенной функции возникают следующие проблемы.

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

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

3. Необходимо указать правило (алгоритм), позволяющее с заданной точностью найти приближение функции.

2.1.2. Описание алгоритма.

В данной программе реализован метод Гаусса со схемой частичного выбора.

В переменную n вводится порядок матрицы системы. С помощью вспомогательной процедуры Read System в двумерный массив a и одномерный массив вводится c клавиатуры расширенная матрицасистемы, после чего оба массива и переменная nпередаются функции Gauss. Вфукции Gauss для каждого k-го шага вычислений выполняется поиск максимального элементав k-м столбце матрицы начинаяя с k-й строки.Номер строки, содержащей максимальный элемент сохраняеется в переменной l. Втом случае если максимальный элемент находится не в k-й строке,строки с номерами k и lменяются местами. Если жевсе эти элементы равны нулю, то происходит прекращение выполнения функции Gaussc результатом false. После выбора строки выполняетсяпреобразование матрицы по методу Гаусса. Далее вычисляется решениесистемы и помещается в массив x. Полученное решение выводится на экран припомощи вспомогательной процедуры WriteX.

2.1.3. Листинг программы и результаты работы

Uses CRT;

Const

maxn = 10;

Type

Data = Real;

Matrix =Array[1..maxn, 1..maxn] of Data;

Vector =Array[1..maxn] of Data;

{ Процедура ввода расширенной матрицы системы }

Procedure ReadSystem(n: Integer; var a: Matrix; var b:Vector);

Var

i, j, r:Integer;

Begin

r := WhereY;

GotoXY(2, r);

Write('A');

For i := 1 ton do begin

GotoXY(i*6+2, r);

Write(i);

GotoXY(1,r+i+1);

Write(i:2);

end;

GotoXY((n+1)*6+2, r);

Write('b');

For i := 1 ton do begin

For j := 1to n do begin

GotoXY(j * 6 + 2, r + i + 1);

Read(a[i, j]);

end;

GotoXY((n+ 1) * 6 + 2, r + i + 1);

Read(b[i]);

end;

End;

{ Процедура вывода результатов }

Procedure WriteX(n :Integer; x: Vector);

Var

i: Integer;

Begin

For i := 1 ton do

Writeln('x', i, ' = ', x[i]);

End;

{ Функция, реализующая метод Гаусса }

Function Gauss(n: Integer; a: Matrix; b: Vector; varx:Vector): Boolean;

Var

i, j, k, l:Integer;

q, m, t: Data;

Begin

For k := 1 ton - 1 do begin

{ Ищемстроку l с максимальным элементом в k-ом столбце}

l := 0;

m := 0;

For i := kto n do

If Abs(a[i,k]) > m then begin

m:= Abs(a[i, k]);

l:= i;

end;

{ Если увсех строк от k до n элемент в k-м столбце нулевой,

тосистема не имеет однозначного решения }

If l = 0then begin

Gauss:= false;

Exit;

end;

{ Меняемместом l-ую строку с k-ой }

If l<> k then begin

For j:= 1 to n do begin

t:= a[k, j];

a[k, j] := a[l, j];

a[l, j] := t;

end;

t :=b[k];

b[k] :=b[l];

b[l] :=t;

end;

{Преобразуем матрицу }

For i := k+ 1 to n do begin

q :=a[i, k] / a[k, k];

For j:= 1 to n do

Ifj = k then

a[i, j] := 0

else

a[i, j] := a[i, j] - q * a[k, j];

b[i] := b[i] - q * b[k];

end;

end;

{ Вычисляемрешение }

x[n] := b[n] /a[n, n];

For i := n - 1downto 1 do begin

t := 0;

For j := 1to n-i do

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

x[i] := (1/ a[i, i]) * (b[i] - t);

end;

Gauss := true;

End;

Var

n, i: Integer;

a: Matrix ;

b, x: Vector;

Begin

ClrScr;

Writeln('Программа решения систем линейных уравнений по методу Гаусса');

Writeln;

Writeln('Введите порядок матрицы системы (макс. 10)');

Repeat

Write('>');

Read(n);

Until (n >0) and (n <= maxn);

Writeln;

Writeln('Введите расширенную матрицу системы');

ReadSystem(n,a, b);

Writeln;

If Gauss(n,a, b, x) then begin

Writeln('Результат вычислений по методу Гаусса');

WriteX(n,x);

end

else

Writeln('Данную систему невозможно решитьпо методу Гаусса');

Writeln;

End.

Программа решения системлинейных уравнений по методу Гаусса

Введите порядок матрицы системы (макс. 10)

>4

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

A 1 2 3 4 b

1 3.2 5.4 4.2 2.2 2.6

2 2.1 3.2 3.1 1.1 4.8

3 1.2 0.4 -0.8 -0.8 3.6

4 4.7 10.4 9.7 9.7 -8.4

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

x1 = 5.0000000000E+00

x2 = -4.0000000000E+00

x3 = 3.0000000000E+00

x4 = -2.0000000000E+00

2.2.Программа решения систем линейных уравнений по методу Зейделя

2.2.1. Постановка задачи. Требуется решить систему линейных алгебраических уравнений с вещественными коэффициентами вида

a11x1+ a12x2 + … + a1nxn = b1 ,
a21x2+ a22x2 + … + a2nxn = b2,
. . . . . . . . . . . . .

an1x1 + an2x2+ … + annxn = bn

для n≤ 10 по методу Зейделя.

2.2.2.Тестовый пример.

4,1x1+ 0,1x2+ 0,2x3 + 0,2x4 = 21,14 ,

0,3x1 + 5,3x2 + 0,9x3- 0,1x4 = - 17,82 ,

0,2x1 + 0,3x2 + 3,2x3+ 0,2x4 = 9,02 ,

0,1x1 + 0,1x2 + 0,2x3- 9,1x4 = 17,08 ,

x1 = 5,2, x2 = -4,2, x3 = 3, x4 = -1,8.

2.2.3. Итерационные методы решения систем линейных алгебраических уравнений

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

2.3 Метод простой итерации.

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

Рассмотрим СЛАУ вида

Ax = B, где А - матрица. (1)

A = {aij}i, j = 1…n

B = {bi}x = {xi}

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

xk = Cxk-1 + D

xk → x*, где х* - решение заданной системы.

В конечном варианте система будет имееть вид:

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

Заметим, что B = B1 + B2 и поэтому решение x исходной системы удовлетворяет равенству

x= B1x + B2 x +c .

Выберем начальное приближение x(0)= [x1(0), x2(0),…, xn(0)]T. Подставляя его в правую часть равенства при верхней треугольной матрице B2ивычисляя полученное выражение, находим первое приближение

x(1)= B1x(0) + B2x(1)

Подставляя приближение x(1), получим

x(2)= B1x(1) + B2x(2)

Продолжая этот процесс далее, получим последовательность x(0),x(1),…, x(n), … приближений к вычисляемых по формуле

x(k+1)= B1(k+1) + B2(k) + c

или в развернутой форме записи

x1(k+1) = b12x2(k) + b13x2(k)+ … + b1nxn(k) + c1 ,

x2(k+1) = b21x1(k+1) + b23x3(k)+ … + b2nxn(k) + c2 ,

x3(k+1) = b31x1(k+1) + b32x2(k+1)+ … + b3nxn(k)+ c3,

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

xn(k+1) = bn1x1(k+1) + bn2x2(k+1) + bn3x3(k+1) + … + cn .

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

xi(k+1)= xi(k) - aii-1(∑j=1i-1aijxj(k+1) + ∑j=1naijxi(k) - bi).

Тогда достаточным условием сходимости метода Зейделя будет

∑j=1, j≠i n | a­ij | < | a­ii |

(условие доминированния диагонали).

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

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

, или .

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:

x1=a11-1 (c1-a12x2 - a13x3-… - a1nxn)

x2=a22-1 (c2-a21x2 - a23x3-… - a2nxn)

………………………. .

xn=ann-1 (cn-an1x2 - an3x3-… - an-1nxn-1)

В результате получим систему:

x1=0+ c12x2+ c13x3-…+ c1n-1xn-1+ c1nxn+d1

x2= c21x2+0 +c23x3+…+ c2n-1xn-1+ c2nxn+d2

………………………………………………………. .

xn= cn1x1+ cn2x2 +cn3x3+…+ cnn-1xn-1+ 0+dn

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

сij=-aij/aii, di=ci/aii (i,j=1,2,3…n, i<>j)

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

3 ГЛАВА. Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

Условие сходимости:

,

Принимаем приближение на 0-ом шаге:

,

,

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 2-м шаге выполняем следующее:

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

:

На 3-м шаге выполняем следующее:

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

:

На 4-м шаге выполняем следующее:

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

:

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить.

3.1.1. Программа для решения СЛАУ методом простых итераций

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

Листинг программы приведен в приложении Г.

Рисунок 4.1 - Программа "Метод простых итераций"

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

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

В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) - й итерации компоненты приближения вычисляются по формулам:

………………………………………….

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

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

, либо

3.1.3. Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью .

Эту систему можно записать в виде:

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

Для удобства преобразуем систему к виду:

Условие сходимости:

,

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

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

:

На 2-м шаге выполняем следующее:

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

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 4-м шаге выполняем следующее:

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

:

Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить.

3.2. Программа для решения СЛАУ методом Зейделя

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

Листинг программы приведен в приложении Г.

Рисунок 3.2 - Программа "Метод Зейделя"

3.2.1. Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:

Таблица 3.1 - Результаты решения СЛАУ

№ шага

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

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

0

x1=1.34

x2=-1.75

x3=0.5

x4=0.65

x1=1.34

x2=-1.75

x3=0.5

x4=0.65

1

x1=1.277

x2=-1.56227

x3=0.3147

x4=0.5335

x1=1.277

x2=-1.57047

x3=0.3324

x4=0.5837

2

x1=1.31335

x2=-1.6127

x3=0.3647

x4=0.5884

x1=1.32469

x2=-1.5974

x3=0.355808

x4=0.58638

3

x1=1.315391

x2=-1.5935

x3=0.34936

x4=0.57867

x1=1.318014

x2=-1.5945

x3=0.354137

x4=0.58556

4

x1=1.3173416

x2=-1.5968

x3=0.35577

x4=0.58589

x1=1.318367

x2=-1.59481

x3=0.35437

x4=0.58554

5

x1=1.3179137

x2=-1.59467

x3=0.35371

x4=0.58462

6

x1=1.3181515

x2=-1.59506

x3=0.35455

x4=0.58557