Лабораторная работа №2
Влияние погрешности вычислений Параллельные методы численного интегрирования.
Цель работы.
Изучение и реализация методов численного интегрирования. Реализация методов численного интегрирования на многопроцессорных архитектурах. Исследование накопления погрешности.
Теоретическая часть.
Сфера приложений приближенных формул при моделировании самых разных природных процессов развивается очень бурно. Объектами приближения служат при этом как решения краевых задач для уравнений и систем уравнений с частными производными, так и обобщенные функции, когда речь идет о кубатурных формулах. В любом случае использование приближенных формул связано с обширными компьютерными вычислениями, в частности операции суммирования. И в этой связи важно знать, в какой степени гарантирована точность численного результата к точному теоретическому. Для суммирования большого числа элементов помимо тривиального суммирования разработан ряд алгоритмов, в том числе с оценкой гарантированной точности результата. Особенно перспективным является алгоритм Кохана. В дальнейшем алгоритм Кохана может быть расширен на вычисление определителя с введенным понятием точного произведения. В любом случае операция суммирования вещественных чисел является базовой для любых вычислительных методов. Основная проблема вещественных чисел – возможность представления необходимого количества знаков мантиссы. Для исследования влияния погрешности вычислений на сходимость численных методов используем задачу численного интегрирования.
Задача численного интегрирования состоит в нахождении приближенного значения интеграла  . Введём на отрезке  расчётную сетку  . Точки  называют узлами сетки, отрезки  – частичными отрезками,  – шагами сетки. В этом случае от непрерывной функции  необходимо перейти к её дискретным значениям  . В качестве приближенного значения интеграла на некоторой расчётной сетке  может выступать выражение, аппроксимирующее точное значение с помощью кусочно-постоянных функций (метод трапеций):
 .
Основной операцией в нахождении численного значения определённого интеграла является операция суммирования.
На рисунке 1 изображена зависимость относительной погрешности численного интегрирования от количества интервалов разбиения при разном количестве значащих знаков мантиссы. Для задачи численного интегрирования полиномиальной функции пятого порядка график сходимости к точному значению при использовании различных типов данных изображен на рисунке 1. Можно сделать вывод, что максимальная точность численного интегрирования ограничена количеством значащих разрядов используемого типа данных.
Рисунок 1. Зависимость погрешности вычисления интеграла методом трапеции от количества интервалов разбиения для различных типов данных языка Fortran.
Основная задача алгоритма суммирования Кохана – уменьшение ошибки численного суммирования последовательности конечной точности с плавающей запятой по сравнению с естественным подходом. В основе алгоритма суммирования Кохана лежит частичная компенсация накапливаемой ошибки суммирования путём введения отдельной переменной, которая хранит малые ошибки по сравнению со всей суммой. Приведём алгоритм суммирования Кохана:
Input: a[1..N]
sum = input[1]
c = 0.0
for i = 2, 3,..., N do
y = input[i] - c
t = sum + y
c = (t - sum)- y
sum = t
end for
Output: sum, c
Практическая часть.
Реализовать заданный метод численного интегрирования для однопроцессорной архитектуры с использованием классического способа суммирования и алгоритма Кохана,
Провести исследования поведения относительной погрешности численного интегрирования при различных типах данных (float, double, long double для языков С/С++; real*4, real*8, real*16 для языка Фортран) для различных способов суммирования,
Реализовать заданный метод численного интегрирования для многопроцессорной архитектуры с использованием классического способа суммирования и алгоритма Кохана,
Оценить арифметическую сложность последовательной и параллельной реализаций метода,
Посчитать теоретическое и практическое ускорение параллельной программы,
Варианты заданий.
Метод прямоугольников,
Метод трапеций,
Метод Симпсона,
Метод Гаусса-4,
Метод Монте-Карло.
|
