Министерство образования и науки Российской Федерации федеральное государственное бюджетное

образовательное учреждение

высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра компьютерной математики

Пояснительная записка

к курсовой работе по дисциплине

«Языки и технология программирования»

Численное дифференцирование функций. Уточнение методами Ромберга и Эйткена.

Выполнила: студент гр.МКН-206

Тимергалин Р.Д

Проверила: доцент кафедры КМ

Зиннатуллина О.Р.

Уфа 2011

СОДЕРЖАНИЕ

Введение…………………………………………………………………3

Программная реализация метода………………………………………8

Оценка погрешности результата………………………………………12

Заключение……………………………………………………………...21

Список литературы……………………………………………………..22

Введение Численное дифференцирование функций

Пусть функция f(x) дифференцируема в точке x. Тогда значение производной определяется следующими пределами [1]

. (1)

Вычисление первой производной

Для вычисления производной необходимо проведение ряда операций. Можно вычислять значения функции и проводить с ними арифметические действия. Но мы не можем вычислять пределы, поскольку это требует бесконечных затрат ресурсов (времени, памяти и т.д.). Получим приближенные формулы:

. (2)

Пусть - шаг разбиения. Введем обозначение и т.д. Тогда (2) можно переписать в виде

. (3)

Первое из этих трех отношений носит название правой разностной производной, второе – левой, третье – центральной разностной производной.

Вычисление второй производной

Для приближенного вычисления второй производной в качестве примера используем формулу [1]

, (4)

где определяется по формуле (3).

Отметим, что значения правой и левой разностных производных в точке одновременно являются центральными разностными производными и , рассчитанными соответственно в точках и (см. рис. 1).

Рис 1. Схема численного дифференцирования

Тогда

. (5)

Применение экстраполяции для оценки погрешности

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

Более точное значение можно вычислить, пользуясь тем же способом, что и проверяемое. Но это приводит к дополнительным требованиям к ресурсам, которые могут оказаться невыполнимыми. Есть и другой способ: использовать более грубые результаты (с меньшим числом узлов и временем счета). Если погрешность метода подчиняется некоторому закону, то, зная этот закон (в виде характера зависимости, например, степенной, экспоненциальный и т.п.), можно по нескольким результатам провести идентификацию и приближенно предсказать значение, соответствующее бесконечному числу узлов.

Ответить на второй вопрос можно с помощью повторной экстраполяции, т.е. экстраполяцией экстраполированных результатов, полученных для разных наборов исходных данных. В этом случае получается оценка погрешности экстраполированных результатов (или размытость оценки погрешности). Если эта оценка удовлетворяет требованиям: в три и более раз меньше оценки погрешности исходных данных (относительная размытость меньше 1/3 [9]), то цель достигнута. Если нет, то данный способ оценки в конкретном случае следует признать ненадежным. Подробнее о критерии надежности сказано ниже.

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

Численная фильтрация

При экстраполяции требуется априорное знание характера зависимости результата расчетов от числа узлов (или математической модели погрешности), например

, (6)

где – точное значение; – приближенный результат, полученный при числе узловых точек, равном n; – коэффициенты, которые предполагаются не зависящими от n; – величина, полагаемая малой по сравнению с при тех значениях n, которые использовались в данных конкретных расчетах, k₁,…, k_L – произвольные действительные числа (предполагается, что k₁<k₂<…< <k_L).

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

Если решение задачи представляет собой функцию с несколькими непрерывными производными, то можно допустить возможность его разложения по формуле Тейлора, тогда – это часть ряда натуральных чисел. Тогда к задаче нахождения предельного при значения z можно подойти как к задаче интерполяции зависимости от параметра алгебраическим многочленом с последующей экстраполяцией до . Есть и другой подход, приводящий при условии постоянства к тому же алгоритму, но не требующий целочисленности . Это решение задачи численной фильтрации, т.е. последовательное устранение степенных слагаемых суммы (6) при сохранении значения константы z. Рассмотрим два значения , , вычисленные при числе узлов, равном и соответственно. Составим линейную комбинацию

и потребуем, чтобы, суммарный коэффициент при z был равен 1, а при (для определенного j) равен 0. Отсюда получим формулу фильтрации, которая совпадает с экстраполяционной формулой Ричардсона [1]

. (7)

Проводя последовательно экстраполяцию по всем парам соседних значений, получим отфильтрованную зависимость, не содержащую члена с

, (8)

где . (9)

Заметим, что отфильтрованная последовательность содержит на один член меньше, чем исходная. Если она содержит больше одного члена, то ее также можно отфильтровать, устранив степенную составляющую с . Операции фильтрации можно повторять последовательно для ,…, , если исходная последовательность содержит достаточное количество членов. Результаты экстраполяций удобно представлять в виде треугольной матрицы

(10)

Применение повторной экстраполяции при k_j=j известно под названием метода Ромберга. При его применении возникает ряд ограничений.

Применение повторной экстраполяции приводит к изменению коэффициентов суммы (6). При увеличение абсолютной величины коэффициентов может оказаться весьма существенным. Это ограничивает число возможных экстраполяций.

Величина в (6) может оказаться суммой регулярной составляющей, имеющей вид , и нерегулярной составляющей , обусловленной погрешностью исходных данных, которая, например, связана с ограниченной разрядностью чисел в машинном представлении. Тогда исходная нерегулярная часть погрешности, содержащаяся в вычисленных значениях , при каждой экстраполяции умножается на коэффициент

.

Для метода Ромберга, применяемого к последовательности (6) при , произведение таких множителей ограничено числом, приблизительно равным 8 (получено численно), т.е. метод Ромберга является устойчивым к погрешности исходных данных, но сам уровень нерегулярной погрешности может ограничить число возможных экстраполяций.

Процесс Эйткена

При оценке погрешности частичных сумм значение k в (2.4) может быть неизвестно. В этом случае можно использовать следующую модификацию правила Ричардсона. Вычислим три значения z₁, z₂, z₃ при трех номерах последовательности: n, nQ, nQ² и составим систему трех уравнений [1, 9]

(11)

Найдем разности

,

,

и, разделив одну на другую, определим Q^k

. (12)

Теперь можно найти z

. (13)

Как и в рассмотренных ранее случаях, мы нашли экстраполированное (уточненное) значение z=z*, а вместе с ним и оценку погрешности z_iz*.

Этот способ экстраполяции при неизвестном порядке точности принято называть алгоритмом Эйткена или ²-алгоритмом, который в более общем случае применяется для экстраполяции векторных последовательностей

.

В последнем выражении z_i – векторы, а скобками обозначается скалярное произведение.

Критерий размытости оценки

Оценка погрешности по правилу Рунге сводится к сравнению значения z_n с экстраполированным значением . Поскольку эта оценка справедлива при допущении, что величина точнее, чем z_n, то необходима проверка справедливости этого допущения. Это можно сделать следующим образом. Повторим процесс экстраполяции и получим значение . Разность представляет собой оценку погрешности приближенного значения z_n.. Разность является оценкой погрешности экстраполированного значения или оценкой погрешности оценки погрешности (рис. 10). Отношение имеет смысл относительной размытости оценки погрешности.

Если , то это означает, что относительная размытость оценки мала, и такой оценке можно доверять.

Рис. 10. Размытость оценки погрешности

Пусть оценка погрешности представляется в виде интервала . Для определения порогового значения _n для принятия или отклонения полученной оценки желательно на основании имеющейся информации установить, не может ли при гипотетическом продолжении экстраполяций произойти переход получающихся значений левее или правее . Для этого предположим, что при последующих гипотетических экстраполяциях значение , как коэффициента уменьшения расстояния между соседними экстраполированными значениями, будет сохраняться: . Тогда предельное удаление предельного значения от определяется суммой геометрической прогрессии . Отсюда следует неравенство

, (14)

где K1 – коэффициент «запаса» надежности оценки. Необходимость введения коэффициента K вызвано желанием получать достаточно надежные оценки в условиях неопределенности, вызванной влиянием нерегулярных составляющих погрешности. Тогда получим условие (критерий принятия оценки)

.

Примем величину K=2. Тогда пороговое значение , тогда при оценка принимается, а при отвергается. Это же значение было получено эмпирически при анализе реальных численных данных [9].

Визуализация результатов экстраполяции

Результаты экстраполяции и оценки погрешности удобно представлять на графике в виде зависимости (десятичного логарифма относительной погрешности) от логарифма n (числа отрезков разбиения) или h (шага сетки при равномерном разбиении). При этом каждая составляющая (степенная функция) представлялась бы на таком графике отрезком прямой. Значение ординаты соответствует числу верных знаков. В реальном случае отличие кривой, соответствующей результату определенной экстраполяции, от прямой свидетельствует о влиянии других составляющих погрешности. Надежные оценки получаются при достаточно большом расстоянии между точками кривых.

Оценку погрешности  можно проводить по правилу Рунге (сравнивать приближенное значение с экстраполированным, которое получено для этого приближенного значения). Можно также все приближенные значения сравнивать с одним числом, которое считается наиболее точным. Второй способ является более надежным при наличии нерегулярных составляющих (см. рис. П3.1, П3.2). Оценки погрешности зависят от выбора эталона , с которым сравниваются приближенные значения. Чтобы оценить эту зависимость и связать ее с величиной размытости оценки, рассмотрим разность

. (15)

Величину можно сравнить с и выразить в виде

,

где – некоторый коэффициент. Абсолютная величина связана с неопределенностью выбора эталона. Из практических соображений можно утверждать, что эта величина меньше 1, иначе это существенно исказило бы верхние кривые. Порядок этой величины определяется по графику разностью ординат между точками на двух верхних линиях. Поскольку для ее определения можно использовать не 3 значения, а относительное положение кривых, влияние случайных факторов на оценку погрешности и размытости существенно уменьшается.

Согласно (15) .

Таким образом, величина имеет тот же смысл, что и значение , а если , то эти определения совпадают с точностью до третьего члена геометрической прогрессии.

Численная фильтрация применялась для обработки результатов, полученных различными численными методами. В качестве примера на рис. 11,а приведены результаты вычисления второй производной по симметричной разностной формуле второго порядка, на рис. 11,б результаты численного интегрирования методом правых прямоугольников. В результате анализа можно утверждать, что вычисленные значения интегралов имеют 1-5 точных десятичных знаков, результат первой экстраполяции 3-10 знаков при относительной размытости менее 0.1.

Ограничение на уровне 14-15 знака объясняется погрешностью округления (применялись числа с двойной точностью). При этом следует отметить увеличение погрешности округления при численном дифференцировании с ростом n. При численном интегрировании этот рост погрешности округления менее заметен.

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