Метод простих ітерацій у загальному вигляді. Метод простої ітерації на вирішення систем лінійних рівнянь (слау)

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

Білет №29

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

Метод Зейделя (іноді званий методом Гаусса-Зейделя) є модифікацією методу простої ітерації, що полягає в тому, що при обчисленні чергового наближення x (k+1) (див. формули (1.13), (1.14)) його вже отримані компоненти x 1 ( k+1) , ...,x i - 1 (k+1) відразу ж використовуються для обчислення x i (k+1) .

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

X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + d n
де x(0) – деяке початкове наближення до рішення.

Таким чином i-та компонента (k+1)-го наближення обчислюється за формулою

Умова закінчення ітераційного процесу Зейделя при досягненні точності в спрощеній формі має вигляд:

|| x(k+1) - x(k) || ≤ ε.

Білет №30

Метод прогонки

Для розв'язання систем A x = b з тридіагональною матрицею найчастіше застосовується метод прогонки, що є адаптацією методу Гауса до цього випадку.

Запишемо систему рівнянь

d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n

у матричному вигляді: A x = b де

A=

Випишемо формули методу прогонки у порядку їх застосування.

1. Прямий хід методу прогонки (обчислення допоміжних величин):

2. Зворотній хідметоду прогонки (знаходження рішення):

Білет №31

Метод простих ітерацій

Суть методу простих ітераційполягає в переході від рівняння

f(x)= 0 (*)

до еквівалентного рівняння

x=φ(x). (**)

Цей перехід можна здійснити різними способами, в залежності від виду f(x). Наприклад, можна покласти

φ(x) = x+bf(x),(***)

де b= const, у своїй коріння вихідного рівняння не изменятся.

Якщо відомо початкове наближення до кореня x 0, то нове наближення

x 1=φx(0),

тобто. загальна схема ітераційного процесу:

x k+1=φ(x k).(****)

Найбільш простий критерій закінчення процесу

|x k +1 -x k |<ε.

Критерій збіжностіметоду простих ітерацій:

якщо поблизу кореня | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого x, то ітерації сходяться за будь-якого початкового наближення.

Досліджуємо вибір константи bз погляду забезпечення максимальної швидкості збіжності. Відповідно до критерію збіжності найбільша швидкість збіжності забезпечується при |? / (x) | = 0. При цьому, виходячи з (***), b = -1/f / (x),та ітераційна формула (****) переходить у x i = x i-1 -f(x i-1)/f/ (x i-1).-тобто. у формулу методу Ньютона. Таким чином, метод Ньютона є окремим випадком методу простих ітерацій, що забезпечує найвищу швидкість збіжності з усіх можливих варіантів вибору функції φ(x).

Білет №32

Метод Ньютона

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

Нехай - певна на відрізку та диференційована на ньому речовиннозначна функція. Тоді формула ітеративного обчислення наближень може бути виведена таким чином:

де α - кут нахилу дотичної в точці.

Отже шуканий вираз має вигляд:

Білет №33

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

Розподіл інтервалу на нерівні частини дозволяє знайти ще ефективніший метод. Обчислимо функцію на кінцях відрізка [ a,b] і покладемо a=x 1 , b=x 2 . Обчислимо також функцію у двох внутрішніх точках x 3 , x 4 . Порівняємо всі чотири значення функції та виберемо серед них найменше. Нехай, наприклад, найменшим виявилося f(x 3). Очевидно, що мінімум перебувати в одному з прилеглих до нього відрізків. Тому відрізок [ x 4 ,b] можна відкинути та залишити відрізок .

Перший крок зроблено. На відрізку знову треба вибрати дві внутрішні точки, обчисливши в них і на кінцях значення функції та зробити наступний крок. Але на попередньому етапі обчислень ми вже знайшли функцію на кінцях нового відрізка і в одній його внутрішній точці x 4 . Тому достатньо вибрати всередині ще одну точку x 5визначити у ній значення функції та провести необхідні порівняння. Це вчетверо зменшує обсяг обчислень однією етапі процесу. Як вигідно розміщувати точки? Щоразу залишок відрізок ділитися на три частини і потім відкидається один із крайніх відрізків.
Позначимо початковий інтервал невизначеності через D.

Так як у загальному випадку може бути відкинутий будь-який відрізок Х 1 ,Х 3або Х 4 ,Х 2то оберемо крапки Х 3і Х 4так, щоб довжини цих відрізків були однакові:

x 3 -x 1 =x 4 -x 2.

Після відкидання вийде новий інтервал невизначеності довжини D′.
Позначимо ставлення D/D′літерою φ:

тобто припустимо, де - наступний інтервал невизначеності. Але

по довжині дорівнює відрізку, відкинутому на попередньому етапі, тобто

Тому отримаємо:

.
Це призводить до рівняння або, що те саме
.

Позитивний корінь цього рівняння дає

.

Білет №34

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

За аналогією з (2.1) систему (5.1) можна подати у наступній еквівалентній формі:

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

• 1) вибирається деякий початковий вектор х ((,) е 5 (х 0 , а)(передбачається, що х* е 5„(х 0 , а));
• 2) наступні наближення обчислюються за формулою

то ітераційний процес завершено і

Як і раніше, нам необхідно з'ясувати, за яких умов

Обговоримо це питання, виконавши простий аналіз. Спочатку ми введемо помилку /г-го наближення як е (^ = x(i) - х *. Тоді ми можемо записати

Підставимо ці вирази (5.3) і розкладемо g(x* + e (/i)) за ступенями е (до>в околиці х* як функцію векторного аргументу (припускаючи, що всі похідні приватні функції g(x) безперервні). Враховуючи також, що х* = g(x*) ми отримаємо

або в матричній формі

В = (b nm)= I (х *) 1 - ітераційна матриця.

Якщо норма помилки ||е®|| досить мала, то другий доданок у правій частині виразу (5.4) можна знехтувати, і тоді воно збігається з виразом (2.16). Отже, умова збіжності ітераційного процесу (5.3) поблизу точного рішення описується теоремою 3.1.

Схожість методу простої ітерації. Необхідне та достатня умовадля збіжності ітераційного процесу (5.3):

та достатня умова:

Ці умови мають радше теоретичне, ніж практичне значення, оскільки ми не знаємо х'. За аналогією з (1.11) отримаємо умову, яка може бути корисною. Нехай х * е 5 про (х 0, а)та матриця Якобі для функції g(x)

існує для всіх x e S n (x 0 a) (зауважимо, що C(x*) = В). Якщо елементи матриці С(х) задовольняють нерівність

для всіх х е 5„(х 0 , а),тоді достатня умова (5.5) також виконується для будь-якої матричної норми.

Приклад 5.1 (метод простої ітерації) Розглянемо таку систему рівнянь:

Одна з можливостей подати цю систему в еквівалентній формі (5.2) – висловити Хз першого рівняння та х 2з другого рівняння:

Тоді ітераційна схема має вигляд

Точне рішення х* е 5„((2, 2), 1). Виберемо початковий вектор х (0) = (2,2) та ? р =КТ 5 . Результати обчислень представлені у табл. 5.1.

Таблиця 5.1

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

тоді матриця приблизно оцінюється як

Легко перевірити, що умова (5.5), ні умова (5.6) не задовольняються, але збіжність має місце, оскільки 5(B) ~ 0.8.

Часто можна прискорити збіжність методу простої ітерації, трохи змінивши процес обчислень. Ідея такої модифікації дуже проста: для обчислення п-й компоненти вектора х (А+1)можна використовувати не тільки (т = п,..., N), але також вже обчислені компоненти вектора наступного наближення х до ^ (/= 1,п - 1). Таким чином, модифікований метод простої ітерації може бути представлений у вигляді наступної ітераційної схеми:

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

Приклад 5.2 (модифікований метод простої ітерації) Модифікована проста ітерація системи (5.7) подається у вигляді

Як і раніше, виберемо початковий вектор х (0) = (2, 2) та р р = = 10 -5. Результати обчислень представлені у табл. 5.2.

Таблиця 5.2

I Теболина зміна порядку обчислень призвела до зменшення кількості ітерацій у два рази, а значить, і до зменшення кількості операцій у два рази.

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

Алгоритм методу простої ітерації:

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

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

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

12. Основна ітераційна формула, що застосовується у методі простої ітерації, для вирішення нелінійного рівняння:

13. Критерій зупинки ітераційного процесу у методі простої ітерації на вирішення нелінійного рівняння:

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

14. Критерій вибору допоміжної функції F(x) для ітераційного відрізка інтервалу:

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

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

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

15. Метод Гауса, що застосовується для розв'язання систем лінійних рівнянь, передбачає:

Метод заснований на перетворенні матриці до трикутного вигляду. Це досягається послідовним виняткомневідомих із рівнянь системи.

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

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

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

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

Постановка задачі[ | ]

Розглянемо методи чисельного розв'язання рівнянь та систем рівнянь:

( f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 (\displaystyle \left\((\begin(array)(lcr)f_(1) )(x_(1),x_(2),\ldots ,x_(n))&=&0\\ldots &&\f_(n)(x_(1),x_(2),\ldots ,x_( n))&=&0\end(array))\right.)

Чисельні методи розв'язування рівнянь[ | ]

Покажемо, як можна вирішити початкову систему рівнянь, не вдаючись до оптимізаційних методів. У випадку, якщо наша система є СЛАУ, доцільно вдатися до таких методів, як метод Гауса або метод Річардсона. Однак ми все ж таки виходитимемо з припущення, що вид функції нам невідомий, і скористаємося одним із ітераційних методів чисельного рішення. Серед великої різноманітності таких виберемо один із найбільш відомих - метод Ньютона. Цей метод у свою чергу ґрунтується на принципі стискаючого відображення. Тому спочатку буде викладено суть останнього.

Стискаюче відображення[ | ]

Визначимо термінологію:

Говорять, що функція здійснює стискаюче відображення на , якщо

Тоді справедлива наступна основна теорема:

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

Пояснимо зміст параметра α (\displaystyle \alpha)для випадку однієї змінної. Відповідно до теореми Лагранжа маємо: