12467

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

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

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

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

Украинкский

2013-04-27

56.5 KB

20 чел.

Лабораторна робота №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 варіант.


 

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

16800. Минерально-сырьевой потенциал платиновых металлов России на пороге XXI века 316 KB
  Минеральносырьевой потенциал платиновых металлов России на пороге XXI века Н.М.Чернышов Д.А.Додин Воронежский государственный университет г.Воронеж ВНИИ Океангеология г.СанктПетербург Аннотация Предложена оригинальная классификация платиноидных ме
16801. Намывные россыпи как новый источник получения золота и платины 80 KB
  Намывные россыпи как новый источник получения золота и платины От редакции бюлл. Золотодобыча. Новое как известно часто является хорошо забытым старым. Нижеприведенная статья по мелкому золоту написана в 1932 году но мы уверены что она с интересом будет прочитана и сег...
16802. НОВЫЕ ТЕХНИКА И ТЕХНОЛОГИИ ОБОГАЩЕНИЯ ПЕСКОВ 225 KB
  НОВЫЕ ТЕХНИКА И ТЕХНОЛОГИИ ОБОГАЩЕНИЯ ПЕСКОВ Несмотря на снижение объема добычи золота из россыпей они продолжают оставаться наиболее выгодным объектом для промышленного освоения как в современных условиях так и в среднесрочной перспективе поскольку их минераль
16803. Стратегическое значение мелких месторождений коренного золота в Хабаровском крае и Амурской области 40 KB
  О стратегическом значении мелких месторождений коренного золота в Хабаровском крае и Амурской области Е.В.Нигай к.г.м.н ст.науч.сотр. ИГД ДВО РАН Золотодобыча №121 Декабрь 2008 Разведка и эксплуатация мелких месторождений коренного золота в пределах Дальнего Востока ...
16804. Обобщенная характеристика россыпей благородных металлов Приморья 46 KB
  Обобщенная характеристика россыпей благородных металлов Приморья Россыпи развитые на территории СихотэАлиня и Южного Приморья Иванов Хомич 1997 разделяются на монокомпонентные однометалльные одноэлементные и многокомпонентные комплексные. Последние охватыва
16805. Оборудование для добычи золота 1.83 MB
  Оборудование для добычи золота 8ми футовая машина Может устанавливаться на берегу или на понтонах легко подготавливается к перевозке любым транспортом. В конструкции нет вибраторов что упрощает эксплуатацию и повышает надёжность.Оптимальный ...
16806. Оборудование для пробоподготовки 1.32 MB
  Оборудование для пробоподготовки Кольцевые мельницы НАСТОЛЬНАЯ КОЛЬЦЕВАЯ МЕЛЬНИЦА Компактная и лёгкая настольная мельница предназначена для истирания проб максимальным весом до 100 грамм. Предназначена для ис...
16807. Освоение сырьевой базы золота Иркутской области 56.5 KB
  Освоение сырьевой базы золота Иркутской области В.А.Назарьев В.А.Мордвин Главное управление природных ресурсов и охраны окружающей среды МПР России по Иркутской области Иркутская область один из основных регионов страны по добыче золота. За более чем полутор
16808. Перспективы организации комплексного извлечения цветных, рассеянных редких и благородных металлов из нетрадиционного природного и техногенного сульфидного сырья Урала 184 KB
  Мелентьев Г.Б. Малинина Е.Н. Овчарова Е.С. Перспективы организации комплексного извлечения цветных рассеянных редких и благородных металлов из нетрадиционного природного и техногенного сульфидного сырья Урала НИЦ Экология и промышленная энерготехнология Объедин...