Курсовая работа (т): Решение систем линейных уравнений. Метод Гаусса

Решение систем линейных уравнений. Метод Гаусса

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

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

Кафедра «Гидропневмоавтоматика и гидропневмопривод»

Пояснительная записка к курсовой работе

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

Тема:

Решение систем линейных уравнений. Метод Гаусса

Выполнил: Швец Александр

студент группы №10105213

Руководитель: Ермилов С.В.

Минск - 2014

РЕФЕРАТ

Пояснительная записка 28 с., 3 рис., 10 источников.

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

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

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

В процессе работы был изучен метод Гаусса, его особенности, алгоритм данного метода и возможные трудности его реализации.

Отчёт работы оформлен с использованием текстового редактора «Microsoft Word».

Применяется для решения СЛАУ в вычислительной технике.

СОДЕРЖАНИЕ

Введение

1. Цель и задачи моделирования

2. Математическое описание объекта моделирования, начальные и граничные условия

3. Алгоритм реализации задачи

4. Порядок выполнения работы

5. Использование модуля CRT

6. Таблицы индификаторов

7. Результаты расчёта и их анализ

Список использованных источников

ВВЕДЕНИЕ

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

Для решения СЛАУ применяют в основном два класса методов: прямые и итерационные. Прямые методы дают алгоритм, по которому можно найти точное решение СЛАУ. И если бы точность была абсолютной, они бы нашли его. Реальная ЭВМ, естественно, работает с погрешностью, поэтому решение будет приближённым. Итерационные методы основаны на использовании повторяющегося процесса и позволяют получить решение в результате последовательных приближений. Прямые методы являются универсальными и применяются для решения систем сравнительно невысокого порядка (п ~ 200). Итерационные методы выгодно использовать для СЛАУ высокого порядка со слабо заполненными матрицами.

Данная курсовая работа посвящена решению систем линейных алгебраических уравнений (СЛАУ) методом Гаусса. Этот метод решения относится к прямым методам. Системами линейных алгебраических уравнений являются системы вида:

 (1)

Данная нам система имеет вид:

, (2)

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

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

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

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

1. Цель и задачи моделирования

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

К главным целям моделирования я бы отнёс следующие:

) научится формализации задач при моделировании;

) научится строить и использовать математические алгоритмические модели для решения математических задач;

) освоить приёмы работы с программой «Pascal»;

) закрепить и расширить знания и умения, полученные при изучении курсов «математика», «информатика».

Из задач моделирования данной программы я бы выделил:

) формирование представления о компьютерном моделировании математических задач и их решений;

) закрепление навыков и знаний, полученных при изучении курса «Информатика»;

) получение необходимого минимума знаний аналитических и численных (приближенных) методах при реализации математических моделей конкретных задач;

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

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

2. Математическое описание объекта моделирования, начальные и граничные условия

Система m линейных алгебраических уравнений с n неизвестными (СЛАУ) в линейной алгебре - это система уравнений вида:

 (2.1)

Здесь  - количество уравнений, а  - количество неизвестных. x₁,x₂, …, x_n - неизвестные, которые надо определить. a₁₁, a₁₂, …, a_{m n} - коэффициенты системы - и b₁, b₂, … b_m - свободные члены - предполагаются известными. Индексы коэффициентов (a_{i j}) системы обозначают номера уравнения i и неизвестного j, при котором стоит этот коэффициент, соответственно.

Система (2.1) называется однородной, если все её свободные члены равны нулю (b₁ = b₂ = … = b_m = 0), иначе - неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (2.1) - совокупность n чисел c₁, c₂, …, c_n, таких что подстановка каждого c_i вместо x_i в систему (2.1) обращает все её уравнения в тождества <https://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D0%B6%D0%B4%D0%B5%D1%81%D1%82%D0%B2%D0%BE_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)>.

Система (2.1) называется совместной <https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D0%B2%D0%BC%D0%B5%D1%81%D1%82%D0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9>, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения.

Совместная система вида (2.1) может иметь одно или более решений.

Из этого выходит главный критерий совместимости - Теорема Кронекера-Капелли:

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

Доказывается она следующим образом:

Необходимость.

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

Достаточность.

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

Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Плюсы метода заключаются в следующем:

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

) Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.

Решения c₁, c₂, …, c_n и c₁, c₂, …, c_m совместной системы вида (2.1) называются различными, если нарушается хотя бы одно из равенств:

₁ = c₁, c₂ = c₂, …, c_n = c_m.

Совместная система вида (2.1) называется определённой <https://ru.wikipedia.org/w/index.php?title=%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%91%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9&action=edit&redlink=1>, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется неопределённой.

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

 или . (2.2)

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

Основные методы решения СЛАУ следующие:

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

) Метод Крамера

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

В данной работе мы воспользуемся первым методом, а именно - методом Гаусса.

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

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

 (2.3)

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

 (2.4)

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

Тогда переменные  называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число  то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.

Пусть . Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом  (,  где  - номер строки):

 (2.5)

 (2.4)

Если свободным переменным системы (2.3) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (2.2), то по теореме об эквивалентности при элементарных преобразованиях системы (2.2) и (2.3) эквивалентны, то есть множества их решений совпадают.

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

3. Алгоритм реализации задачи

Алгоритм реализации задачи рассмотрим на примере. Допустим, необходимо решить СЛАУ:

 (3.1)

где х_к - неизвестные величины;  - заданные элементы расширенной матрицы системы уравнений.

Из первого уравнения системы (3.1) выражаем неизвестное