69320

Ітераційні методи розв’язування СЛАР

Лекция

Математика и математический анализ

Метод простої ітерації умови збіжності Для розріджених великих систем рівнянь досить добрі результати можна отримати як це було показано в попередньому параграфі застосуванням методу визначальних величин.

Украинкский

2014-10-03

307.5 KB

20 чел.

Лекція 4. Ітераційні методи розв’язування СЛАР

3.4. Метод простої ітерації, умови збіжності

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

Оскільки ітерації при рішенні є однією з головних особливостей чисельних методів (глава 1), то розглянемо більш детальніше ітераційний метод рішення системи лінійних рівнянь типу Ах = b.

Для її рішення обирається деяке початкове наближення х(0) , яке використовується для обчислення наступних наближень х(k)за деякою рекурентною формулою обчислень:

х (к + 1) = М х (к) + С(k), (3.19)

де k номер ітерації, М,С(k)ітераційні оператори.

У формулі (3.19) передбачається при обчисленні х(k + 1)використання тільки попередньої ітерації х(k) , тому її називають однокроковою, чи двошаровою. Але існують і більш складні рекурентні формули наближень, в яких, наприклад, при обчисленні х(k + 1)використовуються дві попередні ітерації х(k) і х(k - 1) , тоді їх називають двокроковими, або двошаровими.

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

, (3.20)

де ξ — точне рішення системи лінійних рівнянь.

Найпростіша рекурентна формула наближень типу (3.19) відповідає методу простої ітерації , яка будується на основі використання нев’язку системи лінійних рівнянь, які вирішуються:

r(к) = Ах(к)b (3.21)

Для цього метода формула наближень приймає вигляд:

х(к + 1) = х(к) - r(к) = х(к) - Ах(к) + b = (E - A)х(к) + b (3.22)

Порівнюючи (3.19) і (3. 22), знаходимо, що для методу простої ітерації

М = E - А и С(k) = b

Тобто в якості початкового наближення х(0) для цього методу можливий вибір вектора правої частини системи рівнянь b.

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

,

де, як і раніше, ξ — точне рішення системи лінійних рівнянь

Оскільки = М + С(k)іх(k + 1) = Мх(k) + С(k), то глобальні похибки на сусідніх ітераціях пов’язані лінійною залежностю:

х(k + 1) - = М(х(k) - )

або ||х(k + 1) - )||≤||М||||х(k) - || (3.23)

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

(3.24)

Зручно при обчисленнях оценку глобальної похибки ||x(k + 1) - ξ|| вести за значеннями локальної похибки, тобто за значеннями, отриманими на сусідніх ітераціях. Для цього перепишемо (3. 23), додавши і віднявши справа значення х(k + 1):

||х(k + 1) - )|| ≤ ||М||||х(k) - + х(k + 1) - х(k + 1) || = ||М|||| х(k + 1) - || +

||М|||| х(k + 1) - х(k)||, (3.25)

звідки отримуємо:

(3.26)

або . (3.27)

Нагадаємо, що для метода простої ітерації відповідно формулі (3. 22) М = E - А, тому накладання умови збіжності обчислень ||M|| < 1 обмежує використання цього методу для рішення більшості практичних математичних задач.Але умови його збіжності можна поліпшати, якщо в формулі (3.21) ввести демпфіруючий коефіцієнт ώ≤1 для врахування нев’язку:

х(к + 1) = х(к) - ώr(к) (3.28)

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

Існує ще один різновид умови збіжності обчислень ітераційними методами, який базується на використанні оцінки власних значень матриці перетворення М, про які вже йшлося у параграфі 1.4 і визначенню яких присвячена наступна глава 4. Згідно з цією умовою збіжності необхідно і достатньо, щоб

, (3.29)

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

Доказ умови (3.29) базується на використанні ортогонального координатного базису, який утворюють власні вектори матриці М, і розкладі вектора початкової глобальної похибки у цьому базисі:

.

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

,
.

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

Формула (3.10) має лише теоретичну цінність, тому що задача пошуку власних значень матриці більш складна задача, ніж розв’язування систем рівнянь.

3.5. Метод Якобі

Ітераційний метод Якобі рішення лінійної системи рівнянь Ах = b при умові aii ≠ 0 передбачає рішення кожного рівняння системи окремо відносно тільки однієї змінної при припущенні , що всі інші змінні задані або початковим вибором, або даними попередньої ітерації:

 (3.30).

Для цього розділимо матрицю А на діагональну D , нижню L і верхню U трикутні матриці :

A = D(L + I + U), (3.31)

де 

Тоді рівняння (3.19) для методу Якобі можна записати у вигляді:

х(к + 1) = - (L + U)х(к) + b,

з якого легко доводиться, що матриця перетворення

М = - (L + U), (3.32)

при цьому

Визначення. Матриця A розмірності n має домінуючу головну діагональ, якщо кожний її діагональний елемент за модулем більший за суму модулів інших елементів цього ж рядка:

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

(3.33)

Приклад 3.7.

Вирішити лінійну систему рівнянь з прикладу 3.4 ітераційним методом Якобі:

Перш за все, оцінимо максимальну норму матриці перетворення М, використавши формулу (3.33) для ||M|| для рядків: ||M|| = max(1/2,2/3,2/4,2/5,1/3) = 2/3 = 0,666667 < 1 тобто метод Якобі стійкий для даного прикладу. Ітерації за формулою (3. 30) метода Якобі дають значення, зведені у табл. 3.1.

Таблиця 3.1. Результати рішення методом Якобі

k

1

0,5

- 0,333333

0,5

- 0,6

0,666667

2

0,666667

- 0,666667

0,733333

- 0,833333

0,866667

3

0,833333

- 0,8

0,875

- 0,92

0,944444

4

0,9

- 0,902778

0,93

- 0,963889

0,973333

5

0,951389

- 0,943333

0,966667

- 0,980667

0,987963

6

0,971667

0,972685

0,981

- 0,990926

0,993556

7

0,986343

- 0,984222

0,990903

- 0,994911

0,996975

8

0,992111

- 0,992415

0,994783

- 0,997576

0,998304

1

- 1

1

- 1

1

Оцінимо похибку метода Якобі після п’ятої ітерації, скориставшись формулою (3.26):

3.6. Метод Гаусса–Зейделя

Ітераційний метод Гаусса–Зейделя рішення лінійної системи рівнянь Ах = b при умові
aii ≠ 0 Також передбачає рішення кожного рівняння системи окремо відносно тільки однієї змінної, але при пошуку i–ї компоненти вектора рішень (k + 1)го наближення відразу на поточній (k + 1)ій ітерації використовуються вже знайдені компоненти (k + 1)го наближення з меншими номерами:

(3.34)

Метод Гаусса–Зейделя потребує менше пам’яті ЕОМ, ніж метод Якобі, тому що після обчислення i–ї компоненти вектора x(k + 1) відповідна компонента вектора x(k) стає непотрібною. Оскільки дані (k + 1)го наближення використовуються для знаходження самого (k + 1)го наближення, то метод Гаусса–Зейделя іноді називають неявним ітераційним методом в протилежність методу Якобі, який вважається явним ітераційним методом.

Тоді рівняння (3.19) для методу Гаусса–Зейделя можна записати у вигляді:

х(к + 1) = - Lх(к + 1) - Uх(к) + b,

звідки матриця перетворення

М = - (І + L)1U (3.35)

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

Щоб запобігти обернення матриці у виразі (3.35), ще раз перепишемо рекурентну формулу методу через нормовані значення коефіцієнтів (3.31):

 (3.36)

Переходячи у матрично–векторному виразі (3.36) до норм, можна отримати:

,

де  (3.37)

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

(3.38)

Можна визначити необхідну кількість ітерацій при виборі за початкове наближення нормованої правої частини Ci = bi/aii з метою одержання наближеного розв’язку лінійної системи із заданою точністю , скористувавшись формулою (3.27):

(3.39)

звідки

(k + 1)lg≤ lg - lg  + lg(1 - )

або

k≥ (3.40)

Приклад 3.8.

Проведемо методом Гаусса–Зейделя рішення лінійної системи, яка розглядалася в прикладах 3.4 і 3.7 і для якої:

Оцінимо максимальну норму матриці перетворення ||M||,використавши формули (3.37) та (3.38) для рядків матриці:

1й s1 = 0, r1 = 1/2, М1 = 1/2;

2й s2 = 1/3 r2 = 1/3 М2 = (1/3/(1 - 1/3 = 1/2

3й s3 = 1/4, r3 = 1/4, М3 = 1/3;

4–й s4 = 1/5, r4 = 1/5, M4 = 1/4;

5–й s5 = 1/3, r5 = 0, M5 = 0;

||M|| = max(1/2,1/2,1/3,1/4,0) = 1/2 = 0,5 < 1 тобто метод Гаусса–Зейделя теж стійкий для даного прикладу.

Ітерації за формулою (3.34) метода Гаусса–Зейделя дають значення, зведені у табл. 3.2.

Таблиця 3.2. Результати рішення методом ГауссаЗейделя

k

1

0,5

- 0,5

0,625

- 0,725

0,908333

2

0,75

- 0,791667

0,879167

- 0,9575

0,985833

3

0,895834

- 0,925

0,970625

- 0,991292

0,997097

4

0,9625

- 0,977708

0,99225

- 0,997869

0,99929

5

0,988854

- 0,993701

0,997893

- 0,999437

0,999812

1

- 1

1

- 1

1

Для оцінки похибки у методі ГауссаЗейделя після п’ятої ітерації скористаємося формулою (3.26):

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

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

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

Таблиця 3.3. Результати рішення симетричним методом ГауссаЗейделя

k

1

0,5

- 0,5

0,625

- 0,725

0,908333

2

0,780555

- 0,56111

0,683333

- 0,733333

0,666667

c.з.

0,640277

- 0,530555

0,654166

- 0,729166

0,784998

3

0,765278

- 0,806481

0,883912

- 0,933782

0,977927

4

0,916852

- 0,833703

0,860833

- 0,912777

0,909722

c.з.

0,8410648

- 0,820092

0,872373

- 0,923280

0,943824

1

- 1

1

- 1

1

Розглянемо корисну геометричну інтерпретацію метода Гаусса–Зейделя на прикладі рішення систему рівнянь:

для якої згідно виразу (3.38) необхідні і достатні умови збіжності виконуються:

||M|| = max(1/2,0) = 1/2 = 0,5 < 1

Так як при обчисленні змінної x зберігається незмінним значення y, то геометричний еквівалент методу — рух по горизонталі до перетину з прямою, що відображає перше рівняння (рис. 3.3.).

Рис. 3.3. Геометрична інтерпретація метода ГауссаЗейделя

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

Значення координат виділених точок xi, i = 0,1,…,3 зведені у табл. 3.4.

Таблиця 3.4. Координати точок перетину

k

x

y

0

0

0

1

1

3/2

2

1/4

9/8

3

7/16

39/32

Висновки:

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

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

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

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

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

6. Значне поширення в інженерній практиці мають випадки рішення рівнянь з стрічковими матрицями коефіцієнтів, для яких ефективно застосовуються метод спрощеного LU–розкдаду , метод прогонки і метод верхньої релаксації.

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

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

Вправи

1. Побудувати ненульову структуру матриці за її кодуючими списками
LJ = [ 1,3,2,4,1,3,5,2,4,1,4,5], LI = [1,3,5,8,10,13] і визначити, скільки нових ненульових елементів (ННЕ) з’являються при її LUрозкладу.

2. Побудувати ненульову структуру матриці по її кодуючими списками
LJ = [ 1,3,2,4,1,2,3,5,1,2,4,1,4,5], LI = [1,3,5,9,12,15 ] і привести її до блочно–діагонального виду з обрамленням. До якого порядку може бути скорочений розмір системи рівнянь змінних зв’язку?

3. Побудувати ненульову структуру матриці по її кодуючими списками
LJ = [1,2,3,2,4,1,2,3,5,1,2,4,1,4,5], LI = [1,4,6,10,13,16 ] і провести упорядкування її діагональних елементів згідно критерію Марковиця . Як зміниться кількість нових ненульових елементів (ННЕ) при LUрозкладу?

4. Вирішити ітераційним методом Гаусса–Зейделя систему лінійних алгебраїчних рівнянь:

Знайти вектори рішення після першої і другої ітерацій і похибку рішення після другої ітерації, якщо вектор точного рішення дорівнює [
x]t = [3 - 25 7].

5. Вирішити з похибкою = 0,05 ітераційним методом Якобі систему лінійних рівнянь
.

6. Вирішити ітераційним методом Гаусса–Зейделя систему лінійних рівнянь:

Відповіді:

1. Не з’являються.

2. Зменшується п’ятого поряку до другого відносно змінних зв’язку x3 і x4.

3. Зменшиться з початкових п’яти до одного.

4. [x1]t = [2,6166666 - 2,7945238 7,0056095],
[x1]t = [2,9905565 - 2,4996246 7,0002908]
[E]t = [12,5% 11,8 % 0,0076 %]

5. [x1]t = [1,28515 1,91777 - 0,181698]

6. [x]t = [2,60079 - 6,53755 3,30435]

PAGE  64


 

А также другие работы, которые могут Вас заинтересовать

47533. Методические указания. Экономика и бухгалтерский учет 171.5 KB
  Наумова СОДЕРЖАНИЕ 1 Общие вопросы организации дипломного проектирования.4 2 Содержание дипломного проекта .1 Требования к структуре дипломного проекта .4 Требования к содержанию пояснительной записки дипломного проекта.
47534. Осложнения послеоперационного периода – роль сестринского процесса и их профилактика 2.06 MB
  Послеоперационный период - это время от момента операции до выздоровления или перевода пациента на инвалидность. В этот период пациент находится в определенном состоянии, которое обусловлено предшествующей болезнью, оперативным вмешательством по ее устранению и наркотическими средствами, применяемыми во время операции.
47536. Методические указания. Безопасность технологических процессов и производств 305 KB
  Карауш Томск 2005 Дипломное проектирование: методические указания по выполнению выпускной квалификационной работы для студентов специальности 280102 Безопасность технологических процессов и производств Сост. Володина Методические указания предназначены для студентов специальности 280102 Безопасность технологических процессов и производств всех форм обучения и слушателей Института ПК ТГАСУ при написании ими выпускной квалификационной работы. ЦЕЛИ И ЗАДАЧИ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ .
47539. Компютерне запезчення телекомунікацій. Методичні вказівки 1.1 MB
  Сортировку оборудования содержащегося в БД NetCrcker можно производить разными способами: Dtbse Hierrchy Types сортировка по типам оборудования Dtbse Hierrchy Vendors сортировка по фирмамизготовителям Например Вам необходим в сетевом проекте сервер компании Cry Reserch C916. Для этого в разделе Supercomputers выберем г–ппу с оборудованием компании Cry Reserch а в нижнем окне Devices сервер C916. Двойной щелчок левой кнопкой мыши вызовет страницу свойств сервера и вы увидите полный набор его технических характеристик в т....
47540. Методические рекомендации. Государственное и муниципальное управление 644 KB
  Обязанности выпускника в ходе выполнения квалификационной работы Выбор темы выпускной квалификационной работы Структура и содержание выпускной квалификационной работы Оформление выпускной квалификационной работы
47541. Методические указания. Государственное и муниципальное управление 327.5 KB
  Анализ нормативноправовой базы управления Анализ системы управления организацией. Объектами профессиональной деятельности специалиста и практики студента в соответствии с ГОС являются: различные организации и подразделения в системе государственного и муниципального управления; процессы экономической политической организационной и социальной жизни общества; проблемы функционирования и развития государства и его региональных и муниципальных образований; проблемы взаимодействия человека и общества.65 в ходе практики должен быть...