Розв’язок систем лінійних рівнянь

ВСТУП

 

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

Дані методичні вказівки є керівництвом до виконання курсової роботи, присвяченої важливому розділу обчислювальної математики, а саме чисельним методам розв’язку систем рівнянь. Вказівки складено на основі лекційного курсу у відповідності до робочої навчальної програми для студентів денної форми навчання напрямів підготовки 6.050201 «Системна інженерія», спеціалізація «Системи управління та автоматика» та 6.050903 «Телекомунікації», спеціалізація «Телекомунікаційні системи та мережі».

Розділ обчислювальної математики, що розглядається, обумовив таку структуру роботи. Частина 1 присвячена методам розв’язку систем лінійних рівнянь. Розглянуто методи перевірки існування розв’язку; прямі методи розв’язку, такі як метод зворотної матриці, метод Крамера, методи Гауса; числові методи розв’язку – уточнення коренів, простої ітерації, Зейделя.

Частина 2 вказівок містить числові методи розв’язку систем нелінійних рівнянь, а саме метод Ньютона, метод ітерацій та Зейделя.

В частині 3 розглянуто числові методи розв’язку задачі Коші для систем диференціальних рівнянь (ДР), а також рівнянь вищих порядків, розв’язок яких зводиться до розв’язку систем ДР. Наведено методи Ейлера, Рунге-Кута, багатокрокові методи Адамса. Крім того, наведено метод розв’язку крайової задачі для рівняння ІІ порядку.

Додаток містить вимоги до оформлення пояснювальної записки до курсової роботи відповідно до стандартів ДСТУ 3008-95. Також під час виконання курсової роботи студентам необхідно наводити алгоритми згідно з ГОСТ 19.701-90.

Розв’язок систем лінійних рівнянь

 

Постановка задачі

 

Система з лінійних алгебраїчних рівнянь з невідомими має вид:

. (1.1)

Сукупність коефіцієнтів цієї системи запишемо у виді таблиці

. (1.2)

Дана таблиця з елементів, що складається з рядків і стовпців називається квадратною матрицею порядку .

Використовуючи поняття матриці , систему рівнянь (1.1) можна записати в матричному виді:

. (1.3)

де и – вектор-стовпець невідомих і вектор-стовпець правих частин відповідно:

, .

Сукупність чисел (або, коротше, вектор ), що перетворюють систему (1.1) на тотожність, називається розв’язком цієї системи, а самі числа – її коренями.

 

Для існування єдиного розв’язку системи лінійних рівнянь (1.1) необхідно і достатньо, щоб визначник матриці не дорівнював числу 0:

.

 

Методи розв’язку систем лінійних рівнянь поділяються на дві групи – прямі та ітераційні. Прямі (точні) методи використовують кінцеві співвідношення (формули) для обчислення невідомих. Вони дають розв’язок після виконання наперед відомого числа операцій. Приклади цих методів: метод зворотної матриці, метод Крамера, метод Гауса.

Ітераційні методи – це методи послідовних наближень, що вимагають деякого початкового наближення. За допомогою певного алгоритму проводиться один цикл обчислень, який називається ітерацією. Після виконання ітерації буде знайдено нове наближення. Ітерації проводяться до одержання розв’язку з необхідною точністю. До цієї групи методів належать, наприклад, метод простих ітерацій і метод Зейделя.

 

Метод зниження порядку

 

Полягає в обчисленні визначників -го порядку.

Мінором елемента визначника -го порядку називається детермінант -го порядку, який утворюється з заданого визначника шляхом викреслювання -го рядка та -го стовпця.

Алгебраїчним доповненням елемента визначника називається відповідний мінор , взятий з певним знаком

Властивість 9. Визначник дорівнює сумі добутків елементів будь-якого рядка (стовпця) на їхні алгебраїчні доповнення.

. (1.4)

Ця властивість називається розкладанням визначника по елементах рядка (стовпця).

Використовуючи наведені властивості, можна зручно обчислювати визначники вищих порядків. Метод зниження порядку – добитися, щоб в деякому рядку (стовпці) стало якомога більше нулів, і розкласти визначник по елементах цього рідка (стовпця).

Зрозуміло, що формула (1.4) значно спрощується, якщо всі крім одного елементи рядку або стовпця дорівнюють 0 (метод ефективного зниження порядку).

 

Прямі методи

 

Метод Крамера

 

Згідно даного методу кожне невідоме системи (1.1) представляється у виді відношення визначників. Запишемо його для системи рівнянь порядку :

Тоді

, ,

де , , .

В методі Крамера необхідно обчислити () визначник -го порядку, що при великому значенні потребує значної кількості арифметичних операцій. Тому метод застосовується лише для розв’язку систем, що містять декілька рівнянь.

 

Метод зворотної матриці

 

Якщо система рівнянь – невироджена, тобто визначник матриці системи , то система (1.1) або еквівалентне їй матричне рівняння (1.3), має єдиний розв’язок.

За умови існує обернена матриця . Помноживши обидві частини рівняння (1.3) зліва на матрицю , одержимо

або

. (1.5)

Формула (1.5) дає розв’язок рівняння (1.3).

 

Метод Гауса

 

– За схемою одиничного ділення

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

Зворотний хід методу Гауса полягає в послідовному обчисленні невідомих: розв’язуючи останнє рівняння, знаходимо єдине невідоме . Далі, використовуючи це значення, з попереднього рівняння обчислюємо і т.д. Останнім знаходимо з першого рівняння.

Розглянемо схему застосування методу Гауса для системи з трьох рівнянь:

(1.6)

Для виключення з другого і третього рівнянь додамо до кожного з них перше, помножене на і відповідно. Одержимо рівносильну систему виду:

, (1.7)

де ,

,

Помноживши друге рівняння системи (1.7) на і додавши результат до третього рівняння, виключимо тим самим з третього рівняння. В результаті система (1.7) прийме вид:

, (1.8)

де ,

.

Система (1.8) має трикутний вид. На цьому закінчується прямий хід методу Гауса.

Зазначимо, що в процесі виключення невідомих, доводиться виконувати операції ділення на коефіцієнти , і т.д. Тому вони мають бути відмінні від нуля. В іншому випадку необхідно відповідним чином переставити рівняння системи.

Зворотний хід починається з рішення третього рівняння системи (1.8):

.

Використовуючи це значення, можна знайти з другого рівняння, а потім з першого:

,

.

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

 

– З вибором головного елементу

Ця модифікація методу Гауса полягає в тому, що вимога нерівності 0 коефіцієнтів замінюється на більш жорстку: зі всіх елементів, що залишилися в -му стовпці, необхідно обрати найбільший за модулем, і переставити рівняння системи так, що цей елемент став діагональним.

 

– За схемою Жордана

Також є модифікацією метода Гауса. В цьому випадку матриця системи приводиться до діагонального виду, тобто всі елементи, окрім елементів головної діагоналі, дорівнюють 0. Особливих переваг немає: полегшується зворотний хід, проте через збільшення кількості операцій, ускладнюється прямий хід.

Алгоритм розв’язку системи (1.1) методом Гауса-Жордана.

1. Нехай .

2. Перевірити, чи відмінний діагональний елемент від .

3. Якщо відмінний, то -й рядок стає робочим рядком. Якщо , то необхідно замінити -й рядок на -й (), в якій .

4. Для обчислюємо нові матричні елементи, які позначимо, подібно попереднім, за правилом:

, якщо ,

, якщо ,

де

;

аналогічно представимо нові праві частини рівнянь:

.

5. Збільшуємо на одиницю, якщо , и переходимо до пункту 2. Це приведе до того, що всі елементи -го стовпця, за виключенням діагонального елементу, дорівнюватимуть . В результаті отримаємо діагональну матрицю:

.

6. Обчислення вектора-розв’язку :

.

 

– Метод прогонки

Модифікація методу Гауса. Цей метод використовується для розв’язку частинного випадку розріджених систем лінійних рівнянь – рівнянь з тридіагональною матрицею. Такі системи виникають при числовому розв’язку крайових задач для диференціальних рівнянь.

Запишемо систему рівнянь в виді:

де .

Метод прогонки складається з двох етапів – прямої прогонки (аналог прямого ходу методу Гауса) та зворотної прогонки (аналогу зворотного ходу методу Гауса). Пряма прогонка полягає в вираженні кожного невідомого через за допомогою прогоночних коефіцієнтів:

.

З першого рівняння

.

Оскільки , отже: .

З другого рівняння:

,

,

,

.

Так само : , де .

Аналогічно можна обчислити прогоночні коефіцієнти для будь-якого .

,

де .

Отже,

.

Далі виконується зворотна прогонка, для чого спочатку обчислюється з останнього рівняння:

,

,

,

,

.

Потім за формулою

.

та формулами прогоночних коефіцієнтів.

Під час обчислення та необхідно враховувати можливість ділення на 0. Щоб запобігти цьому бажано, щоб в таких системах виконувалась умова переважання діагональних елементів, тобто і хоча б для одного нерівність була строгою.

 

 

Числові методи

 

Метод уточнення коренів

 

Цей метод дозволяє уточнити розв’язок, отриманий за допомогою прямого методу. Метод уточнення коренів дає можливість зменшити помилки обчислень, а саме помилки округлення.

Розглянемо систему лінійних рівнянь (1.1):

.

Нехай за допомогою будь-якого прямого методу (наприклад, методу Гауса), були обчислені наближені значення невідомих . Підставивши ці розв’язки в ліві частини системи, отримаємо значення , що відрізняються від :

.

Введемо позначення – похибка значень невідомих, , .

Віднімаючи з вихідної системи систему рівнянь з наближеними значеннями коренів, отримаємо таку систему:

.

Розв’язуючи цю систему знаходимо значення похибок (), які далі використовуються як поправки до розв’язку, тобто:

.

В той самий спосіб можна знайти поправки до розв’язку () та наступні наближення змінних і т.д. Процес продовжується доти, поки всі чергові значення похибок (поправок) не стануть достатньо малими (такими, що задовольняють нас).

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

 

Метод простої ітерації

 

Проілюструємо цей метод на прикладі розв’язку системи:

(1.9)

Збіжність даного методу гарантується, якщо діагональні елементи не дорівнюють 0 і для них виконується умова:

,

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

Зазначимо, що будь-які системи лінійних рівнянь можна звести до потрібного для збіжності виду за допомогою лінійних перетворень (додавання, вирахування, множення на константу) над рівняннями системи.

Припустимо, що для даної системи умова збіжності виконується. Виразимо невідомі , , з першого, другого і третього рівнянь системи (1.9) відповідно:

. (1.10)

Задамо деякі початкові (нульові) наближення значень невідомих. В якості нульових значень можуть бути обрані: стовпець вільних членів , відношення , а також будь-які інші значення (наприклад, нульові), тому що виконання умови збіжності забезпечує досягнення результату при будь-яких початкових умовах.

Підставляючи ці значення в праву частину рівнянь системи (1.10), одержуємо нове (перше) наближення для невідомих , , .

. (1.11)

Використовуючи обчислені значення , , , можна тим саме способом провести другу ітерацію, у результаті якої будуть знайдені другі наближення до розв’язку , , . Наближення з номером можна представити у виді:

. (1.12)

Ітераційний процес продовжується доти, поки значення , , , не стануть близькими з заданою похибкою до значень , , , що можна перевірити критерієм по абсолютних відхиленнях

, (1.13)

або критерієм по відносних відхиленнях (при )

, (1.14)

де – задана похибка невідомих. При виконанні умови (1.13) або (1.14) процес ітерацій припиняється і за шукані розв’язки приймаються їх останні обчислені значення.

Описаний алгоритм може бути розширений на систему з лінійних рівнянь.

 

Метод Зейделя

 

Ітераційний метод Зейделя відрізняється від методу простої ітерації тим, що на -й ітерації при обчисленні використовуються значення , ,..., , обчислені на тій самій ітерації. Наближення на -м кроці стосовно до системи (1.9) за методом Зейделя має вид:

, (1.15)

Зазначені вище умова збіжності та умова припинення обчислень для методу простої ітерації залишаються вірними для методу Зейделя.

 

Завдання

 

Розв’язати систему лінійних рівнянь:

1) прямими методами (зворотної матриці, Крамера, Гауса) з двома знаками після коми;

2) уточнити отриманий в п. 1) розв’язок числовими методами (уточнення коренів, ітерацій або Зейделя) з точністю ;

3) Навести блок-схеми алгоритмів використаних методів.

 

№	Система рівнянь	Методи
1.		1) метод Крамера; 2) метод уточнення коренів;
2.		1) метод Крамера; 2) метод простої ітерації;
3.		1) метод Крамера; 2) метод Зейделя;
4.		1) метод зворотної матриці; 2) метод уточнення коренів;
5.		1) метод зворотної матриці; 2) метод простої ітерації;
6.		1) метод зворотної матриці; 2) метод Зейделя;
7.		1) метод Гауса за схемою одиничного ділення; 2) метод уточнення коренів;
8.		1) метод Гауса за схемою одиничного ділення; 2) метод простої ітерації;
9.		1) метод Гауса за схемою одиничного ділення; 2) метод Зейделя;
10.		1) метод Гауса з вибором головного елементу; 2) метод уточнення коренів;
11.		1) метод Гауса з вибором головного елементу; 2) метод простої ітерації;
12.		1) метод Гауса з вибором головного елементу; 2) метод Зейделя;
13.		1) метод Гауса за схемою Жордана; 2) метод уточнення коренів;
14.		1) метод Гауса за схемою Жордана; 2) метод простої ітерації;
15.		1) метод Гауса за схемою Жордана; 2) метод Зейделя;
16.		1) метод Крамера; 2) метод уточнення коренів;
17.		1) метод Крамера; 2) метод простої ітерації;
18.		1) метод Крамера; 2) метод Зейделя;
19.		1) метод зворотної матриці; 2) метод уточнення коренів;
20.		1) метод зворотної матриці; 2) метод простої ітерації;
21.		1) метод зворотної матриці; 2) метод Зейделя;
22.		1) метод Гауса за схемою одиничного ділення; 2) метод уточнення коренів;
23.		1) метод Гауса за схемою одиничного ділення; 2) метод простої ітерації;
24.		1) метод Гауса за схемою одиничного ділення; 2) метод Зейделя;
25.		1) метод Гауса з вибором головного елементу; 2) метод уточнення коренів;
26.		1) метод Гауса з вибором головного елементу; 2) метод простої ітерації;
27.		1) метод Гауса з вибором головного елементу; 2) метод Зейделя;
28.		1) метод Гауса за схемою Жордана; 2) метод уточнення коренів;
29.		1) метод Гауса за схемою Жордана; 2) метод простої ітерації;
30.		1) метод Гауса за схемою Жордана; 2) метод Зейделя;

 

 

Постановка задачі

Багато практичних задач зводиться до розв’язку систем нелінійних рівнянь. На відміну від систем лінійних рівнянь, не існує прямих методів розв’язку нелінійних систем. Загальний метод розв’язку системи рівнянь має складатися з двох етапів: відділення коренів і подальшого уточнення розв’язку. Для одержання розв’язку звичайно використовуються ітераційні методи. Вибір первинних наближень впливає на збіг ітераційного процесу; вони мають бути досить близькими до точного розв’язку. У протилежному випадку ітераційний процес може не збігтися. Первинне наближення знаходять графічно (для випадку двох рівнянь із двома невідомими) або іншими методами (аналітичними, методом проб) для систем з великою кількістю рівнянь.

Розглянемо систему нелінійних рівнянь:

(2.1)

У матричному виді:

(2.2)

де

, (2.3)

Метод Ньютона і методи простої ітерації та Зейделя є ітераційними методами. Метод Ньютона має велику швидкість збігу. У той же час метод простої ітерації має більш прості умови збіжності і є менш критичним до вибору первинного наближення. Тому для високоточних обчислень рекомендується застосовувати спочатку метод простої ітерації. Після того, як знайдені наближення, досить близькі до точних, використовувати метод Ньютона.

Числові методи розв’язку

Метод Ньютона

 

Якщо знайдені -і наближення до розв’язку , можна записати точний розв’язок системи (2.1) у виді:

,

де – виправлення до розв’язку, що шукається.

Розкладаючи ліву частину

(2.4)

у ряд Тейлора, обмежуючись лінійними членами розкладання, одержуємо систему лінійних рівнянь відносно виправлень:

.

Розв’язувати отриману систему лінійних рівнянь можна будь-яким методом з розглянутих в розділі 1. При розв’язанні системи методом зворотної матриці отримаємо рекурентну формулу для обчислення виправлень, а звідси і формулу ітераційного процесу визначення розв’язку системи (2.1) або (2.2), яка отримала назву методу Ньютона:

(2.5)

, (2.6)

де – матриця Якобі,

– матриця, зворотна до матриці Якобі.

Якщо в формулі (2.5) матрицю, зворотну до матриці Якобі, обчислювати на кожній ітерації в фіксованій початковій точці замість (тобто використовуємо зафіксовану зворотну матрицю), отримаємо модифікований метод Ньютона. Очевидно, цей метод вимагає менше обчислень, але й дає меншу точність.

Процес ітерації (2.5) триває доти, поки не буде справедлива нерівність:

(2.7)

де – необхідна точність,

Зауваження Метод Ньютона ефективний тільки при достатній близькості первинного наближення до розв’язку системи. Вимоги до збіжності методу досить жорсткі, теореми про швидкість збіжності, стійкість наведені у [7]. Практично метод Ньютона застосовується для уточнення розв’язку, отриманого яким-небудь іншим методом.

Матриця Якобі містить частинні похідні першого порядку. Оскільки аналітичне диференціювання в загальних випадках небажано, окремі похідні заміняють їх наближеними кінцево-різницевими значеннями:

, (2.8)

.

 

 

Метод простої ітерації

 

Для розв’язку системи нелінійних рівнянь методом простої ітерації необхідно навести її у виді:

(2.9)

Ітераційний процес реалізується наступними формулами:

(2.10)

Ітераційний процес продовжується доки не буде досягнуте виконання умов (2.11) або (2.12):

· критерій з абсолютних відхилень:

(2.11)

· критерій з відносних відхилень (якщо ):

(2.12)

де – задана похибка невідомих.

Умова збіжності методу визначається формулою

, (2.13)

де , – перша або друга норма матриці ,

(2.14)

матриця частинних похідних правих частин , , системи (2.9), обчислених у точці первинного наближення , , …, .

Метод Зейделя

 

Метод Зейделя є модифікованим методом простої ітерації, на відміну від якого, уточнені значення коренів відразу підставляються в наступні рівняння.

Послідовні наближення визначаються із співвідношень:

 

(2.15)

Все сказане відносно збіжності методу простої ітерації в п. 2.2.2, вірно і для методу Зейделя, тобто умова збіжності залишається такою самою.

 

Завдання

 

Розв’язати систему нелінійних рівнянь з точністю до .

1) За методом Ньютона отримати систему лінійних рівнянь та розв’язати ії прямим методом з завдання 1.5 п. 1);

2) Розв’язати систему ітераційним методом (ітерацій або Зейделя). Метод вказано в таблиці варіантів;

3) Порівняти результати, отримані за пп. 1) і 2);

4) Навести блок-схеми алгоритмів використаних методів.