Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Численное решение системы линейных алгебраических уравнений методом Гаусса

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 25.01.2010
Размер файла 527,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

2

Содержание

  • Введение
    • 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 - Выходные данные

Заключение

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

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

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

1. Васильев Ф.П. Численные методы решения экстремальных задач. [Текст] / Ф.П. Васильев - М.: Наука, 2002. C.415.

2. Калиткин Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. - М.: Питер, 2001. С.504.

3. Кнут Д.Э. Искусство программирования. Основные алгоритмы [Текст] / Д.Э. Кнут. - М.: Вильямс, 2007. Т.1. - 712 с.

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

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


Подобные документы

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

    Системы линейных алгебраических уравнений. Код программы для решения систем линейных алгебраических уравнений. Математические и алгоритмические основы решения задачи методом Гаусса. Программная реализация решения. Алгоритмы запоминания коэффициентов.

    лабораторная работа [23,5 K], добавлен 23.09.2014

  • Численное решение системы линейных уравнений с помощью метода исключения Гаусса с выбором главного элемента по столбцу

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

    курсовая работа [428,9 K], добавлен 25.01.2010

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

    Системы линейных алгебраических уравнений. Матричный метод решения систем линейных уравнений. Решение задачи математическим методом. Блок-схема алгоритма и листинг программы. Расчет трудоемкости разработки программы. Расчет себестоимости и цены программы.

    дипломная работа [144,8 K], добавлен 25.04.2012

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

    Алгоритм решения систем линейных уравнений методом Гаусса, его этапы. Система уравнений для определения коэффициентов сплайна, представляющая собой частный случай систем линейных алгебраических уравнений. Программная реализация, тестовый пример.

    курсовая работа [431,8 K], добавлен 15.06.2013

  • Реализация на языке программирования Си решения системы линейных уравнений методом Гаусса

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

    курсовая работа [153,9 K], добавлен 18.02.2013

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

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

    лабораторная работа [164,3 K], добавлен 02.10.2013

  • Особенности вычисления определителя матрицы

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

    контрольная работа [455,2 K], добавлен 18.01.2010

  • Сравнительный анализ численных методов

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

    курсовая работа [1,6 M], добавлен 20.01.2010

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

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

    курсовая работа [1,2 M], добавлен 15.06.2013

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

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

    курсовая работа [657,1 K], добавлен 09.01.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены