Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ (стр. 2 из 3)

Выражение для зеркально отраженного вектора позволяет представить нормальный вектор в виде линейной функции от задаваемого вектора z:

Число

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

Выбрав

для комплексных матриц или – для действительных матриц, будем иметь

Такое нормирование не нарушает коллинеарности отраженного и единичного векторов:

Рассмотрим пример воздействия ортогонального преобразования на матрицу

.

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

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

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

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

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

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

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

.

Подстановка последнего в уравнение (

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

.

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

:

.

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

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

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

в направлении вектора

должна быть вычислена так:

.

Если единичные векторы направления последовательно выбирать равными координатным, т.е.

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

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

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

Среди методов, связанных с выбором направления существуют методы, в которых к векторам направлений предъявляются требования их взаимной сопряженности

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

Классическим набором сопряженных векторов являются собственные векторы матрицы (

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

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

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

Выбрав в начале итераций

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

,

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

.