Шкеыҥжым муашлан Йакобин алгоритмже

Шкеыҥжым муашлан Йакобин алгоритмже — вещественле симметрий матрицын чыла шке ыҥжым да чыла шке вектор-влакым муашлан шотпал йӧн. Тиде йӧным Карл Густав Йакоб Йакоби икымше гана 1846 ийыште темлен.

Алгоритм нерген

Шонкалена, A - тиде симметрий матрице да G = G(i,j,θ) - тиде Гивенсын савыралмашын матрицыже. Тунам:

$A'=G^\top A G \,$

симметрий улеш да A матрицелан келшыше улеш.

Тылеч гоч, A′ матрицыште тыгай тӱҥлык-влак улыт:

$\begin{align} A'_{ii} &= c^2\, A_{ii} - 2\, s c \,A_{ij} + s^2\, A_{jj} \\ A'_{jj} &= s^2 \,A_{ii} + 2 s c\, A_{ij} + c^2 \, A_{jj} \\ A'_{ij} &= A'_{ji} = (c^2 - s^2 ) \, A_{ij} + s c \, (A_{ii} - A_{jj} ) \\ A'_{ik} &= A'_{ki} = c \, A_{ik} - s \, A_{jk} & k \ne i,j \\ A'_{jk} &= A'_{kj} = s \, A_{ik} + c \, A_{jk} & k \ne i,j \\ A'_{kl} &= A_{kl} &k,l \ne i,j \end{align}$

кушто s = sin(θ) да c = cos(θ).

Нуно келшыше улыт, садлан A да A′ икгай Фробениусын нормыжым кучат ||·||_F , туге гынат ме θ тыгайым ойырен кертына: A′_ij = 0, туге гын A′ матрицыште диагональыште шогышо тӱҥлык-влакын квадратын чумыржо утларак лиеш:

$A'_{ij} = \cos(2\theta) A_{ij} + \tfrac{1}{2} \sin(2\theta) (A_{ii} - A_{jj})$

Тидым укелыкыш савырена, да тидым луктын налына:

$\tan(2\theta) = \frac{2 A_{ij}}{A_{jj} - A_{ii}}$

Лектышыже сайрак лийже манын, A_ij - эн кугу диагональыште огыл шогышо тӱҥлык лийшаш, тидым pivot лӱмдат.

Шкеыҥжым муашлан Йакобин йӧнже тыгай савырымашым ала-мыняр пачаш ышта, тумарте матрице симметрий наре лиеш. Тунам диагональыште шогышо тӱҥлык-влак A матрицын чын шкеыҥже-влак наре лийыт.

Алгоритм

Ӱлно возымо алгоритм Якобин йӧнжым ончыкта. Тудо C++ йылме дене возымо. Тиде алгоритм шкеыҥжым гына муэш. Шкевекторжым муашлат керек-могай СЛАУ рашемдашлан алгоритмым кучаш лиеш. Мутлан, ик эн изи алгоритм - Гаус йӧн. Тиде йӧн почеш матрицым кумлукан сыныш савыраш кӱлеш, варажым шкевекторым муаш неле огыл.

void diagonalize_sym(array<double,2>^ A, int n)
// A - пуымо тӱҥалтыш вещественле матрице. Тушто ошкыл почеш ошкыл дене
//     шкеыҥже-влак тӱҥ диагональыште шогаш тӱҥалыт.
// n - матрицын кугытшо.
{
        int k, done; 
        double discr, aii, aij, ajj, aik, ajk, v1, v2, norm; 
 
        do
        {
                done = 1; 
                for (int i=0;i<n;i++) // тиде кок цикл-влак укелыкыш савырыме тӱҥлык-влакым ойырен налыт
                        for (int j=0;j<i;j++)
                        { 
                                aii = A[i,i];
                                aij = A[i,j];
                                ajj = A[j,j];
                                if (Math::Abs(aij)>1e-100)
                                { 
                                        discr = Math::Sqrt((aii-ajj)*(aii-ajj)+4*aij*aij); 
                                        /* Шкеыҥжым шотлаш. */
                                        if (aii+ajj>0)
                                        { 
                                                A[i,i] = (aii+ajj+discr)/2;
                                                A[j,j] = (aii*ajj-aij*aij)/A[i,i]; 
                                        }
                                        else
                                        { 
                                                A[j,j] = (aii+ajj-discr)/2;
                                                A[i,i] = (aii*ajj-aij*aij)/A[j,j];
                                        }
                                        A[i,j] = 0;
                                        A[j,i] = 0;
 
                                        if (aii>ajj)
                                        { 
                                                v1 = (aii-ajj+discr)/2;
                                                v2 = aij;
                                        }
                                        else
                                        {
                                                v1 = aij;
                                                v2 = (ajj-aii+discr)/2;
                                        }
                                        norm = Math::Sqrt(v1*v1+v2*v2);
                                        v1 /= norm;
                                        v2 /= norm;
                                        /* Вашталтымашым матрицыште кодшо верыш пурташ. */
                                        for (k=0;k<n;k++) if (k!=i && k!=j)
                                        {
                                                aik = A[i,k];
                                                ajk = A[j,k];
                                                A[i,k] = v1*aik+v2*ajk;
                                                A[k,i] = v1*aik+v2*ajk;
                                                A[j,k] = -v2*aik+v1*ajk;
                                                A[k,j] = -v2*aik+v1*ajk;
                                        }
                                        done = 0;
                                }
                        }
        }
        while (!done);

Англичан википедийыште эше вес алгоритм уло. Тудо математик семын возымо, шкеыҥжым да шкевекторжым муэш, но тудо шкеыҥже-влакым южгунам муын ок керт, алгоритм деч вара тӱткынрак умылтарымашым лудса.

Укелыкыш савырыме тӱҥлыкым кузе ойырен налаш лиеш

Чылаже тудым кум йӧн дене ойырен налаш лиеш:

• Абсолют ыҥже дене эн кугум да диагональыште огыл шогышо тӱҥлыкым налаш лиеш.
• Цикл дене укелыкыш савырыме тӱҥлыкым налаш лиеш. Тудым тыге налыт:

(1,2), (1,3), ..., (1,n), (2,3), (2,4), ..., (2,n), (3,4), ..., (3,n), ..., (n-1,n)

• Оптимал тӱҥлыкым налме йӧн. Тӱҥалашлан корным муаш кӱлеш. Тиде корнышто диагональыште огыл шогышо тӱҥлыкын чумыржо эн кугу лийшаш. А варажым тиде корнышто абсолют ыҥже дене эн кугу тӱҥлыкым муыт. Тиде тӱҥлыкым укелыкыш савыраш кӱлеш.

Негыз

• Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений. К.Ю. Богачев. Моско, 1998.