Реферат «Введение в численные методы»
Тема: «Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ»
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
уменьшаются
медленнее. В
литературе
описываются
модифицированные
методы сопряженных
градиентов,
которые тем
или иным способом
включают в
итерационный
процесс подобные
(конгруэнтные
– для комплексных
матриц) преобразования,
предварительно
уменьшающие
меру обусловленности.
Литература
Бахвалов И.В. Численные методы. БИНОМ, 2008. – 636c.
Волков Е.А. Численные методы. Изд-во ЛАНЬ, 2004. – 256.
Демидович Б.П., ред., Марон И.А., Шувалова Э.З. Численные методы анализа. Издательство ЛАНЬ, 2008.
Пантелеев А.В., Киреев В.И., Пантелеев В.И., Киреев А.В. Численные методы в примерах и задачах. М: Высшая школа, 2004. – 480c.
Пирумов У.Г., Пирумов О.Г. Численные методы. Изд-во: ДРОФА, 2004. – 224c.