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

Разработать схему алгоритма и написать программу на языке Turbo Pascal7.0. для решения систем линейных алгебраических уравнений, используя метод Гаусса-Зейделя.

1.2 Математическая формулировка задачи

Пусть дана система линейных уравнений

(1.1)

Коэффициенты a₁₁,₁₂,..., a_1n, ... , a_n1 , b₂ , ... , b_n считаются заданными.

Вектор-столбец неизвестных - является решением системы (1.1), если при подстановке этих чисел в уравнения системы все они обращаются в верное равенство. Задача состоит в том, чтобы найти вектор-строку неизвестных с заданной точностью е>0. Для решения задачи можно использовать метод Гаусса-Зейделя.

1.3 Обзор существующих численных методов

Методы решения систем линейных алгебраических уравнений делятся на две группы. Прямые методы дают решение задачи за конечное (точно определяемое для каждого метода) число операций. К прямым относятся следующие методы: метод Гаусса, метод Крамера, метод LU-разложения, метод Холецкого (квадратного корня), метод прогонки.

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

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

1.4 Численный метод решения

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

Суть метода в том, что в процессе вычисления очередного приближения х₁^(к), х₂^(к), х_п^(к) найденные новые значения х_i^(к) сразу подставляются в правые части уравнений еще ненайденных переменных:

В общем случае для п уравнений

Если привести линейных алгебраических уравнений Ax = b к эквивалентной системе вида , то итерационный процесс выполняется при этом по соотношению

i = 1, 2, …, n.

Достаточное условие сходимости метода Гаусса-Зейделя определятся той же теоремой, что и достаточное условие сходимости метода простой итерации:

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

Критерий окончания итерационного процесса имеет вид:

, где - допустимая погрешность вычисления.

Существует устойчивое заблуждение, что метод Гаусса-Зейделя сходится быстрее метода Якоби (метода простых итераций). Это действительно так, если матрица А положительно определенная и симметричная. Однако возможны случаи, когда метод итераций Зейделя сходится медленнее метода простой итерации, и даже случаи, когда метод простой итерации сходится, а метод итераций Зейделя расходится. Возможны и противоположные ситуации. Дело в том, что методы ориентированы на решение разных классов систем: метод Якоби -на системы с матрицами, близкими к диагональным, метод Гаусса-Зейделя - на системы с матрицами, близкими к нижним треугольным.

1.5 Схема алгоритма

На рисунке 1.1 представлена схема алгоритма решения задачи №1.

На рисунке 1.2 представлена схема алгоритма ввода исходных данных (подпрограмма-процедура Input).

На рисунке 1.3 представлено продолжение схемы алгоритма ввода исходных данных (подпрограмма-процедура Input).

На рисунке 1.4 представлена схема алгоритма проверки сходимости метода (подпрограмма-процедура proverka_shodimosti).

На рисунке 1.5 представлено продолжение схемы алгоритма проверки сходимости метода (подпрограмма-процедура proverka_shodimosti).

На рисунке 1.6 представлена схема алгоритма решения системы линейных алгебраических уравнений методом Гаусса-Зейделя (подпрограмма-процедура reshenie_sistembl).

На рисунке 1.7 представлена схема алгоритма записи исходных данных и результата в файл (подпрограмма-процедура zapisb_v_fail).

На рисунке 1.8 представлена схема алгоритма вывода содержимого записанного файла на экран (подпрограмма-процедура outputtoscreen).

Рисунок 1.1 - Блок-схема алгоритма решения задачи №1

Рисунок 1.2 - Блок-схема алгоритма ввода данных

Рисунок 1.3 - Блок-схема алгоритма ввода данных (продолжение)

Рисунок 1.4 - Блок-схема алгоритма проверки сходимости метода

Рисунок 1.5 - Блок-схема алгоритма проверки сходимости метода (продолжение)

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

Рисунок 1.7 - Блок-схема алгоритма записи исходных данных и результата в файл

Рисунок 1.8 - Блок-схема алгоритма вывода содержимого записанного файла на экран

1.6 Текст программы

Далее приведен текст программы решения СЛАУ методом Гаусса-Зейделя.

program metod_Gaussa_Zeidelya;

uses crt;

const c=10;

type mas1=array [1..c,1..c] of real;

mas2=array [1..c] of real;

mas3=array [1..c,0..20] of real;

var dannble_i_rezultat,ekran:text;

shodimostb:boolean;

a,alpha:mas1;

b,beta:mas2;

x:mas3;

imya:string;

chetchik,n,prib:integer;

e:real;

procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:mas1; var matr2:mas2);

{Ввод исходных данных}

var i,j,code:integer;

a_s: string;

b_s: string;

begin

writeln(введите количество уравнений);

readln(kolvo);

writeln(введите погрешность вычисления);

readln(pogreshnostb);

writeln(введите матрицу коэффициентов при неизвестных);

for i:=1 to kolvo do

for j:=1 to kolvo do

begin

repeat

begin

writeln(введите элемент [,i,,,j,] и нажмите Enter);

readln(a_s);

if (i=j) and (a_s=0) then

repeat

begin

writeln(Элементы на главной диагонали должны быть отличны от нуля. Повторите ввод);

readln(a_s);

end;

until a_s<>0;

val(a_s,matr1[i,j],code);

end;

until code=0;

end;

writeln(введите вектор свободных коэффициентов);

for j:=1 to kolvo do

begin

repeat

writeln(введите элемент ,j, и нажмите Enter);

readln(b_s);

val(b_s,matr2[j],code);

until code=0

d;

end;

procedure proverka_shodimosti(matr1:mas1;matr2:mas2; kolvo:integer; var matr3:mas1; var matr4:mas2; var bool:boolean);

{Проверяется возможность решения}

var i,j:integer; summa1,summa2:array [1..c] of real; norma1,norma2,norma3,summa3:real;

procedure proverka_shodimosti(matr1:mas1;matr2:mas2; kolvo:integer; var matr3:mas1; var matr4:mas2; var bool:boolean);

{Проверяется возможность решения}

var i,j:integer; summa1,summa2:array [1..c] of real; norma1,norma2,norma3,summa3:real;

begin

for i:=1 to kolvo do

begin

summa1[i]:=0;

summa2[i]:=0;

end;

summa3:=0;

for i:=1 to kolvo do

for j:=1 to kolvo do

begin

if i=j then matr3[i,j]:=0 else matr3[i,j]:=-matr1[i,j]/matr1[i,i];

summa1[i]:=summa1[i]+abs(matr3[i,j]);

summa3:=summa3+sqr(matr3[i,j]);

end;

for j:=1 to kolvo do matr4[j]:=matr2[j]/matr1[j,j];

for j:=1 to kolvo do

for i:=1 to kolvo do

summa2[j]:=summa2[j]+abs(matr3[i,j]);

norma1:=summa1[1];

norma2:=summa1[2];

norma3:=Sqrt(summa3);

for i:=1 to kolvo do

begin

if summa1[i]>norma1 then norma1:=summa1[i];

if summa2[i]>norma2 then norma2:=summa2[i];

end;

if (norma1<1) or (norma2<1) or (norma3<1) then bool:=true else bool:=false;

end;

procedure reshenie_sistembl(matr3:mas1;matr4:mas2;kolvo:integer;pogreshnostb:real; var matr5:mas3; var k:integer);

{В процедуре осуществляется решение системы методом Гаусса-Зейделя}

var s1,s2:real; i,j,p:integer;

begin

for i:=1 to kolvo do matr5[i,0]:=0;

k:=0;

repeat

begin

k:=k+1;

p:=0;

for i:=1 to kolvo do

begin

s1:=0;

s2:=0;

for j:=1 to i-1 do s1:=s1+matr3[i,j]*matr5[j,k];

for j:=i+1 to kolvo do s2:=s2+matr3[i,j]*matr5[j,k-1];

matr5[i,k]:=s1+s2+matr4[i];

if (abs(matr5[i,k]-matr5[i,k-1])<=pogreshnostb) then p:=p+1;

end;

END.

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

Задание: Найти решение СЛАУ методом Гаусса-Зейделя:

Матрица системы

Вектор свободных членов

Решение: Воспользуемся математическим программным пакетом Mathcad13.

На рисунке 1.9 изображен тестовый пример работы программы для данной системы.

Рисунок 1.9 - Тестовый пример работы программы решения СЛАУ методом Гаусса-Зейделя

1.8 Инструкция пользователю

Данная программа осуществляет решение СЛАУ методом Гаусса-Зейделя. Вам будет предложено ввести количество уравнений, погрешность вычисления, построчно матрицу системы (коэффициенты перед неизвестными) и вектор свободных членов. Если система не имеет решений, выводится следующее сообщение: «Процесс итерации расходится, найти решение невозможно. Нажмите Enter для выхода». В случае, если метод сходится, то данные и результат записываются в файл, имя которого вам предложено будет ввести, и его содержимое выводится на экран. После этого для выхода из программы нажмите enter.

1.9 Инструкция программисту

Данная программа осуществляет решение СЛАУ методом Гаусса-Зейделя.

Константы:

С - константа целого типа, обозначает верхнюю границу матрицы системы и свободных членов.

Типы:

mas1=array [1..c,1..c] of real - двумерный массив c одинаковым количеством строк и столбцов;

mas2=array [1..c] of real - одномерный массив (вектор-столбец);

mas3=array [1..c,0..20] of real - двумерный массив.

Переменные:

N:integer-количество уравнений(размерность матрицы системы);

E :real- погрешность вычисления;

A:mas1-матрица коэффициентов перед неизвестными;

B:mas2 - вектор свободных членов;

Alpha:mas1,beta:mas2- матрицы, полученные при выражении неизвестных;

Shodimostb:boolean -логическая переменная, определяющая сходимость метода;

X:mas2- матрица-вектор решения системы;

Prib:integer- номер последнего приближения (вычисленного с заданной погрешностью);

Imya:string- имя файла, в который производится запись данных и результата;

Dannble_i_rezultat:text-файловая переменная, соответствующая записываемому файлу;

Ekran:text-файл, в который копируется данный файл для вывода на экран.

Подпрограммы

1)procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:mas1; var matr2:mas2) - ввод исходных данных.

Формальные параметры:

Kolvo:integer - количество уравнений в системе

(размерность матрицы системы);

pogreshnostb:real-погрешность вычисления;

matr1:mas1-матрица системы(коэффициенты перед неизвестными);

matr2:mas2-вектор свободных членов;

Локальные переменные:

i,j-счетчики в циклах;

summa1,summa2:array [1..c] of real,summa3:real-переменные, необходимые для вычисления норм матрицы коэффициентов перед неизвестными matr3;

norma1,norma2,norma3:real-нормы матрицы коэффициентов

a_s:string, b_s: string - строковые переменные, используемые для контроля ввода элементов матрицы системы и вектора свободных членов;

code:integer - индикатор ошибки ввода данных(параметр процедуры перевода строковой переменной в число Val).

2)procedure proverka_shodimosti(matr1:mas1;matr2:mas2; kolvo:integer; var matr3:mas1; var matr4:mas2; var bool:boolean) - проверка сходимости метода;

Формальные параметры:

-передаваемые значения:

Kolvo:integer -количество уравнений в системе (размерность матрицы системы);

matr1:mas1-матрица системы(коэффициенты перед неизвестными);

matr2:mas2-вектор свободных членов;

-возвращаемые значения:

matr3:mas1, matr4:mas2 -матрицы, полученные при выражении неизвестных;

bool:boolean-логическая переменная, определяющая сходимость метода

Локальные переменные:

i,j-счетчики в циклах;

перед неизвестными matr3;

3) procedure reshenie_sistembl (matr3:mas1;matr4:mas2;

kolvo:integer;pogreshnostb:real; var matr5:mas3; var k:integer) - решение СЛАУ.

Формальные параметры:

-передаваемые значения:

matr3:mas1, matr4:mas2 -матрицы, полученные при выражении неизвестных;

kolvo:integer -количество уравнений в системе;

pogreshnostb:real-погрешность вычисления;

-возвращаемые значения:

matr5:mas3-вектор неизвестных(приближение);

k:integer -номер приближения, вычисленного с заданной погрешностью;

Локальные переменные:

i,j:integer-счетчики в циклах;

p:integer-количество элементов приближения, вычисленных с заданной погрешностью;

s1,s2:real-переменные,необходимые для вычисления элемента приближения;

4) procedure zapisb_v_fail(kolvo:integer; matr1:mas1; matr2:mas2; matr5:mas3; k:integer; var imyafaila:string; var f:text) - запись в файла данных и ответа.

Формальные параметры:

-передаваемые значения:

Kolvo:integer -количество уравнений в системе (размерность матрицы системы);matr1:mas1-матрица системы(коэффициенты перед неизвестными);matr2:mas2-вектор свободных членов;

matr5:mas3-вектор неизвестных(приближение); k:integer -номер приближения, вычисленного с заданной погрешностью;

-возвращаемые значения:

imyafaila:string-имя записываемого файла; f:text-файловая переменная, соответствующая записываемому файлу

Локальные переменные:

i,j-счетчики в циклах;

5) procedure outputtoscreen(var imyafaila:string; var f1,f2:text) - вывод содержимого записанного файла на экран.

Формальные параметры:

-передаваемые значения:

imyafaila:string-имя файла, который выводится на экран;

-возвращаемые значения:

f1,f2:text - файловые переменные, соответствующие копируемому файлу и файлу, в который осущ2 Задача №2: интерполирование функции, заданной в узлах, методом Вандермонда