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