Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 13 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

13
осуществляется таким образом, чтобы в процессе исключения
сохранялась разреженность и обеспечивалась численная устойчивость .
2.2 Гауссово исключение по столбцам
Гауссово исключение по столбцам состоит из n шагов. В результате
выполнения k - го шага исключаются все ненулевые элементы матрицы ,
расположенные в k-м столбце под диагональю. На первом шаге ненулевые
элементы первого столбца матрицы A ≡ A
(1)
исключаются посредством
поэлементного вычитания первой строки, умноженной на соответствующие
скаляры, из всех остальных строк, имеющих ненулевой элемент в первом
столбце. Элемент a
11
, находящийся в строке, которая вычитается из
остальных строк и в столбце, поддиагональные элементы которого
исключаются , называется главным элементом. Предполагается , что он
отличен от нуля. Перед исключением первая строка нормируется путем
деления всех ее ненулевых элементов на главный элемент . После
исключения получается матрица A
(2)
, для которой
0
)2(
1
=
i
a
при i > 1 и
1
)2(
11
=a
.
На втором шаге в качестве главного выбирается элемент
)2(
22
a
. При этом
вновь предполагается , что
0
)2(
22
≠a
. Вторая строка нормируется , и все
ненулевые элементы второго столбца, расположенные ниже диагонали,
исключаются при помощи вычитания из соответствующих строк
нормированной второй строки, умноженной на подходящие множители.
Заметим , что поскольку
0
)2(
21
=a
, то элементы первого столбца не изменят при
этом своих значений . Получается матрица А
(3)
, у которой 0
)3(
1
=
i
a при i > 1,
0
)3(
2
=
i
a при i > 2 и 1
)3(
22
)3(
11
== aa . Т.е. в своих первых двух столбцах матрица
А
(3)
является верхней треугольной с единичной диагональю.
В начале k-го шага матрица А
(k)
имеет нулевые элементы в первых k – 1
столбцах под диагональю и единичные элементы в первых k – 1 позициях на
диагонали.
На k-м шаге в качестве главного выбирается элемент
)( k
kk
a . Затем k - я строка
нормируется , и поддиагональные элементы в k - м столбце матрицы A
(k)
исключаются путем вычитания умноженной на подходящие скаляры
нормированной k - й строки из всех строк, имеющих ненулевые элементы в k -
м столбце под диагональю. Получается матрица A
(k+1)
с нулевыми
элементами в первых
k столбцах ниже диагонали и с единицами в первых k
позициях на диагонали.
Этот процесс продолжается до тех пор , пока в конце n-го шага не
получится матрица A
(n+1)
, которая содержит нулевые элементы под
диагональю и единичные элементы на диагонали, являясь , таким образом,
верхней треугольной с единичной диагональю. Отсюда получается
факторизованная форма матрицы А: А = LU, где U ≡ A
(n+1)
– верхняя
треугольная матрица с единичной диагональю, причем
)1( +
=
k
kjkj
au
при j > k.
Выражения для элементов матрицы L можно получить из уравнений : 
                                         13
осуществляется    таким    образом, чтобы в процессе исключения
сохранялась разреженность и обеспечивалась численная устойчивость.

       2.2 Гауссово исключение по столбцам
        Гауссово исключение по столбцам состоит из n шагов. В результате
выполнения k-го шага исключаются все ненулевые элементы матрицы,
расположенные в k-м столбце под диагональю. На первом шаге ненулевые
элементы первого столбца матрицы A ≡ A(1) исключаются посредством
поэлементного вычитания первой строки, умноженной на соответствующие
скаляры, из всех остальных строк, имеющих ненулевой элемент в первом
столбце. Элемент a11, находящийся в строке, которая вычитается из
остальных строк и в столбце, поддиагональные элементы которого
исключаются, называется главным элементом. Предполагается, что он
отличен от нуля. Перед исключением первая строка нормируется путем
деления всех ее ненулевых элементов на главный элемент. После
исключения получается матрица A(2), для которой ai(12) =0 при i > 1 и a11( 2 ) =1 .
      На втором шаге в качестве главного выбирается элемент a 22       ( 2)
                                                                            . При этом
вновь предполагается, что a22 ≠0 . Вторая строка нормируется, и все
                                       ( 2)


ненулевые элементы второго столбца, расположенные ниже диагонали,
исключаются при помощи вычитания из соответствующих строк
нормированной второй строки, умноженной на подходящие множители.
Заметим, что поскольку a21    ( 2)
                                    =0 , то элементы первого столбца не изменят при
этом своих значений. Получается матрица А(3), у которой ai(13) =0 при i > 1,
ai(23) =0 при i > 2 и a11
                        ( 3)
                             =a 22
                                (3)
                                    =1 . Т.е. в своих первых двух столбцах матрица
 (3)
А является верхней треугольной с единичной диагональю.
      В начале k-го шага матрица А(k) имеет нулевые элементы в первых k – 1
столбцах под диагональю и единичные элементы в первых k – 1 позициях на
диагонали.
      На k-м шаге в качестве главного выбирается элемент akk(k ) . Затем k-я строка
нормируется, и поддиагональные элементы в k-м столбце матрицы A(k)
исключаются путем вычитания умноженной на подходящие скаляры
нормированной k-й строки из всех строк, имеющих ненулевые элементы в k-
м столбце под диагональю. Получается матрица A(k+1) с нулевыми
элементами в первых k столбцах ниже диагонали и с единицами в первых k
позициях на диагонали.
      Этот процесс продолжается до тех пор, пока в конце n-го шага не
получится матрица A(n+1), которая содержит нулевые элементы под
диагональю и единичные элементы на диагонали, являясь, таким образом,
верхней треугольной с единичной диагональю. Отсюда получается
факторизованная форма матрицы А: А = LU, где U≡A(n+1) – верхняя
треугольная матрица с единичной диагональю, причем u kj =akj( k +1) при j > k.
Выражения для элементов матрицы L можно получить из уравнений:

Страницы