Название: Информатика.Алгоритмы и программы вычислительных задач микроэлектроники - Метод.(Н.В. Усольцев)

Жанр: Информатика

Просмотров: 886


3.  метод  lu-разложения

Метод LU-разложения основан на том, что матрица  может быть представлена в виде произведения двух матриц:

                                                                                      (7)

 

где       - нижняя треугольная матрица,

 - верхняя треугольная матрица с единичной  главной диагональю.

При этом разложении исходная система (1) разлагается на две, но с треугольными матрицами:

                                                                                      (8а)

 

                                                                                     (8б)

 

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

 

            1. Прямой ход

Алгоритм разложения  (факторизации)  матрицы   на две треугольных также осуществляется за  шагов. На k-том шаге формируется k-тая строка матрицы  и k-тый столбец матрицы . Каждый шаг состоит из двух частей.

1.1. На первой части вычисляются

                                                         (9а)

                                       (9б)

1.2. На второй части шага пересчитывается оставшаяся часть матрицы , лежащая ниже k-той строки и правее k-того столбца:

 

                                                 (10)

 

2. Обратный ход

2.1. Сначала решается система .  Нижний треугольный вид матрицы  позволяет последовательно найти :

 

                                                   (11)

 

2.2. Затем решается система . Так как она совпадает с системой, получаемой в методе Гаусса, то алгоритм ее решения есть алгоритм обратного хода метода Гаусса.

4. Связь методов Гаусса и LU-разложения

Методы Гаусса и LU-разложения имеют глубокую связь. Подробно об этом можно прочитать, например, в / 5 /. Отметим только, что матрицы  и векторы  в обоих методах одинаковы. Из (8a) следует, что .

Методы Гаусса и LU-разложения имеют одинаковую трудоемкость по количеству вычислительных операций  и примерно одинаково широко используются на практике. LU-разложение матрицы  не затрагивает вектор свободных членов , поэтому этот метод удобно использовать при решении СЛАУ с одной и той же матрицей, но с разными векторами свободных членов.

5. Выбор главного элемента

Методы Гаусса и LU-разложения не будут работать, если в главной диагонали окажется нулевой элемент, стоящий там изначально или полученный при пересчете. Кроме того, если диагональный элемент не равен точно нулю, но мал по величине по сравнению с другими элементами матрицы, то при делении на него возникает большая погрешность результата.

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

В методе Гаусса производится и соответствующий обмен компонентов вектора свободных членов. Такой обмен не изменяет корни СЛАУ и их порядок в векторе .

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

 

6. Метод прогонки

Метод прогонки применяется для СЛАУ с трехдиагональной матрицей, в которой все элементы, не входящие в главную и прилегающие к ней диагонали, равны нулю:

 

При этом нет необходимости хранить всю матрицу и коэффициенты СЛАУ хранятся и обрабатываются в виде трех одномерных массивов:  - массива элементов главной диагонали,  - массива элементов ниже главной диагонали и  - массива элементов выше главной диагонали. Индекс элемента массивов ,  или  соответствует индексу строки матрицы.

 

                           (12)

 

Идея метода прогонки основана на представлении каждой компоненты вектора неизвестных через следующую:

                                                                        (13)

где и  - прогоночные коэффициенты, которые необходимо определить. Умножение первой строки СЛАУ (12) на вектор  и приведение полученного уравнения к виду (13) позволяет найти выражения для первых прогоночных коэффициентов:

 

                                                                   (14)

 

Формулы для последующих прогоночных коэффициентов можно получить, умножая последовательно строки матрицы СЛАУ (12) на вектор  и приводя записи к виду (13):

 

                                                   (15)

 

где                                                         ( i =2, 3, ..., n)

После определения прогоночных коэффициентов совершается обратный ход - последовательное определение компонент вектора неизвестных, начиная с :

                               (i = n-1, n-2, …, 1)                          (16)

 

7. Погрешности решения СЛАУ

Казалось бы прямые методы решения СЛАУ являются достаточно точными; погрешность результата должна быть порядка погрешности вычисления - выполнения арифметических операций, которая определяется типом используемых данных. Для типа double константа машинного нуля DBL_EPSILON, характеризующая эту погрешность, составляет . Для методов Гаусса и LU-разложения выполняется порядка  операций, поэтому ожидаемая погрешность даже при n = 100 должна быть порядка . Но на самом деле, величина погрешности сильно зависит и от конкретных значений элементов матрицы.

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

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

                                                                                                               (17)

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

                                   ;                                                                        (18)

                                                                                                             (19)

Реальная погрешность будет определяться большей из трех величин, получаемых по соотношениям (17), (18) и (19).  Системы с большим значением числа обусловленности называются плохо обусловленными. Для них получение достаточно точного решения невозможно или представляет сложную проблему.

            Для определения числа  обусловленности матрицы используются весьма сложные алгоритмы / 6, 8 / . В данной лабораторной работе для этих целей применяется функция Decomp( ), которая взята из источника / 8 /.