Содержание к диссертации
Введение
ГЛАВА I. Функциональное наполнение пакета прикладных программ сознам 23
1.1 Назначение пакета 23
1.2 Численные алгоритмы решения алгебраической проблемы собственных значений 24
1.3 Алгоритм апостериорной оценки и уточнения приближенного решения задачи на собственные значения 35
1.4 Структура и состав пакета сознам 49
1.5 Алгоритм вычисления точного скалярного произведения на ЭВМ с плавающей запятой 54
ГЛАВА 2. Спецификация программного обеспечения пакета сознам 61
2.1 Назначение языка спецификаций 61
2.2 Язык спецификаций программных модулей 62
2.3 Спецификация программных модулей базового уровня пакета СОЗНАМ 66
ГЛАВА 3. Организация интерфейса пользователей с пакетом сознам 83
3.1 Общение пользователей с ШШ на базовом уровне 83
3.2 Общение пользователей с ШШ на втором уровне 86
3.3 Работа пользователей с ШШ в диалоговом режиме 87
3.4 Организация диалога 89
3.5 Пример диалога 93
Заключение 112
Литература
- Алгоритм апостериорной оценки и уточнения приближенного решения задачи на собственные значения
- Структура и состав пакета сознам
- Язык спецификаций программных модулей
- Общение пользователей с ШШ на втором уровне
Введение к работе
Целью данной работы является разработка пакета прикладных программ, позволяющего решать с гарантированной точностью алгебраическую проблему собственных значений для различных классов матриц, а именно: а) полную и частичную проблему собственных значений для комплексных (общего вида и Эрмитовых) и действительных матриц (общего вида, симметричных плотных, симметричных ленточных, сим метричных трехдиагональных и несимметричных трехдиагональных); б) обобщенную проблему собственных значений для действитель ных симметричных и несимметричных матриц.
Входные данные задачи и результаты промежуточных вычислений в процессе решения должны располагаться в оперативной памяти ЭВМ. Пакетом прикладных программ (ШШ) будем называть комплекс: взаимосвязанных прикладных программ, предназначенных для решения некоторого класса задач (функциональное наполнение); программных и языковых средств для управления расчетами и взаимодействия с пользователями в процессе работы (системное наполнение); информационного файла данных, используемого при выполнении расчетов,и документации (информационное наполнение).
Функциональное наполнение ШШ определяет его прикладные возможности и должно обеспечивать возможность решения любой задачи из рассматриваемого класса. В этом смысле можно говорить о функциональной полноте ШШ.
Функциональное наполнение пакета обычно организуется в виде проблемно-ориентированной библиотеки программных модулей (библиотеки пакета).
Системное наполнение пакета составляют специализированные средства, обеспечивающие управление вычислительным процессом, т.е. организацию выполнения последовательностей модулей библиотеки пакета, обмен информационными массивами между отдельными модулями, формирование библиотеки пакета, хранение и редактирование данных и т.п. [ I ]. Часть программных средств системного наполнения предназначена для поддержки языков общения пользователей с пакетом.
Информационное наполнение пакета,являющееся его неотъемлемой частью, состоит из следующих компонент: информационный файл тех данных, которые обрабатываются модулями библиотеки пакета. Этот файл содержит переменные и константы из соответствующей прикладной области (базу данных пакета); спецификации (формальное описание) модулей библиотеки пакета; исходные тексты модулей функционального и системного наполнения ІШП; сопровождающая документация пакета (руководства для пользователей и для лиц, сопровождающих пакет); система тестов для отдельных модулей функционального и системного наполнения, а также для ШШ в целом.
Такое понимание ШШ можно считать общепринятым [і - 5] .
Модули функционального наполнения пакета должны удовлетворять требованиям точности, эффективности и детерминированности.
Для пакетов прикладных программ, ориентированных на решение задач численного анализа, требование точности является основным: пользователь должен иметь гарантию, что решение поставленной им задачи вычислено с заданным в обращении числом верных знаков; в противном случае необходимо иметь информацию о достигнутой точности для принятия решения о ценности полученных результатов.
Функциональное наполнение пакета должны составлять программные модули, реализующие численно устойчивые методы решения задач в прикладной области пакета. Более того, эти методы должны быть реализованы таким образом, чтобы влияние ошибок округления в процессе вычислений было минимальным. Например, почти во всех программных модулях, реализующих алгоритмы линейной алгебры, содержится операция вычисления скалярного произведения. Использование стандартного алгоритма может привести к значительному накоплению ошибок округления [7,8] , что существенно снижает точность результата, делая его в ряде случаев неприемлемым. Поэтому для обеспечения точности вычислений требуются специальные алгоритмы ( например, см. раздел 1.5 главы I).
Эффективность решения поставленной задачи складывается из эффективности выбранных численных методов и алгоритмов и эффективности их программной реализации [ 6 ] . Программная реализация модуля может считаться эффективной, если для его выполнения на конкретной машине используется минимум ресурсов ( в том числе и время центрального процессора). Для обеспечения эффективности отдельные модули библиотеки пакета могут быть реализованы на языке ассемблера. Поэтому пакет может иметь машинно- зависимую часть.
Любой программный модуль всегда создается для обработки данных некоторого типа, определяемого множеством его допустимых значений. Недопустимыми считаются значения, не пренадлежа-щие указанному множеству. Свойство детерминированности программного модуля функционального наполнения пакета заключается в том, что результат ( эффект) работы этого модуля как с допустимыми, так и недопустимыми наборами входных данных должен быть определен и удовлетворять спецификациям пакета.
Функциональное наполнение пакета имеет уровневую структуру. Это объясняется тем, что в предметной области пакета всегда можно выделить основные (базовые) понятия и отношения между ними (базовые операции). Программные модули, которые реализуют такие операции, назовем базовыми, а их совокупность - базовым уровнем функционального наполнения. Следует отметить, что именно при реализации базовых модулей может возникнуть необходимость использования языка ассемблера.
Для решения задач из рассматриваемого класса обычно требуется выполнение определенной последовательности базовых операций. Каждая такая последовательность практически определяет новую операцию - операцию более высокого уровня. Программные модули, реализующие эти операции, также могут быть включены в состав библиотеки пакета, что и определяет многоуровневую структуру функционального наполнения.
Каждый уровень функционального наполнения определяет проблемно-ориентированный язык общения пользователя с пакетом. Реализация программного обеспечения таких языков (входных языков пакетов) [9, ю] дает возможность общения с пакетом пользователям с различным уровнем профессиональной и программистской подготовки. Программное обеспечение входных языков входит в системное наполнение пакета.
Системное наполнение пакета прикладных программ должно обеспечивать: обслуживание библиотеки пакета, обеспечение ее связи со входными языками пакета; поддержку языков общения с пользователями; - доступ к информационному наполнению пакета. Системное наполнение может включать также средства, повы шающие уровень использования возможностей пакета, например, обеспечивающие диалоговый режим работы пользователей и др.
Достаточно высокого уровня пользовательского сервиса можно добиться и при квалифицированном использовании соответствующих средств системы программирования, существующей на ЭВМ, как это справедливо отмечается автором работы [ I ] , приводящим в качестве примера международный пакет MODULEF [її] . Более того, может быть реализована пакетно- ориентированная система программирования, заменяющая системное наполнение всех ППП, которые в этой системе эксплуатируются.
К информационному наполнению пакета предъявляются следующие требования : полнота документации. Исходные тексты всех программных модулей, их формальные спецификации и инструкции по использованию должны быть приведены полностью в сопровождающей документации пакета ; полнота системы тестов ; удовлетворение информационных запросов, поступающих как от пользователей, так и от программных компонентов пакета.
Для работы с ППП можно использовать несколько языков различного назначения [2,9] : язык, на котором пишутся все или основная часть модулей библиотеки пакета. Будем называть этот язык основным языком пакета (0ЯЇЇ). Как уже отмечалось выше, часть модулей в целях повышения эффективности может быть написана на языке ассемблера той ЭВМ, на которой данный пакет будет эксплуатироваться. Так, например, реализована " сменная" ( отдельно поставляемая) часть пакета [60] ; входные языки пакетов, на которых формулируется задача пользователя [Ю] . Одним из входных языков является ОЯП. Уровне-вая структура функционального наполнения пакета позволяет предо- ставить пользователям различной квалификации языки разных уровней;
3) язык общения с системным наполнением пакета.
Среди специалистов, работающих с пакетом, различаются его разработчики и пользователи. Разработчик имеет возможность вносить изменения в библиотеку пакета. Он определяет структуру ШШ, класс решаемых задач, разрабатывает и модифицирует прикладные программы. Среди разработчиков можно выделить собственно разработчиков и лиц, сопровождающих пакет.
Пользователям разрешен доступ к библиотеке пакета только для чтения и использования имеющихся в ней модулей. Специалисты-пользователи могут иметь различный уровень программистской и профессиональной подготовки [3,5]. Поэтому для работы с ШШ пользователям должны предоставляться различные входные языки. Удобно, чтобы такие языки были проблемно- ориентированными.
В настоящее время разработан ряд проблемно- ориентированных языков для описания вычислений с матрицами, например, А/ЛІЯІХ [62],A?ATLAN [63], 01/2 [64], LINEAL [65]. Обзору предоставляемых этими языками возможностей посвящены работы[66,67].
Появление проблемно- ориентированных языков было обусловлено следующими причинами : во- первых, пользователям удобно описывать постановку задачи в терминах проблемной области, а универсальные языки программирования таких средств не имеют ; во- вторых, матричные вычисления являются одним из этапов при решении многих практических задач, поэтому целесообразно выделить некоторые типовые задачи и реализовать их в виде языковых операций. При этом необходимо, чтобы программные модули, реализующие данные операции, удовлетворяли описанным выше требованиям точности и эффективности ; в- третьих, для некоторых категорий пользователей желательно
10 автоматизировать выбор метода решения поставленной задачи. Такая проблема является достаточно сложной при решении задач численного анализа, в частности, в линейной алгебре и требует от пользователя высокой профессиональной квалификации. Неправильный выбор алгоритма может привести к неправильным результатам, о чем сам пользователь может и не знать.
ППП является сложной программной системой, включающей обычно большое число программных модулей. Разработка ППП, удовлетворяющего современным требованиям, представляет собой сложный и длительный процесс, характеризующийся многообразием подходов [32 - 34]. В настоящее время в целях повышения эффективности и качества разработок большое внимание уделяется вопросам технологии и методов программирования [1,3,12 - 14].
Особую важность приобретают технологии, охватывающие весь процесс разработки (например, [15,16] ) . В основе этих технологий лежит определение требований к разрабатываемой системе в виде спецификаций и отслеживание соответствия этим требованиям на всех этапах разработки.
Формальный метод описания спецификаций существенно облегчает разработку и реализацию больших программных систем. В существующей практике используются, в основном, неформальные методы. При этом спецификации часто даются схематично и неполно, что отрицательно сказывается на качестве разработки. Написание формальных спецификаций заставляет разработчика четко представлять структуру системы и взаимодействие ее частей.
Спецификации можно автоматически интерпретировать и использовать для отладки системы при ее разработке на начальных этапах, когда еще не все необходимые компоненты реализованы. Это важно, поскольку проектирование и реализация пакета требуют больших временных затрат и не все предъявляемые к нему требования мо- могут быть удовлетворены сразу. Период опытной эксплуатации позволяет совершенствовать разрабатываемую систему в целом. Согласно работе Парнаса Д.Л.[17] спецификации должны : предоставлять предполагаемому пользователю ту и только ту информацию, которая необходима для корректного использования программы ; предоставлять реализатору всю информацию о предполагаемом использовании, которая требуется, чтобы выполнить реализацию ( и никакой дополнительной информации) ; быть настолько формальной, чтобы можно было говорить об автоматической проверке ее непротиворечивости, полноты и других полезных свойств ; выражаться в терминах, обычно используемых пользователем и реализатором.
Формальные спецификации являются важным средством общения между различными категориями пользователей, так как содержат все необходимые и достаточные сведения как для разработчика модулей пакета, так и для пользователя, желающего разобраться в уже созданной системе. Поэтому формальные спецификации являются неотъемлемой частью документации для всех категорий пользователей.
Для написания формальных спецификаций используются специальные языки. Обзор методов и описание требований к универсальному языку спецификаций даны в работах [18] и [19]. Предлагаемые различными авторами языки [17,20,61] , которые используются в практических разработках, не имеют пока инструментальной поддержки.
В настоящее время разработан ряд пакетов для решения задач линейной алгебры. Эти пакеты, однако, не полностью удовлетворяют предъявляемым к ним требованиям. %же рассматриваются наиболее известные ППП в данной предметной области.
1. Пакет прикладных программ АРАС (Алгоритмы .решения алгеб раических систем) [21, 35]. Разработан в Институте Кибернетики АН УССР им. В.М.Глушкова.
Пакет предназначен для решения систем линейных уравнений с произвольными действительными матрицами.
Входными данными для работы пакета АРАС являются: исходная матрица и точность задания ее элементов, правые части и точность их задания, требуемая точность решения и некоторые дополнительные сведения о матрице, например, симметричность и т.д.
Результатами работы являются: вычисленное решение и оценка его точности (если решение не может быть получено, то выдается отказ с указанием причины и рекомендациями по дальнейшим действиям пользователя), протокол решения задачи и некоторые промежуточные результаты, выдаваемые по требованию пользователя, например, нормы исходной и оценка нормы обратной матрицы, сингулярные числа и т.д.
Основным языком пакета является Фортран-1У. Режим работы -пакетный.
Пакет АРАС включает библиотеку модулей вычислительных алгоритмов, библиотеку системных модулей и архив. Программные модули объединены управляющей программой, которая анализирует заданную систему уравнений (тип, размерность, точность исходных данных) и выбирает наиболее подходящий метод ее решения [21].
О недостатках пакета АРАС трудно судить, поскольку ни тексты программных модулей функционального наполнения, ни их спецификации не опубликованы. Это является серьезным препятствием для практического использования пакета.
2. Пакет/% для решения систем линейных уравнений с разреженными матрицами [22].
В пакете используется метод исключения Гаусса. Основное вни- ІЗ мание при разработке пакета уделено оптимизации алгоритмов - учету специфики хранения в памяти машины разреженных матриц и получению оптимальной структуры матрицы для решения задачи. Используется динамическое распределение памяти.
Хорошо разработан аппарат диагностики во время работы пакета. При возникновении ошибки или сбоя автоматически устанавливаются и печатаются места в программе, где могут возникнуть прерывания и.их возможные причины. В некоторых случаях в специальном режиме возможно автоматическое исправление данных и продолжение вычислении с точки прерывания.
Кроме решения системы вычисляются с двойной точностью норма невязки и логарифм максимального отношения соседних главных миноров матрицы, характеризующие точность решения системы и обусловленность матрицы.
3. Пакет 7№М/Щ.Є>0 ] для решения систем линейных уравнений с матрицами различного вида.
В пакете ZZ/І^^широко использован пакет 3/А$( Sas/^ tmeat (2 4. Пакет ETSPACtt Гб9, 70] предназначен для решения полной, частичной и обобщенной проблемы собственных значений для широко го класса матриц. Для решения конкретной задачи на собственные значения необходимо собрать и выполнить некоторую последовательность модулей. Это можно сделать различными способами: во-первых, к любой подпрограмме пакета можно обратиться из 14 программы пользователя по имени посредством оператора ALL . Обмен данными в этом случае происходит через фактические и формальные параметры подпрограмм; во-вторых, для наиболее распространных случаев разработаны специальные подпрограммы, в которых уже собраны требуемые расчетные цепочки и выполнено согласование параметров между отдельными подпрограммами; в-третьих, можно использовать управляющую программу, которая вызывается из программы пользователя оператором HAIL . Обращение к управляющей программе можно рассматривать как запись запроса пользователя на решение задачи на проблемно-ориентированном входном языке пакета. Оценка качества программ, включаемых в пакет, проводится по значению следующего коэффициента: при решении: стандартной задачи на собственные значения A і?-Л-^ и по аналогичным зависимостям для других постановок задач. Здесь /V - порядок матрицы А; Множитель 10 выбран эмпирически для получения следующего критерия: если Z^:/, то считается, что программа работает удовлетворительно ; если /^/^^-/Д0 % то работа с программой должна осуществляться осторожно и необходимо выполнить дальнейшее исследование для анализа ошибок; если/^^^7, то для данной матрицы (или класса матриц) программа считается неудовлетворительно работающей и ее исполь- зование при решении задач для данного класса матриц не рекомендуется. Следует отметить, что вычисление описанной выше оценки не решает вопроса о достоверности полученного решения, так как неудовлетворительное значение коэффицента М- может быть обусловлено ошибками в программе, плохой обусловленностью исходной матрицы к проблеме собственных значений или к проблеме обращения, а также ошибками в исходных данных. Таким образом, получив плохую оценку// , пользователь не имеет информации о том, что необходимо делать, чтобы исправить положение: диагностика критической ситуации получается неполной, а поэтому бесполезной. Выяснить причину неудовлетворительного значения^ может помочь апостериорная оценка вычисленного решения, которая, однако, в пакете не вычисляется. Для обеспечения полноты диагностики функциональное наполнение пакета должно содержать программные модули, которые проверяют правильность задания свойств исходной матрицы. Для задач линейной алгебры это очень важно, поскольку вероятность появления ошибки в коэффициентах исходной матрицы, особенно большой размерности, достаточно велика. Тексты программ и их описание на неформальном уровне опубликованы и доступны не только разработчикам (и реализаторам), но и всем пользователям. Существенным недостатком описанного пакета является то, что его функциональное наполнение не позволяет оценить достоверность вычисленного решения. 5. Библиотека Численного анализа МГУ [23]. В части решения задач на собственные значения данный пакет базируется на функциональном наполнении выше описанного пакета ZSPAP. На базе Библиотеки Численного анализа МГУ создан пакет с более развитыми системными возможностями IGEN [24] для решения некоторых задач на собственные значения для различных классов матриц. Средством общения пользователей с пакетом является проблемно- ориентированный язык простой стркутуры, который доступен для использования в рамках языка Фортран в режиме интерпретации. Описание программных модулей и их тексты не опубликованы. Для решения задач линейной алгебры кроме перечисленных ЇЇПЇЇ могут быть использованы программы библиотек &$Р {Scie/itiftC SuStoatine Package ) [25] и І її SI (b-nieraational Malke/naue and Staiisiic LiSraries )[78]. Первая из них является совокупностью программ, реализующих наиболее часто встречающиеся в приложениях методы численного анализа. Библиотека I/iSL в числе других включает программы для решения задач на собственные значения, которые являются прямым переводом на Фортран некоторых программ Справочника [27] . Из сказанного выше можно сделать вывод, что обеспечению гарантированной точности результатов, как одному их основных требований к ІЇЇШ для решения задач численного анализа, не уделяется должного внимания. Пользователь же заинтересован в получении решения поставленной им задачи с заданной точностью. Поэтому в ППП должны быть включены средства, позволяющие оценить достоверность вычисленного приближенного решения и в случае получения результатов, точность которых не удовлетворяет пользователя, не ограничиваться только констатацией факта, а по возможности уточнить эти результаты. Из рассмотренных выше ППП для решения задач линейной алгебры достоверность результатов оценивается лишь в тех из них, где для этого достаточно вычисления невязки решения. Это ППП для решения систем линейных алгебраических уравнений. Средств для уточнения приближенного решения перечисленные ШШ не имеют. При решении задач на собственные значения оценка погрешности вычисления собственных векторов нормальных матриц, а также собственных значений и собственных векторов матриц, которые не являются нормальными, требует более сложных вычислений [7б]. Это вызвано тем, что малое значение невязки в этом случае не гарантирует близости вычисленного решения к точному. Достаточно сложно решается также и задача уточнения приближенного решения. Таким образом, разработка пакета прикладных программ для решения алгебраической проблемы собственных значений, который должен обеспечивать получение пользователем результатов с заданной точностью, является актуальной задачей. При разработке предлагаемого в диссертационной работе ППП СОЗНАМ ( Собственные значения матриц) для решения задач на собственные значения используется технология, предполагающая выполнение двух этапов : определение требований к ШШ в целом и к отдельным компонентам его функционального наполнения и фиксация их в виде формальных спецификаций. В качестве языка спецификаций используется язык, описанный в работе [20] ; реализация программных модулей по их спецификациям ( программирование, отладка и тестирование каждого модуля и комплексная отладка). Диссертация содержит 4 главы и приложение. В первой главе на основе анализа современного состояния теории численных методов решения алгебраической проблемы собственных значений обосновывается состав функционального наполнения разрабатываемого ППП СОЗНАМ. Решение задачи с гарантированной точностью предполагает, что по входным данным ( элементы исходной матрицы, точность их задания, тип матрицы, какие собственные значения и собственные векторы требуется определить) либо вычисляется решение с требуемой точностью, либо выдается сообщение о том, что средствами пакета задача в такой постановке не может быть решена, указываются, если возможно, причины этого и даются рекомендации по возможному изменению постановки задачи. Для решения указанной задачи в состав функционального наполнения ППП включены подпрограммы апостериорной оценки вычисленного приближенного решения и подпрограммы уточнения полученных результатов. Порядок проведения расчета зависит от постановки задачи и от конкретной матрицы. Методы, используемые для создания функционального наполнения разрабатываемого ІЇЇЇЇІ СОЗНАМ, выбраны на основе сравнительного анализа численных методов решения алгебраической проблемы собственных значений, проведенного в главе I. Рассматриваются уровневая структура и состав функционального наполнения пакета. Описывается численный метод вычисления скалярного произведения на ЭВМ с плавающей запятой без накопления ошибок округления результатов промежуточных действий. В основу этого алгоритма положены принцип выполнения операции сложения вещественных чисел с фиксированной запятой и возможность программного доступа ко всем разрядам плавающего регистра ЭВМ. Во второй главе рассматриваются формальные спецификации базового уровня функционального наполнения ППП. Формальное описание ППП фиксирует требования, предъявляемые к отдельным программным модулям и ко всему пакету в целом. Сравнение спецификаций и исходных текстов подпрограмм позволяет выявлять ошибки в подпрограммах, модифицировать их с целью повышения эффективности или адаптации под свои задачи, добавлять в пакет новые подпрограммы для решения конкретных задач. Дается краткое описание используемого языка спецификаций. Одной из особенностей этого языка является выделение понятий модуля ( набор взаимосвязанных входов) и пакета ( набор модулей и других пакетов). Функциональное наполнение ППП СОЗНАМ составляет пакет в смысле языка спецификаций. Приводятся формальные спецификации одной из компонент пакета, а именно, пакета СИМ_ПР0Б1_ СЗН для решения проблемы собственных значений для действительных симметричных матриц. Конкретную подпрограмму, реализующую процедуру или функцию по ее спецификации из описания пакета, разрешается включать в состав функционального наполнения ЇЇЇЇП только в том случае, когда выполняются все условия, описанные в разделах ИСКЛ^СЙТУАЦИЯ ( некорректное обращение к модулю), ЭФФЕКТ ( производимые модулем действия) и ОГРАНИЧЕНИЯ ( дополнительные ограничения на реализацию подпрограммы относительно необходимого объема оперативной памяти ( в байтах) и числа " медленных" операций, например, извлечения квадратного корня, деления и др.). Третья глава посвящена организации работы с ППП СОЗНАМ пользователей с различной профессиональной и программистской подготовкой. Возможность такого обслуживания обеспечивается уров-невой структурой функционального наполнения пакета. При работе с ППП на базовом уровне соответствующие подпрограммы для решения поставленной задачи вызываются непосредственно из программы пользователя. Они используются как операции предметной области пакета. Для некоторых классов матриц могут быть зафиксированы последовательности вызовов подпрограмм базового уровня, использование которых обеспечивает получение результатов с гарантированной точностью. При этом общение с ПШІ упрощается и сводится к вызову подходящих подпрограмм, составляющих второй уровень функционального наполнения. Пользователю предоставляется возможность решать задачи на собственные значения для действительных симметричных матриц в диалоговом режиме. В процессе диалога описывается постановка задачи, с помощью поискового дерева выбирается соответствующая подпрограмма второго уровня для ее решения, задаются значения фактических параметров этой подпрограммы, вычисляются и выводятся результаты расчета. Если постановка задачи определяет не реализованную подпрограмму второго уровня, то пользователь получает соответствующее сообщение и может работать с ППП только на базовом уровне. Приводится пример решения полной проблемы собственных значений для действительной симметричной матрицы с использованием возможностей, предоставляемых пакетом на различных уровнях. В четвертой главе описываются результаты использования разработанного ППП для решения практической задачи исследования динамической нагруженности трансмиссии тракторов на стадии проектирования. Выполнен расчет форм свободных колебаний и собственных частот динамической системы, которые вместе с частотными характеристиками источников возбуждения позволяют до испытаний опытного образца аппроксимировать экспериментальные данные на другие участки силовой передачи, воссоздавая тем самым полную картину ее динамической нагруженности. Кроме того, полученные данные служат основой для проведения оптимизации динамической нагруженности валопровода путем варьирования параметрами, описывающими эквивалентную крутильно- колеблющуюся систему машины. Применение пакета СОЗКАМ позволило более точно определить спектр собственных частот для некоторых марок тракторов и исследовать влияние реактивности системы. Полученные результаты согласуются с данными полевых испытаний. В приложении приведены: тексты программ и результаты тестовых расчетов вычисления всех собственных значений и собственных векторов действительной верхней матрицы Хессенберга. На примере отдельной собственной пары ( собственное значение и соответствующий ему собственный вектор) показано использование различных численных методов для оценки погрешности вычисления решения и его уточнения ; текст подпрограммы второго уровня для решения полной проблемы собственных значений для действительной симметричной матрицы ; текст программы и результат расчета форм свободных колебаний и собственных частот динамической системы трансмиссии одного из тракторов. Новыми результатами в данной работе являются : На основе системного анализа современного состояния теории численных методов решения проблемы собственных значений разработано функциональное наполнение ЇЇШІ, обеспечивающее вычисление решения с гарантированной точностью для различных классов матриц. Неудовлетворительные с точки зрения пользователя решения могут быть правильно интерпретированы с помощью количественной оценки достоверности решения с целью последующего уточнения исходных данных. Выдаются лишь те результаты, точность которых гарантирована. Разработано информационное наполнение ПЇЇЇЇ, основой которого являются формальные спецификации подпрограмм базового уровня функционального наполнения. Наличие формальных спецификаций позволяет выявлять и устранять ошибки в подпрограммах в процессе сопровождения пакета, расширять состав ППП на различных уровнях, а также облегчает переход к использованию другого языка программирования. 3. Разработан и реализован новый метод вычисления скалярного произведения на ЭВМ с плавающей запятой, в котором не накапливаются ошибки округления результатов промежуточных действий. На защиту выносятся : Пакет прикладных программ СОЗНАМ, предназначенный для решения с гарантированной точностью проблемы собственных значений для различных классов матриц. Пакет реализован на языке Фортран в ОС ЕС ЭВМ. Формальные спецификации программных модулей базового уровня ППП, которые являются основой принятой технологии разработки и реализации пакета. Алгоритм точного вычисления скалярного произведения на ЭВМ с плавающей запятой, который позволяет получить результат, отличающийся от точного на ошибку одного округления, связанного с его представлением в ЭВМ. Программное обеспечение пакета СОЗНАМ. Уровневая структура функционального наполнения пакета позволяет реализовать языковые интерфейсы, ориентированные на различные классы пользователей и режимы работы. Использование априорных оценок численных методов решения задачи не позволяет оценить близость машинного и точного решений, поскольку такие оценки оказываются чрезвычайно завышенными. Однако по приближенным собственным значениям и собственным векторам во многих случаях удается получить достаточно хорошие апостериорные оценки погрешности, а затем, если потребуется, уточнить имеющиеся приближения. В данном параграфе рассматриваются некоторые способы вычисления апостериорной оценки погрешности и уточнения результатов решения проблемы собственных значений. Отдельно выделен случай нормальных матриц, поскольку для них задача оценки и уточнения решается более просто. Матрица А называется нормальной, если она перестановочна со своей сопряженной матрицей Л , т.е. А-А = А -А [зі]. Приближенное собственное значение Л и соответствующий ему приближенный собственный вектор ее матрицы А составляют пару (jl, х), в дальнейшем называемую приближенной собственной парой или собственной парой. Для оценки приближения к точному собственному значению (Xra(/H} для стандартной задачи на собственные значения А ос Хэс используется евклидова норма вектора невязки: z Ax-Xx. (I-I) Тогда: Последнее соотношение показывает, что в круге с центром JL и радиусом ё находится хотя бы одно точное собственное значение, При решении обобщенной проблемы собственных значений оценка погрешности вычисляется аналогично: ъ = Асс-Лб , (1_з) и тогда Для нахождения оценок (I.I) и (1.3) требуется вычислять скалярное произведение. Выполнение данной операции по стандартному алгоритму приводит к значительноглу накоплению ошибок округления промежуточных действий, что, в свою очередь, может привести к ухудшению оценки. Поэтому предусматривается возможность использования различных алгоритмов вычисления скалярного произведения. В состав функционального наполнения разрабатываемого пакета СОЗНАМ включено три варианта процедуры апостериорной оценки точности вычисления собственных значений для нормальных матриц, использующие стандартный алгоритм, вычисления с накоплением (операнды типау#и / ) и специальный алгоритм для вычисления скалярного произведения (глава I, раздел 1.5). Проведенные расчеты показывают, что имеет смысл пытаться использовать второй и третий способ вычисления скалярного произ ведения при оценке точности только в том случае, когда погрешность решения на 1-2 десятичных знака больше требуемой. Для нормальных матриц оценка погрешности вычисления собственного вектора ос определяется соотношением [72]: Отсюда видно, что получение этой оценки предполагает вычисление норм невязок по всем собственным значениям, и таким образом, формулой (1.4) можно воспользоваться только в случае решения полной проблемы собственных значений. Если же решается частичная проблема, то используется оценка, описываемая ниже для матриц, которые не являются нормальными. Для оценки точности вычисления собственных значений нормальной матрицы, а также для одновременного их уточнения, может быть использовано отношение Релея C/UA) [73], которое минимизирует норму невязки по всем собственным векторам, соответствующигл собственному значению Л- . Для ненормализованных собственных векторов минимальное значение нормы невязки достигается при _ (Ах,х) ее7 А ее _ ссг(Лос+г) /JL J11 " (сс,сс) cr rr ocTsc -fen , (I-5) где з т- транспонирован относительно вектора JC. В случае, когда собственное значение должно быть найдено с высокой точностью, следует использовать те же способы вычисления скалярного произведения, снижающие уровень ошибок округления промежуточных действий, что и для оценок (I.I) и (1.4). Если /Ах-Лз://- ,, то для соотношения Релея всегда имеет место //Avz/bpz/f e +g. (1#6) Предположим, что в круге с центрому% и радиусом й существует только одно собственное значение (т.е. это собственное значение - простое) и что все другие удовлетворяют условию тах / е - Л а Я- (1.7) Тогда: Как видно из (1.8) отношение Релея имеет ошибку порядка (g )z/ct , поэтому при уменьшении значения а имеет место ухудшение оценки (1.8). Если & и - величины одного порядка, и собственный вектор нормирован так, что // // =1 , то формула (1.8) не пригодна для использования. Однако, как показано в работе [73], ухудшение отношения Ре-лея, которое наблюдается при патологически близких собственных значениях, не происходит для матриц, имеющих кратные корни. Для матриц, которые не являются нормальными, получение апостериорных оценок погрешности является более сложной задачей, так как норма вектора невязки не является достаточной информацией для оценки ошибки в приближенных собственных значениях [74, 76] . Хорошая аппроксимация собственной пары гарантирует малое значение нормы вектора невязки, но обратное утверждение неверно. Функциональное наполнение пакета СОЗНАМ имеет уровневую структуру. Вычислительные возмошюсти пакета отражают подпрограммы самого нижнего - базового уровня. Одним из возможных способов организации расчетов является непосредственное использование этих подпрограмм с помощью средств сборки программ, представляемых стандартной ОС машины, на которой эксплуатируется пакет. Общение пользователя с пакетом на базовом уровне требует от него высокой квалификации в прикладной области и знания основ программирования на ЭВМ. Только в этом случае можно правильно выбрать последовательность базовых подпрограмм пакета и сформировать из них программу для решения конкретной задачи. Пользователь, использующий пакет на этом уровне, должен знать его структуру, назначение и особенности реализации его модулей и т.д. Для задач численного анализа, и в частности, в линейной алгебре, выбор метода решения является достаточно сложной задачей. Неправильный выбор алгоритма может привести к ошибочным результатам, о чем сам пользователь может и не знать, если у него нет средств для оценки достоверности результатов. Очевидно, что непосредственное использование программ базового уровня доступно не всем пользователям, а лишь наиболее подготовленной их части. Такие пользователи в дальнейшем будут называться квалифицированными. Для остальных, неквалифицированных, пользователей должны быть предоставлены некоторые средства, облегчающие использование подпрограмм базового уровня для решения конкретной задачи. Для наиболее распространенных случаев могут быть собраны цепочки базовых подпрограмм, оформленные в виде отдельных подпрограмм. Пользователю такой подпрограммы достаточно правильно задать со ответствующий оператор вызова CALL . При этом отпадает необходимость согласования параметров между отдельными подпрограммами базового уровня, испольуемыми для решения поставленной задачи. Совокупность полученных таким образом подпрограмм составляет второй уровень функционального наполнения пакета. В принципе могут быть созданы программы более высокого уровня, например, типа управляющей программы 1$РАС пакета EISPACK [70] и др. [24]. Значение параметров этой программы задаются в терминах, близких к терминам предметной области. Указанная управляющая программа представляет собой в действительности проблемно- ориентированный язык специального назначения для решения проблемы собственных значений. На третий уровень функционального наполнения разрабатываемого пакета выносятся программы обеспечения работы пользователя в диалоговом режиме. Значения параметров, управляющих выбором подпрограммы второго уровня для решения поставленной задачи, задаются в виде ответов на сообщения системы. Реализация такого режима работы базируется на использовании " меню", описывающем вычислительные возможности пакета в соответствующих терминах предметной области. Далее рассматривается структура базового уровня функционального наполнения. На этом уровне выделяется несколько групп подпрограмм ( рис. I.I) : I. Подпрограммы масштабирования исходной матрицы и восстановления ее собственных векторов. К этой группе относятся подпрограммы, выполняющие : а) масштабирование комплексной и действительной матриц об щего вида. При этом, где возможно, изолируются собственные зна чения ; б) восстановление собственных векторов исходной матрицы. 2. Подпрограммы приведения исходной матрицы к специальному виду и востановления собственных векторов нормированной исход ной матрицы. К этой группе относятся подпрограммы, выполняющие : а) приведение комплексной и действительной матриц общего вида соответственно к комплексной и действительной верхней мат рице Хессенберга ( используются унитарные, элементарные устойчи вые или ортогональные преобразования подобия ) ; б) приведение комплексной Эрмитовой, действительной симмет ричной плотной и ленточной, действительной несимметричной трех диагональной матрицы к действительной симметричной трехдиаго нальной матрице ( используются ортогональные преобразования Хаусхолдера, плоские вращения, диагональные преобразования ) ; в) приведение обобщенной проблемы собственных значений к стандартной задаче ( используются разложение Холецкого и Q2 алгоритм ) ; г) восстановление собственных векторов исходной матрицы из собственных векторов приведенной матрицы и собственных векторов для обобщенной проблемы. 3. Подпрограммы решения полной проблемы собственных значе ний для матриц специального вида. К этой группе относятся под программы, выполняющие : а) решение полной проблемы собственных значений для комп лексной и действительной верхней матрицы Хессенберга ( исполь зуются степенные методы). По желанию пользователя вычисляются либо все собственные значения и соответствующие им собственные векторы, либо только все собственные значения ; Основополагающей идеей используемого метода формального описания программных модулей является определение данных как набора логических объектов, каждый из которых обладает множеством допустимых состояний. Работа с данными осуществляется путем вызова специальных процедур, которые либо выдают состояние объектов, либо меняют его соответствующим образом. При этом эффект описывается совокупностью отношений на значениях состояний объектов до и после обращения к процедуре. В качестве независимой единицы описания программного обеспечения выделяется модуль. Группа взаимосвязанных модулей может быть объединена в пакет. В состав пакета могут входить не только модули, но и другие пакеты. Это определяется сложностью описываемой системы. При описании синтаксиса используемых конструкций с помощью обычных металингвистических формул Бэкуса- Наура приняты следующие соглашения : - группа символов, которая в описании может быть пропущена, заключается в двойные скобки [[ ] ; - группа символов, которая в описании может быть повторена 0 или целое число раз, заключается в фигурные скобки V ; - нетерминальные символы обозначаются прописными буквами. В качестве символа продолжения используется знак подчеркивания - терминальные символы обозначаются заглавными буквами с подчеркиванием ; - разделение альтернатив выполняется знаком ! . описание_пакета::= ПАКЕТ имя_пакета [( список_параметров_ пакета ) [раздел__определений_констант ] [Граздел_определений_типов J описание__элемента_пакета / ; описание_элемента_пакета КРЫШ [[ имя_пакета ] ; Модули описываются с помощью конструкции, имеющей аналогичную структуру : описание_модуля::= МОДУЛЬ имя_модуля ([( список_параметров_ модуля) ВХОДЫ : имя_входа , имя входа V ; ИСПОЛЬЗУЮТСЯ : имя_модуля /, имя__модуляУ; раздел_рпределений_констант J раздел_определений_типов J [[раздел определений процедур и функций КОНЕЦ [[имя модуля ] ; Если в описании пакета ( модуля) присутствует раздел_оп-ределений_констант или типов, то введенные в нем константы и типы являются общими для всех входящих в него модулей ( процедур и функций). Для введения новых типов данных ( на основе предопределенных типов) используются средства, аналогичные аппарату конструирования типов в Паскале [49]. Допускается вводить новые скалярные типы ( тип перечисления или отрезок) и структурные типы ( тип массив, тип строка и тип запись). описаниеш_элемента_пакета ::= описание_пакета ! описание_модуля ! ПАКЕТ имя пакета [[ ( список_статических_выражений) ! МОДУЛЬ имя_модуля ( список_статических_выражений) J Доступные вне модуля ресурсы определяются в списке входов. Элементами этого списка могут быть имена процедур и функций модуля, а также имена констант и типов, которые определены в описываемом модуле. Любой модуль пакета может использовать ресурсы других модулей. При этом доступными считаются ресурсы только тех модулей, имена которых помещены в список используемых модулей. Основное содержание модуля, определяемое выполняемыми им действиями, отражается в разделе определения процедур и функций. В состав пакета могут входить и такие модули, которые содержат только константы или типы ( или и то и другое), описание процедуры : := ПРОЦЕДУРА имя_процедуры I ( список_параметров) J ; спецификация КОНЕЦ имя_процедуры ; Аналогичную структуру имеет описание функции : описание_функции : := ФУНКЦИЯ имя_функции [(список_параметров) ] : указатель_типа ; спецификация КОНЕЦ имя_функции ; Параметры процедур и функций специфицируются как входные, выходные и смешанные ( входной- выходной), с помощью указания соответствующего класса ( по умолчанию устанавливается статус входного параметра). В спецификации процедур и функций описываются начальные значения, исключительные ситуации, эффекты работы и ограничения на реализацию. описание_начальных_значений ::= НАЧ_ЗНАЧЕНИЕ : статическое выражение описание__исключительной_ситуации ::= описание_ситуации /;описание_ситуации Исключительные ситуации могут возникнуть при некорректном обращении к модулю. Каждой такой ситуации дается имя и в виде логического выражения описывается условие ее возникновения ( при истинном значении выражения). Ситуации, связанные с выходом значений параметров за пределы указываемого типа данных, можно не описывать, поскольку предполагается, что при выполнении модуля производится контроль типов. описание_эффекта ::= соотношение /; соотношение Подпрограмма, приведенная в предыдущем разделе ( или аналогичная ей), может быть использована автором или другим пользователем неоднократно. Поэтому такие программы обычно оформляются в виде отдельных подпрограмм и записываются в библиотеку ( текст подпрограммы приведен в приложении). После завершения работы подпрограммы кроме вычисленного решения ( собственных значений и собственных векторов), пользователю предоставляется следующая информация : 1) Достигнута ли заданная точность ( на это указывает значение переменной FLAG- ) ; 2) Если заданная точность не достигнута, то : а) в каких собственных значениях и собственных векторах; б) какая точность достижима. Таких подпрограмм, фиксирующих последовательность вызовов подпрограмм базового уровня, в личной библиотеке пользователя может быть достаточно много. Те из них, которые обеспечивают получение решения с заданной точностью для всех матриц из некоторого класса, целесообразно включить в библиотеку пакета. При этом упрощается решение типовых задач и общение с ШШ сводится к вызову подходящих подпрограмм, составляющих второй уровень функционального наполнения пакета. В практических расчетах может возникнуть необходимость решения задач с матрицами, свойства которых не позволяют гарантировать получение результатов с требуемой точностью. Так, матрицы, не являющиеся нормальными, могут иметь сколь угодно большие коэффициенты перекоса. Это приводит к тому, что не всегда удается даже оценить погрешность вычисленного решения, не говоря уже о его уточнении. Поэтому составление подпрограмм второго уровня для таких матриц теряет смысл и при решении указанных задач пользователю предоставляется только базовый уровень пакета. При этом пользователь, зная конкретные особенности решаемой задачи ( матрицы), применяет методику раздела 3.1, используя подпрограммы базового уровня как операции при написании программы ее решения. Составленная им программа, вообще говоря, будет неприменима к другим матрицам, даже достаточно близким к исходным. Поэтому включение ее в библиотеку пакета нецелесообразно. Работа пользователей с ППП в диалоговом режиме Из сказанного в предыдущих разделах видно, что подпрограмм второго уровня может быть достаточно много. При этом возникает проблема по постановке задачи пользователя либо отыскать нужную подпрограмму, либо выдать сообщение о том, что такой подпрограммы в функциональном наполнении пакета не содержится. Для решения этой проблемы может быть использовано поисковое дерево. Каждая подпрограмма второго уровня предназначена для решения конкретной задачи для определенного узкого класса матриц. На основании классификации характеристик решаемых задач и свойств матриц выделяется ряд параметров, называемых в дальнейшем параметрами выбора, которые используются для построения поискового дерева. И таким образом, каждой подпрограмме второго уровня соответствует определенный набор параметров выбора с заданными их значениями. Вершинами поискового дерева являются параметры выбора, а исходящие из вершин ребра соответствуют значениям этих параметров. Листьями дерева являются имена подпрограмм второго уровня ( либо реализованных, либо не реализованных к моменту решения задачи). Если выбрана не реализованная подпрограмма, то пользователь получает соответствующее сообщение и может работать с ТТГЇЇТ только на базовом уровне. Если постановка задачи определяет реализованную подпрограмму второго уровня, то пользователю предоставляются следующие возможности : 1) распечатать текст подпрограммы на ІЩПУ или просмотреть его на экране дисплея ; 2) записать подпрограмму в библиотеку пользователя и получить описание соответствующего обращения к ней ; 3) выполнить подпрограмму. Поиск по дереву, т.е. выбор подпрограммы второго уровня по постановке задачи, может выполняться либо специальной ( головной) подпрограммой, либо в режиме диалога, например, с помощью "меню". Головная подпрограмма может быть составлена по принципу подпрограммы ГГ6РАС пакета 1 SPA О К [69]. Список параметров указанной подпрограммы содержит параметры переменной длины и " ключевые" параметры для описания задачи ( в терминах предметной области) и для группировки взаимосвязанных подпараметров.Алгоритм апостериорной оценки и уточнения приближенного решения задачи на собственные значения
Структура и состав пакета сознам
Язык спецификаций программных модулей
Общение пользователей с ШШ на втором уровне
Похожие диссертации на Пакет прикладных программ для решения алгебраической проблемы собственных значений с гарантированной точностью
