Все формулы РФ

Математика / Начала анализа

Метод Гаусса—Зейделя для системы линейных уравнений

Метод Гаусса—Зейделя решает Ax=b последовательными проходами: новая компонента сразу участвует в вычислении следующих. Это обычно ускоряет простую итерацию, но делает результат одного прохода зависимым от порядка переменных.

Опубликовано: Обновлено:

Математический анализАлгебраСтраницы с задачами и решениямиЕсть историческая справкаЧисленные методы

Формула

$$x_i^{(k+1)}=\frac{b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}}{a_{ii}}$$
Схема Зейдель: новая x сразу входит в расчёт y
Зейдель: новая x сразу входит в расчёт yЗейдель: новая x сразу входит в расчёт yСтарт: x = 0; y = 0Сначала x = (9−0)/4 = 2,25Затем y = (7−2,25)/3 = 1,583333Второй проход: (1,854167; 1,715278)

Сравнивайте приближение с точным решением и проверяйте невязку исходной системы.

Обозначения

$a_ij$
коэффициент i-й строки системы, зависит от модели
$x_j^(k+1)$
уже обновлённая компонента, единица x_j
$x_j^(k)$
ещё не обновлённая компонента, единица x_j
$b_i$
правая часть i-го уравнения, как у i-й строки

Условия применения

Нужны ненулевые диагональные элементы и фиксированный порядок строк. Строгая диагональная доминантность гарантирует сходимость; для симметричных положительно определённых матриц она также обеспечивается. Стартовый вектор и критерий остановки задают до расчёта. Невязку целесообразно считать после полного прохода, когда сформирован согласованный вектор.

Ограничения

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

Подробное объяснение

Проход Гаусса—Зейделя похож на правку черновика строка за строкой. Найдя x_1^(k+1), его не откладывают до следующего прохода, а тут же подставляют во вторую строку. Так каждая последующая строка использует более свежую информацию. Это главная разница с методом Якоби, а не косметическая смена индексов.

Если A=D+L+U, где L содержит элементы ниже диагонали, итерация записывается (D+L)x^(k+1)=b−Ux^(k). На каждом проходе фактически решается нижнетреугольная система прямой подстановкой. Поэтому один проход требует тех же строковых коэффициентов, но информация течёт в направлении выбранного обхода. Матрица итерации равна −(D+L)^(−1)U; её спектральный радиус определяет сходимость.

На двумерной системе преимущество легко увидеть: после вычисления первой компоненты вторая уже исправляется с учётом этой поправки. Но порядок является частью алгоритма. Обход сверху вниз и снизу вверх могут давать разные промежуточные векторы; на структурированных сетках используют окраску узлов, чтобы разделить независимые обновления.

Не путайте быстроту ранних шагов с математической гарантией. Контролируют невязку исходной системы и при необходимости относительный её масштаб. Если матрица удовлетворяет известному достаточному условию, это объясняет успех; если нет, опыт на одной правой части не становится доказательством для всех задач.

Как пользоваться формулой

  1. Зафиксируйте порядок неизвестных и убедитесь, что на диагонали нет нулей, после чего выберите начальное приближение.
  2. В первой строке вычислите новую компоненту и немедленно запишите её поверх старого значения в рабочем векторе.
  3. Для строки i подставляйте новые значения с индексом меньше i и старые значения с индексом больше i.
  4. По завершении полного прохода вычислите невязку Ax−b и продолжайте, пока её норма не станет меньше допуска.

Историческая справка

Метод носит имена Карла Фридриха Гаусса и Филиппа Людвига фон Зейделя. В современной классификации Netlib Templates его выделяют среди стационарных итераций по правилу немедленно использовать новые компоненты. Это отличает последовательный проход от одновременного обновления Якоби и от прямого исключения неизвестных.

В вычислительной практике XX века большие разреженные системы сделали привлекательными схемы с небольшим расходом памяти. Проход Гаусса—Зейделя можно выполнять в одном рабочем векторе, сохраняя коэффициенты исходной системы. Вместе с этим проявляется последовательная зависимость строк: новое значение должно быть доступно следующей строке. Современная теория связывает сходимость со спектральным радиусом матрицы итерации и выделяет достаточные условия для диагонально доминирующих и симметричных положительно определённых систем. Методы для разреженных матриц используют такой проход также как компонент более сложного решателя.

Историческая линия формулы

Историческое название объединяет имена Гаусса и Зейделя. В современной классификации последовательное использование свежих компонентов определяет алгоритм точнее самого эпонима. Матричная форма через нижнетреугольную часть описывает один полный проход, а критерий сходимости относится к его повторению.

Пример

Возьмём 4x+y=9, x+3y=7 и x^(0)=(0,0). В первом проходе x^(1)=(9−0)/4=2,25. Сразу используем его: y^(1)=(7−2,25)/3=1,583333. Во втором проходе x^(2)=(9−1,583333)/4=1,854167, затем y^(2)=(7−1,854167)/3=1,715278. Точное решение (1,818182;1,727273) уже ближе, чем после второго шага Якоби. Для x^(2) невязка r=b−Ax равна (9−4·1,854167−1,715278;7−1,854167−3·1,715278)≈(−0,131944;0) с округлением точных дробей, поскольку вторая строка на каждом проходе удовлетворяется относительно текущего x. Норма этой невязки ещё задаёт понятную причину не останавливаться: округлённые компоненты сами по себе не являются критерием точности.

Частая ошибка

Нельзя сначала посчитать все компоненты из старого вектора и назвать это методом Гаусса—Зейделя: это Якоби. Не пересчитывайте y с обновлённым x, а затем повторно пересчитывайте x в рамках того же прохода без явного нового правила. Не меняйте порядок строк между проходами случайно: тогда меняется итерационная матрица. Не принимайте нулевую вторую компоненту невязки в примере за решение всей системы — первая строка ещё имеет остаток.

Практика

Задачи с решением

Один проход

Условие. Для 2x+y=5, x+4y=6 и (0,0) выполните один проход сверху вниз.

Решение. x=(5−0)/2=2,5; затем y=(6−2,5)/4=0,875.

Ответ. (2,5; 0,875).

Какое значение подставлять

Условие. При вычислении x_3 нового прохода какие x_1 и x_2 использует стандартный обход?

Решение. Индексы 1 и 2 уже рассчитаны в этом проходе, поэтому берутся новые значения.

Ответ. x_1^(k+1) и x_2^(k+1).

Дополнительные источники

  • https://www.netlib.org/templates/templates.html
  • https://fncbook.com/linear-systems/
  • https://fncbook.com/structure/

Связанные формулы

Математика

Прямой ход метода Гаусса

$R_i\leftarrow R_i-\frac{a_{ik}}{a_{kk}}R_k$

Прямой ход метода Гаусса зануляет коэффициенты под ведущими элементами. В результате система приводится к ступенчатому виду, из которого решение находят обратной подстановкой.

Математика

Обратная подстановка в методе Гаусса

$x_i=\frac{b'_i-\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}}$

Обратная подстановка находит неизвестные после прямого хода метода Гаусса. Она идет снизу вверх по ступенчатой системе: сначала последняя ведущая переменная, затем предыдущие.

Математика

Метод Гаусса-Жордана

$\left[A\mid b\right]\sim\left[I\mid x\right]$

Метод Гаусса-Жордана продолжает метод Гаусса до приведенного ступенчатого вида. Если система имеет единственное решение, расширенная матрица превращается в [I|x], и ответ читается сразу.

Математика

Число обусловленности для задачи МНК

$\kappa_2(A^\top A)=\frac{\sigma_{\max}^2}{\sigma_{\min}^2}=\kappa_2(A)^2.$

При переходе к нормальным уравнениям число обусловленности фактически возводится в квадрат, поэтому ошибки округления и шум в данных могут заметно усилиться.