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

Материал из Викиверситета
Перейти к навигации Перейти к поиску

Пусть - точное значение некоторой величины. - приближенное. Абсолютная погрешность . Относительная погрешность . Точное значение: . , - границы погрешностей: ,

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


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


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


Доказательство.
  1. . Разделив обе части на при и получим результат

при и получим результат


Теорема. . Пусть функция является дифференцируемой функцией каждого аргумента. Тогда

Здесь - это n-мерный отрезок, соединяющий и - точное и приближенное значение аргумента.

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


Замечание. Так как , то на практике формула имеет вид


Корректность задач[править]

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

  1. Её решение при входных данных
  2. Решение единственно
  3. Решение устойчиво по отношению к малым возмущениям входных данных
Определение. Решение вычислительной задачи называется устойчивым по входным данным , если оно зависит от входных данных непрерывным образом:


Относительная устойчивость: вместо и ставим и

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


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


, где - абсолютное число обусловленности. , где - относительное число обусловленности. Если плохо обусловлена.

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

Для интеграла:
Для суммы ряда:

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

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


Определение. Вычислительный алгоритм называется корректным, если:
  1. Он позволяет после выполнения конечного числа элементарных для вычислительной машины операций преобразовать любое входное в результат .
  2. Результат устойчив по отношению к малым возмущениям входных данных.
  3. Результат обладает вычислительной устойчивостью.


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

Определение. Алгоритм называется вычислительно устойчивым, если вычислительная погрешность результата стремится к нулю при ( - машинная погрешность)


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

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


Если , то - число обусловленности алгоритма. Алгоритм плохо обусловлен, если .