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

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

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

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

И.С. Урожай

Самара 2017

Введение

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

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

Объектом исследования данной бакалаврской работы является решение систем уравнений.

Перед проектом определен ряд задач:

· обеспечить пользователю интерфейс для ввода уравнений;

· реализовать функционал для обработки уравнений;

· для каждого введенного уравнения должны быть найдены производные;

· создать методы для решения нелинейных уравнений;

· реализовать структурированный вывод результатов вычислений;

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

Для достижения задач проекта необходимо:

1. изучить методы решения нелинейных уравнений;

2. изучить способы нахождения производных по переменным;

3. изучить способы чтения уравнений из строки.

Руководства от Microsoft Visual Studio стали основными источниками информации при выполнении бакалаврской работы.

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

1. Решение уравнений и систем уравнений

1.1 Решение линейных уравнений

Линейное уравнение - это алгебраическое уравнение, полная степень многочленов которого равна 1. Линейное уравнение можно представить:

· в общей форме:

· в канонической форме:

Линейное уравнение одной переменной можно привести к виду:

Количество решений зависит от параметров a и b.

Если то уравнение имеет бесконечное множество решений, поскольку

Если то уравнение не имеет решений, поскольку

Если то уравнение имеет единственное решение

На рисунке 1.1 изображена графическая интерпретация линейного уравнения.

Рис. 1.1 - Геометрическое место точек линейного уравнения от двух переменных вида:

Линейное уравнение, содержащее две переменные, можно представить:

· в общей форме:

· в канонической форме:

· в форме линейной функции:

Решением, или корнями, данного уравнения называют такую пару значений x и y, которая обращает его в тождество. Таких решений (корней) линейное уравнение с двумя переменными имеет бесконечное множество. Геометрической моделью (графиком) такого уравнения является прямая

1.2 Решение систем линейных уравнений

Система линейных алгебраических уравнений (линейная система, также сокращенная SLAE, SL) представляет собой систему уравнений, каждое уравнение которой является линейно-алгебраическим уравнением первой степени.

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

Решение систем линейных алгебраических уравнений является одной из классических задач линейной алгебры (рис. 1.2), которая в значительной степени определяет ее объекты и методы. Кроме того, линейные алгебраические уравнения и методы их решения играют определенную роль во многих прикладных областях, включая линейное программирование, эконометрику.



Рис. 1.2 - Система линейных уравнений от трех переменных определяет набор плоскостей. Точка пересечения является решением.

Общий вид системы линейных уравнений алгебраических уравнений:

(1.1)

Здесь m - число уравнений, а n - число переменных, - неизвестные значения, коэффициенты и свободные члены считаются известными. Индексы коэффициентов в системах формируются по следующему соглашению: первый индекс (i) обозначает номер уравнения, второй (j) - номер переменной, в которой этот коэффициент стоит.

Если все свободные члены системы равны нулю, то система называется однородной, иначе она неоднородна.

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

Решением системы линейных уравнений является множество n чисел , так что их соответствующее утверждение вместо в системе превращает все его уравнения в тождество.

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

Система линейных алгебраических уравнений может быть представлена в виде матрицы:

= (1.2)

(1.3)

Здесь A - это матрица системы, x - столбец неизвестных, а b - столбец cвободных членов. Если к матрице A приписать справа столбец свободных членов, то получившаяся матрица называется расширенной.

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

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

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

Система линейных алгебраических уравнений {\ A{\ {x}}\ ={\ {b}}} эквивалентна системе {\ CA{\ {x}}\ =C{\ {b}}}, где C{\ C} -- невырожденная матрица. В частности, если сама матрица A{\ A} -- невырожденная, и для неё существует обратная матрица {\ A^{-1}}, то решение системы уравнений можно формально записать в виде {\ {\ {x}}=A^{-1}{\ {b}}}.

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

· метод Гаусса;

· метод Гаусса-Жордана;

· метод Крамера;

· матричный метод;

· метод прогонки (для трехдиагональных матриц);

· разложение Холецкого или метод квадратных корней (для положительно-определённых симметричных и эрмитовых матриц);

· метод вращений.

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

(1.4)

Эквивалентно исходной системе линейных алгебраических уравнений. В итерации х в правой части уравнения, например, в методе Якоби (метод простой итерации) заменяется аппроксимация, найденная на предыдущем шаге:

(1.5)

Итерационные методы делятся на несколько типов, в зависимости от применяемого подхода:

· основанные на расщеплении: ;

· вариационного типа: ;

· проекционного типа: .

Среди итерационных методов:

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

· метод Гаусса -- Зейделя;

· метод релаксации;

· многосеточный метод;

· метод Монтанте;

· метод Абрамова (пригоден для решения небольших СЛАУ);

· метод обобщённых минимальных невязок;

· метод бисопряжённых градиентов;

· стабилизированный метод бисопряжённых градиентов;

· квадратичный метод бисопряжённых градиентов;

· метод квази-минимальных невязок/

1.3 Метод Гаусса

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

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

Рис. 1.3 - Алгоритм Гаусса для решения СЛАУ

Метод Гаусса требует O(n³) арифметических операций.

Этот метод опирается на теорему «о приведении матриц к ступенчатому виду».

Любую матрицу путем элементарных преобразований только над строками можно привести к ступенчатому виду.

Простейший случай

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

 (1.6)

Прямой ход:

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

Пример

Распишем, как можно решить систему, приведенную ниже, методом Гаусса:

(1.7)

Обнулим коэффициенты при x во второй и третьей строчках. Для этого прибавим к ним первую строчку, умноженную на и 1, соответственно:

 (1.8)

Теперь обнулим коэффициент при y в третьей строке, вычтя из нее вторую строку, умноженную на 4:

(1.9)

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

из третьего

из второго, подставив полученное z

из первого, подставив полученные z и y.

Таким образом исходная система решена.

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

В дополнение к аналитическому решению SLAU метод Гаусса также используется для:

Найти матрицу, обратную данному (матрице справа присваивается единица того же размера, что и исходная: [A | E], после которой A сводится к форме единичной матрицы по Гаусс-Иордану Метод, в результате, вместо исходной единичной матрицы.: [E | ])

Определение ранга матрицы (согласно следствию теоремы Кронекера-Капелли, ранг матрицы равен числу ее главных переменных)

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

Преимущества метода Гаусса:

Для матриц ограниченного размера, менее трудоемких по сравнению с другими методами.

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

Находит максимальное число линейно независимых уравнений.

Устойчивость метода Гаусса

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

В 1969 году Штрассен доказал, что большие матрицы можно умножить за время O( O(. Отсюда следует, что инверсия матриц и решение СЛАУ могут выполняться алгоритмами, асимптотически более быстрыми по порядку, чем метод Гаусса. Таким образом, для больших СЛАУ метод Гаусса не является оптимальным по скорости.

1.4 Вычисление первой производной

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

 (1.10)

где h - заданный шаг.

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

(1.11)

1.5 Решение нелинейных уравнений

Численное решение нелинейных (алгебраических или трансцендентных) уравнений вида:

заключается в нахождении значений x, удовлетворяющих (с заданной точностью) данному уравнению и состоит из следующих основных этапов:

Отделение (изоляция, локализация) корней уравнения.

Уточнение с помощью некоторого вычислительного алгоритма конкретного выделенного корня с заданной точностью.

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

При аналитическом способе отделения корней полезна следующая теорема:

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

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

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

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

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

1.6 Решение систем нелинейных уравнений

Систему нелинейных уравнений с n неизвестными можно записать в виде

или, более коротко, в векторной форме

где x - вектор неизвестных величин, f - вектор-функция

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

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

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

1.7 Метод Ньютона

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

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

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

 (1.16)

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна (), окончательная формула для такова:

(1.17)

С учетом этого функция определяется:

(1.18)

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

(1.19)

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

Геометрическая интерпретация

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

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

Пусть:

1. вещественная функция непрерывно дифференцируема на интервале ;

2. существует искомая точка ;

3. существуют такие, что для и для ;

4. точка такова, что .

Тогда формула итеративного приближения может быть выведена из геометрического смысла касательной следующим образом:

 (1.20)

где - угол наклона касательной прямой к графику f в точке

Следовательно (в уравнении касательной прямой полагаем ) искомое выражение для имеет вид:

(1.21)

Если то это значение можно использовать в качестве следующего приближения к .

Если то имеет место «перелет» (корень лежит рядом с границей ). В этом случае надо (воспользовавшись идеей метода половинного деления) заменять до тех пор. пока точка «не вернется» в область поиска .

Замечания.

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

2. случаи граничного (в точке a или в точке b) расположения искомого решения рассматриваются аналогичным образом;

3. с геометрической точки зрения равенство означает, что касательная прямая к графику f в точке - параллельна оси OX и при не пересекается с ней в конечной части;

4. чем больше константа и чем меньше константа из пункта 3 условий, тем для пересечение касательной к графику f и оси OX ближе к точке , т.е. тем ближе значение к искомой .

Итерационный процесс начинается с некоторого начального приближения , причем между и искомой точкой не должно быть других нулей функции f, т.е. «чем ближе к искомому корню , тем лучше». Если предположения о нахождении отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях.

Для предварительно заданных итерационный процесс завершается если

и (1.22)

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

Пример решения:

Методом Ньютона найти положительное решение системы нелинейных уравнений:

с точностью ? = 10^-4

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



Для выбора начального приближения применяем графический способ. Построив на плоскости в интересующей нас области кривые и (рис. 1.5), определяем, что положительное решение системы уравнений находится в квадрате:

Рис. 1.5 - Пересечение графиков функций

За начальное приближение примем

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

В рассматриваемом примере:

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

Результаты вычислений содержатся в таблице.

Таблица1. Результаты вычислений методом Ньютона

k
0	0.25000 0.75000	0.06875 0.04375	1.01250 0.02500	0.30000 0.97500	0.05391	0.04258	0.97969
1	0.19498 0.70654	0.00138 0.00037	1.00760 0.00734	0.28262 0.98050	0.00146	0.00038	0.98588
2	0.19646 0.70615	0.00005 0.00000	1.00772 0.00797	0.28246 0.98035	0.00005	0.00000	0.98567
3	0.19641 0.70615

2. Разработка программы

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

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

2.1 Язык программирования и среда разработки

Цели проекта в основном не ограничивали выбор языка программирования. Для их достижения могли быть выбраны такие языки как - C++, C#, Java. На компьютере, на котором велась работа над программой, имелась лицензия MicroSoft Visual Studio 2012 Ultimate и поэтому была выбрана именно эта среда разработки. Языком программирования был выбран C# в связи с наличием опыта работы на нем.

C# - это язык программирования с несколькими парадигмами, включающий сильные типизирующие, императивные, декларативные, функциональные, общие, объектно-ориентированные (на основе классов) и дисциплины программирования, ориентированные на компоненты. Он был разработан Microsoft в рамках своей инициативы.NET, а затем одобрен в качестве стандарта Ecma (ECMA-334) и ISO (ISO / IEC 23270: 2006). C # - один из языков программирования, предназначенных для инфраструктуры общего языка.

C# - универсальный объектно-ориентированный язык программирования. Его команда разработчиков возглавляет Андерс Хейлсберг. Самая последняя версия - C # 7.0, выпущенна в 2017 году вместе с Visual Studio 2017.

В стандарте ECMA перечислены следующие цели проектирования для C #:

· язык предназначен для простого, современного, универсального, объектно-ориентированного языка программирования;

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

· язык предназначен для использования при разработке программных компонентов, подходящих для развертывания в распределенных средах;

· переносимость очень важна для исходного кода и программистов, особенно тех, которые уже знакомы с C и C ++;

· поддержка интернационализации очень важна;

· C# предназначен для написания приложений как для хостинга, так и для встраиваемых систем, от очень больших, которые используют сложные операционные системы, вплоть до очень небольших функций;

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

По дизайну C # является языком программирования, который наиболее непосредственно отражает базовую инфраструктуру общего языка (CLI). Большинство его встроенных типов соответствуют типам значений, реализованным в рамках CLI. Однако спецификация языка не указывает требования к генерации кода компилятора: то есть он не указывает, что компилятор C # должен ориентироваться на Common Language Runtime или создавать общий промежуточный язык (CIL) или генерировать любой другой конкретный формат. Теоретически компилятор C # мог генерировать машинный код, например, традиционные компиляторы C ++ или Fortran.

C # поддерживает строго типизированные неявные объявления переменных с ключевым словом var и неявно типизированные массивы с ключевым словом new [], за которым следует инициализатор коллекции.

C # поддерживает строгий тип данных Boolean, bool. Выражения, которые принимают условия, такие как while и if, требуют выражения типа, реализующего истинный оператор, такой как булевский тип. Хотя C ++ также имеет тип Boolean, он может быть свободно преобразован в целые числа и из них, а выражения, такие как if (a), требуют только того, чтобы a был конвертирован в bool, что позволяет быть int или указателем. C # запрещает этот подход «целочисленный смысл истинного или ложного» на том основании, что принуждение программистов использовать выражения, которые возвращают точно bool, могут препятствовать некоторым типам ошибок программирования, например, if (a = b) (использование присваивания = вместо равенства ==, Которые, хотя и не являются ошибкой на C или C ++, все равно поймаются компилятором).

C # более безопасен по сравнению с C ++. Единственными неявными преобразованиями по умолчанию являются те, которые считаются безопасными, например, расширение целых чисел. Это выполняется во время компиляции, вовремя JIT и, в некоторых случаях, во время выполнения. Не происходит никаких неявных преобразований между булевыми и целыми числами, а также между членами перечисления и целыми числами (кроме литерала 0, который может быть неявно преобразован в любой нумерованный тип). Любое пользовательское преобразование должно быть явно помечено как явное или неявное, в отличие от конструкторов копирования C ++ и операторов преобразования, которые по умолчанию являются неявными.

C # имеет явную поддержку ковариации и контравариантности в родовых типах, в отличие от C ++, которая имеет некоторую степень поддержки контравариантности просто через семантику возвращаемых типов для виртуальных методов.

Члены перечисления размещаются в своем собственном объеме.

Язык C # не допускает глобальных переменных или функций. Все методы и члены должны быть объявлены внутри классов. Статические члены открытых классов могут заменять глобальные переменные и функции.

Локальные переменные не могут теневые переменные вложенного блока, в отличие от C и C ++.

Как и большинство языков программирования высокого уровня C# имеет набор элементов. К элементам относятся:

Алфавит - включает буквы (буквы латинского алфавита от a до z и от A до Z, а также знак подчеркивания), цифры (арабские цифры от 0 до 9), специальные символы (+ - * / =,<>:=.: ; и др.), пробелы, зарезервированные слова. C# имеет множество зарезервированных слов. Зарезервированные слова - это английские слова, указывающие компилятору на необходимость выполнения определенных действий.

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

Константы - целые, вещественные, шестнадцатеричные числа, логические константы, символы, строки символов, конструкторы множеств и признак неопределенного указателя null.

Выражения - константы, переменные, обращения к функциям, соединенные знаками операций и скобками.

Операции: унитарные (~), мультипликативные (*, /, &, |), аддитивные (+, -), отношения (==, !=, <=, >=, <, >).

2.2 DataGridView

Элемент управления DataGridView (рис. 2.1) предоставляет настраиваемую таблицу для отображения данных. Класс DataGridView позволяет настраивать ячейки, строки, столбцы и границы с помощью таких свойств, как DefaultCellStyle, ColumnHeadersDefaultCellStyle, CellBorderStyle и GridColor.

Рис 2.1 - Внешний вид DataGridView

Вы можете использовать элемент управления DataGridView для отображения данных с исходными данными или без них. Не указывайте dataGridView, используя свойство Rows и свойство Columns. Вы также можете использовать коллекцию String для доступа к объекту DataGridViewRow и использовать свойство DataGridViewRow.Cells для прямого чтения и записи значений ячеек. Indexer. Этот элемент также обеспечивает прямой доступ к ячейке.

Вместо назначения данных элементу управления вы можете выполнить свойства DataSource и DataMember, чтобы привязать DataGridView к источнику данных и автоматически заполнить данные. Дополнительные сведения см. В разделе Отображение данных с помощью элемента управления DataGridView в Windows Forms.

VirtualMode Когда вы используете виртуальные данные для виртуального объекта, отображается подмножество данных. Для виртуального режима требуется реализация, которая кэширует данные в элементе управления DataGridView.

2.3 Лексический анализатор

Лексический анализатор (англ. lexical analyzer, lexer; или «токенизатор» от tokenizer) -- это программа или часть программы, выполняющая лексический анализ. Схема лексического анализатора отображена на рисунке 2.2.

Лексер формирует первую фазу интерфейса компилятора в современной обработке. Обычно анализ выполняется за один проход.

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

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

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

Слово лексема в информатике определяется иначе, чем лексема в лингвистике. Лексема в информатике примерно соответствует тому, что можно назвать этим словом в лингвистике (термин слово в информатике имеет иное значение, чем слово в лингвистике), хотя в некоторых случаях он может быть более похож на морфему.

Лексема - это строка символов, которая образует синтаксическую единицу.

Некоторые авторы называют это токеном, используя «токен» как взаимозаменяемое слово, чтобы представить строку, являющуюся набором токенов, в структуру данных, которая возникает из-за перемещения этой строки в процесс создания токенов.

Рис. 2.2 - Схема лексического анализатора

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

Генераторы лексических анализаторов:

· lex - стандартный генератор в Unix

· Flex - альтернативный вариант классической утилиты lex

· JLex - генератор на Java

· ANTLR

2.4 Синтаксический анализатор

Синтаксимческий анамлиз (ил разбор, жарг. памрсинг ? англ. parsing) в лингвистике и информатике (рис. 2.3) -- это процесс анализа строки символов, как на естественном языке, так и на компьютерных языках, в соответствии с правилами формальной грамматики. Термин «парсинг» происходит от латинских пар (orationis), что означает часть (речи).

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

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



Рис. 2.3 - Пример разбора выражения с преобразованием его структуры из линейной в древовидную.

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

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

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

Чтобы разобрать данные естественного языка, исследователи должны сначала договориться о грамматике, которая будет использоваться. На выбор синтаксиса влияют как лингвистические, так и вычислительные проблемы; Например, в некоторых синтаксических системах используется лексическая функциональная грамматика, но в целом разбор по грамматикам этого типа, как известно, является NP-полным. Глоссария фразовой структуры, управляемая голосом, является еще одним лингвистическим формализмом, который был популярен в сообществе синтаксического анализа, но другие исследовательские усилия были сосредоточены на менее сложных формализмах, таких как та, которая используется в Penn Treebank. Малый синтаксический анализ направлен на поиск только границ основных составляющих, таких как фразы-существительные. Другой популярной стратегией для предотвращения лингвистических разногласий является анализ грамматики зависимости.

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

Алгоритмы анализа для естественного языка не могут полагаться на грамматику, обладающую «хорошими» свойствами, как с ручными грамматиками для языков программирования. Как уже упоминалось ранее, некоторые грамматические формализмы очень трудно анализировать вычислительно; В общем случае, даже если желаемая структура не является контекстно-свободным, для выполнения первого прохода используется какое-то контекстно-свободное приближение к грамматике. Алгоритмы, которые используют контекстно-свободные грамматики, часто опираются на какой-то вариант алгоритма CYK, обычно с некоторой эвристикой, чтобы отсечь маловероятные анализы, чтобы сэкономить время. Однако некоторые системы торгуют скоростью для точности с использованием, например, линейных версий алгоритма сдвига-сокращения. Несколько недавняя разработка - это анализ парсинга, в котором парсер предлагает некоторое большое количество анализов, а более сложная система выбирает лучший вариант.

2.5 Math Parser

Для синтаксического анализа и решения вводимых уравнений в программе используется сторонняя библиотека MathParser.dll. Это анализатор, написанный для программного языка C#, который использует RegEx (регулярные выражения) для решения математических выражений. Библиотека лицензирована и распространяется в соответствии с Code Project Open License. DLL поддерживает следующие возможности:

· Функции:

o abs

o acos

o asin

o atan

o cos

o cosh

o floor

o ln

o log

o sign

o sin

o sinh

o sqrt

o tan

o tanh

· Операторы: +, -, *,, ^, !

· Константы: Pi

Библиотека не поддерживает операционные системы, старше Windows Xp Service Pack 3.

2.6 Функциональная схема программы

При разработке программы «Решение нелинейных уравнений» была составлена блок-схема работы программы, в которой отражена логика работы приложения. Блок-схема изображена на рисунке 2.4



Рис. 2.4 - Блок-схема работы программы

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

2.7 Диаграмма классов UML

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

Рис. 2.5 - Диаграмма классов UML

Данная диаграмма показывает отношения между классами OneVariable, TwoVariable, ThreeVariable, LinearEquation и формами MainForm, Calculator. В форме MainForm есть такие поля, как Log - описывает ход решения системы линейных или нелинейных уравнений, Counter - количество итераций которое было произведено при поиске решения, сама форма описывает взаимодействие пользователя с программой и вызов соответствующих классов для решения уравнений.

Методы класса OneVariable:

private static void Derivative (string equation, double x, out double dfdx, out byte flag) - поиск первой производной по x.

· string equation - строка содержащая уравнение;

· double x - значение переменной x;

· out double dfdx - первая производная уравнения по переменной x;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет.

private static double Solve (string equation, double x, out byte flag) - возвращает значение уравнения, при заданном x.

· string equation - строка содержащая уравнение;

· double x - значение переменной x;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет.

public static void Newton (string equation, double x, out string[,] log, out byte flag, out byte counter) - решение нелинейного уравнения методом Ньютона.

string equation - строка содержащая уравнение;

double x - значение переменной x;

out string[,] log - подробное решение нелинейного уравнения;

out byte flag - возвращает номер ошибки, 0 - если ошибок нет;

out byte counter - количество итераций.

Методы класса TwoVariable:

private static void Derivative (string equation, double x, double y, out double dfdx, out double dfdy, out byte flag) - нахождение первой производной по x и по y.

· string equation - строка содержащая уравнение;

· double x - значение переменной x;

· double y - значение переменной y;

· out double dfdx - возвращает первую производную по x;

· out double dfdy - возвращает первую производную по y;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет.

private static double Solve (string equation, double x, double y, out byte flag) - возвращает значение уравнения при заданном x и y.

· string equation - строка содержащая уравнение;

· double x - значение переменной x;

· double y - значение переменной y;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет.

public static void Newton (string equation1, string equation2, double x, double y, out string[,] log, out byte flag, out byte counter) - решение системы нелинейных уравнений методом Ньютона.

· string equation1 - строка содержащая первое уравнение;

· string equation2 - строка содержащая второе уравнение;

· double x - начальное приближение переменной x;

· double y - начальное приближение переменной y;

· out string[,] log - подробное решение системы нелинейных уравнений;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет;

· out byte counter - количество итераций.

Методы класса ThreeVariable: private static void Derivative(string equation, double x, double y, double z, out double dfdx, out double dfdy, out double dfdz, out byte flag) - нахождение первой производной по x и по y.

· string equation - строка содержащая уравнение;

· double x - значение переменной x;

· double y - значение переменной y;

· double z - значение переменной z;

· out double dfdx - возвращает первую производную по x;

· out double dfdy - возвращает первую производную по y;

· out double dfdz - возвращает первую производную по z;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет.

private static double Solve (string equation, double x, double y, out byte flag) - возвращает значение уравнения при заданном x, y и z.

· string equation - строка содержащая уравнение;

· double x - значение переменной x;

· double y - значение переменной y;

· double z - значение переменной z;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет.

public static void Newton (string equation1, string equation2, string equation3, double x, double y, double z, out string[,] log, out byte flag, out byte counter) - решение системы нелинейных уравнений методом Ньютона.

· string equation1 - строка содержащая первое уравнение;

· string equation2 - строка содержащая второе уравнение;

· string equation3 - строка содержащая третье уравнение;

· double x - начальное приближение переменной x;

· double y - начальное приближение переменной y;

· double z - начальное приближение переменной z;

· out string[,] log - подробное решение системы нелинейных уравнений;

· out byte flag - возвращает номер ошибки, 0 - если ошибок нет;

· out byte counter - количество итераций.

Методы класса LinearEquation:

public static double[] Gauss(double[,] a, double[] b) - решение системы линейных уравнений методом Гаусса.

· double[,] a - матрица система;

· double[] b - столбец свободных членов;

· return - вектор искомых значений.

Методы класса Program:

static void Main() - инициализация работы программы.

Методы класса MainForm:

public MainForm() - вызов главного окна приложения.

private void SaveText_Click_1(object sender, EventArgs e) - сохранение в файл.

private void Reference_Click(object sender, EventArgs e) - вывод справки.

private void NumberOfEquations_ValueChanged(object sender, EventArgs e) - настройка числа нелинейных уравнений.

private void SolveEquations_Click(object sender, EventArgs e) - решение системы нелинейных уравнений.

private void ClearFirstDGV_Click(object sender, EventArgs e) - очищает поле вывода.

private void Calculator_Click(object sender, EventArgs e) - калькулятор функций.

private void LineEquation_Click(object sender, EventArgs e) - решение системы линейных уравнений.

private void ClearSecondDGV_Click(object sender, EventArgs e) - очищает поле вывода.

private void NumberOfLineEquations_ValueChanged(object sender, EventArgs e) - настройка числа линейных уравнений.

Методы класса Form2:

public Form2() - окно для решения выражений.

private void button1_Click(object sender, EventArgs e) - решение выражения введенного в текстовое поле.

2.8 Работа программы

При запуске программы перед пользователем открывается окно, которое сразу предлагает решить нелинейное уравнений с одной неизвестной (рис. 2.6).

Рис. 2.6 - Окно решения нелинейных уравнений

После нажатия на кнопку «Решить» Если данные введены корректно произойдет поиск решения и вывод результатов в специальное поле снизу (рис. 2.7).

Рис. 2.7 - Результат решения уравнения

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

Рис. 2.8 - Система уравнений с двумя неизвестными

Если пользователь допустил ошибку при введении системы уравнений, то при нажатии кнопки решить появится сообщение о том, что допущена ошибка (2.9).



Рис. 2.9 - Сообщение об ошибке

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



Рис. 2.10 - Решение системы линейных уравнений

Если у пользователя появились вопросы о том, какие функции можно использовать в программе, на верхней панели есть кнопка «Справка», при нажатии на которую всплывет меню подсказок показанное на рисунке 2.11.



Рис. 2.11 - Окно справки

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

Рис. 2.12 - Окно калькулятора

Пользователь может сохранить полученный результат в Excel файл. На рисунке 2.13 изображен процесс сохранения результатов, полученных ранее (см. рис. 2.8), а на рисунке 2.14 полученный файл.

Рис. 2.13 - Диалог сохранения

Рис. 2.14 - Результат сохранения файла

2.9 Перспективы разработки

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

Рис. 2.15 - Область для отображения графиков функций

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

Рис. 2.16 - Построение графика функции

математический программирование уравнение файл

Заключение

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

Разработанная программа полностью соответствует заданию бакалаврской работы. В приложении реализован функционал:

...