МЕТОД ГАУССА-СЕЙДЕЛЯ: ПОЯСНЕННЯ, ДОДАТКИ, ПРИКЛАДИ - МАТЕМАТИКА - 2024

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

Його створив Карл Фрідріх Гаус (1777-1855), який влаштував приватну демонстрацію одному зі своїх учнів у 1823 р. Пізніше її офіційно опублікував Філіпп Людвіг фон Сейдель (1821-1896) у 1874 р., Звідси і назва обох математиків.

Малюнок 1. Метод Гаусса-Сейделя швидко сходиться, щоб отримати рішення системи рівнянь. Джерело: Ф. Сапата.

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

Математично це виражається так:

Пояснення за допомогою простого випадку

Щоб проілюструвати, з чого складається метод Гаусса-Сейделя, ми візьмемо простий випадок, в якому значення X і Y можна знайти в системі лінійних рівнянь 2 × 2, показаній нижче:

5X + 2Y = 1

X - 4Y = 0

Кроки для виконання

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

-5 -> - 2-

Аналогічно, другий коефіцієнт у другому ряду також є діагонально домінуючим:

--4 -> - 1-

2- Змінюються змінні X і Y:

X = (1 - 2Y) / 5

Y = X / 4

3- Ставиться довільне початкове значення, яке називається "насінням": Xo = 1, I = 2.

4-Починається ітерація: щоб отримати перше наближення X1, Y1, насіння заміщене в першому рівнянні кроку 2 і результат у другому рівнянні кроку 2:

X1 = (1 - 2 I) / 5 = (1 - 2 × 2) / 5 = -3/5

Y1 = X1 / 4 = (-3/5) / 4 = -3/20

5- Проходимо аналогічним чином, щоб отримати друге наближення рішення системи рівнянь:

X2 = (1 - 2 Y1) / 5 = (1 - 2x (-3/20)) / 5 = 13/50

Y2 = X2 / 4 = (13/50) / 4 = 13/200

6- Третя ітерація:

X3 = (1 - 2 Y2) / 5 = (1 - 2 (13/200)) / 5 = 87/500

Y3 = X3 / 4 = (87/500) / 4 = 87/2000

7- Четверта ітерація, як остаточна ітерація цього ілюстративного випадку:

X4 = (1 - 2 Y3) / 5 = (1 - 2 (87/2000)) / 5 = 913/5000

Y4 = X4 / 4 = (913/5000) / 4 = 913/20000

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

Аналіз методу

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

Метод Гаусса-Сейделя не є паралельною процедурою, тоді як метод Гаусса-Йордана. Це також є причиною того, що метод Гаусса-Сейделя має більш швидку конвергенцію - за кілька кроків - ніж метод Йордана.

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

Попередній результат, отриманий чотирма ітераціями методу Гаусса-Сейделя, може бути записаний у десятковій формі:

X4 = 0,1826

Y4 = 0,04565

Точне рішення запропонованої системи рівнянь:

X = 2/11 = 0,1818

Y = 1/22 = 0,04545.

Тож за допомогою лише 4 ітерацій ви отримуєте результат з однією тисячною точністю (0,001).

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

Програми

Метод Гаусса-Сейделя не обмежується лише 2 × 2 системою лінійних рівнянь. Попередня процедура може бути узагальнена для розв’язання лінійної системи n рівнянь з n невідомими, яка представлена ​​в матриці так:

A X = b

Де A - матриця nxn, а X - вектор n компонентів n змінних, що підлягають обчисленню; і b - вектор, що містить значення незалежних доданків.

Для узагальнення послідовності ітерацій, застосованих у ілюстративному випадку до nxn-системи, з якої хоче бути обчислена змінна Xi, буде застосована наступна формула:

У цьому рівнянні:

- k - індекс для значення, отриманого в ітерації k.

-k + 1 вказує нове значення в наступному.

Кінцеве число ітерацій визначається тоді, коли значення, отримане в ітерації k + 1, відрізняється від отриманого безпосередньо перед цим на величину ε, яка є точно бажаною точністю.

Приклади методу Гаусса-Сейделя

- Приклад 1

Напишіть загальний алгоритм, який дозволяє обчислити вектор наближених розв’язків X лінійної системи рівнянь nxn, задавши матрицю коефіцієнтів A, вектор незалежних доданків b , кількість ітерацій (i ter) та початкове значення або "seed" «вектора X .

Рішення

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

Для k ∊

Для i ∊

X: = (1 / A) * (b - ∑ _{j = 1} ⁿ (A * X) + A * X)

- Приклад 2

Перевірте роботу попереднього алгоритму через його застосування у вільному та вільному користуванні математичним програмним забезпеченням SMath Studio, доступним для Windows та Android. Візьмемо як приклад матрицю 2 × 2, яка допомогла нам проілюструвати метод Гаусса-Сейделя.

Рішення

Малюнок 2. Розв’язування системи рівнянь з прикладу 2 х 2 за допомогою програмного забезпечення SMath Studio. Джерело: Ф. Сапата.

- Приклад 3

Застосуйте алгоритм Гаусса-Сейделя для наступної системи 3 × 3 рівнянь, попередньо впорядковану таким чином, що домінуючі коефіцієнти діагоналі (тобто більші абсолютні значення, ніж абсолютні значення коефіцієнтів той же ряд):

9 X1 + 2 X2 - X3 = -2

7 X1 + 8 X2 + 5 X3 = 3

3 X1 + 4 X2 - 10 X3 = 6

Використовуйте нульовий вектор як насіння і врахуйте п’ять ітерацій. Прокоментуйте результат.

Рішення

Малюнок 3. Розв’язування системи рівнянь вирішеного прикладу 3 за допомогою SMath Studio. Джерело: Ф. Сапата.

Для тієї ж системи з 10 ітераціями замість 5 виходять такі результати: X1 = -0,485; X2 = 1,0123; X3 = -0,3406

Це говорить про те, що п'яти ітерацій достатньо для отримання точності трьох десяткових знаків і що метод швидко переходить до рішення.

- Приклад 4

Використовуючи алгоритм Гаусса-Сейделя, наведений вище, знайдіть рішення 4 × 4 системи рівнянь, наведених нижче:

10 x1 - x2 + 2 x3 + 0 x4 = 6

-1 x1 + 11 x2 - 1 x3 + 3 x4 = 25

2 x1 - 1 x2 + 10 x3 - 1 x4 = -11

0 x1 + 3 x2 - 1 x3 + 8 x4 = 15

Щоб розпочати метод, скористайтеся цим насінням:

x1 = 0, x2 = 0, x3 = 0 і x4 = 0

Розгляньте 10 ітерацій та оцініть похибку результату, порівнюючи з ітерацією №11.

Рішення

Малюнок 4. Розв’язування системи рівнянь розв’язаного прикладу 4 за допомогою SMath Studio. Джерело: Ф. Сапата.

При порівнянні з наступною ітерацією (число 11) результат є ідентичним. Найбільші відмінності між двома ітераціями є в порядку 2 × 10 ^-8 , а це означає, що відображене рішення має точність не менше семи знаків після коми.

Список літератури

1. Ітеративні методи рішення. Гаус-Сейдель. Відновлено з: cimat.mx
2. Числові методи. Гаус-Сейдель. Відновлено з: test.cua.uam.mx
3. Числовий: метод Гаусса-Сейделя. Відновлено з: aprendeenlinea.udea.edu.co
4. Вікіпедія. Метод Гаусса-Сейделя. Відновлено: en. wikipedia.com
5. Вікіпедія. Метод Гаусса-Сейделя. Відновлено з: es.wikipedia.com