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

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

AX = f. (1)

Канонической формой итерационного метода решения системы (1) называется его запись в виде [19]

(2)

где – вещественная невырожденная матрица порядка , задающая тот или иной итерационный метод, - итерационный параметр.

Если B_к+1=E, где Е – единичная матрица, то итерационный метод (2) называется явным, в противном случае неявным.

Если и не зависят от номера итераций, то итерационный метод (2) называется стационарным, и нестационарным - в противном случае.

Рассмотрим метод скорейшего спуска.

Пусть имеем систему (1) с симметричной положительно определенной матрицей А.

Обозначим через

(3)

невязку, которая получается при подстановке приближенного значения X^(k), полученного на k -й итерации, в уравнение (1).

Рассмотрим явный нестационарный итерационный метод [20]

. (4)

Перепишем метод (4) с учетом равенства (3), имеем

. (5)

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

.

Величина будет минимальной, если положить

.

Величина неизвестна, так как неизвестно точное решение . Однако надо учесть, что погрешность и невязка связаны равенством , следовательно, вычисление можно проводить по формуле

. (6)

Таким образом, в методе скорейшего спуска переход от k -ой итерации к (k+1)- ой осуществляется следующим образом: по найденному значению вычисляется вектор невязки (3) и по формуле (6) находится параметр , затем по формуле (5) вычисляется вектор приближенного решения . Вектор начального приближения выбирается произвольно.

Для погрешности метода скорейшего спуска справедлива оценка [19].

где .

Пример 1. Методом скорейшего спуска решить систему линейных алгебраических уравнений AX = f, где

, .

Решение:

Выберем начальное приближение .

Рассчитаем вектор невязки по формуле .

Получим .

Вычислим ,

Приближение вычислим по формуле: , имеем .

Вычислим вектор невязки по формуле , получим .

Продолжаем итерации. Имеем ,

Приближение находим по формуле: , получим .

Найдем вектор невязки по формуле , имеем .

Вычислим ,

Приближение вычислим по формуле: , получим .

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

Пример 2. В рамках метода скорейшего спуска реализовать нахождение скалярного произведения векторов.

Данный метод описан в классе «Vector». Реализация на языке программирования С++ может иметь следующий вид:

double Vector:: mul(Vector r) {

double result = 0;

for (int i=0; i< this.getColCount; i++)

{

result += this.elements[i] * r.elements[i];

}

return result;

}

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