Основные понятия вычислительной математики

Пусть $A$ - точное значение некоторой величины. $A_{n}$ - приближенное. Абсолютная погрешность $\Delta (A_{n})=|A-A_{n}|$. Относительная погрешность $\delta (A_{n})={\frac {\Delta (A_{n})}{|A|}}$. Точное значение: $A=A_{n}\pm \Delta (A_{n})$ $A=(1\pm \delta (A_{n}))\cdot A_{n}$. ${\overline {\delta }}{A_{n}}$, ${\overline {\Delta }}{A_{n}}$ - границы погрешностей: $|A-A_{n}|\leq {\overline {\Delta }}{A_{n}}$, ${\overline {\delta }}{A_{n}}={\frac {{\overline {\Delta }}{A_{n}}}{|A|}}$

Определение. Значащими цифрами в записи числа называеются все цифры числа, начиная с первой ненулевой слева.

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

Утверждение.

1. $\Delta (A_{n}+B_{n})\leq \Delta (A_{n})\pm \Delta (B_{n})$
2. $\delta (A_{n}\cdot B_{n})=\delta (A_{n})+\delta (B_{n})$
3. $\delta (A_{n}/B_{n})=\delta (A_{n})+\delta (B_{n})$

Доказательство.

1. $\Delta (A_{n}\pm B_{n})=|A_{n}\pm B_{n}-(A+B)|=|(A_{n}-A)\pm (B_{n}-B)|\leq |A_{n}-A|+|B_{n}-B|=\Delta (A_{n})+\Delta (B_{n})$
2. $|A\cdot B|\delta (A_{n}\cdot B_{n})=\Delta (A_{n}\cdot B_{n})=|A\cdot B-A_{n}\cdot B_{n}|=|(A-A_{n})\cdot B\cdot (B-B_{n})\cdot A-(A-A_{n})\cdot (B-B_{n})|\leq \leq |B|\cdot \Delta (A_{n})+|A|\cdot \Delta (B_{n})+\Delta (A_{n})\cdot \Delta (B_{n})=|A\cdot B|(\delta (A_{n})+\delta (B_{n})+\delta (A_{n})\cdot \delta (B_{n}))$. Разделив обе части на $|A\cdot B|$ при $\delta (A_{n})\ll n$ и $\delta (B_{n})\ll 1$ получим результат
3. $|B_{n}|=|B+(B_{n}-B)|\geq |B|\Delta (B_{n})=|B|(1-\delta (B_{n}))$

$\delta (A_{n}/B_{n})={\frac {|A/B-A_{n}/B_{n}|}{|A/B|}}={\frac {|AB_{n}-B_{n}B|}{|AB_{n}|}}={\frac {|A(B_{n}-B)+B(A-A_{n})|}{|AB_{n}|}}\leq {\frac {|A|\Delta (B_{n})+|B|\Delta (A_{n})}{|AB|(1-\delta (B_{n}))}}={\frac {\delta (B_{n})+\delta (A_{n})}{1-\delta (B_{n})}}$ при ${\overline {\delta }}(A_{n})\ll 1$ и ${\overline {\delta }}(B_{n})\ll 1$ получим результат

Теорема. $y=f(x_{1},x_{2},...,x_{n}),x_{i}=x_{i}^{*}\pm \Delta x_{i}$. Пусть функция $f(X)$ является дифференцируемой функцией каждого аргумента. Тогда

$\Delta f(X^{*})=\sum \max {[X,X^{*}]}|{\frac {\delta f}{\delta x_{i}}}|\Delta x_{i}$

Здесь $[X,X^{*}]$ - это n-мерный отрезок, соединяющий $X$ и $X^{*}$ - точное и приближенное значение аргумента.

Доказательство. $X={\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}};f(X)=f(X^{*})+\delta f(X^{*})+{\frac {\delta ^{2}f(X^{*})}{2!}}+...$

$f(x)=f(X^{*})+df(\xi ^{*}),\quad \xi ^{*}\in [X,X^{*}],\quad df(X)=\sum {\frac {\partial f}{\partial x_{i}}}{\frac {dx_{i}}{\Delta x_{i}}}$

$|f(X)-f(X^{*})|\leq \sum {\frac {\partial f(X^{*})}{\partial x_{i}}}\cdot \Delta x_{i},\quad \delta f={\frac {\Delta f(X^{*})}{|f(X)|}}$

Замечание. Так как $X\approx X^{*}$, то на практике формула имеет вид

$\Delta f\leq \sum |{\frac {\partial f(X^{*})}{\partial x_{i}}}|\cdot \Delta x_{i}$

Корректность задач

Вычислительная задача называется корректной, если выполняется:

1. Её решение $y\in Y\exists$ при $\forall$ входных данных $x\in X$
2. Решение единственно
3. Решение устойчиво по отношению к малым возмущениям входных данных

Определение. Решение $Y$ вычислительной задачи называется устойчивым по входным данным $X$, если оно зависит от входных данных непрерывным образом:

$\forall \varepsilon >0\quad \exists \delta =\delta (\varepsilon )>0:(\forall X^{*}:\Delta (X^{*})<\delta \quad \exists Y^{*}:\Delta (Y^{*})<\varepsilon )$

Относительная устойчивость: вместо $\Delta (x^{*})$ и $\Delta (Y^{*})$ ставим $\delta (x^{*})$ и $\delta (Y^{*})$

Определение. Под обусловленностью вычислительной задачи понимается чувствительность её решения к малым погрешностям входных данных.

Определение. Число обусловленности - количественная мера степени обусловленности вычислительной задачи.

$\Delta (Y^{*})\leq \nu _{\Delta }\Delta (X^{*})$, где $\nu _{\Delta }$ - абсолютное число обусловленности. $\delta (Y^{*})\leq \nu _{\delta }\delta (X^{*})$, где $\nu _{\delta }$ - относительное число обусловленности. Если $\nu >10\Rightarrow$ плохо обусловлена.

Обусловленность задачи вычисления значения функции одной переменной:

$\nu _{\Delta }\approx |f'(x)|\qquad \nu _{\delta }={\frac {|x|\cdot |f'(x)|}{|f(x)|}}$

Для интеграла:$\quad I=\int _{a}^{b}f(x)dx\quad \nu _{\Delta }={\frac {\int _{a}^{b}|f(x)|dx}{\int _{a}^{b}f(x)dx}}$

Для суммы ряда:$\quad \nu _{\Delta }={\frac {\sum _{k=0}^{\infty }|a_{k}|}{\sum _{k=0}^{\infty }a_{k}}}$

Корректность алгоритмов

Определение. Вычислительный алгоритм - точное предписание действий над входными данными, задающее вычислительный процесс, направленный на преобразование произвольных входных данных $x\in X$ в полностью определенный этими входными данными результат.

Определение. Вычислительный алгоритм называется корректным, если:

1. Он позволяет после выполнения конечного числа элементарных для вычислительной машины операций преобразовать любое входное $x\in X$ в результат $y$.
2. Результат $y$ устойчив по отношению к малым возмущениям входных данных.
3. Результат $y$ обладает вычислительной устойчивостью.

Пункт 2 - это устойчивость по входным данным. Означает то, что результат непрерывным образом зависит от входных данных при условии, что отсутствует вычислительная погрешность.

Определение. Алгоритм называется вычислительно устойчивым, если вычислительная погрешность результата стремится к нулю при $\varepsilon _{M}\to 0$ ($\varepsilon _{m}$ - машинная погрешность)

Если алгоритм устойчив по входным данным и вычислительно устойчив, то он называется устойчивым.

Определение. Вычислительный алгоритм называют хорошо обусловленным, если малые относительные погрешности округления (характеризуемые числом $\varepsilon _{M}$) приводят к малой относительной вычислительной погрешности $\delta (y^{*})$ результата $y^{*}$

Если $\delta (y^{*})\leq \nu _{A}\varepsilon _{M}$, то $\nu _{A}$ - число обусловленности алгоритма. Алгоритм плохо обусловлен, если $\nu _{A}\gg 1$.