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

Лекція Ітераційні методи розв'язання системи лінійних рівнянь алгебри.

Умова збіжності ітераційного процесу. Метод Якобі. Метод Зейделя

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

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

Для застосування ітераційних методів система має бути наведена до еквівалентного вигляду

Потім вибирається початкове наближення до розв'язання системи рівнянь і знаходиться послідовність наближень до кореня.

Для збіжності ітераційного процесу достатньо, щоб було виконано умову
(Норма матриці). Критерій закінчення ітерацій залежить від застосовуваного ітераційного методу.

Метод Якобі .

Найпростіший спосіб приведення системи до вигляду, зручного для ітерації, полягає в наступному:

З першого рівняння системи висловимо невідоме x 1 , з другого рівняння системи виразимо x 2 і т. д.

В результаті отримаємо систему рівнянь із матрицею B, в якій на головній діагоналі стоять нульові елементи, а решта елементів обчислюється за формулами:

Компоненти вектора d обчислюються за формулами:

Розрахункова формула методу простої ітерації має вигляд:

або у покоординатній формі запису виглядає так:

Критерій закінчення ітерацій у методі Якобі має вигляд:

Якщо
, то можна застосовувати простіший критерій закінчення ітерацій

приклад 1.Розв'язання системи лінійних рівнянь методом Якобі.

Нехай дана система рівнянь:

Потрібно знайти рішення системи з точністю

Наведемо систему до вигляду зручного для ітерації:

Виберемо початкове наближення, наприклад,

- Вектор правої частини.

Тоді перша ітерація виходить так:

Аналогічно виходять такі наближення до рішення.

Знайдемо норму матриці B.

Будемо використовувати норму

Оскільки сума модулів елементів у кожному рядку дорівнює 0.2, то
тому критерій закінчення ітерацій у цьому завданні

Обчислимо норми різниць векторів:

Так як
задану точність досягнуто на четвертій ітерації.

Відповідь: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

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

Метод можна як модифікацію методу Якобі. Основна ідея полягає в тому, що при обчисленні чергового (n+1)-го наближення до невідомого x iпри i >1використовують уже знайдені (n+1)-е наближення до невідомих x 1 ,x 2 , ...,x i - 1 , а не n-ое наближення, як у методі Якобі.

Розрахункова формула методу у покоординатній формі запису виглядає так:

Умови збіжності та критерій закінчення ітерацій можна взяти такими ж, як у методі Якобі.

приклад 2.Вирішення систем лінійних рівнянь методом Зейделя.

Розглянемо паралельно розв'язання 3-х систем рівнянь:

Наведемо системи до вигляду зручного для ітерацій:

Зауважимо, що умова збіжності
виконано лише першої системи. Обчислимо 3 перші наближення до рішення у кожному випадку.

1-а система:

Точним рішенням будуть значення: x 1 = 1.4, x 2 = 0.2 . Ітераційний процес сходиться.

Друга система:

Очевидно, що ітераційний процес розходиться.

Точне рішення x 1 = 1, x 2 = 0.2 .

3-я система:

Очевидно, що ітераційний процес зациклився.

Точне рішення x 1 = 1, x 2 = 2 .

Нехай матриця системи рівнянь A – симетрична та позитивно визначена. Тоді за будь-якого вибору початкового наближення метод Зейделя сходиться. Додаткових умов трохи норми деякої матриці тут не накладається.

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

Якщо A – симетрична та позитивно визначена матриця, то систему рівнянь часто призводять до еквівалентного вигляду:

x=x-τ (A x- b), τ – ітераційний параметр.

Розрахункова формула методу простої ітерації в цьому випадку має вигляд:

x (n+1) =x n- τ (A x (n) - b).

параметр τ > 0 вибирають так, щоб по можливості зробити мінімальною величину

Нехай λ min та λ max – мінімальне та максимальне власні значенняматриці A. Оптимальним є вибір параметра

В цьому випадку
приймає мінімальне значення рівне:

приклад 3. Рішення систем лінійних рівняньметодом простої ітерації. (в MathCAD)

Нехай дана система рівнянь Ax = b

Для побудови ітераційного процесу знайдемо власні числаматриці A:

- Використовується вбудована функція для знаходження власних чисел.

Обчислимо ітераційний параметр та перевіримо умову збіжності

Умову збіжності виконано.

Візьмемо початкове наближення - вектор x0, задамо точність 0.001 і знайдемо початкові наближення за наведеною нижче програмою:

Точне рішення

Зауваження. Якщо в програмі повертати матрицю rez, можна переглянути всі знайдені ітерації.

1. Нехай відомий відрізок , який містить один корінь рівняння f(x) = 0. Функція f є безперервно функцією, що диференціюється на цьому відрізку (f(x)ÎC 1 ). За виконання цих умов можна застосовувати метод простої ітерації.

2. За функцією f(x) будується функція j(x), що задовольняє трьом умовам: вона повинна бути безперервно диференційованою (j(x)ÎC 1 ), така, що рівняння x = j(x) рівносильно рівнянню f(x)=0; повинна також перекладати відрізок у собі.

Будемо говорити, що функція j ( x ) перекладає відрізок [ a , b ] у себе, якщо для будь-кого x Î [ a , b ], y = j ( x ) також належить[ a , b ] ( y Î [ a , b ]).

На функцію j(x) накладається третя умова:

Формула методу: x n +1 = j(x n).

3. У разі виконання цих трьох умов для будь-якого початкового наближення x 0 Î послідовність ітерацій x n +1 = j(x n) сходить до кореня рівняння: x = j(x) на відрізку ().

Як правило, як x 0 вибирається один з кінців.

,

де e – задана точність

Число x n +1 при виконанні умови зупинки ітераційного процесу є наближеним значенням кореня рівняння f(x) = 0 на відрізку , знайденим методом простої ітерації з точністю e .

Побудувати алгоритм для уточнення кореня рівняння: x 3 + 5x – 1 = 0 на відрізку методом простої ітерації з точністю e .

1. Функція f(x) = x 3+5x-1 є безперервно диференційованою на відрізку, що містить один корінь рівняння.

2. Найбільшу складність у методі простої ітерації представляє побудова функції j(x), яка задовольняє всім умовам:

Розглянемо: .

Рівняння x = j 1 (x) еквівалентно рівнянню f(x) = 0, але функція j 1 (x) не є безперервно диференційованою на відрізку .

Рис. 2.4. Графік функції j 2 (x)

З іншого боку, отже, . Звідси: - Безперервно функція, що диференціюється. Зазначимо, що рівняння: x = j 2 (x) еквівалентне рівнянню f (x) = 0 . З графіка (рис. 2.4) видно, що функція j 2 (x) переводить відрізок у себе.

Умова, що функція j(x) переводить відрізок у собі, можна переформулювати в такий спосіб: нехай – область визначення функції j(x), а – область зміни j(x).

Якщо відрізок належить відрізку , то функція j(x) переводить відрізок у собі.

, .

Усі умови функції j(x) виконані.

Формула ітераційного процесу: x n +1 = j 2 (xn).

3. Початкове наближення: x0 = 0.

4. Умова зупинення ітераційного процесу:

Рис. 2.5. Геометричний змістметоду простої ітерації

.

За виконання цієї умови x n +1 – наближене значення кореня на відрізку, знайдене методом простої ітерації з точністю e. На рис. 2.5. ілюструється застосування методу простої ітерації.

Теорема про збіжність та оцінка похибки

Нехай відрізок містить один корінь рівняння x = j(x), функція j(x ) є безперервно диференційованою на відрізку , перекладає відрізок в собі, і виконано умову:

.

Тоді для будь-якого початкового наближення x 0 Î послідовність сходиться до кореня рівняння y = j(x ) на відрізку і справедлива оцінка похибки:

.

Стійкість методу простої ітерації. При виконанні умов теореми про збіжність алгоритм методу простої ітерації є стійким.

Складність методу простої ітерації. Обсяг пам'яті ЕОМ, необхідний реалізації методу простої ітерації, незначний. На кожному кроці слід зберігати x n , x n +1 , q і e.

Оцінимо кількість арифметичних дій, необхідні реалізації методу простої ітерації. Запишемо оцінку для числа n 0 = n 0 (e) такого, що для всіх n ³ n 0 виконується нерівність:

З цієї оцінки випливає, що чим ближче до q одиниці, тим повільніше сходиться метод.

Зауваження. Не існує загального правилапобудови j(x) f(x) так, щоб виконувались всі умови теореми про збіжність. Часто використовується наступний підхід: як функцію j вибирається функція j(x) = x + k× f(x), де k – константи.

При програмуванні методу простої ітерації для припинення ітераційного процесу часто вимагають одночасного виконання двох умов:

та .

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

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

Теорема Самарського

Нехай - самосполучена позитивно визначена матриця:

,
,

- позитивно визначена матриця, - додатне число:

,
.

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

Перш ніж переходити до доказу теореми, обговоримо докладніше головну її вимогу – позитивну визначеність матриці
. Цю вимогу можна переписати у вигляді:

,
,
.

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

.

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

і підставимо рекурентну формулу для ітераційної послідовності. В результаті отримаємо:

.

Відмінність ітераційної формули полягає в тому, що вона є однорідною.

Матриця - Позитивно визначена. Отже вона невироджена і має зворотну
. З її допомогою рекурентне співвідношенняможна дозволити щодо
:

, так що
.

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

.

Розглянемо послідовність позитивних функціоналів:

.

Складемо аналогічний вираз для
і перетворимо його за допомогою рекурентних формул і:

З самосполучення матриці і формули слід

У результаті формула набуває вигляду:

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

.

,

де
- Суворо позитивна константа. В результаті, згідно і будемо мати

З цієї нерівності та збіжності послідовності функціоналів випливає, що
при
. В свою чергу
, так що

Теорему доведено.

1. Метод простий ітерації.

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

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

.

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

Розкладемо вектор
за базисом власних векторів

У результаті формули випливає, що метод простої ітерації сходиться за будь-якого , що належить інтервалу

.

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

,

і перепишемо формулу у вигляді

.

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

.

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

Лемма 1

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

.

Підтвердження просто. Воно проводиться прямою перевіркою

При самосполученій матриці матриця також є самосполученим. Отже, її норма визначається найбільшим за модулем власним значенням
:

.

Лемма 2

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

,

Достатність. Умова означає, що норма матриці , відповідно, буде менше одиниці:
. В результаті отримуємо

При
.

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

.

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

,
.

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

Лемма 2 визначає програму подальшого дослідження збіжності методу простої ітерації: потрібно встановити діапазон зміни параметра у якому всі власні значення задовольняють нерівності. Це легко зробити. На рис. 1 наведено графіки спадних лінійних функцій
. Усі вони виходять із однієї точки
,
і йдуть вниз через негативні коефіцієнти при , причому найшвидше зменшується функція
. Коли вона набуває значення
, Умова для неї перестає виконуватися:

, при
.

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

.

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

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

.

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

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

яке дає

.

В результаті отримуємо:

Своє найменше значення норма матриці досягає при
:

.

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

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

Завдання 2.

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

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

Випишемо відразу рішення системи

,
,

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

Перейдемо до вирішення системи шляхом простої ітерації. Матриця системи має вигляд

.

Вона самосполучена та позитивно визначена, оскільки

Складемо характеристичне рівняння для матриці і знайдемо його коріння:

,

,

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

,
.

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

, де

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

,
,
,

,
,
,

,
,
,

,
,
.

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

.

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

Слід зауважити, що умови та швидкість збіжності ітераційного процесу суттєво залежать від властивостей матриці. Асистеми та від вибору початкових наближень.

Для застосування методу ітерацій вихідну систему (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:

Очевидно, отримано результат майже сьомої ітерації.

Метод простих ітерацій заснований на заміні вихідного рівняння еквівалентним рівнянням:

Нехай відоме початкове наближення до кореня х = х 0. Підставивши його в праву частинурівняння (2.7), отримаємо нове наближення потім аналогічним чином отримаємо і т.д.:

. (2.8)

Не за всіх умов ітераційний процес сходиться до кореня рівняння х. Розглянемо цей процес докладніше. На рис.2.6 наведено графічна інтерпретаціяодностороннього схожого і розбіжного процесу. На рис.2.7 зображені двосторонній схожий і розбіжний процеси. Розбіжний процес характеризується швидким наростанням значень аргументу та функції та аварійним завершенням відповідної програми.

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

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

Отже, що менше поблизу кореня, то швидше сходиться процес.

Для того щоб ітераційний процес був схожим, необхідно в околиці кореня виконання наступної нерівності:

Перехід від рівняння (2.1) до рівняння (2.7) можна здійснити у різний спосібзалежно від виду функції f(x).За такого переходу необхідно побудувати функцію те щоб виконувалася умова збіжності (2.9).

Розглянемо один із загальних алгоритмів переходу від рівняння (2.1) до рівняння (2.7).

Помножимо ліву та праву частини рівняння (2.1) на довільну константу bі додамо до обох частин невідоме х.При цьому коріння вихідного рівняння не зміниться:

Введемо позначення і перейдемо від співвідношення (2.10) до рівняння (2.8).

Довільний вибір константи bдозволить забезпечити виконання умови збіжності (2.9). Критерієм закінчення ітераційного процесу буде умова (2.2). На рис.2.8 наведено графічна інтерпретація методу простих ітерацій при описаному способі уявлення (масштаби по осях X та Y різні).

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

Програмна реалізація методу простих ітерацій виконана у вигляді процедури-підпрограми Iteras(ПРОГРАМА 2.1).

Вся процедура практично складається з одного циклу Repeat... Until, що реалізує формулу (2.11) з урахуванням умови припинення ітераційного процесу (формула (2.2)).

У процедуру вбудовано захист від зациклювання шляхом підрахунку числа циклів за допомогою змінної Niter. на практичних заняттяхнеобхідно переконатися шляхом прогону програми у тому, як позначається вибір коефіцієнта bта початкового наближення на процесі пошуку кореня. При зміні коефіцієнта bхарактер ітераційного процесу досліджуваної функції змінюється. Він стає спочатку двостороннім, та був зациклюється (рис.2.9). Масштаби по осях Xі Yрізні. Ще більше значення модуля b призводить до процесу, що розходиться.

Порівняння методів наближеного розв'язування рівнянь

Порівняння описаних вище методів чисельного рішеннярівнянь проводилося за допомогою програми, що дозволяє на екрані ПЕОМ спостерігати процес знаходження кореня в графічному вигляді. Процедури, що входять до цієї програми та реалізують порівнювані методи, наведено нижче (ПРОГРАМА 2.1).

Рис. 2.3-2.5, 2.8, 2.9 є копіями екрана ПЕОМ після закінчення ітераційного процесу.

Як досліджувану функцію у всіх випадках було взято квадратне рівняння x 2 -x-6 = 0, що має аналітичне рішення х 1 = -2 і х 2 = 3. Похибка та початкові наближення приймалися для всіх методів рівними. Результати пошуку кореня х= 3 представлені на малюнках, такі. Найбільш повільно сходиться метод дихотомії – 22 ітерації, найшвидший – метод простих ітерацій при b = -0.2 – 5 ітерацій. Тут немає суперечності із твердженням, що метод Ньютона є найшвидшим.

Похідна досліджуваної функції у точці х= 3 дорівнює -0.2, тобто розрахунок у разі вівся практично методом Ньютона з величиною похідної у точці кореня рівняння. При зміні коефіцієнта bшвидкість збіжності падає і процес, що поступово сходить, спочатку зациклюється, потім стає розбіжним.