Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Численное решение системы линейных уравнений с помощью метода исключения Гаусса с выбором главного элемента по столбцу
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 04:04:23 21 января 2010 Похожие работы
Просмотров: 1559 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

СОДЕРЖАНИЕ

Введение

1 Постановка задачи

2 Математические и алгоритмические основы решения задачи

2.1 Схема единственного деления

2.1.1 Прямой ход

2.1.2 Обратный ход

2.2 Метод Гаусса с выбором главного элемента по столбцу

3 Функциональные модели и блок-схемы решения задачи

4 Программная реализация решения задачи

5 Пример выполнения программы

Заключение

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


ВВЕДЕНИЕ

Решение систем линейных алгебраических уравнений – одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности – нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.

Одна из трудностей практического решения систем большой размерности связанна с ограниченностью оперативной памяти ЭВМ. Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее, еще быстрее возрастают потребности практики в решении задач все большей размерности. В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты машинного времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ.

К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего числа элементов матрицы. Такие матрицы принято называть разреженными. Одним из основных источников разреженных матриц являются математические модели технических устройств, состоящих из большого числа элементов, связи между которыми локальны. Простейшие примеры таких устройств – сложные строительные конструкции и большие электрические цепи.

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 100 тыс. уравнений в формате двойной точности заняла бы около 75 Гбайт).

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

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

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


1 Постановка задачи

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

a1,1 x1 + a1,2 x2 + a1,3 x3 + . . . + a1,n xn = b1

a2,1 x1 + a2,2 x2 + a2,3 x3 + . . . + a2,n xn = b2

(1)

an,1 x1 + an,2 x2 + an,3 x3 + . . . + an,n xn = bn

или в векторной форме

AX=B

где A -матрица коэффициентов; X - вектор неизвестных; B- вектор правых частей.

Будем считать, что D = det A ¹ 0 т.е. решение существует и единственно.

Рассмотрим вначале прямые методы. В явном виде решение системы (1) записывается в виде формул Крамера

xi = Di /D

где Di - определитель матрицы, которая получается из матрицы A путем замены i-того столбца на столбец правых частей.

Этот метод очень неэкономичен так как для его применения требуется (n+1)! операций, поэтому на практике используются различные варианты метода исключения переменных (Гаусса). Метод исключения переменных состоит из двух этапов: прямого хода, заключающегося в преобразовании исходной системы к системе с треугольной матрицей коэффициентов, и обратного хода, т.е. решения системы с треугольной матрицей.

Пример 1. Решить следующую систему с помощью метода исключения Гаусса с выбором главного элемента по столбцу:

.

Решение:

.

Пример 2. Решить следующую систему с помощью метода исключения Гаусса с выбором главного элемента по столбцу:

.

Составим расширенную матрицу системы.

.

Решением системы являются:x =1, y = 2, z = 3.


2 Математические и алгоритмические основы решения задачи

2.1 Схема единственного деления

Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

2.1.1 Прямой ход

Прямой ход состоит из n - 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11 = 0. Будем называть его главным элементом 1-го шага.

Найдем величины

qi1 = ai1/a11 (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a11x1 + a12x2 + a13x3 + … + a1nxn = b1 ,

a22(1)x2 + a23(1)x3 + … + a2n(1)xn = b2(1) ,

a32(1)x2 + a33(1)x3 + … + a3n(1)xn = b3(1) ,

an2(1)x2 + an3(1)x3 + … + ann(1)xn = bn(1) .

в которой aij(1) и bij(1) вычисляются по формулам

aij(1) = aij − qi1a1j bi(1) = bi − qi1b1.

2-й шаг. Целью этого шага является исключение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1) ≠ 0, где a22(1) – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

qi2 = ai2(1) / a22(1) (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2.

В результате получим систему

a11x1 + a12x2 + a13x3 + a1nxn =b1,

a22(1)x2 + a23(1)x3 + a2n(1) =b2(1) ,

a33(2)x3 + a3n(2)xn =b3(2),

an3(2)x3 + ann(2)xn = bn(2)

Здесь коэффициенты aij(2) и bij(2) вычисляются по формулам

aij(2) = aij(1) – qi2a2j(1) ,bi(2) = bi(1) – qi2b2(1).

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага akk(k–1) отличен от нуля, вычислим множители k-го шага

qik = aik(k–1) / akk(k–1) (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на

qk+1,k, qk+2,k, …, qnk.


После (n - 1)-го шага исключения получим систему уравнений

a11x1 +a12x2 +a13x3 + a1nxn= b1

a22(1)x2 a23(1)x3 +… + a2n(1)xn = b2(1)

a33(2)x3 + a3n(2)xn = b3(2),

ann(n–1)xn =bn(n–1)

Матрица A(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

2.1.2 Обратный ход

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn–1. Осуществляя обратную подстановку, далее последовательно находим xn–1, xn–2, …, x1. Вычисления неизвестных здесь проводятся по формулам

xn = bn(n–1) / ann(n–1),

xk = (bn(k–1) – ak,k+1(k–1)xk+1 – akn(k–1)xn) / akk(k–1), (k = n – 1, , 1).

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


2.2 Метод Гаусса с выбором главного элемента по столбцу

На k-м шаге прямого хода метода Гаусса с выбором главного элемента по столбцу коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

aij(k) = aij(k–1) − qikakj , bi(k) = bi(k–1) − qikbk(k–1) , i = k + 1, …, n.

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

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

|qik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n.

Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk(k-1). После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.


3 Функциональные модели и блок-схемы решения задачи

Блок-схема решения задачи представлена на рисунке 1.

Условные обозначения:

· K – размерность матрицы;

· MATRIX – матрица;

· N – размерность матрицы;

· X – матрица решения СЛАУ;

· I_MAX – индекс максимального элемента в строке;

· J_MAX – индекс максимального элемента в столбце;

· OTV – массив позиций элементов;

· RES – вспомогательный массив;

· TEMP – временная переменная;

· GLAV_EL – функция, определяющая на какой позиции должен стоять главный элемент;

· INDEX – рабочая переменная.


Рисунок 1 – Блок-схема решения задачи для функции GAUSS

\


4 Программная реализация решения задачи

ФУНКЦИЯ ПОИСКА МАКСИМАЛЬНОГО ЭЛЕМЕНТА И ПЕРЕСТАНОВКИ СТРОК И СТОЛБЦОВ

(DEFUN GLAV_EL (K MATRIX N X)

(DECLARE (SPECIAL I_MAX))

(DECLARE (SPECIAL J_MAX))

(DECLARE (SPECIAL TEMP))

(DECLARE (SPECIAL I))

(SETQ I_MAX K)

(SETQ J_MAX K)

;ИЩЕМ МАКСИМАЛЬНЫЙ ПО МОДУЛЮ ЭЛЕМЕНТ

(DO

((I K))

((>= I N))

(DO

((J K))

((>= J N))

(IF (< (ABS (AREF MATRIX I_MAX J_MAX)) (ABS (AREF MATRIX I J)))

(PROGN

(SETQ I_MAX I)

(SETQ J_MAX J)

)

)

(SETQ J (+ J 1))

)

(SETQ I (+ I 1))

)

;ПЕРЕСТАВЛЯЕМ СТРОКИ

(DO

((J K))

((>= J (+ N 1)))

(SETQ TEMP (AREF MATRIX K J))

(SETF (AREF MATRIX K J) (AREF MATRIX I_MAX J))

(SETF (AREF MATRIX I_MAX J) TEMP)

(SETQ J (+ J 1))

)

;ПЕРЕСТАВЛЯЕМ СТОЛБЦЫ

(DO

((I 0))

((>= I N))

(SETQ TEMP (AREF MATRIX I K))

(SETF (AREF MATRIX I K) (AREF MATRIX I J_MAX))

(SETF (AREF MATRIX I J_MAX) TEMP)

(SETQ I (+ I 1))

)

;УЧИТЫВАЕМ ИЗМЕНЕНИЕ ПОРЯЛКА КОРНЕЙ

(SETQ I (AREF X K))

(SETF (AREF X K) (AREF X J_MAX))

(SETF (AREF X J_MAX) I)

)

(DEFUN GAUSS (MATRIX N X)

(DECLARE (SPECIAL OTV))

(DECLARE (SPECIAL RES))

(SETQ OTV (MAKE-ARRAY 50 :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))

(SETQ RES (MAKE-ARRAY N :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))

;СНАЧАЛА ВСЕ КОРНИ ПО ПОРЯДКУ

(DO

((I 0))

((>= I (+ N 1)))

(SETF (AREF OTV I) I)

(SETQ I (+ I 1))

)

;ПРЯМОЙ ХОД МЕТОДА ГАУССА

(DO

((K 0))

((>= K N))

;ОПРЕДЕЛЯЕМ НА КАКОЙ ПОЗИЦИИ ДОЛЖЕН СТОЯТЬ ГЛАВНЫЙ ЭЛЕМЕНТ

(GLAV_EL K MATRIX N OTV)

(IF (< (ABS (AREF MATRIX K K)) 0.0001) (PRINT "SYSTEMA NE IMEET EDINSTVENNOGO RESHENIYA"))

(DO

((J N))

((< J K))

(SETF (AREF MATRIX K J) (FLOAT (/ (AREF MATRIX K J) (AREF MATRIX K K))))

(SETQ J (- J 1))

)

(DO

((I (+ K 1)))

((>= I N))

(DO

((J N))

((< J K))

(SETF (AREF MATRIX I J) (- (AREF MATRIX I J) (* (AREF MATRIX K J) (AREF MATRIX I K))))

(SETQ J (- J 1))

)

(SETQ I (+ I 1))

)

(SETQ K (+ K 1))

)

;ОБРАТНЫЙ КОД

(DO

((I 0))

((>= I N))

(SETF (AREF X I) (AREF MATRIX I N))

(SETQ I (+ I 1))

)

(DO

((I (- N 2)))

((< I 0))

(DO

((J (+ I 1)))

((>= J N))

(SETF (AREF X I) (- (AREF X I) (* (AREF X J) (AREF MATRIX I J))))

(SETQ J (+ J 1))

)

(SETQ I (- I 1))

)

(DO

((I 0) (INDEX 0))

((>= I N) RES)

(DO

((J 0))

((>= J N))

;РАССТАВЛЯЕМ КОРНИ ПО ПОРЯДКУ

(IF (= I (AREF OTV J))

(PROGN

(SETF (AREF RES INDEX) (AREF X J))

(SETQ INDEX (+ INDEX 1))

)

)

(SETQ J (+ J 1))

)

(SETQ I (+ I 1))

)

(SETQ X RES)

)

(SETQ INPUT_STREAM(OPEN " D:\GAUSS_MATRIX.TXT" :DIRECTION :INPUT))

;ПОЛУЧАЕМ РАЗМЕРНОСТЬ МАТРИЦЫ

(SETF N (READ INPUT_STREAM))

;ПОЛУЧАЕММАТРИЦУ

(SETF MATRIX (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

(SETQ X (MAKE-ARRAY 50 :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))

(SETQ RES (GAUSS MATRIX N X))

;ЗАПИСЫВАЕМКОРНИСЛАУВФАЙЛ

(SETQ OUTPUT_STREAM(OPEN " D:\KORNI_SLAY.TXT" :DIRECTION :OUTPUT))

(PRINT RES OUTPUT_STREAM)

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)


5 Пример выполнения программы

Пример 1.

Рисунок 2 – Входные данные

Рисунок 3 – Выходные данные

Пример 2.

Рисунок 4 – Входные данные

Рисунок 5 – Выходные данные


Пример 3.

Рисунок 6 – Входные данные

Рисунок 7 – Выходные данные


ЗАКЛЮЧЕНИЕ

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

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


СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы

1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.

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

3. Высшая документация – Online документация [Электронный ресурс] – Режим доступа: http://vm.psati.ru/online-vmath/index.php?page=8

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

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

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

7. Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.

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

9. Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. – 460 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:45:44 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:51:44 28 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151189)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru