Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 33 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

- 33 -
Но такой выбор влияет на устойчивость процесса гауссова исключения, так
как если ведущий элемент мал , то возможна потеря устойчивости
вычислений.
4.5. Вычислительные ошибки в гауссовом исключении
При реализации метода Гаусса приходится выполнять арифметические
действия типа
lU
a
b
−
=
. Для операций с плавающей точкой границы
ошибки обычно устанавливаются следующим образом:
)
1
)(
(
)
(
ε
+
=
y
x
y
x
l
oo , где символ
o
обозначает одну из элементарных
операций
)
(
;
/
,
,
,
y
x
o
×
−
+
– точный результат операции;
)
(
y
x
l
o –
округленный результат ;
M
ε
ε
≤
, где
M
ε
– машинная точность.
Пусть
α
<
ba , , тогда для оценки погрешности имеем
+
−
⋅
−
⋅⋅≤ 2
1
1
1
1
MM
M
εε
εαε .
Таким образом, для того чтобы вычислительная погрешность была не
слишком велика, не следует допускать чрезмерного роста чисел
U
l
a
,
,
.
А в методе Гаусса
U
l
a
,
,
– элементы
k
-х промежуточных матриц.
Поэтому вводится показатель промежуточного роста в методе Гаусса
k
ijk
a max=α
{
}
(
)
k
ijk
aA = , который должен быть не слишком велик.
4.6. Стратегия , осуществляющая компромисс между оптимизацией
устойчивости и оптимизацией алгоритма
Пусть сделаны первые
k
шагов метода Гаусса с выбором главного
элемента по столбцу . Возьмем число
1
0
:
<<
<
U
U
. Определим в
k
-ом
столбце множества
{
}
sp
k
ijikikst
RaUaaR ,max: ⋅≥=
– - множество
ненулевых элементов
k
-го столбца , предпочтительных с точки зрения
разреженности, например таких, для которых цена Марковица не
превосходит некоторого фиксированного числа.
Выбор ведущего элемента осуществляется в множестве
stsppiv
RRR I
=
,
ориентируясь на
sp
R
или
sp
R
.
Литература
1. Писсанецки С . Технология разреженных матриц / C. Писсанецки. – М .:
Мир, 1988.
2. Джордж А ., Лю Д . Численные методы решения больших разреженных
систем уравнений / А . Джордж , Д . Лю . – М .: Мир, 1984. 
                                          - 33 -

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

     4.5. Вычислительные ошибки в гауссовом исключении
  При реализации метода Гаусса приходится выполнять арифметические
  действия типа           b =a −lU . Для операций с плавающей точкой границы
  ошибки            обычно          устанавливаются     следующим          образом:
   f l ( x  y ) =( x  y )(1 +ε) , где символ  обозначает одну из элементарных
  операций +, −, ×, / ; ( x  y ) – точный результат операции;         f l ( x  y) –
  округленный результат;      ε ≤εM , где εM – машинная точность.
  Пусть a , b <α , тогда для оценки погрешности имеем
                                             1         �    1       �
                        ε ≤α ⋅εM ⋅                 ⋅ ��        +2 �� .
                                          1 −εM        � 1 −εM        �
  Таким образом, для того чтобы вычислительная погрешность была не
  слишком велика, не следует допускать чрезмерного роста чисел a, l , U .
  А в методе Гаусса    a, l , U – элементы k -х промежуточных матриц.
  Поэтому вводится показатель промежуточного роста в методе Гаусса
  α k =max aijk        (A ={a }) ,
                          k
                                   k
                                   ij      который должен быть не слишком велик.

    4.6. Стратегия, осуществляющая компромисс между оптимизацией
          устойчивости и оптимизацией алгоритма
   Пусть сделаны первые k шагов метода Гаусса с выбором главного
  элемента по столбцу. Возьмем число U : 0

Страницы