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

 

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

 

В случае матрицы размерности п х п метод Гивенса требует п — 2 основных шагов, на каждом из которых выполняется ряд преобразований, число которых зависит от числа нулей, кото­рое хотят получить в данном столбце или строке. На k -м шаге обращают в нули элементы, стоящие вне трех диагоналей k -й строки и k -го столбца, сохраняя в то же время нулевые элементы, полученные на предыдущих шагах. Таким образом, перед нача­лом k -го шага преобразованная матрица является трехдиа­гональной, если ограничиться рассмотрением ее первых k — 1 строк и столбцов. По мере преобразований симметричная матри­ца размерности 5х5 приобретает следующие формы:

 

 

	*	*	*	*	*
	*	*	*	*	*
A0=	*	*	*	*	*	исходная матрица,
	*	*	*	*	*
	*	*	*	*	*

 

 

	*	*
	*	*	*	*	*
A1=		*	*	*	*	после первого основного шага,
		*	*	*	*	состоящего из трех преобразований,
		*	*	*	*

 

 

	*	*
	*	*	*
A2=		*	*	*	*	после второго основного шага,
			*	*	*	состоящего из двух преобразований,
			*	*	*

 

 

	*	*
	*	*	*			после третьего основного шага,
A3=		*	*	*		состоящего из одного преобразования.
			*	*	*	Теперь матрица име­ет трехдиагональный вид.
				*	*

 

 

На каждом основном шаге изменяются лишь те элементы мат­рицы а_ij, которые расположены в ее правой нижней (заштрихо­ванной) части. Таким образом на k-м шаге преобразуется только матрица порядка (п — k + 1), занимающая правый нижний угол исходной матрицы. Ясно, что на каждой следующей стадии вы­полняется меньшее число преобразований, чем на предыдущей. Всего для приведения матрицы к трехдиагональному виду тре­буется выполнить (n ² — Зп + 2)/2 преобразований.

 

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