Содержание к диссертации
Введение
1. Анализ основных методов оценки качества вычислительных алгоритмов 8
2. Концепция многомерного пространства качества вычислительного алгоритма 17
2.1. Построение структуры пространства качества вычислительного алгоритма 17
2.2. Методы вычисления базовых показателей качества алгоритмов решения интегральных уравнений Фредгольма II рода 20
2.2.1. Методика оценки сложности алгоритма решения интегральных уравнений Фредгольма II рода 21
2.2.2. Методика оценки скорости сходимости решения интегрального уравнения Фредгольма II рода 22
2.2.3. Методика оценки устойчивости алгоритма решения интегральных уравнений Фредгольма II рода 25
2.3. Методы вычисления дополнительных показателей качества алгоритмов решения интегральных уравнений Фредгольма II рода 28
2.3.1. Методика оценки погрешности алгоритма решения интегральных уравнений Фредгольма II рода 29
2.3.2. Методика оценки эффективного порядка точности алгоритма решения интегральных уравнений Фредгольма II рода 30
2.3.3. Методика оценки времени выполнения алгоритма решения интегральных уравнений Фредгольма II рода 31
2.4. Алгоритм комплексной оценки эффективности алгоритма решения интегральных уравнений Фредгольма II рода 33
Краткие выводы ..35
3. Программный комплекс оценки эффективности алгоритмов решения интегральных уравнений Фредгольма Ирода 37
3.1. Структурные особенности программного комплекса 37
3.2. Конструктор формализованных описаний интегральных уравнений Фредгольма II рода 42
3.3. Конструктор описаний алгоритмов решения интегральных уравнений Фредгольма II рода 44
3.4. Подсистема оценки качества алгоритма решения интегральных уравнений Фредгольма II рода 48
3.4.1. Модуль построения поверхности сложности алгоритма решения интегральных уравнений Фредгольма II рода 48
3.4.2. Модуль построения информационного графа алгоритма решения интегральных уравнений Фредгольма II рода 54
3.5. Подсистема оценки эффективности алгоритма решения интегральных уравнений Фредгольма II рода 62
3.5.1. Модуль оценки скорости сходимости алгоритма решения интегральных уравнений Фредгольма П рода 62
3.5.2. Модуль оценки требуемого объема памяти и времени выполнения алгоритма решения интегральных уравнений Фредгольма II рода 66
3.5.3. Модуль оценки погрешности и эффективного порядка точности алгоритма решения интегральных уравнений Фредгольма II рода 68
3.5.4. Модуль построения вектора устойчивости алгоритма решения интегральных уравнений Фредгольма II рода 70
3.6. Подсистема визуализации результатов оценки эффективности алгоритмов решения интегральных уравнений Фредгольма II рода 73
Краткие выводы 80
4. Экспериментальные, исследования разработанного алгоритмического и программного обеспечения 82
4.1. Обоснование выбора исследуемых интегральных уравнений и алгоритмов 82
4.2. Анализ оценки числа итераций решения интегральных уравнений... 86
4.3. Анализ необходимых ресурсов машинного времени и памяти для решения интегральных уравнений 89
4.4. Анализ сложности алгоритмов решения интегральных уравнений... 92
4.5. Анализ погрешности и эффективного порядка точности алгоритмов решения интегральных уравнений 93
4.6. Анализ устойчивости алгоритмов решения интегральных уравнений 98
Краткие выводы 101
Основные выводы 102
Список литературы
- Методы вычисления базовых показателей качества алгоритмов решения интегральных уравнений Фредгольма II рода
- Методы вычисления дополнительных показателей качества алгоритмов решения интегральных уравнений Фредгольма II рода
- Подсистема оценки качества алгоритма решения интегральных уравнений Фредгольма II рода
- Анализ необходимых ресурсов машинного времени и памяти для решения интегральных уравнений
Введение к работе
Развитие численных методов решения математических задач обусловило появление разнообразных алгоритмов и их модификаций, используемых при разработке программно-алгоритмических комплексов математического моделирования систем. При этом особую актуальность приобрела задача выбора одного из нескольких алгоритмов, конкурирующих на применение к решению одной и той же задачи. Правильность выбора алгоритма позволяет существенно сократить время разработіш программного обеспечения [146], что особенно важно в условиях ограниченности используемых ресурсов.
Одним из универсальных инструментов математического моделирования является аппарат интегральных уравнений, который применяется для численного моделирования разнообразных процессов в инженерно-технических областях знаний, а также физике, биологии и экономике. Универсальность интегральных уравнений Фредгольма II рода обусловила появление большого числа алгоритмов их решения. Поэтому при разработке программно-алгоритмических комплексов численного моделирования систем с использованием интегральных операторов фредгольмовского типа особую актуальность приобретает задача выбора наиболее эффективного алгоритма. Недостаток практических рекомендаций по выбору алгоритмов решения интегральных уравнений приводит к тому, что часто тривиальность программной реализации алгоритма, а не его эффективность, становится основным критерием выбора алгоритмического обеспечения. При этом «плохой выбор алгоритма становится очевидным только после его апробирования, ... и тогда весь процесс разработки программного обеспечения придется повторять сначала» [16].
Традиционно для решения описанной проблемы применяются системы выбора рациональных алгоритмов [174, 183, 186 - 188], построенные на основе различных критериев эффективности алгоритма. Но, как правило, такие системы применимы для алгоритмов решения обыкновенных дифференциальных уравнений и уравнений . в частных производных. Для анализа алгоритмов решения интегральных уравнений большинство известных методик [6, 12, 24, 25, 69, 166, 178] предлагают использовать апостериорные оценки, то есть исследовать эффективность алгоритма после его программной реализации, что, естественно, увеличивает время разработки программного обеспечения.
Таким образом, известные методы анализа структур алгоритмов не позволяют сделать обоснованный выбор варианта алгоритма решения интегральных уравнений. Поэтому решение задачи разработки и реализации метода априорного анализа эффективности алгоритмов решения интегральных уравнений приобретает существенное теоретическое и практическое значение. При этом базовой задачей является построение количественного критерия для сравнения алгоритмов. В результате проведенного в диссертации анализа показана целесообразность использования для решения данной задачи метода комплексной оценки качества и эффективности вычислительных алгоритмов [18, 40, 42, 45, 97, 126], который позволяет получить априорную количественную оценку эффективности алгоритма. Но реализация данного метода весьма проблематична из-за отсутствия практических рекомендаций по вычислению значений показателей качества для некоторых классов алгоритмов, а именно, для алгоритмов решения интегральных уравнений Фредгольма II рода. Поэтому для практического применения метода комплексной оценки эффективности вычислительных алгоритмов необходимо модифицировать математическое обеспечение метода и разработать его алгоритмическое и программное обеспечение.
Таким образом, разработка математического, алгоритмического и программного обеспечения для комплексной оценки эффективности алгоритмов решения интегральных уравнений Фредгольма II рода, являющаяся целью настоящей работы, обусловлена необходимостью получения комплексных и единичных оценок качества алгоритма до этапа его программной реализации, что имеет важное практическое значение для повышения эффективности программно-алгоритмических комплексов численного моделирования с использованием интегральных операторов фредгольмовского типа.
Методы вычисления базовых показателей качества алгоритмов решения интегральных уравнений Фредгольма II рода
Рассмотрим базовые показатели качества вычислительных алгоритмов. Как видно из анализа литературных источников, для алгоритмов решения интегральных уравнений Фредгольма II рода наиболее практически востребованными показателями качества являются [24, 45, 56, 179] сложность алгоритма [7, 12, 13, 24, 47, 178, 179]; скорость сходимости алгоритма [12, 13, 21, 24, 25, 43, 44, 49, 56, 69, 88,91,109,110,112,124]; устойчивость алгоритма к ошибкам исходных данных [12, 24, 25, 39,50,51,69,85,88,109,110,130,141].
Сложность алгоритма оценивается по максимальному числу обращений к базовой операции. Базовой (или основной) операцией называют операцию, определяющую все остальные операции алгоритма [80]. При анализе алгоритмов решения интегральных уравнений Фредгольма II рода в качестве базовой операции, в соответствии с положениями [39, 54, 82, 90, 150, 152], рассматривается следующая совокупность базовых операций вычисление определенного интеграла; вычисление прямых или обратных тригонометрических функций; вычисление экспоненциальных функций; вычисление логарифмических функций; вычисление элементарных математических функций; обращение к функции, определенной на одном из шагов алгоритма.
Для оценки сложности алгоритма определяется сложность каждого его блока, при этом анализируют арифметическое выражение, вычисляемое на каждом шаге алгоритма, и определяют число обращений к базовой операции. Для оценки сложности циклических структур значение показателя сложности каждого блока, входящего в тело цикла, умножается на число повторений цикла, которое определяется на основании исходных данных исследуемого алгоритма — ядра, правой части и параметров интегрального уравнения Фредгольма II рода.
При оценке сложности условного оператора применяется вероятностная методика, описанная в [136, 148, 149, 171, 182], в соответствии с которой значение показателя сложности каждой ветви условного оператора и умножается на вероятность ее выбора. В [148, 149] для оценки вероятности выбора определенной ветви условного оператора используется следующий метод. В пространстве исходных данных выделяют области, при попадании в которые активизируется заданная ветвь условного оператора. Затем вычисляется вероятность попадания в эти области; вероятность выбора соответствующей ветви условного оператора полагается равной вычисленной.
Описанные преобразования позволяют заменить исходный алгоритм ациклическим, обладающим такими же характеристиками: сложностью, точностью и устойчивостью [149]. Сложность построенного ациклического алгоритма вычисляется как сумма значений показателей сложности отдельных его блоков.
Скорость сходимости алгоритма оценивается по количеству итераций, нужных для получения решения интегрального уравнения Фредгольма II рода с заданной степенью точности [20, 24, 32, 41, 44, 49, 69, 77, 121, 133, 148, 149, 159, 180, 186]. Для того чтобы оценить число итераций воспользуемся принципом сжимающих отображений [105, 154]. При этом в качестве сжимающего оператора будем рассматривать тело итерационного цикла, в результате выполнения которого строится очередное приближение к решению интегрального уравнения. В [24, 25, 56, 105, 154] показано, что если итерационный алгоритм решения интегральных уравнений позволяет построить сходящуюся последовательность приближений, то соответствующий оператор будет сжимающим.
Рассмотрим приведенную в [105, 154] оценку скорости сходимости процесса последовательных приближений Я" (2.7) Уп У l-q ЩУо)-У0\ где Ф(у) - сжимающий оператор с коэффициентом сжатия q\ у - решение уравнения; у0 - нулевое приближение; уп - приближение, полученное на и-й итерации, причем уп = Ф(уп_1); п - число выполненных итераций. Так как требуется построить решение интегрального уравнения с заданной степенью точности є, то
Методы вычисления дополнительных показателей качества алгоритмов решения интегральных уравнений Фредгольма II рода
Рассмотрим методы вычисления дополнительных показателей качества вычислительного алгоритма. Для алгоритмов решения интегральных уравнений Фредгольма II рода дополнительными показателями качества являются [12, 24, 69, 75, 133, 179] погрешность полученного решения [12, 69, 75, 133]; эффективный порядок точности алгоритма [12, 68, 69, 75, 133]; время выполнения алгоритма и требуемый объем памяти [3, 7, 15, 31,54,82,183,184,189].
Рассмотрим методику оценки погрешности алгоритма решения интегральных уравнений Фредгольма II рода. Погрешность решения интегрального уравнения [12, 15, 24, 32, 46, 57, 68, 69, 75, 94, 133, 136, 137, 149, 150, 152, 180, 182, 184, 186] характеризует близость результатов вычислений теоретически верным значениям. С помощью исследуемого алгоритма построим решение заданного уравнения на двух равномерных сетках /г, и h2=khly k l. Полученные решения обозначим ух(х) и у2(х).
Тогда погрешность решения заданного интегрального уравнения с помощью исследуемого алгоритма будет определяться как [12, 69, 75, 94,133] Ау(х) \\у2(х)-У](х)\\, (2.24) причем для вычисления погрешности будем использовать ту же норму, что и в исследуемом алгоритме.
При построении оценки погрешности заменим решения интегрального уравнения УІ(Х) и у2(х) приближениями, полученными после выполнения
М первых итераций алгоритма. В [5, 12, 69, 75, 133, 161] показано, что погрешность итерационного алгоритма не убывает в процессе вычислений. Причем для алгоритмов решения интегральных уравнений Фредгольма II рода накопление погрешности носит следующий характер [24, 25, 46] (рис. 2.2). Следовательно, заменяя в выражении (2.24) решение уравнения приближением, построенным после М итераций, получим нижнюю границу диапазона значений погрешности решения интегрального уравнения Фредгольма II рода Ау(х) Аум (х) = \\у? (х) - у? {х)\. (2.25)
Экспериментально доказано (см. раздел 4.5), что оценка погрешности решения, построенного с помощью сходящегося алгоритма, не зависит от коэффициента к, а особенностями решаемого уравнения и методом интегрирования, используемым в алгоритме. При этом увеличение значения параметра М приводит к повышению точности получаемой оценки.
Методика оценки эффективного порядка точности алгоритма решении интегральных уравнений Фредгольма IIрода
Рассмотрим методику оценки эффективного порядка точности алгоритма, построенную на основе процесса Эйткена [12, 69, 75, 133]. Для определения эффективного порядка точности алгоритма рассмотрим три равномерных сетки с шагами fy, h2 и Іц, причем к2 = Щ, hi=kh2=k2hl, к 1. На каждой сетке с помощью исследуемого алгоритма построим решение заданного интегрального уравнения Фредгольма II рода. Обозначим эти решения соответственно ух{х), у2(х), уг(х). Повторяя вывод, приведенный в [75], получим формулу для вычисления эффективного порядка точности алгоритма решения интегральных уравнении Фредгольма II рода \\УЛХ)-У2(Х)\\ In р= Ь - Я, (2.26) Ink где р - эффективный порядок точности алгоритма, к - коэффициент изменения шага сетки, ух{х), у2(х), у3(х) решения интегрального уравнения, полученные на трех различных сетках. Заметим, при вычислении эффективного порядка точности используется та же норма, что и анализируемом алгоритме.
При построении априорной оценки эффективного порядка точности алгоритма вместо решения интегрального уравнения в формуле (2.26) будем использовать результаты, полученные после выполнения нескольких первых итераций алгоритма. Экспериментально доказано (см. раздел 4.5), что оценка эффективного порядка точности сходящегося алгоритма не зависит от коэффициента к и количества выполненных итераций, а определяется только особенностями решаемого уравнения и методом интегрирования, используемым в алгоритме.
Подсистема оценки качества алгоритма решения интегральных уравнений Фредгольма II рода
Сложность алгоритма является одной из основных теоретических характеристик его качества [7, 32, 38, 82]. Априорная оценка сложности позволяет оценить потенциальные затраты времени и памяти при решении интегральных уравнений до этапа программной реализации алгоритма его решения.
Для оценки сложности алгоритма решения интегральных уравнений Фредгольма II рода используется методика, построенная в разделе 2.3.1. Для каждой базовой операции сложность алгоритма описывается функцией (и +1 )-го аргумента, где п - количество циклов в исследуемом алгоритме, а единица обозначает еще один аргумент функции, а именно - количество узлов сетки изменения аргументов. Процесс построения функции сложности алгоритма состоит из нескольких этапов, на каждом из которых заполняются следующие поля специальной структуры данных - таблицы сложности: номер блока алгоритма; число обращений к базовой операции в блоке алгоритма; уровень вложенности блока; совокупность циклов, содержащих данный блок.
На первом этапе для каждого блока алгоритма определяется совокупность циклов, в которые он входит. Все циклы исследуемого алгоритма последовательно пронумерованы, и каждому из них поставлена в соответствие переменная, значение которой равно числу повторений тела цикла. В результате число повторений і -го цикла обозначается переменной щ, которая идентифицирует этот цикл. Вычисления значений полей таблицы сложности выполняются по следующему алгоритму. 1. Определить N- число шагов анализируемого алгоритма. 2. Создать таблицу сложности, содержащую 7V строк. 3. Цикл по і от 1 до TV. 3.1.Очистить все поля z -й строки таблицы сложности. 3.2.В поле «Номер блока алгоритма» г -й строки таблицы сложности записать значение переменной г. 4. Конец цикла по і. 5. УровенъВложенности = 0. 6. Цикл по / от 1 до TV. 6.1.Если z -й блок алгоритма является началом цикла, то перейти к шагу 6.2, иначе перейти к шагу 6.3. 6.2. УровенъВложенности = УроееньВлооїсенности +1, 6.3.В поле «Уровень вложенности блока» г-й строки таблицы сложности записать значение переменной УровенъВложенности. 6.4.Если і -й блок алгоритма является концом цикла, то перейти к шагу 6.5, иначе перейти к шагу 7. 6.5. УровенъВложенности — УровенъВложенности -1. 7. Конец цикла по і. 8. ИдентификаторЦикла = 0. 9. Цикл по і от 1 до N. 9.1.Если і -й блок алгоритма является началом цикла, то перейти к шагу 9.2, иначе перейти к шагу 10. 9.2. ИдентификаторЦикла = ИдентификаторЦикла +1. 9.3.В переменную Уровень записать значение столбца «Уровень вложенности блока» і -й строки таблицы сложности. 9.4.7 = г. 9.5.7 столбец «Совокупность циклов» /-й строки таблицы сложности дописать ИдентификаторЦикла. 9.6.Если /-й блок алгоритма является концом цикла и значение столбца «Уровень вложенности блока» j -й строки таблицы сложности равно значению переменной Уровень, то перейти к шагу 10, иначе перейти к шагу 9.7. 9.7.у = ./ + 1. 9.8.Если значение, записанное в столбце «Уровень вложенности блока» 7-й строки таблицы сложности, меньше значения переменной Уровень, то прейти к шагу 10, иначе перейти к шагу 9.5. 10. Конец цикла по і . 11. Конец алгоритма 3.1. Блок-схема построенного алгоритма приведена в приложении 6.
В результате работы алгоритма 3.1 создается таблица сложности исследуемого алгоритма, в которой заполнены все поля, кроме поля «Число обращений к базовой операции».
На втором этапе вычисляются оценки значений сложности каждого блока алгоритма. При этом анализируют арифметическое выражение, вычисляемое на каждом шаге алгоритма, и определяют число обращений к базовой операции. Полученное значение умножается на коэффициент, который зависит от типа левой части выражения (см. табл. 2)
Анализ необходимых ресурсов машинного времени и памяти для решения интегральных уравнений
Задача данной серии экспериментов - исследовать зависимость оценок требуемого объема памяти и времени выполнения алгоритма решения интегральных уравнений от количества узлов сетки. Для каждого рассматриваемого уравнения с помощью разработанного специального конструктора [48] построим несколько формализованных описаний, отличающихся друг от друга числом узлов в сетке. Затем оценим требуемый объем памяти и время выполнения алгоритмов, используя в качестве исходных данных алгоритмов построенные формализованные описания интегральных уравнений. В разделе 3.5.2 показано, что одним из параметров алгоритма оценки времени выполнения является число итераций, выполняемых алгоритмом при решении интегрального уравнения. Значения этого параметра возьмем из результатов первой серии экспериментов (раздел 4.2). Так как вид исследуемых зависимостей практически не зависит от типа решаемого уравнения, то на рис. 4.3 и 4.4 представим результаты только для одного уравнения, а именно для уравнения (4.1).
Рассмотрим полученные зависимости. Характер зависимости требуемого объема памяти от числа узлов сетки обусловлен обработкой функций двух переменных, которую выполняют все исследуемые алгоритмы. При этом требования к необходимым ресурсам памяти для алгоритма метода Положего более высокие, чем для алгоритма метода простой итерации, так как для вычислений по методу Положего требуется обрабатывать три функции двух переменных, а для вычислений по методу простой итерации или методу осреднения функциональных поправок -одну.
Характер зависимости времени выполнения алгоритма от числа узлов сетки обусловлен функцией сложности рассматриваемых алгоритмов решения интегральных уравнений (см. раздел 4.4). Так как алгоритму метода Положего для получения результата с заданной степенью точности требуется наибольшее число итераций, то время его выполнения является максимальным. Другая ситуация возникает при сравнении алгоритмов метода осреднения функциональных поправок и метода простой итерации. Число итераций, выполняемых алгоритмом метода осреднения функциональных поправок, на 40% меньше, чем число итераций, выполняемых алгоритмом метода простой итерации, но при этом оценка времени вычислений для первого алгоритма на 22% больше, чем для второго. Такие результаты объясняются при анализе сложности алгоритмов решения интегральных уравнений. В качестве базовой операции возьмем операцию вычисления определенного интеграла. На одной итерации алгоритма метода простой итерации определенный интеграл вычисляется т раз (т - число узлов сетки), а на одной итерации алгоритма метода осреднения функциональных поправок - (2т+ 1) раз (см. раздел 4.4). Следовательно, более высокая скорость сходимости алгоритма метода осреднения функциональных поправок (по сравнению с алгоритмом методом простой итерации) не определяет уменьшение времени вычислений.
Сравним значения показателей сложности выбранных алгоритмов решения интегральных уравнений Фредгольма II рода. С помощью разработанного программного комплекса построим функции сложности каждого алгоритма, рассматривая в качестве базовых операции, определенные в разделе 2.2.1. Полученные результаты представим на рис. 4.5 и в виде таблицы 5, обозначив т - число узлов сетки, п - число итераций, выполняемых алгоритмом решения интегральных уравнений.
Рассмотрим вычисленные оценки сложности. Из данных, приведенных в таблице 5, следует, что, по сравнению с другими алгоритмами, алгоритм метода Положего обладает максимальной сложностью, обуславливающей большее время его выполнения. Функции сложности алгоритмов метода осреднения функциональных поправок и метода простой итерации имеют одинаковый характер, но сложность алгоритма метода осреднения функциональных поправок вдвое больше, чем сложность алгоритма метода простой итерации. Следовательно, для того чтобы время вычислений по алгоритму метода осреднения функциональных поправок было меньше, чем время вычислений по алгоритму метода простой итерации, скорость сходимости первого алгоритма должна быть в два раза больше, чем скорость сходимости второго алгоритма.
Таким образом, полученные результаты полностью согласуются с оценками времени выполнения алгоритма, рассмотренными в разделе 4.3, что подтверждает работоспособность построенного алгоритма оценки сложности.
Оценки погрешности и эффективного порядка точности алгоритма решения интегральных уравнений, получаемые по алгоритму, разработанному в разделе 3.5.3, зависят от двух параметров: коэффициента к 1, используемого для построения сеток с меньшим шагом, и параметра S, определяющего количество итераций, выполняемых для получения оценки. Исследуем влияние этих параметров на оценки значений показателей эффективности.
Задача первой серии экспериментов - определить зависимость получаемых оценок от величины коэффициента к. Вычислим оценки эффективного порядка точности и погрешности для каждого рассматриваемого интегрального уравнения и алгоритма его решения, последовательно полагая коэффициент к равным х/2, X, X и Уь- Так как вид исследуемой зависимости одинаков для всех выбранных интегральных уравнений и алгоритмов их решения, то в таблице 6 приведем часть полученных результатов, а именно, оценки значений показателей эффективности, вычисленные для уравнения (4.11) и алгоритма метода простой итерации.
