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

 

Содержание

 

Введение

1 Теоретические сведения 4

1.1 Решение системы  алгебраических линейных уравнений  методом Гаусса 4

1.2 Вычисление обратной матрицы методом Гаусса 8

1.3 Вычисление определителя  методом Гаусса 9

2 Практическая часть 11

2.1 Декомпозиция задачи 11

2.2 Схема взаимодействия  интерфейсных форм 12

2.3 Схема взаимодействия  модулей 14

2.4 Описание процедур  и функций 15

2.5 Обоснование выбора  структуры представления данных 15

2.6 Руководство пользователю 15

2.7 Тестирование 19

Заключение 30

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

Приложение А - Символьная схема алгоритма  32

Приложение Б – Код программы 41             

Введение

 

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

Наиболее известным  и популярным способом решения СЛАУ является метод Гаусса. Целью данной курсовой работы является следующее: исследовать область применения метода Гаусса к решению различных прикладных задач и

разработать программу «Решение задач методом Гаусса», выполняющую следующие операции:

1) Решение СЛАУ методом Гаусса

2) Нахождение обратной матрицы методом Гаусса

3) Вычисление определителей методом Гаусса

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретическая часть.

 

1. Решение систем алгебраических линейных уравнений методом Гаусса.

 

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

                (1)

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

Числа называют коэффициентами СЛАУ. Их номеруют двумя индексами: номером уравнения  i и номером неизвестного j. Действительные числа   называют свободными членами уравнений.

СЛАУ называют однородной, если . Иначе ее называют неоднородной.

Решением СЛАУ, да и вообще  всякой системы уравнений, называют такой набор неизвестных

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

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

Если СЛАУ имеет решение, и притом единственное, то ее называют определенной, а если решение неединственное – то неопределенной. При m=n, т.е. когда системе 1 количество уравнений совпадает с количеством неизвестных, СЛАУ называют квадратной.

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

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

Пусть дана система линейных алгебраических уравнений с n неизвестными.

                 (2)

обозначим через 

 А = 

матрицу коэффициентов  системы (2) , через

 b = - столбец ее свободных членов, и через

 x = - столбец из неизвестных (свободный вектор)

тогда система (2) может  быть записана в виде матричного уравнения Ax=b.

При решении СЛАУ методом  Гаусса всевозможные преобразования производят не над уравнениями (2), а над так  называемой расширенной матрицей системы, которая получается путем добавления к основной матрице А столбца свободных членов b.

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

 

   =                    (3)

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

  =             (4)

В общем виде этот процесс можно  записать так:

2-я строка = 2-я строка – М*1-я строка

3-я строка = 3-я строка – М*1-я строка

...

i-я строка =  i-я строка – М*1-я строка

...

n-я строка = n-я строка – М*1-я строка

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

Так  как с целью данных преобразований является обнуление первого элемента строки, то М выбирается из условия:

М =

Элементы третьей строки и коэффициент М можно рассчитать аналогично:

М =

Таким образом преобразование i-й строки будет происходить следующим образом:

Коэффициент М для i-й строки выбирается из условия:

и равен

  М =

После проведения подобных преобразований для всех строк матрица (3) примет вид:

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

Заметим, что если в матрице (3) на главной диагонали встретиться элемент , равный нулю, то расчет коэффициента

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

В результате выполнения прямого метода Гаусса матрица (3) преобразуется в  матрицу (4), а система уравнений (2) будет иметь следующий вид:

(5)

Решение системы (5) называют обратным ходом метода Гаусса.

Последнее n-е уравнение системы (5) имеет вид:

.

Тогда, если

,

то 

.

В случае, если

 и  ,

то система (5), а следовательно  и система (2)  имеет бесконечное  множество решений.

При

 и 

система (5) , а значит, и система (2) решения не имеет.

Предпоследнее (n-1)-е уравнение системы (5) имеет вид:

.

Значит 

Следующее (n-2)-е уравнение системы будет выглядеть так:

.

Отсюда имеем

или

 

 

 

Таким образом, формула  для вычисления i-го значения x будет иметь вид:

 

1.2 Вычисление обратной матрицы методом Гаусса.

 

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

        (6)

Необходимо найти матрицу  , которая является обратной к матрице А:

          (7)

Матрица (7) будет обратной к матрице (6) , если выполняется соотношение

,

где Е – это единичная  матрица, или более подробно:

         (8)

Результат перемножения матриц из соотношения (8) можно представить  поэлементно в виде n-го числа систем линейных уравнений. Умножение матрицы (6) на первый столбец матрицы (7) даст первый столбец единичной матрицы:

  .

Система полученная в  результате умножения матрицы на i-й столбец матрицы (7) , будет выглядеть следующим образом:

 

Понятно, что n-я система будет иметь вид:

Решением каждой из приведенной  выше систем будет i-й столбец обратной матрицы. Количество систем равно размерности обратной матрицы. Для решения систем линейных алгебраических уравнений можно воспользоваться методом Гаусса.

 

1.3 Вычисление определителя методом Гаусса.

 

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

.

Преобразование матрицы (3) к виду (4) можно осуществить  с помощью прямого хода Гаусса.

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

 

2 Практическая часть

 

2.1 Декомпозиция задачи 

 

Декомпозиция задачи представлена на рисунке 2.1.1

 

 

         Рисунок  2.1.1 – Декомпозиция задачи

 

 

 

 

 

 

       

 

 

 

 

 

 

                                             

 

 

 

 

 

 

 

 

 

МЕНЮ ОПЕРАЦИЙ   1.Решить систему линейных уравнений методом Гаусса.   2.Найти обратную матрицу.   3.Вычислить определитель матрицы.   4.Выход.

  2.2 Схема взаимодействия интерфейсных форм

 

Интерфейсные формы  схематически представлены на рисунках 2.2.1-2.2.4

 

 

 

 

 

 

 

 

 

 

Рисунок 2.2.1 – Схематическое изображение формы «Меню операций»

 

Введите количество переменных ___   Введите матрицу коэффициентов                          Введите вектор свободных членов                                       РЕШИТЬ   Вектор свободных членов

 

Рисунок 2.2.2 – Схематическое  изображение формы 1

 

Введите количество переменных ___     Введите квадратную матрицу                                                    НАЙТИ      Обратная матрица

 

Рисунок 2.2.3 – Схематическое  изображение формы 2

 

Введите строк и столбцов  ___     Введите квадратную матрицу                                                    НАЙТИ   Определитель матрицы равен __

 

Рисунок 2.2.4 – Схематическое  изображение формы 3

 

Взаимодействие представленных выше интерфейсных форм описано в  виде диаграммы переходов состояний интерфейса программы (рисунок 2.2.5).