Розв'язання систем лінійних рівнянь алгебри методом ітерацій. Рішення слау методом простої ітерації
Перевагою ітераційних методів є їх застосування до погано обумовлених систем і систем високих порядків, їх самовиправність і простота реалізації на ПК. Ітераційні методи для початку обчислення вимагають завдання будь-якого початкового наближення до шуканого рішення.
Слід зауважити, що умови та швидкість збіжності ітераційного процесу істотно залежать від властивостей матриці. Асистеми та від вибору початкових наближень.
Для застосування методу ітерацій вихідну систему (2.1) або (2.2) необхідно привести до вигляду
після чого ітераційний процесвиконується за рекурентними формулами
, k = 0, 1, 2, ... . (2.26а)
Матриця Gта вектор отримані в результаті перетворення системи (2.1).
Для збіжності (2.26 а) необхідно і достатньо, щоб | i(G)| < 1, где li(G) - всі власні значенняматриці G. Схожість буде також і у разі, якщо || G|| < 1, так как |li(G)| < " ||G||, де "- будь-який. |
Символ | ... || означає норму матриці. При визначенні її величини найчастіше зупиняються на перевірці двох умов:
||G|| = чи || G|| = , (2.27)
де. Східність гарантована також, якщо вихідна матриця Амає діагональне переважання, тобто.
. (2.28)
Якщо (2.27) або (2.28) виконується, метод ітерації сходиться за будь-якого початкового наближення . Найчастіше вектор беруть або нульовим, або одиничним, або беруть сам вектор (2.26).
Існує багато підходів до перетворення вихідної системи (2.2) із матрицею Адля забезпечення виду (2.26) або виконання умов збіжності (2.27) та (2.28).
Наприклад, (2.26) можна отримати в такий спосіб.
Нехай А = У+ З, det У¹ 0; тоді ( B+ З)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B-1 , Звідки = − B –1 C+ B –1 .
Поклавши – B –1 C = G, B-1 = , Отримаємо (2.26).
З умов збіжності (2.27) та (2.28) видно, що подання А = У+ Зне може бути довільним.
Якщо матриця Азадовольняє умовам (2.28), то як матриця Уможна вибрати нижню трикутну:
, a ii ¹ 0.
; Þ ; Þ 
; Þ
Підбираючи параметр a, можна домогтися, щоб || G|| = ||E+ a A|| < 1.
Якщо має місце переважання (2.28), тоді перетворення на (2.26) можна здійснити, вирішуючи кожне i-е рівняння системи (2.1) щодо x iза наступними рекурентними формулами:
(2.28а)
Якщо у матриці Анемає діагонального переважання, його потрібно домогтися за допомогою якихось лінійних перетворень, які не порушують їх рівносильності.
Як приклад розглянемо систему
(2.29)
Як видно, в рівняннях (1) і (2) немає діагонального переважання, а (3) є, тому його залишаємо незмінним.
Досягнемо діагонального переважання в рівнянні (1). Помножимо (1) на a, (2) на b, складемо обидва рівняння та в отриманому рівнянні виберемо a та b так, щоб мало місце діагональне переважання:
(2a + 3b) х 1 + (–1,8a + 2b) х 2 + (0,4a - 1,1b) х 3 = a.
Взявши a = b = 5, отримаємо 25 х 1 + х 2 – 3,5х 3 = 5.
Для перетворення рівняння (2) з переважанням (1) помножимо на g, (2) помножимо на d і (2) віднімемо (1). Отримаємо
(3d – 2g) х 1+ (2d + 1,8g) х 2 +(-1,1d - 0,4g) х 3 = −g.
Поклавши d=2, g=3, отримаємо 0 х 1 + 9,4 х 2 – 3,4 х 3 = -3. В результаті отримаємо систему
(2.30)
Такий прийом можна застосовувати для визначення рішення широкого класу матриць.
або 
Взявши як початкове наближення вектор = (0,2; –0,32; 0) Т, вирішуватимемо цю систему за технологією (2.26 а):
k = 0, 1, 2, ... .
Процес обчислення припиняється, коли два сусідніх наближення вектора рішення збігаються точності, тобто.
.
Технологія ітераційного вирішення виду (2.26 а) названа методом простої ітерації .
Оцінка абсолютної похибкидля методу простої ітерації:
де символ | ... || означає норму.
Приклад 2.1. Методом простої ітерації з точністю e = 0,001 розв'язати систему лінійних рівнянь:
Число кроків, що дають відповідь з точністю до e = 0,001, можна визначити із співвідношення
£ 0,001.
Оцінимо збіжність за формулою (2.27). Тут | G|| = = max(0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.
Як початкове наближення візьмемо вектор вільних членів, тобто = (2,15; -0,83; 1,16; 0,44) Т. Підставимо значення вектора (2.26 а):
Продовживши обчислення, результати занесемо до таблиці:
| k | х 1 | х 2 | х 3 | х 4 |
| 2,15 | –0,83 | 1,16 | 0,44 | |
| 2,9719 | –1,0775 | 1,5093 | –0,4326 | |
| 3,3555 | –1,0721 | 1,5075 | –0,7317 | |
| 3,5017 | –1,0106 | 1,5015 | –0,8111 | |
| 3,5511 | –0,9277 | 1,4944 | –0,8321 | |
| 3,5637 | –0,9563 | 1,4834 | –0,8298 | |
| 3,5678 | –0,9566 | 1,4890 | –0,8332 | |
| 3,5760 | –0,9575 | 1,4889 | –0,8356 | |
| 3,5709 | –0,9573 | 1,4890 | –0,8362 | |
| 3,5712 | –0,9571 | 1,4889 | –0,8364 | |
| 3,5713 | –0,9570 | 1,4890 | –0,8364 |
Схожість у тисячних частках має місце вже на 10-му кроці.
Відповідь: х 1» 3,571; х 2 »-0,957; х 3» 1,489; х 4» -0,836.
Це рішення може бути отримано за допомогою формул (2.28 а).
Приклад 2.2. Для ілюстрації алгоритму за допомогою формул (2.28 а) Розглянемо рішення системи (тільки дві ітерації):
; . (2.31)
Перетворимо систему до виду (2.26) згідно (2.28) а):
Þ 
(2.32)
Візьмемо початкове наближення = (0; 0; 0) Т. Тоді для k= 0 очевидно, що значення = (0,5; 0,8; 1,5) Т. Підставимо ці значення (2.32), тобто при k= 1 отримаємо = (1,075; 1,3; 1,175) Т.
Помилка e 2 = 
= max(0,575; 0,5; 0,325) = 0,575.
Блок-схема алгоритму знаходження рішення СЛАУ за методом простих ітераційзгідно з робочими формулами (2.28 а) представлена на рис. 2.4.
Особливістю блок-схеми є наявність наступних блоків:
– блок 13 – його призначення розглянуто нижче;
– блок 21 – виведення результатів на екран;
– блок 22 – перевірка (індикатор) збіжності.
Проведемо аналіз запропонованої схеми з прикладу системи (2.31) ( n= 3, w = 1, e = 0,001):
= ; .
Блок 1. Вводимо вихідні дані A, , w, e, n: n= 3, w = 1, e = 0,001.
Цикл I. Задаємо початкові значення векторів x 0iі х i (i = 1, 2, 3).
Блок 5. Обнулюємо лічильник числа ітерацій.
Блок 6. Обнулюємо лічильник поточної похибки.
Уциклі II виконується зміна номерів рядків матриці Аі вектор.
Цикл II:i = 1: s = b 1 = 2 (блок 8).
Переходимо до вкладеного циклу III, блок9 – лічильник номерів стовпців матриці А: j = 1.
Блок 10: j = i, отже, повертаємось до блоку 9 і збільшуємо jна одиницю: j = 2.
У блоці 10 j ¹ i(2 ¹ 1) – виконуємо перехід до блоку 11.
Блок 11: s= 2 - (-1) × х 0 2 = 2 - (-1) × 0 = 2, переходимо до блоку 9, в якому jзбільшуємо на одиницю: j = 3.
У блоці 10 умова j ¹ iвиконується тому переходимо до блоку 11.
Блок 11: s= 2 - (-1) × х 0 3 = 2 – (–1) × 0 = 2, після чого переходимо до блоку 9, у якому jзбільшуємо на одиницю ( j= 4). Значення jбільше n (n= 3) – закінчуємо цикл та переходимо до блоку 12.
Блок 12: s = s / a 11 = 2 / 4 = 0,5.
Блок 13: w = 1; s = s + 0 = 0,5.
Блок 14: d = | x i – s | = | 1 – 0,5 | = 0,5.
Блок 15: x i = 0,5 (i = 1).
Блок 16. Перевіряємо умову d > de: 0,5 > 0, отже, переходимо до блоку 17, в якому присвоюємо de= 0,5 і виконуємо повернення за посиланням « А» до наступного кроку циклу II – до блоку7, в якому iзбільшуємо на одиницю.
Цикл II: i = 2: s = b 2 = 4 (блок 8).
j = 1.
За допомогою блоку 10 j ¹ i(1 ¹ 2) – виконуємо перехід до блоку 11.
Блок 11: s= 4 - 1 × 0 = 4, переходимо до блоку 9, в якому jзбільшуємо на одиницю: j = 2.
У блоці 10 умова не виконується, тому переходимо до блоку 9, в якому jзбільшуємо на одиницю: j= 3. За аналогією переходимо до блоку 11.
Блок 11: s= 4 - (-2) × 0 = 4, після чого закінчуємо цикл III і переходимо до блоку 12.
Блок 12: s = s/ a 22 = 4 / 5 = 0,8.
Блок 13: w = 1; s = s + 0 = 0,8.
Блок 14: d = | 1 – 0,8 | = 0,2.
Блок 15: x i = 0,8 (i = 2).
Блок 16. Перевіряємо умову d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «А» до наступного кроку циклу II – до блоку7.
Цикл II: i = 3: s = b 3 = 6 (блок 8).
Переходимо у вкладений цикл III, блок9: j = 1.
Блок 11: s= 6 - 1 × 0 = 6, переходимо до блоку 9: j = 2.
За допомогою блоку 10 виконуємо перехід до блоку 11.
Блок 11: s= 6 - 1 × 0 = 6. Закінчуємо цикл III і переходимо до блоку 12.
Блок 12: s = s/ a 33 = 6 / 4 = 1,5.
Блок 13: s = 1,5.
Блок 14: d = | 1 – 1,5 | = 0,5.
Блок 15: x i = 1,5 (i = 3).
Згідно з блоком 16 (з урахуванням посилань « А» та « З») Виходимо з циклу II і переходимо до блоку18.
Блок 18. Збільшуємо кількість ітерацій it = it + 1 = 0 + 1 = 1.
У блоках 19 та 20 циклу IV замінюємо початкові значення х 0iотриманими значеннями х i (i = 1, 2, 3).
Блок 21. Виконуємо друк проміжних значеньпоточної ітерації, у разі: = (0,5; 0,8; 1,5) T, it = 1; de = 0,5.
Переходимо до циклу II блок 7 і виконуємо розглянуті обчислення з новими початковими значеннями х 0i (i = 1, 2, 3).
Після чого отримаємо х 1 = 1,075; х 2 = 1,3; х 3 = 1,175.
Тут, отже, метод Зейделя сходиться.
За формулами (2.33)
| k | х 1 | х 2 | х 3 |
| 0,19 | 0,97 | –0,14 | |
| 0,2207 | 1,0703 | –0,1915 | |
| 0,2354 | 1,0988 | –0,2118 | |
| 0,2424 | 1,1088 | –0,2196 | |
| 0,2454 | 1,1124 | –0,2226 | |
| 0,2467 | 1,1135 | –0,2237 | |
| 0,2472 | 1,1143 | –0,2241 | |
| 0,2474 | 1,1145 | –0,2243 | |
| 0,2475 | 1,1145 | –0,2243 |
Відповідь: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.
Зауваження. Якщо однієї і тієї ж системи методи простої ітерації і Зейделя сходяться, то метод Зейделя краще. Однак на практиці області збіжності цих методів можуть бути різними, тобто метод простої ітерації сходиться, а метод Зейделя розходиться і навпаки. Для обох методів, якщо || G|| близька до одиниці, Швидкість збіжності дуже мала.
Для прискорення збіжності використовується штучний прийом – так званий метод релаксації . Суть його полягає в тому, що отримане методом ітерації чергове значення x i (k) перераховується за формулою
де w прийнято змінювати в межах від 0 до 2 (0< w £ 2) с каким-либо шагом (h= 0,1 чи 0,2). Параметр w підбирають те щоб збіжність методу досягалася за мінімальне число ітерацій.
Релаксація- Поступове ослаблення будь-якого стану тіла після припинення дії факторів, що викликали цей стан (фіз. техн.).
Приклад 2.4. Розглянемо результат п'ятої ітерації із застосуванням формули релаксації. Візьмемо w = 1,5:
Очевидно, отримано результат майже сьомої ітерації.
Тема 3 Рішення систем лінійних алгебраїчних рівняньітераційними методами
Описані вище прямі методи рішення СЛАУ не дуже ефективні при вирішенні систем великої розмірності (тобто коли значення n досить велике). Для вирішення СЛАУ у таких випадках більше підходять ітераційні методи
Ітераційні методи вирішення СЛАУ(їх друга назва - методи послідовного наближення до рішення) не дають точного рішення СЛАУ, а дають лише наближення до рішення, причому кожне наступне наближення виходить із попереднього і є більш точним, ніж попереднє (за умови, що забезпечене збіжністьітерацій). Початкове (або, так зване, нульове) наближення вибирається поблизу передбачуваного рішення або довільно (як його можна взяти вектор правої частини системи). Точне рішення знаходиться як межа таких наближень при прагненні їх кількості до нескінченності. Як правило, за кінцеве число кроків (тобто ітерацій) ця межа не досягається. Тому на практиці вводиться поняття точності рішення, А саме задається деяке позитивне і досить мале число eта процес обчислень (ітерацій) проводять доти, доки не буде виконано співвідношення .
Тут наближення до рішення, отримане після ітерації номер n , а - точне рішення СЛАУ (яке невідомо). Число ітерацій n = n (e ) , необхідне досягнення заданої точності для конкретних методів можна з теоретичних розглядів (т. е. при цьому є розрахункові формулы). Якість різних ітераційних методів можна порівняти за необхідною кількістю ітерацій задля досягнення однієї й тієї ж точності.
Для дослідження ітераційних методів на збіжністьнеобхідно вміти обчислювати норми матриць. Норма матриці- це якась числова величина, Що характеризує величину елементів матриці по абсолютній величині У вищій математиці є кілька різних видівнорм матриць, які зазвичай є еквівалентними. У нашому курсі ми користуватимемося лише однією з них. А саме, під нормою матриціми розумітимемо максимальну величину серед сум абсолютних величин елементів окремих рядків матриці. Для позначення норми матриці - її назва полягає у дві пари вертикальних рис. Так, для матриці A під її нормою розумітимемо величину
. (3.1)
Приміром, норма матриці А з прикладу 1 перебуває так:
Найбільш широке застосування для вирішення СЛАУ отримали три ітераційні методи
Метод простої ітерації
Метод Якобі
Метод Гуас-Зейделя.
Метод простої ітерації передбачає перехід від запису СЛАУ у вихідному вигляді (2.1) до запису її як
(3.2)
або, що теж, у матричному вигляді,
x = З × x + D , (3.3)
C - матриця коефіцієнтів перетвореної системи розмірності n ´ n
x - вектор невідомих, що складається з n компонент
D - вектор правих частин перетвореної системи, що складається з n компонент.
Система у вигляді (3.2) може бути представлена у скороченому вигляді
Виходячи з цього уявлення формула простої ітераціїматиме вигляд
де m - Номер ітерації, а - значення x j на m ом етапі ітерації. Тоді, якщо процес ітерацій сходиться,зі збільшенням кількості ітерацій спостерігатиметься
Доведено, що процес ітерацій сходиться,якщо нормаматриці D буде менше одиницьы.
Якщо початкове (нульове) наближення взяти вектор вільних членів, тобто. x (0) = D , то величина похибкимає вигляд
(3.5)
тут під x * розуміється точне рішення системи. Отже,
якщо 
, то по заданої точностіe
можна заздалегідь розрахувати необхідна кількість ітерацій. А саме, із співвідношення
після невеликих перетворень отримаємо
. (3.6)
За виконання такої кількості ітерацій гарантовано буде забезпечена задана точність знаходження рішення системи. Ця теоретична оцінка необхідної кількостікроків ітерації дещо завищено. На практиці необхідну точність можна досягти за меншу кількість ітерацій.
Пошук рішень заданої СЛАУ методом простої ітерації зручно проводити із занесенням отриманих результатів до таблиці наступного виду:
| x 1 | x 2 | x n |
||
Слід особливо наголосити, що у рішенні СЛАУ цим методом найбільш складним та трудомісткимє виконання перетворення системи із виду (2.1) до виду (3.2). Ці перетворення мають бути еквівалентними, тобто. не змінюють рішення вихідної системи, і забезпечують величину норми матриці C (Після виконання їх) меншої одиниці. Єдиного рецепта виконання таких перетворень немає. Тут у кожному конкретному випадку необхідно виявляти творчість. Розглянемо приклади, В яких будуть наведені деякі способи перетворення системи до необхідного виду.
приклад 1.Знайдемо рішення системи лінійних рівнянь алгебри методом простої ітерації (з точністю e= 0.001)
Ця система наводиться до необхідного вигляду найпростішим способом. Перенесемо всі складові з лівої частини в праву, а потім до обох частин кожного рівняння додамо по x i (i = 1, 2, 3, 4). Отримаємо перетворену систему такого виду
.
Матриця C та вектор D у цьому випадку будуть наступними
C
=
,
D
=
.
Обчислимо норму матриці C . Отримаємо
Оскільки норма виявилася меншою одиниці - збіжність методу простий ітерації забезпечена. Як початкове (нульове) наближення приймемо компоненти вектора D . Отримаємо
, 
, 
, 
.
За формулою (3.6) обчислимо необхідну кількість кроків ітерації. Визначимо спочатку норму вектора D . Отримаємо
.
Отже, для досягнення заданої точності необхідно виконати щонайменше 17 ітерацій. Виконаємо першу ітерацію. Отримаємо
Виконавши всі арифметичні операції, отримаємо
.
Продовжуючи аналогічно, здійснимо подальші кроки ітерацій. Результати їх зведемо до наступної таблиці ( D- найбільша величина зміни компонентів рішення між поточним і попереднім кроками)
| M | |||||
Тому що вже після десятого кроку різниця між значеннями на двох останніх ітераціях стала меншою за задану точність - процес ітерацій припинимо. Як знайдене рішення приймемо значення, отримані на останньому кроці.
приклад 2.
Надійдемо спочатку аналогічно попередньому прикладу. Отримаємо
Матриця C такої системи буде
C
=
.
Обчислимо її норму. Отримаємо
Очевидно, що ітераційний процес для такої матриці схожим не буде. Необхідно знайти інший спосіб перетворення заданої системи рівнянь.
Переставимо у вихідній системі рівнянь окремі її рівняння так, щоб третій рядок став першим, перший - другий, другий - третім. Тоді, перетворюючи її тим самим способом, отримаємо
Матриця C такої системи буде
C
=
.
Обчислимо її норму. Отримаємо
Оскільки норма матриці C виявилася меншою одиниці, перетворена таким чином система придатна для вирішення методом простої ітерації.
приклад 3.Перетворимо систему рівнянь
на вигляд, який дозволив би використовувати при її вирішенні метод простої ітерації.
Надійдемо спочатку аналогічно прикладу 1. Отримаємо
Матриця C такої системи буде
C
=
.
Обчислимо її норму. Отримаємо
Очевидно, що ітераційний процес для такої матриці схожим не буде.
Для перетворення вихідної матриці до виду, зручному для застосування методу простої ітерації, надійде наступним чином. Спочатку утворимо “проміжну” систему рівнянь, у якій
- перше рівнянняє сумою першого та другого рівнянь вихідної системи
- друге рівняння- сумою подвоєного третього рівняння з другим за вирахуванням першого
- третє рівняння- Різниця третього та другого рівнянь вихідної системи.
В результаті отримаємо еквівалентну вихідну “проміжну” систему рівнянь
З неї нескладно отримати ще одну систему "проміжну" систему
,
а з неї перетворену
.
Матриця C такої системи буде
C
=
.
Обчислимо її норму. Отримаємо
Ітераційний процес для такої матриці буде схожим.
Метод Якобі передбачає, що це діагональні елементи матриці A вихідної системи (2.2) не дорівнюють нулю. Тоді вихідну систему можна переписати як
(3.7)
З такого запису системи утворено ітераційна формула методу Якобі
Умовою збіжності ітераційного процесу методу Якобі є так звана умова домінування діагоналіу вихідній системі (виду (2,1)). Аналітично ця умова записується у вигляді
. (3.9)
Слід зазначити, що якщо в заданій системірівнянь умова збіжності методу Якобі (тобто. умова домінування діагоналі) не виконується, у багатьох випадках можна шляхом еквівалентних перетворень вихідної СЛАУ привести її рішення до вирішення еквівалентної СЛАУ, в якій ця умова виконується.
приклад 4.Перетворимо систему рівнянь
до виду, який дозволив би використовувати за її вирішенні метод Якобі.
Цю систему ми вже розглядали у прикладі 3, тому перейдемо від неї до одержаної там “проміжної” системи рівнянь. Легко встановити, що в неї умова домінування діагоналі виконується, тому перетворимо її на вид, необхідний застосування методу Якобі. Отримаємо
З неї отримуємо формулу для виконання обчислень за методом Якобі для заданої СЛАУ
Взявши за початкове, тобто. нульове, наближення вектора вільних членів виконаємо всі необхідні обчислення. Результати зведемо до таблиці
| m | D |
||||
Досить високу точність отриманого рішення досягнуто за шість ітерацій.
Метод Гауса-Зейделя є удосконаленням методу Якобі і також передбачає, що всі діагональні елементи матриці A вихідної системи (2.2) не дорівнюють нулю. Тоді вихідну систему можна переписати у вигляді аналогічному методу Якобі, але дещо відмінному від нього
Тут важливо пам'ятати, що якщо у знаку підсумовування верхній індекс менший за нижній, то ніякого підсумовування не проводиться.
Ідея методу Гауса-Зейделя полягає в тому, що автори методу вбачали можливість прискорити процес обчислень щодо методу Якобі за рахунок того, що в процесі чергової ітерації знайшовши нове значення x 1 можна, можливо одразу жвикористовувати це нове значення у цій же ітераціїдля обчислення інших змінних. Аналогічно цьому далі знайшовши нове значення x 2 можна його також одразу використовувати у цій самій ітерації тощо.
Виходячи з цього, формула ітерацій для методу Гауса-Зейделямає такий вигляд
Достатнім условом збіжностіітераційного процесу методу Гауса-Зейделя є все та ж умова домінування діагоналі (3.9). Швидкість збіжностіцього методу дещо вище, ніж у методу Якобі.
Приклад 5.Вирішимо методом Гаусса-Зейделя систему рівнянь
Цю систему ми вже розглядали в прикладах 3 і 4, тому відразу перейдемо від неї до перетвореної системи рівнянь (див. Приклад 4), в якій умова домінування діагоналі виконується. З неї отримуємо формулу для виконання обчислень за методом Гауса-Зейделя
Взявши за початкове (тобто нульове) наближення вектор вільних членів, виконаємо всі необхідні обчислення. Результати зведемо до таблиці
| m | ||||
Досить високу точність отриманого рішення досягнуто за п'ять ітерацій.
p align="justify"> Метод простої ітерації, званий також методом послідовного наближення, - це математичний алгоритм знаходження значення невідомої величини шляхом поступового її уточнення. Суть цього у тому, що, як очевидно з назви, поступово висловлюючи з початкового наближення наступні, отримують дедалі більше уточнені результати. Цей метод використовується для пошуку значення змінної в заданої функції, і навіть під час вирішення систем рівнянь, як лінійних, і нелінійних.
Розглянемо, як даний методреалізується під час вирішення СЛАУ. Метод простої ітерації має такий алгоритм:
1. Перевірка виконання умови збіжності у вихідній матриці. Теорема про збіжність: якщо вихідна матриця системи має діагональне переважання (тобто, у кожному рядку елементи головної діагоналі повинні бути більшими за модулем, ніж сума елементів побічних діагоналей за модулем), то метод простих ітерацій - схожий.
2. Матриця вихідної системи який завжди має діагональне переважання. У разі систему можна перетворити. Рівняння, задовольняють умові збіжності, залишають недоторканими, і з незадовольняючими становлять лінійні комбінації, тобто. множать, віднімають, складають рівняння між собою до отримання потрібного результату.
Якщо в отриманій системі на головній діагоналі знаходяться незручні коефіцієнти, то до обох частин такого рівняння додають доданки з i * x i, знаки яких повинні збігатися зі знаками діагональних елементів.
3. Перетворення отриманої системи до нормального вигляду:
x - =β - +α*x -
Це можна зробити безліччю способів, наприклад, так: з першого рівняння виразити х 1 через інші невідомі, з другого-х 2, з третього-х 3 і т.д. При цьому використовуємо формули:
α ij = -(a ij / a ii)
i = b i /a ii
Слід знову переконатися, що одержана система нормального вигляду відповідає умові збіжності:
∑ (j=1) |α ij |≤ 1, причому i= 1,2,...n
4. Починаємо застосовувати, власне, сам спосіб послідовних наближень.
x (0) - початкове наближення, виразимо через нього х (1), далі через х (1) виразимо х (2). Загальна формула в матричному вигляді виглядає так:
x(n) = β - +α*x (n-1)
Обчислюємо, доки не досягнемо необхідної точності:
max |x i (k)-x i (k+1) ≤ ε
Отже, давайте розберемо практично метод простої ітерації. Приклад:
Вирішити СЛАУ:
4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 з точністю ε=10 -3
Подивимося, чи переважають по модулю діагональні елементи.
Ми бачимо, що умовою збіжності задовольняє лише третє рівняння. Перше і друге перетворимо, до першого рівняння додамо друге:
7,6x1+0.6x2+2.4x3=3
З третього віднімемо перше:
2,7x1+4.2x2+1.2x3=2
Ми перетворили вихідну систему на рівноцінну:
7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4
Тепер наведемо систему до нормального вигляду:
x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3 = 0.8511-0.383x1-0.5319x2
Перевіряємо збіжність ітераційного процесу:
0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383 + 0.5319 = 0.9149 ≤ 1, тобто. умова виконується.
0,3947
Початкове наближення х(0) = 0,4762
0,8511
Підставляємо дані значення рівняння нормального вигляду, отримуємо наступні значення:
0,08835
x(1) = 0,486793
0,446639
Підставляємо нові значення, отримуємо:
0,215243
x(2) = 0,405396
0,558336
Продовжуємо обчислення до того моменту, поки не наблизимося до значень, що задовольняють задану умову.
x(7) = 0,441091
Перевіримо правильність отриманих результатів:
4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977
Результати, отримані при підстановці знайдених значень вихідні рівняння, повністю задовольняють умов рівняння.
Як бачимо, метод простої ітерації дає досить точні результати, проте на вирішення цього рівняння нам довелося витратити багато часу й зробити громіздкі обчислення.
ВСТУП
1. РІШЕННЯ СЛАУ МЕТОДОМ ПРОСТОЙ ІТЕРАЦІЇ
1.1 Опис методу розв'язання
1.2 Вихідні дані
1.3 Алгоритм
1.4 Програма мовою QBasic
1.5 Результат роботи програми
1.6 Перевірка результату роботи програми
2. УТОЧНЕННЯ КОРИНЯ МЕТОДОМ ЩОДО
2.1 Опис методу розв'язання
2.2 Вихідні дані
2.3 Алгоритм
2.4 Програма мовою QBasic
2.5 Результат роботи програми
2.6 Перевірка результату роботи програми
3.ЧИСЛОВЕ ІНТЕГРУВАННЯ ЗА ПРАВИЛОМ ПРЯМОКУТНИКА
3.1 Опис методу розв'язання
3.2 Вихідні дані
3.3 Алгоритм
3.4 Програма мовою QBasic
3.5 Перевірка результату роботи програми
4.1 Загальні відомостіПро програму
4.1.1 Призначення та відмітні особливості
4.1.2 Обмеження WinRAR
4.1.3 Системні вимоги WinRAR
4.2 Інтерфейс WinRAR
4.3 Режими керування файлами та архівами
4.4 Використання контекстних меню
ВИСНОВОК
СПИСОК ЛІТЕРАТУРИ
ВСТУП
Метою даної курсової роботиє розробка алгоритмів та програм для вирішення системи лінійних рівнянь алгебри за допомогою методу Гаусса; нелінійного рівняння з допомогою методу хорд; для чисельного інтегрування за правилом трапецій
Алгебраїчними рівняннями називають рівняння, що містять лише функції алгебри (цілі, раціональні, ірраціональні). Зокрема, багаточлен є цілою функцією алгебри. Рівняння, що містять інші функції (тригонометричні, показові, логарифмічні та інші), називаються трансцендентними.
Способи розв'язання систем лінійних рівнянь алгебри діляться на дві групи:
· Точні методи, що являють собою кінцеві алгоритми для обчислення коренів системи (рішення систем за допомогою зворотної матриці, правило Крамера, метод Гауса та ін.),
· Ітераційні методи, що дозволяють отримати рішення системи із заданою точністю шляхом схожих ітераційних процесів (метод ітерації, метод Зейделя та ін).
Внаслідок неминучих округлень результати навіть точних методів є наближеними. При використанні ітераційних методів, до того ж, додається похибка методу.
Рішення систем лінійних рівнянь алгебри – одне з основних завдань обчислювальної лінійної алгебри. Хоча завдання розв'язання системи лінійних рівнянь порівняно рідко представляє самостійний інтерес для додатків, від уміння ефективно вирішувати такі системи часто залежить можливість математичного моделювання найрізноманітніших процесів із застосуванням ЕОМ. Значна частина чисельних методів розв'язання різних (особливо – нелінійних) завдань включає рішення систем лінійних рівнянь як елементарний крок відповідного алгоритму.
Для того щоб система лінійних рівнянь алгебри мала рішення, необхідно і достатньо, щоб ранг основної матриці був дорівнює рангурозширеної матриці. Якщо ранг основної матриці дорівнює рангу розширеної матриці і дорівнює числу невідомих, то система має єдине рішення. Якщо ранг основної матриці дорівнює рангу розширеної матриці, але менший від числа невідомих, то система має нескінченну кількість рішень.
Одним із найпоширеніших методів розв'язання систем лінійних рівнянь є метод Гауса. Цей метод відомий у різних варіантахвже понад 2000 років. Метод Гаусса - класичний метод розв'язання системи лінійних рівнянь алгебри (СЛАУ). Це метод послідовного виключеннязмінних, коли за допомогою елементарних перетвореньсистема рівнянь наводиться до рівносильної системі ступінчастого (або трикутного) виду, з якої послідовно, починаючи з останніх (за номером) змінних, знаходяться решта змінних.
Строго кажучи, описаний вище метод правильно називати методом Гаусса-Жордана (Gauss-Jordan elimination), оскільки він є варіацією методу Гаусса, описаної геодезистом Вільгельмом Жорданом в 1887 р.). Також цікаво помітити, що одночасно з Жорданом (а за деякими даними навіть раніше за нього) цей алгоритм придумав Класен (B.-I. Clasen).
Під нелінійними рівняннямирозуміються алгебраїчні та трансцендентні рівняння виду , де х – дійсне число, а – нелінійна функція. Для вирішення цих рівнянь застосовується метод хорд – ітераційний чисельний методнаближеного знаходження коріння. Як відомо, багато рівнянь та системи рівнянь не мають аналітичних рішень. Насамперед це стосується більшості трансцендентних рівнянь. Доведено також, що не можна побудувати формулу, за якою можна було б вирішити довільне рівняння алгебри ступеня вище четвертого. Крім того, в деяких випадках рівняння містить коефіцієнти, відомі лише приблизно, і, отже, саме завдання про точне визначення коренів рівняння втрачає сенс. Для їх вирішення використовуються ітераційні методи із заданим ступенем точності. Вирішити рівняння ітераційним способом означає встановити, чи має воно коріння, скільки коренів і знайти значення коренів з необхідною точністю.
Завдання знаходження кореня рівняння f(x) = 0 ітераційним методом складається з двох етапів:
· Відділення коренів - відшукання наближеного значення кореня або містить його відрізка;
· Уточнення наближених коренів - доведення їх до заданого ступеня точності.
Певним інтеграломфункції f(x), взятому в інтервалі від aдо b, називається межа, якого прагне інтегральна сума при прагненні всіх проміжків ∆x i до нуля. Згідно з правилом трапецій, необхідно замінити графік функції F(x) прямої, що проходить через дві точки (х 0, у 0) і (х 0 + h, у 1), і обчислити значення елемента інтегральної суми як площу трапеції: 
.
РІШЕННЯ СЛАУ МЕТОДОМ ПРОСТОЙ ІТЕРАЦІЇ
1.1 Опис методу постій ітерації
Системи рівнянь алгебри (СЛАУ) мають вигляд:
або, при записі у матричній формі:
У практиці використовують два типи методів чисельного рішення СЛАУ – прямі та опосередковані. При використанні прямих методів СЛАУ наводиться до однієї зі спеціальних форм (діагональної, трикутної), що дозволяють точно отримати потрібне рішення (якщо таке існує). Найбільш поширеним прямим методом розв'язання СЛАУ є метод Гаусса. Ітераційні методи служать для пошуку наближеного рішення СЛАУ із заданою точністю. Слід зазначити, що ітераційний процес який завжди сходиться до рішення системи, лише тоді, коли послідовність одержуваних при розрахунках наближень прагнути точному решению. При вирішенні СЛАУ методом простої ітерації її перетворюють на вигляд, коли в лівій частині знаходиться лише одна з змінних, що шукаються:
Задавши деякі вихідні наближення xi, i=1,2,…,n, підставляють їх у праву частинувиразів та обчислюють нові значення x. Процес повторюють до тих пір, поки максимальна з нев'язок, що визначаються за виразом:
не стане менше заданої точності? Якщо максимальна нев'язка при k-ой ітерації виявиться більше максимальної нев'язки при k-1-ой ітерації, процес аварійно завершують, т.к. ітераційний процес розходиться. Для мінімізації кількості ітерацій нові значення x можна обчислювати з використанням значення нев'язок на попередній ітерації.
Завантаження...