Теорема об lu разложении

Введем обозначения: - угловой минор порядка j матрицы А, т.е.

Теорема. Пусть все угловые миноры матрицы А не равны нулю (Δj0 для j= ). Тогда матрицу А можно представить единственным образом в виде произведения А=L*U.

Идея доказательства. Рассмотрим матрицу А второго порядка и будем искать разложение этой матрицы в виде L и U.

.

Сопоставляя эти два равенства, определяем элементы матриц L и U (перемножим и приравняем неизвестные). Система имеет единственное решение. Методом математической индукции сказанное можно обобщить для матрицы размерности mm.

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

1.1.3 Метод Гаусса с выбором главного элемента

Может оказаться так, что система (1.1) имеет единственное решение, хотя какой либо из миноров матрицы А равен нулю. Заранее неизвестно, что все угловые миноры матрицы А не равны нулю. Избежать этого можно с выбором главного элемента.

1. Выбор главного элемента по строке, т.е. производится перенумерация неизвестных системы.

ПРИМЕР. Пусть дана система второго порядка

при а₁₂> а₁₁, тогда на первом шаге вместо неизвестного х₁ исключают х₂:

.

К этой системе применяем первый шаг прямого хода метода Гаусса.

2. Выбор главного элемента по столбцу

Предположим, что а₂₁> а₁₁и переставим уравнения

и применяем первый шаг прямого хода метода Гаусса. Здесь имеет место перенумерация строк.

3. Поиск главного элемента по всей матрице заключается в совместном применении методов 1 и 2. Всё это приводит к уменьшению вычислительной погрешности.

1.1.4 Метод Холецкого (метод квадратных корней)

Пусть дана система

Ах=В , (1.11)

где матрица А - симметричная матрица. Тогда решение проводится в два этапа:

Симметричная матрица А представляется как произведение двух матриц

А = L * L^Т.

Рассмотрим метод квадратных корней на примере системы 4-го порядка:

.

Перемножаем матрицы в левой части разложения и сравниваем с элементами в левой части:

, , , , ,

, , .

Решаем последовательно две системы:

Ly=B,

L^Tx=у.

Особенности:

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

2) Возможно переполнение - если угловые элементы близки к нулю.

1.2 Итерационные методы решений систем алгебраических уравнений

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

Суть итерационных методов заключается в том, что решение х системы (1.1) находится как предел последовательности .

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

,

где n=n() – функция , - норма вектора.

Прямые методы рассчитаны для решения систем, если её порядок не больше 100, иначе используются итерационные методы.