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

Рассмотрим метод простых итераций [19]. Имеем систему линейных алгебраических уравнений

(1)

или в матричном виде . (2)

Приведем систему (1) к эквивалентному виду

(3)

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

, (4)

где , , .

Такое приведение может быть выполнено различными способами.

Итерационную последовательность векторов

(5)

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

В качестве критерия сходимости метода простых итераций имеет место следующее утверждение [20]:

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

, (6)

так как , где - первая или вторая норма матрицы.

Таким образом выбор матрицы В для системы (5) метода простой итерации должен подчиняться требованиям сходимости и не может быть совсем произвольным.

Если матрица А имеет диагональное преобладание, т.е. ее элементы удовлетворяют неравенствам

(7)

то в качестве матрицы В можно задать матрицу с элементами

(8)

В этом случае систему (1) в эквивалентном виде (3) можно записать следующим образом:

(9)

т.е.

,

Описанная модификация метода простой итерации, связанная с делением уравнений на диагональные элементы матрицы системы, называется методом Якоби [10].

Если , то для метода простых итераций известна оценка погрешности [18]:

, (10)

где - точное решение.

Выход из итерационного процесса осуществляется по результатам выполнения неравенства

, (11)

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

. (12)

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

Решение:

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

Преобразуем эту систему к эквивалентному виду (5). Для этого выразим из первого уравнения , из второго , из третьего , получаем

Имеем

, .

Заметим, что ,следовательно, условие сходимости выполнено.

Зададим вектор начального приближения .

Выполним расчеты по формуле (6)

На первой итерации имеем систему

.

Условие окончания итерационного процесса не выполняется, значит продолжаем процесс. На второй итерации получаем систему

.

Условие окончания итерационного процесса не выполняется, продолжаем итерировать до требуемой точности.

На пятой итерации требуемая точность достигнута

.

Пример 2. Описать алгоритм метода простой итерации на языке программирования С++.

При описании алгоритма используются объекты и методы классов «SquareMatrix», «Vector».

void IterationMethods:: simpleIterationMethod(SquareMatrix A, Vector f, double tochnost){

/* Создание вспомогательной матрицы В, векторов g, x1 и вектора решений x */

SquareMatrix B = SquareMatrix(A.getRowCount());

Vector g = Vector(A.getColCount());

Vector x = Vector(A.getColCount());

Vector x1 = Vector(A.getColCount());

/* Получение канонического вида системы: X = BX + g, т.е. матрицы В и g */

for (int i = 0; i < A.getRowCount(); i++){

for (int j = 0; j < A.getColCount(); j++){

if (i == j){

B.setElement(i, j, 0);

}

if (i!= j){

B.setElement(i,j,-A.getElement(i,j)/A.getElement(i, i));

}

}

g.setElement(i, f.getElement(i)/A.getElement(i, i));

}

/* Построение итерационной последовательности и вычисление значения вектора на текущей итерации по формуле X(k+1) = BX(k) + g */

.................................................

/*Вывод вектора решений*/

}

Данный алгоритм основан на матричном представлении метода простой итерации. Однако можно обойтись без построения матрицы В и вектора g, воспользовавшись непосредственно формулами (10) для описания итерационного процесса. Это позволит сэкономить вычислительные ресурсы.

Поиск по сайту: