Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

Белорусский национальный технический университет

Кафедра «Горные работы»

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

по дисциплине «Информатика»

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

Минск 2017



Введение

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

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

3. Перечень идентификаторов программы

4. Описание алгоритма решения задачи

5. Блок-схем алгоритма

5.1 Блок-схема алгоритма основной программы

5.2 Блок-схема алгоритмов процедур

6. Текст программы на языке Pascal

7. Результаты выполнения программы

8. Анализ результатов в Excel

9. Результаты работы программы

Заключение

Литература



Введение

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

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

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

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

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

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

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

2x1-x2+x3=-3

3x1+5x2-2x3=1

x1-4x2+10x3=0



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

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

2x1-x2+x3=-3

3x1+5x2-2x3=1

x1-4x2+10x3=0

Решение системы линейных алгебраических уравнений (СЛАУ) имеет большое значение, поскольку к нему сводится решение широкого круга сложных практических задач. В линейной алгебре эту задачу называют первой основной задачей. Так, около 75% всех расчетных математических задач приходится на решение СЛАУ. Хотя эта задача сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением компьютера. Как известно, значительная часть численных методов решения различных (в особенности ? нелинейных) задач включает в себя решение СЛАУ как элементарный шаг соответствующего алгоритма.

Системой m линейных уравнений с n неизвестными называется система вида



где aij и bi (i=1,…,m; b=1,…,n) - некоторые известные числа, а x1,…,xn - неизвестные. В обозначении коэффициентов aij первый индекс i обозначает номер уравнения, а второй j - номер неизвестного, при котором стоит этот коэффициент.

Коэффициенты при неизвестных будем записывать в виде матрицы

,

которую назовём матрицей системы.

Числа, стоящие в правых частях уравнений, b1,…,bm называются свободными членами.

Совокупность n чисел c1,…,cn называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c1,…,cn вместо соответствующих неизвестных x1,…,xn.

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

1) система может иметь единственное решение.

2) система может иметь бесконечное множество решений. Например,

Решением этой системы является любая пара чисел, отличающихся знаком.

3) система вообще не имеет решения. Например,

,

если бы решение существовало, то x1 + x2 равнялось бы одновременно нулю и единице.

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



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

программа решение линейный уравнение

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

Ax=b

где А -невырожденная квадратная матрица порядка m, - вектор правой части, - искомый вектор. В развернутом виде:

(1)

Требуется определить вектор неизвестных x.

Метод простой итерации (метод Якоби)

Для применения данного метода, необходимо преобразовать исходную систему (1) к виду, удобному для итераций

(2)

В выражении (2) B - квадратная матрица, с - вектор-столбец.

В наиболее простом случае, к которому относятся метод простой итерации и метод Зейделя, приведение к виду, удобному для итераций, достигается выражением переменной из i-го уравнения:



(3)

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

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

(4)

В случае применения (2) и вычисления коэффициентов по формуле (4), метод простой итерации называют методом Якоби.

Шаг метода простой итерации

Для применения метода выбирается начальное приближение

Далее расчет производится по итеративной формуле:

(5)

Сходимость метода простой итерации

Метод простой итерации сходится при выполнении условия . В частности, применяют норму .

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

При заданной точности критерий окончания имеет вид

(6)

Если , то применяют простой критерий окончания

(7)



3. Перечень идентификаторов программы

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

Таблица 1 - Перечень идентификаторов программа

№	Обозначение в формуле	Обозначение в программе	Описание
1		e	точность
2	x	x	вектор, найденных x
3	A	A	матрица коэффицентов
4	B	B	вектор свободных членов



4. Описание алгоритма решения задачи

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

Метод простых итераций описывается следующим алгоритмом:

1. Задать начальное приближение

x(0)=(x10,x20,…,xn0)T

и малое положительное число ? (точность). Положить

k=0

2. Вычислить x(k+1) по формуле

x(k+1)=?(x(k))

или

x1(k+1)=?1(x1(k),x2(k),…,xn(k)),

3. Если , процесс завершен и x??x(k+1).

Если ?(k+1)>?, то положить k=k+1 и перейти к п.2.



5. Блок-схем алгоритма

5.1 Блок-схема алгоритма основной программы

Рисунок 2 - Блок-схема основной программы

5.2 Блок-схема алгоритмов процедур

Для уменьшения кода программы были созданы четыре процедуры:

InputData() - процедура ввода данных

IterationForm(A,b) - процедура для получения итерационной формы системы

Check(C,d) - проверка системы на сходимость

Iteration(C,d) - реализация метода итерации

Рисунок 3 - Блок-схема процедуры ввода данных



Рисунок 4 - Блок-схема процедуры для получения итерационной формы системы



Рисунок 5 - Блок-схема процедуры проверки системы на сходимость



Рисунок 6 - Блок-схема процедуры итерации



6. Текст программы на языке Pascal

Программа была реализована на языке Pascal.

Program pr1;

const

n=3;

Var

A:array of array of real; {матрица коэффициентов}

b:array Of real; {вектор-столбец свободных членов}

C:array of Array of real; {матрица Якоби - итерационная форма матрицы А}

d:array of real; {итерационная форма вектора свободных членов}

Err:Boolean; {переменная, по значению которой после выполнения процедуры проверки}

X:array of Real; {вектор неизвестных}

procedure InputData;

var

i,j:Integer;

begin

SetLength(A,n);

writeln('Введите матрицу коэффициентов');

{ввод матрицы А}

for i:=0 To n-1 Do

begin

SetLength(A[i],n); {многомерные массивы в PascalABC можно определять как массивы массивов}

end;

for i:=0 To n-1 Do

begin

for j:=0 To n-1 Do

begin

read(A[i,j]);

end;

writeln('');

end;

writeln('введите матрицу свободных членов');

{ввод вектора B}

SetLength(b,n);

for i:=0 To n-1 Do

begin

readln(b[i]);

end;

end;

Procedure IterationForm(A:array of Array of real;b:array of real);

{получение итерационной формы системы}

var i,j:Integer;

begin

SetLength(C,n);

for i:=0 To n-1 Do

begin

Setlength(C[i],n);

end;

SetLength(d,n);

for i:=0 To n-1 Do

begin

for j:=0 To n-1 Do

begin

if i=j then

C[i,j]:=0

else

C[i,j]:=-A[i,j]/A[i,i];

end;

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

end;

end;

Procedure Check(C:array of array of real;d:array of real);

{проверка системы на сходимость}

var i,j:Integer;

summ:real;

begin

summ:=0;

for i:=0 To n-1 Do

begin

for j:=0 To n-1 Do

begin

summ:=summ+C[i,j]*C[i,j];

end;

end;

if SQRT(Abs(summ))>1 then

begin

writeln('Данная система не удовлетворяет условию сходимости');

Err:=True;

end

Else Err:=False;

end;

Procedure Iteration(C:array of array of real;d:array of real);

var i,j:Integer;

X0:array of real;

delta:real;

E:array of real;

iter:integer;

begin

SetLength(X0,n);

SetLength(X,n);

Setlength(E,n);

X0:=Copy(d);

iter:=0;

repeat

begin

for i:=0 To n-1 Do

begin

X[i]:=0;

for j:=0 To n-1 Do

begin

X[i]:=X[i]+C[i,j]*X0[j];

end;

X[i]:=X[i]+d[i];

E[i]:=Abs(X[i]-X0[i]);

end;

delta:=E[0];

for i:=1 To n-1 Do

begin

if delta<E[i] then delta:=E[i];

end;

X0:=Copy(X);

iter:=iter+1;

end;

Until delta<=0.0005;

writeln('Решение системы');

For i:=0 To n-1 Do

begin

Writeln('x',(i+1),' = ',X[i]:3:3);

end;

writeln('Количество итераций ',iter);

end;

BEGIN

Err:=False;

InputData();

IterationForm(A,b);

Check(C,d);

if Err=False then Iteration(C,d);

end.



7. Результаты выполнения программы

Воспользуемся компилятором Turbo Pascal для запуска нашей программы.

Введем данные из примера:

2x1-x2+x3=-3

3x1+5x2-2x3=1

x1-4x2+10x3=0

Рисунок 7 - Тестирование программы

Введем данные из другого примера



Рисунок 8 - Тестирование программы



8 Анализ результатов в Excel

Дана система уравнений

Значения элементов введем в ячейки Excel в виде таблицы.

Рисунок 8 - Данные в Excel

Найдем обратную матрицу. Выделим диапазон, куда впоследствии будут помещены элементы матрицы (ориентируемся на количество строк и столбцов в исходной матрице). Открываем список функций (fx). В категории «Математические» находим МОБР. Аргумент - массив ячеек с элементами исходной матрицы.

Рисунок 9 - Функция МОБР



Нажимаем ОК - в левом верхнем углу диапазона появляется значение. Последовательно жмем кнопку F2 и сочетание клавиш Ctrl + Shift + Enter.

Рисунок 10 - Обратная матрица

Умножим обратную матрицу А-1 на матрицу В (именно в таком порядке следования множителей!). Выделяем диапазон, где впоследствии появятся элементы результирующей матрицы (ориентируемся на число строк и столбцов матрицы В). Открываем диалоговое окно математической функции МУМНОЖ. Первый диапазон - обратная матрица. Второй - матрица В. Закрываем окно с аргументами функции нажатием кнопки ОК. Последовательно нажимаем кнопку F2 и комбинацию Ctrl + Shift + Enter.

Рисунок 11 - Решение системы уравнений

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



9. Результаты работы программы

Для запуска программы необходимо запустить файл program.pas в среде программирования PascalABC.Net и откомпилировать ее. После запуска программы появится окно с просьбой ввести матрицу коэффициентов и вектор свободных членов (рисунок 12).

Рисунок 12 - Ввод данных в программу

Если условие сходимости не соблюдается, то программа выдаст ошибку (рисунок 13).

Рисунок 13 - Ошибка



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

Завершение работы с программой реализуется нажатием любой клавиши.



Заключение

Необходимость решения СЛАУ возникает при решении многомерных анизотропных краевых задач, в задачах вычислительной гидродинамики, в теории электрических цепей, при решении уравнений балансов и сохранения в механике, гидравлике и т.п. В геомеханике матрица СЛАУ имеет чрезмерно большие размеры и является плохо обусловленной. Поэтому обычные методы решения СЛАУ здесь оказываются неэффективными. Задача нахождения устойчивых приближенных решений СЛАУ является определяющей задачей для гравиметрии и магнитометрии. Необходимость решения трех диагональных СЛАУ возникает и в физике (оптика, теория теплопроводности, газовая динамика и др.), и в математике (теория разностных схем, проекционные и вариационные методы). Также проблема решения СЛАУ существует в задачах управления и контроля, которые предъявляют высокие требования к скорости получения результатов, пусть даже приближенных. Среди них можно выделить класс задач оценки и предсказания критических ситуаций, связанных, например, с измерением температуры и вычислением плотности теплового потока на поверхности спускаемого летательного аппарата и др.

В курсовой работе приводится разработка программы решений системы линейных уравнений методом итераций с предварительной оценкой числа необходимых шагов по заданной точности. Получено с погрешностью =0,510-3 решение системы:

2x1-x2+x3=-3

3x1+5x2-2x3=1

x1-4x2+10x3=0



Литература

1. Бахвалов Н.С., Жибков Н.П., Кобельков Г.М. Численные методы. - М.: Наука, 2014.

2. Голуб Дж., Ван Лоун Ч. Матричные вычисления. - М.: Мир, 1999.

3. Икрамов Х.Д. Вычислительные методы линейной алгебры. (Решение больших разреженных систем уравнений прямыми методами). - М.: Знание, 1989.

4. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. - М.: Мир, 1984.

5. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. - М.: Мир, 1969.

Размещено на Allbest.ur

...