Итерационные методы решения СЛАУ

Алгоритмы   8 марта 2012  Автор статьи:  

Все методы решения систем линейных алгебраических уравнений делятся на два класса: прямые (точные) и итерационные. В данной статье мы подробно рассмотрим второй из этих классов, а именно итерационные методы решения СЛАУ.


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

Рассмотрим систему линейных алгебраических уравнений следующего вида:

СЛАУ

Или она же в матричной форме:

СЛАУ в матричном виде

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

Метод Якоби (метод простой итерации)

Данный метод решения систем линейных алгебраических уравнений был предложен немецким математиком Карлом Якоби (1804 — 1851). Итерационный процесс в этом методе имеет вид:

\LARGE\limits x_{i}^{(k)}=\frac{b_i-\sum_{j=1}^{i-1}a_{ij}x_{j}^{(k-1)}-\sum_{j=i+1}^{n}a_{ij}x_{j}^{(k-1)}}{a_{ii}} где i=\overline{1,n} — номер неизвестной, а k=1,2,... — номер итерации алгоритма.

Если рассмотреть систему, приведенную выше, то легко заметить, что формулу итерационного процесса можно получить переносом в i-ой строке i-ой переменной влево, а всех остальных слагаемых вправо. Из формулы видно, что значение i-ой неизвестной на k-ой итерации вычисляется через значения всех остальных переменных на итерации с номером k-1 с помощью столбца свободных членов (b_i) и элементов матрицы (a_{ij}). Приближением на 0-ой итерации удобно выбрать нулевой вектор (x^{(0)})=(0, 0, ..., 0).

Очевидно в формуле итерационного процесса необязательно разбивать правую часть на 2 суммы, а именно можно просто производить суммирование по всем j \not= i. Тем не менее, такая запись оказывается удобной при записи формул итерационного процесса для метода Зейделя.

Реализации алгоритма на различных языках программирования с комментариями можно найти по ссылкам ниже:

Метод Зейделя

Этот метод решения систем линейных алгебраических уравнений был предложен немецким математиком и астрономом Филлипом Людвигом Зейделем (1821 — 1896). Итерационный процесс в этом методе имеет вид:

\LARGE\limits x_{i}^{(k)}=\frac{b_i-\sum_{j=1}^{i-1}a_{ij}x_{j}^{(k)}-\sum_{j=i+1}^{n}a_{ij}x_{j}^{(k-1)}}{a_{ii}} где i=\overline{1,n} — номер неизвестной, а k=1,2,... — номер итерации алгоритма.

Итерационный процесс метода Зейделя отличается от итерационного процесса метода простой итерации тем, что на k-ой итерации вычисления i-ой неизвестной мы уже можем использовать только что посчитанные значения переменных x_{j}^{(k)} при j<i. Приближением на 0-ой итерации удобно выбрать нулевой вектор (x^{(0)})=(0, 0, ..., 0).

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

Реализации алгоритма на различных языках программирования с комментариями можно найти по ссылкам ниже:

Научиться программировать

  • на Delphi

  • на Java

  • на C++