7. Порядок решения задачи на эвм

1. По указанию преподавателя выбрать метод экстраполяции (правило Рунге (2.6), метод Ромберга (2.11) или таблицу Нэвилла (2.12).

2. Составить подпрограмму, реализующую данный метод.

3. Предусмотреть в программе многократную экстраполяцию.

4. Оценить размытость оценки погрешности согласно п. 5.

5. Отладить программу путем экстраполяции частичных сумм (см. раздел 6 «Численный эксперимент»).

6. Применить программу для экстраполяции последовательности, заданной преподавателем. Результат оценки погрешности представить в виде графика (рис. 2.2) и в виде таблицы 2.1.

8. Требования к отчету по лабораторной работе

Отчет по лабораторной работе должен содержать:

1. файл исходного текста программы;

2. файлы результатов для тестового примера и для экстраполяции заданной последовательности;

3. описание алгоритма расчета (в текстовой форме и в виде блок-схемы) в электронном и распечатанном виде;

4. распечатку файлов п. 2) с комментариями;

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

9. Вопросы для самопроверки

1. Математические модели погрешности.

2. Область применения разных методов экстраполяции.

3. Оценка эффективности разных способов экстраполяции.

4. Влияние погрешности округления на результат экстраполяции.

5. Основное условие, ограничивающее применение методов экстраполяции типа Ромберга, основанных на применении интерполяционных формул.

Лабораторная работа №3 экстраполяция при неизвестном порядке аппроксимации

1. Цель работы

Продолжение ознакомления с методами экстраполяции.

2. Задачи работы

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

3. Вводная часть

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

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

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

4. Теоретические основы

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

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

(3.1)

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

,

,

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

. (3.2)

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

. (3.3)

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

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

.

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

Ошибка экстраполяции. Оценим ошибку экстраполяции, возникающую при применении этого метода. Предположим, что z_i представляется в виде (2.18). Применим формулы (3.2) и (3.3), подставив в них разложение (2.18)

. (3.4)

Аналогично (2.20) получим оценку

.

Отсюда следует, что, в отличие от метода Ромберга, применение ² – алгоритма приводит к дополнительной погрешности экстраполяции, имеющей порядок, отличный от k₂. Это может мало сказаться на результатах первой и второй экстраполяции. Однако при третьей экстраполяции будет оцениваться не следующий член разложения , а погрешность первой экстраполяции (предполагается, что k₃>2k₃-k₁).

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

Следует также отметить, что метод Ромберга не требует монотонного убывания коэффициентов разложения c_i, так как погрешность (2.22) не зависит от соотношения коэффициентов. Погрешность (3.4) ² – алгоритма зависит от отношения c₂/c₁ и если это отношение достаточно велико, результат экстраполяции трудно предсказуем.

Иллюстрация на численном эксперименте. На рис. 3.1а приведены результаты применения повторной экстраполяции с помощью ² - алгоритма (3.3) при Q=2 к последовательности сумм (2.2).

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

а)

б)

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

а) – последовательности сумм (2.2); б) – упрощенной последовательности (3.5).

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

, (3.5)

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

4.2. -алгоритм

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

,

далее

. (3.6)

Тогда числа представляют собой значения z, полученные из точного решения системы 2j+1 нелинейных уравнений типа (2.14), в которой неизвестными являются и коэффициенты d_i и числа . Элементы нечетных столбцов содержат решения аналогичных систем, в которых используются значения z_l для l=i-2j,…,i.

Результаты применения -алгоритма для экстраполяции последовательности сумм (2.2) даны на рис. 3.2а. Номера прямых j=0, 1,… соответствуют 2j+1 столбцам -матрицы.

а)

б)

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

а) – последовательности сумм (2.2); б) – упрощенной последовательности (3.5).

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

Точность решения системы уравнений иллюстрируется на рис. 3.2б, где показаны результаты применения -алгоритма к упрощенной последовательности (3.5). Погрешность порядка 10^1310^14, которая остается после применения трехкратной экстраполяции, обусловлена только ошибками округления. Эти ошибки имеют большее значение, чем при применении метода Ромберга, так как для получения экстраполированных значений с помощью -алгоритма приходится использовать разности более высокого порядка.

4.3. -алгоритм

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

,

,

, (3.7)

где

, .

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

-алгоритм применяется для данных, соответствующих последовательному увеличению n на единицу (для последовательностей, представимых в виде суммы степенных функций от n). На рис. 3.3а представлены результаты применения -алгоритма к последовательности (2.26). Видно, что в отличие от -алгоритма -алгоритм не решает точно задачу выделения степенных слагаемых последовательности. Применение -алгоритма к последовательности сумм (2.2) позволяет достичь точности порядка 10^-5-10^-6 при n=10-20. Дальнейшее уточнение ограничивается погрешностью округления.

а)

б)

Рис. 3.3. Результаты экстраполяции с помощью -алгоритма:

а) – к последовательности (2.26); б) – к последовательности сумм (2.2).

4.4. u-алгоритм

u-алгоритм предполагает для ускорения сходимости последовательности z_i , (i=1,…,n) использовать формулу

, где . (3.8)

Здесь может k изменяется от 2 до n-1, номер экстраполяции равен k-1. Экстраполированные значения получаются путем применения формулы (3.8) к последовательности z_i начиная с номера 1, 2,…

Как и -алгоритм u-алгоритм применяется для данных, соответствующих последовательному увеличению n на единицу или на константу. На рис. 3.4 представлены результаты применения u-алгоритма к последовательностям (2.26) и (2.2). Особенностью данного алгоритма является то, что если начинать экстраполяцию не с первого номера, а со второго или большего, то результаты экстраполяции могут ухудшаться.

При использовании подпоследовательности z_kh, при h=10, 1000 результаты экстраполяции практически не меняются (рис. 3.5а,б). Таким же свойством обладает и -алгоритм.

а)

б)

Рис. 3.4. Результаты экстраполяции с помощью u-алгоритма:

а) – последовательности (2.26); б) – последовательности сумм (2.2).

а)

б)

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

а) – на 10; б) – на 1000.

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

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

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

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