Xreferat.com » Рефераты по информатике и программированию » Численное решение системы линейных алгебраических уравнений методом Гаусса

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

Содержание


Введение

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 с.

Метод Гаусса [Электронный ресурс] - Режим доступа: /wiki/Метод_Гаусса.

Степанов П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А. Степанов, А.В. Бржезовский. - М.: ГУАП, 2003. С.79.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: