Методы обработки результатов численного эксперимента для увеличения их точности и надежности

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, ЧИСЛЕННЫЕ МЕТОДЫ И КОМПЛЕКСЫ ПРОГРАММ

УДК 519.6

Н. М. ШЕРЫХАЛИНА

МЕТОДЫ ОБРАБОТКИ РЕЗУЛЬТАТОВ ЧИСЛЕННОГО ЭКСПЕРИМЕНТА ДЛЯ УВЕЛИЧЕНИЯ ИХ ТОЧНОСТИ И НАДЕЖНОСТИ

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

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

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

1. ПОСТАНОВКА ЗАДАЧИ

В практике вычислений очень часто встречается задача определения предела. При вычислении сумм сходящихся рядов, например,

ОО ^

С

*=1

мы имеем дело с последовательностью частичных сумм

п

*, = £<;, а2>

*=1

для которой требуется найти предел при .

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

ь

J / (х) с1,х и а

аГ,шЬ-^±/

п-юо П £—4 \ п }

г=1 4 7

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

Список примеров, в которых получается последовательность, предел которой желательно установить, может быть продолжен. Это решение уравнений, систем уравнений, поиск экстремума функций итерационными методами и т. д.

Итак, в общем случае задача сводится к следующему. Имеется несколько членов последовательности , номера

которых могут быть расположены не подряд, а выборочно по какому-нибудь закону, либо произвольно. Необходимо по этим данным найти приближенно предел последовательности z. Тогда разность ^ — г можно использовать для оценки погрешности приближенного значения ^. Однако, поскольку само значение z получено приближенно, необходимо также иметь критерий, по которому можно судить о мере надежности этой оценки (или об ее точности). Совокупность оценки и критерия

ее надежности позволяет принять решение об окончании расчетов, если можно утверждать, что заданная точность достигнута, или о необходимости продолжения исследований.

2. МЕТОДЫ ЭКСТРАПОЛЯЦИИ И ОЦЕНКИ ПОГРЕШНОСТИ ВЫЧИСЛЕНИЙ ПРИ ИЗВЕСТНОМ ПОРЯДКЕ АППРОКСИМАЦИИ

2.1. Правила Рунге и Ричардсона

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

Ь

п

где г — точное значение; — приближенный результат, полученный при числе узловых точек (или числе слагаемых суммы), равном п; с\ — коэффициент, который предполагается не зависящим от п; к — порядок точности метода; — величина, полагаемая малой по

сравнению с С1П~к при тех значениях п, которые использовались в данных конкретных расчетах.

Вычислив два приближенных значения и гдп для числа узловых точек п и С^)п, (ф > ), пренебрегаем малыми и решаем систему двух уравнений относительно и

Щп = ^ + сі{С}пУ

Из нее находим уточненное по правилу Ричардсона значение

Тогда погрешность приближенного значения по правилу Рунге оценивается разностью .

Данное правило используется при условии, если порядок точности известен, а действительно является пренебрежимо малой величиной при используемом значении .

2.2. Методы Ромберга и Нэвилла

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

= г •

сі гг

С-2П

СіП

8

Тогда, чтобы найти неизвестные г, с\, ... , , нужно использовать значение

и записать задачу в виде системы линейных уравнений, пренебрегая малыми величинами. Эту задачу можно решить путем построения интерполяционного многочлена Лагранжа [1] Ь-й степени и экстраполяцией его до п —> ос

1+1 1+11-1

“ Х'*Г П,- — П:

г=1 _7=1 3 >

зФ>-

ь+1 ь+1 п-\

(гь ... , гь+і) = V г,; ТТ ^ .

“ п.: - гг.-

г=1 _7=1 > 3

ЗФ'І

В скобках перечислены числа , которые использованы для получения экстраполированного значения .

Значение, которое получается по формуле (2.4), может быть найдено путем последовательного применения рекуррентного соотношения Эйткена

п

-і

Ь+1

г (гь .... гі+і) = ------гг (гь ... , гь)-

пі+і^пі

пл

-1

пЬ+1 П1

г

То есть для получения экстраполированного значения Ь+1-го порядка можно использовать два значения -го порядка, вычисленные для двух наборов данных , причем номер первой точки одного набора сдвинут на единицу относительно другого.

В случае, если , выражение

(2.5) принимает вид

г (гь .... гь+і) = г (г-2,.... гь+і) г (г-2,.... гь+і) - г (гі,.

Я1

что при Ь = 1 совпадает с (2.2), а при

Ь > 1 представляет собой аналогичное выражение, в котором вместо вычисленных участвуют экстраполированные значения. Повторное применение правила Ричардсона для экстраполяции результата вычислений гп при последовательном увеличении номера в раз называют методом Ромберга [1]. При этом для уменьшения объема расчетов величина обычно выбирается равной 2 как наименьшему натуральному числу, большему 1.

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

Для последовательности {^„} строится таблица Нэвилла [2,3], представляющая собой матрицу ( ), в которой

нулевой столбец — исходная последовательность, а все остальные столбцы находятся по правилу

=

і - (І - І-) і.л і

= Чь-і

которое является следствием (2.5).

2.3. Метод численной фильтрации

В более общем случае математическая модель погрешности представляется в виде

_Ь1

= г + с\п + с-2П

-к-2

...+сьп~к1- + 8

где &!,... ,кь — произвольные действительные числа, к\ < <    < кь. При увели-

чении п в целое число раз, т. е. щ = пі^'-1, задача определения коэффициентов с* и экстраполированного значения решается аналитически. Для этого рассмотрим два значения , , вычисленные при числе узлов,

равном п\ и П2 = <3^1 соответственно. Составим линейную комбинацию

\) = («? + :\\) * •

ат

УЧ

с і

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

г{1} ~ г

П 2

^П‘2

'"П1

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

г^ = г + с{ 1)П-к^

4-іп кі~1

4+і пкі+і

с) п

п

(1) оЧ-оЩ где с) ) = С[ и 4 .

Заметим, что отфильтрованная последова-

тельность содержит на один член меньше, чем исходная. Если она содержит больше одного члена, то ее также можно отфильтровать, устранив степенную составляющую с . Операции фильтрации можно повторять последовательно для , если ис-

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

п

10 гю —

20 Z20 ^20

40 240 4] г40 -

ап „ „

80 ^80 г80 г80

Таким образом, определение искомого значения и в случае произвольных (в общем случае не целых) показателях (но только при сводится к повторному ис-

пользованию уточнения (2.2), т. е. к фильтрации.

В случае щ ф пхО1^1 задача экстраполяции сводится к решению системы ли-

нейных уравнений типа (2.7) численным методом.

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

2.4. Иллюстрация на численном эксперименте

В табл. 2.1 представлены результаты расчетов сумм (1.2) при а = 1,1 для п = 2-?. Поскольку сумма этого ряда может быть вычислена независимо через интегралы [4]

ии * <("> = £* =

1

а

0 — 1

сН,

00

О

этот пример взят в качестве тестового. При а = 1,1 сумма ряда

^"ГОЧН

и 10,5844484649508098.

Для ряда (1.1) справедливо разложение

у --- у - -----VI 1) + _VI ^ -

*п — Л-ТОЧН 1Ь -у- п

а — 1 I

а —;а+1) , «

2! -6 4!-30 +"'

а (а + 1)... (а + 2_] — 2) Ду (0+27-1) . " (2])\ П +

+ 61

где В2] — числа Бернулли. Будем считать известными показатели при п, и используем метод фильтрации (2.7) для оценки погрешности частичных сумм.

Как видно из табл. 2.1, погрешность гп —

" ^ТОЧН

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

всех приведенных в таблице вполне приемлема, а для совпадает с самой погреш-

ностью с точностью не ниже 3-х десятичных знаков. Погрешность

^точн

уточненных

значений при увеличении быстро уменьшается.

Погрешность

^ТЬ ^ТОЧН

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

В результате первая экстраполяция при уменьшает погрешность результатов до 10-5, а вторая — до Ю-10. Нетрудно подсчитать, что для получения такой точности путем прямого вычисления сумм потребуется более 1050-10100 слагаемых. На современном компьютере это заняло бы более 10 лет.

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

На рис. 2.1 цифрой обозначена зависимость погрешностей

^ТЬ ^ТОЧН

рассчитанных

результатов, цифрами ( обозначены

результаты последовательного вычитания из

^точн

одного, двух и трех и т. д. слагаемых согласно (2.11). Тем самым, рис. 2.1 есть иллюстрация того, как может работать идеальный метод экстраполяции.

0 1 2 3 4

а

0 1 2 3 4

б

Рис. 2.1. Результаты «идеальной экстраполяции» при удвоении числа слагаемых

Ограничение графиков на уровне, соответствующем величине погрешности порядка нескольких единиц 17-го разряда объясняется ограниченной разрядностью чисел в машинном преставлении.

На рис. 2.2 приведены результаты применения повторной фильтрации по формуле (2.8) при <5 = 2. Цифрой 1 обозначена зависимость погрешностей результатов, экстраполированных один раз, цифрой 2 — два раза и т. д. Величина при оценке равнялось 0.1 и далее при возрастании номера значение увеличивалось на 1. Согласно расчетам прямые и совпадают, что объясняется и формулой (2.11), в которой слагаемое с ^=3.1 отсутствует. Из рис. 2.2,а видно, что путем повторной экстраполяции получаются хотя и не идеальные, но весьма точные результаты.

Таблица 2.1

п %п 2-точн г — г

2 -9,11 -6,49 -2,61-10° 2,87-Ю”1 - -

4 -8,60 -7,19 - 1,40-10° 1,63-Ю”1 - 3,50-Ю”1 2,48-Ю”1

8 -8,07 -7,36 - 7,06-10"”1 8,75-Ю”2 - 9,25-Ю”2 1,31-Ю”1

16 -7,55 -7,21 - 3,41-Ю”1 4,52-Ю”2 - 2,24-Ю”2 6,57-Ю”2

32 -7,06 -6,89 - 1,62-Ю”1 2,29-Ю”2 - 5,29-Ю”3 3,26-Ю”2

64 -6,59 -6,51 - 7,63-10"”“ 1,15-Ю”2 - 1,23-Ю”3 1,62-Ю”2

128 -6,15 -6,11 - 3,57-10"”" 5,81-Ю”3 - 2,89-10—1 8,08-Ю”3

256 -5,74 -5,72 - 1,67-10”2 2,91-Ю”3 - 6,74-10”"' 4,03-Ю”3

512 -5,35 -5,35 - 7,80-10”3 1,45-Ю”3 - 1,57-10”"' 2,01-Ю”3

1024 -4,99 -4,99 -3,64-Ю”3 7,28-Ю”4 -3,67-10”° 1,00-Ю”3

2048 -4,66 -4,66 - 1,70-10-* 3,64-Ю”1 - 8,56-Ю”7 5,03-Ю”1

4096 -4,35 -4,35 -7,93-10”1 1,82-Ю”1 - 1,99-Ю”7 2,51-Ю”1

8192 -4,06 -4,06 -3,70-10”1 9,11-10”'"' - 4,65-Ю”8 1,25-Ю”'4

16384 -3,78 -3,78 - 1,72-Ю”4 4,55-10”"' - 1,08-Ю”8 6,29-10”'"'

32768 -3,53 -3,53 - 8,05-10”"' 2,27-10”"' -2,53-Ю”1* 3,14-10”'"'

65536 -3,29 -3,29 - 3,75-10”"' 1,13-10”'"' - 5,91-10”10 1,57-10”'"'

131072 -3,07 -3,07 - 1,75-10”"' 5,69-10”° - 1,37-Ю”10 7,86-10”°

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

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

ггп = г + слщк1 + с2щк'2 + ... + с^п^£,

гГ1,2 = г + С1П2 кг + с-2П2к- + • • • + С1Щкь,

гП£+1 = г + сщ1к+\ + с2п1к+\ + ... + сщ1к+\.

На рис. 2.3, а представлены результаты такой фильтрации расчетов сумм (1.2) при а = = 1,1. Как видно из рис. 2.3, а, таким способом возможно получение уточнения до 6 знаков при п = 10 и до 9 знаков при п = 20-30. При удвоении числа слагаемых при таких получается только 2-4 верных знака. Однако дальнейшее уточнение при увеличении на единицу невозможно из-за накопления погрешности округления. В то же время при удвоении погрешность, связанная с округлением не растет так быстро и позволяет при той же длине мантиссы (порядка 16 десятичных разрядов) уточнить результат до 10 -10

при п = 1000-10000.

Рис. 2.2. Результаты экстраполяции данных, полученных при удвоении числа слагаемых, с помощью фильтрации по формуле (2.8): а — сравнение с точным; б — оценки по правилу Рунге

/

• /

7

V*. 3

**** * 2

— • і а- 1

О

О 0.5 1 1.5

а

3 м#

•

—

•

1

•

О

1 2.5 3 3.5 1э«

б

Рис. 2.3. Результаты экстраполяции данных путем численного решения систем уравнений (2.12) при увеличении числа слагаемых на постоянную величину: а — на единицу; б — на

100

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

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

Метод Нэвилла (2.6) применяется для тех случаев, когда показатели разложения (2.7) увеличиваются пропорционально Ї, т. е.

. В этом случае, обозначив = п^а, приходим к алгебраическому многочлену или степенному ряду. Номера членов

последовательности должны увеличиваться на константу. Поэтому рассмотрим следующий пример

Результаты применения экстраполяции с помощью метода Нэвилла к этой последовательности показаны на рис. 2.4, а. Поскольку последовательность (2.13) представляет алгебраический многочлен относительно п~1, то результаты второй экстраполяции дают теоретически точное значение. Остаточная погрешность вызвана ошибкой округления.

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

0 ‘ 0.5 1 1.5 1ял

а

* •

£

* Л лГ • »г фГ ^4

£001

0 0.5 1 1.5 1§ п

б

Рис. 2.4. Результаты экстраполяции последовательности (2.13) с помощью метода Нэвилла, начинающейся: а — с 1-го номера; б — со 2-го номера

В результате рассмотрения примеров можно сформулировать следующие выводы.

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

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

Процесс экстраполяции должен контролироваться критерием, выполнение которого позволяет в некотором смысле гарантировать справедливость результатов.

3. МЕТОДЫ ЭКСТРАПОЛЯЦИИ И ОЦЕНКИ ПОГРЕШНОСТИ ВЫЧИСЛЕНИЙ ПРИ НЕИЗВЕСТНОМ ПОРЯДКЕ АППРОКСИМАЦИИ

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

В случае, когда значение в (2.1) неизвестно, можно использовать следующую модификацию правила Ричардсона. Вычислим три значения , , при трех номерах после-

довательности: п, п^,п^ и составим систему трех уравнений, из которой можно найти

г = г3

гз ~ г-2

г і -г? _ і г-2-г:і

= г3

Ы - г2)2

г\ — 2 г-2 + гз 1

= *2

zz—z2 г2—г\

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

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

3.2. е-алгоритм

-алгоритм состоит в построении треугольной матрицы , в которой первые 2 столбца задаются по правилу

далее

1

— єі- 1,і-2 н----------

Єі^ — і 1,^ — 1

.7 2.........2/.+ 1

.7.....'2.1. + 1.

Тогда числа £зз, е55, ...,£2Я-1,2Я-1, ••• представляют собой значения г, полученные из точного решения системы нелиней-

ных уравнений. Элементы нечетных столбцов содержат решения аналогичных

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

3.3. -алгоритм

-алгоритм [2, 3] заключается в построении -таблицы по следующим правилам:

0І.-1 = О,

0І,О = 2*! * = 1; = 0.

в;

гД?+1 — "i+l,2j—l

0

'і&+2 — $г+1Д?

А ((),:>,) ’

А {6і+1.2і) А

А2 {0І.2І+1) і = 1,..., п , і = 0,..., п/ 3,

где

* а;

А (М = 0г+м - 0,

А2 (0.,,) = А (0г+м) - А (0.,,).

Экстраполированные значения находятся в четных столбцах матрицы. (Для того чтобы получить 1-е экстраполированное значение, необходимо использовать 4 рассчитанных. Для получения дважды экстраполированного нужно 4 экстраполированных один раз и т. д).

3.4. Иллюстрация на численном эксперименте

На рис. 3.1, а приведены результаты применения повторной экстраполяции с помощью 82-алгоритма (3.1) при С} = 2 к последовательности сумм (1.2).

Цифрой 1, как и выше, обозначена зависимость погрешностей результатов, экстраполированных один раз, цифрой 2 — два раза и т.д. Из сравнения рис. 2.2,а и 3.1,а видно, что применение -алгоритма для получения той же точности, что и метод Ромберга, требует использования в 10-100 раз больше слагаемых. Это — следствие незнания показателей и накопления погрешности при экстраполяции.

Рис. 3.1. Результаты экстраполяции с помощью -алгоритма: а — последовательности сумм

Рис. 3.2. Результаты экстраполяции с помощью -алгоритма: а — последовательности сумм

На рис. 3.1, б показаны результаты применения -алгоритма к последовательности

гГ1 = — Юп-0'1 + О.бп-1'1 - 0,0816(6)п-2'1,

т. е. к упрощенной последовательности (2.11). Рисунок показывает, что качество экстраполяции от такого упрощения не улучшается.

Результаты применения -алгоритма для экстраполяции последовательности сумм

(1.2) даны на рис. 3.2, а. Номера прямых

соответствуют столбцам -

матрицы.

Сравнивая рис. 3.2, а с 3.1, а нетрудно обнаружить заметное улучшение точности экстраполяции при применении -алгоритма, особенно, для трех и более раз экстраполированных данных. Это является следствием точного решения системы уравнений (2.8).

Тем не менее, метод Ромберга дает лучшие результаты (рис. 2.2, б), так как использует известные значения показателей £у, и поэтому допускает меньшую ошибку экстраполяции.

Точность решения системы уравнений иллюстрируется на рис. 3.2, б, где показаны результаты применения е-алгоритма к упрощенной последовательности (3.4). Погрешность порядка 10 - , которая остает-

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

-алгоритм применяется для данных, соответствующих последовательному увеличению на единицу (для последовательностей, представимых в виде суммы степенных функций от ). На рис. 3.3, а представлены результаты применения -алгоритма к последовательности (2.11).

Из рис. 3.3, а видно, что в отличие от -алгоритма -алгоритм не решает точно задачу выделения степенных слагаемых последовательности. Применение -алгоритма к последовательности сумм (1.2) позволяет достичь точности порядка 10 -10 при

-20. Дальнейшее уточнение ограничивается погрешностью исходных данных.

О 0.5 1.5 1%п

а

б

Рис. 3.3. Результаты экстраполяции с помощью -алгоритма: а — к последовательности (2.27);

б — к последовательности сумм

4. КРИТЕРИЙ НАДЕЖНОСТИ

Повторная экстраполяция позволяет проверить надежность полученных оценок. Первая экстраполяция позволяет оценить погрешность решения Дь вторая — оценить погрешность экстраполированных значений . Вторая оценка одновременно является оценкой погрешности оценки погрешности численного результата. Их отношение Дд = = Д2/Ді представляет собой оценку относительной размытости оценки А\ [5,6]. Если существенно меньше 1, то оценке можно доверять, в противном случае оценку следует считать ненадежной. Эти условия определяют критерий надежности оценки погрешности. Число экстраполяций можно увеличивать, уточняя результат, если относительная размытость погрешности результата очередной экстраполяции остается малой.

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

(2.3)). Для интегрирования функций с осо-

бенностями (когда порядок аппроксимации заранее определить затруднительно) можно применить -алгоритм.

На рис. 4.1 цифрой 0 обозначена зависимость погрешностей рассчитанных ре-

зультатов, цифрами 1-4 — результаты последовательного применения одной, двух, трех и т. д. экстраполяций.

а

Рис. 4.1. Результаты экстраполяции: а — для

численного дифференцирования; б — для численного интегрирования

Как видно из графиков, использование алгоритмов экстраполяции позволяет увеличить точность на несколько знаков и достичь погрешности порядка 10 -10 для по-

рядка 100. Прямым методом достичь такой точности не удается из-за погрешности округления.

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

Тем самым, полученные оценки можно считать достаточно точными.

5. МОДИФИЦИРОВАННЫЕ МЕТОДЫ ЭКСТРАПОЛЯЦИИ

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

Если известно не менее 3-х вычисленных значений искомого параметра при различных , то задачу можно записать в виде системы равенств типа (6), возмущенных погрешностями

г\ = г + с + и 1, г-2 = г + 012 + и'2:

П\

где Щ = —•

гт = г

*-*1т

Эту задачу будет более удобно решать, если прологарифмировать

1п \zj — г\ = а + к 1пqj + Vj, = 1,.... т.

а = 1п С, V-: И —т-

сдк-

При применении метода наименьших квадратов задача сводится к поиску экстремума

Ф (а, к, г) =

-2 I

= а - 1 [а + к 1п qj — 1п | Zj

^=1

—г> 111111,

где т ^ 3, а/ — оценки погрешностей гу. Эта задача сводится к решению системы нелинейных уравнений

ат т

О ф __9

~0~ = 2 2_^ C!j " [и + к 1п щ — 1п \г^ — г\] = 0.

П з=1

дФ ^

— = 2 2_^ Vj " [и + к 1п щ — 1п \г^ — г\] 1п щ = 0.

3=1

лт т -

О ф __9

—— = 2 > а  ^ \и + к 1п (Ц — 1п |г,- — гП — — = 0.

дг ^ г,- г

^'=1 3

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

к в третье уравнение задача сводится к поиску корня одного нелинейного уравнения относительно . Это уравнение может быть решено численным методом.

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

3 1ВЛГ

б

Рис. 5.1. Оценка погрешности результатов экстраполяции методом наименьших квадратов: а — исходная зависимость; б — результаты экстраполяции

Результаты экстраполяции представлены на рис. 5.1. Из рис. 5.1, а видно, что зависимость логарифма модуля погрешности от плохо аппроксимируется прямой. Вблизи точки погрешность меняет знак,

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

последующими экстраполяциями. В результате наилучший результат имеет погрешность около 1,5-10_14 при размытости 0,2.

Таким образом, повторное применение метода наименьших квадратов при анализе результатов решения задачи позволило уменьшить погрешность примерно на 2 порядка, что было бы невозможно достичь прямыми вычислениями за реальное время и, кроме того, дало возможность оценить размытость оценок и тем самым подтвердить их надежность.

ВЫВОДЫ

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Бахвалов, Н. С. Численные методы /

Н. С. Бахвалов, Н. П. Жидков, Г. М. Ко-

бельков. М.: Наука, 1987. 598 с.

2. Smith, D. A. Acceleration of linear and logarithmic convergence / D. A. Smith, W. F. Ford // SIAM J. Numer. Anal. 1979. V. 16. P. 223-240.

3. Smith, D. A. Numerical comparisons of nonlinear convergence accelerations / D. A. Smith, W. F. Ford // Mathematics of Computation. 1982. V. 38, 158. P. 481-499.

4. Прудников, А. П. Интегралы и ряды / А. П. Прудников, Ю. А. Бычков, О. И. Мари-чев. М. : Наука, 1981. 800 с.

5. Шерыхалина, Н. М. Критерий применимости правила Рунге для оценки погрешности численных результатов / Н. М. Шерыхалина // Принятие решений в условиях неопределенности. Уфа: УГАТУ. 1999. С. 349-356.

6. Житников, В. П. Оценка интервала неопределенности на основе анализа результатов численного эксперимента / В. П. Житников, Н. М. Шерыхалина // Интеллектуальное управление в сложных системах 99: матер. Ре-сп. науч.-техн. конф. Уфа: УГАТУ, 1999. С. 68.

7. Житников, В. П. Линейные некорректные задачи. Верификация численных результатов : учеб. пособие / В. П. Житников, Н. М. Шеры-халина, А. Р. Ураков. Уфа : УГАТУ, 2002. 91 с.

8. Sherykhalina, N. M. Application of extrapolation methods of numerical results for improvement of hydrodynamics problem solution / N. M. Sherykhalina, V. P. Zhitnikov // Computational Fluid Dynamics J. 2002. V. 11, no. 2. P. 155-160.

9. Житников, В. П. Методы верификации математических моделей в условиях неопределенности / В. П. Житников, Н. М. Шерыхалина // Вестник УГАТУ. 2000. № 2. С. 53-60.

ОБ АВТОРЕ

Шерыхалина Наталия Михайловна, доц. каф. компьют. мат. Дипл. инж. (УГАТУ, 1993). Канд. физ.-мат. наук (БГУ, 1996). Иссл. в обл. волновых течений жидкости, уединенных волн, методов оценки погрешности численных результатов.