Программная реализация методов решения системы линейных уравнений - Дипломная работа

Данный дипломный проект создан для решения систем линейных алгебраических уравнений, методами линейной алгебры. В специальной части изложены основные аспекты теории по теме линейная алгебра, блок-схема алгоритма программы, результаты ручного просчета, листинг программы и результаты тестирования программы. Линейная алгебра - часть алгебры, изучающая векторные (линейные) пространства и их подпространства, линейные отображения (операторы), линейные, билинейные, и квадратичные функции на векторных пространствах. Линейная алгебра, численные методы - раздел вычислительной математики, посвященный математическому описанию и исследованию процессов численного решения задач линейной алгебры.Среди задач линейной алгебры наибольшее значение имеют две: решение системы линейных алгебраических уравнений определение собственных значений и собственных векторов матрицы. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым.Систему [1] вида принято называть системой n линейных алгебраических уравнений (СЛАУ) с n неизвестными. При этом произвольные числа aij (i = 1, 2,…, n; j = 1, 2,…, n) называются коэффициентами системы (коэффициентами при неизвестных), а числа bi (i = 1, 2,…, n) - свободными членами. Решением СЛАУ (1) называется совокупность чисел xi (i = 1, 2,…, n), при подстановке которых в систему каждое из ее уравнений обращается в тождество.Пусть дана система линейных уравнений: Рассмотрим матрицу, составленную из коэффициентов при неизвестных: Свободные члены и неизвестные можно записать в виде матрицы столбцов: Тогда, используя правило умножение матриц, эту систему уравнений можно записать так: или A·x = b. Матрица А коэффициентов при неизвестных называется главной матрицей системы. Иногда рассматривают также расширенную матрицу системы, т. е. главную матрицу системы, дополненную столбцом свободных членов, которую записывают в следующем виде: Любую линейную систему уравнений можно записать в матричном виде. Например, пусть дана система: Эта система из двух уравнений с тремя неизвестными - x, y,. В высшей математике можно рассматривать системы из очень большого числа уравнений с большим количеством неизвестных и поэтому неизвестные принято обозначать только буквой х, но с индексами: Запишем эту систему в матричном виде: Здесь главная матрица системы: Расширенная матрица будет иметь вид: Решения матричных уравнений.При решении систем линейных уравнений по методу Крамера последовательно выполняется следующий алгоритм: 1. Записывают систему в матричном виде (если это еще не сделано). Иначе рассматривают вопрос о разрешимости данной системы (имеет бесчисленное множество решений или не имеет решений). Решить по методу Крамера систему из трех уравнений с тремя неизвестными: РешениеПри решении систем линейных уравнений по методу Крамера используются формулы, в которых участвуют как главный, так и дополнительные определители системы: Напомним, что главным определителем системы называется определитель главной матрицы системы, составленной из коэффициентов при неизвестных: Если в главном определителе системы заменить поочередно столбцы коэффициентов при x1, x2,...xn на столбец свободных членов, то получим n дополнительных определителей (для каждого из n неизвестных): При этом важен вопрос о разрешимости данной системы, который решается сравнением главного и дополнительных определителей системы с нулем: Метод Гаусса - прямой и обратный ход. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными: Будем считать, что a11 ? Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а11. В результате получим матрицу: Т. е. первая строка осталась без изменений, а в столбце под а11 на всех местах оказались нули. Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент б22.Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхне-треугольной матрицей.Программное обеспечение, установленное на компьютере: u Операционная система Windows XP Professional u Визуальная среда разработки приложений Borland Delphi 6 u Язык программирования Турбо-Паскаль 7.0. Программа написана на языке Object Pascal с использованием интегрированной среды разработки приложений Borland Delphi 6. Delphi использует структурный объектно-ориентированный язык (Object Pascal), который сочетает с одной стороны выразительную мощь и простоту программирования, характерную для языков 4GL, а с другой стороны эффективность языка 3GL. Действительно, все в Delphi написано на нем же, поэтому разработчики имеют доступ к тем же объектам и инструментам, которые использовались для создания среды разработки. В результате нет никакой разницы между объектами, поставляемы

Содержание

Введение

Раздел 1. Специальная часть

1.1 Системы линейных алгебраических уравнений

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

1.3 Матричный метод решения систем линейных уравнений

1.4 Решение задачи математическим методом

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

1.6 Характеристика ЭВМ, ОС и алгоритмического языка программирования

1.7 Листинг программы

Раздел 2. Охрана труда

2.1 Требования безопасности перед началом работы на персональном компьютере

2.2 Требования безопасности во время работы на персональном компьютере

2.3 Требования безопасности после окончания работы на персональном компьютере

Раздел 3. Экономическая часть

3.1 Расчет трудоемкости разработки программы

3.2 Расчет себестоимости программы

3.2.1 Расчет расходных материалов

3.2.2 Расчет заработной платы с начислениями

3.2.3 Расчет расходов на электроэнергию

3.2.4 Расчет цеховых, общехозяйственных и внепроизводственных расходов

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

3.3 Расчет отпускной цены

3.4 Расчет показателей экономической эффективности программного продукта

Заключение

Иллюстрация работы программы

Список литературы

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

Дипломный проект состоит из трех частей: 1. Специальная часть;

2. Охрана труда;

3. Экономическая часть;

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

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

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

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

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

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

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

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

При решении систем линейных уравнений по методу Крамера используются формулы, в которых участвуют как главный, так и дополнительные определители системы: Напомним, что главным определителем системы называется определитель главной матрицы системы, составленной из коэффициентов при неизвестных: Если в главном определителе системы заменить поочередно столбцы коэффициентов при x1, x2,...xn на столбец свободных членов, то получим n дополнительных определителей (для каждого из n неизвестных): При этом важен вопрос о разрешимости данной системы, который решается сравнением главного и дополнительных определителей системы с нулем: Метод Гаусса - прямой и обратный ход.

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными: Будем считать, что a11 ? 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования: C2-(a21/a11)*C1, ...

Cm-(am1/a11)*C1, т.е. Ci-(ai1/a11)*C1, i = 2, 3, ..., m.

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

В результате получим матрицу: Т. е. первая строка осталась без изменений, а в столбце под а11 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А - aij, где I = j.

Повторим наши элементарные преобразования, но уже для элемента б22.

C1-(а12/б22)*С2, ...

Cm-(бм2/б22)*С2, т.е. Ci-(бі2/б22)*С2, i = 3, ..., m.

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

Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее - треугольному виду. Т. е. под главной диагональю не окажутся все нули: Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид: гmn*xn = дм.

Отсюда легко можно найти значение первого корня - xn = дм/гmn.

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1-ого корня.

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

Пример 1

Рассмотрим систему уравнений: Главный определитель данной системы: Д = [1*(-4)*(-2) 2*2*1 (-1)*(-1)*(-1)]-[1*(-4)*(-1) 2*(-1)*(-2) 2*(-1)*1] = [8 4-1]-[4 4-2] = 11-6 =5, т. е. Д ? 0.

Т. е. система определена и разрешима. Решим ее по методу Гаусса.

Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы: Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C2-(a21/a11)*C1 = C2-(2/1)*C1 = C2-2*C1: Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3-(a31/a11)*C1 = C3-(-1/1)*C1 = C3 C1: Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C3-(a32/a22)*C2 = C3-(1/-2)*C2 = C3 1/2C2: Таким образом, проведя прямой ход метода Гаусса, мы получили расширенную матрицу системы, приведенную к верхне-треугольному виду: Эта матрица эквивалентна системе: Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х3: -5/2x3 = 3/2, x3 = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.

Корень x3 = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x2-3x3 = 1): -2x2-3(-3/5) = 1, -2x2 9/5 = 1, -2x2 = 1-9/5, -2x2 = -4/5, x2 = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.

Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1-x2 x3 = 0): x1-2/5 (-3/5) = 0, x1-5/5 = 0, x1 = 5/5 = 1.

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

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

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