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

Рассматривается система Ax = b. Для применения итерационных методов система должна быть приведена к эквивалентному виду x=Bx+d. Затем выбирается начальное приближение к решению системы уравнений и находится последовательность приближений к корню. Для сходимости итерационного процесса достаточно, чтобы было выполнено условие

.

Критерий окончания итераций зависит от применяемого итерационного метода.

Метод Якоби

Самый простой способ приведения системы к виду удобному для итерации состоит в следующем: из первого уравнения системы выразим неизвестное x₁, из второго уравнения системы выразим x₂, и т. д. В результате получим систему уравнений с матрицей, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

, i, j = 1, 2, ... n.

Компоненты вектора d вычисляются по формулам:

, i = 1, 2, ... n.

Расчетная формула метода простой итерации имеет вид:

,

или в покоординатной форме записи выглядит так:

, i = 1, 2, ... m.

Критерий окончания итераций в методе Якоби имеет вид:

, где .

Если , то можно применять более простой критерий: окончания итераций

ПРИМЕР 1. Решение системы линейных уравнений методом Якоби.

Пусть дана система уравнений:

Требуется найти решение системы с точностью

Приведем систему к виду удобному для итерации: .

Выберем начальное приближение, например, - вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

, ,

Найдем норму матрицы . Будем использовать норму .

Так как сумма модулей элементов в каждой строке равна 0.2, то = 0.2 < 1/2, поэтому критерий окончания итераций в этой задаче .

Вычислим нормы разностей векторов: , .

Так как , заданная точность достигнута на четвертой итерации.

Ответ: x ₁ = 1.102, x ₂ = 0.991, x ₃ = 1.101

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

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1)-го приближения к неизвестному x_i при i >1 используют уже найденные (n+1)-е приближения к неизвестным x₁, x₂, ..., x_{i - 1}, а не n-ое приближение, как в методе Якоби. Расчетная формула метода в покоординатной форме записи выглядит так:

,

i = 1, 2, ... m.. Условия сходимости и критерий окончания итераций можно взять такими же как в методе Якоби.

ПРИМЕР 2. Решение систем линейных уравнений методом Зейделя.

Рассмотрим параллельно решение 3-х систем уравнений:

, , .

Приведем системы к виду удобному для итераций:

, , .

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

1-ая система. , , ,

Точное решение здесь x ₁ = 1.4, x ₂ = 0.2. Итерационный процесс сходится.

2-ая система. , , , - итерационный процесс разошелся.

Точное решение x ₁ = 1, x ₂ = 0.2.

3-я система. , , , - итерационный процесс зациклился.

Точное решение x ₁ = 1, x ₁ = 2.

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

Метод простой итерации.

Если A - симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду: x = x - (Ax - b), - итерационный параметр.

Расчетная формула метода простой итерации в этом случае имеет вид: x ⁽ⁿ⁺¹⁾ = x ⁿ - (Ax ⁿ - b).

Здесь B = E - A и параметр > 0 выбирают так, чтобы по возможности сделать минимальной величину .

Пусть и - минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра . В этом случае принимает минимальное значение равное .

ПРИМЕР 3. Решение систем линейных уравнений методом простой итерации.

% Решить систему Ax=b методом простой итерации.

A = [3 -2 0; -2 3 0; 0 0 3];

b = [-21;24;15];

e = eig(A);

% Вычислим итерационный параметр

tau = 2 / (min(e) + max(e));

r = 1;

% Выполняем метод простой итерации с начальным приближением x0

x0 = [0;0;0];

y = x0;

while r > 100 * eps

x = y - tau * (A * y - b);

r = norm(x-y);

y = x;

end

% Проверим полученное значение

A * x – b

>>

ans =

1.0e-013 *

	-0.2842
0.2487

Задание для самостоятельной работы

1. Убедиться в том, что если A- нижняя треугольная матрица с ненулевыми диагональными элементами, то метод Зейделя сходится за одну итерацию.

2. Пусть A - верхняя треугольная матрица с ненулевыми диагональными элементами. Доказать, что метод Зейделя сходится за конечное число итераций и указать, за какое именно.

3. Вывести оценку числа итераций, требуемых для достижения заданной точности в методе Якоби.

Вопросы

1. Сформулируйте достаточное условие сходимости методов Якоби и метода Зейделя.

2. Сформулируйте критерий окончания итераций в методе Якоби.

3. Сформулируйте условия сходимости метода простой итерации и метода Зейделя для случая симметрических положительно определенных матриц.

4. Из каких условий выбирается итерационный параметр в методе простой итерации.

5. Сформулируйте алгоритм нахождения оптимального итерационного параметра в методе простой итерации.

Приближение функций

На практике часто возникает необходимость найти функциональную зависимость между величинами x и y, которые получены в результате эксперимента. Часто вид эмпирической зависимости известен, но числовые параметры неизвестны.

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