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

1. Методы предварительных эквивалентных преобразований
1.1 Преобразование вращения
Следующий важный подход к решению алгебраических систем уравнений базируется на применении эквивалентных преобразований с помощью унитарных матриц, сводящем исходную матрицу к эквивалентной ей диагональной.
Смысл этого подхода состоит в том, чтобы последовательно, умножением слева и / или справа на специальные унитарные матрицы, превратить некоторые компоненты исходной матрицы в нуль.
Матрица S называется унитарной, если ее произведение со своей комплексно сопряженной равно единичной матрице. Это означает, что комплексно сопряженная матрица равна обратной матрице:

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

Чтобы сохранить эквивалентность результирующей матрицы при умножении ее на матрицу вращения, необходимо исходную матрицу умножать справа на  и слева на . Умножение же матрицы вращения на вектор дает такой же по величине вектор, но повернутый на заданный угол.
Поворот вектора в многомерном пространстве на произвольный угол можно представить, как последовательность плоских вращений каждой проекции на некоторый угол. Если подобрать угол вращения так, чтобы в плоском повороте одну из проекций вектора совместить с координатной осью, то вторая проекция в этой плоскости становится равной нулю.
Частные повороты вектора в многомерном пространстве с помощью матрицы вращения можно выполнять, если ее расширить до матрицы размера  следующим образом:
.
Индексы i, j обозначают матрицу вращения, поворачивающую вектор в плоскости  на угол .
Теперь частное эквивалентное преобразование матрицы A вращением на угол  записываются так:
.
Условие превращения в нуль ij-тых элементов симметричной матрицы A можно получить методом неопределенных коэффициентов на двумерной матрице:
.
.

Угол поворота, при котором , находится из уравнения
.
Разделив на  и обозначив , , получим квадратное уравнение для тангенса требуемого угла поворота
.
Из двух решений для тангенса выбирается такое, чтобы . В этом случае . Подставив выражение для угла в соотношения для диагональных элементов, после тригонометрических преобразований получаются следующие формулы:

Для получения результирующей матрицы выполнять матричное умножение трех матриц совсем необязательно. Структура матриц вращения вызывает при умножениях изменение только тех элементов исходной матрицы, которые находятся на i-той и j-той строчках и на i-том и j-том столбцах. Изменения представляются суммами элементов, стоящих в строчках и столбцах, умноженных на синус или косинус угла  в соответствии с формулами, где j>i:
преобразования строк – ;
преобразование столбцов – .
На пересечениях i-й строки и i-того столбца и j-й строки и j-того столбца располагаются соответственно вычисленные выше  и , а на местах ij-того и ji-того элементов вставляются нули.
Для приведения к диагональной матрице необходимо выполнить  таких элементарных преобразований.
1.2 Ортогональные преобразования отражением
Следующей важной унитарной матрицей, с помощью которой в различных алгоритмах выполняются ортогональные преобразования, являются матрицы отражения. Использование этого инструмента позволяет, например, последовательными эквивалентными преобразова-ниями свести исходную матрицу к верхней треугольной (QR-алгоритмы), трех или двух диагональным и т.д.
Смысл этого подхода состоит в том, чтобы умножением матрицы A слева на специально подобранную унитарную матрицу  один из столбцов исходной матрицы (например, ) преобразовать в вектор, параллельный единичному координатному вектору  ( или ). Тогда, последовательно подбирая нужные унитарные матрицы  и соответствующие единичные векторы , после n циклов эквивалентных преобразований можно будет получить верхнюю треугольную матрицу:


При выборе в качестве начального вектора  и умножениях матрицы A на ортогональные матрицы справа в конечном счете можно получить нижнюю треугольную матрицу.
Весь вопрос состоит в том, как формировать унитарную матрицу с заданными свойствами из векторов  и столбцов  матрицы A.
Из аналитической геометрии известно, что любые векторы, лежащие в плоскости, взаимно перпендикулярны с ее нормалью, т.е. их проекции на нормаль равны нулю. Последнее эквивалентно равенству нулю скалярных произведений.
Чтобы (k+1) – мерный векторный треугольник  сделать параллельным k-мерной гиперплоскости с нормалью n (вектор единичной длины, перпендикулярный плоскости), необходимо приравнять нулю скалярное произведение: (n, y)=0.
Пусть вектор z не параллелен плоскости, заданной своей нормалью, тогда его проекции на эту плоскость и нормаль соответственно будут представлены векторами  и . Вектор z и вектор зеркально-симметричный ему  через эти проекции можно выразить так:

Разрешив первое относительно  и подставив его в , получим


Проекцию вектора  можно заменить скалярным произведением (n, z) и подставить в выражение для , выразив тем самым зеркально отраженный вектор через исходный вектор и нормаль гиперплоскости:

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

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

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


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

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


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




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

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

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


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

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

2.2 Метод сопряженных направлений
Среди методов, связанных с выбором направления существуют методы, в которых к векторам направлений предъявляются требования их взаимной сопряженности , т.е. матрица A преобразует вектор  в вектор, ортогональный вектору . Доказано, что выбор направлений из множества сопряженных позволяет при любом начальном  свести задачу к точному решению не более, чем за n шагов, если матрица симметричная и положительно определенная ( ) размера .
Классическим набором сопряженных векторов являются собственные векторы матрицы ( ). Однако задача их определения сложнее решения заданной системы уравнений. Не менее сложна и задача построения произвольной системы ортогональных векторов.
В то же время примером ортогональных направлений являются направления вектора градиента и нормали в заданной точке некоторой гиперповерхности. Такая поверхность выше была представлена функционалом в виде скалярного произведения вектора невязки и вектора x, которая и определяла направление спуска по направлению градиента. Если, используя такой же подход к вычислению , в выражении для последнего вектор невязок дополнительно модифицировать, как показано ниже, то рекуррентно вычисляемые очередные направления окажутся сопряженными:

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

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

Литература
1.   Бахвалов И.В. Численные методы. БИНОМ, 2008. – 636c.
2.   Волков Е.А. Численные методы. Изд-во ЛАНЬ, 2004. – 256.
3.   Демидович Б.П., ред., Марон И.А., Шувалова Э.З. Численные методы анализа. Издательство ЛАНЬ, 2008.
4.   Пантелеев А.В., Киреев В.И., Пантелеев В.И., Киреев А.В. Численные методы в примерах и задачах. М: Высшая школа, 2004. – 480c.
5.   Пирумов У.Г., Пирумов О.Г. Численные методы. Изд-во: ДРОФА, 2004. – 224c.