Зміст
Вступ................................................. .................................................. ........ 2
1. Постановка задачі.............................................. ........................................ 3
2. Математичні та алгоритмічні основи розв'язання задачі.................. 5
2.1 Визначник матриці............................................... .............................. 5
2.2 Метод Гауса для вирішення систем лінійних рівнянь........................ 6
2.3 Метод Гауса для обчислення визначника........................................................ 8
3. Функціональні моделі та блок-схеми розв'язання задачі.......................... 9
4. Програмна реалізація розв'язання задачі............................................ .. 11
5. Приклад виконання програми............................................. ................. 16
Висновок................................................. .................................................. .
Список використаних джерел та літератури 19
Вступ
Багато проблем, що виникають в економічних дослідженнях, плануванні та управлінні, будучи сформульованими математично, є завданнями, в яких необхідно вирішити систему алгебраїчних рівнянь.
Історично першим, найпоширенішим методом розв'язання систем лінійних рівнянь є метод Гауса, або метод послідовного виключенняневідомих. Сутність цього методу полягає в тому, що за допомогою послідовних винятків невідомих дана системаперетворюється на ступінчасту (зокрема, трикутну) систему, рівносильну даній.
При практичному вирішенні системи лінійних рівнянь методом Гауса зручніше приводити до ступінчастого вигляду не саму систему рівнянь, а розширену матрицю цієї системи, виконуючи елементарні перетворення над її рядками. Послідовно отримувані в ході перетворення матриці зазвичай з'єднують знаком еквівалентності. Цей метод (який також називають методом послідовного виключення невідомих) відомий у різних варіантахвже понад 2000 років.
Крім аналітичного рішення СЛАУ, метод Гаусса також застосовується для знаходження матриці, зворотної до даної визначення рангу матриці і знаходження визначника.
Метою даної курсової роботиє реалізація обчислення визначника шляхом виключення Гауса.
1. Постановка задачі
Обчислення визначника матриці полягає у виконанні над матрицею алгоритму Гауса для вирішення систем лінійних рівнянь алгебри. В результаті виконання алгоритму отримуємо діагональну матрицю, її визначник дорівнює добутку елементів, що стоять на діагоналі.
. ~. . .Обчислити визначник матриці методом виключення Гауса.
.
Наведемо матрицю до діагонального вигляду методом Гаусса.
~.
Тоді визначник матриці дорівнює добутку її елементів, що стоять на діагоналі:
.Знак визначається кількістю обмінів рядків, отже визначник матриці
.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)-ий).
Зрештою, ми приведемо систему до так званого діагонального вигляду:
Тобто. ми знайшли рішення системи.
Зауваження 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))
((> = J (- SIZE 1)))
; ВИКЛЮЧАЄМО ПОДІЛ НА 0
(IF (= (AREF MATRIX J J) 0)
(SETQ II (+ J 1))
;ШУКАЄМО РЯДКУ В ЯКІЙ J-Й ЕЛЕМЕНТ НЕ 0
((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))
Обчислимо визначник методом Гаусса.
Суть методу полягає в наступному: визначник приводиться до трикутного вигляду за допомогою елементарних перетворень, і він дорівнює добутку елементів, що стоять на головній діагоналі.
Ідея методу полягає в наступному: нехай дано визначник третього порядку
елемент 
повинен дорівнювати 
, для цього перший рядок розділимо на 
.
Отримаємо визначник виду 
(2)
Обнулили елементи, що стоять у першому стовпці, крім першого. Для цього з другого рядка віднімемо перший, помножений на 
, Далі з третього рядка віднімемо перший, помножений на 
. Отримаємо визначник виду 
.
Позначимо його елементи буквою с, тоді
(3)
Тепер треба обнулити елемент 
. Елемент 
повинен дорівнювати 
, для цього другий рядок розділимо на 
. Отримаємо визначник виду 
.
.
Позначимо його елементи буквою t, тоді
(4)
Ось ми привели визначник до трикутного вигляду, тепер він дорівнює 
.
Розберемо тепер це конкретному прикладі.
Приклад 4:Обчислити визначник 
методом Гауса.
Рішення: Поміняємо місцями перший та третій рядки (при заміні двох стовпців (рядків) визначник змінює знак на протилежний).
Отримали 
З другого рядка віднімемо перший, помножений на 2, далі з третього рядка віднімемо перший, помножений на 3. Отримали 
Отримали - 
§2.Матриці Види матриць
Визначення 7:Якщо в матриці рядків істовбців, то вона називається розмірністю m 
ні пишуть 
.
Визначення 8:Якщо 
, то матриця називається квадратною.
Визначення 9:Матриця, що складається лише з одного рядка (стовпця) називається матрицею-рядком (стовпцем).
Визначення 10:Матриця, що складається з нулів, називається нульовою матрицею.
Визначення 11:Діагональною матрицею називається квадратна матриця, яка має всі елементи, що не належать головній діагоналі рівні нулю.
Визначення 12:Одиничною матрицею називається діагональна матриця, яка має всі елементи, що стоять на головній діагоналі рівні одиниці.
Визначення 13:Трикутною називається квадратна матриця, яка має елементи, розташовані з одного боку від головної діагоналі рівні нулю.
Дії над матрицями.
Визначення 14:Дві матриці вважаються рівними, якщо вони мають однакову кількість рядків і стовпців і відповідні рівні елементи.
Приклад 5:
Матриці А й рівні, тобто. 
Визначення 15:Сумою (різницею) матриць А і В називається така матриця, у якої кожен елемент дорівнює 
.
Приклад 6:Знайти матрицю 
, якщо
Рішення:
Властивості додавання
А+В=В+А(переміщувальне)
2 0 А+О=А, де О-нульова матриця
3 0 А+(В+С)=(А+В)+С (дистрибутивне)
4 0 А+(-А)=О, де – А протилежна матриця
(тобто елементи мають протилежні знаки)
Визначення 16:Добутком матриці А на число 
називається матриця, отримана з даної множенням всіх її елементів на число 
.
Приклад 7:
Примноження матиць
Ця дія поширюється так звані узгоджені матриці.
Визначення 17:Матриця А називається узгодженою з матрицею, якщо число стовпців у матриці А дорівнює числу рядків у матриці В.
Приклад 8:
і 
- узгоджені
і 
- Неузгоджені
і 
неузгоджені
Визначення 18:Добутком двох матриць А і В називається така матриця, кожен елемент якої дорівнює сумітворів елементівiстроки матриці А на відповідні елементиj-го стовпця матриці В.
Якщо матриця А має розмірність 
, а матриця 
, то 
.
Приклад 9:Помножити матриці
У ході вирішення завдань з вищої математики часто виникає необхідність обчислити визначник матриці. Визначник матриці фігурує в лінійній алгебрі, аналітичній геометрії, математичний аналізта інших розділах вищої математики. Таким чином, без навички рішення визначників просто не обійтись. Також для самоперевірки Ви можете безкоштовно скачати калькулятор визначників, він сам по собі не навчить вирішувати визначники, але дуже зручний, оскільки завжди вигідно знати правильну відповідь!
Я не даватиму строгого математичного визначення визначника, і, взагалі, намагатимуся мінімізувати математичну термінологію, більшості читачів легше від цього не стане. Завдання цієї статті – навчити Вас вирішувати визначники другого, третього та четвертого порядку. Весь матеріал викладений у простій та доступній формі, і навіть повний (порожній) чайник у вищій математиці після уважного вивчення матеріалу зможе правильно вирішувати визначники.
Насправді найчастіше можна зустріти визначник другого порядку, наприклад: , і визначник третього порядку, наприклад: 
.
Визначник четвертого порядку 
теж не антикваріат, і до нього ми підійдемо наприкінці уроку.
Сподіваюся, всім зрозуміло таке:Числа всередині визначника живуть самі по собі, і ні про яке віднімання не йдеться! Міняти місцями числа не можна!
(Як зокрема, можна здійснювати парні перестановки рядків або стовпців визначника зі зміною його знака, але часто в цьому немає необхідності - див. наступний урок Властивості визначника та зниження його порядку)
Таким чином, якщо дано якийсь визначник, то нічого всередині нього не чіпаємо!
Позначення: Якщо дана матриця 
, її визначник позначають . Також дуже часто визначник позначають латинською літероюабо грецькою.
1)Що означає вирішити (знайти, розкрити) визначник?Обчислити визначник – це означає ЗНАЙТИ ЧИСЛО. Знаки питання у вищерозглянутих прикладах – це прості числа.
2) Тепер залишилося розібратися в тому, Як знайти це число?Для цього потрібно застосувати певні правила, формули та алгоритми, про що зараз і йтиметься.
Почнемо з визначника "два" на "два":
Це потрібно запам'ятати, принаймні на час вивчення вищої математики у ВНЗ.
Відразу розглянемо приклад:
Готово. Найголовніше, не заплутатися у знаках.
Визначник матриці "три на три"можна розкрити 8 способами, 2 з них прості та 6 - нормальні.
Почнемо з двох простих способів
Аналогічно визначнику "два на два", визначник "три на три" можна розкрити за допомогою формули:
Формула довга і припуститися помилки по неуважності простіше простого. Як уникнути прикрих промахів? Для цього придумано другий спосіб обчислення визначника, який фактично збігається з першим. Він називається способом Саррюса або способом «паралельних смужок».
Суть полягає в тому, що праворуч від визначника приписують перший і другий стовпець і акуратно олівцем проводять лінії:
Багато людей, які перебувають на «червоних» діагоналях, входять у формулу зі знаком «плюс».
Багато мешканців, що знаходяться на «синіх» діагоналях, входять у формулу зі знаком мінус:
Приклад:
Порівняйте два рішення. Неважко помітити, що це ОДНЕ І ТЕ Ж, просто в другому випадку трохи переставлені множники формули, і, найголовніше, ймовірність припуститися помилки значно менше.
Тепер розглянемо шість нормальних способівдля обчислення визначника
Чому нормальні? Тому що у переважній більшості випадків визначники потрібно розкривати саме так.
Як Ви помітили, у визначника «три на три» три стовпці та три рядки.
Вирішити визначник можна, розкривши його за будь-яким рядком або за будь-яким стовпцем.
Таким чином, виходить 6 способів, при цьому у всіх випадках використовується однотипнийалгоритм.
Визначник матриці дорівнює сумі творів елементів рядка (стовпця) на відповідні алгебраїчні доповнення. Страшно? Все набагато простіше будемо використовувати ненауковий, але зрозумілий підхід, доступний навіть для людини, далекої від математики.
У наступному прикладі розкриватимемо визначник по першому рядку.
Для цього нам знадобиться матриця символів: . Легко помітити, що знаки розташовані у шаховому порядку.
Увага! Матриця знаків – це мій власний винахід. Це поняттяне наукове, його потрібно використовувати у чистовому оформленні завдань, воно лише допомагає Вам зрозуміти алгоритм обчислення визначника.
Спочатку я наведу повне рішення. Знову беремо наш піддослідний визначник і проводимо обчислення:
І головне питання: ЯК з визначника «три на три» отримати ось це ось: 
?
Отже, визначник "три на три" зводиться до рішення трьох маленьких визначників, або як їх ще називають, МІНОРІВ. Термін рекомендую запам'ятати, тим більше він запам'ятовується: мінор - маленький.
Якщо вибраний спосіб розкладання визначника по першому рядкуочевидно, що все обертається навколо неї:
Елементи зазвичай розглядають зліва направо (або зверху вниз, якщо було б обрано стовпець)
Поїхали, спочатку знаємося з першим елементом рядка, тобто з одиницею:
1) З матриці знаків виписуємо відповідний знак: 
2) Потім записуємо сам елемент: 
3) ДУМКОВО викреслюємо рядок і стовпець, в якому стоїть перший елемент: 
Чотири числа, що залишилися, і утворюють визначник «два на два», який називається МІНОРОМцього елемента (одиниці).
Переходимо до другого елемента рядка.
4) З матриці знаків виписуємо відповідний знак:
5) Потім записуємо другий елемент: 
6) ДУМКОВО викреслюємо рядок і стовпець, в якому стоїть другий елемент: 
Та й третій елемент першого рядка. Жодної оригінальності:
7) З матриці знаків виписуємо відповідний знак: 
8) Записуємо третій елемент: 
9) ДУМКОВО викреслюємо рядок і стовпець, в якому стоїть третій елемент: 
Чотири числа, що залишилися, записуємо в маленький визначник.
Інші дії не становлять труднощів, оскільки визначники «два на два» ми вважати вже вміємо. НЕ ПЛУТАЄМОСЯ У ЗНАКАХ!
Аналогічно визначник можна розкласти за будь-яким рядком або за будь-яким стовпцем.Звісно, у всіх шести випадках відповідь виходить однаковою.
Визначник "чотири на чотири" можна обчислити, використовуючи цей же алгоритм.
При цьому матриця знаків у нас збільшиться:
У наступному прикладі я розкрив визначник по четвертому стовпцю:
А як це вийшло, спробуйте розібратися самостійно. Додаткова інформаціябуде пізніше. Якщо хтось захоче вирішувати визначник до кінця, правильна відповідь: 18. Для тренування краще розкрити визначник по якомусь іншому стовпцю або іншому рядку.
Потренуватися, розкрити, провести розрахунки – це дуже добре та корисно. Але скільки часу ви витратите великий визначник? Чи не можна якось швидше і надійніше? Пропоную ознайомитись з ефективними методамиобчислення визначників на другому уроці – Властивості визначника. Зниження порядку визначника.
БУДЬТЕ УВАЖНІ!
Тут ви зможете безкоштовно вирішити систему лінійних рівнянь методом Гауса онлайн великих розміріву комплексних числах із дуже докладним рішенням. Наш калькулятор вміє вирішувати онлайн як звичайну певну, так і невизначену систему лінійних рівнянь методом Гаусса, яка має безліч рішень. І тут у відповіді ви отримаєте залежність одних змінних через інші, вільні. Також можна перевірити систему рівнянь на сумісність онлайн, використовуючи рішення методом Гаусса.
Про метод
При вирішенні системи лінійних рівнянь онлайн методомГауса виконуються такі кроки.
- Записуємо розширену матрицю.
- Фактично рішення поділяють на прямий та зворотний хід методу Гаусса. Прямим ходом методу Гаусса називається приведення матриці до ступінчастого вигляду. Зворотним ходомМетод Гауса називається приведення матриці до спеціального ступінчастого вигляду. Але на практиці зручніше відразу занулювати те, що знаходиться і зверху і знизу елемента, що розглядається. Наш калькулятор використовує цей підхід.
- Важливо, що при вирішенні методом Гауса, наявність у матриці хоча б одного нульового рядка з НЕнульовим правою частиною(Стовпець вільних членів) говорить про несумісність системи. Рішення лінійної системиу разі немає.
Щоб найкраще зрозуміти принцип роботи алгоритму Гауса онлайн, введіть будь-який приклад, виберіть "дуже докладне рішення" і перегляньте його рішення онлайн.
