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

Содержание

Введение

Глава 1. Теоретическая часть

1.1 Теория метода

1.2 Вычислительная схема метода Зейделя

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

Глава 2. Инструменты разработки консольного приложения

2.1 Интегрированная среда разработки Microsoft Visual Studio

2.2 Язык программирования C#2

Глава 3. Описание программы

Глава 4. Тестирование программы

Заключение

Библиографический список

Приложения

Введение

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

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

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

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

В данной работе, для реализации программного кода, был выбран широко известный язык программирования - С# и среда разработки Microsoft Visual Studio.

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

Предметом работы является консольное приложение.

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

Целью данной работы является разработать консольное приложение, предназначенное для нахождения корней СЛАУ методом Зейделя.

Глава 1. Теоретическая часть

алгебраический уравнение программа зейдель

Система m линейных уравнений с n неизвестными имеет следующий вид:

,

где

- корни СЛАУ;

коэффициенты системы;

свободные члены.

Если число m уравнений равно числу n неизвестных, то такая система называется квадратной. В данной работе рассматривается решение квадратных систем. В матричном виде квадратная система линейных алгебраических уравнений выглядит следующим образом:

или ,

где А - матрица коэффициентов системы;

х - столбец неизвестных;

b - столбец свободных членов.

Для матрицы А существует невырожденная матрица С, если .

Тогда . Если матрица С является обратной для А, т.е. , тогда:

Для решения СЛАУ разработано множество методов. Прямые методы позволяют найти решение за определенное количество шагов. К ним относятся:

1. Метод Гаусса;

2. Метод Гаусса -- Жордана;

3. Метод Крамера;

4. Матричный метод и др.

Итерационные методы дают возможность найти решение систем линейных алгебраических уравнений посредством уточнений начальных приближений многократным повторением одинаковых итераций. Число итераций зависит от заданной точности решения[10].

Наиболее распространенные итерационные методы:

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

2. Метод Гаусса - Зейделя.

К решению систем линейных уравнений сводятся такие группы задач:

1. Задачи механики (статические, теплотехнические);

2. Задачи из геодезии, связанные с построением карт на основании данных геодезической съемки;

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

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

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

1.1 Теория метода

Способ Гаусса-Зейделя можно рассматривать как улучшенную версию метода Якоби.

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

Пусть дана квадратная система линейных алгебраических уравнений с n неизвестными, корни которой нужно найти с заданной точностью :

или

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

Преобразуем матричное выражение к виду , разрешив n-ю строку относительно переменной :



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

В общем виде расчетные формулы выглядят:

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

1.2 Вычислительная схема метода Зейделя

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

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

,

вектор-столбец

1. Задается точность ()

2. Проверяется условие сходимости матрицы:

верно;

верно;

верно

3. Вычисление начальных приближений:

4. Нахождение приближений:

5. Критерий близости:

, заданная точность не достигнута.

Дальнейшие итерации выполняются аналогично (таблица 1).

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

k
0	0,187	-0,169	-0,137
1	0,187	-0,173	-0,076	0,0007	0,0044	0,0615	0,0615
2	0, 190	-0,155	-0,085	0,0024	0,0179	0,0088	0,0179
3	0,189	-0,158	-0,083	0,0010	0,0027	0,0014	0,0027
4	0,189	-0,158	-0,083	0,0001	0,0004	0,0002	0,0004

Решение достигается за 4 итерации.

Корни СЛАУ:

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

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

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

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

Глава 2. Инструменты разработки консольного приложения

2.1 Интегрированная среда разработки Microsoft Visual Studio

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

2.2 Язык программирования C#

C# - объектно-ориентированный язык программирования, который был разработан в 1998-2001 годах группой инженеров компании Microsoft под руководством Андерса Хейлсберга и Скотта Вильтаумота как язык разработки приложений для платформы Microsoft .NET Framework [1].

C# относится к семье языков с C-подобным синтаксисом, из них его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку операторов (в том числе операторов явного и неявного приведения типа), делегаты, атрибуты, события, свойства, обобщённые типы и методы, итераторы, анонимные функции с поддержкой замыканий, исключения, комментарии в формате XML.

С# принял многое от своих предшественников - языков C++, Delphi, Модула-2, Smalltalk и, в особенности, Java - С#, опираясь на практику их использования, исключает некоторые модели, зарекомендовавшие себя как проблематичные при разработке программных систем, например, C# в отличие от C++ не поддерживает множественное наследование классов (между тем допускается множественное наследование интерфейсов)[2].

C# разрабатывался как язык программирования прикладного уровня для CLR и, как таковой, зависит, прежде всего, от возможностей самой CLR.

Существует несколько реализаций C#:

· Реализация C# в виде компилятора csc.exe включена в состав .NET Framework (включая .NET Micro Framework, .NET Compact Framework и его реализации под Silverlight и Windows Phone 7).

· В составе проекта Rotor (Shared Source Common Language Infrastructure) компании Microsoft.

· Проект Mono включает в себя реализацию C# с открытым исходным кодом.

· Проект DotGNU также включает компилятор C# с открытым кодом.

· DotNetAnywhere -- ориентированная на встраиваемые системы реализация CLR, поддерживает практически всю спецификацию C# 2.0.

Глава 3. Описание программы

Поставленная задача была решена посредством следующих методов:

· Console.WriteLine - записывает текстовые представления заданного массива объектов, за которым следует текущий признак конца строки, в стандартный выходной поток с использованием заданных сведений о форматировании;

· Console.Write - записывает текстовое представление заданного значения или значений в стандартный выходной поток;

· Console.ReadKey - получает следующий нажатый пользователем символ или функциональную клавишу;

· Convert.ToDouble - преобразует заданное значение в число с плавающей запятой двойной точности.

Первоначально осуществляется определение количества строк для построения матрицы по следующему алгоритму:

int n = Convert.ToInt32(Console.ReadLine());

B = new double[n];

X = new double[n];

d = new double[n];

A = new double[n, n];

for (i = 0; i < n; i++)

{

B[i] = 0;

X[i] = 0;

d[i] = 0;

for (j = 0; j < n; j++)

{

A[i, j] = 0;

}

}

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

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

{

Console.Write("A[" + i +"][" + j + "] = ");

A[i, j] = Convert.ToDouble(Console.ReadLine());

if ((i == j) && (A[i, j] == 0))

{

Console.WriteLine("Ошибка ввода");

Console.ReadKey();

return;

}

}

}

Затем составляется результирующая матрица по следующему алгоритму:

for (i = 0; i < n; i++)

{

Console.Write("B[" + i + "] = ");

B[i] = Convert.ToDouble(Console.ReadLine());

}

После того как матрица коэффициентов перед x и результирующая матрица будут введены пользователем, программа выведет их на экран:

Console.WriteLine("Матрица коэффициентов перед х имеет вид:");

for (i = 0; i < n; ++i)

{

for (j = 0; j < n; ++j)

{

Console.Write(A[i, j] + " ");

}

Console.WriteLine();

}

Console.WriteLine("Результирующая матрица имеет вид:");

for (i = 0; i < n; ++i)

{

Console.WriteLine(B[i]);

}

Далее выполняется проверка на сходимость, если последовательность не сходится, на экран выводится: “Последовательность не является сходящейся”

Листинг проверки:

for (i = 0; i < n; ++i)

{

for (j = 0; j < n; ++j)

{

if (i != j)

{

k = -A[i, j] / A[i, i];

sum_kv += k * k;

}

else

{

sum_kv += 0;

}

}

}

sum_kv = Math.Sqrt(sum_kv);

if (sum_kv >= 1)

{

Console.WriteLine("Последовательность не является сходящейся!");

Console.ReadKey();

return;

}

Если последовательность удовлетворяет правилам сходимости - вводится значение погрешности и непосредственно выполняется решение СЛАУ методом Зейделя с учетом погрешности:

do

{

for (i = 0; i < n; ++i)

{

d[i] = X[i];

X[i] = B[i];

for (j = 0; j < n; ++j)

{

if (i != j)

{

X[i] -= A[i, j] * X[j];

}

}

X[i] = X[i] / A[i, i];

d[i] = Math.Abs(d[i] - X[i]);

}

maxd = d[0];

for (i = 1; i < n; ++i)

{

if (d[i] > maxd)

{

maxd = d[i];

}

}

} while (maxd > eps);

Полный листинг программы представлен в приложении 1.

Алгоритм (блок-схема) представлен в приложении 2.

Глава 4. Тестирование программы

Разработка консольного приложения на языке C# в программе Visual Studio начинается с выбора шаблона, подходящего для решаемой задачи. Представлен на рисунке 4.1.

Рис.4.1. Шаблон консольного приложения.

При запуске программы zeydel.sln открывается окно консольного приложения. На данном этапе программа просит ввести количество строк для определения размера матрицы (рис.4.2).

Рис.4.2. Колличество строк

Для проверки программы возьмем данную систему уравнений представленную на рисунке 4.3:



Рис.4.3. СЛАУ.

Вводим количество строк. Далее программа запрашивает поэлементно ввести значения матрицы коэффициентов перед x (Рис.4.4).

Рис.4.4. Ввод значений коэффициентов

Программа составила матрицу и вывела ее в командное окно. Далее вводим свободные члены (Рис.4.5).

Рис.4.5. Вывод матрицы

После ввода свободных членов программа запрашивает ввод значения погрешности в десятичном виде (Рис.4.6).

Рис.4.6. Результат вычислений

Программа проверяет на сходимость последовательность. Если сходится вычисляет СЛАУ методом Зейделя, если не сходится, то выводит на экран: «Последовательность не является сходящейся!» (Рис.4.7). Командное окно завершает свою работу нажатием на «Enter».

Рис.4.7. Вывод не сходящейся последовательности.

Заключение

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

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

Библиографический список

1. Джеффри Рихтер. CLR via C#. Программирование на платформе Microsoft.NET

2. Framework 4.5 на языке C# / Д. Рихтер - М.: влияние Питер, 2017 - 893с.

3. ГОСТ 2.105-95 ЕСКД - «Общие требования к текстовым документам».

4. ГОСТ 7.1-2003 - «Библиографическая запись. Библиографическое описание. Общие требования и правила составления».

5. ГОСТ 19.106-78 ЕСПД. - «Требования к программным документам, выполненным печатным способом».

6. ГОСТ 19.202-78 ЕСПД. - «Спецификация. Требования к содержанию и оформлению».

7. ГОСТ 19-301-79 ЕСПД. - «Программа и методика испытаний. Требования к содержанию и оформлению».

8. ГОСТ 19-404-79 ЕСПД. - «Пояснительная записка. Требования к содержанию и оформлению».

9. Газизов Т.Р., Куксенко С.П. Итерационные методы решения СЛАУ с плотной матрицей. - Томск: ТУСУР. - 2012. - 158с.

10. Бакушинский А. Б., Кокурин М. Ю. Итерационные методы решения некорректных операторных уравнений с гладкими операторами; Едиториал УРСС - М., 2017. - 192 c.

Приложение

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace zeydel

{

class Program

{

static void Main(string[] args)

{

double maxd, maxdp = 0, eps, k, sum_kv = 0;

int i, j;

double[] B, X, d;

double[,] A;

Console.Write("Задайте количество строк: ");

int n = Convert.ToInt32(Console.ReadLine());

B = new double[n];

X = new double[n];

d = new double[n];

A = new double[n, n];

for (i = 0; i < n; i++)

{

B[i] = 0;

X[i] = 0;

d[i] = 0;

for (j = 0; j < n; j++)

{

A[i, j] = 0;

}

}

Console.WriteLine("Построчно введите значения матрицы коэффициентов перед x\n(при i=j A[i][j] не равно 0)");

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

{

Console.Write("A[" + i +"][" + j + "] = ");

A[i, j] = Convert.ToDouble(Console.ReadLine());

if ((i == j) && (A[i, j] == 0))

{

Console.WriteLine("Ошибка ввода");

Console.ReadKey();

return;

}

}

}

Console.WriteLine("Введите значения результирующей матрицы");

for (i = 0; i < n; i++)

{

Console.Write("B[" + i + "] = ");

B[i] = Convert.ToDouble(Console.ReadLine());

}

Console.WriteLine("Матрица коэффициентов перед х имеет вид:");

for (i = 0; i < n; ++i)

{

for (j = 0; j < n; ++j)

{

Console.Write(A[i, j] + " ");

}

Console.WriteLine();

}

Console.WriteLine("Результирующая матрица имеет вид:");

for (i = 0; i < n; ++i)

{

Console.WriteLine(B[i]);

}

//Выполняем проверку

for (i = 0; i < n; ++i)

{

for (j = 0; j < n; ++j)

{

if (i != j)

{

k = -A[i, j] / A[i, i];

sum_kv += k * k;

}

else

{

sum_kv += 0;

}

}

}

sum_kv = Math.Sqrt(sum_kv);

if (sum_kv >= 1)

{

Console.WriteLine("Последовательность не является сходящейся!");

Console.ReadKey();

return;

}

//Водим значение погрешности

Console.WriteLine("Введите значение погрешности:");

eps = Convert.ToDouble(Console.ReadLine());

//Производится решение методом Зейделя

do

{

for (i = 0; i < n; ++i)

{

d[i] = X[i];

X[i] = B[i];

for (j = 0; j < n; ++j)

{

if (i != j)

{

X[i] -= A[i, j] * X[j];

}

}

X[i] = X[i] / A[i, i];

d[i] = Math.Abs(d[i] - X[i]);

}

maxd = d[0];

for (i = 1; i < n; ++i)

{

if (d[i] > maxd)

{

maxd = d[i];

}

}

} while (maxd > eps);

//Вывод ответа

Console.WriteLine("Корнями данной системы линейных алгебраических уравнений являются:");

for (i = 0; i < n; ++i)

{

Console.WriteLine("X[" + i + "] = " + X[i]);

}

Console.ReadKey();

return;

}

}

}



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

...