Ітераційні методи вирішення систем лінійних рівнянь алгебри

У цій групі методів ми познайомимося з двома старими і простими методами:методом Якобі таметодом Гауса –Зейделя [8, 14].

Метод Якобі (простих ітерацій)

Задано систему лінійних рівнянь алгебри

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

Для збіжності ітераційного процесу, необхідно виконання умови «переважання діагональних елементів», тобто. діагональні елементи матриціА повинні задовольняти умови:

Перетворимо систему (3.10)до еквівалентної, виражаючи невідоме з кожногоi-го рівняння:

Система (3.13) називається системою,наведеною до нормального вигляду.

систему (3.13) можна записати у матричній формі

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

Таким чином, отримали послідовність наближень (ітерацій):

Якщо ця послідовність має межу

він є точним рішенням системи (3.11).

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

Критерій близькості двох наближень може бути визначений таким чином:

Якщо умова (3.18) виконано, то ітераційний процес припиняється. За наближене рішення системи (3.11) із заданою точністю e приймається (k)-е наближення, тобто.

.

Якщо умова (3.18) не виконується, то ітераційний процес (3.17) необхідно продовжити доти, доки умова не виконається.

GЗа мі ча н я:

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

2.Схожий процес ітерації має важливу властивістьсамовиправність, тобто. окрема помилка у обчисленнях не позначиться на остаточному результаті, отже помилкове наближення можна як новий початковий вектор.

nПриклад 3.2. Методом Якобі вирішити систему лінійних рівнянь алгебри:

Рішення: Умову переважання діагональних коефіцієнтів матриці системи виконано. Наведемо цю систему до нормального вигляду:

У матричній формі систему (3.20) можна записати так:

Започаткове(нульове) наближення рішення системи приймемонульовийвектор, тобто.

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

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

Після нової підстановки матимемо 3-тє наближення:

Аналогічно отримаємо 4-ту ітерацію:

Перевіримо виконання умови «близькості» двох ітерацій, тобто. умова (3.18):

Таким чином, за наближене рішення системи (3.19) з точністю ε=0,1 приймаємо 4 ітерацію

Щоб отримати рішення СЛАУ (3.19) з точністю ε=0,001, потрібно 8 ітерацій. Точне рішення:х1=1; х2=2; х3=1.

Рішення цього прикладу з використанням електронних таблицьExcelнаведено у розділі 3.6.3.

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

Метод є модифікацією методу Якобі. Основна ідеяМетоду у тому, що з обчисленні (k+1)-й ітерації невідоме обчислюється з урахуванням вже знайдених: .

Проілюструємо методn=3. Нехай система лінійних рівнянь алгебри вже приведена до нормального вигляду:

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

і підставляємо в перше рівняння системи (3.22):

Отримане перше наближення підставляємо в друге рівняння системи (3.22)

Використовуючи , знаходимо з 3-го рівняння

Цим закінчується побудова першої ітерації

Використовуючи значення , можна у такий самий спосіб побудувати такі ітерації. Ітерацію з номером (k+1) можна подати так:

Ітераційний процес триває доти, доки два сусідні наближення не стануть досить близькими. Критерій близькості може бути заданий умовою (3.18) і якщо воно виконується, то за наближене рішення системи (3.22) з точністюприймається (k+1) ітерація, тобто.

nПриклад 3.3. Методом Гауса – Зейделя вирішити ту саму систему (3.19), яку вирішували методом Якобі.

Система, наведена до нормального вигляду:

Як нульове наближення візьмемо вектор вільних членів:

Застосовуючи алгоритм Гауса-Зейделя, послідовно отримаємо

і т.д.

Розрахункова схема методу Гаусса-Зейделя з використанням електронних таблицьExcelаналогічно розрахунковій схемі методу Якобі, наведеної в розділі 3.6.1.

---