iterative_point_recovery/documentation/iterative_point_recovery_documentation-russian.tex

\documentclass[14pt%,showframe%
]{ipr_doc}
\usepackage{fix-cm}%   fix of Computer Modern font DO NOT MOVE!!!
\usepackage{calc}%     simple arithmetic in expressions
\usepackage{etoolbox}% some Latex interfaces
\usepackage{longtable,multirow}% tables
\usepackage{float,adjustbox,placeins,caption}% processing of float objects
%
% page geometry
%
\usepackage[
    top    = 0.06734007\paperheight,
    bottom = 0.06734007\paperheight,
    right  = 0.1190476\paperwidth,
    left   = 0.0952381\paperwidth
]{geometry}
%
% language and fonts
%
\usepackage{amsmath,amsfonts,amssymb,xfrac}
\usepackage[cmintegrals,cmbraces]{newtxmath}
\usepackage{xltxtra,polyglossia,csquotes}
\usepackage{verbatim,fancyvrb,framed}
\usepackage{relsize}
\setmainlanguage{russian}
\setotherlanguage{english}
\setkeys{russian}{babelshorthands=true}
\defaultfontfeatures{Scale=MatchLowercase,Mapping=tex-text}
\input{fonts/font_settings-IBM_Plex.tex}
% \input{fonts/font_settings-Computer_Modern.tex}
% \input{fonts/font_settings-my_fonts.tex}
%
% paragraphs and align
%
\usepackage{indentfirst,framed}
\frenchspacing\sloppy\raggedbottom
\setlength{\parindent}{0.0604762\paperwidth}%
%%%%% additional colontitles settings
\RequirePackage{fancyhdr}
\fancyhf{}\renewcommand{\headrulewidth}{0pt}
\fancyfoot{}
\fancyfoot[R]{\thepage}
\pagestyle{fancy}
%
% references and toc
%
\RequirePackage{hyperref}
\RequirePackage{xcolor}
\definecolor{DarkBlue}{rgb}{0,0,0.5}
\hypersetup{bookmarksnumbered,colorlinks=true,linkcolor={black},
            urlcolor=DarkBlue,citecolor={black}}
\makeatletter\renewcommand{\Hy@numberline}[1]{#1. }\makeatother
\let\savenumberline\numberline\relax\def\numberline#1{\savenumberline{#1.}}
\setcounter{tocdepth}{4}
%%%%% обеспечение меток для элементов списков
\makeatletter%
\def\itemlabel#1#2{{\phantomsection\def\@currentlabel{#2}\label{#1}}}%
\makeatother%
%
% lists
%
\usepackage{enumitem}
\usepackage{dirtree}
%
% figures and graphics
%
\RequirePackage{subfigure,graphicx,wrapfig}
\graphicspath{{images/}}

\newcommand{\pnt}[1]{\symbfup{#1}}%     точка
\newcommand{\vct}[1]{\vec{#1}}%         вектор
\newcommand{\sofs}[1]{\symbfsfup{#1}}%  множество множеств
\newcommand{\sofsofs}[1]{\symfrak{#1}}% множество множеств множеств
\newcommand{\prop}[1]{\symtt{#1}}%      высказывание (логическое выражение)
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\verbI}[1]{\textit{\Verb|#1|}}%
\newcommand{\NmCnvDescript}%
    {\addtolength{\leftskip}{0.0604762\paperwidth}%
     \setlength{\parindent}{-0.0604762\paperwidth}}%
\newenvironment{ImpNote}
    {\setlength{\parindent}{0.0604762\paperwidth}%
     \setlength{\LTleft}{\parindent}%
     \setlength{\LTpre}{\parsep}\setlength{\LTpost}{\parsep}%
     \begin{longtable}{|p{\linewidth-\tabcolsep-1\parindent}}%
     \noindent\textsf{\textbf{Важное замечание:}}}%
    {\end{longtable}}

\title{Итеративное восстановление точки в $n$\nobreakdash-мерном пространстве
по $n+1$~точкам и недостоверным расстояниям}
\author{hk@r4in.tk\\ mns@r4in.tk}
\begin{document}
\maketitle

\section{Введение}
\label{sec:introduction}

Проблема восстановления координат точки в пространстве в целом проблемой не
является. Формулировка задачи выглядит следующим образом: в гладком эвклидовом
пространстве $\symbb{R}^n$ существует точка
${\pnt{x}=\left\{ x_{i}\right\}_{i=0}^{n-1}}$, координаты которой неизвестны,
но известны координаты ${n+1}$ других точек
${\sofs{C}=\left\{\pnt{c}_{j}\right\}_{j=0}^{n}}$, не лежащих в одной
гиперплоскости, а также расстояния ${R=\left\{r_{j}\right\}_{j=0}^{n}}$ от них
до точки $\pnt{x}$. Очевидно, что восстановление координат точки $\pnt{x}$
осуществляется решением системы уравнений:
\begin{equation}
\label{eq:naive_approach_system}
    \begin{cases}
        \,r_{0}^{2}=\sum\limits_{k=0}^{n-1}\left(x_{k}-c_{0,k}\right)^{2}\\
        \,r_{1}^{2}=\sum\limits_{k=0}^{n-1}\left(x_{k}-c_{1,k}\right)^{2}\\
        \hfil\cdots\\
        \,r_{n}^{2}=\sum\limits_{k=0}^{n-1}\left(x_{k}-c_{n,k}\right)^{2}
    \end{cases}
\end{equation}

\noindent%
Решение такой системы при~${n=2}$ не представляет проблемы. При~${n=3}$ оно уже
сложнее. При дальнейшем увеличении~$n$ сложность решения такой системы
уравнений растёт очень быстро\footnote{Точная оценка вычислительной сложности
решения таких систем уравнений в зависимости от~$n$ не приводится, так как
зависит от конкретного алгоритма.}. Учитывая, что в настоящее время размерность
может достигать весьма больших значений от сотен и более, а кроме того может
определяться самой структурой данных и меняться в ходе их обработки,
представляется целесообразным выработать общий алгоритм восстановления точки,
с приемлемым (и желательно контролируемым) временем выполнения для больших~$n$.

Ситуация осложняется тем, что в прикладных задачах точность измерения
расстояния может быть разной. Так, например, четыре радиоприёмника, оценивая
расстояние до источника по силе сигнала, могут давать значения радиусов,
которые не имеют единой точки пересечения, в результате чего решение такой
системы уравнений будет комплексным, а следовательно неподходящим для
практического использования. В подобных случаях необходимо не точное решение
системы уравнений~\eqref{eq:naive_approach_system}, а некое, желательно
наилучшее, приближение. Одна из таких ситуаций приведена на рис.\ref{fig:fig1}.
\begin{wrapfigure}{R}{0.5\textwidth}
\includegraphics[width=\linewidth]{fig1.eps}%
\captionsetup{format=hang}%
\caption{Ситуация при ${n=2}$,\newline
${\pnt{c}_{0}=\left\{-0.976,0.401\right\}}$,\newline
${\pnt{c}_{1}=\left\{-0.251,-0.506\right\}}$,\newline
${\pnt{c}_{2}=\left\{0.368, 0.327\right\}}$,\newline
${R=\left\{0.98,0.653,0.816\right\}}$.}%
\vspace{-1\baselineskip}   % IBM Plex
% \vspace{-3\baselineskip}   % Computer Modern
\label{fig:fig1}
\end{wrapfigure}
Представляется справедливым, что искомая точка вероятнее всего принадлежит
области~$a$, ограниченной $1$\nobreakdash-сферами с центрами в~$\pnt{c}_{i}$ и
радиусами~$r_{i}$ соответственно. Данная гипотеза основана на том, что для
любой точки внутри области~$a$ сумма расстояний до поверхностей сфер меньше,
чем вне области~$a$. В идеальном случае, если радиусы сфер абсолютно точны, то
расстояния от искомой точки до поверхностей сфер равны~$0$ в соответствии со
смыслом системы уравнений~\eqref{eq:naive_approach_system}. Уточнения и
раскрытие данного утверждения приведены ниже с рассмотрением случаев, когда
область~$a$ может быть неограниченной, включая случай, когда ни одна пара сфер
не имеет общих точек.

Также нельзя не отметить, что в прикладных задачах часто есть возможность
получить данные не с ${n+1}$~датчиков, дающих неточные значения, а с большего
их (датчиков) количества. С одной стороны может показаться, что решение
системы~\eqref{eq:naive_approach_system} при этом усложнится и это так, но если
отталкиваться от иных подходов, то в прикладной сфере дополнительная информация
может (и должна) улучшать приближение искомой точки, что будет показано в
разделе~\ref{subsubsec:prototype_regress_estimation}.

Здесь и далее иллюстрации для наглядности приводятся для случаев~${n=2}$,
однако, подразумевается, что все изложенное справедливо для
любых~${n\in\symbb{N}}$ и, соответственно, ${(n-1)}$\nobreakdash-сфер.

Таким образом, целью данного документа является описание алгоритма, который
получает в качестве аргументов:
\begin{enumerate}
    \item Размерность пространства~--~${n\in\symbb{N}}$;
    \item Координаты ${m}$~точек
        (${m\in\symbb{N}}$~и~${m>n}$)\footnote{\label{note:m_restriction}%
        Ограничение~${m>n}$ очевидно и продиктовано тем, что при~${m<n+1}$
        существует сфера (множество точек) такая, что искомая точка
        равновероятно находится в любой точке принадлежащей поверхности
        такой сферы.} в данном пространстве~--~%
        ${\sofs{C}=\left\{\pnt{c}_{i}\in\symbb{R}^{n}\right\}_{i=0}^{m-1}}$;
    \item Недостоверные расстояния от точек~$\sofs{C}$ до искомой
        точки~--~${R=\left\{r_{i}\in\symbb{R}\right\}_{i=0}^{m-1}}$.
\end{enumerate}

\noindent%
Результат работы алгоритма это
точка~${\pnt{x}=\left\{x_{i}\right\}_{i=0}^{n-1}}$, являющаяся наилучшим
приближением искомой точки. Это расплывчатое определение дано в связи с тем,
что при описании алгоритма умышленно не будет использоваться <<настоящая>>
искомая точка, так как в практических задачах, для решения которых
вырабатывается алгоритм, искомая точка всегда неизвестна даже в случае
полностью контролируемых условий оценки алгоритма. В
разделе~\ref{subsec:prototype_testing} при оценке прототипа будет использована
<<настоящая>> искомая точка для вычисления статистики по ошибке приближения, но
при этом необходимо понимать, что хороший алгоритм должен демонстрировать
прямую корреляцию качества своей работы и точности датчиков выдающих
расстояния~$R$, а в таком случае оценка расстояния между алгоритмически
вычисленной и искомой точкой будет не оценкой алгоритма, а оценкой точности
датчиков, причём косвенной. В общем же случае лучше говорить, что алгоритм
рассчитывает координаты точки, где наиболее вероятно нахождение искомой точки;
либо полученное приближение достаточно точно для принятия решения и дальнейших
действий. Грубо говоря, если поставить целью <<уничтожение>> искомой точки
бомбой, которая при детонации сохраняет разрушающее воздействие в радиусе
$100$~метров от эпицентра взрыва, то достаточно того, чтобы алгоритмически
рассчитанная точка была менее чем в ста метрах от искомой.

\section{Алгоритм}
\label{sec:algorithm}

\subsection{Предварительные утверждения}
\label{subsec:preliminary_propositions}

В данном разделе приведены самоочевидные или доказуемые утверждения, постулаты,
леммы, отношение которых к описываемому алгоритму на данном этапе изложения
может быть неясно. Поэтому вы можете при первом чтении пропустить этот раздел и
перейти к общему описанию
алгоритма~(разд.~\ref{subsec:general_algorithm_description}) и в ходе его
чтения по ссылкам вернуться в этот раздел при необходимости.

\subsubsection{Кратчайшее расстояние от точки до поверхности сферы в гладком
эвклидовом пространстве}
\label{subsubsec:shortest_distance_to_sphere_surface}

Определим функцию ${\delta\left(\pnt{a},\pnt{b}\right)}$ как эвклидово
расстояние:
\begin{equation}
\label{eq:delta}
    \delta\left(\pnt{a},\pnt{b}\right):\Leftrightarrow\sqrt[2]{
        \sum\limits_{i=0}^{n-1}\left(a_{i}-b_{i}\right)^{2}}
\end{equation}

\noindent%
Тогда минимальное расстояние~$\mu$ от точки $\pnt{a}$ до поверхности
${(n-1)}$\nobreakdash-сферы с центром в~$\pnt{c}$ и радиусом~$r$:
\begin{gather}
    \sofs{S}:\Leftrightarrow\left\{
       \left.\pnt{s}\in\symbb{R}^{n}\right|\delta\left(\pnt{c},\pnt{s}\right)=r
    \right\}\notag\\
    \pnt{s}_{\mu}=
        \argmin_{\pnt{s\in\sofs{S}}}\delta\left(\pnt{a},\pnt{s}\right)\notag\\
    \mu =\delta\left(\pnt{a},\pnt{s}_{\mu}\right)\notag\\
    \mu\left(\pnt{a},\pnt{c},r\right):\Leftrightarrow\left|
        \delta\left(\pnt{a},\pnt{c}\right)-r\right|\label{eq:mue}
\end{gather}

\noindent%
Формула~\eqref{eq:mue} это удобное следствие из определения сферы, позволяющее
алгоритмически эффективно рассчитывать~$\mu$ без вычисления
точки~$\pnt{s}_{\mu}$. Также необходимо помнить, что при смене метрики на иную
формула~\eqref{eq:mue} может перестать работать. Особенно надо быть осторожным
при смене метрики на непринадлежащую метрикам Минковского или даже на
некоммутирующую функцию расстояния, и учитывать, что при смене функции
расстояния должна меняться не только формула, но и определение сферы. Это
связано с тем, что формула (3) в данном случае следует из определения сферы
через метрику, или, иными словами, в данном случае формула~\eqref{eq:mue}
справедлива потому, что $\delta$~и~$r$ косвенно определены одна через
другую~(circulus vitiosus!).

В худших случаях смена функции расстояния может привести к тому, что ${n+1}$
сфер могут иметь более одной общей точки и/или что точный способ нахождения
кратчайшего расстояния от точки до сферы может быть неизвестен, сложен для
машинного вычисления, или реализовано только приблизительное его вычисление
через поиск~${\argmin_{\pnt{s}}\delta\left(\pnt{a},\pnt{s}\right)}$.

В дальнейшем в данном документе используется и подразумевается эвклидова
метрика.

\subsubsection[Уравнение координат пересечения
\texorpdfstring{$(n-1)$}{(n-1)}-сферы с прямой, проходящей через центр
\texorpdfstring{$(n-1)$}{(n-1)}-сферы]{Уравнение координат пересечения
$(n-1)$\nobreakdash-сферы с прямой, проходящей через центр
$(n-1)$\nobreakdash-сферы}
\label{subsubsec:line-sphere_intersection_equation}

Для нахождения координат точки пересечения $(n-1)$\nobreakdash-сферы в
пространстве~$\symbb{R}^{n}$ с прямой необходимо решить систему уравнений:
\begin{equation}
\label{eq:line-sphere_system}
    \begin{array}{ll}
        \begin{cases}
            \,\frac{x_{0}-p_{0}}{v_{0}}=\frac{x_{1}-p_{1}}{v_{1}}\\
            \,\frac{x_{0}-p_{0}}{v_{0}}=\frac{x_{2}-p_{2}}{v_{2}}\\
            \hfil\cdots\\
            \,\frac{x_{0}-p_{0}}{v_{0}}=\frac{x_{n-1}-p_{n-1}}{v_{n-1}}\\
            \,r^{2}=\sum\limits_{i=0}^{n-1}\left( x_{i}-c_{i}\right) ^{2}
        \end{cases}&
        \begin{aligned}
            &&\text{, }&\text{где}\hfil&&\\
            &&\pnt{x}&=\left\{x_{i}\right\}_{i=0}^{n-1}&\text{--- }&%
                \text{точка пересечения;}&\\
            &&\pnt{p}&=\left\{p_{i}\right\}_{i=0}^{n-1}&\text{--- }&%
                \text{точка принадлежащая прямой;}&\\
            &&\vec{v}&=\left\{v_{i}\right\}_{i=0}^{n-1}&\text{--- }&%
                \text{вектор коллинеарный прямой;}&\\
            &&\pnt{c}&=\left\{c_{i}\right\}_{i=0}^{n-1}&\text{--- }&%
                \text{центр сферы;}&\\
            &&r&&\text{--- }&\text{радиус сферы;}&\\
            &&n&&\text{--- }&\text{размерность пространства.}&
        \end{aligned}
    \end{array}
\end{equation}

\noindent%
Полагаю излишним приводить решение данной системы уравнений, но необходимо
отметить, что в период первоначального составления документа математические
программы актуальных версий (Wolfram Mathematica, Mathcad Prime) при~${n>3}$
дают неверные, но приближенные решения системы
уравнений~\eqref{eq:line-sphere_system}. Так в ходе работы над алгоритмом было
проведено ручное решение и декомпозиция системы~\eqref{eq:line-sphere_system}
вплоть до~${n=5}$, что и обнаружило неточность машинных решений системы.
Поэтому в случае необходимости модификации алгоритма и решения подобных систем
уравнений осторожно относитесь к результатам машинного решения уравнений, если
нет полной уверенности в точности алгоритма решения. Далее приведена
окончательная формула искомой точки с декомпозицией (внимательно отнеситесь к
индексам!):
\begin{equation}
\label{eq:line-sphere_intersection}
\pnt{x}=\left\{
    x_{i}=p_{i}+
    \frac{v_{i}\left(l\pm\sqrt[2]{e^{2}-4df}\right)}{2dv_{0}}
\right\}_{i=0}^{n-1}\text{,}
\end{equation}

\noindent где
\begin{equation*}
    \begin{array}{ll}
        g=\sum\limits_{i=1}^{n-1}v_{i}^{2} & d=g+v_{0}^{2}\\
        h=\sum\limits_{i=1}^{n-1}\left(c_{i}-p_{i}\right)^{2}&%
            e=2\left(p_{0}g+v_{0}\left(c_{0}v_{0}+k\right)\right)\\
        k=\sum\limits_{i=1}^{n-1}v_{i}\left(c_{i}-p_{i}\right)\qquad&%
            f=v_{0}^{2}\left(c_{0}^{2}-r^{2}+h\right)+%
                                             p_{0}\left(p_{0}g+2v_{0}k\right)\\
        &l=2v_{0}\left(k+v_{0}\left(c_{0}-p_{0}\right)\right)
    \end{array}
\end{equation*}

Из формулы\footnote{Обратите внимание, что $d$~это дополнение суммы~$g$ до
полной размерности~$n$ вектора~$\vec{v}$; а $l$~это произведение ${2v_{0}}$~на
дополнение суммы~$k$ до полной размерности $n$ вектора~$\vec{v}$ и
точек~$\pnt{p}$,~$\pnt{c}$. Данное замечание может быть полезно при реализации
алгоритма.}~\eqref{eq:line-sphere_intersection} и геометрического смысла
системы~\eqref{eq:line-sphere_system} очевидно, что любая прямая проходящая
через центр сферы с~${r>0}$ в гладком эвклидовом пространстве имеет две точки
пересечения с поверхностью сферы. Поэтому определим
функцию~${\chi\left(\pnt{p},\vec{v},\pnt{c},r\right)}$ как
\begin{equation}
\label{eq:chi}
\chi\left(\pnt{p},\vec{v},\pnt{c},r\right):\Leftrightarrow%
\left\{\pnt{x}_{0},\pnt{x}_{1}\right\}\text{,}
\end{equation}

\noindent%
где
\begin{align*}
\pnt{x}_{0}=\left\{
    x_{i}=p_{i}+
    \frac{v_{i}\left(l+\sqrt[2]{e^{2}-4df}\right)}{2dv_{0}}
\right\}_{i=0}^{n-1}\,\,\,\text{ и }\,\,\,
\pnt{x}_{1}=\left\{
    x_{i}=p_{i}+
    \frac{v_{i}\left(l-\sqrt[2]{e^{2}-4df}\right)}{2dv_{0}}
\right\}_{i=0}^{n-1}
\end{align*}

\paragraph[Замечание]{Замечание.}\label{par:note_about_restrictions}Так как
ожидается, что~${\pnt{x}\in\symbb{R}^{n}}$, то
формула~\eqref{eq:line-sphere_intersection} влечёт явные ограничения.
Так~${\pnt{x}\notin\symbb{R}^{n}}$ в следующих случаях:
{\setlist[enumerate]{label*=(\alph*)}
    \begin{enumerate}[leftmargin=2\parindent]
        \item ${v_{0}=0}$, т.~е первая компонента вектора~$\vec{v}$
            системы~\eqref{eq:line-sphere_system} равна нолю. В
            геометрическом смысле вектор~$\vec{v}$ ортогонален абсциссе.
        \item $\|\vec{v}\|=0\Rightarrow{d=0}$, т.~е норма
            вектора~$\vec{v}$ и следовательно сумма~$d$ квадратов компонент
            вектора~$\vec{v}$ системы~\eqref{eq:line-sphere_system} в
            формуле~\eqref{eq:line-sphere_intersection} равны нолю. В
            геометрическом смысле вектор~$\vec{v}$ имеет нулевую длину, в
            связи с чем его направление не определено.
        \item ${e^{2}-4df<0}$, т.~е подкоренное выражение
            формулы~\eqref{eq:line-sphere_intersection} отрицательно. В
            геометрическом смысле это значит, что поверхность сферы не имеет
            общих точек с прямой в гладком эвклидовом пространстве. Может
            показаться, что такое невозможно раз уж прямая проходит через центр
            сферы, но как всегда есть нюансы: во\nobreakdash-первых это
            утверждение верно не для всех сочетаний размерностей; а,
            во\nobreakdash-вторых, особенности обработки чисел с плавающей
            запятой в практических реализациях алгоритма могут давать
            результаты не соответствующие абстрактным математическим ожиданиям.
    \end{enumerate}
}

\subsection{Общее описание алгоритма}
\label{subsec:general_algorithm_description}

В целом алгоритм является вариантом градиентного спуска с дополнительной
информацией. Стоит напомнить, что согласно разделу~\ref{sec:introduction}
аргументами алгоритма являются:
\begin{itemize}
    \item размерность пространства ${n\in\symbb{N}}$;
    \item координаты ${m}$~точек~%
        ${\sofs{C}=\left\{\pnt{c}_{i}\in\symbb{R}^{n}\right\}_{i=0}^{m-1}}$,
        ${m\in\symbb{N}}$~и~${m>n}$;
    \item недостоверные расстояния~${R=\left\{r_{i}\right\}_{i=0}^{m-1}}$.
\end{itemize}

\noindent%
Пары <<точка\nobreakdash-расстояние>> рассматриваются как описание множества
сфер~${\sofsofs{S}=%
\left\{\left\{\pnt{c}_{i},r_{i}\right\}\right\}_{i=0}^{m-1}}$~%
(<<центр\nobreakdash-радиус>>), то есть постулируется взаимно однозначное
соответствие по индексу известной точки и расстояния от неё до искомой точки.

Далее приводится пошаговая схема алгоритма:
\begin{enumerate}
    \item Методом~$\phi$~(разд.~\ref{subsubsec:first_approx_selection}~%
        \eqref{eq:phi}) выбирается начальное приближение искомой точки.
\begin{equation*}
\pnt{p}=\phi\left(\sofs{C}\right)
\end{equation*}
    \item\itemlabel{item:the_second_step}{2} Выбирается
        сфера~${\left\{\pnt{c}_{j},r_{j}\right\}}$, поверхность которой
        наиболее удалена по~$\mu$~(разд.~%
        \ref{subsubsec:shortest_distance_to_sphere_surface}~\eqref{eq:mue})
        от~$\pnt{p}$.
\begin{equation*}
\forall\left\{\pnt{c},r\right\}\in\sofsofs{S}\,:\,\bigwedge\limits_{i=0}^{m-1}
    \mu\left(\pnt{p},\pnt{c}_{j},r_{j}\right)\geqslant
    \mu\left(\pnt{p},\pnt{c}_{i},r_{i}\right)
\end{equation*}
    \item\itemlabel{item:the_third_step}{3} Методом~%
        $\chi$~(разд.~\ref{subsubsec:line-sphere_intersection_equation}~%
        \eqref{eq:chi}) рассчитывается пара
        точек~${\sofs{Q}=\left\{\pnt{q}_{0},\pnt{q}_{1}\right\}}$,
        принадлежащих сфере~${\left\{\pnt{c}_{j},r_{j}\right\}}$ и прямой
        проходящей через точки~$\pnt{c}$~и~$\pnt{p}$.
\begin{equation*}
\sofs{Q}=\left\{\pnt{q}_{0},\pnt{q}_{1}\right\}=
\chi\left(\pnt{p},\vec{v},\pnt{c}_{j},r_{j}\right)
\end{equation*}
    \item\itemlabel{item:chosing_point_from_pair}{4} К результатам~$\chi$
        применяется процедура~$\Lambda$, которая выбирает из пары~$\sofs{Q}$
        точку, для которой значение~%
        $\lambda$~(разд.~\ref{subsubsec:point_quality}~\eqref{eq:lambda})
        больше, или, иными словами, рассчитывается показатель качества
        приближения и выбирается наилучшее приближение искомой
        точки из пары~${\left\{\pnt{q}_{0},\pnt{q}_{1}\right\}}$.
\begin{equation}
\label{eq:chosing_point_from_pair}
\Lambda\left(\sofs{Q},\sofs{C},R\right):\Leftrightarrow
    \left(\left.\pnt{t}\in\sofs{Q}\,\right|%
        \,\forall\pnt{q}\in\sofs{Q}\,:%
        \,\bigwedge\limits_{i=0}^{\left|\sofs{Q}\right|-1}%
        \lambda\left(\pnt{t},\sofs{C},R\right)\geqslant%
        \lambda\left(\pnt{q}_{i},\sofs{C},R\right)\right)
\end{equation}
    \item\itemlabel{item:new_point_step}{5}%
        $\pnt{p}$~присваивается значение~$\Lambda$.
\begin{equation*}
\pnt{p}=\Lambda\left(\sofs{Q},\sofs{C},R\right)
\end{equation*}
    \item Проверяется утверждение~$\prop{Z}$~%
        (разд.~\ref{subsubsec:the_last_iteration_condition}), если
        $\prop{Z}$~истинно, осуществляется переход к
        шагу~\ref{item:the_last_step}.
    \item\itemlabel{item:next_iteration}{7}%
        Переход к шагу~\ref{item:the_second_step}.
    \item\itemlabel{item:the_last_step}{8}%
        Методом~$\psi$~(разд.~\ref{subsubsec:point_refinement}~\eqref{eq:psi})
        осуществляется уточнение приближения искомой точки.
\begin{equation*}
\pnt{x}=\psi\left(\pnt{p},\sofs{C},R\right)
\end{equation*}
\end{enumerate}

\subsection{Предположения}
\label{subsec:assumptions}

В данном разделе приведены неочевидные предположения, доказуемость которых
неустановлена, но они обоснованы рядом аргументов или проверены эмпирическим
путём. При этом надо понимать, что результат эмпирической проверки может быть
статистической флуктуацией.

\subsubsection{Выбор начального приближения искомой точки}
\label{subsubsec:first_approx_selection}

В принципе строгих ограничений выбора начального приближения искомой точки не
выявлено. В случае если расстояния до искомой точки известны точно и являются
абсолютно достоверными, то никаких ограничений на выбор начального приближения
нет и можно брать случайную точку. Но если расстояния до искомой точки
недостоверны, то в ряде случаев при <<неудачном>> выборе начального приближения,
результат работы алгоритма может не быть <<лучшим>>, а только <<хорошим>>
приближением. Это связано с тем, что в данном ряде случаев может быть не одна,
а несколько областей, в которых вероятно присутствие искомой точки. Если
говорить в терминах градиентного спуска, то может быть более одного глобального
экстремума функции~$\lambda$ и/или ещё и несколько локальных экстремумов, в
один из которых и приведёт алгоритм, в случае <<плохого>> выбора начального
приближения. В связи с этим были изучены несколько подходов к выбору начального
приближения при прочих равных, и проверены эмпирически на нерепрезентативной
выборке:
\begin{enumerate}
    \item Использовать в качестве начального приближения один из
        центров~$\sofs{C}$.
    \item Использовать в качестве начального приближения одну из вершин
        параллелограмма (естественно, $n$\nobreakdash-мерного), грани которого
        являются касательными к сферам в различных точках.
    \item\itemlabel{item:first_point_select_approach}{3} Использовать в
        качестве приближения усреднение по точкам~$\sofs{C}$.
\end{enumerate}

\noindent%
В данном документе не приводится статистика проверок предложенных методов, в
связи с тем, что (1) данный список не исчерпывающий, был проверен примерно
десяток подходов, но записи о них производились на черновиках и утрачены; (2)
выборка при проверке была нерепрезентативна и при принятии решения бесполезна;
(3) ни один из проверенных способов не показал полного избегания локальных
экстремумов, то есть независимо от выбора подхода возникают ситуации, при
которых алгоритм завершается не в глобальном, а в локальном экстремуме
функции~$\lambda$.

Лучший эмпирический результат показал и наиболее обоснованным представляется
метод~\ref{item:first_point_select_approach}, в связи с чем функция~$\phi$
определена как
\begin{equation}
\label{eq:phi}
\phi\left(\sofs{C}\right):\Leftrightarrow%
\left\{\left.\sum\limits_{i=0}^{m-1} c_{i,j}\right/ m\right\}_{j=0}^{n-1}
\end{equation}

\noindent%
В формуле~\eqref{eq:phi} используется среднее арифметическое, но допустимо
поэкспериментировать с другими степенными средними, а при достаточно больших
значениях~$n$ можно испытать и нестепенные средние. По крайней мере, на момент
написания документа, не было сформулировано аргументов против использования
других средних.

В практической реализации алгоритма, если время принятия решения позволяет или
есть возможность параллельных вычислений, можно снизить вероятность <<плохого>>
выбора начального приближения путём вычисления алгоритма из нескольких начальных
приближений подобранных разными методами, а затем выбрать из нескольких
результатов приближение с наилучшим
качеством~(см.~разд.~\ref{subsubsec:point_quality}). Так, например, в прототипе
алгоритма в качестве начального приближения берутся общее усреднение по
известным точкам и попарные усреднения со сдвигом, в последствии выбирается
наилучшее конечное приближение.

\subsubsection{Критерий качества точки}
\label{subsubsec:point_quality}

Предполагается, что в искомой точке расстояния до всех сфер равны нолю, а для
наилучшего приближения минимальны, в связи с чем критерий качества точки может
быть выражен очень разными способами, дающими, в общем, сходные результаты.
Поэтому в качестве критерия был выбран самый простой, а именно отрицательная
сумма расстояний от точки до поверхности всех сфер.
\begin{equation}
\label{eq:lambda}
\lambda\left(\pnt{p},\sofs{C},R\right):\Leftrightarrow%
-\sum\limits_{i=0}^{m-1}\mu\left(\pnt{p},\pnt{c}_{i},r_{i}\right)
\end{equation}

Отрицательная сумма взята исключительно из эстетических соображений, чтобы
показатель качества рос с приближением к точке пересечения сфер, в которой он
очевидно обращается в ноль, а если расстояния недостоверны, то просто
максимизируется.

Также как и выбор начального приближения точки, данная функция качества была
проверена эмпирически среди других подходов, показала хороший результат, имеет
достаточно очевидную и твёрдую аргументацию под собой, но не доказательство. Её
можно сменить, например, на средние расстояний или иным образом, исходя из иных
предположений о качестве точки.

\subsubsection{Условие последней итерации}
\label{subsubsec:the_last_iteration_condition}

Условием последней итерации является истинность утверждения~$\prop{Z}$. Само
утверждение~$\prop{Z}$ сильно зависит от решаемой задачи и обстановки
исполнения алгоритма. Поэтому будет рассмотрено три варианта
утверждения~$\prop{Z}$, в зависимости от надёжности значений~$R$ и требований
обстановки.

\paragraph[Утверждение~\texorpdfstring{$\prop{Z}$}{Z} при абсолютно точных
значениях~\texorpdfstring{$R$}{R}]{Утверждение~$\prop{Z}$ при абсолютно точных
значениях~$R$.}

Так, в случае если расстояния от известных точек до искомой достоверны и
абсолютно точны\footnote{В контексте документа абсолютно точными можно считать
значения~$R$ при абстрактном анализе алгоритма без использования актуальных
значений, либо ситуацию, когда ошибка измерения в датчике\nobreakdash-источнике
значений~$R$ существенно меньше машинного~$\varepsilon$~(эпсилон).}, то
последней считается итерация, после которой сумма расстояний от найденного
приближения до поверхности всех сфер равна нолю или
машинному~$\varepsilon$~(эпсилон).
\begin{equation*}
\label{eq:zed_without_uncertainty}
\prop{Z}\Leftrightarrow%
\sum\limits_{i=0}^{m-1}\mu\left(\pnt{p},\pnt{c}_{i},r_{i}\right)=0
\end{equation*}

\noindent%
При истинности такого утверждения шаг~\ref{item:the_last_step} алгоритма можно
пропустить, так как уточнять приближение не требуется, да и невозможно. Но
вероятность возникновения такой ситуации в реальности стремиться к нолю,
поэтому рассмотрим другое утверждение~$\prop{Z}$ при ухудшении обстановки.

\paragraph[Утверждение~\texorpdfstring{$\prop{Z}$}{Z} при недостоверных
значениях~\texorpdfstring{$R$}{R} и известной допустимой ошибке
приближения~\texorpdfstring{$\Delta$}{Дельта}]%
{Утверждение~$\prop{Z}$ при недостоверных значениях~$R$ и известной допустимой
ошибке приближения~$\Delta$.}

Предположим, множество~$R$ содержит заведомо неточные расстояния, но для
принятия решения, необходимо приближение, расположенное не далее, чем
в~$\Delta$ от искомой точки. В таком случае, учитывая, что на
шаге~\ref{item:new_point_step} алгоритма
${\exists\sofs{S}_{i}\in\sofsofs{S}\,:\,\pnt{p}\in\sofs{S}_{i}\Rightarrow%
\mu\left(\pnt{p},\pnt{c}_{i},r_{i}\right)=0}$, то если расстояния от данного
приближения до всех из $m-1$~приближений, которые могут быть получены
относительно других сфер, меньше~$\Delta$, утверждение~$\prop{Z}$ истинно.
\begin{equation*}
\label{eq:zed_with_uncertainty_and_delta}
\prop{Z}\Leftrightarrow%
\bigwedge\limits_{i=0}^{m-1}\mu\left(\pnt{p},\pnt{c}_{i},r_{i}\right)<\Delta
\end{equation*}

\noindent%
В зависимости от задачи и обстановки можно использовать строгое и нестрогое
сравнение.

Необходимо понимать, что использование такого утверждения возможно только
тогда, когда погрешность измерения в датчике\nobreakdash-источнике значений~$R$
существенно меньше~$\Delta$. Иными словами, если известно матожидание
погрешности датчиков\nobreakdash-источников~$R$, то допустимо использовать эту
величину с запасом~(например,~${2\times 3\sigma}$) в качестве~$\Delta$. Если же
$\Delta$~меньше погрешности датчиков\nobreakdash-источников значений~$R$,
возникнет ситуация, при которой состояние <<$\prop{Z}$ \textit{истинно}>>
недостижимо, в связи с чем рассмотрим наихудшую обстановку.

\paragraph[Утверждение~\texorpdfstring{$\prop{Z}$}{Z} при недостоверных
значениях~\texorpdfstring{$R$}{R} и отсутствии информации о допустимой ошибке
приближения]{Утверждение~$\prop{Z}$ при недостоверных значениях~$R$ и
отсутствии информации о допустимой ошибке приближения.}

Наихудшая ситуация, но и наиболее частая на практике: значения~$\sofs{C}$~и~$R$
недостоверны и информации о величине возможной ошибки нет и не предвидится. Для
этого было эмпирически выработано утверждение~$\prop{Z}$, которое может
показаться избыточным, однако, соответствуют неким ситуациям, возникшим в ходе
эксплуатации реализации алгоритма. В связи с вышеизложенным, если нет
уверенности в минимальной стабильности обстановки работы алгоритма,
рекомендуется использовать данное или ещё более строгое относительно данного
утверждение~$\prop{Z}$.
\begin{equation}
\label{eq:zed_with_total_uncertainty}
\prop{Z}\Leftrightarrow%
\left(\forall\lambda\in L\,:\,%
        \bigwedge\limits_{i=\omega-m^{2}}^{\omega}%
            \lambda_{max}\geqslant\lambda\left(%
                \pnt{p}_{i},\sofs{C},R\right)\right)\vee%
        \omega\geqslant\left(wm\right)\text{,}
\end{equation}

\noindent где
\begin{itemize}[leftmargin=2\parindent]
    \item[]$\omega$\kern1ex---\kern1ex номер текущей итерации алгоритма,
        увеличение~$\omega$ на единицу происходит на
        шаге~\ref{item:next_iteration} алгоритма;
    \item[]${L=\left\{
        \lambda\left(\pnt{p}_{i},\sofs{C},R\right)
        \right\}_{i=\omega-m^{2}}^{\omega}}$\kern1ex---\kern1ex множество
        значений функции~$\lambda$ для ${m^{2}}$ последних итераций,
        соответственно ${\pnt{p}_{i}}$~--~приближение $i$\nobreakdash-той
        итерации;
    \item[]${\left.\lambda_{max}\,\right|\,\forall\lambda\in%
        \left\{\lambda\left(
            \pnt{p}_{i},\sofs{C},R\right)\right\}_{i=0}^{\omega-1}\,:\,%
        \bigwedge\limits_{i=0}^{\omega-1}\lambda_{max}\geqslant\lambda\left(
        \pnt{p}_{i},\sofs{C},R\right)}$\kern1ex---\kern1ex максимальное
        значение функции~$\lambda$ среди всех итераций алгоритма,
        кроме последней;
    \item[]$w$\kern1ex---\kern1ex предопределённая константа, которая
        определяет максимально возможное количество итераций из расчёта
        на количество известных сфер, иными словами, если прошло
        ${\left(wm\right)}$~итераций, то производим уточнение~$\psi$ и
        возвращаем результат.
\end{itemize}

$w$~выбирается исходя из ограничений по времени и в прототипе определено
как~${100}$ на сферу (см.~раздел~\ref{subsubsec:prototype_settings}), а значит
прототип всегда завершается после ${100m}$ итераций и переходит к
уточнению~$\psi$. Очевидно, что $w$~должно выбираться так, что~${w>m}$, ведь
в ином случае становится бессмысленным сравнение с ${\lambda_{max}}$ для
последних ${m^{2}}$~итераций, либо должен быть снижен критерий количества
итераций без улучшения под~${m^{2}}$.

Данное условие обосновано только эмпирически и может быть изменено в
соответствии с иными представлениями об обстоятельствах влекущих завершение
работы алгоритма. Дополнительные соображения по выбору~$w$ в условиях строгих
ограничений на время исполнения алгоритма приведены
в~\hyperref[impNote:on_w]{замечании} к
разделу~\ref{subsubsec:prototype_settings}.

\subsubsection{Уточнение приближения последней итерации}
\label{subsubsec:point_refinement}

Учитывая, что все точки полученные как значение функции~$\chi$ принадлежат
поверхности одной из известных сфер, а при неточных значениях расстояний~$R$
сферы вероятнее всего не имеют единой точки пересечения, следовательно любое
приближение принадлежащее одной из сфер будет иметь ненулевое расстояние до
одной или более других сфер. В связи с этим имеет смысл уточнять приближение
полученное после установления истинности высказывания~$\prop{Z}$ таким образом,
чтобы в идеальном случае (когда расстояние от приближения до всех сфер равно
нолю) уточнение не перемещало точку~$\pnt{p}$. В числе прочих для этого
подходит усреднение по $m$~точкам, которые являются результатом выбора лучшего
приближения для каждой из известных сфер от текущего приближения, или в
символах:
\begin{equation}
\label{eq:psi}
\psi\left(\pnt{p},\sofs{C},R\right):\Leftrightarrow
    \left\{\left.\sum\limits_{i=0}^{m-1} t_{i,j}\right/ m\right\}_{j=0}^{n-1}
    \text{,}
\end{equation}
\noindent%
где
\begin{equation*}
\sofs{T}=\left\{
    \pnt{t}_{i}=\Lambda\left(
        \chi\left(\pnt{p},\vec{v},\pnt{c}_{i},r_{i}\right),\sofs{C},R\right)
\right\}_{i=0}^{m-1}
\end{equation*}
\noindent%
и $\Lambda$~---~процедура~\eqref{eq:chosing_point_from_pair}, определённая для
шага~\ref{item:chosing_point_from_pair} общего описания алгоритма в
разделе~\ref{subsec:general_algorithm_description}.

Данный подход выбирался исходя из ситуации полной неопределённости погрешности
датчиков\nobreakdash-источников~$R$ и даже более сильном условии, состоящим в
том, что сама искомая точка принципиально не определяема точно. Поэтому, исходя
из особенностей частной обстановки применения алгоритма, вполне возможно, что и
среднее арифметическое, и метод~$\Lambda$, и процедура уточнения в целом могут
быть изменены на релевантные специфичным условиям применения алгоритма.

\section{Прототип}
\label{sec:prototype}

Прототип представляет собой реализацию вышеописанного алгоритма на языке~C.
Прототип не является строго оптимальной реализацией алгоритма и предназначен
для проверки возможных изменений алгоритма и сравнения результатов
(регресс\nobreakdash-оценки). Но в целом, если к программному обеспечению не
предъявляется строгих требований по времени и пространству исполнения, то можно
использовать прототип <<как есть>>.

\subsection{Состав прототипа}
\label{subsec:prototype_content}

Получить копию прототипа можно по адресу:\\*%
{\small\href{https://ggs.void.r4in.tk/hk/%
iterative_point_recovery/archive/master.tar.gz}%
{\nolinkurl{https://ggs.void.r4in.tk/hk/%
iterative\_point\_recovery/archive/master.tar.gz}}}\\%
после чего распаковать полученный архив. Кроме того, при наличии установленной
СКВ Git (\href{https://git-scm.com}{\nolinkurl{https://git-scm.com}}) можно
получить копию прототипа командой\\*
{\small\centerline{%
\Verb|git clone https://ggs.void.r4in.tk/hk/iterative\_point\_recovery.git|}}

В состав прототипа входят следующие файлы и каталоги:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
    .2 documentation/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}%
        исходный код и сопутствующие файлы данного документа,
        см.~раздел~\ref{subsec:prototype_documentation_source}.
        \end{minipage}}.
    .2 examples/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}исходный
        код с примерами использования прототипа,
        см.~раздел~\ref{subsec:prototype_use_examples}.
        \end{minipage}}.
    .2 src/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}исходный код
        собственно прототипа,
        см.~раздел~\ref{subsec:prototype_prototype}.\end{minipage}}.
    .2 test\_suite/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}исходный
        код проверочного комплекта прототипа,
        см.~раздел~\ref{subsec:prototype_testing}.\end{minipage}}.
    .2 visualisation/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}набор
        сценариев для визуализации результатов тестирования,
        см.~раздел~\ref{subsec:prototype_testing}.\end{minipage}}.
    .2 Makefile\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}сценарий
        сборки прототипа,
        см.~раздел~\ref{subsec:prototype_prototype}.\end{minipage}}.
}}
\end{minipage}\end{samepage}

Далее рассмотрены составляющие прототипа, даны их краткие описания и
руководства по использованию.

\subsection{Прототип. Сборка и описание}
\label{subsec:prototype_prototype}

Основной блок прототипа представляет собой функцию на языке C, которая может
быть собрана в библиотеку или использована в виде исходного кода <<как есть>>.
К основному блоку прототипа относятся:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
    .2 \ldots.
    .2 src/.
        .3 include\_hd/.
            .4 iterative\_point\_recovery.clh\DTcomment{\\\hspace*{\fill}%
                \begin{minipage}[t]{0.6666667\linewidth} заголовочный (header)
                файл, содержащий объявления функций и структур прототипа,
                см.~раздел~\ref{subsubsec:prototype_functions_and_structures}.
                \end{minipage}}.
            .4 ptrc\_hd\_settings.clh\DTcomment{\\\hspace*{\fill}%
                \begin{minipage}[t]{0.6666667\linewidth} заголовочный (header)
                файл, содержащий настройки прототипа,
                см.~раздел~\ref{subsubsec:prototype_settings}.\end{minipage}}.
        .3 iterative\_point\_recovery.clc\DTcomment{\\\hspace*{\fill}%
                \begin{minipage}[t]{0.6666667\linewidth} файл, содержащий
                определения функций прототипа,
                см.~раздел~\ref{subsubsec:prototype_functions_and_structures}.
                \end{minipage}}.
    .2 \ldots.
    .2 Makefile\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}сценарий
        сборки прототипа в библиотеку,
        см.~раздел~\ref{subsubsec:prototype_build_and_install}.
        \end{minipage}}.
}}
\end{minipage}\end{samepage}

\subsubsection{Сборка и установка прототипа}
\label{subsubsec:prototype_build_and_install}

\paragraph[Сборка]{Сборка.}
\begin{samepage}
Для сборки по умолчанию необходимо перейти в каталог
\verb|iterative_point_recovery| и выполнить команду\par\nopagebreak
\indent\indent\verb|make|
\end{samepage}

\noindent Если команда завершена без ошибок, то в
каталоге \verb|iterative_point_recovery/build| появится
файл \verb|libIterPntRcv.so.|\verbI{I}\verb|.|\verbI{J} и несколько
несколько служебных файлов. В имени файла \verbI{I}~--~основная версия
библиотеки, а \verbI{J}~--~дополнительная.

При необходимости возможна сборка для отладки (debug) командой\par\nopagebreak
\indent\indent\verb|make debug|

Если при сборке указать переменную \verb|GPGPU_DEV_IDX=|\verbI{N}, например
так\par\nopagebreak
\indent\indent\verb|make GPGPU_DEV_IDX=0|\par
\noindent%
то, при наличии установленного пакета OpenCL\_helpers
(\href{https://ggs.void.r4in.tk/hk/OpenCL_helpers}%
{\nolinkurl{https://ggs.void.r4in.tk/hk/OpenCL\_helpers}}), кроме обычной
библиотеки будет собрана OpenCL\nobreakdash-библиотека с прототипом для
GPGPU\nobreakdash-устройства с индексом~\verbI{N} в системе. Если пакет
OpenCL\_helpers был установлен не в путь по умолчанию, то надо указать
актуальный путь в переменной \verb|OCLH_PATH=|\verbI{путь\_установки}. После
сборки с указанием переменной~\verb|GPGPU_DEV_IDX|, если сборка завершена без
ошибок, в каталоге \verb|iterative_point_recovery/build| появится появится
дополнительный
файл~\verb|libIterPntRcv-|\verbI{имя\_устройства\_GPGPU}\verb|.clso|.

\paragraph[Установка]{Установка.}
Установка осуществляется командой\par\nopagebreak
\indent\indent\verb|make install|\par
\noindent%
В результате будет создан каталог \verb|~/opt/iterative_point_recovery|, куда в
подкаталоги \verb|lib|, \verb|include_hd| будут скопированы файлы библиотеки и
заголовочные файлы соответственно. Затем целесообразно добавить каталог
\verb|~/opt/iterative_point_recovery/lib| в переменную
окружения~\verb|LD_LIBRARY_PATH|.

Можно изменить целевой путь если задать команду\par\nopagebreak
\indent\indent\verb|make PRFX_PATH=|\verbI{путь\_установки}\verb| install|

\paragraph[Удаление]{Удаление.}
Удаление производится командой\par\nopagebreak
\indent\indent\verb|make uninstall|\par
\noindent либо\par\nopagebreak
\indent\indent\verb|make PRFX_PATH=|\verbI{путь\_установки}\verb| uninstall|%
\par
\noindent если установка производилась не в каталог по умолчанию.


\subsubsection{Настройки прототипа}
\label{subsubsec:prototype_settings}

Настройка прототипа производится изменением макроопределений в
файле \verb|src/include_hd/ptrc_hd_settings.clh|:\par\medskip
{\NmCnvDescript \verb|_PTRC_VAL_T|\\* тип значений с плавающей точкой компонент
    точек и векторов. Допустимые значения \verb|half|, \verb|float|,
    \verb|double|, \verb|long double|. Учитывайте, поддерживается ли данный тип
    компилятором и математическими библиотеками или, иными словами, перегружены
    ли для данного типа операторы  \verb|+|, \verb|-|, \verb|*|, \verb|/| и
    функции \verb|sqrt()|, \verb|abs()|. Также учитывайте, что на момент
    написания данного документа тип \verb|long double| и более длинные чаще
    всего обрабатываются не аппаратно, а программно, что влечёт значительное
    увеличение времени расчётов. В прототипе данное макроопределение
    установлено в значение~\verb|flt32_t|.\par\medskip}
{\NmCnvDescript \verb|_PTRC_MAX_ITERATIONS_ON_SPHERE|\\* значение~$w$
    условия~$\prop{Z}$ (см.~разд.~\ref{subsubsec:the_last_iteration_condition}%
    ~\eqref{eq:zed_with_total_uncertainty}). В прототипе данное
    макроопределение установлено в значение~\verb|100|.
    \begin{ImpNote}
    \itemlabel{impNote:on_w} введение данной настройки может
    показаться бессмысленным, так как вероятность срабатывания
    условия~${\omega\geqslant\left(wm\right)}$~%
    (разд.~\ref{subsubsec:the_last_iteration_condition}%
    ~\eqref{eq:zed_with_total_uncertainty}) очень мала, но ненулевая. Для RTOS
    в условиях строгого ограничения времени эта настройка становится
    актуальной, поэтому рекомендуется использовать следующие подходы для
    выбора~$w$:
    \begin{equation*}
    w=\left\lfloor\frac{\left.\prop{CutOff}\right/
        \prop{ExecT}}{m}\right\rfloor\text{,}
    \end{equation*}\\
    где\\{\addtolength{\leftskip}{2ex}%
    $m$~---~количество известных сфер (датчиков\nobreakdash-источников
    расстояний);\par}\nointerlineskip\\{\addtolength{\leftskip}{2ex}%
    ${\prop{CutOff}}$~---~интервал времени отсечки восстановления точки (по
    истечении этого интервала результат восстановления теряет смысл). Может
    измеряться в секундах (чаще нано\nobreakdash- или микро\nobreakdash-) для
    гибридных архитектур процессоров или в тактах для традиционных
    архитектур;\par}\nointerlineskip\\{\addtolength{\leftskip}{2ex}%
    ${\prop{ExecT}}$~---~интервал времени выполнения (в тех же единицах,
    что и~${\prop{CutOff}}$) функции \verb|_ptrc_recoverPoint()|
    (см.~раздел~\ref{subsubsec:prototype_functions_and_structures}) при
    \verb|_PTRC_MAX_ITERATIONS_ON_SPHERE| определённом как~\verb|1|,
    аргументе~\verb|u64NofRuns| равном~\verb|1| и точном выходе по
    условию~${\omega\geqslant\left(wm\right)}$.\par}\nointerlineskip\\
    Оценка ${\prop{ExecT}}$ для традиционных архитектур процессоров
    должна показывать постоянное время отличающееся от запуска к запуску менее,
    чем на время одного такта процессора и может оцениваться по количеству
    машинных команд. Если такого не наблюдается или используется процессор
    гибридной архитектуры, то рекомендуется брать максимальное
    значение~${\prop{ExecT}}$ не менее чем от $10000$ замеров, так как
    практические оценки показывают, что кривая времени для гибридных архитектур
    достаточно сглаживается только на $10$\nobreakdash-ти тысячах и более
    замеров.
    \par\nointerlineskip\\
    При замерах необходимо учитывать контур размещения внутренних часов
    процессора, по возможности использовать замеры времени по часам на
    внутреннем контуре. Необходимо учитывать количество регистров часов и
    возможность множественных переполнений.\par\nointerlineskip\\
    Данный подход сформулирован исходя из пессимистичных соображений оценки
    времени и тактов исполнения, и даёт время/такты <<с запасом>>, что
    идеологически верно, однако при уверенности в стабильности работы
    архитектуры и константных оценках времени/тактов можно добавить оптимизма
    и, проведя поблочную оценку времени исполнения одной итерации алгоритма в
    прототипе, уточнить оценку приемлемого значения~$w$.
    \end{ImpNote}
    \par\medskip}
{\NmCnvDescript \verb|_PTRC_NONRECONSTRUCTABLE_PNT_ERR|\\* значение
    возвращаемое функцией в случае когда нет возможности сформировать
    приближение искомой точки или, иными словами это код ошибки <<точка не
    восстанавливаема>>. Такая ошибка возвращается в случае
    если~${m<n+1}$~(см.~сноску~\ref{note:m_restriction} на
    стр.~\pageref{note:m_restriction}); в случаях
    из~\hyperref[par:note_about_restrictions]{замечания} на
    стр.~\pageref{par:note_about_restrictions}; и если указано нулевое
    количество проверяемых начальных
    приближений~(см.~аргумент \verb|u64NofRuns| основной функции прототипа в
    разделе~\ref{subsubsec:prototype_functions_and_structures}). В прототипе
    данное макроопределение установлено в значение~\verb|73|.\par}
{\NmCnvDescript \verb|_PTRC_MEMALLOC_ERR|\\* значение функции, возвращаемое в
    случае ошибки выделения памяти. В прототипе данное макроопределение
    установлено в значение~\verb|-150|.\par}

\subsubsection{Функции и структуры прототипа}
\label{subsubsec:prototype_functions_and_structures}

Почти все структуры и функции объявлены и определены таким образом, что
прототип без изменений компилируется как компилятором соответствующим
стандарту~C11 (ISO/IEC~9899:2011), так и компиляторами
OpenCL\nobreakdash-диалекта~С версии~1.2 и выше. Это достигается за счёт
широкого использования препроцессора языка~C и макроопределением, указывающим,
что необходимо осуществлять сборку для OpenCL\nobreakdash-диалекта~С, является
макроопределение \verb|_OCLH_OCL_COMPILER_|~--~если оно определено, то
препроцессор сгенерирует код OpenCL\nobreakdash-диалекта~С, в ином случае будет
сгенерирован код соответствующий стандарту~C11. Самостоятельно определять
\verb|_OCLH_OCL_COMPILER_| нет необходимости, если вы используете пакет
OpenCL\_helpers, который автоматически определяет данный макрос при компиляции.
Кроме того, в связи с особенностями выделения памяти на GPGPU и вычислительных
акселераторах, код OpenCL\nobreakdash-диалекта~С использует заголовочный файл
\verb|oclh_d_mem_alloc.clh| пакета OpenCL\_helpers.
\begin{ImpNote}
Пакет OpenCL\_helpers реализует единый механизм выделения памяти для
вычислительных акселераторов как без прямого доступа к оперативной памяти
несущего компьютера, так и с таким доступом. Но для акселераторов с доступом
данный механизм может работать медленнее, чем реализации
\verb|malloc()|/\verb|free()| от их производителей. Для использования
выделения, проверки и освобождения памяти релевантных диалекту
OpenCL\nobreakdash-диалекта~С конкретного вычислительного акселератора
необходимо переопределить макропределения \verb|__PTRC_VAL_T_alloc_and_check| и
\verb|__PTRC_VAL_T_free| в файле
\verb|src/include_hd/iterative_point_recovery.clh|.
\end{ImpNote}


\paragraph[Структура, описывающая исходные данные]%
{Структура, описывающая исходные данные.}

Исходные данные хранятся и передаются в структуре\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
typedef struct _PTRC_INPUT_DATA {
              uint64_t     u64D;
    __private _PTRC_VAL_T* pfCnt;
    __private _PTRC_VAL_T* pfRds;
              uint64_t     u64NofS;
} _PTRC_INDAT;
\end{Verbatim}

\noindent Модификаторы \verb|__private| не имеют смысла для языка~C
стандарта~C11 и будут проигнорированы в соответствии с макроопределением.
Для OpenCL\nobreakdash-диалекта~С эти модификаторы обозначают, что указатели
указывают на собственную память нити исполнения.\par\medskip
{\NmCnvDescript \verb|u64D|\\* размерность пространства.\par\medskip}
{\NmCnvDescript \verb|pfCnt|\\* указатель на координаты \verb|u64NofS|~центров
известных сфер, по \verb|u64D|~значений для каждого центра.\par\medskip}
{\NmCnvDescript \verb|pfRds|\\* указатель на \verb|u64NofS|~неточных расстояний
от центров известных сфер до искомой точки.\par\medskip}
{\NmCnvDescript \verb|u64NofS|\\* количество известных сфер.\par\medskip}

\paragraph[Основная функция прототипа]{Основная функция прототипа.}

Основной функцией прототипа является \verb|_ptrc_recoverPoint()| и для
стандарта C11 она объявлена как\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t _ptrc_recoverPoint(      _PTRC_VAL_T* const pfDst,
                                 _PTRC_VAL_T* const pfQlt,
                           const _PTRC_INDAT        in,
                           const uint64_t           u64NofRuns)
\end{Verbatim}

\noindent а для OpenCL\nobreakdash-диалекта~С как\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t _ptrc_recoverPoint(__private       _PTRC_VAL_T* const pfDst,
                           __private       _PTRC_VAL_T* const pfQlt,
                           __private const _PTRC_INDAT        in,
                           __private const uint64_t           u64NofRuns,
                           _GDM_heap_PROTO(__private))
\end{Verbatim}

Функция возвращает~\verb|0| в случае нахождения приближения,
\verb|_PTRC_MEMALLOC_ERR|~--~в случае ошибки выделения памяти и
\verb|_PTRC_NONRECONSTRUCTABLE_PNT_ERR|~--~в случае если восстановление точки
не представилось возможным (коды ошибок
см.~в~разд.~\ref{subsubsec:prototype_settings}).\par\medskip
{\NmCnvDescript \verb|in|\\* исходные данные в виде
структуры~\verb|_PTRC_INDAT|.\par\medskip}
{\NmCnvDescript \verb|pfDst|\\* указатель на память размером не менее чем
\verb|in.u64D| размеров \verb|_PTRC_VAL_T|, где будет сохранено лучшее
найденное приближение.\par\medskip}
{\NmCnvDescript \verb|pfQlt|\\* указатель на память размером не менее чем
один размер \verb|_PTRC_VAL_T|, где будет сохранен показатель
качества~$\lambda$ (см.~раздел~\ref{subsubsec:point_quality}) лучшего
найденного приближения.\par\medskip}
{\NmCnvDescript \verb|u64NofRuns|\\* количество начальных приближений, от
которых будет произведён поиск наилучшего приближения. Первое начальное
приближение является усреднением по центрам известных сфер, последующие
начальные приближения являются попарными усреднениями известных центров сфер со
сдвигом к лучшему найденному приближению. Если \verb|u64NofRuns<1|, то функция
вернёт \verb|_PTRC_NONRECONSTRUCTABLE_PNT_ERR|.\par\medskip}
{\NmCnvDescript \verb|_GDM_heap_PROTO(__private)|\\*
макроопределение\nobreakdash-прототип собственной <<кучи>> нити исполнения
OpenCL для выделения памяти. При вызове функции в качестве данного аргумента
передаётся макроопределение \verb|_GDM_heap_ARG(__private)|. Перед
использованием макроопределения \verb|_GDM_heap_ARG(__private)| собственная
<<куча>> нити исполнения должна быть инициализирована макроопределением
\verb|_GDM___private_heap_init()|.\par\medskip}

\paragraph[Внутренние функции и структуры прототипа]%
{Внутренние функции и структуры прототипа.}
Далее обзорно описаны функции, вызываемые при выполнении
\verb|_ptrc_recoverPoint()|. Модификаторы \verb|__private| не имеют смысла для
языка~C стандарта~C11 и будут проигнорированы в соответствии с
макроопределением. Для OpenCL\nobreakdash-диалекта~С эти модификаторы
обозначают, что указатели указывают на собственную память нити
исполнения.\medskip

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t __ptrc_Phi_meanOfPoints(
                          __private       _PTRC_VAL_T* const pfDstPnt,
                          __private const _PTRC_VAL_T* const pfSrcPnt,
                          __private const uint64_t           u64D,
                          __private const uint64_t         u64NofSrcPnts)

int32_t __ptrc_meanOfPointsBiased(
                          __private       _PTRC_VAL_T* const pfDstPnt,
                          __private const _PTRC_VAL_T* const pfSrcPnt,
                          __private const _PTRC_VAL_T* const pfBiasPnt,
                          __private const uint64_t           u64D,
                          __private const uint64_t       u64NofSrcPnts)
\end{Verbatim}
Функции являются реализациями
функции~$\phi$~(разд.~\ref{subsubsec:first_approx_selection}) и осуществляют
выбор начального приближения. Функция \verb|__ptrc_Phi_meanOfPoints()|
сохраняет в~\verb|pfDstPnt| усреднение по точкам~\verb|pfSrcPnt|. Функция
\verb|__ptrc_meanOfPointsBiased()| сохраняет в~\verb|pfDstPnt| усреднение
по точкам~\verb|pfSrcPnt| со сдвигом к~\verb|pfBiasPnt|.
\verb|u64D|~и~\verb|u64NofSrcPnts|~---~размерность пространства и количество
исходных точек соответственно.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t __ptrc_onePointRoutine(__private       _PTRC_VAL_T* const pfPnt,
                               __private const _PTRC_INDAT        in,
                               _GDM_heap_PROTO(__private))
\end{Verbatim}
Функция является реализацией
шагов~\ref{item:the_second_step}--\ref{item:the_last_step}
алгоритма~(разд.~\ref{subsec:general_algorithm_description}) для исходных
данных~\verb|in| и одного начального приближения~\verb|pfPnt|, по этому же
указателю будет сохранено найденное приближение. Для вызова функции в
программах стандарта~C11 аргумент~\verb|_GDM_heap_PROTO(__private)| не
указывается; для вызова функции в программах OpenCL\nobreakdash-диалекта~С в
качестве данного аргумента передаётся макроопределение
\verb|_GDM_heap_ARG(__private)|.
Перед использованием макроопределения \verb|_GDM_heap_ARG(__private)|
собственная <<куча>> нити исполнения должна быть инициализирована
макроопределением \verb|_GDM___private_heap_init()|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
_PTRC_VAL_T __ptrc_Lambda_quality(
                          __private const _PTRC_VAL_T* const pfPnt,
                          __private const _PTRC_INDAT        in)
\end{Verbatim}
Функция является реализацией
функции~$\lambda$~(разд.~\ref{subsubsec:point_quality}~\eqref{eq:lambda}) и
возвращает значение качества приближения~\verb|pfPnt| для исходных
данных~\verb|in|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t __ptrc_copyVec(__private       _PTRC_VAL_T* const pfDst,
                       __private const _PTRC_VAL_T* const pfSrc,
                       __private       uint64_t           u64D)
\end{Verbatim}
Функция копирования вектора/точки~\verb|pfSrc| размерности~\verb|u64D| в
вектор/точку~\verb|pfDst|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
uint64_t __ptrc_idxOfFarestSphere(
                          __private const _PTRC_VAL_T* const pfPnt,
                          __private const _PTRC_INDAT        in)
\end{Verbatim}
Функция выбора наиболее удалённой сферы реализует
шаг~\ref{item:the_second_step}
алгоритма~(разд.~\ref{subsec:general_algorithm_description}) и
функцию~$\mu$~(разд.~\ref{subsubsec:shortest_distance_to_sphere_surface}~%
\eqref{eq:mue}). Возвращает индекс сферы из исходных данных~\verb|in|,
поверхность которой наиболее удалена от точки~\verb|pfPnt|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t __ptrc_nextPntAndQuality(
                          __private       _PTRC_VAL_T* const pfDst,
                          __private const _PTRC_VAL_T* const pfPnt,
                          __private const _PTRC_INDAT        in,
                          __private const uint64_t    u64IdxOfSphere,
                          __private      _PTRC_VAL_T* const pfQuality,
                          _GDM_heap_PROTO(__private))
\end{Verbatim}
Функция реализует
шаги~\ref{item:the_third_step}--\ref{item:chosing_point_from_pair}
алгоритма~(разд.~\ref{subsec:general_algorithm_description}). От
приближения~\verb|pfPnt| рассчитывается новое приближение к сфере из~\verb|in|
с индексом~\verb|u64IdxOfSphere|. Новое приближение сохраняется по
указателю~\verb|pfDst|; показатель качества нового приближения сохраняется по
указателю~\verb|pfQuality|. Допустимо передавать в качестве
\verb|pfDst|~и~\verb|pfPnt| один адрес. Для вызова функции в программах
стандарта~C11 аргумент~\verb|_GDM_heap_PROTO(__private)| не указывается; для
вызова функции в программах OpenCL\nobreakdash-диалекта~С в качестве данного
аргумента передаётся макроопределение \verb|_GDM_heap_ARG(__private)|. Перед
использованием макроопределения \verb|_GDM_heap_ARG(__private)| собственная
<<куча>> нити исполнения должна быть инициализирована макроопределением
\verb|_GDM___private_heap_init()|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t __ptrc_Psi_refineApproximation(
                          __private       _PTRC_VAL_T* const pfPnt,
                          __private const _PTRC_INDAT        in,
                          _GDM_heap_PROTO(__private))
\end{Verbatim}
Функция реализует
процедуру~$\psi$~(разд.~\ref{subsubsec:point_refinement}~\eqref{eq:psi}). Для
приближения~\verb|pfPnt| и исходных данных~\verb|in| рассчитывается уточнение
приближения, которое сохраняется по указателю~\verb|pfPnt|. Для вызова функции
в программах стандарта~C11 аргумент~\verb|_GDM_heap_PROTO(__private)| не
указывается; для вызова функции в программах OpenCL\nobreakdash-диалекта~С в
качестве данного аргумента передаётся
макроопределение \verb|_GDM_heap_ARG(__private)|. Перед использованием
макроопределения \verb|_GDM_heap_ARG(__private)| собственная <<куча>> нити
исполнения должна быть инициализирована макроопределением
\verb|_GDM___private_heap_init()|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
_PTRC_VAL_T __ptrc_EuclDist(__private const _PTRC_VAL_T* const pfA,
                            __private const _PTRC_VAL_T* const pfB,
                            __private       uint64_t           u64D)
\end{Verbatim}
Функция расчёта расстояния в эвклидовой метрике, реализует
функцию~$\delta$~(разд.~\ref{subsubsec:shortest_distance_to_sphere_surface}~%
\eqref{eq:delta}). Возвращает значение расстояния между
точками~\verb|pfA|~и~\verb|pfB| в пространстве размерности~\verb|u64D|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
int32_t __ptrc_Chi_intersections(__private       _PTRC_VAL_T* const pfDst,
                                 __private const _PTRC_VAL_T* const pfP,
                                 __private const _PTRC_VAL_T* const pfV,
                                 __private const _PTRC_VAL_T* const pfC,
                                 __private const _PTRC_VAL_T        fR,
                                 __private const uint64_t           u64D)
\end{Verbatim}
Функция реализует
функцию~$\chi$~(разд.~\ref{subsubsec:line-sphere_intersection_equation}~%
\eqref{eq:line-sphere_intersection}~и~\eqref{eq:chi}). Функция в пространстве
размерности~\verb|u64D| рассчитывает пару точек, в которых прямая, проходящая
через точки~\verb|pfP|~и~\verb|pfC|, пересекает поверхность сферы с центром
в~\verb|pfC| и радиусом~\verb|fR|. Результат (пара точек) сохраняется по
указателю~\verb|pfDst|.
\end{samepage}\medskip\hrule

\begin{samepage}
\begin{Verbatim}[samepage=true,fontsize=\small]
_PTRC_DEFL_VARS __ptrc_deflFunc(__private const _PTRC_VAL_T* const P,
                                __private const _PTRC_VAL_T* const V,
                                __private const _PTRC_VAL_T* const C,
                                __private const uint64_t           u64D,
                                __private const _PTRC_VAL_T        r)
_PTRC_GHK_VARS __ptrc_ghkFunc(__private const _PTRC_VAL_T* const P,
                              __private const _PTRC_VAL_T* const V,
                              __private const _PTRC_VAL_T* const C,
                              __private const uint64_t           u64D)
\end{Verbatim}
Функции рассчитывают значения $d$, $e$, $f$, $g$, $h$, $k$, $l$
формулы~\eqref{eq:line-sphere_intersection}
раздела~\ref{subsubsec:line-sphere_intersection_equation}. Возвращают
структуры, содержащие эти значения:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
typedef struct _PTRC_G_H_K_VARS {
    _PTRC_VAL_T g; _PTRC_VAL_T h; _PTRC_VAL_T k;
} _PTRC_GHK_VARS;

typedef struct _PTRC_D_E_F_L_VARS {
    _PTRC_VAL_T d; _PTRC_VAL_T e; _PTRC_VAL_T f; _PTRC_VAL_T l;
} _PTRC_DEFL_VARS;
\end{Verbatim}
\end{samepage}\medskip

\subsection{Примеры использования прототипа в приложениях}
\label{subsec:prototype_use_examples}

К примерам использования прототипа в приложениях относятся следующие
файлы:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
  .2 \ldots.
  .2 examples/.
    .3 Makefile\DTcomment{%
    \begin{minipage}[t]{0.6666667\linewidth}сценарий сборки
    примеров.\end{minipage}}.
    .3 point\_recovery\_kernel.clc\DTcomment{\\\hspace*{\fill}%
    \begin{minipage}[t]{0.6666667\linewidth}файл, содержащий определение
    ядерной GPGPU\nobreakdash-функции, вызывающей
    \Verb|\_ptrc\_recoverPoint()|.\end{minipage}}.
    .3 point\_recovery-C11.c\DTcomment{\\\hspace*{\fill}%
    \begin{minipage}[t]{0.6666667\linewidth}файл, содержащий исходный код
    консольного приложения, вызывающего функцию \Verb|\_ptrc\_recoverPoint()|.
    \end{minipage}}.
    .3 point\_recovery-OpenCL.c\DTcomment{\\\hspace*{\fill}%
    \begin{minipage}[t]{0.6666667\linewidth}файл, содержащий исходный код
    консольного приложения, разворачивающего инфраструктуру OpenCL и
    запускающего ядерную GPGPU\nobreakdash-функцию из файла
    \Verb|point\_recovery\_kernel.clc|.\end{minipage}}.
  .2 \ldots.
}}
\end{minipage}\end{samepage}

Для сборки примера на языке C стандарта C11 необходимо, находясь в каталоге
\verb|iterative_point_recovery/examples|, выполнить команду\par\nopagebreak
\indent\indent\verb|make c11|\par\noindent Если прототип установлен
не в каталог по умолчанию, то при сборке необходимо указывать актуальный путь
(префикс) в переменной окружения \verb|IPR_PATH|. Если команда \verb|make|
завершена без ошибок, то в каталоге
\verb|iterative_point_recovery/examples/build| появится
файл~\verb|ptrc_example-c11|. Запуск данного файла приведёт к выводу входных
данных и результирующего приближения, рассчитанного функцией
\verb|_ptrc_recoverPoint()|. При этом в переменной окружения
\verb|LD_LIBRARY_PATH| должен быть путь к файлу \verb|libIterPntRcv.so.0.0| (по
умолчанию \verb|~/opt/iterative_point_recovery/lib|).

Несколько иначе осуществляется сборка прототипа
для OpenCL\nobreakdash-диалекта~С. Предполагается, что установлен пакет
OpenCL\_helpers, и прототип
собран~(см.~разд.~\ref{subsubsec:prototype_build_and_install}) с указанием
индекса устройства GPGPU. Тогда выполнение команды\par\nopagebreak
\indent\indent\verb|make GPGPU_DEV_IDX=|\verbI{N}\verb| opencl|\par\noindent
(где \verbI{N}~---~тот же индекс устройства GPGPU, который был указан при сборке
прототипа) приведёт к появлению в каталоге
\verb|iterative_point_recovery/examples/build|
файла~\verb|ptrc_example-ocl-|\verbI{имя\_устройства\_GPGPU}. Запуск данного
файла приведёт к выводу входных данных и результирующего приближения,
рассчитанного функцией \verb|_ptrc_recoverPoint()|. При этом в переменной
окружения \verb|LD_LIBRARY_PATH| должен быть путь к файлу \verb|liboclh.so.0.0|
(по умолчанию \verb|~/opt/oclh/lib|). В ходе выполнения
файла~\verb|ptrc_example-ocl-|\verbI{имя\_устройства\_GPGPU} ведётся журнал в
файле~\verb|ipr_oclh.log|, где отображаются события и действия связанные с
OpenCL инфраструктурой.

Сами файлы содержащие примеры использования, не превышают 50\nobreakdash-ти
строк кода достаточно прозрачного для дальнейшей интеграции прототипа в
приложения.


\subsection{Проверка и оценка прототипа. Визуализация результатов}
\label{subsec:prototype_testing}

\subsubsection{Проверочный комплект}
\label{subsubsec:test_suite}

Проверочный комплект состоит из следующих файлов:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
  .2 \ldots.
  .2 test\_suite/.
    .3 Makefile\DTcomment{%
    \begin{minipage}[t]{0.6666667\linewidth}сценарий сборки проверочного
    комплекта.\end{minipage}}.
    .3 ptrc\_test\_settings.h\DTcomment{\\\hspace*{\fill}%
    \begin{minipage}[t]{0.6666667\linewidth}файл, содержащий настройки
    проверочного комплекта.\end{minipage}}.
    .3 ptrc\_test.c\DTcomment{%
    \begin{minipage}[t]{0.6666667\linewidth} файл, содержащий исходный код
    проверочного комплекта.\end{minipage}}.
  .2 \ldots.
}}
\end{minipage}\end{samepage}

Проверочный комплект реализован только для проверки алгоритма на языке~C
стандарта~C11, исходя из предположения, что алгоритм на
OpenCL\nobreakdash-диалекте~С идентичен за исключением округлений и случаев
оптимизации обработки числе с плавающей запятой.

Для сборки примера на языке C стандарта C11 необходимо, находясь в каталоге
\verb|iterative_point_recovery/test_suite|, выполнить команду\par\nopagebreak
\indent\indent\verb|make stable|\par\noindent или\par\nopagebreak
\indent\indent\verb|make debug|\par\noindent если необходима сборка с
отладочной информацией. Если команда \verb|make| завершена без ошибок, то в
каталоге \verb|iterative_point_recovery/test_suite/build| появится
файл~\verb|ptrc_test|. Запуск данного файла приведёт к выполнению процедуры
проверки в соответствии с настройками из файла \verb|ptrc_test_settings.h|,
которые описаны \hyperref[par:test_suite_settings_synopsis]{ниже}.

При проверке одного случая проверочный комплект выбирает псевдослучайные точки
в пространстве~${\symbb{R}^n}$, затем рассчитывает расстояния от точек до
последней из них и вносит псевдослучайную погрешность в рассчитанные
расстояния.
Таким образом формируются данные, где первые точки~--~центры сфер, расстояния
с погрешностью~--~радиусы сфер, а последняя точка~--~искомая. Этот блок данных
передаётся функции восстановления точки \verb|_ptrc_recoverPoint()|, после чего
рассчитывается расстояние от полученного приближения до последней
псевдослучайной точки, что интерпретируется как ошибка приближения. Такие
параметры как размерность пространства, интервал выбора псевдослучайных точек,
количество известных сфер и максимальная погрешность
датчика\nobreakdash-источника расстояния задаются в
\hyperref[par:test_suite_settings_synopsis]{настройках проверочного
комплекта}.

\paragraph[Сводка настроек проверочного комплекта]%
{Сводка настроек проверочного комплекта.}
\label{par:test_suite_settings_synopsis}

Настройки проверочного комплекта хранятся в файле \verb|ptrc_test_settings.h|
и представляют собой накроопределения на языке~C, в связи с чем после изменения
настроек необходима пересборка проверочного комплекта в порядке описанном в
разделе~\ref{subsubsec:test_suite}.\par\medskip
{\NmCnvDescript \verb|_PTRC_TS_DIMENSIONALITY|\\* размерность
пространства.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_NUM_OF_SPHERES|\\* количество известных сфер
(пар <<центр\nobreakdash-радиус>>).\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_NUM_OF_RUNS|\\* количество начальных
приближений, от которых будет выполняться алгоритм. Соответственно,
данное количество точек равно количеству запусков алгоритма.
Рекомендуется использовать размерность пространства, увеличенную на
единицу.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_RANGE_MULTIPLIER|\\* множитель интервала, из
которого выбираются проверочные точки. Так, если
\verb|_PTRC_TS_RANGE_MULTIPLIER| определён как \verb|1.0f|, то точки
принадлежат интервалу~${\left\lbrack-1;1\right\rbrack}$ по каждой оси
координат. При изменении множителя концы интервала умножаются на данное
число.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_MIN_SENSOR_UNCERTAINTY|\\* начальная
относительная случайная инструментальная погрешность
датчика\nobreakdash-источника расстояний, которая будет использована при
проверке.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_MAX_SENSOR_UNCERTAINTY|\\* конечная
относительная случайная инструментальная погрешность
датчика\nobreakdash-источника расстояний, которая будет использована при
проверке .\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_SENSOR_UNCERTAINTY_INCREMENT|\\* приращение
погрешности датчика\nobreakdash-источника расстояний.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_NUM_OF_CASES_FOR_ONE_INCREMENT|\\* количество
частных случаев, которые будут проверены для одного значения погрешности
датчика\nobreakdash-источника расстояний.\par\medskip}
{\NmCnvDescript \verb|_PTRC_MAX_ITERATIONS_ON_SPHERE|\\* переопределение
значения~$w$ условия~$\prop{Z}$
(см.~разд.~\ref{subsubsec:the_last_iteration_condition}%
    ~\eqref{eq:zed_with_total_uncertainty}, а также
разд.~\ref{subsubsec:prototype_settings}).\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_STATISTICS_FILENAME|\\* имя файла, в который
будет сохранена итоговая статистика результатов проверки. Данный файл
используется для визуализации
результатов~(см.~разд.~\ref{subsubsec:prototype_regress_estimation}).%
\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_STATISTICS_DISCRETISATION_STEP|\\* частота
дискретизации значений ошибки для расчёта статистики. Так, если частота
дискретизации определена как \verb|0.001f|, тогда ошибка
приближения~${0{,}00345\ldots}$ рассматривается в статистике
как~${0{,}003}$.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_FLOAT_OUTFORM|\\* формат вывода чисел с
плавающей запятой. Соответствует преобразованиям функции \verb|printf()| из
стандартной библиотеки языка~C.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_DATA_OUTPUT_MODE|\\* значение данного
макроопределения несущественно. В случае если данное макроопределение
определено, будет производится машиночитаемый вывод следующих значений
разделённых пробельными символами (значения указаны в порядке вывода):
\begin{itemize}[leftmargin=-2\parindent]
    \item погрешность датчика\nobreakdash-источника расстояний,
    \item значение~$w$~(см.~разд.~\ref{subsubsec:the_last_iteration_condition}%
        ~\eqref{eq:zed_with_total_uncertainty}~и~%
        \ref{subsubsec:prototype_settings}),
    \item размерность пространства,
    \item количество известных сфер,
    \item количество проверяемых начальных приближений,
    \item координаты центров известных сфер,
    \item неточные радиусы известных сфер (расстояния до искомой точки);
\end{itemize}
затем выводится блок записей итераций, каждая запись состоит из следующих
значений разделённых пробельными символами:
\begin{itemize}[leftmargin=-2\parindent]
    \item номер итерации,
    \item координаты нового приближения,
    \item качество нового
        приближения~$\lambda$~(см.~разд.~\ref{subsubsec:point_quality}).
\end{itemize}
Две последние положительные записи блока итераций отличаются номером итерации
на~$2$, и это значит, что последняя запись с положительным номером итерации
есть результат уточнения
приближения~$\psi$~(см.~разд.~\ref{subsubsec:point_refinement}) и его
качество~$\lambda$; предпоследняя запись в блоке итераций имеет номер
итерации~${-1}$ и является окончательным приближением, выбранным из приближений
полученных из разных начальных точек; последняя запись в блоке итераций имеет
номер итерации~${-2}$ и содержит координаты <<настоящей>> искомой точки, а
последнее число это эвклидово расстояние до наилучшего выбранного
приближения~(т.~н.~ошибка). Данные значения в таком порядке машиночитаемы и
могут быть использованы для визуализации шагов алгоритма с помощью сценариев из
раздела~\ref{subsubsec:prototype_particular_case_visualisation}.\par\medskip}
{\NmCnvDescript \verb|_PTRC_TS_VERBOSE_MODE|\\* значение данного
макроопределения несущественно. В случае если данное макроопределение
определено, будет производится человекочитаемый вывод о действиях алгоритма при
работе функции \verb|_ptrc_recoverPoint()|, что позволяет убедиться в
соответствии функции \verb|_ptrc_recoverPoint()| описанию алгоритма. Данная
настройка сделана исключительно в демонстрационных целях. Рекомендуется
использовать её только в случае проверки единственного частного случая. Не
рекомендуется определять данное макроопределение в любых других случаях, так
как это приводит к объёмному избыточному выводу.\par\medskip}


\subsubsection[Регресс-оценка прототипа]{Регресс\nobreakdash-оценка прототипа}
\label{subsubsec:prototype_regress_estimation}

Визуализация регресс\nobreakdash-оценки прототипа реализована в следующих
файлах:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
  .2 \ldots.
  .2 visualisation/.
    .3 Scilab/.
      .4 \ldots.
      .4 ptrc\_statistics.sce\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Scilab для визуализации
      результата работы проверочного комплекта для
      регресс\nobreakdash-оценки алгоритма.\end{minipage}}.
      .4 \ldots.
    .3 Wolfram\_Mathematica/.
      .4 \ldots.
      .4 ptrc\_statistics.wls\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Wolfram~Mathematica для
      визуализации результата работы проверочного комплекта для
      регресс\nobreakdash-оценки алгоритма.\end{minipage}}.
      .4 \ldots.
    .3 example\_stat\_report.txt\DTcomment{демонстрационные данные.}.
    .3 example\_stat\_report0.txt\DTcomment{демонстрационные данные.}.
  .2 \ldots.
}}
\end{minipage}\end{samepage}
Визуализация регресс\nobreakdash-оценки реализована для пакетов Scilab и
Wolfram~Mathematica, описание приводится для пакета Scilab, однако всё
написанное справедливо и для сценария Wolfram~Mathematica, за исключением прямо
оговорённых отличий.

Регресс\nobreakdash-оценка предназначения для общей статистической оценки
изменения корректности сформированного алгоритмом приближения после внесения
изменений в параметры алгоритма или изменения его отдельных частей. Для
регресс\nobreakdash-оценки необходимо, используя проверочный комплект,
сформировать два файла: первый~--~содержит статистические данные для текущей
версии алгоритма, а второй~--~для изменённой.

\begin{samepage}
Рекомендуемые настройки проверочного комплекта для
регресс\nobreakdash-оценки:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small,commandchars=\\\{\}]
#define _PTRC_TS_DIMENSIONALITY                  \textit{по условиям испытаний}
#define _PTRC_TS_NUM_OF_SPHERES                  \textit{по условиям испытаний}
#define _PTRC_TS_NUM_OF_RUNS                     \textit{по условиям испытаний}
#define _PTRC_TS_RANGE_MULTIPLIER                1.0f
#define _PTRC_TS_MIN_SENSOR_UNCERTAINTY          0.0f
#define _PTRC_TS_MAX_SENSOR_UNCERTAINTY          0.5f
#define _PTRC_TS_SENSOR_UNCERTAINTY_INCREMENT    0.01f
#define _PTRC_TS_NUM_OF_CASES_FOR_ONE_INCREMENT  10000ul
#define _PTRC_MAX_ITERATIONS_ON_SPHERE           100ul
#define _PTRC_TS_STATISTICS_FILENAME             "stat_report.txt"
#define _PTRC_TS_STATISTICS_DISCRETISATION_STEP  0.001f
#define _PTRC_TS_FLOAT_OUTFORM                   "%.7f"
// #define _PTRC_TS_DATA_OUTPUT_MODE
// #define _PTRC_TS_VERBOSE_MODE
\end{Verbatim}
\end{samepage}

\noindent После установки настроек проверочного комплекта, необходимо
осуществить его сборку в порядке указанном~в~разделе~\ref{subsubsec:test_suite}
и запустить полученный исполняемый файл. В результате будет сформирован файл
статистики \verb|stat_report.txt|, который сохраняется отдельно как данные о
текущей версии алгоритма. В демонстрационных целях для размерности~$5$ и
количества известных сфер~$6$ сформирован такой файл и сохранён как\\*
\centerline{\small%
\Verb|iterative\_point\_recovery/visualisation/example\_stat\_report0.txt|}
Затем необходимо внести желаемые изменения в алгоритм или его настройки,
пересобрать проверочный комплект и снова запустить. Так,
в~разделе~\ref{sec:introduction} был выражен тезис <<\textit{\ldots в
прикладных задачах часто есть возможность получить данные не с
${n+1}$~датчиков, дающих неточные значения, а с большего их (датчиков)
количества \ldots\ дополнительная информация может (и должна) улучшать
приближение искомой точки\ldots}>>. Для демонстрации справедливости этого
тезиса для размерности~$5$ и количества известных сфер~$9$ сформирован файл
статистики и сохранён как\\*
\centerline{\small%
\Verb|iterative\_point\_recovery/visualisation/example\_stat\_report1.txt|}
Иными словами, далее в примерах сравнивается точность работы алгоритма при
поиске точки в пятимерном пространстве при 6\nobreakdash-ти и 9\nobreakdash-ти
известных сферах (парах <<точка\nobreakdash-расстояние>>).

На данном этапе доступны два файла: первый~--~со статистической оценкой
исходной версии прототипа (\verb|example_stat_report0.txt|); второй~--~со
статистической оценкой изменённой версии прототипа
(\verb|example_stat_report1.txt|). Теперь в
файле (для сценария Scilab):\par\nopagebreak
\indent\verb|visualisation/Scilab/ptrc_statistics.sce|\par\noindent%
либо (для сценария Wolfram~Mathematica):\par\nopagebreak
\indent\verb|visualisation/Wolfram_Mathematica/ptrc_statistics.wls|\par%
\nopagebreak\noindent%
необходимо изменить значения переменных\par\nopagebreak
\begin{Verbatim}[samepage=true]
dataFile0="../example_stat_report0.txt";
dataFile1="../example_stat_report1.txt";
\end{Verbatim}
\par\nopagebreak\noindent%
на актуальные. Здесь \verb|dataFile0|~--~путь к первому файлу с данными текущей
версии прототипа, и, соответственно, \verb|dataFile1|~--~путь к второму файлу с
данными изменённого прототипа. После чего сохраните файл и выполните его
командой (для сценария Scilab):\par\nopagebreak
\indent\indent\verb|scilab -f ptrc_statistics.sce -quit|\par\noindent%
либо (для сценария Wolfram~Mathematica):\par\nopagebreak
\indent\indent\verb|wolframscript -f ptrc_statistics.wls|\par\noindent%
Для сценария Scilab можно не указывать ключ \verb|-quit|, а в дальнейшем
перезапускать сценарий из открытой оболочки Scilab. Для сценария
Wolfram~Mathematica, чтобы сохранить сценарий открытым в оболочке с
возможностью перезапуска откройте его командой:\par\nopagebreak
\indent\indent\verb|Mathematica ptrc_statistics.wls|\par\noindent%
В результате выполнения данного сценария будут сохранены файлы
\verb|errors.png|, \verb|errors.svg| и \verb|solves.png|, \verb|solves.svg|.

\paragraph[Визуализация регресс-оценки по ошибкам приближений]%
{Визуализация регресс\nobreakdash-оценки по ошибкам приближений.}
\label{par:vis_errors}

Рассмотрим для начала файл \verb|errors.png| (или \verb|svg| в векторном
представлении). Содержимое файла выглядит примерно как на
рис.~\ref{fig:fig2_errors}.
\begin{figure}[!ht]
\includegraphics[width=\linewidth]{fig2_errors.eps}%
\captionsetup{format=hang}%
\caption{Статистика ошибок приближений.}%
\label{fig:fig2_errors}
\end{figure}
Сплошная синяя линия описывает математическое
ожидание величины ошибки для условий описанных в легенде к графику, в
приведённом примере это: размерность~$5$, известных сфер~$6$, множитель
интервала выбора точек~${1.0}$, количество проверенных начальных
приближений~$6$; погрешность датчика при оценке изменялась от~$0$ до~${0.5}$ с
шагом приращения~${0.01}$, для каждой погрешности было испытано~${10 000}$
случаев, частота дискретизации значений ошибки~${0.001}$. Как и было указано в
разделе~\ref{sec:introduction} <<\textit{алгоритм должен демонстрировать прямую
корреляцию качества своей работы и точности датчиков выдающих расстояния~$R$, а
в таком случае оценка расстояния между алгоритмически вычисленной и искомой
точкой будет не оценкой алгоритма, а оценкой точности датчиков, причём
косвенной}>>, что и можно наблюдать в данном примере, так как видно, что
математическое ожидание ошибки растёт с ростом погрешности датчика, однако
очевидно, чем алгоритм лучше, тем математической ожидание ошибки при оценке
должно быть ниже. Светло\nobreakdash-синяя пунктирная линия это, согласно
легенде, сумма математического ожидания с одним среднеквадратичным
(стандартным) отклонением, чем она ближе к математическому ожиданию, тем
алгоритм лучше. Светло\nobreakdash-синие точечные линии это минимумы и
максимумы, соответственно. С одной стороны, чем ближе минимумы и максимумы к
математическому ожиданию, тем лучше, но с другой стороны большинство таких
максимизированных выбросов обусловлены не качеством алгоритма как такового, а
ситуациями, когда выбранные для оценки точки находятся близко к одной
гиперплоскости, что приводит к возникновению нескольких областей с примерно
одинаковыми качествами приближений и неопределённости в выборе (подобный пример
будет рассмотрен в
разделе~\ref{subsubsec:prototype_particular_case_visualisation}).
Представляется очевидным, что, в случае если известные точки принадлежат одной
гиперплоскости, местонахождение искомой точки становится полностью
неопределённым, поэтому при решении практических задач необходимо следить,
чтобы датчики\nobreakdash-источники расстояний по возможности не принадлежали и
не находились близко к одной гиперплоскости.

Сплошная красная, пунктирная и точечная светло\nobreakdash-красные линии
отображают, соответственно, математическое ожидание, сумму математического
ожидания и среднеквадратичного отклонения, минимумы и максимумы для испытаний
второго варианта алгоритма или условий. Так, из легенды к графику можно видеть,
что условия для испытаний, при которых получены красные показатели, отличаются
только количеством известных сфер. По сравнению с $6$\nobreakdash-ю~известными
сферами $9$~известных сфер снижают математическое ожидание ошибки и уменьшают
среднеквадратичное отклонение ошибки.

Увеличение точности приближений с ростом количества известных сфер ожидаемо, но
не бесплатно, стоимость такого увеличения точности рассматривается в следующем
параграфе.

\paragraph[Визуализация регресс-оценки по количеству произведённых действий]%
{Визуализация регресс\nobreakdash-оценки по количеству произведённых действий.}
\label{par:vis_solves}

Для данного варианта алгоритма самым затратным повторяющимся шагом является
расчёт
формулы~$\chi$~(разд.~\ref{subsubsec:line-sphere_intersection_equation}~%
\eqref{eq:line-sphere_intersection}~и~\eqref{eq:chi}) с последующим вычислением
качества~$\lambda$~(разд.~\ref{subsubsec:point_quality}~\eqref{eq:lambda}) для
двух приближений при осуществлении выбора. Так как для каждого
вычисления~$\chi$ производится вычисление~$\lambda$, в проверочном комплекте в
глобальной переменной~\verb|fSolves| осуществляется подсчёт таких шагов для
каждого испытанного случая. Полученная статистика отображается на графике в
файле \verb|solves.png| (или \verb|svg| в векторном представлении). Содержимое
файла выглядит примерно как на рис.~\ref{fig:fig3_solves}.
\begin{figure}[!ht]
\includegraphics[width=\linewidth]{fig3_solves.eps}%
\captionsetup{format=hang}%
\caption{Статистика количеств расчётов формулы~$\chi$.}%
\label{fig:fig3_solves}
\end{figure}
Цветовые обозначения и формы линий аналогичны таковым при визуализации
статистики ошибок приближений. Так линии синего и светло\nobreakdash-синего
цветов соответствуют данным первого набора испытаний (эталонного), а линии
красного и светло\nobreakdash-красного цвета соответствуют данным второго
набора испытаний (для изменённого алгоритма или условий). Сплошная линия в
контексте данного графика обозначает математическое ожидание количества шагов
(вычислений~$\chi$) к погрешности датчика\nobreakdash-источника расстояний,
пунктирная линия показывает сумму математического ожидания и стандартного
отклонения количества шагов, точечные линии отображают минимумы и максимумы
соответственно их расположению.

Из представленного примера видно, что при изменении условий исполнения
алгоритма от~$6$\nobreakdash-и к $9$\nobreakdash-и известным сферам количество
расчётов увеличилось. Иными словами, изменение количества известных сфер делает
найденное приближение точнее, но увеличивает время выполнения алгоритма для
одного случая. Необходимо учитывать данное обстоятельство при формировании
входящих данных для алгоритма, так, например, при ограничении времени и наличии
нескольких датчиков\nobreakdash-источников расстояний имеет смысл не
использовать все известные сферы, а выбирать, только ${n+1}$~тех из них, центры
которых, которые наиболее удалены от одной гиперплоскости. Окончательный выбор
входных данных должен производится исходя из отмеченного обстоятельства
зависимости точности и времени исполнения, объективных ограничений и рисков
обстановки исполнения алгоритма.

\paragraph[Данные по каждому испытанию]{Данные по каждому испытанию.}
\label{par:cases_raw_data}

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

\begin{samepage}
Значения ошибок представлены в виде:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
Sensor_uncertainty Raw_Deltas
0.0000000 0.0000018 0.0000024 0.0000140 ...
0.0100000 0.0380290 0.0628870 0.0381434 ...
0.0200000 0.1352121 0.2248735 0.0489258 ...
...       ...       ...       ...
\end{Verbatim}
\end{samepage}

Здесь число в первом столбце это значение погрешности
датчика\nobreakdash-источника расстояний, далее до конца строки значения
ошибок для каждого испытанного случая. При этом надо иметь в виду, что могут
возникать ситуации, когда количество значений ошибки меньше, чем
\verb|_PTRC_TS_NUM_OF_CASES_FOR_ONE_INCREMENT|, так как не все точки могут быть
восстановлены (см.~\hyperref[par:note_about_restrictions]{замечание} на
стр.~\pageref{par:note_about_restrictions}).

\begin{samepage}
Значения количеств шагов представлены в виде:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
Sensor_uncertainty Raw_Solves
0.0000000 2566 2885 710 ...
0.0100000 866  546  994 ...
0.0200000 997  935  570 ...
0.0300000 1231 2668 463 ...
...       ...  ...  ...
\end{Verbatim}
\end{samepage}

Здесь число в первом столбце это значение погрешности
датчика\nobreakdash-источника расстояний, далее до конца строки значения
количеств предпринятых шагов для каждого испытанного случая. При этом надо
иметь в виду, что при малых
значениях~$w$~(см.~разд.~\ref{subsubsec:the_last_iteration_condition}%
~\eqref{eq:zed_with_total_uncertainty} и~\hyperref[impNote:on_w]{замечание} к
разделу~\ref{subsubsec:prototype_settings})  большинство значений не будет
превышать~${\left(wm\right)+\symrm{const}}$.

Исходя их этих данных можно строить иные показатели качества алгоритма,
например, композитный показатель отношения точности к количеству шагов или иные
согласно предполагаемым условиям эксплуатации алгоритма.

\subsubsection{Визуализация одного частного случая}
\label{subsubsec:prototype_particular_case_visualisation}

Визуализация частного случая работы алгоритма реализована в следующих
файлах:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
  .2 \ldots.
  .2 visualisation/.
    .3 Scilab/.
      .4 \ldots.
      .4 ptrc\_one\_sample\_vis-2d-anim.sce\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Scilab для
      анимированной визуализации двухмерного случая работы
      алгоритма.\end{minipage}}.
      .4 ptrc\_one\_sample\_vis-2d.sce\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Scilab для визуализации
      двухмерного случая работы алгоритма.\end{minipage}}.
      .4 ptrc\_one\_sample\_vis-3d.sce\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Scilab для визуализации
      трёхмерного случая работы алгоритма.\end{minipage}}.
      .4 sample\_data\_parser.sce\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Scilab для чтения и
      разбора данных частного случая, сформированных проверочным
      комплектом.\end{minipage}}.
      .4 \ldots.
    .3 Wolfram\_Mathematica/.
      .4 \ldots.
      .4 ptrc\_one\_sample\_vis-2d-anim.wls\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Wolfram~Mathematica для
      анимированной визуализации двухмерного случая оценки
      алгоритма.\end{minipage}}.
      .4 ptrc\_one\_sample\_vis-2d.wls\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Wolfram~Mathematica для
      визуализации двухмерного случая оценки алгоритма.\end{minipage}}.
      .4 ptrc\_one\_sample\_vis-3d.wls\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Wolfram~Mathematica для
      визуализации трёхмерного случая оценки алгоритма.\end{minipage}}.
      .4 sample\_data\_parser.wl\DTcomment{\\\hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}сценарий Wolfram~Mathematica для
      чтения и разбора данных частного случая, сформированных проверочным
      комплектом.\end{minipage}}.
      .4 \ldots.
    .3 one\_case\_data-2d\_\#.txt\DTcomment{демонстрационные данные.}.
    .3 one\_case\_data-3d\_\#.txt\DTcomment{демонстрационные данные.}.
  .2 \ldots.
}}
\end{minipage}\end{samepage}
Визуализация регресс\nobreakdash-оценки реализована для пакетов Scilab и
Wolfram~Mathematica, описание приводится для пакета Scilab, однако всё
написанное справедливо и для сценария Wolfram~Mathematica, за исключением прямо
оговорённых отличий.

Визуализация одного частного случая не имеет значительной практической пользы и
сделана в разъяснительных целях для понимания алгоритма лицами, склонными к
пространственно\nobreakdash-геометрическому мышлению больше, нежели к
синтаксическому. Учитывая, что человек способен достаточно полно воспринимать
только двухмерное пространство, визуализация частного случая сделана только для
двухмерного и ограниченно для трёхмерного случая. Теоретически можно сделать
визуализации случаев и больших размерностей, разбивая их на проекции, но так
как в целом практической пользы от такой визуализации нет или крайне мало, для
случаев с размерностью выше трёх сценарии визуализации не создавались.

\paragraph[Визуализация двухмерного частного случая работы
алгоритма]{Визуализация двухмерного частного случая работы алгоритма.}
\label{par:one_2d_case_vis}
\begin{samepage}
Рекомендуемые настройки проверочного комплекта для визуализации одного
двухмерного частного случая работы алгоритма:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small,commandchars=\\\{\}]
#define _PTRC_TS_DIMENSIONALITY                  2ul
#define _PTRC_TS_NUM_OF_SPHERES                  \textit{по условиям испытаний}
#define _PTRC_TS_NUM_OF_RUNS                     3ul
#define _PTRC_TS_RANGE_MULTIPLIER                1.0f
#define _PTRC_TS_MIN_SENSOR_UNCERTAINTY          \textit{по условиям испытаний}
#define _PTRC_TS_MAX_SENSOR_UNCERTAINTY     \textit{равно предыдущему значению}
#define _PTRC_TS_SENSOR_UNCERTAINTY_INCREMENT    0.01f
#define _PTRC_TS_NUM_OF_CASES_FOR_ONE_INCREMENT  1ul
#define _PTRC_MAX_ITERATIONS_ON_SPHERE           100ul
#define _PTRC_TS_STATISTICS_FILENAME             "stat_report.txt"
#define _PTRC_TS_STATISTICS_DISCRETISATION_STEP  0.001f
#define _PTRC_TS_FLOAT_OUTFORM                   "%.7f"
#define _PTRC_TS_DATA_OUTPUT_MODE
//#define _PTRC_TS_VERBOSE_MODE
\end{Verbatim}
\end{samepage}

\noindent После установки настроек проверочного комплекта, необходимо
осуществить его сборку в порядке указанном
в~разделе~\ref{subsubsec:test_suite}. Затем из выполните сценарий Scilab
командой:\par\nopagebreak
\indent\indent\verb|scilab -f ptrc_one_sample_vis-2d.sce|\par\noindent%
либо сценарий Wolfram~Mathematica командой:\par\nopagebreak
\indent\indent\verb|Mathematica -f ptrc_one_sample_vis-2d.wls|\par\noindent%
После выполнения сценария останется открытая оболочка и графические окна с
визуализацией. В данном случае открытые оболочки остаются специально, чтобы
можно было в интерактивных графических окнах масштабировать изображение, так
как часть визуализации достаточно мала и неразборчива на общем плане. В
сценарии первые строки представляют собой присвоение значений двум
переменным\par\nopagebreak
\begin{Verbatim}[samepage=true]
fileName="one_case_data-2d.txt";
generateNewCase=1;
\end{Verbatim}
\par\nopagebreak\noindent%
Первая их них \verb|fileName| определяет путь к и имя файла, куда будут
сохранены результаты запуска проверочного комплекта, выведенные в стандартный
вывод; вторая \verb|generateNewCase|~--~указывает сценарию производить ли новый
запуск проверочного комплекта (значение~\verb|1|) или работать с
файлом~\verb|fileName| без его изменения (значение~\verb|0|).

Для начала рассмотрим случай, когда начальные условия достаточно корректны. Так
на рис.~\ref{fig:fig4_closed_case} показан случай, когда в результате ошибок
датчиков\nobreakdash-источников расстояний образуется закрытая область.
\begin{figure}[!h]
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig4_sample_start_point_1.eps}} (a)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]{fig4_sample_start_point_2.eps}}
(b)\\
\end{minipage}
\vfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig4_sample_start_point_3.eps}} (c)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig4_sample_start_point_1_zoom.eps}} (d)\\
\end{minipage}
\captionsetup{format=hang}%
\caption{Визуализация работы алгоритма в случае закрытой области.}%
\label{fig:fig4_closed_case}
\end{figure}
Визуализация строится на фоне тепловой карты значений
функции~$\lambda$~(разд.~\ref{subsubsec:point_quality}~\eqref{eq:lambda}).
Известные окружности и их центры (расположение датчиков\nobreakdash-источников
расстояний) обозначены оттенками цветов (в данном случае
тёмно\nobreakdash-красным, тёмно\nobreakdash-зелёным и
тёмно\nobreakdash-синим). Символом~$\bigotimes$ обозначается начальное
приближение. Чёрные линии показывают переход от приближения к приближению в
ходе выполнения алгоритма. Последнее приближение для данного начального
обведено чёрной окружностью. Фиолетовым символом~$+$ обозначается наилучшее
приближение выбранное среди всех результатов работы из разных начальных
приближений. Фиолетовым символом~$\ast$ обозначается <<настоящая>> искомая
точка. На рис.~\ref{fig:fig4_closed_case} изображение (a) показывает
<<путь>> улучшения приближений для первого начального приближения и последующие
два изображения (b) и (c) для 2\nobreakdash-ого и 3\nobreakdash-его
соответственно. Последнее изображение (d) это увеличенный фрагмент первого
изображения, где продемонстрирована замкнутая область, образованная
окружностями построенными из неточных расстояний. Можно видеть, как на
четвёртом изображении алгоритм попадает в замкнутую область и завершается. В
результате, как написано в заголовках изображений, расстояние от найденного
приближения до искомой точки составляет~$0.0048018$.

Аналогично на рис.~\ref{fig:fig5_open_case} продемонстрирован случай, когда по
расстояниям с ошибками построены сферы образующие незамкнутую (открытую
область), где алгоритм находит наилучшее приближение. Завершение работы
алгоритма можно видеть на рис.~\ref{fig:fig5_open_case} изображение~(d).
\begin{figure}[!h]
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig5_sample_start_point_1.eps}} (a)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]{fig5_sample_start_point_2.eps}}
(b)\\
\end{minipage}
\vfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig5_sample_start_point_3.eps}} (c)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig5_sample_start_point_1_zoom.eps}} (d)\\
\end{minipage}
\captionsetup{format=hang}%
\caption{Визуализация работы алгоритма в случае открытой области.}%
\label{fig:fig5_open_case}
\end{figure}

Можно и далее приводить различные случаи и классифицировать их, включая
случаи, когда есть полузакрытая область или случаи, когда окружности не
пересекаются, но в целом в большинстве таких случаев алгоритм ведёт себя
правильно и даёт хорошее приближение. Интереснее рассмотреть случаи, когда
условия выполнения алгоритма действительно плохие и на тепловой карте явно
образованы 2 (иногда больше) экстремумов функции~$\lambda$, что, как было
сказано выше, происходит, если датчики\nobreakdash-источники расстояний
расположены на одной или близко к одной гиперплоскости. На таких случаях
становятся видны преимущества нескольких запусков алгоритма из разных начальных
приближений. Так на рис.~\ref{fig:fig6_hard_case} можно видеть, что
датчики\nobreakdash-источники расстояний (центры сфер) расположены почти на
одной гиперплоскости (прямой для двухмерного случая), что приводит к появлению
двух примерно равных экстремумов на севере и юго\nobreakdash-востоке
изображения, причём искомая точка расположена на юго\nobreakdash-востоке.
\begin{figure}[!h]
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig6_sample_start_point_1.eps}} (a)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]{fig6_sample_start_point_2.eps}}
(b)\\
\end{minipage}
\vfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig6_sample_start_point_3.eps}} (c)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig6_sample_start_point_2_zoom.eps}} (d)\\
\end{minipage}
\captionsetup{format=hang}%
\caption{Визуализация работы алгоритма в случае двух экстремумов
функции~$\lambda$ и нахождении <<хорошего>> приближения.}%
\label{fig:fig6_hard_case}
\end{figure}
Можно видеть, что на изображении~(a)~рис.~\ref{fig:fig6_hard_case} из первого
начального приближения алгоритм приходит в область между двумя экстремумами и в
отсутствии улучшения
функции~$\lambda$~(разд.~\ref{subsubsec:point_quality}~\eqref{eq:lambda})
прекращает поиск, возвращая плохое приближение. Но при проверке второго
начального приближения на изображении~(b)~рис.~\ref{fig:fig6_hard_case},
алгоритм приходит в <<правильный>> экстремум функции~$\lambda$ и возвращает
<<хорошее>> приближение искомой точки, завершение чего можно видеть на
масштабированном изображении~(d)~рис.~\ref{fig:fig6_hard_case}. И при проверке
третьего начального приближения алгоритм уходит к <<неправильному>> северному
экстремуму функции~$\lambda$, где и завершается. И только выбор из этих трёх
финальных приближений позволяет выбрать наилучшее, соответствующее
изображению~(b).

В отдельных случаях, когда датчики\nobreakdash-источники расстояний расположены
на одной или близко к одной гиперплоскости может образоваться область, в
которой значение функции~$\lambda$ выше, чем в области с искомой точкой. В
таком случае алгоритм вернёт очень <<плохое>> приближение. Подобный пример
приведён на рис.~\ref{fig:fig7_bad_case}.
\begin{figure}[!h]
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig7_sample_start_point_1.eps}} (a)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]{fig7_sample_start_point_2.eps}}
(b)\\
\end{minipage}
\vfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig7_sample_start_point_3.eps}} (c)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig7_sample_start_point_1_zoom.eps}} (d)\\
\end{minipage}
\captionsetup{format=hang}%
\caption{Визуализация работы алгоритма в случае двух экстремумов
функции~$\lambda$ и нахождении ошибочного приближения.}%
\label{fig:fig7_bad_case}
\end{figure}
Интересным в приведённом примере является то, что при исполнении алгоритма от
третьего начального приближения на изображении~(c) видно как алгоритм пришёл в
область близкую к искомой точке, но после сравнения качества финальных первого
и третьего приближений было выбрано первое, то есть значение функции~$\lambda$
оказалось выше в экстремуме противоположном области с искомой точкой. Как можно
попытаться избегать подобных ситуаций, будет описано в
разделе~\ref{sec:possible_advances}.

\paragraph[Анимированная визуализация двухмерного частного случая работы
алгоритма]{Анимированная визуализация двухмерного частного случая работы
алгоритма.}
\label{par:one_2d_case_anim_vis}

Анимированная визуализация двухмерного частного случая осуществляется с теми же
настройками, что и статическая визуализация, описанная в предыдущем параграфе.
Сценарий анимированной визуализации использует сценарий статической
визуализации, поэтому настройки переменных
\verb|fileName|~и~\verb|generateNewCase| необходимо менять в соответствующих
файлах \verb|ptrc_one_sample_vis-2d.sce| или \verb|.wls|. Имя файла с анимацией
определено в сценарии \verb|ptrc_one_sample_vis-2d-anim.sce| для Scilab или
\verb|.wls| для Wolfram~Mathematica переменной\par\nopagebreak
\begin{Verbatim}[samepage=true]
animationFileName="animation.gif";
\end{Verbatim}
\par\nopagebreak\noindent%
Сценарий Scilab, создающий анимированный gif\nobreakdash-файл, запускается
командой:\par\nopagebreak
\indent\indent%
\verb|scilab -f ptrc_one_sample_vis-2d-anim.sce -quit|\par\noindent%
а сценарий Wolfram~Mathematica командой:\par\nopagebreak
\indent\indent%
\verb|Mathematica ptrc_one_sample_vis-2d-anim.wls|\par\noindent%
В результате выполнения данной команды в каталоге появится файл
\verb|animation.gif|, где и будет анимированная визуализация одного двухмерного
случая.

Сценарий Scilab формирует gif\nobreakdash-файл с помощью пакета
ImageMagic~({\href{https://imagemagick.org}%
{\nolinkurl{https://imagemagick.org}}}), который должен быть установлен и
доступен.

Сценарий Wolfram~Mathematica формирует gif\nobreakdash-файл собственными
средствами, но есть нюанс: так как формирование gif\nobreakdash-файла
производится модулем на Java, при большом количестве кадров сценарий может
использовать очень много оперативной памяти вплоть до 200 гигабайт. В связи с
изложенным рекомендуется запускать сценарий с ограничением по оперативной
памяти, например, в ОС~Linux это можно сделать с помощью контрольных групп
командами:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
sudo cgcreate -t user:user -a user:user -g memory:mem2G
echo 2048M > /sys/fs/cgroup/memory/mem2G/memory.limit_in_bytes
\end{Verbatim}
\par\nopagebreak\noindent%
А затем запустить сценарий при данных ограничениях:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small]
cgexec -g memory:mem2G Mathematica ptrc_one_sample_vis-2d-anim.wls
\end{Verbatim}

\paragraph[Визуализация трёхмерного частного случая работы
алгоритма]{Визуализация трёхмерного частного случая работы алгоритма.}
\label{par:one_3d_case_vis}
\begin{samepage}
Рекомендуемые настройки проверочного комплекта для визуализации одного
трёхмерного частного случая работы алгоритма:\par\nopagebreak
\begin{Verbatim}[samepage=true,fontsize=\small,commandchars=\\\{\}]
#define _PTRC_TS_DIMENSIONALITY                  3ul
#define _PTRC_TS_NUM_OF_SPHERES                  \textit{по условиям испытаний}
#define _PTRC_TS_NUM_OF_RUNS                     3ul
#define _PTRC_TS_RANGE_MULTIPLIER                1.0f
#define _PTRC_TS_MIN_SENSOR_UNCERTAINTY          \textit{по условиям испытаний}
#define _PTRC_TS_MAX_SENSOR_UNCERTAINTY     \textit{равно предыдущему значению}
#define _PTRC_TS_SENSOR_UNCERTAINTY_INCREMENT    0.01f
#define _PTRC_TS_NUM_OF_CASES_FOR_ONE_INCREMENT  1ul
#define _PTRC_MAX_ITERATIONS_ON_SPHERE           100ul
#define _PTRC_TS_STATISTICS_FILENAME             "stat_report.txt"
#define _PTRC_TS_STATISTICS_DISCRETISATION_STEP  0.001f
#define _PTRC_TS_FLOAT_OUTFORM                   "%.7f"
#define _PTRC_TS_DATA_OUTPUT_MODE
//#define _PTRC_TS_VERBOSE_MODE
\end{Verbatim}
\end{samepage}

\noindent После установки настроек проверочного комплекта, необходимо
осуществить его сборку в порядке указанном
в~разделе~\ref{subsubsec:test_suite}. Затем из выполните сценарий Scilab
командой:\par\nopagebreak
\indent\indent\verb|scilab -f ptrc_one_sample_vis-3d.sce|\par\noindent%
либо сценарий Wolfram~Mathematica командой:\par\nopagebreak
\indent\indent\verb|Mathematica -f ptrc_one_sample_vis-3d.wls|\par\noindent%
После выполнения сценария останется открытая оболочка и графические окна с
визуализацией. В данном случае открытые оболочки остаются специально, чтобы
можно было в интерактивных графических окнах масштабировать изображение, так
как часть визуализации достаточно мала и неразборчива на общем плане. В
сценарии первые строки представляют собой присвоение значений двум
переменным\par\nopagebreak
\begin{Verbatim}[samepage=true]
fileName="one_case_data-3d.txt";
generateNewCase=1;
\end{Verbatim}
\par\nopagebreak\noindent%
Первая их них \verb|fileName| определяет путь к и имя файла, куда будут
сохранены результаты запуска проверочного комплекта, выведенные в стандартный
вывод; вторая \verb|generateNewCase|~--~указывает сценарию производить ли новый
запуск проверочного комплекта (значение~\verb|1|) или работать с
файлом~\verb|fileName| без его изменения (значение~\verb|0|).

Для визуализации трёхмерного случая тепловая карта функции~$\lambda$ не
строится. В целом визуализация трёхмерного случая весьма неинформативна и после
построения требуется посмотреть с нескольких точек обзора, чтобы понять, как
происходило улучшение приближений. В сценарии визуализации для Scilab сферы
отображаются с помощью сетки, частоту которой регулирует
переменная~\verb|meshSize|, а в сценарии визуализации для Wolfram~Mathematica
поверхности сфер отображаются полностью, но введён регулятор прозрачности
поверхности сфер.

Сложность восприятия визуализации трёхмерного случая можно понять из
рис.~\ref{fig:fig8_one_3d_case}.
\begin{figure}[!h]
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig8_sample_start_point_1_SL.eps}} (a)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig8_sample_start_point_1_zoom_SL.eps}} (b)\\
\end{minipage}
\captionsetup{format=hang}%
\vfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig8_sample_start_point_1_WM.eps}} (c)\\
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=1\linewidth]%
{fig8_sample_start_point_1_zoom_WM.eps}} (d)\\
\end{minipage}
\captionsetup{format=hang}%
\caption{Визуализация работы алгоритма в трёхмерном
случае.\newline (a), (b)~--~Scilab. (c), (d)~--~Wolfram~Mathematica.}%
\label{fig:fig8_one_3d_case}
\end{figure}

\subsection{Исходный код документации и сопутствующие файлы}
\label{subsec:prototype_documentation_source}

Данная документация предоставляется в виде исходных кодов в следующих
файлах:\par\nopagebreak
\noindent\begin{samepage}\begin{minipage}[t]{\linewidth}
{\small\dirtree{%
.1 iterative\_point\_recovery/.
  .2 \ldots.
  .2 documentation/.
    .3 fonts/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}каталог,
содержащий шрифты и их настройки.\end{minipage}}.
    .3 images/\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}каталог,
      содержащий иллюстрации документации и       исходные файлы для построения
      иллюстраций.\end{minipage}}.
    .3 build\_script\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}сценарий
      сборки документации.\end{minipage}}.
    .3 ipr\_doc.cls\DTcomment{\begin{minipage}[t]{0.6666667\linewidth}файл с
      определениями стиля документации.\end{minipage}}.
    .3 iterative\_point\_recovery\_documentation-russian.tex\DTcomment{\\%
      \hspace*{\fill}%
      \begin{minipage}[t]{0.6666667\linewidth}исходный код
      документации.\end{minipage}}.
  .2 \ldots.
}}
\end{minipage}\end{samepage}

Документация собирается отдельно. Для её сборки необходима система вёрстки
\XeTeX /\XeLaTeX\ или иная \TeX /\LaTeX\nobreakdash-система. Система \XeTeX\ и
сопутствующие пакеты поставляются в составе дистрибутива
\TeX~Live~({\href{https://www.tug.org/texlive/}%
{\nolinkurl{https://www.tug.org/texlive/}}}). Использование системы отличной от
\XeTeX\ может потребовать внесения изменений в исходный код документации.

Сама сборка документации осуществляется из каталога
\verb|iterative_point_recovery/documentation| запуском сценария сборки\par
\indent\indent\verb|./build_script|\par
\noindent%
Если в ходе исполнения данного сценария не возникло ошибок, то в каталоге
\verb|iterative_point_recovery/documentation/build| появится файл\par
\indent\indent%
\verb|iterative_point_recovery_documentation-russian.pdf|\par
\noindent%
с документацией.

При сборке будут использованы шрифты семейства IBM~Plex, но можно вернуться к
базовому семейству Computer~Modern просто раскомментировав
строку\par\nopagebreak
\begin{Verbatim}[samepage=true]
\input{fonts/font_settings-Computer_Modern.tex}
\end{Verbatim}
\par\nopagebreak\noindent%
в преамбуле исходного кода документации.

\section{Основные направления возможных доработок}
\label{sec:possible_advances}

При реализации алгоритма для конкретных условий работы прежде всего необходима
ревизия предположений из раздела~\ref{subsec:assumptions}, так как приведённые
предположения могут не соответствовать известным условиям работы алгоритма и
требовать пересмотра. В настоящее время они сформулированы достаточно общо, что
оставляет маневр для уточнения в конкретных реализациях. При изменении
подходов, описанных в разделе~\ref{subsec:assumptions}, рекомендуется проводить
регресс\nobreakdash-оценку на случайном или специфичном задачам проверочном
множестве.

Для избегания ситуаций неправильного выбора приближения в случаях когда,
экстремум
функции~$\lambda$~(разд.~\ref{subsubsec:point_quality}~\eqref{eq:lambda})
находится на удалении от искомой точки, а возможности удовлетворительного
выбора датчиков\nobreakdash-источников расстояний нет, рассматривается
возможность сохранения и выбора из нескольких приближений, исходя из
дополнительной информации, например, о предыдущем положении искомой точки.

\newpage
\tableofcontents

\end{document}