Реферат: Алгебраическая проблема собственных значений

STOP

END

Результат работы программы получаем в виде:

Собственные значения равны

0.33709179E 08

0.19149061E 08

0.71417603E 07

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

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

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

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

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

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

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

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

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

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

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

А_k = Р_k A_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 = Sa² _k,i

i=k+1

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

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

*	*	0	0	0	0
*	*	*	0	0	0
*	*	*	*	0	0
*	*	*	*	*	0
*	*	*	*	*	*
*	*	*	*	*	*

5. ОПРЕДЕЛЕНИЕ СОБСТВЕННЫХ ЗНАЧЕНИЙ СИММЕТРИЧНОЙ ТРЕХДИАГОНАЛЬНОЙ МАТРИЦЫ

Приведя симметричную матрицу к трехдиагональному виду методом Гивенса или Хаусхолдера, необходимо найти ее собст­венные значения. Чтобы ясней были достоинства трехдиагональной формы, сформулируем задачу о собственных значениях в виде

dеt(А— l E) = 0 ,

где А — симметричная трехдиагональная матрица. Раcкрыв выражение в скобках, получим

a1 - l	b2	0
b1	a2 - l	= 0
bn
0	bn	an - l

Произвольный определитель порядка п можно выразить через п миноров порядка п — 1, каждый из которых в свою очередь выражается через п — 1 миноров порядка п — 2. Удобство трех­диагональной формы в том, что на каждом шаге все миноры, кроме двух, оказываются равными нулю. В результате исходный определитель представляется последовательностью полиномов

f_m (l) = (a_m - l ) f_m-1 (l) – b² _m f_{m -2} (l).