Метод Хаусхолдера для симметричных матриц

 

Метод Хаусхолдера позволяет привести матрицу к трехдиа­гональному виду, выполнив почти вдвое меньше вычислений по сравнению с другими методами. Это обусловлено тем, что при его применении становятся нулевыми сразу все элементы строк и столбцов, стоящие вне трех диагоналей матрицы. Метод Хаусхол­дера позволяет получить требуемый результат быстрее, чем метод Гивенса, так как связан с выполнением меньшего числа, хотя и более сложных преобразований. Это его свойство особенно ярко проявляется применительно к большим матрицам. Хотя в методе Хаусхолдера вместо плоских вращении используются эрмитовы ортогональные преобразования матриц, трехдиагональная форма матрицы, которую получают этим методом, имеет те же собствен­ные значения, что и трехдиагональная матрица, получаемая методом Гивенса. При использовании метода Хаусхолдера на п — 2 основных шагах выполняются следующие преобразования:

А_k = Р_kA_k-1Р_k, k=1, 2,..., п-2,

где Aо == А.

 

Каждая преобразующая матрица имеет вид

u_k u_k^T

P_k = E - --------------,

2K_k²

где

u_i,_k = 0 при i = 1, 2, …, k,

u_i,_k = a_k,_i при i = k+2, …, n,

u_k+1,_k = a_k,k+1 ± Sk.

 

Здесь

n 1/2

S_k = S a²_k,i

i=k+1

 

2K²_k = S²_k ± ak, k+1 Sk.

В этих уравнениях берется знак, соответствующий элементу a _k,_k+1. Это позволяет сделать значение и_k+1,k максимальным. Отметим, что методами Гивенса и Хаусхолдера можно пользо­ваться и в случае несимметричных матриц, приводя их, правда, не к трехдиагональному, а другому частному виду треугольной матрицы известной как матрица Гессенберга:

 

*	*
*	*	*
*	*	*	*
*	*	*	*	*
*	*	*	*	*	*
*	*	*	*	*	*