\documentclass[a4paper,12pt]{article}
\usepackage[left=2cm,right=2cm,
    top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage{amsmath, amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{cite}
\usepackage{listings}
\lstset{extendedchars=\true, inputencoding=utf8}
\usepackage{color}
\usepackage{float}
\usepackage{caption}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\lstset{
    language=C++,
    aboveskip=3mm,
    belowskip=3mm,
    showstringspaces=false,
    columns=flexible,
    basicstyle={\small\ttfamily},
    numbers=left,
    numberstyle=\tiny\color{mygray},
    keywordstyle=\color{blue},
    commentstyle=\color{mygreen},
    stringstyle=\color{mymauve},
    breaklines=true,
    breakatwhitespace=true,
    tabsize=4
}

\begin{document}

\begin{titlepage}
    \begin{center}
        \vspace*{2cm}
        \Large{\textbf{Отчёт по реализации метода наименьших квадратов для полиномиальной аппроксимации}}\\[1.5cm]
        
        \normalsize
        \textbf{Выполнил:} Давыдов Даниил Андреевич\\
        \textbf{Проверил:} Малыхин Дмитрий Андреевич\\[2cm]
        
        \textbf{Дата:} \today
    \end{center}
\end{titlepage}

\tableofcontents
\newpage

\section{Введение}

В данном отчёте рассматривается реализация метода наименьших квадратов для полиномиальной аппроксимации экспериментальных данных. Цель работы — разработать программу на C++ для вычисления коэффициентов полинома заданной пользователем степени, а также визуализировать результаты с помощью Python.

\section{Теоретическая часть}

\subsection{Метод наименьших квадратов}

Метод наименьших квадратов (МНК) — это статистический метод, предназначенный для нахождения параметров модели, минимизирующих сумму квадратов отклонений между измеренными значениями и значениями, предсказанными моделью.

Пусть у нас есть набор данных $(x_i, y_i)$, $i = 1, 2, \ldots, N$. Требуется найти функцию $P(x)$, которая минимизирует сумму квадратов отклонений:

\[
S = \sum_{i=1}^{N} [y_i - P(x_i)]^2 \rightarrow \min.
\]

\subsection{Полиномиальная аппроксимация}

В случае полиномиальной аппроксимации искомая функция $P(x)$ задаётся в виде полинома степени $n$:

\[
P(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n,
\]

где $a_0, a_1, \dots, a_n$ — искомые коэффициенты.

\subsection{Получение системы нормальных уравнений}

Для минимизации суммы $S$ по коэффициентам $a_j$ необходимо занулить частные производные:

\[
\frac{\partial S}{\partial a_j} = -2 \sum_{i=1}^{N} [y_i - P(x_i)] x_i^j = 0.
\]

В результате получаем систему нормальных уравнений:

\[
\sum_{k=0}^{n} a_k \sum_{i=1}^{N} x_i^{k+j} = \sum_{i=1}^{N} y_i x_i^j, \quad j = 0, 1, \dots, n.
\]

Матрица этой системы имеет размерность $(n+1)\times(n+1)$ и заполняется суммами степеней $x_i$.

\subsection{Решение системы уравнений методом Гаусса}

Полученная система линейных алгебраических уравнений решается методом Гаусса:

\begin{itemize}
    \item \textbf{Прямой ход:} Приведение расширенной матрицы к верхнетреугольному виду.
    \item \textbf{Обратный ход:} Вычисление неизвестных коэффициентов полинома путём последовательной подстановки.
\end{itemize}

\subsection{Выбор степени полинома}

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

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

\section{Реализация}

\subsection{Описание программы на C++}

Программа на C++ реализует следующий функционал:

\begin{itemize}
    \item \textbf{Чтение данных:} Считывает пары $(x_i, y_i)$ из стандартного ввода.
    \item \textbf{Ввод степени полинома:} Пользователь задаёт степень полинома через аргумент командной строки.
    \item \textbf{Вычисление коэффициентов:} Использует функцию \texttt{polynomialFit} для решения системы нормальных уравнений методом Гаусса и нахождения коэффициентов.
    \item \textbf{Вывод результатов:} Отображает степень полинома и вычисленные коэффициенты.
\end{itemize}

\subsection{Структура кода}

Основные функции программы:

\begin{enumerate}
    \item \textbf{\texttt{polynomialFit}}: Решает систему нормальных уравнений и возвращает вектор коэффициентов.
    \item \textbf{\texttt{calculateError}}: Вычисляет сумму квадратов отклонений для проверки качества аппроксимации (не обязателен для вывода, но может использоваться при анализе).
\end{enumerate}

\subsection{Код программы}

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

\begin{lstlisting}
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <iomanip>
#include <string>
#include <sstream>
#include <cstdlib>

std::vector<double> polynomialFit(const std::vector<double>& x, const std::vector<double>& y, int degree) {
    int N = (int)x.size();
    int n = degree;

    std::vector<double> coeffs(n + 1, 0.0);

    std::vector<std::vector<double>> A(n + 1, std::vector<double>(n + 2, 0.0));

    // Заполнение матрицы нормальных уравнений
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            double sum = 0.0;
            for (int k = 0; k < N; ++k) {
                sum += std::pow(x[k], i + j);
            }
            A[i][j] = sum;
        }
        double sum = 0.0;
        for (int k = 0; k < N; ++k) {
            sum += y[k] * std::pow(x[k], i);
        }
        A[i][n + 1] = sum;
    }

    // Прямой ход метода Гаусса
    for (int i = 0; i <= n; ++i) {
        double maxElement = std::fabs(A[i][i]);
        int maxRow = i;
        for (int k = i + 1; k <= n; ++k) {
            if (std::fabs(A[k][i]) > maxElement) {
                maxElement = std::fabs(A[k][i]);
                maxRow = k;
            }
        }

        for (int k = i; k <= n + 1; ++k) {
            std::swap(A[maxRow][k], A[i][k]);
        }

        for (int k = i + 1; k <= n; ++k) {
            double factor = -A[k][i] / A[i][i];
            for (int j = i; j <= n + 1; ++j) {
                if (i == j) {
                    A[k][j] = 0;
                } else {
                    A[k][j] += factor * A[i][j];
                }
            }
        }
    }

    // Обратный ход
    for (int i = n; i >= 0; --i) {
        coeffs[i] = A[i][n + 1] / A[i][i];
        for (int k = i - 1; k >= 0; --k) {
            A[k][n + 1] -= A[k][i] * coeffs[i];
        }
    }

    return coeffs;
}

double calculateError(const std::vector<double>& x, const std::vector<double>& y, const std::vector<double>& coeffs) {
    double error = 0.0;
    int N = x.size();
    int degree = coeffs.size() - 1;

    for (int i = 0; i < N; ++i) {
        double yi = 0.0;
        for (int j = 0; j <= degree; ++j) {
            yi += coeffs[j] * std::pow(x[i], j);
        }
        error += std::pow(y[i] - yi, 2);
    }
    return error;
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        std::cerr << "Ошибка: не указана степень полинома. Использование: " << argv[0] << " degree" << std::endl;
        return 1;
    }

    int degree = std::atoi(argv[1]);
    if (degree < 0) {
        std::cerr << "Ошибка: степень полинома должна быть неотрицательным числом." << std::endl;
        return 1;
    }

    std::vector<double> x;
    std::vector<double> y;

    std::string line;
    while (std::getline(std::cin, line)) {
        std::stringstream ss(line);
        double xi, yi;
        if (ss >> xi >> yi) {
            x.push_back(xi);
            y.push_back(yi);
        }
    }

    if (x.size() != y.size() || x.empty()) {
        std::cerr << "Ошибка: некорректные входные данные." << std::endl;
        return 1;
    }

    std::vector<double> coeffs = polynomialFit(x, y, degree);

    std::cout << std::fixed << std::setprecision(6);
    std::cout << "DEGREE " << degree << std::endl;
    std::cout << "COEFFICIENTS ";
    for (size_t i = 0; i < coeffs.size(); ++i) {
        std::cout << coeffs[i];
        if (i != coeffs.size() - 1)
            std::cout << ", ";
    }
    std::cout << std::endl;

    return 0;
}
\end{lstlisting}

\section{Результаты}

\subsection{Пример тестирования}

Используя тестовые данные:

\begin{verbatim}
-3 9
-1 3
0 0
1 3
3 9
\end{verbatim}

Вызов программы (например, для полинома степени 2):

\begin{verbatim}
./polynomial_fit 2 < data.txt
\end{verbatim}

Программа выдаст коэффициенты для квадратичного полинома, аппроксимирующего заданные точки.

\subsection{Вывод программы}

Пример вывода программы при вводе степени полинома 2:

\begin{verbatim}
DEGREE 2
COEFFICIENTS 0.000000, 0.000000, 3.000000
\end{verbatim}

\subsection{Графическая визуализация}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{approximation.png}
    \caption{Аппроксимация данных полиномом 2 степени}
    \label{fig:approximation}
\end{figure}

На рисунке \ref{fig:approximation} представлены исходные данные и линия, соответствующая найденному квадратичному полиному.

\section{Заключение}

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

\newpage
\section{Используемые источники}

\begin{enumerate}
	\item \url{http://www.mathprofi.ru/metod_gaussa_dlya_chainikov.html}
	\item \url{http://www.mathprofi.ru/metod_naimenshih_kvadratov.html}
	\item \url{https://habr.com/ru/articles/672540/}
	\item \url{https://web.williams.edu/Mathematics/sjmiller/public_html/BrownClasses/54/handouts/MethodLeastSquares.pdf}
\end{enumerate}

\end{document}