Связь метода Гаусса с разложением матрицы на множители. Теорема об 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 ={a_ij} квадратная матрица размерности (m´m,); х =(х ₁ ,…., х_m)^T; T – операция транспонирования; b =(b ₁ ,….,b_m)^T; det A ¹0.

Предположим, что определитель матрицы A не равен нулю. Тогда решение х существует и единственно. На практике встречаются системы, имеющие большой поря­док.Методы решения системы (1.1) делятся на две группы:

1) прямые (точные методы);

2) итерационные методы (приближенные).

Точные методы

 

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

Метод Гаусса

 

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

 

Прямой ход метода

1-й шаг. Предположим, что а ₁₁¹0. Поделим первое уравнение на этот элемент, который назовем ведущим элементом первого шага:

. (1.3)

 

Остальные уравнения системы (1.1) запишем в виде

 

, (1.4)

где i= .

Уравнение (1.3) умножаем на a_{i 1} и вычитаем из i-го уравнения системы (1.4). Это позволит обратить в нуль коэффициенты при x ₁ во всех уравнениях, кроме первого.

Получим эквивалентную систему вида:

. (1.5)

 

,

где i,j= . Система (1.5) имеет матрицу вида:

 

.

 

Дальше работаем с укороченной системой, т.к. х ₁ входит только в 1-ое уравнение

.

2-й шаг. На этом шаге исключаем неизвестное х ₂ из уравнений с номерами i= 3,4,…, m. Если ведущий элемент второго шага , то из укороченной системы ана­логично исключаем неизвестное x ₂ и получаем матрицу коэффициентов такого вида:

.

 

Аналогично повторяем указанные действия для неиз­вестных х ₃ ,х ₄ ,...,х_{m- 1}и приходим к системе:

 

. (1.6)

Эта система с верхней треугольной матрицей:

 

.

Обратный ход метода. Из последнего уравнения сис­темы (1.6) находим х_m, из предпоследнего х_{m- 1} ,..., из пер­вого уравнения – х ₁.

Общая формула для вычислений:

x_m=y_m/c_mm,

, (i=m -1,…,1).

Для реализации метода Гаусса требуется примерно (1/3) m ³ арифметических операций, причем большинство из них приходится на прямой ход.

Ограничение метода единственного деления заключа­ется в том, что ведущие элементы на k -ом шаге ис­ключения не равны нулю, т.е. ≠0.

Но если ведущий элемент близок к нулю, то в процессе вычисления может накапливаться погрешность. В этом случае на каждом шаге исключают не х_k, a х_j (при j¹k). Такой подход называется методом выбора главного элемента. Для этого выбирают неизвестные x_j с наибольшим по абсолютной величине коэффициентом либо в строке, либо в столбце, либо во всей матрице. Для его реализации требуется − арифметических действий.

 

Связь метода Гаусса с разложением матрицы на множители. Теорема об LU разложении.

 

Пусть дана система Aх = b (1.1), которая при прямом ходе преобразуется в эквивалентную систему (1.6) и запишем ее в виде

C х = y, (1.6*)

где С – верхняя треугольная матрица с единицами на главной диагонали, полученная из (1.6) делением последнего уравнения системы на с_mm.

Как связаны в системе (1.1) элементы b и элементы y из (1.6*)?

Если внимательно посмотреть на прямой ход метода Гаусса, то можно увидеть, что

.

Для произвольного j имеем

, (1.7)

где j= , d_ji – числовые коэффициенты:

 

. (1.8)

Можно записать систему:

 

b = Dy,

где D −нижняя треугольная матрица с элементами на главной диагонали (j= , ).

В связи с тем, что в методе Гаусса угловые коэффици­енты не равны нулю , то на главной диагонали матрицы D стоят не нулевые элементы. Следовательно, эта матрица имеет обратную, тогда y = D ^{- 1} b, С x = D ^{- 1} b.

Тогда

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.

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