Численное решение системы линейных алгебраических уравнений методом Гаусса
Содержание
Введение
1. Постановка задачи
2. Математические и алгоритмические основы решения задачи
2.1 Описание метода
2.2 Алгоритм
3. Функциональные модели и блок-схемы решения задачи
4. Программная реализация решения задачи
5. Пример выполнения программы
Заключение
Список использованных источников и литературы
Введение
Математические модели процессов часто или сразу строятся как линейные алгебраические системы или сводятся к ним. Необходимость решения СЛАУ возникает при вычислении определителя, обращения матриц, нахождении собственных чисел.
Методы численного решения системы Ax=b, где A - матрица n x n, det A ≠ 0, x - искомый вектор, b - заданный вектор, разделяются на два класса: прямые и итерационные. Прямые методы позволяют находить решение системы за конечное число арифметических операций. Если операции реализуются точно, то решение будет точным (прямые методы еще называют точными). На деле при вычислении на ЭВМ прямые методы не приводят к точному решению вследствие погрешностей округления.
Итерационные методы позволяют найти точное решение путем бесконечного повторения единообразных действий т.е. решение, которое реально можно получить, будет приближенным.
1. Постановка задачи
Требуется решить систему линейных алгебраических уравнений с вещественными коэффициентами вида
a11x1 + a12x2 + … + a1nxn = b1,a21x2 + a22x2 + … + a2nxn = b2,... ... ...
an1x1 + an2x2 + … + annxn = bn
с помощью метода исключения Гаусса.
Пример 1. Покажем, как методом Гаусса можно решить следующую систему:
>
>
Обнулим
коэффициенты при x во
второй и третьей строчках. Для этого
домножим их на
и 1 соответственно и сложим с первой
строкой:
>
>
Теперь обнулим коэффициент при y в третьей строке, домножив вторую строку на - 6 и сложив с третьей:
>
>
В результате мы привели исходную систему к треугольному виду, тем самым закончив первый этап алгоритма.
На втором этапе разрешим полученные уравнения в обратном порядке.
Имеем:
z = - 1 из третьего;
y = 3 из второго, подставив полученное z
x = 2 из первого, подставив полученные z и y.
Таким образом исходная система решена.
Пример 2. Покажем, как методом Гаусса можно решить следующую систему:
>
>
Составим расширенную матрицу системы.
>
>
>.>
Таким образом, исходная система может быть представлена в виде:
>
>,
откуда получаем: x =1, y
= 2, z = 3.
2. Математические и алгоритмические основы решения задачи
2.1 Описание метода
Метод Гаусса - классический метод решения системы линейных алгебраических уравнений (СЛАУ). Состоит в постепенном понижении порядка системы и исключении неизвестных.
Пусть исходная система выглядит следующим образом
,
.
(1)
Тогда согласно свойству элементарных преобразований над строками эту систему можно привести к трапециальному виду:
,
.
Переменные
называются главными переменными. Все
остальные называются свободными.
Если
,
то рассматриваемая система несовместна.
Предположим,
что
.
Перенесём
свободные переменные за знаки равенств
и поделим каждое из уравнений системы
на свой коэффициент при самом левом
,
i=1,…,r. (где
i - номер строки):
где i=1,…,r, k=i+1, …, n.
Если свободным переменным системы (2) придавать все возможные значения и вычислить через них главные переменные, то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях полученное нами решение является решением системы (1).
Следствия:
Если в совместной системе все переменные главные, то такая система является определённой.
Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной.
Условие совместности:
Упомянутое
выше условие
может быть сформулировано в качестве
необходимого и достаточного условия
совместности:
Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).
2.2 Алгоритм
Численное решение систем вида:
(3)
или Ax=b методом Гаусса заключается в последовательном исключении неизвестных. Система (3) поэтапно приводится к треугольному виду. Сначала исключается x1 из 2-го, 3-го,..., n-го уравнений, для этого необходимо сложить уравнения 2,3,...,n с первым уравнением, умноженным на - a21/a11, - a31/a11,..., - an1/a11 соответственно.
(4)
Потом x2 из 3-го,..., n-го умножением второго уравнения на - a¹32/a¹22, - a¹42/a¹22,..., - a¹n2/a¹22 и сложением с 3,4,. n уравнениями.
И дальше по аналогии система приводится к треугольному виду:
.
Процесс приведения системы к треугольному виду называется прямым ходом. Общие формулы для прямого хода:
,
,
где k =1,...,n - 1; i,j = k+1,...,n.
Для нахождения решения теперь необходимо вычислить неизвестные, начиная с n-го уравнения. Процесс вычисления значений неизвестных называется обратным ходом.
На каждом этапе xk находится по формуле
,
где k = n, n-1,...,
3. Функциональные модели и блок-схемы решения задачи
Функциональные модели и блок-схемы решения задачи представлены на рисунках 1 и 2.
Условные обозначения:
I, J - временные переменные;
A - временная матрица;
B - массив свободных членов матрицы;
X - массив решений;
NUMB - временная переменная;
MATRIX - матрица для расчета;
ROW_COL, R_C, LEN - количество строк и столбцов в матрице;
ARRAY_B - рабочий массив свободных членов.
Рисунок 1 - Функциональная модель решения задачи для функции PRINT_RES
Рисунок 2 - Блок-схема решения задачи для функции METHOD_GAUS
4. Программная реализация решения задачи
; ROW_COL - КОЛИЧЕСТВО СТРОК И СТОЛБЦОВ МАТРИЦЫ
(SETQ ROW_COL 0)
(SETQ INPUT (OPEN " D: \MATRIX. TXT": DIRECTION: INPUT))
(SETF ROW_COL (READ INPUT))
; MATRIX - МАТРИЦА ДЛЯ ВЫЧИСЛЕНИЯ
(SETQ MATRIX (MAKE-ARRAY (LIST ROW_COL ROW_COL): ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
(SETF MATRIX (READ INPUT))
; ПОЛУЧАЕМ СВОБОДНЫЕ ЧЛЕНЫ
(SETQ B (MAKE-ARRAY ROW_COL: ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
; ПОЛУЧАЕМ МАТРИЦУ
(SETQ B (READ INPUT))
(CLOSE INPUT)
(DEFUN METHOD_GAUS (MATRIX ARRAY_B R_C)
; ОБЪЯВЛЛЯЕМ ПЕРЕМЕННЫЕ
; ИТЕРАТОРЫ
(DECLARE (SPECIAL I))
(DECLARE (SPECIAL J))
(DECLARE (SPECIAL A))
(DECLARE (SPECIAL B))
(DECLARE (SPECIAL X))
; ВРЕМЕННАЯ ПЕРЕМЕННАЯ
(DECLARE (SPECIAL NUMB))
; A - ВРЕМЕННАЯ МАТРИЦА
(SETQ A (MAKE-ARRAY (LIST R_C R_C): ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
(SETF A MATRIX)
; В - МАТРИЦА СВОБОДНЫХ ЧЛЕНОВ
(SETQ B (MAKE-ARRAY R_C: ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
(SETF B ARRAY_B)
; X - МАССИВ РЕШЕНИЙ
(SETQ X (MAKE-ARRAY R_C: ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
; ВЫПОЛНЯЕМ ПРЕОБРАЗОВАНИЯ СТРОК
(DO
( (P 0))
( (>= P ( - R_C 1)))
(DO
( (I (+ P 1)))
( (>= I R_C))
(SETQ NUMB (/ (AREF A I P) (AREF A P P)))
(DO
( (J P))
( (>= J R_C))
(SETF (AREF A I J) ( - (AREF A I J) (* (AREF A P J) NUMB)))
(SETQ J (+ J 1))
)
(SETF (AREF B 0 I) ( - (AREF B 0 I) (* (AREF B 0 P) NUMB)))
(SETQ I (+ I 1))
)
(SETQ P (+ P 1))
)
(SETF (AREF X ( - R_C 1)) (FLOAT (/ (AREF B 0 ( - R_C 1)) (AREF A ( - R_C 1) ( - R_C 1)))))
; ПОЛУЧИЛИ СТУПЕНЧАТУЮ МАТРИЦУ
; НАХОДИМ X
(DO
( (I ( - R_C 2)))
( (< I 0))
(SETQ NUMB 0)
(DO
( (J (+ I 1)))
( (>= J R_C) X)
(SETQ NUMB (+ NUMB (* (AREF A I J) (AREF X J))))
(SETQ J (+ J 1))
)
(SETF (AREF X I) (FLOAT (/ ( - (AREF B 0 I) NUMB) (AREF A I I))))
(SETQ I ( - I 1))
)
X
)
; ПРИМЕНЯЕМ МЕТОД ГАУССА ДЛЯ ЗАДАННОЙ МАТРИЦЫ
(METHOD_GAUS MATRIX B ROW_COL)
; ФУНКЦИЯ ВЫВОД МАССИВА X
(DEFUN PRINT_RES (MATR_X LEN)
(DO
( (I 0))
( (>= I LEN))
(PRINT (LIST 'X I '= (AREF MATR_X I)) OUTPUT)
(SETQ I (+ I 1))
)
)
; ВЫВОД МАССИВА X В ФАЙЛ
(SETQ OUTPUT (OPEN " D: \RESULT. TXT": DIRECTION: OUTPUT))
(PRINT_RES X ROW_COL)
(TERPRI OUTPUT)
(CLOSE OUTPUT)
5. Пример выполнения программы
Пример 1.
Рисунок 3 - Входные данные
Рисунок 4 - Выходные данные
Пример 2.
Рисунок 5 - Входные данные
Рисунок 6 - Выходные данные
Пример 3.
Рисунок 7 - Входные данные
Рисунок 8 - Выходные данные
Заключение
Помимо аналитического решения СЛАУ, метод Гаусса также применяется для нахождения матрицы, обратной к данной, определения ранга матрицы, численного решения СЛАУ в вычислительной технике.
Итогом работы можно считать созданную функциональную модель решения системы линейных алгебраических уравнений методом Гаусса. Данная модель применима к невырожденным матрицам с одинаковым количеством строк и столбцов. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
Список использованных источников и литературы
Васильев Ф.П. Численные методы решения экстремальных задач. [Текст] / Ф.П. Васильев - М.: Наука, 2002. C.415.
Калиткин Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. - М.: Питер, 2001. С.504.
Кнут Д.Э. Искусство программирования. Основные алгоритмы [Текст] / Д.Э. Кнут. - М.: Вильямс, 2007. Т.1. - 712 с.
Метод Гаусса [Электронный ресурс] - Режим доступа: http://www.wikipedia.org/wiki/Метод_Гаусса.
Степанов П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А. Степанов, А.В. Бржезовский. - М.: ГУАП, 2003. С.79.