Связь метода Гаусса с разложением матрицы на множители. Теорема об LU разложении
Государственное образовательное учреждение
Высшего профессионального образования
Поволжский государственный университет
Телекоммуникаций и информатики
Кафедра Программное обеспечение и управление в технических системах
ЗАДАНИЯ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ
К контрольной работе по дисциплине
«ЧИСЛЕННЫЕ МЕТОДЫ»
Для студентов заочной формы обучения
САМАРА, 2012 Г.
СОДЕРЖАНИЕ
1.Теоретическая часть 3
1.1 Точные методы 3
1.1.1 Метод Гаусса 3
1.1.2 Связь метода Гаусса с разложением матрицы на множители. Теорема об LU разложении. 6
1.1.3 Метод Гаусса с выбором главного элемента 8
1.1.4 Метод Холецкого (метод квадратных корней) 9
2. Практическая часть 10
2.1 Задание на контрольную работу 10
2.2 Варианты заданий 10
2.3 Пример решения задачи 13
2.4 Требования к оформлению контрольной работы 22
Список использованной литературы 24
Теоретическая часть
Решение систем линейных алгебраических уравнений
Рассмотрим систему линейных алгебраических уравнений:
(1.1)
или в матричной форме:
Aх=b, (1.2)
где: A={aij} квадратная матрица размерности (m´m,); х=(х1,…., хm)T; T – операция транспонирования; b=(b1,….,bm)T; detA¹0.
Предположим, что определитель матрицы A не равен нулю. Тогда решение х существует и единственно. На практике встречаются системы, имеющие большой порядок.Методы решения системы (1.1) делятся на две группы:
1) прямые (точные методы);
2) итерационные методы (приближенные).
Точные методы
В точных методах решение х находится за конечное число действий, но из-за погрешности округления и их накопления прямые методы можно назвать точными, только отвлекаясь от погрешностей округления.
Метод Гаусса
Вычисления с помощью метода Гаусса (который называют также методом последовательного исключения неизвестных) состоят из двух основных этапов: прямого хода и обратного хода. Прямой ход метода заключается в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с треугольной матрицей. На этапе обратного хода производят вычисления значений неизвестных. Рассмотрим простейший вариант метода Гаусса, называемый схемой единственного деления.
Прямой ход метода
1-й шаг. Предположим, что а11¹0. Поделим первое уравнение на этот элемент, который назовем ведущим элементом первого шага :
. (1.3)
Остальные уравнения системы (1.1) запишем в виде
, (1.4)
где i= .
Уравнение (1.3) умножаем на ai1 и вычитаем из i-го уравнения системы (1.4). Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого.
Получим эквивалентную систему вида:
. (1.5)
,
где i,j= . Система (1.5) имеет матрицу вида:
.
Дальше работаем с укороченной системой, т.к. х1 входит только в 1-ое уравнение
.
2-й шаг. На этом шаге исключаем неизвестное х2 из уравнений с номерами i=3,4,…,m. Если ведущий элемент второго шага , то из укороченной системы аналогично исключаем неизвестное x2 и получаем матрицу коэффициентов такого вида:
.
Аналогично повторяем указанные действия для неизвестных х3,х4,...,хm-1и приходим к системе :
. (1.6)
Эта система с верхней треугольной матрицей:
.
Обратный ход метода. Из последнего уравнения системы (1.6) находим хm, из предпоследнего хm-1, ..., из первого уравнения – х1.
Общая формула для вычислений:
xm=ym/cmm,
, (i=m-1,…,1).
Для реализации метода Гаусса требуется примерно (1/3)m3 арифметических операций, причем большинство из них приходится на прямой ход.
Ограничение метода единственного деления заключается в том, что ведущие элементы на k-ом шаге исключения не равны нулю, т.е. ≠0.
Но если ведущий элемент близок к нулю, то в процессе вычисления может накапливаться погрешность. В этом случае на каждом шаге исключают не хk, a хj (при j¹k). Такой подход называется методом выбора главного элемента. Для этого выбирают неизвестные xj с наибольшим по абсолютной величине коэффициентом либо в строке, либо в столбце, либо во всей матрице. Для его реализации требуется − арифметических действий.
Связь метода Гаусса с разложением матрицы на множители. Теорема об LU разложении.
Пусть дана система Aх=b (1.1), которая при прямом ходе преобразуется в эквивалентную систему (1.6) и запишем ее в виде
Cх=y, (1.6*)
где С – верхняя треугольная матрица с единицами на главной диагонали, полученная из (1.6) делением последнего уравнения системы на сmm.
Как связаны в системе (1.1) элементы bи элементы yиз (1.6*)?
Если внимательно посмотреть на прямой ход метода Гаусса, то можно увидеть, что
.
Для произвольного j имеем
, (1.7)
где j= , dji – числовые коэффициенты:
. (1.8)
Можно записать систему:
b=Dy,
где D−нижняя треугольная матрица с элементами на главной диагонали (j= , ).
В связи с тем, что в методе Гаусса угловые коэффициенты не равны нулю , то на главной диагонали матрицы D стоят не нулевые элементы. Следовательно, эта матрица имеет обратную, тогда y=D-1b, Сx= D-1b.
Тогда
D´Cx=b. (1.9)
В результате использования метода Гаусса, получили разложение матрицы А на произведение двух матриц
A = D´C,
где D − нижняя треугольная матрица, у которой элементы на главной диагонали не равны нулю, а C – верхняя треугольная матрица с единичной диагональю.
Таким образом, если задана матрица A и вектор b, то в методе Гаусса сначала производится разложение этой матрицы А на произведение D и C, а затем последовательно решаются две системы:
Dy=b,
Cx=y. (1.10)
Из последней системы находят искомый вектор x. При этом разложение матрицы А на произведение СD – есть прямой ход метода Гаусса, а решение систем (1.10) обратный ход. Обозначим нижнюю треугольную матрицу через L, верхнюю треугольную матрицу − U.
Теорема об LU разложении
Введем обозначения: − угловой минор порядка j матрицы А, т.е.
Теорема.Пусть все угловые миноры матрицы А не равны нулю (Δj¹0 для j= ). Тогда матрицу А можно представить единственным образом в виде произведения А=L*U.
Идея доказательства.Рассмотрим матрицу А второго порядка и будем искать разложение этой матрицы в виде L и U.
.
Сопоставляя эти два равенства, определяем элементы матриц L и U (перемножим и приравняем неизвестные). Система имеет единственное решение. Методом математической индукции сказанное можно обобщить для матрицы размерности m´m.
Следствие. Метод Гаусса (схему единственного деления) можно применять только в том случае, когда угловые миноры матрицы А не равны нулю.