Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Розділ 2. Методи розв’язку систем лінійних рівнянь
Короткі теоретичні відомості Система лінійних алгебраїчних рівнянь (СЛАР) у загальному випадку має вигляд: (2.1) де - коефіцієнти системи, - вільні члени системи, - невідомі, які необхідно визначити. Вводячи матрицю коефіцієнтів системи , та вектор-стовпчик вільних членів , ф також вектор-стовпчик невідомих , систему (2.1) можна подати у матричній формі: . (2.2) Якщо всі вільні члени , то СЛАР називається однорідною. Із курсу лінійної алгебри відомо, що неоднорідна СЛАР має єдиний розв’язок у випадку, коли , де - визначник матриці .
Метод Гаусса Метод Гаусса або метод послідовного виключення невідомих – один з найвідоміших та широко застосовуваних прямих методів розв’язування СЛАР. Процес розв’язання даним методом поділяють на два етапи: перший – це зведення системи (2.3) до трикутного вигляду(2.4) (прямий хід): (2.3) (2.4) Другий етап – це визначення невідомих за формулами (2.5) (зворотний хід); (2.5) На практиці обчислення методом Гаусса зручно проводити, скориставшись схемою єдиного ділення, яку подано в табл. 2.1. Таблиця 2.1.
Наприклад: Скориставшись схемою єдиного ділення розв’язати систему лінійних рівнянь методом Гаусса. Розв’язок: Використовуючи схему єдиного ділення складемо таблицю:
Відповідь: х1 =1; х2 =2; х3 =3. Метод прогонки Даний метод реалізується у випадку, коли матриця - трьохдіаганальна. Матрицю можна записати у розгорнутому вигляді як: , , , (2.6) Якій відповідає розширена матриця: (2.7) Якщо до (2.7) застосувати алгоритм прямого ходу метода Гаусса, то матриця буде замінена на матрицю : (2.8) Враховуючи, що останній стовпчик цієї матриці відповідає правій частині матриці , та переходячи до системи яка включає невідомі, маємо рекурентну формулу: , . (2.9) Співвідношення (2.9) є формулою оберненого ходу, а коефіцієнти , - називаються прогоночними та визначаються:
, , . (2.10) Обернений хід метода прогонки починається з обчислення . Для цього використовують останнє рівняння, коефіцієнти якого визначено у прямому ході: , . Звідси , тобто . Інші значення невідомих знаходять рекурентно за формулою (2.9). Алгоритм метода прогонки називається коректним, якщо для всіх , та стійким, якщо , . Достатньою умовою коректності та стійкості даного метода є умова преобладания діагональних елементів у матриці , в якій та : (2.11) та у (2.11) має місце строга нерівність хоча б при одному . Наприклад: Дана система лінійних алгебраїчних рівнянь яка складається з трьох діагональної матриці : . Розв’язати дану систему методом прогонки.
Розв’язання. Перевіримо систему на умову преобладания діагональних елементів (2.11): у першому рівнянні ; у другому рівнянні ; у третьому ; у четвертому , отже умова (2.11) виконується. Запишемо дане рівняння у вигляді матриці: . Прямий хід: Обчислимо прогоночні коефіцієнти: ; ; ; . Так як , то виходячи з (2.6) у другому доданку візьмемо від’ємний знак: ; . Обернений хід: ; ; ; . Відповідь: .
Метод LU – декомпозицій У цьому методі матриця коефіцієнтів А подається у вигляді добутку матриць L та U: A = LU, (2.12) де L – нижня трикутна матриця; а U – верхня трикутна матриця, усі діагональні елементи якої дорівнюють 1: . (2.13)
Метод LU -факторизації складається з двох етапів: 1) етапу факторизації матриці A; 2) етапу отримання розв’язку X. Вектор В у процесі факторизації не змінюється. Із виразів (2.12) та (2.13) випливає, що для i > j елементи матриці A можна виразити через елементи матриць L та U: (2.14) Із рівнянь (2.14) випливає, що факторизація матриці A виконується за n стадій. На кожній j -й стадії послідовно обчислюють елементи lij чергового j -го стовпчика матриці L за формулою , (2.15) та елементи uji чергового j -го рядка матриці U за формулою . (2.16) Із формул (2.15), (2.16) випливає, що на першій стадії елементи , а . На практиці елементи матриць L та U в процесі розкладання розміщуються на місцях елементів матриці А, причому елементи не запам’ятовуються. Таким чином, факторизована форма матриці А має вигляд
. Після факторизації матриці A система буде мати вигляд LUX = B. (2.17) Позначимо Y = UX, тоді із (2.17) маємо рівняння LY = B. (2.18) Оскільки L – нижня трикутна матриця, то розв’язок системи (2.18) отримуємо прямою підстановкою: . Після цього залишається розв’язати ще систему з верхньою трикутною матрицею U, всі діагональні елементи якої дорівнюють 1: UX = Y. (2.19) Розв’язавши систему (2.19), остаточно отримаємо шуканий вектор X: . Наприклад: Розв’язати систему лінійних алгебраїчних рівнянь методом LU-декомпозицій. Розв’язок: Виконаємо операцію факторизації: : при при при . В результаті маємо дві трикутні матриці: , . Розважимо систему : або Звідси маємо: Розважимо систему : або Звідси маємо: Відповідь: .
Метод простих ітерацій Розв’яжемо перше рівняння системи (2.1) відносно , друге відносно і так далі. В результаті отримаємо систему рівнянь еквівалентну системі (2.1): (2.20) де , при , при . Використовуючи позначення , , систему (2.20) можна записати у матричному вигляді . Таким чином, метод простої ітерації є частковим випадком методу коли матриця С дорівнює: Для розв’язання системи за допомогою формули необхідно вибрати початкове наближення . В якості такого наближення можна вибрати . На практиці при застосуванні методу простої ітерації за критерій зупинки обчислень вибирають збіжність за аргументом: , (2.21) де D — задана абсолютна похибка обчислень або: , (2.22) де ‑ задана відносна похибка обчислень. Для збіжності ітераційного процесу методу простої ітерації достатньо, щоб матриця системи була діагонально домінуючою: . (2.23) Наприклад: Нехай необхідно розв’язати систему рівнянь методом простої ітерації з абсолютною похибкою не більше 1%: (2.24) Перевіримо виконання умови (2.23): Умова (2.23) виконується, отже система (2.24) може бути розв’язана методом простої ітерації. Ітераційна формула відповідно до має вигляд: . Виконаємо ітерацію. . Використовуючи норми , перевіримо досягнуту похибку розв’язку: Потрібна точність не досягнута, виконуємо наступну ітерацію: . Потрібна точність не досягнута, виконуємо наступну ітерацію: . Необхідна точність досягнута. Для порівняння, точний розв’язок системи .
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-06; просмотров: 483; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.226.82.78 (0.062 с.) |