Федченко Г.М. Лекции. Численные методы
Подождите немного. Документ загружается.
МЕТОД ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. СТРУКТУРА ПОГРЕШНОСТИ
учитывают вращение Земли вокруг своей оси, зависимость плотности
воздуха и ускорения свободного падения от высоты, кривизну земной
поверхности и метеорологические данные, данные о скорости и направления
ветра, давления воздуха и т.д.
y – погрешность исходных данных, порождает неустранимую
погрешность решения
y = A(x+x) – A(x).
y – погрешность метода. Переходя к другим функциональным
пространствам X, Y , и (или) меняя отображение A , мы
реализуем сравнительно «простую» вычислительную схему
нахождения не точного, а приближенного решения (например,
заменяя интеграл суммой, производную – разностью, функцию –
многочленом, или строя бесконечный итерационный процесс и
обрывая его после конечного числа итераций). Величина
y = y – = A(x) – ()
и представляет собой погрешность метода.
Пример 2.3. Рассмотрим задачу вычисления sin x. Ряд Тейлора для синуса
имеет вид:
sin x = x – + – +...
Ряд сходится для любого
x
, но для вычисления
sin x
необходимо найти
сумму бесконечного ряда чисел, что практически невозможно реализовать.
На практике вычисляют сумму какого-то числа первых членов ряда, а
«хвост» ряда, содержащий бесконечное число членов, отбрасывают. В
результате приближенный результат. Если мы остановимся на первых
четырех членах ряда
y = sin x = + y ,
где = , а ошибка метода y равна сумме бесконечного числа отброшенных
членов ряда. Точно вычислить y невозможно, однако ее можно оценить
сверху: .
y – вычислительная погрешность. При численной реализации вычисления
, которая уже, по предположению, возможна, получают y; \s\up8((,
отличное от в силу округления промежуточных результатов. Таким
образом, вычислительная погрешность может быть описана в виде:
y = – y; \s\up8((= () – y; \s\up8((.
Полная погрешность y получается как сумма всех погрешностей:
y = y + y + y + y.
19
МЕТОД ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. СТРУКТУРА ПОГРЕШНОСТИ
Если вместо погрешностей y, y, y, y удается лишь получить их
абсолютные верхние оценки , , , , то приходится довольствоваться
оценочным представлением общей погрешности:
y + + + .
При решении конкретных задач те или иные виды погрешности могут
различным образом влиять на окончательный результат. Тем не менее, для
исчерпывающего представления о точности окончательного результата в
каждом случае необходим полный анализ погрешностей всех видов. Это в
полной мере относится и к неустранимой погрешности и погрешности
модели. Располагая несовершенной математической моделью, исследователь
должен составить представление о величине погрешности модели. В случае
слишком грубой модели не имеет смысл проводить уточненный анализ
вычислительных ошибок. Следовательно, оценка погрешности модели и
неустранимой погрешности входных данных может послужить удобным
поводом для понижения точности последующих вычислений.
Полезно сразу же сформулировать некоторые эмпирические правила,
которых придерживаются при реализации вычислений:
1) При проведении вычислений надо стремиться, чтобы погрешность
метода y была бы в несколько (2-5) раз меньше неустранимой
погрешности решения y.
2) Вычислительная погрешность y должна быть существенно меньше
всех остальных погрешностей решения, т.е. расчеты надо вести с
таким количеством значащих цифр, чтобы погрешность округления
была существенно меньше всех остальных погрешностей.
2.3. Корректность. Устойчивость
Задача y=A(x) называется корректно поставленной, если для любых
входных данных x из некоторого класса решение y существует, единственно
и устойчиво по входным данным (т.е. непрерывно зависит от входных
данных).
Действительно, чтобы численно решать задачу y=A(x), надо быть
уверенным в том, что искомое решение существует. Естественно также
требовать единственности решения точной задачи: численный алгоритм –
однозначная последовательность действий, и она может привести к одному
решению. Но этих требований недостаточно.
Нас интересует решение y, соответствующее входным данным x. Чаще
всего мы имеем входные данные с погрешностью x+x и находим
возмущенной решение y+y =A(x+x). Погрешность входных данных
порождает неустранимую погрешность y =A(x+x) – A(x).
Если решение непрерывно зависит от входных данных, то
20
МЕТОД ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. СТРУКТУРА ПОГРЕШНОСТИ
||y||0 при ||x||0
и задача (2.3) устойчива по входным данным, в противном случае задача
неустойчива по входным данным.
Отсутствие устойчивости обычно означает, что даже сравнительно
небольшой погрешности x может соответствовать большая погрешность y,
т.е. получаемое при расчете решение будет далеко от искомого.
Непосредственно к такой задаче применять численные методы
бессмысленно, так как погрешности, неизбежно появляющиеся при
численном расчете, будут катастрофически нарастать в ходе вычислений.
На практике даже не всякую формально устойчивую задачу легко
решить. Пусть имеет место оценка
||y|| C ||x||, причем C – велико.
Задача формально устойчива, но фактическая неустранимая ошибка может
быть большой. Этот случай называют слабой устойчивостью или плохой
обусловленностью.
Уже на этапе записи десятичных чисел в компьютер возникают
ошибки округления. Погрешности могут содержаться и в исходных данных
задачи. В ходе вычислений погрешности нарастают. Проблема состоит в
нахождении решения с достаточной точностью.
Пример 2.4. Пусть требуется найти решение уравнения . Это уравнение имеет
вещественный корень, равный 2, кратности 4. Пусть в одном из
коэффициентов допущена ошибка: вместо свободного члена 16 в
развернутом виде многочлена подставлено 15.9999. Таким образом
относительная погрешность, допущенная в этом коэффициенте 0.0006%.
Тогда необходимо вычислить корни полинома
.
Корни удовлетворяют уравнению и, следовательно,
или .
Итак, корнями будут числа , , , . Таким образом, так называемый возмущенный
многочлен имеет корни, которые отличаются от корней исходного полинома на
5%, причем не только вещественные.
Пример 2.5. Линейная система
имеет единственное решение x=1, y=1. Допустив абсолютную погрешность в
0.01 в правой части первого уравнения, получим возмущенную систему
с единственным решением x=11.01, y=0. Последнее никак не назовешь
близким к решению исходной системы.
21
МЕТОД ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. СТРУКТУРА ПОГРЕШНОСТИ
Замечание. В примерах 2.4, 2.5 малые изменения входных данных приводят к
гораздо большим изменениям решения независимо от того, каким методом
вычисляется решение. Подобные задачи называют плохо обусловленными.
Эту сверхчувствительность решения невозможно уменьшить каким-либо
вычислительным приемом; она связана с самой задачей, а не с методом.
Даже если задача устойчива, то численный алгоритм может быть
неустойчивым. Например, если производные заменяются разностями, то
приходится вычитать близкие числа, при этом существенно теряется
точность. Неточные промежуточные результаты используются в дальнейших
вычислениях, и ошибки могут сильно нарастать.
Пример 2.6. Ряд Тейлора для функции
сходится для всех значений аргумента x. Ниже приведен алгоритм
вычисления приближенного значения суммы этого ряда. Суммирование
заканчивается при отсутствии изменений в значении частичной суммы ряда.
Входные данные: x
// s, a, x – величины вещественного типа
1. s:=1
2. a:=x
3. n:=1
4. пока s+a < > s
5. s:=s+a
6. n:=n+1
7. a:=a*x/n
Выходные данные: s – приближенное значение величины
Результаты вычислений по данному алгоритму для вещественных
чисел одинарной точности для различных значений x приведены в таблице.
Вычисленные значения сравниваются с и приводится их относительная
погрешность.
x
(алгоритм) относительная погрешность
25 7.2004911·10 7.2004899·10 1.6·10
20 4.8516528·10 4.8516520·10 1.7·10
15 3.2690175·10 3.2690174·10 3.9·10
10 2.2026469·10 2.2026466·10 1.3·10
5 1.4841318·10 1.4841316·10 1.2·10
22
МЕТОД ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. СТРУКТУРА ПОГРЕШНОСТИ
1 2.71828198 2.71828183 5.7·10
0 1 1 0
–1 3.6787939·10 3.6787944·10 1.4·10
–5 6.7374613·10 6.7379470·10 7.2·10
–10 –7.265709·10 4.5399930·10 2.6
–15 9.3568088·10 3.0590232·10 3.1·10
–20 7.5668406·10 2.0611536·10 3.7·10
–25 1.2487959·10 1.3887944·10 9·10
Для x0 результат алгоритма согласуется с ожидаемым значением. Но этого
нет при x<0. В некоторых случаях даже неверны знаки, а уже при x = –10
относительная погрешность достигает 260%.
Замечание. В примере 2.6 причина затруднений кроется не в задаче, а в
выборе алгоритма. Подобные алгоритмы называют неустойчивыми. Плохо
продуманный алгоритм может дать плохой ответ даже для идеально
обусловленной задачи.
По аналогии можно говорить о корректности алгоритма =(),
подразумевая существование и единственность приближенного решения для
любых входных данных некоторого класса и устойчивость относительно
всех ошибок в исходных данных и промежуточных вычислениях.
В рамках раздела «Численные методы» рассматриваются следующие
вопросы:
1. конструирование дискретной (вычислительной) модели ;
2. разработка на ее основе соответствующих алгоритмов решения
редуцированной задачи вычисления =();
3. анализ погрешности метода и вычислительной погрешности
алгоритма, реализующего вычисления .
2.4. Контрольные вопросы и упражнения
1. Назовите и охарактеризуйте основные этапы решения задачи методом
математического моделирования.
2. В чем состоит основная задача и метод вычислительной математики?
3. Какая задача называется корректно поставленной?
4. Какая задача называется устойчивой по входным данным?
5. Какая задача называется слабо устойчивой по входным данным?
Приведите примеры.
6. Какой численный метод называется корректным?
23
МЕТОД ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. СТРУКТУРА ПОГРЕШНОСТИ
7. Какой вычислительный алгоритм называется неустойчивым? Приведите
примеры.
8. Попытайтесь объяснить, в чем причина неустойчивости алгоритма
вычисления , приведенного в примере 2.6.
9. Познакомьтесь с содержанием Приложения 2. Ответьте на контрольные
вопросы и выполните упражнения.
24
ТЕОРИЯ ПОГРЕШНОСТЕЙ
Лекция 3
ТЕОРИЯ ПОГРЕШНОСТЕЙ
3.1. Абсолютная погрешность
Значение величины, в истинности которого мы не сомневаемся,
называется точным. Часто, отыскивая значение какой-либо величины,
получают лишь ее приближенное значение.
Пусть A – точное значение некоторой величины (как правило, оно
неизвестно), a – известное приближение к нему (т.е. приближенное значение
для A). Этот факт обозначают: A a или a A. Например, – число точное,
но вследствие его иррациональности при вычислениях можно пользоваться
лишь его приближенным значением. Так 3.14 – приближенное значение для
: 3.14.
Определение 3.1. Разность a – A между приближенным и точным значениями
величины называется погрешностью приближенного значения a.
Степень точности приближений удобно характеризовать с помощью
неотрицательных чисел, поэтому понятие погрешности для этого не годится.
Действительно в случае чисел погрешность может быть как положительным,
так и отрицательным числом, а в случае векторов или функций она также
будет вектором или функцией.
Определение 3.2. Абсолютной погрешностью приближения называется
расстояние
(A, a) между точным и приближенным значениями.
Так как A, как правило, неизвестно,
(A, a) вычислить невозможно.
Тогда прибегают к оценке сверху расстояния между точным и
приближенным значениями.
Определение 3.3. Любое неотрицательное число , удовлетворяющее
неравенству
(A, a) , (3.1)
называется верхней границей абсолютной погрешности (предельной
абсолютной погрешностью) приближенного значения a.
Верхняя граница абсолютной погрешности определяется
неоднозначно. Если
(A, a) , то любое число, превышающее , также
будет верхней границей абсолютной погрешности. На практике стараются
выбрать возможно меньшее число, удовлетворяющее неравенству (3.1) и
25
ТЕОРИЯ ПОГРЕШНОСТЕЙ
именно его использовать для характеристики точности приближенных
значений. В дальнейшем верхнюю границу абсолютной погрешности будем
для краткости называть абсолютной погрешностью приближенного
значения.
Если точное значение A известно, то =
(A, a). Если a = A, то =
(A, a) = 0.
Абсолютная погрешность дает ценную информацию о неизвестном
точном значении A: оно находится от известного приближения a на
расстоянии, не большем чем .
В случае числовых величин имеем
| A – a | a#–p A Oa#+p
Следовательно, найдя приближенное значение a и его абсолютную
погрешность , мы определяем, что точное значение A располагается” на
отрезке [a#–p;Oa#+p], т.е. находится “в пределах от a#–p доOa#+p (иногда
говорят, что именно поэтому называют предельной абсолютной
погрешностью).
Определение 3.4. Если известна абсолютная погрешность
a
приближенного
значения a величины A, то a называют приближением к A с точностью до
a
.
3.2. Относительная погрешность
Знание только абсолютной погрешности недостаточно для
характеристики качества определения приближенного значения искомой
величины.
Пример 3.1. Пусть при взвешивании двух предметов получены значения
a#=p253.5кг и b = 0.7кг с одной и той же точностью до 0.1кг. Хотя = =
0.1кг, ясно, что первое измерение выполнено лучше, чем второе.
Для оценки качества определения приближенного значения искомой
величины вводится понятие относительной погрешности.
Определение 3.5. Относительной погрешностью приближения a искомой
величины A (||A||0) называется неотрицательное число
= .
Так как точное значение величины A обычно неизвестно, его
заменяют приближенным значением и тогда:
= , (||a||0).
26
ТЕОРИЯ ПОГРЕШНОСТЕЙ
Определение 3.6. Любое неотрицательное число
, удовлетворяющее
неравенству
, (3.2)
называется верхней границей относительной погрешности (предельной
относительной погрешностью) приближенного значения a.
Очевидно, за предельную относительную погрешность можно
принять отношение предельной абсолютной погрешности к норме
приближенного значения величины:
= , (||a||0). (3.3)
Формула (3.3) связывает абсолютную и относительную погрешности.
Из нее, в частности, следует важное соотношение:
= ||a|| ·
.
Относительную погрешность часто выражают в процентах:
p=p· 100%
(
p=p· 100%).
Предельная относительная погрешность, как и предельная
абсолютная, не единственна.
Везде далее мы будем использовать предельные погрешности и для
краткости называть их относительная и абсолютная погрешности
приближенного значения. Как и абсолютную погрешность, относительную
погрешность записывают с одной-двумя значащими цифрами и
округляют при необходимости с избытком.
Заметим, что при фиксированном относительная погрешность тем
меньше, чем больше норма приближенного значения величины. Этот факт
хорошо иллюстрируется данными из примера 3.1. Имеем:
= 0.0004, или
0.04%;
= 0.14, или 14%. Это означает, что при взвешивании первого
предмета ошибка составила примерно 0,04%, а второго – 14%.
3.3. Абсолютная и относительная погрешности действительных
чисел
Множество действительных чисел R чаще всего рассматривают с
нормой || x || = | x | для x R и расстоянием между x, y R, определенным как
модуль разности между этими числами
(x, y) = | y – x |.
Следовательно, погрешностью приближенного числа называется
разности между приближенным и точным значениями pa1–ppA, абсолютной
погрешностью приближенного числа называется модуль разности между
приближенным и точным значениями = |pa1–ppA |. Относительной
погрешностью приближенного значения a для искомой точной величины A
(A 0) называется неотрицательное число = , которую можно выразить и в
процентах: = 100%.
27
ТЕОРИЯ ПОГРЕШНОСТЕЙ
Действительными числами выражают значения различных
физических величин, задавая тем самым количественные характеристики
свойств физических объектов (систем, явлений, процессов). Часто значения
физических величин получают с помощью непосредственных измерений,
используя разнообразные измерительные средства. Измерения всегда
производятся с погрешностями, источниками которых являются
ограниченная точность прибора, выбор метода измерений, случайные
процессы, сопровождающие процесс измерения, а в неавтоматизированной
системе еще и индивидуальные особенности оператора. Для уменьшения
влияния случайных ошибок измерения производятся несколько раз и
арифметическое среднее результатов есть наиболее вероятное значение
измеряемой физической величины.
В основе теории случайных погрешностей лежат два положения,
подтвержденные практикой:
1. при большом числе измерений случайные погрешности
одинаковой величины, но разного знака, встречаются одинаково часто;
2. большие (по абсолютной величине) погрешности встречаются
реже, чем малые.
Пусть для определения числовой величины A выполнено n
равноточных независимых измерений, в результате которых получены
приближенные значения a, a, …, a искомой величины. Тогда за
приближенное значение для A можно взять арифметическое среднее
результатов измерений:
A a;\s\up8(– = . (3.4)
При неограниченном увеличении числа измерений арифметическое среднее
стремится к истинному значению измеряемой величины.
Каждое измерение характеризуется своей абсолютной и
относительной погрешностью. Так как появление того или иного значения a
в процессе измерения является случайным событием, величины
арифметического среднего результатов измерений, погрешностей отдельных
измерений и абсолютной погрешности результата серии измерений | A – a;\s\
up8(– | также имеют случайный характер и подчиняются законам теории
случайных величин.
Характеристиками рассеяния отдельных результатов измерений
являются:
1. средняя арифметическая погрешность
(;\s\up8(– = ; (3.5)
2. средняя квадратическая погрешность
S = . (3.6)
Средняя квадратическая погрешность применяется чаще, так как
величина S является оценкой дисперсии распределения случайных величин
28