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


 

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

4733. Соціологія, як наука. Її місце в системі наук 910.96 KB
  Предмет соціології та її місце в системі суспільної науки. Структура та функції соціології. Мета вивчення соціології. Societas – суспільство. Logos – наука...
4734. Современные проблемы отечественной энергетики 49.5 KB
  Введение В данном реферате отображены некоторые проблемы, стоящие перед энергетическим сектором страны, и возможные пути их решения. В работе рассмотрены вопросы выработки ресурса энергетического оборудования, эксплуатирующегося в РАО ЕЭС России...
4735. Стены из облегченной кладки 110 KB
  Стены из облегченной кладки Выполнение наружных стен зданий из облегченной кладки с утеплителями, позволяет существенно уменьшить расход кирпича и цемента, а также повысить сопротивление стен теплопередаче, что уменьшает расход топлива. Рекомендуетс...
4736. Системы автоматической посадки самолетов для XXI века 60 KB
  Системы автоматической посадки самолетов для XXI века Катастрофа в августе 1997 года. самолета Boeing-747, выполнявшего заход на посадку по неточной системе посадки (non-precision) ночью в сложных метеоусловиях на ВПП 06L международного аэропорта...
4737. Основы технологии производства установок ЛА 8.68 MB
  Основы технологии производства установок ЛА. Основные понятия и определения. Процесс изготовления изделия проходит много этапов, начиная с добычи руды (продукт природы) и превращения её на металлургических предприятиях в металл или по...
4738. Конденсаційні установки. Замкненість пароводяного циклу ТЕС та АЕС 1.09 MB
  Конденсаційні установки Замкненість пароводяного циклу ТЕС та АЕС досягається конденсацією відпрацьованої пари у конденсаційній установці (конденсаторі). Цей процес відбувається при постійному тискові завдяки передачі тепла конденсації пари во...
4739. Применение уравнения Шредингера 120.5 KB
  Применение уравнения Шредингера Частица в потенциальной яме с бесконечно высокими стенками. Пусть в одномерном пространстве создано силовое поле, потенциальная энергия которого бесконечна везде, кроме области...
4740. Развитие и деловая оценка персонала на примере ФГУП Институт реакторных материалов 663.5 KB
  Введение Жизнестойкость, конкурентоспособность национальной экономики напрямую зависят от того, насколько образованы и подготовлены к профессиональной деятельности работники, насколько эффективно используются их знания и навыки, как отлажен механизм...
4741. Расчёт эксплуатационных свойств автомобиля 512 KB
  Введение Тяговый расчет автомобиля производится с целью определения его тяговых и динамических качеств. Тяговый расчет подразделяется на: тяговый расчет проектируемой машины поверочный тяговый расчет, производимый для существующей машины. Поверочны...