Решение систем уравнений методом халецкого

Разложение матриц на треугольные множители. Схема Холецкого

Лекция 3. Метод Холецкого

Метод Гаусса, подробно рассмотренный выше, был и остается основным инструментом для решения систем линейных уравнений. Основным, но не единственным. Нам следует получить представление еще о двух группах методов: 1) методы разложения матрицы на треугольные множители; 2) итерационные методы.

Рассмотрим метод Холецкого, который предназначен для решения систем с симметричными положительно определенными матрицами. Почему нас интересуют именно такие матрицы?

Во-первых, как известно, матрица жесткости (см (1.1)) является симметричной матрицей.

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

, (3.1)

где q – вектор перемещений конструкции, а K – ее матрица жесткости.

Аналогично, для кинетической энергии системы получено

, (3.2)

где M – матрица инерции.

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

Теорема Холецкого. Если A – симметричная положительно определенная матрица, то существует действительная невырожденная нижняя треугольная матрица L такая, что , т.е.

Согласно этой теореме мы можем заменить в исходной системе линейных уравнений матрицу на ее разложение:

. (4)

Если мы обозначим , то можем легко решить задачу в два этапа:

1) — определяем y;

2) — определяем x.

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

Остается только научиться строить матрицу L.

Вспомним определение произведения матриц: . Следовательно, элемент есть произведение i-й строки матрицы L на j-й столбец матрицы :

. (3.5)

Учтем симметричность матрицы A. Это значит, что мы можем ограничиться рассмотрением только элементов нижнего треугольника матрицы A :

. (3.6)

Теперь для получения удобных для использования формул полезно записать это выражение отдельно для поддиагональных и для диагональных элементов матрицы A:

(3.7)

Кстати, эти формулы позволяют понять, почему в теореме Холецкого содержится ограничение, которое требует положительной определенности матрицы . Если попытаться применить формулы (3.7) к матрице, не являющейся положительно определенной, то это приведет либо к получению отрицательного числа под знаком квадратного корня при вычислении , либо к некорректной операции деления на ноль при вычислении .

Пример. Найти по схеме Холецкого решение системы:

(3.8)

Матрица этой системы

(3.9)

в результате применения формул (3.7)

представляется в виде разложения , где

(3.10)

Теперь находим решение исходной системы путем решения двух треугольных систем:

1)

2)

Метод главных элементов.

Сумы 2006

Содержание

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

2. Точные методы решения СЛАУ

3. Практическая реализация метода Халецкого

3.1 Программа на языке Pascal

3.2 Решение в Excel

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

Введение

Существует несколько способов решения таких систем, которые в основном делятся на два типа: 1) точные методы, представляющие собой конечные алгоритмы для вычисления корней системы, 2) итерационные методы, позволяющие получать корни системы с заданной точностью путем сходящихся бесконечных процессов.

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

Пример системы линейных уравнений:

Или в матричном виде: ,

где матрица коэффициентов системы;

— вектор неизвестных; — вектор свободных членов.

Точные методы решения СЛАУ

Метод главных элементов.

Пусть дана система линейных алгебраических уравнений. Рассмотрим расширенную матрицу, состоящую из коэффициентов системы a[i,j] и свободных членов b[i]. Метод главных элементов — это обобщение метода исключения переменных (метода Гаусса). Обозначим матрицу, состоящую из коэффициентов при неизвестных и столбца свободных членов исходной системы за M.

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

Далее производим следующие преобразования: к каждой неглавной строке прибавим главную строку, умноженную на соответствующий множитель для этой строки. В результате мы получим матрицу, у которой q-й столбец состоит из нулей. Отбросим этот столбец и главную p-ю строку, получим новую матрицу с меньшим на единицу числом строк и столбцов. Над матрицей повторяем те же операции, после чего получаем матрицу и т.д. Таким образом, мы построим последовательность матриц

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

Заметим, что метод Гаусса является частным случаем, метода главных элементов, а схема метода Гаусса получается, если за главный элемент всегда выбирать левый верхний элемент соответствующей матрицы. Запрограммировать метод главных элементов непросто, поэтому чтобы уменьшить вычислительную погрешность, применяют метод Гаусса с выбором главного элемента. Необходимое условие применения метода главных элементов: определитель системы не равен нулю.