Схема єдиного ділення ( метод Гауса)

Опис документу:
У цьому документі йде мова про розв'язування систем лінійних алгебраїчних рівнянь.

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

Перегляд
матеріалу
Отримати код Поділитися

РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

Нехай дано систему n лінійних алгебраїчних рівнянь з n змінними

ax= b (i = 1,2,…n). (1)

Систему (1) можна записати у вигляді одного матричного рівняння АХ=В,

де А = (а) = – матриця коефіцієнтів а (індекс і вказує рівняння, якому належить коефіцієнт, а індекс j – змінну, при якій він стоїть),

В = , Х = – відповідно стовпець вільних членів і стовпець змінних.

Упорядкована сукупність n чисел с, с, …, с, яка, будучи підставленою в систему (1) замість х, х , …, х, перетворює всі рівняння в правильні числові рівності, називається розв’язком системи (1).

Якщо визначник системи (1)

= det A = 0,

то вона має єдиний розв’язок. Його можна обчислити за формулами Крамера

х = , (к = 1, 2, …, n),

де матрицю А дістають з матриці А, замінивши її к-й стовпець стовпцем вільних членів.

Методи розв’язування систем ліній них рівнянь можна поділити на дві групи: точні й ітераційні.

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

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

Метод послідовного виключення змінних.

Найпростішим методом розв’язання систем лінійних алгебраїчних рівнянь є метод послідовного виключення змінних, або метод Гауса. Є кілька модифікацій цього методу. Розглянемо схему єдиного ділення, за якою систему розв’язують в два етапи. На першому етапі вихідну систему рівнянь зводять до рівносильної їй системи трикутної форми. Цей процес перетворення називають прямим ходом. На другому етапі, який називають зворотним ходом, знаходять розв’язок лінійної системи рівнянь трикутної форми.

Обмежимося розглядом системи трьох рівнянь з трьома змінними

(1)

визначник якої не дорівнює нулю.

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

++=, (2)

де

=/, (=) (3).

Виключимо тепер змінну з другого і третього рівнянь системи(1). Для цього рівняння (2) помножимо послідовно спочатку на коефіцієнт і віднімемо його від другого рівняння системи (1), а потім на a і віднімемо від третього рівняння системи (1). Дістанемо систему двох рівнянь з двома змінними і

(4)

де коефіцієнти обчислюють за формулами

=- (). (5)

Верхній індекс (1) вказує на те, що над коефіцієнтами системи (4) виконано перше перетворення.

Далі поділимо коефіцієнти першого рівняння системи (4) на (якщо =0, то переставляємо рівняння місцями). Дістанемо рівняння

+=, (6)

де

=/, (). (7)

Із системи (4) виключимо змінну так само, як і з системи (1). Дістанемо рівняння

x=, (8)

де

=- (). (9)

З рівняння (8) маємо

= , (10)

де

=/. (11)

Після трьох кроків перетворення дістанемо систему рівнянь трикутної форми

(12)

яка еквівалентна системі (1).

На цьому прямий хід методу Гаусса завершено. Описаний процес перетворень системи (1) до рівносильної ій системи (12) можна здійснити, якщо виконуються умови 0, 0, 0. Можна довести, що коли 0, то для цього достатньо, щоб поряд з умовою визначник 0 виконувалась нерівність

Близькість діагональних коефіцієнтів системи (1) до нуля може призвести до значної втрати точності.

Оскільки системи (1) і (12) еквівалентні, то розв’язком системи (1) буде розв’язок системи(12), який можна записати формулами

(13)

Цим завершено зворотний хід методу Гаусса.

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

Кроки перетв-

орень

рядок

Коефіцієнти при змінних

Вільний член

Контроль

Х1

Х2

Х3

Контрольна сума

Рядкова сума

1

2

3

4

5

6

7

8

1

1

2

3

2

4

5

6

1

3

7

8

1

4

9

10

11

1

1

1

У процесі розв’язування системи рівнянь треба організувати контроль правильності обчислень. Щоб вчасно виявити (і виправити) випадкові обчислювальні помилки, доцільно забезпечити контроль правильності обчислень у кожному рядку таблиці (так званий поточний контроль). Для цього до схеми обчислень введено два додаткових стовпців: 7-й- контрольна сума і 8-й- рядкова сума.

Контрольна сума () – це сума коефіцієнтів при змінних і вільного члена для кожного рівняння системи (1)

= (). (14)

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

Рядкові суми – це суми всіх елементів відповідного рядка, що містяться в стовпцях з 3-го по 6-й включно. Поточний контроль обчислень за схемою єдиного ділення полягає в тому, що в кожному рядку обчислюють контрольну і рядкові суми та порівнюють їх між собою. Якщо вони збігаються або відрізняються на 1-2 одиниці нижчого розряду, що обумовлено впливом похибок округлення, то обчислення виконано правильно і можна переходити до обробки наступного рядка. Якщо ці суми в будь –якому рядку значно відрізняються між собою, то обчислення треба припинити і зясувати причину розбіжності. Значна розбіжність між контрольною і рядковими сумами може свідчити про випадкові помилки в обчисленнях або про нестійкість алгоритму обчислень відносно похибок округлень. Якщо причиною розбіжності є випадкова помилка, то її виправляють і продовжують обчислення. А якщо причиною розбіжності сум є нестійкість алгоритму обчислень відносно похибок округлення, то від нього слід відмовитися.

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

Розв’язок , , системи (1) зв’язаний з розв’язком , , допоміжної системи

(). (15)

простою залежністю

(). (16)

Справді, підставивши (16) і врахувавши формули (14), дістанемо тотожність

().

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

Другою формою заключного контролю є безпосередня перевірка знайденого розв’язку підстановкою його і систему (1). Якби всі обчислення виконувалися точно, то в результаті підстановки дістали б правильну числову рівність. Але в процесі обчислень виконувалися округлення, тому значення лівих частин рівнянь системи (1), взагалі кажучи, не збігатимуться із значенням їх правих частин. Значення різниць між вільними членами вихідної системи лінійних рівнянь і результатами підстановки в ці рівняння обчислених значень змінних називають нев’язками. Якщо невязки досить малі, то можна стверджувати, що розв’язок системи (1) знайдено з малими похибками. Якщо невязки досить значні, то це означає, що значення шуканих змінних обчислено з недостатньою точністю і їх треба уточнити. Це буває здебільшого тоді, коли проміжні обчислення виконують з недостатньою точністю. Зменшити невязки можна так: розв’язують систему повторно, залишаючи в проміжних результатах більшу кількість десяткових розрядів, ніж при попередньому розв’язуванні, або обчислюють значення поправок до знайденого раніше розв’язку системи. Перший шлях досить громіздкий, потребує тим більших затрат обчислювальної роботи, чим вищий порядок системи. Тому перевагу доцільно надати другому шляху.

Нехай - наближений розв’язок системи (1). Підставивши його в систему (1), дістанемо невязка

(17)

Шукатимемо тепер новий розв’язок системи (1) в такому вигляді

,

, (18)

,

де , , - шукані похибки розв’язку. Підставивши (18) в систему (1) і взявши до уваги невязки (17), для знаходження поправок (j=1,2,3) дістанемо систему рівнянь

(). (19)

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

Практичні завдання.

№1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

Приклад розв’язання

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

Обчислювання проведемо методом єдиного ділення

Коефіцієнти при невідомих

Вільні члени

Контрольні суми

Рядкові суми

X1

X2

X3

X4

0,68

0,21

-0.11

-0,08

0,05

-0,13

-0,84

0,15

-0,11

0,27

0,28

-0,5

0.08

-0,8

0,06

-0,12

2,15

0,44

-0,83

1,16

2,85

-0,01

-1,44

0,61

2,85

-0,01

-1,44

0,61

1

0,0735

-0,1618

0,1176

3,1618

4,1912

4,1912

-0,1454

-0,8319

0,1559

0,30398

0,2622

-0,5129

-0,8247

0,0729

-0,1106

-0.22398

-0,4822

1,4129

-0,89015

-0,97897

0,97897

-0,9801

-0,97896

0,9453

1

-2,0906

5,6719

1,5404

6,1221

-1,47697

-0,18697

4,79139

-0.9948

0,7992

1,1723

4,1140

-0,00913

1

-3,2441

-0,5411

-2,7854

-1,6013

1,0711

-0,5299

1

-0,6689

0,3309

2,8264

-0,3337

-2,710

-0,6689

3,8263

0,6664

-1,7119

0,3309

Відповідь x1=2,826; x2=-0,334; x3=-2,711; x4=-0669.

Зверніть увагу, свідоцтва знаходяться в Вашому особистому кабінеті в розділі «Досягнення»

Всеосвіта є суб’єктом підвищення кваліфікації.

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

Співпраця із закладами освіти.

Дізнатись більше про сертифікати.

Приклад завдання з олімпіади Українська мова. Спробуйте!
До ЗНО з МАТЕМАТИКИ залишилося:
0
3
міс.
2
2
дн.
2
1
год.
Готуйся до ЗНО разом із «Всеосвітою»!