close

Вход

Забыли?

вход по аккаунту

?

Lab 4KMVT

код для вставкиСкачать
Лабораторна робота №4
Використання чисельних методів в комп'ютерному моделюванні
Чисельні методи розв'язання систем лінійних алгебраїчних рівнянь
і знаходження коренів поліномів
Завдання на лабораторну роботу:
• ознайомитися з теоретичними відомостями;
• розв'язати систему лінійних алгебраїчних рівнянь одним із методів;
• знайти корені заданого рівняння методом половинного ділення.
Теоретичні відомості
4.1 Чисельні методи розв'язання систем лінійнихалгебраїчних рівнянь
4.1.1 Основі визначення
Системою лінійних алгебраїчних рівнянь називається система виду:
(4.1)
де - кількість невідомих.
Розв'язком системи (1) називається множина чисел , при підстановці яких на місце невідомих всі рівняння системи перетворюються в тотожність.
У деяких практичних випадках система виду (1) складає задачу, яку необхідно вирішувати, в інших випадках задача зводиться до такої системи (наприклад, при апроксимації експериментальних даних деякої кривої за методом найменших квадратів) . Перш ніж приступити до розв'язання системи, її оцінюють на наявність розв'язку. Якщо при візуальному розгляді системи лінійних алгебраїчних рівнянь виявиться хоча б два рівняння з пропорційними коефіцієнтами при невідомих, то така система є виродженою (тобто має нескінченну безліч рішень або взагалі їх не має).
Відомий метод розв'язання систем лінійних алгебраїчних рівнянь за формулами Крамера критичний за обсягом обчислень до розмірності системи і практично стає неприйнятним, якщо система містить більше п'яти рівнянь. Тому з появою ЕОМ широке застосування отримали чисельні методи розв'язання таких систем. Їх можна розділити на точні (кінцеві) та ітераційні (нескінченні). Точні методи дають точне рішення (з точністю до помилок округлення) за допомогою кінцевого числа арифметичних операцій. Ітераційні методи вимагають нескінченного числа арифметичних операцій для отримання точного рішення. Тому на практиці обчислення закінчуються тоді, коли досягається прийнятна для задачі похибка, що називається похибкою обмеження. Кожен із зазначених методів має свої переваги і недоліки.
4.1.2 Метод Гауса (послідовних виключень)
Найбільш відомим представником класу кінцевих методів є метод Гауса. Він складається з прямого і зворотного ходів. У процесі прямого ходу вихідна система виду (4.1) шляхом еквівалентних перетворень приводиться до трикутного виду, y зворотному ході обчислюються всі невідомі системи, починаючи з останнього. Для складання алгоритму розв'язання системи - лінійних алгебраїчних рівнянь з невідомими за методом Гауса розв'яжемо систему з трьома невідомими і помічені закономірності поширимо на загальний випадок:
(4.2)
(4.3)
(4.4)
Якщо, то рівняння системи переставляємо так, щоб в першому рівнянні коефіцієнт при невідомому не був рівним нулю. Введемо множники для рівнянь (4.3) і (4.4):
Помножимо перше рівняння системи спочатку на і віднімемо його з рівняння (4.3), потім помножимо перше рівняння на множник і віднімемо його з рівняння (4.4). Отримаємо:
(4.5)
(4.6)
Врахуємо, що коефіцієнти при невідомому в рівняннях (4.5) і (4.6) дорівнюють нулю, і введемо нові позначення коефіцієнтів при і :
(4.7)
(4.8)
Тоді вихідну систему після виключення першого невідомого можна переписати в наступному вигляді:
(4.9)
(4.10) Виключимо таким же чином невідоме з рівняння (4.10). Для цього рівняння (4.9) домножимо на множник
і віднімемо з рівняння (4.10). Отримаємо
де (4.11)
Після цього система рівнянь отримує такий вид:
(4.12)
(4.13)
(4.14)
У такому вигляді система легко вирішується. Для цього з рівняння (4.14) визначають , підставляють його значення в рівняння (4.13) і визначають , підставивши і в (4.12), визначають . Цей процес зворотного ходу описується для нашого прикладу наступними формулами:
Як видно, процес вирішення системи лінійних алгебраїчних рівнянь в обчислювальному плані зводиться до певних операцій над коефіцієнтами розширеної матриці системи. У загальному випадку, при виключенні -го невідомого з -го рівняння системи, коефіцієнт при -му невідомому і вільний член обчислюються за наступними формулами (див. вирази (4.7), (4.8) і (4.11):
(4.15)
(4.16)
де (4.17)
Невідомі в процесі зворотної підстановки обчислюють за формулою
. (4.18)
Граф-схема алгоритму розв'язання системи лінійних алгебраїчних рівнянь методом Гауса наведена на рис. 4.1.
На граф-схемі прийнято такі позначення: - кількість рівнянь в системі; - номер невідомого, яке виключається із решти рівнянь; - номер рівняння, з якого в даний момент виключається невідоме; - номер стовпця. Граф-схема точно відповідає розібраному вище процесу, тому особливого пояснення не вимагає.
Рисунок 4.1 - Граф-схема алгоритма розв'язання системи лінійних рівнянь методом Гауса
4.1.3 Ітераційний метод Гауса - Зейделя
Даний метод виключно зручний для використання на ЕОМ, так як легко програмується, але не завжди дає послідовність значень невідомих, що наближаються до точного розв'язання системи (тобто не завжди сходиться). Проілюструємо його на прикладі системи з трьома невідомими. Якщо коефіцієнти , , і , то систему (4.1) можна записати в наступному вигляді:
(4.19)
(4.20)
(4.21)
Задамося першим наближенням до вирішення цієї системи, позначивши його , , (зазвичай вибирають). Підставивши цей розв'язок в (4.19), обчислимо нове значення:
(4.22)
Підставивши знайдене значення та значення в (5.20), обчислимо нове значення :
(4.23)
Аналогічно:
(4.24) Цим закінчується перша ітерація. Замінивши значення , , на, , відповідно, повторимо зазначений процес і отримаємо наступне наближення. У загальному випадку, для системи з рівнянь -е наближення до розв'язку системи буде обчислюватися по формулі:
(4.25)
де Ітерації потрібно повторювати до тих пір, поки всі не стануть досить близькі до . Умова закінчення ітераційного процесу можна задати у вигляді: , (4.26)
де - похибка розв'язання.
Ітераційний метод Гауса - Зейделя сходиться в тому випадку, якщо виконуються умови:
для всіх , і по крайній мірі ( 4.27 а)
для одного , (4.27 б)
де - модуль .
Іншими словами, кожний діагональний елемент матриці системи повинен бути більше суми елементів відповідної стрічки (по модулю). Наприклад, для системи:
Для даної системи рівнянь метод Гауса-Зейделя є збіжним, оскільки виконуються умови (4.27):
.
Оскільки алгоритм методу Гауса-Зейделя нескладний, то його складові при виконанні лабораторної роботи виконуються самостійно.
5.2 Чисельні методи знаходження коренів поліномів
Як було показано в попередньому розділі, модель лінійної динамічної системи може бути представлена у вигляді передаточної функції у вигляді дробу, в якому чисельних і знаменник є поліномами оператора Лапласа s або оператора диференціювання p. Корені цих поліномів відіграють важливу роль у визначанні таких характеристик динамічних систем, як стійкість і точність, запас стійкості та інш. Нелінійни динамічні системи часто описуються математичними моделями у вигляді нелінійних і трансцендентних рівнянь. Тому важливо вміти використовувати комп'ютерні методи знаходження коренів поліномів заданого степеня та функцій однієї змінної інших видів.
5.2.1 Етапи знаходження наближених значень коренів рівняння Будь-яке рівняння з одним невідомим можна записати у вигляді
. (5.28)
Коренем рівняння (5.28) називається всяке значення змінної х, яке перетворює в нуль. Знайти точні значення коренів можливо тільки в незначній кількості випадків, для яких відомі прості формули обчислення значень коренів (наприклад, випадок квадратного і кубічного алгебраїчних рівнянь). Для рівнянь вищого степеня, трансцендентних рівнянь, рівнянь з наближеними значеннями коефіцієнтами знаходження точних значень коренів неможливе. Тому для розв'язання більшості рівнянь виду (5.28) використовують методи наближеного (чисельного) знаходження коренів рівняння, зручні для комп'ютерної реалізації. Наближеним значенням кореня х0 з точністю до ε будемо вважати будь-яке, що міститься між числами a і b, для якого виконується умова . (5.29)
Наприклад, якщо корінь х0 міститься між числами 2.118 і 2.119 (тобто 2.118<х0 <2.119), то за наближене значення кореня з точністю до 0,001 можна прийняти числа 2.338, 2.119 і будь-яке число, що міститься між ними.
Процес знаходження наближених значень коренів рівняння складається з двох етапів:
1) Відділення коренів.
2) Уточнення значень коренів до заданого степеня точності. 5.2.2 Відділення коренів рівняння
Відділити корені - це значить розділити всю область допустимих значень на відрізки, що містять всередині один корінь.Це можна зробити або графічним, або аналітичним способами.
В графічному методі будують графік функції для рівняння (5.28). Абсциси точок перетину графіка функції з віссю 0х є значеннями дійсних коренів рівняння. Оскільки побудова графіка функції по точках є трудомістким процесом, то зазвичай вихідне рівняння перетворюють до вигляду . Інтервал ізоляції кореня знаходиться на числовому проміжку, що містить абсцису точки перетину графіків функцій і (рис. 5.2).
Приклад. Задано рівняння Відділити корені рівняння графічним методом. Розв'язання: 1) Перетворюємо задане рівняння до вигляду . 2) Виконуємо наближену побудову графіків і (рис.5.2).
3) По рисунку визначаємо, що за інтервал ізоляції кореня можна прийняти відрізок [-1..0].
Рисунок 5.2 - Відділення коренів графічним способом
Графічний метод відділення коренів не володіє великою точністю. Він лише дає можливість грубо визначити інтервали ізоляції кореня.
Аналітично корені рівняння (5.28) можна відділити, використовуючи деякі властивості функцій. Ці властивості визначаються наступними теоремами, які наведені без доведення: Теорема 1. Якщо функція неперервна і монотонна на відрізку [a..b] і приймає на кінцях цього відрізку значення різних знаків, то всередині відрізка існує по крайній мірі один корінь рівняння .
Теорема 2. Якщо функція неперервна і монотонна на відрізку [a..b] і приймає на кінцях відрізку значення різних знаків, то всередині відрізка міститься корінь рівняння і цей корінь єдиний.
Теорема 3. Якщо функція неперервна на відрізку [a..b] і приймає на кінцях відрізку значення різних знаків, а похідна зберігає постійний знак всередині відрізка, то всередині відрізка міститься корінь рівняння , причому цей корінь єдиний.
Таким чином, зміна знаку функції на деякому відрізку свідчить про наявність на даному відрізку коренів рівняння. Практично для відділення коренів аналітичним методом виконують наступні дії:
1. Знаходять першу похідну .
2. Прирівнюють першу похідну до нуля і знаходять критичні точки (точки, в яких може бути екстремум).
3. Складають таблицю знаків функції, вважаючи х рівним:
а) критичним значенням для похідної чи найближчим до них;
б) граничним значенням невідомого (виходячи з ОДЗ невідомого).
4. Визначають інтервали, на кінцях яких функція приймає значення протилежних знаків. Всередині них є тільки по одному кореню. 5.2.3 Уточнення коренів методом половинного ділення
Якщо на етапі відділення коренів знайдено відрізок [a..b], на якому знаходиться корінь рівняння, то для знаходження значення кореня із заданою точністю необхідно визначити новий, більш вузький інтервал такий, щоб виконувалась умова .
Одним із зручних для реалізації на ЕОМ методом уточнення коренів є метод половинного ділення, суть якого полягає в наступному:
Припустимо, що корінь відділений і знаходиться на відрізку [a..b], тобто , причому . Виберемо на відрізку [a..b] проміжну точку с таким чином, щоб вона ділила даний відрізок навпіл. Якщо , то с точний корінь рівняння . В протилежному випадку з двох утворених відрізків і виберемо той, на кінцях якого функція приймає значення різних знаків (рис.5.3).
Рисунок 5.3 - Геометрична ілюстрація метода половинного ділення
Позначимо цей відрізок . Після цього відрізок теж методом ділимо навпіл і виконуємо аналогічні дії. Проце поділу відрізка навпіл проводимо до тих пір, коли на якомусь n-тому кроці буде отримано відрізок такий, що .
За наближене значення кореня потрібно прийняти .
Схема алгоритма знаходження коренів рівняння методом половинного ділення представлена на рис.5.4.
Рисунок 5.4 -Схема алгоритма знаходження коренів методом половинного ділення
Варіанти завдань на лабораторну роботу.
Знайи корені таких рівнянь:
1)
2)
3) 4) 5) 6) .
Розв'язати системи лінійних алгебраїчних рівнянь
1) 2) 3) 4) 5) 6) 
Документ
Категория
Рефераты
Просмотров
61
Размер файла
1 006 Кб
Теги
4kmvt, lab
1/--страниц
Пожаловаться на содержимое документа