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 варіант.


 

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

66962. Поговоримо про дружбу 404.5 KB
  Наприклад: Правдивий друг любить за всякого часу в недолі ж він робиться братом Є товариші на розбиття та є й приятель більше від брата прив’язаний. Не смійся коли хтось говорить за винятком якщо хтось жартує Завдання № 1 На початку уроку звучить запис пісні Справжній друг муз.
66964. Заняття з елементами СПТ «Чи знаєш ти про вплив тютюнового диму?» 52 KB
  Йдеться про проблему куріння. Під час куріння кожен три чотири рази затягувався випускаючи дим через ніздрі. куріння проникло до Іспанії Португалії Франції Англії Голландії. Проте Холтер Ролі фаворит двора королеви Єлизавети популяризував куріння тютюну.
66965. Прощавай наш дитсадок! 77.5 KB
  Ведуча: Шановні мами і тата, дорогі бабусі і дідусі! Сьогодні ми всі трохи сумуємо, тому що настав час розставання. Незабаром для наших випускників продзвенить перший шкільний дзвінок. Позаду залишилися дні, наповнені цікавими подорожами у світ непізнаного, нерозгаданого...
66967. Свято 1 Дзвоника 61.5 KB
  І сьогодні радісний і світлий Він відкриє двері знань для нас. Увага Сьогодні 1 вересня 2010 року починається новий відлік часу для наших первачків В1. Зустрічайте наші першокласники Таке велике сьогодні свято Радіють мами бабусі й тата Усмішки всюди і гарні квіти Сьогодні в школу говорять діти.
66968. ТОРЖЕСТВЕННАЯ ЛИНЕЙКА, ПОСВЯЩЕННАЯ ПРАЗДНИКУ ПЕРВОГО ЗВОНОКА 51.5 KB
  Школа, здравствуй! Учеба, здравствуй! Идем за знаньями в поход. Сегодня праздник! Школьный праздник! Встречаем мы учебный год! ВЕДУЩИЙ 1. Настал поистине чудесный день, Которого мы долго ждали, Ведь в школе нашей – юбилей Поэтому мы здесь собрались!
66969. Spring. Easter 51.5 KB
  Teaching goals: engagement into intercultural communication acquiring knowledge about cultural traditions of other peoples mastering basic skills in listening, speaking Developing goals: development of speaking, intellectual and cognitive abilities...
66970. Осень – лету конец, всей работе венец 44 KB
  Цель: познакомить учащихся с результатами работы на учебно-опытном участке, с явлениями, происходящими в природе осенью, с народными обычаями и традициями, связанными с этим временем года. Показать необходимость проведения опытнической и исследовательской работы в природе и на участке.