1. Аналіз похибок заокруглення

1.1. Види похибок

Нехай необхідно розв’язати рівняння

\begin{equation} \label{eq:1.1.1} A u = f. \end{equation}

За рахунок неточно заданих вхідних даних насправді ми маємо рівняння

\begin{equation} \label{eq:1.1.2} \tilde A \tilde u = \tilde f. \end{equation}

Означення: Назвемо $\delta_1 = u - \tilde u$ неусувною похибкою.

Застосування методу розв’язання \eqref{eq:1.1.2} приводить до рівняння

\begin{equation} \label{eq:1.1.3} \tilde A_h \tilde u_h = \tilde f_h, \end{equation}

де $h > 0$ — малий параметр.

Означення: Назвемо $\delta_2 = \tilde u - \tilde u_h$ похибкою методу.

Реалізація методу на ЕОМ приводить до рівняння

\begin{equation} \label{eq:1.1.4} \tilde A_h^\star \tilde u_h^\star = \tilde f_h^\star. \end{equation}

Означення: Назвемо $\delta_3 = \tilde u_h - \tilde u_h^\star$ похибкою заокруглення.

Означення: Тоді повна похибка $\delta = u - \tilde u_h^\star = \delta_1 + \delta_2 + \delta_3$.

Означення: кажуть, що задача \eqref{eq:1.1.1} коректна, якщо

• $\forall f \in F$: $\exists! u \in U$;

• Задача \eqref{eq:1.1.1} стійка, тобто $\forall \varepsilon > 0$: $\exists \delta > 0$:

\begin{equation} | A - \tilde A | < \delta, | f - \tilde f | < \delta \implies | u - \tilde u | < \varepsilon. \end{equation}

Якщо задача \eqref{eq:1.1.1} некоректна, то або розв’язок її не існує, або він неєдиний, або він нестійкий, тобто $\exists \varepsilon > 0$: $\forall \delta > 0$:

\begin{equation} | A - \tilde A | < \delta, | f - \tilde f | < \delta \implies | u - \tilde u | > \varepsilon. \end{equation}

Означення: Абсолютна похибка $\Delta x \le \vert x - x^\star \vert$.

Означення: Відносна похибка $\delta x \le \Delta x / \vert x \vert$, або $\Delta x / \vert x^\star \vert$.

Означення: Значущими цифрами називаються всі цифри, починаючи з першої ненульової зліва.

Означення: Вірна цифра — це значуща, якщо абсолютна похибка за рахунок відкидання всіх молодших розрядів не перевищує одиниці розряду цієї цифри.

Тобто, якщо $x^\star = \alpha_n\ldots\alpha_0.\alpha_{-1}\ldots\alpha_{-p} \ldots$, то $\alpha_{-p}$ вірна, якщо $\Delta x \le 10^{-p}$ (інколи $\Delta x \le w \cdot 10^{-p}$, де $1/2 \le w < 1$ наприклад, $w = 0.55$).

1.2. Підрахунок похибок в ЕОМ

Підрахуємо відносну похибку заокруглення числа $x$ на ЕОМ з плаваючою комою. В $\beta$-ічній системі числення число представляється у вигляді

\begin{equation} \label{eq:1.1.5} x = \pm (\alpha_1 \beta^{-1} + \alpha_2 \beta^{-2} + \ldots + \alpha_t \beta^{-t} + \ldots) \cdot \beta^p, \end{equation}

де $0 \le \alpha_k < \beta$, $\alpha_1 \ne 0$, $k = 1, 2, \ldots$

Якщо в ЕОМ $t$ розрядів, то при відкиданні молодших розрядів ми оперуємо з наближеним значенням

\begin{equation} x^\star = \pm (\alpha_1 \beta^{-1} + \alpha_2 \beta^{-2} + \ldots + \alpha_t \beta^{-t}) \cdot \beta^p \end{equation}

і відповідно похибка заокруглення

\begin{equation} x - x^\star = \pm \beta^p \cdot (\alpha_{t + 1} \beta^{- t - 1} + \ldots). \end{equation}

Тоді її можна оцінити так

\begin{equation} \vert x - x^\star \vert \le \beta^{p - t - 1} \cdot (\beta - 1) \cdot (1 + \beta^{-1} + \ldots) \le \beta^{p - t - 1} \cdot (\beta - 1) \cdot \frac{1}{1 - \beta^{-1}} = \beta^{p - t}. \end{equation}

Якщо в представлені \eqref{eq:1.1.5} взяти $\alpha_1 = 1$, то $\vert x \vert \ge \beta^p \cdot \beta^{-1}$. Звідси остаточно

\begin{equation} \delta x \le \frac{\beta^{p - t}}{\beta^{p - 1}} = \beta^{- t + 1}. \end{equation}

При більш точних способах заокруглення можна отримати оцінку $\delta x \le \frac{1}{2} \cdot \beta^{- t + 1} = \varepsilon$. Число $\varepsilon$ називається «машинним іпсилон». Наприклад, для $\beta = 2$, $t = 24$, $\varepsilon = 2^{-24} \approx 10^{-7}$.

1.3. Підрахунок похибок обчислення значення функції

Нехай задана функція $y = f(x_1, \ldots, x_n) \in C^1 (\Omega)$. Необхідно обчислити її значення при наближеному значенні аргументів $\vec x^\star = (x_1^\star, \ldots, x_n^\star)$, де $\vert x_i - x_i^\star \vert \le \Delta x_i$ та оцінити похибку обчислення значення функції $y^\star = f(x_1^\star, \ldots, x_n^\star)$. Маємо

\begin{equation} \vert y - y^\star \vert = \left\vert f\left(\vec x\right) - f \left(\vec x^\star\right) \right\vert = \left\vert \Sum_{i = 1}^n \frac{\partial f}{\partial x_i} \left(\vec \xi\right) \cdot (x_i - x_i^\star) \right\vert \le \Sum_{i = 1}^n B_i \cdot \Delta x_i, \end{equation}

де $B_u = \Max_{\vec x \in U} \left\vert \dfrac{\partial f}{\partial x_i} \left(\vec x\right) \right\vert$.

Тут

\begin{equation} U = \left\{ \vec x = (x_1, \ldots, x_n) : \left| x_i - x_i^\star \right| \le \Delta x_i \right\} \subset \Omega, \end{equation}

для $i = \overline{1, n}$. Отже з точністю до величин першого порядку малості по

\begin{align} \Delta x &= \Max_i \Delta x_i, \newline \Delta y &= \vert y - y^\star \vert \prec \Sum_{i = 1}^n b_i \cdot \Delta x_i, \end{align}

де $b_i = \left\vert \dfrac{\partial f}{\partial x_i} \left(\vec x^\star \right) \right\vert$ та «$\prec$» означає приблизно менше.

Розглянемо похибки арифметичних операцій.

• Сума: $y = x_1 + x_2$, $x_1, x_2 > 0$:

  \begin{align} \Delta y &\le \Delta x_1 + \Delta x_2, \newline \delta y &\le \frac{\Delta x_1 + \Delta x_2}{x_1 + x_2} \le \Max(\delta x_1, \delta x_2). \end{align}

• Різниця: $y = x_1 - x_2$, $x_1 > x_2 > 0$:

  \begin{align} \Delta y &\le \Delta x_1 + \Delta x_2, \newline \delta y &\le \frac{x_2 \delta x_1 + x_1 \delta x_2}{x_1 - x_2}. \end{align}

  При близьких $x_1$, $x_2$ зростає відносна похибка (за рахунок втрати вірних цифр).

• Добуток: $y = x_1 \cdot x_2$, $x_1, x_2 > 0$:

  \begin{align} \Delta y &\prec x_2 \Delta x_1 + x_1 \Delta x_2, \newline \delta y &\le \delta x_1 + \delta x_2. \end{align}

• Частка $y = x_1 / x_2$, $x_1, x_2 > 0$:

  \begin{align} \Delta y &\prec \frac{x_2 \Delta x_1 + x_1 \Delta x_2}{x_2^2}, \newline \delta y &\le \delta x_1 + \delta x_2. \end{align}

  При малих $x_2$ зростає абсолютна похибка (за рахунок зростання результату ділення).

Означення: Пряма задача аналізу похибок: обчислення $\Delta y$, $\delta y$ по заданих $\Delta x_i$, $i = \overline{1,n}$.

Означення: Обернена задача: знаходження $\Delta x_i$, $i = \overline{1,n}$ по заданих $\Delta y$, $\delta y$. Якщо $n > 1$, маємо одну умову

\begin{equation} \Sum_{i = 1}^n b_i \cdot \Delta x_i < \varepsilon \end{equation}

для багатьох невідомих $\Delta x_i$.

Вибирають їх із однієї з умов:

\begin{equation} \forall i: b_i \cdot \Delta x_i < \frac{\varepsilon}{n} \end{equation}

або

\begin{equation} \Delta x_i < \frac{\varepsilon}{\Sum_{i = 1}^n b_i}. \end{equation}