Численные методы. Корнюшин П.Н. - 54 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

54
Тогда условия (22) будут выполнены, а условия (21) – выполнены для i=1. Запишем
оставшиеся соотношения следующим образом:
∑
−
=
−==+=
==
1
1
_
^^
1
1
^
,1,...,3,2;,...,4,3,
,,...,3,2,
j
k
jkikij
ij
i
i
ijNisssa
Nias
и из (24) найдем
j
ij
ij
dss /
^
=
. Отсюда следует алгоритм.
Находим сначала d
1
=a
11
.
Для i от 2 до N выполняем действия:
.
.3
./,
:12
,32.2
./,.1
1
1
_
^
1
1
^
_
^^
1
1
^
11
1
^
end
ssad
dssssas
doitojfor
elsetogotheniif
dssas
begin
i
k
ikik
iii
j
k
j
ij
ij
jkik
ij
ij
i
ii
i
→
−
=−=
−=
=
==
→
∑
∑
−
=
−
=
Замечание. Вычисляемые элементы s
ij
и d
i
могут быть размещены на месте a
ij
и a
ii
, если
элементы матрицы A не нужно сохранять. Дополнительная память требуется для размещения при
фиксированном i чисел
ij
s
^
(j=1, 2,…, i-1); очевидно, нужно не более N-1 ячеек памяти для их
хранения.
Алгоритм SDS
*
-разложения может оказаться численно неустойчивым даже при выборе
главного элемента. Однако в двух случаях можно гарантировать устойчивость алгоритма – для
положительно определенных матриц A и матриц с диагональным преобладанием.
Определитель матрицы равен
∏
=
=
N
i
iiii
sdA
1
2
.det (26)
Метод квадратного корня требует порядка N
3
/3 арифметических действий, т.е. при
больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это
обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.
3.5.2.3. Связь метода Гаусса с разложением матрицы на множители
Пусть дана невырожденная матрица A размера N*N. Представим ее в виде произведения
A=BC, A=(a
ij
), B=(b
ij
), C=(c
ij
), (27)
где B и C – треугольные матрицы вида
,
...
...................
0...
0...0
0...00
321
333231
2221
11
=
NNNNN
bbbb
bbb
bb
b
B
,
1...000
...................
...100
...10
...1
3
223
11312
=
N
N
N
c
cc
ccc
C
т.е. b
ik
=0 при k>i, c
ik
=0 при k<i, c
ii
=1. Из (27) следует, что
∑
=
=
N
k
kjikij
cba
1
. Преобразуем эту
сумму двумя способами: 
                                                                     54


      Тогда условия (22) будут выполнены, а условия (21) – выполнены для i=1. Запишем
оставшиеся соотношения следующим образом:
                            ^
                            s i1 = ai1 , i = 2,3,..., N ,
                                   ^       j −1 ^     _
                            aij = s ij + ∑ s ik s jk , i = 3,4,..., N ; j = 2,3,..., i − 1,
                                           k =1
                        ^
и из (24) найдем s ij = s ij / d j . Отсюда следует алгоритм.
        Находим сначала d1=a11.
        Для i от 2 до N выполняем действия:
                                  → begin
                                            ^                         ^
                                       1. s i1 = ai1 , si1 = s i1 / d1 .
                                       2.if i = 2 then go to3, else
                                                for j = 2 to i − 1 do :
                                       ^                    j −1 ^    _    ^
                                       s ij = aij − ∑ s ik s jk , sij = s ij / d j .
                                                           k =1
                                                           i −1 ^     _
                                        3.d i aii − ∑ s ik s ik
                                                           k =1
                                  → end .
       Замечание. Вычисляемые элементы sij и di могут быть размещены на месте aij и aii, если
элементы матрицы A не нужно сохранять. Дополнительная память требуется для размещения при
                            ^
фиксированном i чисел s ij (j=1, 2,…, i-1); очевидно, нужно не более N-1 ячеек памяти для их
хранения.
       Алгоритм SDS*-разложения может оказаться численно неустойчивым даже при выборе
главного элемента. Однако в двух случаях можно гарантировать устойчивость алгоритма – для
положительно определенных матриц A и матриц с диагональным преобладанием.
       Определитель матрицы равен
                                                          N
                                       det A = ∏ d ii sii2 .                   (26)
                                                          i =1
       Метод квадратного корня требует порядка N3/3 арифметических действий, т.е. при
больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это
обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.


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

        Пусть дана невырожденная матрица A размера N*N. Представим ее в виде произведения
                            A=BC, A=(aij), B=(bij), C=(cij),  (27)
        где B и C – треугольные матрицы вида
                        b11   0           0        ...      0        1 c12 c13        ... c1N 
                       b                                            0 1 c             ... c 2 N 
                        21 b22            0        ...      0                   23

                   B =  b31 b32        b33         ...      0 , C =  0 0       1      ... c3 N ,
                                                                                                 
                        .... ....      ....        ...     ....     .... .... ....    ... .... 
                       bN 1 bN 2     bN 3 ...             bNN      0 0      0      ... 1 

                                                                                       ∑
                                                                                           N
т.е. bik=0 при k>i, cik=0 при k

Страницы