Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ
Реферат «Введение в численные методы»
Тема: «Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ»
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) – ом шаге
итераций необходимо
сначала получить
величину
и единичный
вектор направления
и просуммировать
предыдущий
вектор
с добавочным
вектором:
.
Подстановка
последнего
в уравнение
(
)
образует вектор
из покомпонентных
невязок. Для
задания структурной
взаимосвязи
каждой невязки
с соответствующей
компонентой
вектора
и образования
функционала
(скалярной
функции от
вектора невязок)
возмем скалярное
произведение
вектора невязки
на вектор-строку
:
.
После
подстановки
очередного
вектора функционал
получит новое
значение, которое
будет зависеть
от некоторого
скаляра