Итерационные методы решения систем линейных алгебраических уравнений

 

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

1) процесс итераций может оказаться расходящимся для данной системы;

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

Пусть дана система линейных алгебраических уравнений

                               (7.6.36)

с неособенной матрицей . Точное решение системы  является пределом последовательности векторов , которые строятся по рекуррентным формулам:

    (7.6.37)

или

,              (7.6.38)

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

Итерационные процессы, протекающие по формулам (7.6.37) и (7.6.38), обладают тем свойством, что для каждого из них точное решение  является неподвижной точкой. Это значит, что если за начальное приближение  взято , то все последующие приближения будут также равны .

Простейшими среди итерационных процессов являются стационарные, в которых матрицы в (7.6.37) и (7.6.38) не зависят от номера шага .

 

Метод последовательных приближений

Под процессом последовательных приближений понимается следующий итерационный процесс. Система уравнений (7.6.36) записывается в виде:

где ,  – единичная матрица соответствующего порядка, , и последовательные приближения вычисляются по формуле:

.                       (7.6.39)

Сходимость метода последовательных приближений определяется следующими теоремами.

Теорема . Для сходимости метода последовательных приближений (7.6.39) необходимо и достаточно, чтобы все собственные значения матрицы  были по модулю меньше единицы.

Теорема . Для сходимости метода последовательных приближений достаточно, чтобы какая-либо норма матрицы  была меньше единицы.

Таким образом, для сходимости метода последовательных приближений достаточно, чтобы выполнялось одно из условий:

,

где  – элементы матрицы .

 

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

Запишем систему (7.6.36) в развернутом виде:

    (7.6.40)

Поделив каждое уравнение этой системы на соответствующий диагональный элемент, получим систему:

      (7.6.41)

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

,                     (7.6.42)

где

, .

Преобразование исходной системы (7.6.40) в систему (7.6.42) равносильно матричному преобразованию:

,                 (7.6.43)

где  – диагональная матрица, на диагонали которой находятся элементы  матрицы  и

.

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

  (7.6.44)

были по модулю меньше единицы.

Достаточным условием сходимости является выполнение одного из условий:

 

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

Пусть система (7.6.36) представлена в виде:

                       (7.6.45)

где , .

Одношаговый циклический процесс, называемый методом Зейделя, отличается от процесса последовательных приближений тем, что при вычислении k-го приближения для i-ой компоненты учитываются вычисленные ранее k-е приближения для компонент . Таким образом, вычисления ведутся по формулам:

.   (7.6.46)

Представим систему (7.6.45) в матричном виде:

                   (7.6.47)

где

Тогда итерационное правило (7.6.46) можно представить в матричной форме в виде:

             (7.6.48)

или

(7.6.49)

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

были по модулю меньше единицы. Достаточное условие сходимости состоит в том, чтобы правая или вторая норма матрицы  были меньше единицы.

 

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: