Участник:Sergey.protserov/Метод Якоби решения СЛАУ

Материал из Алговики
Перейти к навигации Перейти к поиску

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Метод Якоби -- одношаговый стационарный итерационный метод решения СЛАУ вида [math]Ay = f[/math], где [math] A = \left( \begin{array}{ccc} a_{11} & \dots & a_{1m} \\ \vdots & \ddots & \vdots \\ a_{m1} & \dots & a_{mm} \\ \end{array} \right) [/math], [math] f = \left( \begin{array}{c} f_{1} \\ \vdots \\ f_{m} \\ \end{array} \right) [/math], [math] y = \left( \begin{array}{c} y_{1} \\ \vdots \\ y_{m} \\ \end{array} \right) [/math], [math]\det A \ne 0[/math].

Каноническая форма одношагового стационарного итерационного метода имеет вид [1]: [math] B\frac{y^{n+1} - y^{n}}{\tau} + Ay^{n} = f, \quad n = 0,\,1,\,\dots\,, [/math]

где [math]B[/math] — невырожденная матрица [math]m \times m[/math], [math]\tau \in \mathbb{R}[/math], [math]y^{0}[/math] — заданное начальное приближение. Решение исходной СЛАУ находится приближённо посредством последовательных итераций. На [math]n[/math]-ом шаге находится [math]y^{n+1}[/math] — очередное приближение для искомого решения [math]y[/math].

В методе Якоби [math]\tau = 1[/math], [math]B = D[/math], где [math]D[/math] — диагональная матрица, элементы которой совпадают с элементами, стоящими на главной диагонали матрицы [math]A[/math].

Достаточным условием сходимости метода является свойство строгого диагонального преобладания у матрицы [math]A[/math]. [2]

1.2 Математическое описание алгоритма

В обозначениях предыдущего пункта выражение для [math]y^{n+1}[/math] через [math]y^{n}[/math]: [math]y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f[/math].

В поэлементной записи:

[math]y^{n+1}_{i} = \frac{1}{a_{ii}}\left(f_{i} - \sum_{j=1,\,j \ne i}^{m}a_{ij}y^{n}_{j}\right),\quad i = 1,\,\dots,\,m[/math].

В качестве условия окончания итерационного процесса можно использовать условие [math]\left\lVert y^{n+1} - y^{n}\right\rVert \le \varepsilon[/math], где [math]\varepsilon[/math] — заданная точность. Для оценки ошибки можно использовать невязку [math]Ay^{n+1} - f[/math].

1.3 Вычислительное ядро алгоритма

Основное время работы алгоритма приходится на последовательные вычисления векторов [math]y^{n+1}[/math] по формуле, приведённой в предыдущем пункте, при уже вычисленных в начале работы алгоритма матрице [math]D^{-1}\left(D-A\right)[/math] и векторе [math]D^{-1}f[/math].

1.4 Макроструктура алгоритма

В описываемом алгоритме можно выделить следующие макрооперации:

  1. вычисление [math]D^{-1}[/math]
  2. вычисление [math]D^{-1}\left(D-A\right)[/math]
  3. вычисление [math]D^{-1}f[/math]
  4. вычисление [math]y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f[/math]

Макрооперации 1-3 выполняются единожды, и в силу того, что матрица [math]D[/math] — диагональная, занимают лишь незначительную часть времени работы алгоритма.

Макрооперация 4 выполняется многократно до наступления сходимости, поэтому она составляет вычислительное ядро алгоритма.

1.5 Схема реализации последовательного алгоритма

  1. составить диагональную матрицу [math]D[/math]
  2. вычислить [math]D^{-1}[/math]
  3. вычислить [math]D^{-1}\left(D-A\right)[/math]
  4. вычислить [math]D^{-1}f[/math]
  5. выбрать начальное приближение [math]y_{0}[/math]
  6. выбрать константу [math]\varepsilon[/math]
  7. пока не выполнено условие [math]\left\lVert y^{n+1} - y^{n}\right\rVert \le \varepsilon[/math], выполнять вычисления по формуле [math]y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f[/math], [math]n = 0,\,1,\,\dots[/math]

При этом на [math]n[/math]-ом шаге итераций необходимо хранить оба вектора [math]y^{n}[/math], [math]y^{n+1}[/math].

2 Литература

  1. ↑ Абакумов М. В., Гулин А.В. Лекции по численным методам математической физики. - Москва: ИНФРА-М, 2013. - 61 с.
  2. ↑ Bagnara, Roberto. (2001). A Unified Proof For The Convergence Of Jacobi And Gauss-Seidel Methods. SIAM Review. 37. 10.1137/1037008.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Sergey.protserov/Метод_Якоби_решения_СЛАУ&oldid=27464