Зміст
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 D...
