Метод Гаусса – Зейделя - это итерационный метод решения квадратной системы из n линейных уравнений с неизвестным x :
- .
Он определяется итерацией
где является к - е приближение или итерацияследующая или k + 1 итерация, а матрица A раскладывается на нижнюю треугольную составляющую, и строго верхнетреугольная составляющая т.е. . [3]
Более подробно выпишите A , x и b в их компонентах:
Тогда разложение A на его нижнюю треугольную компоненту и строго верхнюю треугольную компоненту имеет вид:
Систему линейных уравнений можно переписать как:
Метод Гаусса – Зейделя теперь решает левую часть этого выражения для x , используя предыдущее значение для x в правой части. Аналитически это можно записать так:
Однако, пользуясь преимуществом треугольной формы , элементы x ( k +1) могут быть вычислены последовательно с использованием прямой подстановки :
- [4]
Процедура обычно продолжается до тех пор, пока изменения, внесенные итерацией, не станут ниже некоторого допуска, например, достаточно малого остатка .
Обсуждение
Поэлементная формула метода Гаусса – Зейделя очень похожа на формулу метода Якоби .
Вычисление x ( k +1) использует элементы x ( k +1) , которые уже были вычислены, и только элементы x ( k ) , которые не были вычислены в итерации k + 1. Это означает, что, в отличие от метода Якоби, требуется только один вектор хранения, поскольку элементы могут быть перезаписаны по мере их вычисления, что может быть выгодно для очень больших задач.
Однако, в отличие от метода Якоби, вычисления для каждого элемента не могут выполняться параллельно . Кроме того, значения на каждой итерации зависят от порядка исходных уравнений.
Гаусса-Зейделя такое же , как SOR (метод релаксации) с.
Пример для матричной версии
Линейная система, показанная как дан кем-то:
- а также
Мы хотим использовать уравнение
в виде
где:
- а также
Мы должны разложить в сумму нижней треугольной составляющей и строгий верхнетреугольный компонент :
- а также
Обратное является:
- .
Теперь мы можем найти:
Теперь у нас есть а также и мы можем использовать их для получения векторов итеративно.
Прежде всего, мы должны выбрать : мы можем только догадываться. Чем точнее предположение, тем быстрее будет работать алгоритм.
Мы предполагаем:
Затем мы можем вычислить:
Как и ожидалось, алгоритм сходится к точному решению:
Фактически, матрица A строго диагонально доминирует (но не положительно определена).
Другой пример для матричной версии
Другая линейная система, показанная как дан кем-то:
- а также
Мы хотим использовать уравнение
в виде
где:
- а также
Мы должны разложить в сумму нижней треугольной составляющей и строгий верхнетреугольный компонент :
- а также
Обратное является:
- .
Теперь мы можем найти:
Теперь у нас есть а также и мы можем использовать их для получения векторов итеративно.
Прежде всего, мы должны выбрать : мы можем только догадываться. Чем точнее предположение, тем быстрее будет выполнен алгоритм.
Мы предполагаем:
Затем мы можем вычислить:
Если мы проверим сходимость, мы обнаружим, что алгоритм расходится. Фактически, матрица A не является ни диагонально доминирующей, ни положительно определенной. Тогда сходимость к точному решению
не гарантируется и в этом случае не произойдет.
Пример версии уравнения
Предположим, что даны k уравнений, где x n - векторы этих уравнений и начальная точка x 0 . Из первого уравнения решите для x 1 черезДля следующих уравнений подставьте предыдущие значения x s.
Чтобы было понятно, рассмотрим пример.
Решение для а также дает:
Предположим, мы выбрали (0, 0, 0, 0) в качестве начального приближения, тогда первое приближенное решение дается формулой
Используя полученные приближения, итерационная процедура повторяется до тех пор, пока не будет достигнута желаемая точность. Ниже приведены приближенные решения после четырех итераций.
Точное решение системы - (1, 2, −1, 1) .
Пример использования Python и NumPy
Следующая численная процедура просто повторяется для получения вектора решения.
импортировать numpy как npITERATION_LIMIT = 1000# инициализировать матрицу A = np . массив ([[ 10. , - 1. , 2. , 0. ], [ - 1. , 11. , - 1. , 3. ], [ 2. , - 1. , 10. , - 1. ], [ 0. , 3. , - 1. , 8. ]]) # инициализировать вектор RHS b = np . массив ([ 6.0 , 25.0 , - 11.0 , 15.0 ])печать ( "Система уравнений:" ) для I в диапазоне ( . форма [ 0 ]): строка = [ " {0: 3g} * х {1} " . Формат ( [ я , J ], J + 1 ) для J в диапазоне ( . форма [ 1 ])] для печати ( "[ {0} ] = [ {1: 3g} ]" . Формат ( "+" . join ( строка ), b [ i ])) х = нп . zeros_like ( b ) для it_count в диапазоне ( 1 , ITERATION_LIMIT ): x_new = np . zeros_like ( х ) печать ( "Итерация {0} : {1} " . Формат ( it_count , х )) для I в диапазоне ( . форма [ 0 ]): s1 = нп . Точка ( [ я , : я ], x_new [: я ]) с2 = нп . точка ( A [ i , i + 1 :], x [ i + 1 :]) x_new [ i ] = ( b [ i ] - s1 - s2 ) / A [ i , i ], если np . allclose ( x , x_new , rtol = 1e-8 ): break x = x_new print ( "Решение: {0} " . format ( x )) error = np . точка ( A , x ) - b print ( "Ошибка: {0} " . формат ( ошибка ))
Производит вывод:
Система из уравнений : [ 10 * x1 + - 1 * х2 + 2 * х3 + 0 * х4 ] = [ 6 ] [ - 1 * x1 + 11 * х2 + - 1 * х3 + 3 * х4 ] = [ 25 ] [ 2 * x1 + - 1 * x2 + 10 * x3 + - 1 * x4 ] = [ - 11 ] [ 0 * x1 + 3 * x2 + - 1 * x3 + 8 * x4 ] = [ 15 ] Итерация 1 : [ 0 . 0. 0. 0. ] Итерация 2 : [ 0,6 2,32727273 - 0,98727273 0,87886364 ] Итерация 3 : [ 1,03018182 2,03693802 - 1,0144562 0,98434122 ] Итерация 4 : [ 1,00658504 2,00355502 - 1,00252738 0,99835095 ] Итерация 5 : [ 1,00086098 2,00029825 - 1,00030728 0,99984975 ] Итерация 6 : [ 1.00009128 2.00002134 - 1.00003115 0.9999881 ] Итерация 7 : [ 1,00000836 2,00000117 - 1,00000275 0,99999922 ] Итерация 8 : [ 1,00000067 2,00000002 - 1,00000021 0,99999996 ] Итерация 9 : [ 1,00000004 1,99999999 - 1,00000001 1. ] Итерация 10 : [ 1. 2. - 1. 1. ] Решение : [ 1. 2. - 1. 1. ] Ошибка : [ 2.06480930e-08 - 1.25551054e-08 3.61417563e-11 0.00000000e + 00 ]
Программы для решения произвольной нет. уравнений с помощью Matlab
В следующем коде используется формула
функция x = gauss_seidel ( A, b, x, iters ) для i = 1 : iters для j = 1 : размер ( A , 1 ) x ( j ) = ( b ( j ) - сумма ( A ( j , :) . * x ) + A ( j , j ) * x ( j )) / A ( j , j ); конец конецконец