Лекция 2. Системы линейных алгебраических уравнений

ПРЯМЫЕ МЕТОДЫ.

ЦЕЛЬ ЛЕКЦИИ: Определить два класса численных методов (прямые и итерационные); показать, как строятся прямые методы Гаусса, LU-факторизации, Холесского; выполнить оценку их эффективности.

Постановка задачи.

Основная задача вычислительной алгебры — решение систем линейных алгебраических уравнений (СЛАУ).

В дальнейшем будем использовать запись этой системы в компактной форме:

(запись означает, что индекс i изменяется от 1 до n с шагом 1), или в векторном виде.

.

где Предполагается, что матрица неособенная, т. е., и решение единственно.

Прямые и итерационные методы.

Численные методы решения СЛАУ делятся на две большие группы: прямые и итерационные.

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

.

где k — номер итерации. В действительности итерационный процесс прекращается, как только становится достаточно близким к .

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

Какой класс методов лучше? Однозначно на этот вопрос ответить нельзя. Итерационные методы привлекательнее с точки зрения объема вычислений и требуемой памяти, когда решаются системы с матрицами высокой размерности. При небольших порядках системы используют прямые методы либо прямые методы в сочетании с итерационными методами.

Метод Гаусса.

В методе Гаусса линейная система решается в два этапа. На первом этапе система преобразуется к виду ,.

Рис. 2.1. Структура системы и портрет ее ненулевых элементов до (а) и после (б) прямого хода Гаусса

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

Прямой ход. Прямой ход Гаусса состоит из n шагов.

Первый шаг. Полагаем, что и разделим на него первое уравнение. Перепишем систему с учетом этого преобразования:

Умножим первое уравнение на и вычтем его из i-го уравнения преобразованной системы:

Обозначим.

.

Получим.

Второй шаг. На втором шаге из системы.

исключается аналогичным образом:

K-й шаг. Запишем общий вид преобразованной системы после k-го шага прямого хода Гаусса:

Здесь.

Проиллюстрируем, как меняется матрица системы в процессе прямого хода Гаусса на примере системы четвертого порядка.

Оценим количество длинных операций (умножений и делений) на первом шаге прямого хода Гаусса. Преобразование первого уравнения требует n таких операций. Преобразование остальных n-1 уравнений — n (n-1) операций умножения и деления. Таким образом, первый шаг выполняется за длинных операций. Рассуждая по аналогии, нетрудно найти затраты на остальных n-1 шагах. Суммарные затраты прямого хода Гаусса определяются в итоге рядом.

.

Последняя оценка имеет место для n>>1.

Обратный ход. Запишем систему, решаемую на обратном ходе, в координатном виде.

Ее решение:

Запись означает, что индекс k изменяется от значения n-1 до 1 с шагом 1.

Требуемое число длинных операций на обратном ходе.

Приближенная оценка справедлива для n>>1.

Общие затраты метода Гаусса:

Таким образом, при больших n основные затраты в методе Гаусса приходятся на прямой ход.

Метод LU-факторизации.

В методе LU-факторизации (эту схему называют компактной схемой Гаусса) при решении системы выполняется следующая последовательность действий.

Матрица представляется в виде произведения.

.

где L нижняя треугольная матрица, U верхняя треугольная матрица. Такое разложение единственно при условии предварительного выбора диагональных элементов одной из матриц. В этом случае число элементов в матрице A совпадает с суммарным числом неизвестных элементов матриц L и U. Если диагональ L принимается единичной, то такое разложение называют разложением Дулиттла если единична диагональ U — разложением.

Система заменяется системой.

.

легко решаемой за два шага:

Шаг 1.. Принимая во внимание треугольный вид матрицы L, нетрудно получить, что в алгоритме Краута.

Шаг 2.. Решение этой системы в алгоритме Краута:

.

Суммарные затраты реализации обоих шагов при n>>1 составляют длинных операций.

Получим соотношения для расчета элементов матриц L и U в алгоритме Краута. Для этого перемножим матрицы L и U и приравняем результат к A. По правилу перемножения матриц.

Учтем, что.

Рассмотрим элемент (рис. 2.4), расположенный на центральной диагонали либо в нижней треугольной части матрицы A. Для такого элемента i? j. Из рисунка следует, что Иллюстрация вычисления элемента матрицы, расположенного ниже главной диагонали.

.

так как i? j и. Отсюда.

Рассмотрим элемент (рис. 2.5), находящийся выше главной Иллюстрация вычисления элемента матрицы, расположенного выше главной диагонали диагонали матрицы A (для него j>i). В этом случае.

Следовательно,.

Получили в итоге соотношения, которые позволяют вычислять элементы матриц L и U. Последовательность вычислений: сначала вычисляется столбец матрицы L, далее строка матрицы U, затем опять столбец матрицы L, далее строка матрицы U и т. д. (см. рис. 2.6, который иллюстрирует последовательность вычислений и схему хранения матриц L и U).

Вычисление столбца матрицы L и строки матрицы U назовем шагом LU-разложения. Приведем в качестве примера схему хранения элементов матриц A,L,U после второго шага LU-разложения (рис. 2.7).

Число длинных арифметических операций на этапе LU-разложения при n>>1 составляет величину, на шаге решения ли;

нейных систем с треугольными матрицами —. Суммарное число длинных операций приближенно равно (как и в методе Гаусса),.

Рис. 2.6. Исходная матрица A (а), схема хранения L и U матриц (б), последовательность вычисления элементов в принятой схеме хранения (в)

Рис. 2.7 Схема хранения элементов 44 матриц A, L, U после второго шага LU-факторизации

т. е. основные затраты приходятся на LU-факторизацию матрицы A. Эта особенность делает особо привлекательным метод LU-факторизации при решении СЛАУ с одной и той же матрицей A, но разными правыми частями:

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

Метод Холесского.

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

Будем полагать, что решаемая система.

имеет симметрическую положительно определенную матрицу A. В этом случае матрица A представляется в виде.

Здесь — нижняя треугольная матрица. Такое разложение существует и единственно для положительно определенных симметрических матриц.

Система преобразуется к виду .

Вектор ищется путем последовательного решения двух систем с треугольными матрицами: ; .Для получения расчетных соотношений элементов матрицы рассмотрим произвольный элемент матрицы A:

Суммирование здесь выполняется только до j, т. к. j?i. Выделим член при значении k=j:

.

Теперь.