Зміст
Введення 2
1. Постановка завдання 3
2. Математичні та алгоритмічні основи рішення задачі 5
2.1 Визначник матриці 5
2.2 Метод Гаусса для вирішення систем лінійних рівнянь 6
2.3 Метод Гаусса для обчислення визначника 8
3. Функціональні моделі та блок-схеми виконання завдання 9
4. Програмна реалізація рішення задачі 11
5. Приклад виконання програми 16
Висновок 18
Список використаних джерел та літератури 19
Введення
Багато проблем, які виникають в економічних дослідженнях, плануванні та управлінні, будучи сформульованими математично, представляють собою завдання, в яких необхідно вирішити систему алгебраїчних рівнянь.
Історично першим, найбільш поширеним методом вирішення систем лінійних рівнянь є метод Гауса, або метод послідовного виключення невідомих. Сутність цього методу полягає в тому, що за допомогою послідовних виключень невідомих дана система перетворюється на ступінчасту (зокрема, трикутну) систему, рівносильну даної.
При практичному вирішенні системи лінійних рівнянь методом Гаусса зручніше приводити до ступінчастого вигляду не саму систему рівнянь, а розширену матрицю цієї системи, виконуючи елементарні перетворення над її рядками. Послідовно виходять в ході перетворення матриці зазвичай з'єднують знаком еквівалентності. Цей метод (який також називають методом послідовного виключення невідомих) відомий у різних варіантах вже більше 2000 років.
Крім аналітичного рішення СЛАР, метод Гаусса також застосовується для знаходження матриці, оберненої до даної, визначення рангу матриці і знаходження визначника.
Метою даної курсової роботи є реалізація обчислення визначника методом виключення Гауса.
1. Постановка завдання
Нехай дана квадратна матриця A розміром NxN. Потрібно обчислити її визначник.
Обчислення визначника матриці полягає у виконанні над матрицею алгоритму Гаусса для вирішення систем лінійних алгебраїчних рівнянь. В результаті виконання алгоритму отримуємо діагональну матрицю, її визначник дорівнює добутку елементів, що стоять на діагоналі.
Приклад 1.
Обчислити визначник матриці методом A виключення Гауса.
.
Рішення:
Наведемо матрицю до діагонального вигляду методом Гаусса.
~
.
Тоді визначник матриці дорівнює твору її елементів, що стоять на діагоналі:
.
Знак визначається кількістю обмінів рядків, отже визначник матриці .
Приклад 2.
Обчислити визначник матриці методом A виключення Гауса.
.
Рішення:
Наведемо матрицю до діагонального вигляду методом Гаусса.
~
.
Тоді визначник матриці дорівнює твору її елементів, що стоять на діагоналі:
.
Знак визначається кількістю обмінів рядків, отже визначник матриці .
2. Математичні та алгоритмічні основи рішення задачі
2.1 Визначник матриці
Введемо визначення визначника квадратної матриці будь-якого порядку. Це визначення буде рекурентним, тобто щоб встановити, що таке визначник матриці порядку n, потрібно вже знати, що таке визначник матриці порядку n-1. Відзначимо також, що визначник існує тільки у квадратних матриць.
Визначник квадратної матриці A будемо позначати або det A.
Визначення. Визначником квадратної матриці
другого порядку називається число
.
Визначником
квадратної матриці порядку n, , Називається число
де - Визначник матриці порядку n-1, отриманої з матриці A викреслюванням першого рядка і стовпця з номером k.
2.2 Метод Гаусса для вирішення систем лінійних рівнянь
Нехай дана квадратна матриця A розміром NxN. Потрібно обчислити її визначник.
Скористаємося ідеями методу Гауса розв'язування систем лінійних рівнянь.
Дана система:
a11 x1 + a12 x2 + ... + a1n xn = b1
a21 x1 + a22 x2 + ... + A2n xn = b2
...
an1 x1 + an2 x2 + ... + Ann xn = bn
Виконаємо наступний алгоритм.
На першому кроці знайдемо в першому стовпці найбільший за модулем елемент, поставимо рівняння з цим елементом на перший рядок (обмінявши дві відповідні рядки матриці A і два відповідних елемента вектора B), а потім будемо віднімати це рівняння від всіх інших, щоб у першому стовпчику всі елементи (крім першого) звернулися в нуль. Наприклад, при додаванні до другої рядку будемо домножать перший рядок на -a21/a11, при додаванні до третьої - на -a31/a11, і т.д.
На другому кроці знайдемо в другому стовпці, починаючи з другого елементу, найбільший за модулем елемент, поставимо рівняння з цим елементом на другу сходинку, і будемо віднімати це рівняння від всіх інших (в тому числі і від першого), щоб у другому стовпці всі елементи (крім другого) звернулися в нуль. Зрозуміло, що ця операція ніяк не змінить перший стовпець - адже від кожного рядка ми будемо віднімати другий рядок, домноженную на певний коефіцієнт, а у другому рядку в першому стовпці стоїть нуль.
Тобто на i-му кроці знайдемо в i-му стовпці, починаючи з i-го елемента, найбільший за модулем елемент, поставимо рівняння з цим елементом на i-й рядок, і будемо віднімати це рівняння від всіх інших. Зрозуміло, що це ніяк не вплине на всі попередні стовпці (з першого по (i-1)-ий).
Врешті-решт, ми приведемо систему до так званого діагонального вигляду:
c11 x1 = d1
c22 x2 = d2
...
cnn xn = dn
Тобто ми знайшли рішення системи.
Зауваження 1. На кожній ітерації знайдеться хоча б один ненульовий елемент, інакше система б мала нульовий визначник, що суперечить умові.
Зауваження 2. Вимога, що на кожному кроці ми вибираємо найбільший за модулем елемент, дуже важливо в сенсі чисельної стійкості методу. Якщо вибирати довільний ненульовий елемент, то це може призвести до гігантської похибки, коли вийшло рішення буде відрізнятися в рази від правильного.
2.3 Метод Гаусса для обчислення визначника
Будемо виконувати ті ж самі дії, що і при вирішенні системи лінійних рівнянь, виключивши тільки поділ поточного рядка на a [i] [i] (точніше, саме розподіл можна виконувати, але маючи на увазі, що число виноситься за знак визначника). Тоді всі операції, які ми будемо проводити з матрицею, не будуть змінювати величину визначника матриці, за винятком, можливо, знака (ми тільки обмінюємо місцями два рядки, що змінює знак на протилежний, або додаємо один рядок до іншої, що не змінює величину визначника).
Але матриця, до якої ми приходимо після виконання алгоритму Гауса, є діагональною, і визначник її дорівнює добутку елементів, що стоять на діагоналі. Знак, як уже говорилося, буде визначатися кількістю обмінів рядків (якщо їх непарне, то знак визначника слід змінити на протилежний). Таким чином, ми можемо за допомогою алгоритму Гауса обчислювати визначник матриці за O (N3).
Залишилося лише зауважити, що якщо в якийсь момент ми не знайдемо в поточному стовпці ненульового елемента, то алгоритм слід зупинити і повернути 0.
3. Функціональні моделі та блок-схеми виконання завдання
Блок-схема рішення задачі представлена на малюнку 1.
Рисунок 1 - Блок-схема рішення задачі для функції DETERMINATE
4 Програмна реалізація рішення задачі
; Функція, що обчислює ВИЗНАЧНИК
(DEFUN DETERMINANT (MATRIX SIZE)
; ОГОЛОШЕННЯ ЗМІННИХ
; ВИЗНАЧНИК
(DECLARE (SPECIAL DET))
; ДОПОМІЖНІ МАСИВИ І ЗМІННІ
(DECLARE (SPECIAL PAR))
(DECLARE (SPECIAL R))
(DECLARE (SPECIAL T_))
(DECLARE (SPECIAL I))
(DECLARE (SPECIAL II))
;*********************
(SETQ R (MAKE-ARRAY SIZE: ELEMENT-TYPE 'FLOAT: INITIAL-ELEMENT 0))
(SETQ T_ 1)
(SETQ DET 1)
(DO
((J 0))
((> = J (- SIZE 1)))
; ВИКЛЮЧАЄ РОЗПОДІЛ НА 0
(IF (= (AREF MATRIX JJ) 0)
(PROGN
(SETQ II (+ J 1))
; ШУКАЄМО РЯДОК В ЯКІЙ J-Й ЕЛЕМЕНТ НЕ 0
(DO
(())
((OR (/ = (AREF MATRIX II J) 0) (= II (- SIZE 1))))
(SETQ II (+ II 1))
)
; ЯКЩО НІ ТАКИЙ РЯДКИ ВИЗНАЧНИК ДОРІВНЮЄ 0
(IF (AND (= (AREF MATRIX II J) 0) (= II (- SIZE 1))) (SETQ T_ 0))
; МІНЯЄМО J РЯДОК і Найдьонов
(DO
((K 0))
((> = K SIZE))
(SETF (AREF RK) (AREF MATRIX JK))
(SETF (AREF MATRIX JK) (AREF MATRIX II K))
(SETF (AREF II K) (AREF RK))
(SETQ K (+ K 1))
)
)
)
; ПРЯМОЇ ХІД
; ПРИВЕДЕННЯ До ТРИКУТНИЙ ТИПОМ
(DO
((I (+ J 1)))
((> = I SIZE))
; ЕСЛИ (AREF MATR IJ) = 0 РОБИТИ НІЧОГО НЕ ТРЕБА
(IF (/ = (AREF MATRIX IJ) 0)
(PROGN
(SETQ PAR (/ (AREF MATRIX IJ) (AREF MATRIX JJ)))
(DO
((JJ J))
((> = JJ SIZE))
(SETF (AREF MATRIX J JJ) (* (AREF MATRIX J JJ) PAR))
(SETF (AREF MATRIX I JJ) (- (AREF MATRIX I JJ) (AREF MATRIX J JJ)))
(SETF (AREF MATRIX J JJ) (/ (AREF MATRIX J JJ) PAR))
(SETQ JJ (+ JJ 1))
)
)
)
(SETQ I (+ I 1))
)
(SETQ J (+ J 1))
)
(IF (/ = T_ 0)
(PROGN
(DO
((I 0))
((> = I SIZE))
(SETQ DET (* DET (AREF MATRIX II)))
(SETQ I (+ I 1))
)
)
; ІНАКШЕ
(SETQ DET 0)
)
, І вернися ВИЗНАЧНИК
DET
)
(SETQ N 0)
(SETQ INPUT_STREAM (OPEN "D: \ MATRIX.TXT": DIRECTION: INPUT))
; РОЗМІР МАТРИЦІ
(SETF N (READ INPUT_STREAM))
(SETQ MATR (MAKE-ARRAY (LIST NN): ELEMENT-TYPE 'FLOAT: INITIAL-ELEMENT 0))
(SETF MATR (READ INPUT_STREAM))
(CLOSE INPUT_STREAM)
(SETQ DETERM (DETERMINANT MATR N))
; РЕЗУЛЬТАТ
(SETQ OUTPUT_STREAM (OPEN "D: \ DETERMINANT.TXT": DIRECTION: OUTPUT))
; ЗАПИСУЮТЬ ВИЗНАЧНИК
(PRINT 'DETERMINANT OUTPUT_STREAM)
(PRINT DETERM OUTPUT_STREAM)
; ЗАКРИВАЮТЬ ФАЙЛ
(TERPRI OUTPUT_STREAM)
(CLOSE OUTPUT_STREAM)
5 Приклад виконання програми
Приклад 1.
Рисунок 2 - Вхідні дані
Рисунок 3 - Вихідні дані
Приклад 2.
Рисунок 4 - Вхідні дані
Малюнок 5 - Вихідні дані
Приклад 3.
Малюнок 6 - Вхідні дані
Малюнок 7 - Вихідні дані
Висновок
Проблема підвищення якості обчислень, як невідповідність між бажаним і дійсним, існує і буде існувати надалі. Її вирішення сприятиме розвиток інформаційних технологій, яке полягає як в удосконаленні методів організації інформаційних процесів, так і їх реалізації за допомогою конкретних інструментів - середовищ і мов програмування.
Підсумком роботи можна вважати створену функціональну модель для обчислення визначника методом виключення Гауса. Створена функціональна модель і її програмна реалізація можуть служити органічною частиною вирішення більш складних завдань.
Список використаних джерел та літератури
Бронштейн, І.М. Довідник з математики для інженерів і учнів втузів [Текст] / І.М. Бронштейн, К.А. Семендяев. - М.: Наука, 2007. - 708 с.
Васильєв, Ф.П. Чисельні методи розв'язання екстремальних задач. [Текст] / Ф.П. Васильєв - М.: Наука, 2002. C. 415.
Каліткін, М.М. Чисельні методи. [Електронний ресурс] / М.М. Каліткін. - М.: Питер, 2001. С. 504.
Кнут, Д.Е. Мистецтво програмування. Основні алгоритми [Текст] / Д.Е. Батіг. - М.: Вільямс, 2007. Т.1. - 712 с.
Метод Гауса [Електронний ресурс] - Режим доступу: http://www.wikipedia.org/wiki/Метод_Гаусса.
Степанов, П.А. Функціональне програмування мовою Lisp. [Електронний ресурс] / П. А. Степанов, А.В. Бржезовскій. - М.: ГУАП, 2003. С. 79.
Сіманков, В.С. Основи функціонального програмування [Текст] / В.С. Сіманков, Т.Т. Зангієв, І.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.
Хювенен Е. Світ Ліспу [Текст] / Е. Хювенен, Й. Сеппянен. - М.: Світ, 1990. - 460 с.