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

Итерационный метод, используемый для решения линейной системы уравнений

В числовой линейной алгебре метод Гаусса –Зейделя , также известный как метод Либмана или метод последовательного смещения , является итеративным методом, используемым для решения системы линейных уравнений . Он назван в честь немецких математиков Карла Фридриха Гаусса и Филиппа Людвига фон Зейделя . Хотя его можно применять к любой матрице с ненулевыми элементами на диагоналях, сходимость гарантируется только в том случае, если матрица либо строго диагонально доминирующая , ^[1] либо симметричная и положительно определенная . Он был упомянут только в частном письме Гаусса своему ученику Герлингу в 1823 году. ^[2] Публикация не была представлена ​​до 1874 года Зейделем. ^[3]

Описание

Пусть будет квадратной системой из n линейных уравнений, где: ${\textstyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

$${\displaystyle \mathbf {A} ={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.}$$

Когда и известны, а неизвестно, метод Гаусса–Зейделя может быть использован для итеративного приближения . Вектор обозначает начальное предположение для , часто для . Обозначим через -ое приближение или итерацию , а через приближение на следующей (или -ой) итерации. ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} ^{(0)}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} _{i}^{(0)}=0}$ ${\displaystyle i=1,2,...,n}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} ^{(k+1)}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle k+1}$

Формула на основе матрицы

Решение получается итеративно с помощью разложения матрицы на нижний треугольный компонент и строго верхний треугольный компонент , такой что . ^[4] Более конкретно, разложение на и задается формулой: $${\displaystyle \mathbf {L} \mathbf {x} ^{(k+1)}=\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)},}$$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {L} }$ ${\displaystyle \mathbf {U} }$ ${\displaystyle \mathbf {A} =\mathbf {L} +\mathbf {U} }$ ${\displaystyle A}$ ${\displaystyle L_{*}}$ ${\displaystyle U}$

$${\displaystyle \mathbf {A} =\underbrace {\begin{bmatrix}a_{11}&0&\cdots &0\\a_{21}&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}} _{\textstyle \mathbf {L} }+\underbrace {\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}} _{\textstyle \mathbf {U} }.}$$

Почему работает матричная формула

Систему линейных уравнений можно переписать как:

${\displaystyle {\begin{alignedat}{1}\mathbf {A} \mathbf {x} &=\mathbf {b} \\(\mathbf {L} +\mathbf {U} )\mathbf {x} &=\mathbf {b} \\\mathbf {L} \mathbf {x} +\mathbf {U} \mathbf {x} &=\mathbf {b} \\\mathbf {L} \mathbf {x} &=\mathbf {b} -\mathbf {U} \mathbf {x} \end{alignedat}}}$

Метод Гаусса–Зейделя теперь решает левую часть этого выражения для , используя предыдущее значение для в правой части. Аналитически это можно записать как ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} }$ $${\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {L} ^{-1}\left(\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)}\right).}$$

Формула на основе элементов

Однако, используя преимущество треугольной формы , элементы можно вычислить последовательно для каждой строки, используя прямую подстановку : ^[5] ${\displaystyle \mathbf {L} }$ ${\displaystyle \mathbf {x} ^{(k+1)}}$ ${\displaystyle i}$ $${\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\dots ,n.}$$

Обратите внимание, что формула использует два суммирования на итерацию, которые можно выразить как одно суммирование , использующее последнюю вычисленную итерацию . Процедура обычно продолжается до тех пор, пока изменения, внесенные итерацией, не станут ниже некоторого допуска, например, достаточно малого остатка . ${\displaystyle \sum _{j\neq i}a_{ij}x_{j}}$ ${\displaystyle x_{j}}$

Обсуждение

Поэлементная формула для метода Гаусса–Зейделя похожа на формулу (итеративного) метода Якоби , но с важным отличием:

В методе Гаусса-Зейделя вычисление использует элементы , которые уже были вычислены, и только элементы , которые не были вычислены в -й итерации. Это означает, что, в отличие от метода Якоби, требуется только один вектор хранения, поскольку элементы могут быть перезаписаны по мере их вычисления, что может быть выгодно для очень больших задач. ${\displaystyle \mathbf {x} ^{(k+1)}}$ ${\displaystyle \mathbf {x} ^{(k+1)}}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle (k+1)}$

Однако, в отличие от метода Якоби, вычисления для каждого элемента, как правило, гораздо сложнее реализовать параллельно , поскольку они могут иметь очень длинный критический путь , и, таким образом, наиболее осуществимы для разреженных матриц . Кроме того, значения на каждой итерации зависят от порядка исходных уравнений.

Гаусс-Зейдель — это то же самое, что и последовательная сверхрелаксация с . ${\displaystyle \omega =1}$

Конвергенция

Свойства сходимости метода Гаусса–Зейделя зависят от матрицы . А именно, известно, что процедура сходится, если: ${\displaystyle \mathbf {A} }$

• ${\displaystyle \mathbf {A} }$симметричен и положительно определен , ^[6] или
• ${\displaystyle \mathbf {A} }$является строго или нередуцируемо диагонально доминирующим . ^[7]

Метод Гаусса–Зейделя может сходиться, даже если эти условия не выполняются.

Голуб и Ван Лоан приводят теорему для алгоритма, который разбивается на две части. Предположим, что является невырожденным. Пусть будет спектральным радиусом . Тогда итерации, определенные с помощью , сходятся к для любого начального вектора, если является невырожденным и . ^[8] ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {A} =\mathbf {M} -\mathbf {N} }$ ${\displaystyle r=\rho (\mathbf {M} ^{-1}\mathbf {N} )}$ ${\displaystyle \mathbf {M} ^{-1}\mathbf {N} }$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle \mathbf {M} \mathbf {x} ^{(k+1)}=\mathbf {N} \mathbf {x} ^{(k)}+\mathbf {b} }$ ${\displaystyle \mathbf {x} =\mathbf {A} ^{-1}\mathbf {b} }$ ${\displaystyle \mathbf {x} ^{(0)}}$ ${\displaystyle \mathbf {M} }$ ${\displaystyle r<1}$

Алгоритм

Поскольку элементы могут быть перезаписаны по мере их вычисления в этом алгоритме, требуется только один вектор хранения, а индексация векторов опускается. Алгоритм выглядит следующим образом:

Алгоритм метода Гаусса–Зейделя : входы  :  A , b  , выход:  φ Выбрать начальное предположение φ для решения  повторить до сходимости для  i  от 1 до  n  сделать  σ ← 0  для  j  от 1 до  n  сделать  если  j ≠ i  то  σ ← σ + a ij φ j  конец если  конец ( j -цикл) φ i ← ( b i − σ ) / a ii  конец ( i -цикл) проверить, достигнута ли сходимость конец (повторить)

Примеры

Пример для матричной версии

Линейная система, показанная как, задается формулой: ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$ $${\displaystyle \mathbf {A} ={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {b} ={\begin{bmatrix}11\\13\end{bmatrix}}.}$$

Используйте уравнение в форме, где: $${\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {L} ^{-1}(\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)})}$$ $${\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {T} \mathbf {x} ^{(k)}+\mathbf {c} }$$

${\displaystyle \mathbf {T} =-\mathbf {L} ^{-1}\mathbf {U} \quad {\text{and}}\quad \mathbf {c} =\mathbf {L} ^{-1}\mathbf {b} .}$

Разложим на сумму нижнего треугольного компонента и строго верхнего треугольного компонента : ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {L} }$ ${\displaystyle U}$ $${\displaystyle \mathbf {L} ={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {U} ={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.}$$

Обратное значение : ${\displaystyle \mathbf {L} }$ $${\displaystyle \mathbf {L} ^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}.}$$

Теперь найдите: $${\displaystyle {\begin{aligned}\mathbf {T} &=-{\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\end{bmatrix}}={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1194\end{bmatrix}},\\[1ex]\mathbf {c} &={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}11\\13\end{bmatrix}}={\begin{bmatrix}0.6875\\-0.7439\end{bmatrix}}.\end{aligned}}}$$

С помощью и векторы можно получить итеративно. ${\displaystyle \mathbf {T} }$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {x} }$

Прежде всего, выберите , например Чем ближе предположение к окончательному решению, тем меньше итераций потребуется алгоритму. ${\displaystyle \mathbf {x} ^{(0)}}$ $${\displaystyle \mathbf {x} ^{(0)}={\begin{bmatrix}1.0\\1.0\end{bmatrix}}.}$$

Затем рассчитайте: $${\displaystyle {\begin{aligned}\mathbf {x} ^{(1)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}1.0\\1.0\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.5000\\-0.8636\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(2)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.5000\\-0.8636\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8494\\-0.6413\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(3)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8494\\-0.6413\\\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8077\\-0.6678\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(4)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8077\\-0.6678\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8127\\-0.6646\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(5)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8127\\-0.6646\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8121\\-0.6650\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(6)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8121\\-0.6650\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(7)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.\end{aligned}}}$$

Как и ожидалось, алгоритм сходится к решению: . $${\displaystyle \mathbf {x} =\mathbf {A} ^{-1}\mathbf {b} \approx {\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}}$$

На самом деле матрица A строго диагонально доминирующая, но не положительно определенная.

Еще один пример для матричной версии

Другая линейная система, показанная как, имеет вид: ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

$${\displaystyle \mathbf {A} ={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {b} ={\begin{bmatrix}11\\13\\\end{bmatrix}}.}$$

Используйте уравнение в форме, где: $${\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {L} ^{-1}(\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)})}$$ $${\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {T} \mathbf {x} ^{(k)}+\mathbf {c} }$$

${\displaystyle \mathbf {T} =-\mathbf {L} ^{-1}\mathbf {U} \quad {\text{and}}\quad \mathbf {c} =\mathbf {L} ^{-1}\mathbf {b} .}$

Разложим на сумму нижнего треугольного компонента и строго верхнего треугольного компонента : ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {L} }$ ${\displaystyle \mathbf {U} }$ $${\displaystyle \mathbf {L} ={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {U} ={\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}.}$$

Обратное значение : ${\displaystyle \mathbf {L} }$ $${\displaystyle \mathbf {L} ^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}.}$$

Теперь найдите: $${\displaystyle {\begin{aligned}\mathbf {T} &=-{\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}={\begin{bmatrix}0.000&-1.500\\0.000&1.071\\\end{bmatrix}},\\[1ex]\mathbf {c} &={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}.\end{aligned}}}$$

С помощью и векторы можно получить итеративно. ${\displaystyle \mathbf {T} }$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {x} }$

Прежде всего, нам нужно выбрать , например ${\displaystyle \mathbf {x} ^{(0)}}$ $${\displaystyle \mathbf {x} ^{(0)}={\begin{bmatrix}1.1\\2.3\end{bmatrix}}}$$

Затем рассчитайте: $${\displaystyle {\begin{aligned}\mathbf {x} ^{(1)}&={\begin{bmatrix}0&-1.500\\0&1.071\\\end{bmatrix}}{\begin{bmatrix}1.1\\2.3\\\end{bmatrix}}+{\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}={\begin{bmatrix}2.050\\0.393\\\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(2)}&={\begin{bmatrix}0&-1.500\\0&1.071\\\end{bmatrix}}{\begin{bmatrix}2.050\\0.393\\\end{bmatrix}}+{\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}={\begin{bmatrix}4.911\\-1.651\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(3)}&=\cdots .\end{aligned}}}$$

В тесте на сходимость мы обнаруживаем, что алгоритм расходится. Фактически, матрица не является ни диагонально доминирующей, ни положительно определенной. Тогда сходимость к точному решению не гарантируется и, в этом случае, не произойдет. ${\displaystyle \mathbf {A} }$ $${\displaystyle \mathbf {x} =\mathbf {A} ^{-1}\mathbf {b} ={\begin{bmatrix}-38\\29\end{bmatrix}}}$$

Пример для версии уравнения

Предположим, что даны уравнения и начальная точка . На любом шаге итерации Гаусса-Зейделя решите первое уравнение для в терминах ; затем решите второе уравнение для в терминах только что найденного и оставшегося ; и продолжите до . Затем повторяйте итерации до тех пор, пока не будет достигнута сходимость, или прервитесь, если расхождение в решениях начнет выходить за пределы предопределенного уровня. ${\displaystyle n}$ ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2},\dots ,x_{n}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{3},\dots ,x_{n}}$ ${\displaystyle x_{n}}$

Рассмотрим пример: $${\displaystyle {\begin{array}{rrrrl}10x_{1}&-x_{2}&+2x_{3}&&=6,\\-x_{1}&+11x_{2}&-x_{3}&+3x_{4}&=25,\\2x_{1}&-x_{2}&+10x_{3}&-x_{4}&=-11,\\&3x_{2}&-x_{3}&+8x_{4}&=15.\end{array}}}$$

Решая и получаем: ${\displaystyle x_{1},x_{2},x_{3}}$ ${\displaystyle x_{4}}$ $${\displaystyle {\begin{aligned}x_{1}&=x_{2}/10-x_{3}/5+3/5,\\x_{2}&=x_{1}/11+x_{3}/11-3x_{4}/11+25/11,\\x_{3}&=-x_{1}/5+x_{2}/10+x_{4}/10-11/10,\\x_{4}&=-3x_{2}/8+x_{3}/8+15/8.\end{aligned}}}$$

Предположим, что (0, 0, 0, 0) — начальное приближение, тогда первое приближенное решение имеет вид: $${\displaystyle {\begin{aligned}x_{1}&=3/5=0.6,\\x_{2}&=(3/5)/11+25/11=3/55+25/11=2.3272,\\x_{3}&=-(3/5)/5+(2.3272)/10-11/10=-3/25+0.23272-1.1=-0.9873,\\x_{4}&=-3(2.3272)/8+(-0.9873)/8+15/8=0.8789.\end{aligned}}}$$

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

Точное решение системы: (1, 2, −1, 1) .

Пример использования Python и NumPy

Следующая итерационная процедура создает вектор решения линейной системы уравнений:

импортировать  numpy  как  npПРЕДЕЛ_ИТЕРАЦИИ  =  1000# инициализируем матрицу A  =  np . array (  [  [ 10.0 ,  - 1.0 ,  2.0 ,  0.0 ],  [ - 1.0 ,  11.0 ,  - 1.0 ,  3.0 ],  [ 2.0 ,  - 1.0 ,  10.0 ,  - 1.0 ],  [ 0.0 ,  3.0 ,  - 1.0 ,  8.0 ],  ] ) # инициализируем вектор RHS b  =  np . array ( [ 6.0 ,  25.0 ,  - 11.0 ,  15.0 ])print ( " Система уравнений:" ) для  i  в  диапазоне ( A.shape [ 0 ]): row = [ f " { A [ i , j ] : 3g } *x { j + 1 } " для j в диапазоне ( A.shape [ 1 ] ) ] print ( "[ {0} ] = [ {1:3g} ]" .format ( " +" .join ( row ) , b [ i ] ))         x  =  np.zeros_like ( b , np.float_ ) для it_count в диапазоне ( 1 , ITERATION_LIMIT ) : x_new = np.zeros_like ( x , dtype = np.float_ ) print ( f " Итерация { it_count } : { x } " ) для i в диапазоне ( A.shape [ 0 ] ) : s1 = np.dot ( A [ i , : i ] , x_new [ : i ] ) s2 = np.dot ( 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 ( f "Решение: { x } " ) error  =  np . dot ( A ,  x )  -  b print ( f "Ошибка: { error } " )

Производит вывод:

Система уравнений: [ 10*x1 + -1*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] Итерация 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

Следующий код использует формулу $${\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\quad {\begin{array}{l}i=1,2,\ldots ,n\\k=0,1,2,\ldots \end{array}}}$$

функция  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 ); конец, конец , конец                     

Смотрите также

• Метод сопряженных градиентов
• Распространение гауссовского убеждения
• Итерационный метод: линейные системы
• Метод Качмажа («строчно-ориентированный» метод, тогда как Гаусс-Зейдель — «столбцово-ориентированный». См., например, эту статью.)
• Матричное расщепление
• итерация Ричардсона

Примечания

1. Зауэр, Тимоти (2006). Числовой анализ (2-е изд.). Pearson Education, Inc. стр. 109. ISBN 978-0-321-78367-7.
2. Гаусс 1903, стр. 279; прямая ссылка.
3. Зайдель, Людвиг (1874). «Über ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate führt, sowie lineäre Gleichungen überhaupt, durch последовательный Annäherung aufzulösen» [О процессе решения последовательным приближением уравнений, к которым приводит метод наименьших квадратов, а также линейных уравнения в целом]. Abhandlungen der Mathematish-Physikalischen Klasse der Königlich Bayerischen Akademie der Wissenschaften (на немецком языке). 11 (3): 81–108.
4. Голуб и Ван Лоан 1996, с. 511.
5. Голуб и Ван Лоан 1996, уравнение (10.1.3)
6. Голуб и Ван Лоан 1996, Thm 10.1.2.
7. Bagnara, Roberto (март 1995 г.). «Единое доказательство сходимости методов Якоби и Гаусса-Зейделя». SIAM Review . 37 (1): 93–97. CiteSeerX 10.1.1.26.5207 . doi :10.1137/1037008. JSTOR  2132758. 
8. Голуб и Ван Лоан 1996, Thm 10.1.2

Ссылки

• Гаусс, Карл Фридрих (1903), Werke (на немецком языке), том. 9, Геттинген: Köninglichen Gesellschaft der Wissenschaften.
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Джонс Хопкинс, ISBN 978-0-8018-5414-9.
• Блэк, Ноэль и Мур, Ширли. «Метод Гаусса-Зейделя». MathWorld .

В данной статье использован текст из статьи Gauss-Seidel_method на CFD-Wiki, которая распространяется по лицензии GFDL .

Внешние ссылки

• «Метод Зейделя», Энциклопедия математики , EMS Press , 2001 [1994]
• Гаусс–Зейдель с www.math-linux.com
• Гаусс-Зейдель из Института целостных численных методов
• Итерация Гаусса Зиделя с сайта www.geocities.com
• Метод Гаусса-Зейделя
• Биксон
• Код Matlab
• Пример кода на языке С