vma_lab06.tex

\documentclass[12pt]{report}

\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{caption}
\usepackage[a4paper,margin=1.0in,footskip=0.25in]{geometry}
\usepackage{listings}  
\usepackage{color}
\usepackage{tabto}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=Python,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=3,
  frame=none
}

%Title
\title{\vspace{-3cm}Лабораторная №6}
\author{Жидович Максим, группа №1}
\date{15 декабря 2021}

\renewcommand\thesection{\arabic{section}}

\begin{document}

\maketitle

\section{Постановка задачи}

Разработать программу вычисления наибольшего и второго по величине модуля
собственных значений и соответствующих им собственных векторов симметричной
матрицы.
Матрицу задаём таким же образом, как в лабораторной 2, положив k = 0.
\[
\begin{bmatrix}
a_{11} & a_{12}  & \cdots   & a_{1n}   \\
a_{21} & a_{22}  & \cdots   & a_{2n}  \\
\vdots & \vdots  & \ddots   & \vdots  \\
a_{n1} & a_{n2}  & \cdots\  & a_{nn}  \\
\end{bmatrix}
\]

\section{Входные данные}

В работе использовались:

Матрица $A$ 5 порядка:
\[ 
\begin{bmatrix}
11 & -2  & 0  & -4 & -4 \\
-2 & 10 & -4 & -3 & -1 \\
0 & -4 & 6 & -1 & -1 \\
-4 & -3 & -1 & 11 & -3 \\
-4 & -1 & -1 & -3 & 9 \\
\end{bmatrix}
\]

\section{Краткая теория}
\tabСтепенной метод является итерационным методом решения полной
(теоретически, а на практике частичной) проблемы собственных значений.
Суть метода заключается в последовательном приближении $y^{(k)}$: к
собственному вектору соответствующему максимальному собственному
значению $\lambda$. За $\lambda^{(k)}$: берётся отношение соответствующий произвольных
координат векторов $y^{(k+1)}$ и $y^{(k)}$:.

\section{Листинг программы}

\lstset{language=Python}
\lstset{extendedchars=\true}

Код программы, реализующий Степенной метод: 

\begin{lstlisting}
def stepennoy(A, num_of_iterations, m):
    """Find the maximum eigenvalue after `num_of_iterations` iterations using Stepennoy method"""

    n = len(A)

    U = []
    V = []

    # initial approximation: U[0] = [1, 0, 0, ..., 0]
    U.append(np.zeros((n, 1), dtype=int))
    U[0][0, 0] = 1

    V.append(np.zeros((n, 1), dtype=int))

    for k in range(1, num_of_iterations + 2):
        V.append(np.matmul(A, U[k - 1]))    
        U.append(np.divide(V[k], np.linalg.norm(V[k], ord=np.inf)))

    index_of_max_component = np.abs(V[num_of_iterations+1]).argmax()
    lambda1_1 = V[num_of_iterations + 1][index_of_max_component] * np.sign(U[num_of_iterations][index_of_max_component])
    lambda1_2 = np.matmul(V[num_of_iterations + 1].T, U[num_of_iterations]) / np.matmul(U[num_of_iterations].T, U[num_of_iterations])

    index = np.array([abs(V[m][i] - lambda1_1 * U[m - 1][i]) for i in range(n)]).argmax()
    lambda2_1 = (V[m + 1][index] * np.linalg.norm(V[m], ord=np.inf) - lambda1_1 * V[m][index]) / (V[m][index] - lambda1_1 * U[m - 1][index])
    
    index = np.array([abs(V[m][i] - lambda1_2 * U[m - 1][i]) for i in range(n)]).argmax()
    lambda2_2 = (V[m + 1][index] * np.linalg.norm(V[m], ord=np.inf) - lambda1_2 * V[m][index]) / (V[m][index] - lambda1_2 * U[m - 1][index])

    return lambda1_1, lambda1_2, lambda2_1, lambda2_2, U[num_of_iterations].T, V[num_of_iterations + 1]
\end{lstlisting}

\section{Выходные данные}

Кол-во итераций: 46

$\lambda_1$(первый способ): 15.2248

$\lambda_1$(второй способ): 15.2353

$u^{(46)}: $ \begin{bmatrix} 1 & 0.0525 & 0.0956 & -0.7992 & -0.2832 \end{bmatrix}

\noindent
Кол-во итераций: 47

$\lambda_1$(первый способ): 15.2254

$\lambda_1$(второй способ): 15.2355

$u^{(47)}: $ \begin{bmatrix} 1 & 0.0541 & 0.0949 & -0.801 & -0.2824 \end{bmatrix}

\noindent
Кол-во итераций: 48

$\lambda_1$(первый способ): 15.226

$\lambda_1$(второй способ): 15.2355

$u^{(48)}: $ \begin{bmatrix} 1 & 0.0556 & 0.0943 & -0.8027 & -0.2816 \end{bmatrix}

\noindent
Кол-во итераций: 49

$\lambda_1$(первый способ): 15.2265

$\lambda_1$(второй способ): 15.2356

$u^{(49)}: $ \begin{bmatrix} 1 & 0.0556 & 0.0944 & -0.8027 & -0.2816 \end{bmatrix}

\noindent
Кол-во итераций: 50

$\lambda_1$(первый способ): 15.227

$\lambda_1$(второй способ): 15.2357

$u^{(50)}: $ \begin{bmatrix} 1 & 0.0583 & 0.0932 & -0.8058 & -0.2802 \end{bmatrix}

$\nu^{(k+1)} - \lambda_1 u^{(k)}$(первый способ): \begin{bmatrix} 0 & 0.0194 & -0.0079 & -0.0218 & 0.0103 \end{bmatrix}

$\nu^{(k+1)} - \lambda_1 u^{(k)}$(второй способ): \begin{bmatrix} -0.0087 & 0.0189 & -0.0087 & -0.0148 & 0.0127 \end{bmatrix}

$\|\nu^{(k+1)} - \lambda_1 u^{(k)}\|$(первый способ): 0.0218

$\|\nu^{(k+1)} - \lambda_1 u^{(k)}\|$(второй способ): 0.0189

\noindent
Кол-во итераций: 50, $m$=30

$x_1$: \begin{bmatrix} 0 & 0.0194 & -0.0079 & -0.0218 & 0.0103 \end{bmatrix}

$x_2$: \begin{bmatrix} -0.0087 & 0.0189 & -0.0087 & -0.0148 & 0.0127 \end{bmatrix}

$\lambda_2$(первый способ): 14.4557

$Ax_1 - \lambda_2 x_1$: \begin{bmatrix} 0.0073 & 0.0003 & 0.0007 & -0.0057 & -0.0021 \end{bmatrix}

$\|Ax_1 - \lambda_2 x_1\|$: 0.0073

\noindent
Кол-во итераций: 50, $m$=50

$\lambda_2$(первый способ): 14.7104

$Ax_1 - \lambda_2 x_1$: \begin{bmatrix} 0.0073 & -0.0046 & 0.0028 & -0.0002 & -0.0047 \end{bmatrix}

$\|Ax_1 - \lambda_2 x_1\|$: 0.0073

\noindent
Кол-во итераций: 50, $m$=50

$\lambda_2$(второй способ): 14.442

$Ax_2 - \lambda_2 x_2$: \begin{bmatrix} 0.0005 & $1.96 \cdot 10^{-6}$ & $6.04 \cdot 10^{-5}$ & -0.0004 & -0.0002  \end{bmatrix}

$\|Ax_2 - \lambda_2 x_2\|$: 0.0005

\section{Выводы}

\tabС помощью степенного метода мы нашли максимальное, второе по модулю собственные значения и соответствующие им собственные вектора. Погрешности близки к нулю, это говорит о том, что ответ достаточно точен.

\end{document}