Участник:Sergey.protserov/Метод Якоби решения СЛАУ: различия между версиями
(+= references) |
(+= 1.3, 1.4, 1.5) |
||
| Строка 49: | Строка 49: | ||
В качестве условия окончания итерационного процесса можно использовать условие <math>\left\lVert y^{n+1} - y^{n}\right\rVert \le \varepsilon</math>, где <math>\varepsilon</math> — заданная точность. Для оценки ошибки можно использовать невязку <math>Ay^{n+1} - f</math>. | В качестве условия окончания итерационного процесса можно использовать условие <math>\left\lVert y^{n+1} - y^{n}\right\rVert \le \varepsilon</math>, где <math>\varepsilon</math> — заданная точность. Для оценки ошибки можно использовать невязку <math>Ay^{n+1} - f</math>. | ||
| + | |||
| + | === Вычислительное ядро алгоритма === | ||
| + | Основное время работы алгоритма приходится на последовательные вычисления векторов <math>y^{n+1}</math> по формуле, приведённой в предыдущем пункте, при уже вычисленных в начале работы алгоритма матрице <math>D^{-1}\left(D-A\right)</math> и векторе <math>D^{-1}f</math>. | ||
| + | |||
| + | === Макроструктура алгоритма === | ||
| + | В описываемом алгоритме можно выделить следующие макрооперации: | ||
| + | # вычисление <math>D^{-1}</math> | ||
| + | # вычисление <math>D^{-1}\left(D-A\right)</math> | ||
| + | # вычисление <math>D^{-1}f</math> | ||
| + | # вычисление <math>y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f</math> | ||
| + | |||
| + | Макрооперации 1-3 выполняются единожды, и в силу того, что матрица <math>D</math> — диагональная, занимают лишь незначительную часть времени работы алгоритма. | ||
| + | |||
| + | Макрооперация 4 выполняется многократно до наступления сходимости, поэтому она составляет вычислительное ядро алгоритма. | ||
| + | |||
| + | === Схема реализации последовательного алгоритма === | ||
| + | # составить диагональную матрицу <math>D</math> | ||
| + | # вычислить <math>D^{-1}</math> | ||
| + | # вычислить <math>D^{-1}\left(D-A\right)</math> | ||
| + | # вычислить <math>D^{-1}f</math> | ||
| + | # выбрать начальное приближение <math>y_{0}</math> | ||
| + | # выбрать константу <math>\varepsilon</math> | ||
| + | # пока не выполнено условие <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>. | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия 15:29, 18 октября 2019
Содержание
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 Макроструктура алгоритма
В описываемом алгоритме можно выделить следующие макрооперации:
- вычисление [math]D^{-1}[/math]
- вычисление [math]D^{-1}\left(D-A\right)[/math]
- вычисление [math]D^{-1}f[/math]
- вычисление [math]y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f[/math]
Макрооперации 1-3 выполняются единожды, и в силу того, что матрица [math]D[/math] — диагональная, занимают лишь незначительную часть времени работы алгоритма.
Макрооперация 4 выполняется многократно до наступления сходимости, поэтому она составляет вычислительное ядро алгоритма.
1.5 Схема реализации последовательного алгоритма
- составить диагональную матрицу [math]D[/math]
- вычислить [math]D^{-1}[/math]
- вычислить [math]D^{-1}\left(D-A\right)[/math]
- вычислить [math]D^{-1}f[/math]
- выбрать начальное приближение [math]y_{0}[/math]
- выбрать константу [math]\varepsilon[/math]
- пока не выполнено условие [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].
