12467

Прямі методи розв’язання систем лінійних алгебраїчних рівнянь. Метод Гаусса та LU-розкладу

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторна робота №1 Прямі методи розв’язання систем лінійних алгебраїчних рівнянь. Метод Гаусса та LUрозкладу. Мета роботи: ознайомитися з методами розв‘язання систем лінійних алгебраїчних рівнянь. Розглянути особливості реалізації прямих методів розв‘язання ...

Украинкский

2013-04-27

56.5 KB

18 чел.

Лабораторна робота №1

Прямі методи розв’язання систем

лінійних алгебраїчних рівнянь. Метод Гаусса та LU-розкладу.

Мета роботи: ознайомитися з методами розв‘язання систем лінійних алгебраїчних рівнянь. Розглянути особливості реалізації прямих методів розв‘язання систем лінійних алгебраїчних рівнянь у вигляді m-файлу функції у середовищі MatLab.

Задачі лабораторної роботи: реалізувати один з прямих методів розв‘язання систем лінійних алгебраїчних рівнянь у вигляді m-файлу функції у середовищі MatLab у відповідності з варіантом. Продемонструвати його роботу, оцінити точність отриманих розв‘язків та визначити джерела виникнення похибок на прикладі розв‘язання конкретної систем лінійних алгебраїчних рівнянь.

Теоретичні відомості.

Математичні моделі багатьох технічних задач представлені системами лінійних рівнянь. Багато методів розв’язання нелінійних задач також зводяться до розв’язання деякої послідовності систем лінійних алгебраїчних рівнянь (систем ЛАР) на ЕОМ. Для багатьох методів розроблений математичний апарат, що дозволяє оцінити точність отриманого розв’язку. Чисельні методи розв’язку систем ЛАР поділяються на прямі та ітераційні (наближені).

Прямі (точні) методи дозволяють розв’язати систему рівнянь за скінчене число арифметичних операцій. Якщо всі операції виконуються точно (без помилок округлення), то розв’язок заданої системи також отримуємо точним. До прямих методів належать: метод послідовного виключення невідомих (метод Гаусса та його модифікації: метод головного елемента, метод квадратного кореня, метод відображень та ін.), метод ортогоналізації, метод LU-розкладу. Прямі методи застосовують на практиці для розв’язання систем ЛАР за допомогою обчислювальної техніки, як правило, з числами порядку не вище 103 .

Ітераційні методи є наближеними. Вони дозволяють знайти розв’язок системи, як межу послідовних наближень, що обчислюються по однаковому алгоритму. Для застосування ітераційних методів у початкових умовах необхідно задати точність обчислень ε і початкове наближення х0 чи (х01, х02, х03, …). До ітераційних методів належать: метод Зейделя, метод простої ітерації, метод релаксації, градієнтні методи та їх модифікації. На практиці ітераційні методи застосовують для розв’язання систем ЛАР з числами порядку 106 і вище.

Розглянемо систему m лінійних алгебраїчних рівнянь з n невідомими:

              (1.1)

Коротко її можна записати в матричному вигляді:

     (1.2)

де матриця m×n;  - вектор n-го порядку; - вектор m-го порядку.

Розв’язком системи ЛАР називається така впорядкована сукупність чисел х1= с1, х2 = с2, … хn = сn, яка обертає всі рівняння системи у істинні рівняння.

Система ЛАР називається сумісною, якщо вона має хоча б один розв’язок, і несумісною – якщо вона не має розв’язків. Сумісна система називається визначеною, якщо вона має один розв’язок, і невизначеною, якщо має більше одного розв’язку.

Метод Гаусса

Розглянемо систему ЛАР:

    а11х1 + а12х2 + …+а1nхn = b1

    а21х1 + а22х2 + …+а2nхn = b2

    ……………………………………………                                          (1.3)

    аn1х1 + аn2х2 + …+аnnхn = bn

у якій матриця А = (аij) не вироджена. Метод Гаусса полягає у послідовному виключенні невідомих. Суть його у перетворенні системи (1.3) в систему з трикутною матрицею, з якої послідовно (при зворотному розв‘язку, тобто від останнього рівняння до першого) отримують значення всіх невідомих.

Алгоритм послідовного виключення невідомих може бути побудований за різними обчислювальними схемами. Побудуємо його по схемі єдиного ділення.

Перетворимо систему (1.3): припустимо а11  0, розділимо всі коефіцієнти першого рівняння на а11. Віднімемо з кожного рівняння системи перше рівняння, що помножене на коефіцієнт при х1. На перетворюючи першого рівняння, зробимо аналогічні перетворення над всіма іншими рівняннями системи і т.д. Отримуємо систему з трикутною матрицею:

   х1 + 12х2 + …+1nхn = 1

          22х2 + …+2nхn = 2

   ……………………………………………                            (1.4)

                                   хn = n

Із системи рівнянь (1.4) послідовно знаходимо значення всіх невідомих  хn, хn-1,…, х1.

Таким чином процес розв‘язання системи (1.3) по методу Гаусса можна розділити на два етапи.

1) Перший етап полягає в послідовному виключенні невідомих (приведенні матриці коефіцієнтів А = (аij) до верхньої трикутної матриці). Його називають прямим ходом.

2) Другий етап – безпосереднє отримання значень невідомих, як результату розв’язання низки рівнянь однією змінною – називають зворотнім ходом. Таку назву етап отримав, оскільки розв‘язання починають із n-го останнього рівняння, послідовно проводячи розрахунки з n-1, n-2, n-3…3, 2, 1 рівняннями.

В ході виконання операцій ділення в методі Гауса виникає обчислювальна похибка, яка при збільшенні кількості операцій (≥40) може значно спотворювати результат. Для зменшення обчислювальної похибка застосовують перестановки рівнянь у системі в залежності від головного елементу. Головний елемент – це максимальний коефіцієнт рівняння. Сукупність рівнянь в системі потрібно переставити таким чином, щоб на головній діагоналі матриці коефіцієнтів стояли максимальні елементи.

Метод LU-розкладу

 При розв‘язанні системи лінійних алгебраїчних рівнянь цим методом матрицю коефіцієнтів А розкладають на добуток двох матриць нижньої трикутної матриці L, на головній діагоналі якої стоять одиниці, та верхньої трикутної матриці U, елементи головної діагоналі якої не дорівнюють нулю. У матричному вигляді при n = 4 це можна записати таким чином:

 (1.5)

Для розкладання матриці коефіцієнтів А на трикутні матриці використаємо метод виключення Гауса. Отримаємо матрицю L з допомогою одиничної матриці. Для цього помножимо зліва матрицю А на одиничну матрицю. Наприклад:

   (1.6)

Перший рядок матриці А використовуємо для обнулення елементів першого стовпчика цієї ж матриці. Помножимо перший рядок на –0,5 і віднімемо від другого, помножимо перший рядок на 0,25 і віднімемо від третього рядка. Вказану операцію проводимо не тільки з матрицею А, а й з одиничною матрицею, але замість віднімання першого рядка від чергового здійснюємо додавання першого рядка до чергового. В результаті отримаємо:

   (1.7)

Другий рядок матриці А використовуємо для обнулення елементів другого стовпчика цієї ж матриці, що знаходяться нижче другого рядка (у матриці, що утворена з одиничної, проводимо додавання відповідного елементу):

  (1.8)

В результаті отримуємо LU - розклад матриці А і розв’язуємо систему рівнянь у два етапи:

   (1.9)

На першому етапі знаходимо проміжний вектор Y, використовуючи пряму підстановку, на другому етапі знаходимо безпосередньо вектор розв’язків Х, застосовуючи зворотну підстановку. Зокрема, приймаючи в даному прикладі з проміжної системи LY = B матимемо . Здійснюючи другий етап розв‘язання системи, тобто розв‘язуючи рівняння UX = Y , отримаємо .

 Завдання для виконання лабораторної роботи:

 Створити програму на внутрішній мові середовища МatLAB, що реалізує метод Гауса з вибором головного елементу (для непарних варіантів) чи метод LU-розкладу (для парних варіантів). Провести тестування створеної програми на прикладі, вибраному за варіантом. Здійснити перевірку отриманих результатів, в разі виникнення похибки, пояснити джерело її виникнення та накопичення (компенсації).

Варіанти завдань:

1 варіант.  2 варіант.

3 варіант.  4 варіант.

5 варіант.  6 варіант.

7 варіант.  8 варіант.

9 варіант.  10 варіант.


 

А также другие работы, которые могут Вас заинтересовать

18286. ДОДАВАННЯ І ВІДНІМАННЯ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ 74 KB
  Лекція 13 ДОДАВАННЯ І ВІДНІМАННЯ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ Означення суми цілих невід’ємних чисел через об’єднання множин. Існування і єдність суми. Операція додавання цілих невід’ємних чисел та їх властивості. Формування понять суми і додавання в початкові...
18287. МНОЖЕННЯ І ДІЛЕННЯ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ 85 KB
  Лекція 14 МНОЖЕННЯ І ДІЛЕННЯ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ Означення добутку цілих невід’ємних чисел через декартів добуток множин. Існування і єдність добутку. Означення добутку цілих невід’ємних чисел через суму. Операція множення цілих невід’ємних чисел та...
18288. АКСІОМИ ПЕАНО 93 KB
  Лекція 15 АКСІОМИ ПЕАНО Поняття про аксіоматичний метод побудови теорії. Аксіоматична побудова множини цілих невід’ємних чисел; неозначувані поняття аксіоми Пеано та деякі наслідки з них. Аксіоматичне означення операції додавання цілих невід’ємних чисел...
18289. ВЛАСТИВОСТІ МНОЖИНИ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ 124 KB
  Лекція 16 ВЛАСТИВОСТІ МНОЖИНИ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ Ділення з остачею. Теорема про ділення з остачею. Операції ділення з остачею. Формування поняття ділення з остачею в початковій школі. Принцип і метод математичної індукції. б Натуральне число як р...
18290. НАТУРАЛЬНЕ ЧИСЛО ЯК МІРА ВІДРІЗКА 87 KB
  Лекція 17 НАТУРАЛЬНЕ ЧИСЛО ЯК МІРА ВІДРІЗКА Поняття про величини та їх вимірювання. Поняття про відрізок. Відношення дорівнює€ менше€ більше€ на множині відрізків та їх властивості. Поняття про додавання і віднімання над відрізками та їх властивос...
18291. ДЕСЯТКОВА СИСТЕМА ЧИСЛЕННЯ 148 KB
  Лекція 18 ДЕСЯТКОВА СИСТЕМА ЧИСЛЕННЯ Поняття про систему числення. Число і цифра. Непозиційні і позиційні системи числення. Десяткова система числення запис читання і порівняння цілих невід’ємних чисел в ній. Алгоритм додавання чисел в десятковій системі ...
18292. НЕДЕСЯТКОВІ ПОЗИЦІЙНІ СИСТЕМИ ЧИСЛЕННЯ 158 KB
  Лекція 19 НЕДЕСЯТКОВІ ПОЗИЦІЙНІ СИСТЕМИ ЧИСЛЕННЯ Недесяткові позиційні системи числення: запис читання і порівняння чисел в них. Алгоритми додавання і віднімання чисел в недесяткових позиційних системах числення. Таблиці додавання. Алгоритми множення і д...
18293. ВІДНОШЕННЯ ПОДІЛЬНОСТІ 73 KB
  Лекція 20 ВІДНОШЕННЯ ПОДІЛЬНОСТІ Відношення подільності на множині цілих невід’ємних чисел та його властивості. Подільність суми різниці і добутку. Поняття про ознаку подільності. Ознака подільності Паскаля. Ознаки подільності на 2 3 4 5 9 11 25 в десятко...
18294. СПІЛЬНІ КРАТНІ І ДІЛЬНИКИ 101 KB
  Лекція 21 СПІЛЬНІ КРАТНІ І ДІЛЬНИКИ Спільні кратні та найменше спільне кратне кількох натуральних чисел і його властивості. Спільні дільники та найбільший спільний дільник кількох натуральних чисел і його властивості. Взаємно прості та попарно взаємнопрості...