Реферат: Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ

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

2. Итерационные методы с минимизацией невязки

2. 1 Ускорение сходимости итерационных методов

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

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

Процедуры ускорения связаны с построением очередного вектора по одному или нескольким его значениям на предыдущих итерационных циклах. Фактически речь идет о построении на каждом шаге итераций интерполирующей функции с векторным аргументом, по которой вычисляют очередной вектор для подстановки. Для вычисления вектора на (k+ 1) – ом шаге итераций необходимо сначала получить величину и единичный вектор направления и просуммировать предыдущий вектор с добавочным вектором:

.

Подстановка последнего в уравнение () образует вектор из покомпонентных невязок. Для задания структурной взаимосвязи каждой невязки с соответствующей компонентой вектора и образования функционала (скалярной функции от вектора невязок) возмем скалярное произведение вектора невязки на вектор-строку :

.

После подстановки очередного вектора функционал получит новое значение, которое будет зависеть от некоторого скаляра :

.

Чтобы невязки на каждом шаге итераций становились меньше, желательно соответствующим образом выбирать . Найдем такое значение , при котором . Для этого приравняем производную по нулю. Индекс номера итерации пока опустим.

Из последнего равенства для (k+ 1) – й итерации величина шага в направлении вектора должна быть вычислена так:

.

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

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

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

Среди методов, связанных с выбором направления существуют методы, в которых к векторам направлений предъявляются требования их взаимной сопряженности , т.е. матрица A преобразует вектор в вектор, ортогональный вектору . Доказано, что выбор направлений из множества сопряженных позволяет при любом начальном свести задачу к точному решению не более, чем за n шагов, если матрица симметричная и положительно определенная () размера .

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

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

Выбрав в начале итераций и , после выполнения приведенных вычислений в (n- 1) цикле будут получены векторы направлений, удовлетворяющие соотношениям

,

а векторы невязок будут ортогональными:

.

Относительно метода сопряженных градиентов доказывается, что, если матрица (положительно определенная и симметричная) имеет только m (m<n ) различных собственных значений, то итерационный процесс сходится не более, чем за m итераций. Однако в практической реализации скорость сходимости существенно зависит от величины меры обусловленности и в итерационном процессе может быть оценена согласно неравенству: