Вычислительные методы алгебры и оценивания. Семушин И.В. - 118 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

7 Ортогональные преобразования
Алгоритм. Для j = n, n − 1 , . . . , 1 вычислять
x(j) =
z(j) −
n
X
k=j+1
R(j, k)x(k)
/R(j, j). (7.28)
По сложности этот алгоритм почти такой же, как матричное умножение.
Он допускает записывать x(j) поверх z(j), что очень удобно в приложениях.
Если все же требуется иметь матрицу U , R
−1
, то ее можно вычислять
по алгоритму окаймления, основанному на следующем легко проверяемом
тождестве для треугольных матриц:
R
j
y
0 σ
j+1
−1
=
R
−1
j
−R
−1
j
yσ
−1
j+1
0 σ
−1
j+1
= R
−1
j+1
. (7.29)
Это соотношение позв оляет вычислять матрицу U , R
−1
рекуррентно, а
именно: если R
−1
j
= U
j
, где R
j
обозначает верхнюю левую часть матрицы
R, то
U
j+1
=
U
j
−U
j
[R(1, j + 1), . . . , R(j, j + 1)]
T
σ
j+1
0 σ
j+1
, (7.30)
где σ
j+1
= 1/R (j + 1, j + 1). Полагая U = R
−1
, этот результат представим в
алгоритмической форме.
Алгоритм. Обращение верхней треугольной матрицы. Задать началь-
ное значение
U(1, 1) = 1/R(1, 1) . (7.31)
Для j = 2 , . . . , n вычислять по формулам (7.32) и (7.33):
U(j, j) = 1/R(j, j) , (7.32)
U(k, j) = −
j−1
X
i=k
U(k, i) R(i, j)
!
U(j, j) , k = 1, . . . , j − 1 . (7.33)
Замечание 7.5. R
−1
вычисляется по столбцам, при этом элементы
матрицы R
−1
могут записываться поверх элементов исходной матрицы R.
В справочных целях приведем примеры реализации данного алгоритма
на яз ыке FORTRAN. Эти примеры могут помочь студента м написать свои
собственные программы на других языках выс о кого уровня при выполнении
лабораторного проекта № 6, о писа ние которого дано ниже в подразд. 7.16.
118

Страницы