\documentclass[a4paper,12pt,titlepage,finall]{article}

\usepackage[T1,T2A]{fontenc}     % форматы шрифтов
\usepackage[utf8x]{inputenc}     % кодировка символов, используемая в данном файле
\usepackage[russian]{babel}      % пакет русификации
\usepackage{tikz}                % для создания иллюстраций
\usepackage{pgfplots}            % для вывода графиков функций
\usepackage{geometry}        % для настройки размера полей
\usepackage{indentfirst}         % для отступа в первом абзаце секции

% выбираем размер листа А4, все поля ставим по 3см
\geometry{a4paper,left=30mm,top=30mm,bottom=30mm,right=30mm}

\setcounter{secnumdepth}{0}      % отключаем нумерацию секций

\usepgfplotslibrary{fillbetween} % для изображения областей на графиках

\begin{document}
% Титульный лист
\begin{titlepage}
    \begin{center}
    {\small \sc Московский государственный университет \\имени М.~В.~Ломоносова\\
    Факультет вычислительной математики и кибернетики\\}
    \vfill
    {\Large \sc Отчет по заданию №6}\\
    ~\\
    {\large \bf <<Сборка многомодульных программ. \\
    Вычисление корней уравнений и определенных интегралов.>>}\\
    ~\\
    {\large \bf Вариант 5 / 2* / 3}
    \end{center}
    \begin{flushright}
    \vfill {Выполнил:\\
    студент 101 группы\\
    Боровко~Н.~А.\\
    ~\\
    Преподаватель:\\
    Дудина~И.~А.}
    \end{flushright}
    \begin{center}
    \vfill
    {\small Москва\\2021}
    \end{center}
\end{titlepage}

% Автоматически генерируем оглавление на отдельной странице
\tableofcontents
\newpage

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

Нашей задачей является написание и сборка программы из нескольких файлов, позволяющей для 3 заданных функций найти их точки пересечения и соответствующую ограниченную площадь. Ключевые моменты:
\begin{itemize}
\item точки пересечения находятся \textbf{методом хорд} либо \textbf{бисекции}, интеграл считается по \textbf{формуле Симпсиона},
\item функции надо написать на ассемблере, остальную часть программы на Си,
\item программа должна поддерживать ряд ключей, позволяющий запускать ее в разных режимах,
\item необходимо вручную найти отрезок для поиска точек пересечения и обосновать его выбор,
\item нужны свои тестовые функции и возможность запускать тестирование на них вместо заданных,
\item выбор погрешностей $\varepsilon_1$ и $\varepsilon_2$ для вычисления корня и интеграла соответственно должен гарантировать общую точность $\varepsilon$.
\end{itemize}

\newpage

\section{Математическое обоснование}

Необходимо определить, при каких $\varepsilon_1$ и $\varepsilon_2$ общая точность будет не хуже $\varepsilon$. Заметим, что если каждая из 3 точек пересечения двух кривых, лежит в "квадрате погрешности" с центром в правильной точке пересечения и стороной $\varepsilon_1$, то такая площадь отличается от правильной не сильнее, чем на сумму площадей этих квадратов, т. е. на $3\varepsilon_1^2$. Поскольку площадь мы вычисляем как сумму интегралов, а каждое такое вычисление дает в худшем случае погрешность $\varepsilon_2$, суммарная точность будет не хуже $3\varepsilon_1^2 + x\varepsilon_2$, где $x$ - то, сколько раз вызывается функция integral, поэтому итоговое неравенство, которому должны удовлетворять числа: $3\varepsilon_1^2 + x\varepsilon_2 \leq \varepsilon$, в моем случае $x = 2$, $\varepsilon = 0.001$, поэтому можно взять $\varepsilon_1 = \varepsilon_2 = 0.00001$.

Вторые производные наших функций равны $0.7$, $0$ и $\frac{2}{(x+2)^3}$ соответственно. Для метода хорд достаточно~\cite{1} непрерывной дифференцируемости функции и сохранения знака ее 2 производной. Это означает, что для поиска точки пересечения функций $f_1$ и $f_3$ надо взять отрезок от $-1.9$ до $-1.5$ ($f_{13}^{''}(x) = 0.7 - \frac{2}{(x+2)^3}$, $f_{13}^{''}(-1.9) = 0.7 - \frac{2}{0.1^3} > 0$, $f_{13}^{''}(-1.5) = 0.7 - \frac{2}{0.5^3} > 0$, а также производная монотонно убывает на отрезке, поэтому знак будет сохраняться). Остальные 2 точки тривиальны и находятся на отрезке от $-1$ до $1$, поскольку $f_{12}^{''}$ и $f_{23}^{''}$ - константы, и для них сохранение знака очевидно.

Для метода бисекции требуется~\cite{1} только непрерывность и неравенство знаков на концах отрезка, уже выбранные отрезки удовлетворяют этим условиям:\\$f_{13}(x) = 0.35x^2-0.95x+2.7 - \frac{1}{x+2}$,\\ $f_{13}(-1.9) = 0.35(-1.9)^2+0.95*1.9+2.7 - \frac{1}{0.1} < 0$,\\ $f_{13}(-1.5) = 0.35(-1.5)^2+0.95*1.5+2.7 - \frac{1}{0.5} > 0$,\\ $f_{12}(x) = 0.35x^2-0.95x+2.7 - (3x+1)$,\\ $f_{12}(-1) = 0.35+0.95+2.7 + 2 > 0$,\\ $f_{12}(1) = 0.35-0.95+2.7 - 4 < 0$,\\ $f_{23}(x) = (3x+1) - \frac{1}{x+2}$,\\ $f_{23}(-1) = -2 - 1 < 0$,\\ $f_{23}(1) = 4 - \frac{1}{3} > 0$,\\поэтому и метод бисекции будет работать на них.

Находить интеграл будем последовательным делением отрезка на $2^n$ равных отрезков на $n$-ом шаге, вычислением интеграла на каждом и суммированием этих значений. Корректность этого способа следует из того, что при $n\to+\infty$ значение будет сходиться~\cite{2}.

\newpage
\begin{figure}[h]
\centering
\begin{tikzpicture}
\begin{axis}[% grid=both,                % рисуем координатную сетку (если нужно)
             axis lines=middle,          % рисуем оси координат в привычном для математики месте
             restrict x to domain=-8:8,  % задаем диапазон значений переменной x
             restrict y to domain=-3:8,  % задаем диапазон значений функции y(x)
             axis equal,                 % требуем соблюдения пропорций по осям x и y
             enlargelimits,              % разрешаем при необходимости увеличивать диапазоны переменных
             legend cell align=left,     % задаем выравнивание в рамке обозначений
             scale=2.5]                    % задаем масштаб 2:1

% первая функция
% параметр samples отвечает за качество прорисовки
\addplot[green,samples=256,thick] {0.35*x*x - 0.95*x + 2.7};
% описание первой функции
\addlegendentry{$y=0.35x^2-0.95x+2.7$}

% добавим немного пустого места между описанием первой и второй функций
\addlegendimage{empty legend}\addlegendentry{}

% вторая функция
\addplot[blue,samples=256,thick] {3*x+1};
\addlegendentry{$y=3x+1$}

% дополнительное пустое место не требуется, так как формулы имеют небольшой размер по высоте

% третья функция
\addplot[red,samples=256,thick] {1/(x+2)};
\addlegendentry{$y=\frac{1}{x+2}$}
\end{axis}
\end{tikzpicture}
\caption{Плоская фигура, ограниченная графиками заданных уравнений}
\label{plot1}
\end{figure}

\newpage

\section{Результаты экспериментов}

\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\hline
Кривые & $x$ & $y$ \\
\hline
1 и 2 &  0.4482 & 2.3445 \\
2 и 3 &  -0.1529 & 0.5414 \\
1 и 3 & -1.8211 & 5.5909 \\
\hline
\end{tabular}
\caption{Координаты точек пересечения}
\label{table1}
\end{table}

\begin{figure}[h]
\centering
\begin{tikzpicture}
\begin{axis}[% grid=both,                % рисуем координатную сетку (если нужно)
             axis lines=middle,          % рисуем оси координат в привычном для математики месте
             restrict x to domain=-2:4,  % задаем диапазон значений переменной x
             restrict y to domain=-1:6,  % задаем диапазон значений функции y(x)
             axis equal,                 % требуем соблюдения пропорций по осям x и y
             enlargelimits,              % разрешаем при необходимости увеличивать диапазоны переменных
             legend cell align=left,     % задаем выравнивание в рамке обозначений
             scale=2,                    % задаем масштаб 2:1
             xticklabels={,,},           % убираем нумерацию с оси x
             yticklabels={,,}]           % убираем нумерацию с оси y

% первая функция
% параметр samples отвечает за качество прорисовки
\addplot[green,samples=256,thick,name path=A] {0.35*x*x - 0.95*x + 2.7};
% описание первой функции
\addlegendentry{$y=0.35x^2-0.95x+2.7$}

% добавим немного пустого места между описанием первой и второй функций
\addlegendimage{empty legend}\addlegendentry{}

% вторая функция
% здесь необходимо дополнительно ограничить диапазон значений переменной x
\addplot[blue,domain=-0.5:4,samples=256,thick,name path=B] {3*x+1};
\addlegendentry{$y=3x+1$}

% дополнительное пустое место не требуется, так как формулы имеют небольшой размер по высоте

% третья функция
\addplot[red,samples=256,thick,name path=C] {1/(x+2)};
\addlegendentry{$y=\frac{1}{x+2}$}

% закрашиваем фигуру
\addplot[blue!20,samples=256] fill between[of=A and B,soft clip={domain=-0.1529:0.4482}];
\addplot[blue!20,samples=256] fill between[of=A and C,soft clip={domain=-1.8211:-0.1529}];
\addlegendentry{$S=5.1202$}


\end{axis}
\end{tikzpicture}
\caption{Плоская фигура, ограниченная графиками заданных уравнений}
\label{plot2}
\end{figure}

\newpage

\section{Структура программы и спецификация функций}

\begin{enumerate}
    \item \texttt{\small int sign(double x)} - определение знака числа типа double.
    \item \texttt{\small void swap(double *a, double *b)} - обмен значений по 2 указателям на double.
    \item \texttt{\small double (*g1)(double), (*g2)(double)} - указатели на 2 функции, для которых ищется точка пересечения.
    \item \texttt{\small double f(double x)} - функция $g_1(x) - g_2(x)$.
    \item \texttt{\small double f1(double x), double f2(double x), double f3(double x)} - сами заданные функции, записанные на ассемблере и подключенные из Си.
    \item \texttt{\small double d1(double x), double d2(double x), double d3(double x)} - выбранные нами функции для тестирования.
    \item \texttt{\small double method1(double a, double b, double eps1, double(*func1)(double), double(*func2)(double))} - функция нахождения точки пересечения методом хорд.
    \item \texttt{\small double method2(double a, double b, double eps1, double(*func1)(double), double(*func2)(double))} - функция нахождения точки пересечения методом бисекции.
    \item \texttt{\small double root(double a, double b, double eps1, double(*func1)(double), double(*func2)(double))} - буферная функция, вызывающая один из методов в зависимости от передачи ключа -DBISECTION.
    \item \texttt{\small double formula(double a, double b, double(*g)(double))} - формула Симпсона вычисления интеграла на отрезке.
    \item \texttt{\small double integral(double a, double b, double eps2, double(*g)(double))} - функция вычисления интеграла делением отрезка на более мелкие и вызовом формулы Симпсона для каждого.
    \item \texttt{\small void print\_help()} - вывод всех допустимых ключей.
    \item \texttt{\small int main(int argc, char *argv[])} - главная функция, осуществляющая основной функционал.
\end{enumerate}

\begin{figure}
    \centering
        \includegraphics[scale=1.0]{images/ww.png}
    \caption{Схема взаимодействия функций программы}
\end{figure}

\newpage

\section{Сборка программы (Make-файл)}

Ввиду необходимости смены метода нахождения корня на этапе препроцессирования, мы должны задать дополнительные команды сборки, которые отличаются от стандартных тем, что при указании команды для сборки файла main.o мы передаем ключ \texttt{-DBISECTION}, который позволит использовать \texttt{\#ifdef BISECTION} в коде основной программы.
\texttt{\small \\\\
all: program \\
using\_bisection: program\_bisection \\
program: main.o func.o \\
\- \ \ \ gcc -m32 func.o main.o -lm -o program \\
program\_bisection: main.o\_bisection func.o \\
\- \ \ \ gcc -m32 func.o main.o -lm -o program \\
main.o: main.c \\
\- \ \ \ gcc -m32 -c main.c -o main.o \\
main.o\_bisection: main.c \\
\- \ \ \ gcc -m32 -c main.c -DBISECTION -o main.o \\
func.o: func.asm \\
\- \ \ \ nasm -f elf32 -o func.o func.asm \\
clean: \\
\- \ \ \ rm -rf *.o program \\\\
}
Всего программа состоит из 2 модулей: main.o, полученный из main.c и func.o, полученный из func.asm. Функция main находится в первом файле, из второго файла выхываются только необходимые функции кривых f1, f2, f3.

\newpage

\section{Отладка программы, тестирование функций}

Для тестирования разработаны ключи \texttt{-testroot} и \texttt{-testint} для отладки функций \texttt{root} и \texttt{integral} соответственно. Для заданных функций надо передавать номера 1, 2, 3, а для дополнительных номера 4, 5, 6. В качестве дополнительных функций можно взять $x$, $\frac{1}{x}$, $2x^4$. Их вторые производные . Входные данные задаются в формате "левая\_граница правая\_граница точность функция\_1 функция\_2". Результаты тестирования:\\\\
\texttt{0.5 2 0.001 4 5} \\
\texttt{Output: 1.000000 is abscissa}\\
(правильный ответ: 1, вторая производная: $\frac{-2}{x^3}$) \\\\
\texttt{0.5 1 0.001 4 6} \\
\texttt{Output: 0.793701 is abscissa}\\
(правильный ответ: $\frac{1}{2^{\frac{1}{3}}}$, вторая производная: $-24x^2$) \\\\
\texttt{0.5 1 0.001 5 6} \\
\texttt{Output: 0.870551 is abscissa}\\
(правильный ответ: $\frac{1}{2^{\frac{1}{5}}}$, вторая производная: $\frac{2}{x^3} - 24x^2$) \\\\

Входные данные для тестирования интеграла задаются в формате "левая\_граница правая\_граница точность функция". Результаты тестирования:\\\\
\texttt{0 10 0.001 4} \\
\texttt{Output: 50.000000 is answer for this integral}\\
(правильный ответ: 50) \\\\
\texttt{3 6 0.001 5} \\
\texttt{Output: 0.693148 is answer for this integral}\\
(правильный ответ: $log(2)$) \\\\
\texttt{5 10 0.001 6} \\
\texttt{Output: 38750.000050 is answer for this integral}\\
(правильный ответ: 38750) \\\\

\newpage

\section{Программа на Си и на Ассемблере}

Коды обоих модулей, а также Make-файл, находятся в прилагаемом архиве. Для запуска необходимо перенести все файлы архива в отдельную папку, открыть в ней терминал, и ввести \\\\ \texttt{\small make all} \\ \texttt{\small ./program} (со всеми необходимыми ключами).

\newpage

\section{Анализ допущенных ошибок}

Первая ошибка заключалась в некорректной работе с функциями из ассемблера. Для правильной работы необходимо перед функцией \texttt{f} прописать \texttt{global f}, а в Си объявить ее в виде \texttt{extern double f(double x);}. \\

Вторая ошибка связана c неправильной работой с Make-файлом и вызовом метода бисекции. Для корректной работы в Make-файле нужна строка \texttt{gcc -m32 -c main.c -DBISECTION -o main.o}. Тогда в Си-файле можно воспользоваться слудующей инструкцией: \\\\\texttt{
\#ifdef BISECTION \\
int method = 2; \\
\#else \\
int method = 1; \\
\#endif \\}

Теперь в зависимости от значения \texttt{method} мы вызываем нужный метод.

\newpage
\begin{raggedright}
\addcontentsline{toc}{section}{Список цитируемой литературы}
\begin{thebibliography}{99}
\bibitem{1} Демидович Б. П., Марон И. А. Основы вычислительной математики. — Москва: Наука, 1970.
\bibitem{2} Костомаров Д. П., Фаворский А. П. Вводные лекции по численным методам. Москва: Логос, 2004.
\end{thebibliography}
\end{raggedright}


\end{document}