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

Реферат «

Введение

в численные методы"

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

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) различных собственных значений, то итерационный процесс сходится не более, чем за m итераций. Однако в практической реализации скорость сходимости существенно зависит от величины меры обусловленности и в итерационном процессе может быть оценена согласно неравенству:

где — коэффициент, степень которого на каждом шаге итерационного процесса показывает во сколько раз уменьшилось расстояние до вектора точного решения x*.

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

1. Бахвалов И. В. Численные методы. БИНОМ, 2008. — 636c.

2. Волков Е. А. Численные методы. Изд-во ЛАНЬ, 2004. — 256.

3. Демидович Б. П., ред., Марон И. А., Шувалова Э. З. Численные методы анализа. Издательство ЛАНЬ, 2008.

4. Пантелеев А. В., Киреев В. И., Пантелеев В. И., Киреев А. В. Численные методы в примерах и задачах. М: Высшая школа, 2004. — 480c.

5. Пирумов У. Г., Пирумов О. Г. Численные методы. Изд-во: ДРОФА, 2004. — 224c.