Универсальные разреженные методы (стр. 2 )

1.4 Прямые методы

Еще одним большим семейством методов решения СЛАУ являются прямые методы. Их основное отличие от итерационных – они позволяют за конечное количество шагов найти точное решение системы линейных алгебраических уравнений. Если вычисления выполняются с абсолютной точностью, то решение тоже будет найдено точно. Конечно, реальная вычислительная система работает с некоторой погрешностью, поэтому нельзя утверждать, что прямые методы позволяют найти абсолютно точное решение на ЭВМ.

1.4.1 Матричный метод

При использовании этого метода квадратная система

записывается в матричном виде

Основная идея метода заключается в матрице, обратной к A и умножении на нее обеих частей равенства слева. Тогда решение получится в виде

Условием применимости данного метода (как и вообще существования решения неоднородной системы линейных уравнений с числом уравнений, равным числу неизвестных) является невырожденность матрицы A. Необходимым и достаточным условием этого является неравенство нулю определителя матрицы A. Для однородной системы линейных уравнений, то есть когда вектор b = 0, действительно обратное правило: система

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

1.4.2 Метод гауссова исключения

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

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

Среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив ее на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

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

1.4.3 Метод Холецкого

Метод Холецкого, или так же известный как метод квадратных корней – это вариант гауссова исключения, адаптированных для симметричных положительно-определенных матриц.

Пусть ставится задача решения системы линейных алгебраических уравнений:

Здесь А – симметричная положительной определенная матрица коэффициентов размера , b – вектор, называемый правой частью, x – вектор, который необходимой найти.

Для решения такой системы методом Холецкого необходимо найти разложение матрицы системы

После того, как такой разложение найдено, система может быть переписана в виде

Если обозначить , то решение системы сводится к решению двух систем уравнений:

Первоначально может показаться, что сведение системы к решению двух систем – не самый оптимальный путь. Однако, стоит помнить, что множитель Холецкого – это диагональная матрица, и решение диагональной системы можно производить достаточно эффективно[Ващенко].

ГЛАВА 2. Применение метода Холецкого для решения СЛАУ

2.1 Положительно-определенные и неопределенные матричные задачи

Как было сказано выше, будут рассматриваться исключительно задачи решения систем линейных уравнений, в которых матрица системы является симметричной, разреженной и положительно-определенной. В противном случае, появляется проблемы выбора главного элемента, то есть необходимость перестановки строк и столбцов. То есть матрица системы претерпевает преобразование вида

В этом случае Q и P являются матрицами перестановок соответствующих размеров. Умножение слева на Q переставляет строки матрицы A, справа на P – столбцы.

Стоит отметить, что зачастую не представляется возможности заранее найти необходимые перестановки, так как они производятся в процессе вычисления, исходя из соображений компромисса между численной устойчивостью и разреженностью.

В нашем же случае, данные перестановки можно вычислить заранее. Это поможет более качественно и эффективно производить вычисления и хранить операнды в памяти компьютера.

2.2 Разложение Холецкого

Разложение Холецкого – это представление симметричной положительно-определённой матрицы A в виде

где L — нижняя треугольная матрица со строго положительными элементами на диагонали. Такую матрицу будем называть множителем Холецкого.

Предложение. Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.

Доказательство.

Существование. Будем доказывать существование разложения по индукции. В качестве базиса индукции можно взять такой тривиальный случай, как положительное число, которое представим в виде матрицы. Далее, предположим, что предложение верно для матрицы размером . Докажем, что оно верно и для матрицы порядка N. Такую матрицу можно представить в следующем блочном виде.

Здесь d – скаляр, v­ – вектор, – матрица порядка . Такую матрицу можно переписать в виде произведения

В данном разложении , – единичная матрица размера N-1. Ясно, что H – симметричная, так как A так же является симметричной. Так же она является положительной определенной. Действительно для любого произвольного x,

Отсюда >0.

По предположению индукции, H имеет разложение Холецкого Причем диагональ у треугольного множителя положительная. Поэтому матрица A может быть разложена в произведение

Единственность[Гулин]

2.3 Метод внешних произведений

Доказательство существования разложения Холецкого в своем составе предлагает алгоритм нахождения разложения Холецкого. Такой алгоритм называется методом внешних произведений. Его можно шаг за шагом записать в виде матричных формул:

Далее

Продолжая, можно убедиться, что . Следует отметить, что в такой цепочке для всех i от 1 до N – положительный скаляр (так как все угловые миноры положительной-определенной матрицы положительны), – вектор длины N-i, – положительно определенная симметричная матрицы порядка N-i. Пройдя все шаги до N, получим