Метод Якоби

Метод Якоби — это итерационный алгоритм для решения систем линейных алгебраических уравнений вида \(Ax = b\), основанный на приведении матрицы к диагонально-преобладающему виду и последовательном уточнении компонент вектора неизвестных. Относится к классу методов простой итерации (методов последовательных приближений) и применяется для систем, где матрица \(A\) имеет строгое диагональное преобладание или является симметричной и положительно определённой. Метод назван в честь немецкого математика Карла Густава Якоба Якоби, который предложил его в 1845 году.

История

Метод Якоби был впервые опубликован в 1845 году в работе Карла Густава Якоби «Об одном новом методе решения систем линейных уравнений». Первоначально алгоритм предназначался для решения систем, возникающих при анализе электрических цепей и механических конструкций. В XIX веке метод не получил широкого распространения из-за трудоёмкости ручных вычислений, однако с развитием вычислительной техники в середине XX века он стал одним из базовых итерационных методов в численном анализе.

В 1950-е годы метод Якоби был формализован в контексте теории матриц и функционального анализа, что позволило доказать его сходимость для определённых классов матриц. В современной вычислительной математике метод Якоби используется как основа для более эффективных алгоритмов, таких как метод Гаусса — Зейделя и метод последовательной верхней релаксации (SOR).

Алгоритм

Постановка задачи

Дана система линейных уравнений: \[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1, \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2, \\ \dots \\ a_{n1}x_1 + a_{n2}x_2 + \dots + a_{nn}x_n = b_n, \end{cases} \] где \(A = (a_{ij})\) — квадратная матрица коэффициентов, \(x = (x_1, x_2, \dots, x_n)^T\) — вектор неизвестных, \(b = (b_1, b_2, \dots, b_n)^T\) — вектор правых частей.

Итерационная формула

Метод Якоби предполагает, что диагональные элементы матрицы \(a_{ii} \neq 0\) для всех \(i\). Каждое уравнение разрешается относительно соответствующей диагональной переменной: \[ x_i = \frac{1}{a_{ii}} \left( b_i - \sum_{j \neq i} a_{ij} x_j \right), \quad i = 1, 2, \dots, n. \]

Итерационный процесс строится следующим образом: на \((k+1)\)-й итерации новое значение \(x_i^{(k+1)}\) вычисляется с использованием значений \(x_j^{(k)}\) с предыдущей итерации: \[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k)} - \sum_{j=i+1}^{n} a_{ij} x_j^{(k)} \right), \quad i = 1, 2, \dots, n. \]

В матричной форме метод Якоби записывается как: \[ x^{(k+1)} = D^{-1} (b - (L + U) x^{(k)}), \] где \(D\) — диагональная матрица, составленная из элементов \(a_{ii}\), \(L\) — строго нижняя треугольная часть матрицы \(A\) (с нулевой диагональю), \(U\) — строго верхняя треугольная часть (с нулевой диагональю). Таким образом, \(A = D + L + U\).

Начальное приближение и критерий остановки

В качестве начального приближения \(x^{(0)}\) обычно выбирается нулевой вектор или вектор, состоящий из компонент \(b_i / a_{ii}\). Итерации продолжаются до выполнения условия: \[ \| x^{(k+1)} - x^{(k)} \| < \varepsilon, \] где \(\varepsilon\) — заданная точность, а \(\| \cdot \|\) — какая-либо норма (чаще всего евклидова или бесконечная). Альтернативно используется критерий по невязке: \(\| Ax^{(k)} - b \| < \varepsilon\).

Сходимость

Условия сходимости

Метод Якоби сходится к точному решению системы при любом начальном приближении, если матрица \(A\) удовлетворяет одному из следующих условий:

1. Строгое диагональное преобладание: для каждой строки матрицы модуль диагонального элемента больше суммы модулей всех внедиагональных элементов в этой строке:

\[ |a_{ii}| > \sum_{j \neq i} |a_{ij}|, \quad i = 1, 2, \dots, n. \]

1. Симметричность и положительная определённость: если \(A\) — симметричная положительно определённая матрица, метод Якоби сходится.

Скорость сходимости

Скорость сходимости метода Якоби линейна и определяется спектральным радиусом итерационной матрицы \(B = D^{-1}(L + U)\). Чем меньше спектральный радиус \(\rho(B)\), тем быстрее сходимость. Для систем с сильным диагональным преобладанием сходимость может быть быстрой, но для плохо обусловленных систем (например, с малыми диагональными элементами) метод может сходиться очень медленно или расходиться.

Пример

Рассмотрим систему: \[ \begin{cases} 4x_1 + x_2 = 9, \\ x_1 + 3x_2 = 7. \end{cases} \]

Матрица \(A\) имеет строгое диагональное преобладание (\(|4| > |1|\), \(|3| > |1|\)). Итерационная формула: \[ x_1^{(k+1)} = \frac{1}{4} (9 - x_2^{(k)}), \quad x_2^{(k+1)} = \frac{1}{3} (7 - x_1^{(k)}). \]

Начальное приближение: \(x^{(0)} = (0, 0)^T\). Первая итерация: \[ x_1^{(1)} = \frac{9}{4} = 2.25, \quad x_2^{(1)} = \frac{7}{3} \approx 2.333. \]

Вторая итерация: \[ x_1^{(2)} = \frac{1}{4} (9 - 2.333) \approx 1.667, \quad x_2^{(2)} = \frac{1}{3} (7 - 2.25) \approx 1.583. \]

Продолжая итерации, последовательность сходится к точному решению \(x = (2, 2)^T\).

Сравнение с другими методами

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

Метод Гаусса — Зейделя является модификацией метода Якоби, в которой при вычислении \(x_i^{(k+1)}\) используются уже обновлённые значения \(x_j^{(k+1)}\) для \(j < i\). Это обычно ускоряет сходимость, но не гарантирует её для всех матриц, где сходится метод Якоби. Метод Гаусса — Зейделя также требует меньше памяти, так как обновления выполняются «на месте».

Метод последовательной верхней релаксации (SOR)

Метод SOR вводит параметр релаксации \(\omega\) для ускорения сходимости. При \(\omega = 1\) он сводится к методу Гаусса — Зейделя. При оптимальном выборе \(\omega\) (обычно \(1 < \omega < 2\)) сходимость может быть значительно быстрее, чем у метода Якоби.

Прямые методы

Прямые методы (например, метод Гаусса) дают точное решение за конечное число операций, но требуют \(O(n^3)\) операций для плотных матриц. Итерационные методы, включая метод Якоби, предпочтительны для разреженных систем большой размерности (например, в задачах математической физики), где прямые методы становятся неэффективными из-за заполнения матрицы.

Применение

Метод Якоби применяется в следующих областях:

• Численное решение дифференциальных уравнений в частных производных: при дискретизации уравнений теплопроводности, диффузии, гидродинамики методом конечных разностей или конечных элементов возникают системы большой размерности с разреженными матрицами.
• Обработка изображений: в задачах реставрации изображений и фильтрации шума метод Якоби используется для решения систем, возникающих при минимизации энергетических функционалов.
• Экономическое моделирование: при анализе межотраслевых балансов (модель Леонтьева) и решении систем линейных уравнений, описывающих равновесные состояния.
• Электротехника: при расчёте цепей постоянного и переменного тока методом узловых потенциалов.

Реализация

Псевдокод

``` Вход: матрица A[n][n], вектор b[n], точность eps, максимальное число итераций max_iter Выход: вектор x[n] (приближённое решение)

x = [0, 0, ..., 0] // начальное приближение for k = 1 to max_iter: x_new = [0, 0, ..., 0] for i = 1 to n: sum = 0 for j = 1 to n: if j != i: sum += A[i][j] * x[j] x_new[i] = (b[i] - sum) / A[i][i] if norm(x_new - x) < eps: return x_new x = x_new return x // если не сошлось за max_iter итераций ```

Пример на Python

```python import numpy as np

def jacobi(A, b, eps=1e-6, max_iter=1000): n = len(b) x = np.zeros(n) for _ in range(max_iter): x_new = np.zeros(n) for i in range(n): s = sum(A[i][j] * x[j] for j in range(n) if j != i) x_new[i] = (b[i] - s) / A[i][i] if np.linalg.norm(x_new - x) < eps: return x_new x = x_new return x ```

Критика и ограничения

Основные недостатки метода Якоби:

• Медленная сходимость для систем без сильного диагонального преобладания. Для многих практических задач требуется большое число итераций.
• Необходимость диагонального преобладания для гарантированной сходимости. Если матрица не удовлетворяет этому условию, метод может расходиться.
• Параллельная реализация, хотя и возможна, требует синхронизации на каждой итерации, что снижает эффективность на некоторых архитектурах.

Интересные факты

• Метод Якоби является частным случаем метода Ричардсона с параметром \(\tau = 1\).
• В некоторых источниках метод Якоби называют «методом одновременных смещений» (в отличие от метода Гаусса — Зейделя — «метода последовательных смещений»).
• Для симметричных положительно определённых матриц метод Якоби сходится, но может быть медленнее, чем метод сопряжённых градиентов.

Источники

• Jacobi, C. G. J. (1845). «Über eine neue Auflösungsart der bei der Methode der kleinsten Quadrate vorkommenden linearen Gleichungen». Astronomische Nachrichten.
• Saad, Y. (2003). «Iterative Methods for Sparse Linear Systems». 2nd ed. SIAM.
• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. (2008). «Численные методы». 6-е изд. БИНОМ. Лаборатория знаний.
• Тыртышников Е. Е. (2007). «Методы численного анализа». Академия.