Различные варианты метода Якоби

⇐ ПредыдущаяСтр 10 из 13Следующая ⇒

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

(i_n, j_n)Þ , n=0, 1, 2,…

Барьерные методы. Используется простая циклическая последовательность аннулирования недиагональных элементов матрицы, т.е. элементы матрицы зануляются в следующем порядке: (2, 1), (3, 1), (3, 2),…, (n, 1), (n, 2),…, (n, n-1), а затем начинается новый проход по матрице в том же порядке. При этом вращения опускаются, если меньше некоторого барьерного значения t, которое может быть фиксировано, а может меняться на каждой итерации.

Фиксированный барьер меняется, если все диагональные элементы стали меньше его следующим образом:

1. В качестве барьера t выбирается произвольное положительное число. Затем, когда все недиагональные элементы становятся по модулю меньше его, барьер заменяется на новый t^’=t/const.

2. В качестве начального барьера выбирается t= , где N – количество над диагональных элементов. Затем на каждой итерации величина уменьшается на и t перевычисляется по той же формуле.

3. Значения барьера выбираются так же как в пункте 2, но в качестве критерия проведения вращения используется условие N > , n=0,1,2,…

Экономическая стратегия выбора аннулируемого элемента. Выбор номера (i_k, j_k) зануляемого элемента матрицы происходит следующим образом:

а) вычисляются суммы внедиагональных элементов матрицы по строкам

S_i= ;

б) выбирается максимальная сумма

в) выбирается максимальный элемент, входящий в максимальную сумму

, k=0, 1, 2,…

Степенной метод

Степенной метод [2-4, 6, 9, 11, 12] предназначен для нахождения наибольшего по модулю собственного значения и соответствующего собственного вектора. Метод является простым, тем не менее, нечасто используется на практике из-за медленной сходимости. Знакомство с методом оправданно тем, что на его идее основаны более эффективные методы.

Пусть А=A^* и

½l₁½<½l₂½<…<½l_n-1½<½l_n½. (4.19)

Зададим произвольный вектор у₀ таким, что

(у₀, x_n)¹0

и образуем последовательность

y_k₊₁=Ay_k . (4.20)

Далее строим последовательность скалярных произведений

(y_k, y_k), (y_k+1, y_k), k=0, 1, 2,…

Покажем, что

= =l_n (4.21)

или

=l_n+О( ). (4.22)

Разложим вектор у₀ по собственным векторам матрицы А

y₀= ,

y₁=Ay₀= = ,

y₂=Ay₁= = ,

………………………………

y_k= ,

y_k+1= .

Тогда

(y_k, y_k)= ,

(y_k+1, y_k)= .

Значит

=l_n, (4.23)

что приводит к (4.21) и (4.22) при k®¥.

Таким образом, наибольшее по модулю собственное значение находится итерационно по формуле

(k=0, 1, 2,…),

что подтверждает (4.22). Из формулы (4.23) видно, что степенной метод нахождения наибольшего по модулю собственного значения сходится при выполнении условия (4.19). Процесс итерации заканчивается при выполнении условия

<e, 0<e<1.

Для вычисления собственного вектора x_n воспользуемся формулой (4.20). Действительно,

y_k₊₁= =c_n,

при k®¥ y_k₊₁» c_nx_n .

Таким образом, вектор y_k₊₁отличается от собственного вектора x_n лишь множителем c_n. Так как величина может быть достаточно большой, то при вычислении x_n формулой (4.20) необходима нормировка вычисляемого вектора y_k₊₁через какое-то число итерации. Нормированный собственный вектор x_n будет таким

x_n= или x_ni= .

Обратный степенной метод

Обратный степенной метод [6, 9, 11, 12] используется для нахождения наименьшего по модулю собственного значения и соответствующего собственного вектора матрицы. При этом метод применяется к обратной матрице A^-1, так как собственные значения последней обратны к собственным значениям матрицы А.

Пусть А=A^* и

½l₁½<½l₂½<…<½l_n-1½<½l_n½. (4.24)

Выберем произвольный вектор z₀ таким, что

(z₀, x₁)¹0

и образуем последовательность

z_k+1=A^-1z_k . (4.25)

Так как собственные значения g_i матрицы A^-1 связаны с собственными значениями l_i матрицы А соотношением

g_il_i=1 ,

имеем

½g_max½=1/½l_min½=1/½l₁½=½g₁½.

Покажем, что

= (4.26)

или

= +О( ). (4.27)

Формулы (4.25) – (4.27) составляют алгоритм определения наименьшего по модулю собственного значения матрицы А.

Далее разложим вектор z₀по собственным векторам матрицы А

z₀= ,

z₁=A^-1z₀= ,

z₂=A^-1z₁= ,

………………

z_k= ,

z_k+1= .

Тогда

(z_k, z_k)= ,

(z_k+1, z_k)= .

Поэтому

=g_n. (4.28)

Из (4.28) следует сходимость обратного степенного метода, и будем иметь

» (k=0, 1, 2,…),

что подтверждает (4.27).

Для нахождения собственного вектора х₁ можно воспользоваться формулой (4.25). Тогда получим

z_k₊₁= = x_i= .

При k®¥ z_k₊₁» , следовательно, вектор z_k₊₁будет отличаться от вектора х₁множителем . При определении собственного вектора х₁требуется нормировка вычисляемых векторов z_k₊₁.

Итерационный метод

Пусть А=А^*>0 , тогда распишем систему уравнений

(А-lЕ)х=0 (4.29)

относительно собственного значения l₁ и собственного вектора матрицы А

или

(4.30)

Поскольку компоненты собственных векторов определяются с точностью до постоянной, то одну из них можно задать произвольно, например, за исключением особого случая, можно положить =1. Систему (4.30) можно решить методом итерации, следующим образом при начальных значениях

Итерация заканчивается при выполнении условия

где 0<e<1.

Таким образом, находится первое собственное значение

и первый собственный вектор

Для определения второго собственного значения l₂ и второго собственного вектора х⁽²⁾ обратимся к системе

(4.31)

Из соотношения ортогональности

(4.32)

исключается одно из неизвестных , например . Тогда система (4.31) заменится эквивалентной

(4.33)

Здесь новые преобразованные коэффициенты. Далее, полагая, что =1 и при заданных начальных значениях решается система уравнений (4.33) методом итерации:

В результате будут найдены второе собственное значение l₂ и второй собственный вектор х⁽²⁾ матрицы А, при чем n-я компонента этого вектора находится из условия ортогональности (4.32). Аналогично находятся остальные l_j (j=3,4,…,n) и соответствующие им собственные векторы х⁽^j).

Дата добавления: 2018-04-15; просмотров: 311; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 4 5 6 7 8 91011 12 13 Следующая ⇒

Мы поможем в написании ваших работ!