Пакет прикладных программ для решения алгебраической проблемы собственных значений с гарантированной точностью тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Теплякова, Татьяна Александровна

• Теплякова, Татьяна Александровна
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Теплякова, Татьяна Александровна

ВВЕДЕНИЕ.

ГЛАВА I. ФУНКЦИОНАЛЬНОЕ НАПОЛНЕНИЕ ПАКЕТА ПРИКЛАДНЫХ

ПРОГРАММ СОЗНАМ.

1.1 Назначение пакета

1.2 Численные алгоритмы решения алгебраической проблемы собственных значений

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

1.4 Структура и состав пакета СОЗНАМ.

1.5 Алгоритм вычисления точного скалярного произведения на ЭВМ с плавающей запятой

ГЛАВА 2. СПЕЦИФИКАЦИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

ПАКЕТА СОЗНАМ.

2.1 Назначение языка спецификаций.

2.2 Язык спецификаций программных модулей.

2.3 Спецификация программных модулей базового уровня пакета СОЗНАМ

ГЛАВА 3. ОРГАНИЗАЦИЯ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЕЙ

С ПАКЕТОМ СОЗНАМ.

3.1 Общение пользователей с ППП на базовом уровне.

3.2 Общение пользователей с ППП на втором уровне

3.3 Работа пользователей с ППП в диалоговом режиме

3.4 Организация диалога.

3.5 Пример диалога.

ГЛАВА 4. ИСПОЛЬЗОВАНИЕ ППП СОЗНАМ ДЛЯ

ИССЛЕДОВАНИЯ ДИНАМИЧЕСКОЙ НА17УЖЕННОСТИ ТРАНСМИССИИ ТРАКТОРОВ НА СТАДИИ

ПРОЕКТИРОВАНИЯ.

Введение диссертации (часть автореферата) на тему «Пакет прикладных программ для решения алгебраической проблемы собственных значений с гарантированной точностью»

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

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

Пакетом прикладных программ (ШШ) будем называть комплекс:

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

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

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

Функциональное наполнение ППП определяет его прикладные возможности и должно обеспечивать возможность решения любой задачи из рассматриваемого класса. В этом смысле можно говорить о функциональной полноте ШШ.

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

Системное наполнение пакета составляют специализированные средства, обеспечивающие управление вычислительным процессом, т.е. организацию выполнения последовательностей модулей библиотеки пакета, обмен информационными массивами между отдельными модулями, формирование библиотеки пакета, хранение и редактирование данных и т.п. [I ]. Часть программных средств системного наполнения предназначена для поддержки языков общения пользователей с пакетом.

Информационное наполнение пакета,являющееся его неотъемлемой частью, состоит из следующих компонент:

- информационный файл тех данных, которые обрабатываются модулями библиотеки пакета. Этот файл содержит переменные и константы из соответствующей прикладной области (базу данных пакета);

- спецификации (формальное описание) модулей библиотеки пакета;

- исходные тексты модулей функционального и системного наполнения ППП;

- сопровождающая документация пакета (руководства для пользователей и для лиц, сопровождающих пакет);

- система тестов для отдельных модулей функционального и системного наполнения, а также для ППП в целом.

Такое понимание ППП можно считать общепринятым [I - 5] .

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

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

Функциональное наполнение пакета должны составлять программные модули, реализующие численно устойчивые методы решения задач в прикладной области пакета. Более того, эти методы должны быть реализованы таким образом, чтобы влияние ошибок округления в процессе вычислений было минимальным. Например, почти во всех программных модулях, реализующих алгоритмы линейной алгебры, содержится операция вычисления скалярного произведения. Использование стандартного алгоритма может привести к значительному накоплению ошибок округления [7,8] , что существенно снижает точность результата, делая его в ряде случаев неприемлемым. Поэтому для обеспечения точности вычислений требуются специальные алгоритмы ( например, см. раздел 1.5 главы I).

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

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

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

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

Каждый уровень функционального наполнения определяет проблемно-ориентированный язык общения пользователя с пакетом. Реализация программного обеспечения таких языков (входных языков пакетов) [9, ю] дает возможность общения с пакетом пользователям с различным уровнем профессиональной и программистской подготовки. Программное обеспечение входных языков входит в системное наполнение пакета.

Системное наполнение пакета прикладных программ должно обеспечивать:

- обслуживание библиотеки пакета, обеспечение ее связи со входными языками пакета;

- поддержку языков общения с пользователями;

- доступ к информационному наполнению пакета.

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

Достаточно высокого уровня пользовательского сервиса можно добиться и при квалифицированном использовании соответствующих средств системы программирования, существующей на ЭВМ, как это справедливо отмечается автором работы [ I ] , приводящим в качестве примера международный пакет МОЛИ!-ЕР [II] . Более того, может быть реализована пакетно- ориентированная система программирования, заменяющая системное наполнение всех ППП, которые в этой системе эксплуатируются.

К информационному наполнению пакета предъявляются следующие требования :

- полнота документации. Исходные тексты всех программных модулей, их формальные спецификации и инструкции по использованию должны быть приведены полностью в сопровождающей документации пакета ;

- полнота системы тестов ;

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

Для работы с ПШ можно использовать несколько языков различного назначения [2,9] :

1) язык, на котором пишутся все или основная часть модулей библиотеки пакета. Будем называть этот язык основным языком пакета (ОЯП). Как уже отмечалось выше, часть модулей в целях повышения эффективности может быть написана на языке ассемблера той ЭВМ, на которой данный пакет будет эксплуатироваться. Так, например, реализована " сменная" ( отдельно поставляемая) часть пакета [60] ;

2) входные языки пакетов, на которых формулируется задача пользователя [10] . Одним из входных языков является ОЯП. Уровне-вая структура функционального наполнения пакета позволяет предоставить пользователям различной квалификации языки разных уровней; 3) язык общения с системным наполнением пакета. Среди специалистов, работающих с пакетом, различаются его разработчики и пользователи. Разработчик имеет возможность вносить изменения в библиотеку пакета. Он определяет структуру ПШ, класс решаемых задач, разрабатывает и модифицирует прикладные программы. Среди разработчиков можно выделить собственно разработчиков и лиц, сопровождающих пакет.

Пользователям разрешен доступ к библиотеке пакета только для чтения и использования имеющихся в ней модулей. Специалисты-пользователи могут иметь различный уровень программистской и профессиональной подготовки [3,5]. Поэтому для работы с ППП пользователям должны предоставляться различные входные языки. Удобно, чтобы такие языки были проблемно- ориентированными.

В настоящее время разработан ряд проблемно- ориентированных языков для описания вычислений с матрицами, например, 1УАТЯ1Х [62],AfAГ¿ANL6>3],0¿/2 [64],1ША1 [65]. Обзору предоставляемых этими языками возможностей посвящены работы[66,67].

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

ППП является сложной программной системой, включающей обычно большое число программных модулей. Разработка ШШ, удовлетворяющего современным требованиям, представляет собой сложный и длительный процесс, характеризующийся многообразием подходов [32 - 34]. В настоящее время в целях повышения эффективности и качества разработок большое внимание уделяется вопросам технологии и методов программирования [1,3,12 - 14].

Особую важность приобретают технологии, охватывающие весь процесс разработки (например, [15,1б] ) . В основе этих технологий лежит определение требований к разрабатываемой системе в виде спецификаций и отслеживание соответствия этим требованиям на всех этапах разработки.

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

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

Согласно работе Парнаса Д.Л. [17] спецификации должны :

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

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

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

- выражаться в терминах, обычно используемых пользователем и реализатором.

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

Для написания формальных спецификаций используются специальные языки. Обзор методов и описание требований к универсальному языку спецификаций даны в работах [18] и [19]. Предлагаемые различными авторами языки [17,20,61] , которые используются в практических разработках, не имеют пока инструментальной поддержки.

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

1. Пакет прикладных программ АРАС (Алгоритмы решения алгебраических систем) [21, 35] . Разработан в Институте Кибернетики АН УССР им. В.М.Глушкова.

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

Входными данными для работы пакета АРАС являются: исходная матрица и точность задания ее элементов, правые части и точность их задания, требуемая точность решения и некоторые дополнительные сведения о матрице, например, симметричность и т.д.

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

Основным языком пакета является Фортран-1У. Режим работы -пакетный.

Пакет АРАС включает библиотеку модулей вычислительных алгоритмов, библиотеку системных модулей и архив. Программные модули объединены управляющей программой, которая анализирует заданную систему уравнений (тип, размерность, точность исходных данных) и выбирает наиболее подходящий метод ее решения [21].

О недостатках пакета АРАС трудно судить, поскольку ни тексты программных модулей функционального наполнения, ни их спецификации не опубликованы. Это является серьезным препятствием для практического использования пакета.

2. Пакет для решения систем линейных уравнений с разреженными матрицами [22].

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

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

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

3. Пакет ] для решения систем линейных уравнений с матрицами различного вида.

В пакете ZI/VE^CKш^ото использован пакет 3/А£( Scrs/s tmeaz. (Z^egza ¿¡¿¿ßzat/faze ) [68], реализующий основные операции линейной алгебры. Пакет ZZ/Vßlflc распространяется с версиями подпрограмм пакета SIAS, составленными на стандартном Фортране. Однако для конкретной вычислительной системы их можно заменить версиями подпрограмм на соответствующем машинном языке и за счет этого повысить эффективность работы пакета.

4. Пакет EZSPACK [69, 70] предназначен для решения полной, частичной и обобщенной проблемы собственных значений для широкого класса матриц.

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

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

J'l = SSL при решении: стандартной задачи на собственные значения А и по аналогичным зависимостям для других постановок задач.

Здесь А/ - порядок матрицы А; - относительная машинная точность.

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

1) если1 то считается, что программа работает удовлетворительно ;

2) если -/¿^уМ¿-/¿X? % то работа с программой должна осуществляться осторожно и необходимо выполнить дальнейшее исследование для анализа ошибок;

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

Следует отметить, что вычисление описанной выше оценки не решает вопроса о достоверности полученного решения, так как неудовлетворительное значение коэффицента/^ может быть обусловлено ошибками в программе, плохой обусловленностью исходной матрицы к проблеме собственных значений или к проблеме обращения, а также ошибками в исходных данных. Таким образом, получив плохую оценку// , пользователь не имеет информации о том, что необходимо делать, чтобы исправить положение: диагностика критической ситуации получается неполной, а поэтому бесполезной. Выяснить причину неудовлетворительного значения jit может помочь апостериорная оценка вычисленного решения, которая, однако, в пакете fZS/MlX не вычисляется.

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

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

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

5. Библиотека Численного анализа МГУ [23]. В части решения задач на собственные значения данный пакет базируется на функциональном наполнении выше описанного пакета HZSPA&*

На базе Библиотеки Численного анализа МГУ создан пакет с более развитыми системными возможностями £IG£N [24] для решения некоторых задач на собственные значения для различных классов матриц. Средством общения пользователей с пакетом является проблемно- ориентированный язык простой стркутуры, который доступен для использования в рамках языка Фортран в режиме интерпретации.

Описание программных модулей и их тексты не опубликованы.

Для решения задач линейной алгебры кроме перечисленных ППП могут быть использованы программы библиотек $$Р {Sczeati/iC ZuStoatine Package ) [25] и I Pi SI {^nteraational Matke/natic and Statistic LiSrariee )[78]. Первая из них является совокупностью программ, реализующих наиболее часто встречающиеся в приложениях методы численного анализа. Библиотека IMBL в числе других включает программы для решения задач на собственные значения, которые являются прямым переводом на Фортран некоторых программ Справочника [27] .

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

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

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

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

При разработке предлагаемого в диссертационной работе ППП СОЗНАМ ( Собственные значения матриц) для решения задач на собственные значения используется технология, предполагающая выполнение двух этапов :

1) определение требований к ППП в целом и к отдельным компонентам его функционального наполнения и фиксация их в виде формальных спецификаций. В качестве языка спецификаций используется язык, описанный в работе [20] ;

2) реализация программных модулей по их спецификациям программирование, отладка и тестирование каждого модуля и комплексная отладка).

Диссертация содержит 4 главы и приложение.

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

Для решения указанной задачи в состав функционального наполнения ППП включены подпрограммы апостериорной оценки вычисленного приближенного решения и подпрограммы уточнения полученных результатов. Порядок проведения расчета зависит от постановки задачи и от конкретной матрицы. Методы, используемые для создания функционального наполнения разрабатываемого ППП СОЗНАМ, выбраны на основе сравнительного анализа численных методов решения алгебраической проблемы собственных значений, проведенного в главе I. Рассматриваются уровневая структура и состав функционального наполнения пакета.

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

Во второй главе рассматриваются формальные спецификации базового уровня функционального наполнения ППП.

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

Дается краткое описание используемого языка спецификаций. Одной из особенностей этого языка является выделение понятий модуля ( набор взаимосвязанных входов) и пакета ( набор модулей и других пакетов). Функциональное наполнение ППП СОЗНАМ составляет пакет в смысле языка спецификаций. Приводятся формальные спецификации одной из компонент пакета, а именно, пакета СИМПР0БЛ СЗН для решения проблемы собственных значений для действительных симметричных матриц.

Конкретную подпрограмму, реализующую процедуру или функцию по ее спецификации из описания пакета, разрешается включать в состав функционального наполнения ППП только в том случае, когда выполняются все условия, описанные в разделах ИСКЛСИТУАЦШ ( некорректное обращение к модулю), ЭФФЕКТ ( производимые модулем действия) и ОГРАНИЧЕНИЯ ( дополнительные ограничения на реализацию подпрограммы относительно необходимого объема оперативной памяти ( в байтах) и числа " медленных" операций, например, извлечения квадратного корня, деления и др.).

Третья глава посвящена организации работы с ППП СОЗНАМ пользователей с различной профессиональной и программистской подготовкой. Возможность такого обслуживания обеспечивается уров-невой структурой функционального наполнения пакета.

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

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

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

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

Применение пакета СОЗНАМ позволило более точно определить спектр собственных частот для некоторых марок тракторов и исследовать влияние реактивности системы. Полученные результаты согласуются с данными полевых испытаний.

В приложении приведены:

- тексты программ и результаты тестовых расчетов вычисления всех собственных значений и собственных векторов действительной верхней матрицы Хессенберга. На примере отдельной собственной пары ( собственное значение и соответствующий ему собственный вектор) показано использование различных численных методов для оценки погрешности вычисления решения и его уточнения ;

- текст подпрограммы второго уровня для решения полной проблемы собственных значений для действительной симметричной матрицы ;

- текст программы и результат расчета форм свободных колебаний и собственных частот динамической системы трансмиссии одного из тракторов.

Новыми результатами в данной работе являются :

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

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

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

На защиту выносятся :

1. Пакет прикладных программ СОЗНАМ, предназначенный для решения с гарантированной точностью проблемы собственных значений для различных классов матриц. Пакет реализован на языке Фортран в ОС ЕС ЭВМ.

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

3. Алгоритм точного вычисления скалярного произведения на ЭВМ с плавающей запятой, который позволяет получить результат, отличающийся от точного на ошибку одного округления, связанного с его представлением в ЭВМ.

4. Программное обеспечение пакета СОЗНАМ. Уровневая структура функционального наполнения пакета позволяет реализовать языковые интерфейсы, ориентированные на различные классы пользователей и режимы работы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Теплякова, Татьяна Александровна

Основные результаты диссертации :

1. Разработан ШШ СОЗНАМ, предназначенный для решения с гарантированной точностью полной, частичной и обобщенной проблемы собственных значений для широкого класса матриц.

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

Пакет реализован на Фортране - 1У в ОС ЕС.

2. Разработано информационное наполнение пакета СОЗНАМ. Его основной компонентой являются формальные спецификации программных модулей функционального наполнения. Наличие формальных спецификаций и исходных текстов программ позволяет полностью из использовать возможности пакета, делает его открытым для модификации и включения новых модулей функционального наполнения, облегчает переход на использование друтого языка программирования, в частности, на язык ассемблера для повышения эффективности программ на конкретной вычислительной технике.

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

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

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

Разработанный ППП СОЗНАМ внедрен в НПО НАТИ и внедряется в МГУ.

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

ЗАКЛЮЧЕНИЕ

Результаты диссертации опубликованы в 6 статьях [54 - 59] и были представлены на :

- УШ Всесоюзном семинаре по комплексам программ математической физики ( г. Ташкент, 20-23 сентября 1983 г.) ;

- научном семинаре отдела Вычислительной математики АН СССР под рук. Воеводина В.В. ( январь 1984 г.) ;

- семинаре рабочей группы ГКНТ СССР по языку программирования АДА ( март 1984 г.) ;

- конференциях молодых ученых Московского авиационного института ( 1982, 1983 гг.) ;

- научном семинаре кафедры Вычислительной математики и программирования Московского авиационного института ( 1982, 1984 гг.).

Список литературы диссертационного исследования кандидат физико-математических наук Теплякова, Татьяна Александровна, 1984 год

1. Ильин В.П. Вопросы технологии пакетов программ для задач математической физики. - В кн.: Разработка ШШ. Новосибирск: Наука, 1982, с. 1.3-I29.

2. Башмаков И.А., Бесфамильный М.С. Принципы построения ППП. Научн. тр./ Московский энергетический институт, 1972, вып. 118. Применение и использование вычислительных машин, с. 27-34.

3. Карпов В.Я., Корягин Д.А., Самарский A.A. Принципы разработки пакетов прикладных программ для задач математической физики. SBM и Ш, 1978, & 2, с. 458-467.

4. Ершов А.П., Ильин В.П. Пакеты программ технология решения прикладных задач. Новосибирск, 1979. - 22 с. ; - (Препринт/ АН СССР, Сиб. отд-ие, ВЦ; 121 ).

5. Фатеев А.Е., Ройтман А.И., Фатеева Т.П. Прикладные программы в системе МО ЕС ЭВМ. М.: Статистика, 1976.

6. Райе Дж. Матричные вычисления и математическое обеспечение: Пер. с англ. М.: Мир, 1984. - 264 с.

7. Воеводин В.В. Вычислительные основы линейной алгебры. -М.: Наука, 1977. 303 с.

8. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М.: Наука, 1970, 564 с.

9. Бежанова М.М. Входные языки ППП. Новосибирск, 1979. -30 с. ; - ( Препринт/ АН СССР, Сиб. отд-ие, ВЦ; 361 ).

10. Бежанова М.М. Пакеты прикладных программ. Новосибирск: НГУ, 1983. - 73 с.

11. Перроне А. Модульная система конечных элементов /¿ODÜlEfr В кн.: Вычислительные методы в математической физике, геофизикеи оптимальном управлении. Новосибирск: Наука, 1978, с. 160-175.

12. Соловьева Л.А. Технология программирования и пакеты прикладных программ. В кн.: Структура и организация ППП. Новосибирск, 1983, с. 159-189.

13. Яненко H.H., Фомин В.М. и др. Современное состояние, пути дальнейшего развития разработки пакетов и архитектура системы " ИСТОК" для организации, эксплуатации ППП. Сб.: Автоматизированные системы вычислений. Новосибирск, ИТПМ СО АН СССР, 1981, с. 3-79.

14. Фуксман A.A. Технологические аспекты создания программных систем. М.: Статистика, 1979. - 184 с.

15. Бежанова М.М. Проектные спецификации пакетов программ.-Новосибирск, 1980. 30 с. ; - ( Препринт/ АН СССР, Сиб. отд-ие, ВЦ ; 221 ).

16. Росс Д.Т. Качество начинается с определения требований.-В кн.: Создание качественного программного обеспечения. Труды рабочей конференции по обработке информации. Т.П. Новосибирск, 1978, с. 132-134.

17. Парнас Д.Л. Метод спецификаций модулей программного обеспечения с примерами. В кн.: Данные в языках программирования. Абстракция и типология. - М.: Мир, 1982, с. 9-24.

18. Агафонов В.Н. О принципах практического универсального языка спецификаций. В кн.: Синтез, тестирование и отладка программ. Тез. докл. Всесоюзн. научн. конф. Рига, 1981, с. 4-5.

19. Лисков Б., Зилес С. Методы спецификации, используемые для абстракции данных. В кн.: Данные в языках программирования. Абстракция и типология. М.: Мир, 1982, с. 91-122.

20. Гайсарян С.С., Чернышев Л.Н. К вопросу о средствах формального описания программных модулей. Моск. авиац. ин-т, М., 1982, 28 е., Рукопись деп. в ВИНИТИ, 21.09.82, № 491482 Деп.

21. Пакет программ для решения систем линейных алгебраических уравнений на ЕС ЭВМ. / Молчанов И.Н., Зубатенко B.C., Нико-ленко Л.Д., Яковлев М.Ф. Киев, 1982. - 39 с. ; - (Препринт/

22. АН УССР, Ин-т кибернетики им. В.М.Глушкова, 82-22 ).

23. Еремин А.Ю., Марьяшкин Н.Я. Пакет программ SPARSE для решения систем линейных уравнений с разреженными матрицами.-М., ВЦ АН СССР, 1978.

24. Библиотека численного анализа НИВЦ МГУ. М., МГУ,1979.

25. Борисов BJtf. Метод реализации системных компонент над библиотеками программ. Диссертация на соискание ученой степени кандидата физ. мат. наук ( 01.01.10 ). - М., 1980. - 104 с.

26. Математическое обеспечение ЕС ЭВМ. Пакет научных программ. ч.1, Ин-т математики АН БССР, Минск, 1973. 226 с.

27. Парлетт Б. Симметричная проблема собственных значений. Численные методы: Пер. с англ. М.: Мир, 1983. - 384 с.

28. Уилкинсон Дж.Х., Райнш С. Справочник алгоритмов на языке Алгол. Линейная алгебра: Пер. с англ. М.: Машиностроение, 1976. - 390 с.

29. Фадеев Д.К., Фадцева В.Н. Вычислительные методы линейной алгебры. М.-Л.: Физматгиз, 1963. - 734 с.

30. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980. - 279 с.

31. Калиткин H.H. Численные методы. М.: Наука, 1978. -512 с.

32. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. -М.: Наука, 1984. 320 с.

33. Пакеты прикладных программ. Методы, разработки. Новосибирск: Наука. Сибирское отд-ие, 1981. - 223 с.

34. Разработка пакетов прикладных программ. Новосибирск: Наука. Сибирское отд-ие, 1982. - 248 с.

35. Яненко H.H., Карначук В.И., Рычков А.Д., Фомин В.М. ШШ математической физики и механики сплошной средн. Сб.: Комплексы программ математической физики. Новосибирск, 1982, с. 3-15.

36. Молчанов И.Н. Пакет задач линейной алгебры. Киев, ИК АН УССР, 1979.

37. Майерс Г. Надежность программного обеспечения. М.: Мир, 1980. - 360 с.

38. Шараев Д.Я. Основные принципы построения ШШ. В кн.: Труды 1У Всесоюзного семинара по комплексам программ математической физики. Новосибирск, 1976, с. I46-I5I.

39. Форд Б. Эволюция подхода к проблеме переноса программного обеспечения. В кн.: Мобильность программного обеспечения. M., 1980, с. 272-294.

40. Фаддева В.Н., Копотилова Л.Ю. Вычислительные методы линейной алгебры. Набор матриц для тестирования: Материалы по математическому обеспечению ЭВМ. чД-З, Ленинград, 1982.

41. Воеводин В.В., Арушанян О.Б. Структура и организация Библиотеки численного анализа НИВЦ MIT. Сб.: Численный анализ на Фортране. Вычислительные методы и инструментальные системы. М.: Изд-во Моск. ун-та, 1979, с. 73-83.

42. Брановицкий В.И., Довгялло А.Н., Никитин А.И., Стог-ний A.A. Диалог человека е ЭВМ: основные понятия и определения.-УС и M, 1978, № 4, с. 3-6.

43. Глушков В.М. Диалог с вычислительной машиной, современные возможности и перспективы. УС и M, 1974, Л2, с. 12-15.

44. Заболоцкий Д.Е., Карпенко С.Н., Кузин С.Т. и др. Принципы построения и архитектуры ШШ. УС и M, 1978,Щ, с. 8-14.

45. Создание качественного программного обеспечения/п.р. Ершова А.П. . /. Новосибирск, 1978.

46. Коллатц Л. Задачи на собственные значения с техническими приложениями. М.: Мир, 1968.

47. Пакеты прикладных программ: Вычислительный эксперимент. сб.статей. / АН СССР, ВЦ/. М.: Наука, 1983. - 147 с.

48. Молчанов И.Н. О некоторых требованиях к вычислительным проблемам линейной алгебры. SBM и МФ, 1980, 20, № 3, с. 550 -561.

49. Йенсен К., Вирт Н. Паскаль. М.: Финансы и статистика, 1982. - 159 с.

50. Язык программирования АДА ( предварительное описание). Пер. с англ. Курочкина В.М. и Подшивалова Д.В. М.: Финансы и статистика, 1981, 190 с.

51. Демерс А., Донахью Дж., Тейтельбаум Р., Уильяме Дж. Инкапсулированные типы данных и полиморфные процедуры. В кн.: Данные в языках программирования. Абстракция и типология. - М.: Мир, с. 214-242. .

52. Агафонов В.Н. Типы и абстракции данных в языках программирования. Абстракция и типология.- М.: Мир,1982, с. 265-327.

53. Комплексы программ математической физики ( материалы УП Всесоюзного семинара по комплексам программ математической физики). Новосибирск, 1982. - 325 с.

54. Теплякова Т.А. Пакет прикладных программ для решения алгебраической проблемы собственных значений. Сб.: Комплексы программ математической физики. Новосибирск, 1984, с. 310.

55. Гайсарян С.С., Теплякова Т.А. Об одном численном алгоритме уточнения спектра собственных значений матрицы. } Сб. научн. трудов. М.: МАИ, 1984, с. 11-15 ( в печати).

56. Теплякова Т.А. Функциональное наполнение пакета программ для решения алгебраической проблемы собственных значений.-Моск. авиац. ин-т, М., 1984, II е., Рукопись деп. в ВИНИТИ 05.06.84.

57. Гайсарян С.С., Теплякова Т.А. Описание пакета подпрограмм для решения симметричной алгебраической проблемы собственных значений. Моск. авиац. ин-т, М., 1983, 14 е., Рукопись деп. в ВИНИТИ 24.06.83, J& 3447-83 Деп.

58. Гайсарян С.С., Ластовецкий А.Л., Теплякова Т.А. Алгоритм точного вычисления скалярного произведения на ЭВМ с плавающей запятой. Моск. авиац. ин-т, М., 1984, 9с., Рукопись деп. в ВИНИТИ 05.06.84, № 3630-84 Деп.

59. UNPACK- User's Guide PhiCadaipAia, SIAM, /9?9.368р.в*. 3e¿cÁCer JTU, ¿2, PeéjScA. S/AN-42 so/éurara specification- anc¿ des¿p/t Ca/tpuape. I£££ Гг. S£m/W,&-/0,*/2,./>./55'/02.

60. Sß. ía¿¿rs¿?/z Г./. S/.AS -3as¿? /Li/геаА ¿2/peâAa 5a^ao¿//zvzé>s. Jêé Pao/>¿/3A¿szo/z /aáúa¿r/¿?7¿/, /025. 60. S/TzzéA 3.2y 3¿?¿/¿<Pj:H,2)o/7¿raAAaJ:J.) e.c.

61. Па/AÏ ce fige/isysAp/Tz. £auAz/zé>ss EISPACK

62. Yama/rzoAo Г Aaaûa 6ú¿z/zds /ûa ¿û/npz/ééd. eigp?z¿7¿zA¿/ás a/z¿2 eiçe&fipefo/s. A/u/n. /тг&АА., 708O, v. 34, /9Р.73. \Aï AAZ/zsû/i J.M £-¿&oa0¿/s ¿ea/zdsfor computed ¿íge/tsysáp/TzSj £ о/при ¿.J., /S>6/y v. л/3, p. 23û~24i.

63. Sy/K/n- f/.Z, "W-iteitt-so/L J.tf. j£é>a£ts£zû prrar Sounds /or a sz/np¿ú fzgé/zaa^ae a/zaf t/s associated, ezpe/zzr^otoA. Ци/п. Maúi., /P8¿?yv.35, ss 2, p. 726.

64. VarraA J.M Л-içoroc/s i?7za¿?Áz7z¿? Soalzafs /or e¿^á/¿s¿/sés/7t а/ a ¿?é/2ara¿f oa/7z/>¿?¿3i7?a¿A2ce. -fflaà/i. £о/пр., v.22, * 793-60/,

65. AaAafi V, J>ar¿?á¿¿ AM., Лаку £esz¿/zza¿f

66. So¿//zds -ZZZ ¿^OS-OXZSK&te £2g?07ZS¿/s2?0/rzs ¿/лок/мгутю:/? /7i¿z/z¿Oés. SIAJV J. /¿ziy^or C2^za¿.,

67. Р82, v. /9 az3, f. 470- 480.

68. HonçarraJJ, Tftoâer £.3., 1/'z^ízzso/zJ'.//. I-mproir-inç ¿Ae aoooraoz/ о/ ¿м/npafeaf ozyezz^a¿f¿/es a/id 51 A M -T. 7Zu/7L.¿Z7z¿rf., /¿>84, v.2ú, и//, 23-^5.

69. I77SL Uблок/ /,2,3 /¿e/oreszoe Жаша^ 7Ы £c7zéïorzj /Р7779. ¿i'sÁocr 3., S/Lz/<2?ûr A. TZ^s/raré/on7Z ecA&TZ-ZSTrtS -ñt ££¿7 ¿'¿?/7Z/>¿¿¿Or¿¿¿?/Z

70. Groa/) fosn/rz. /077, v. 20,*/8, p. SS4-Sá?.

71. M ¿JOSAS Aózzazzoí J. Sz/m/netAtc znatAz¿?esri¿í faâscaised eip£?z¿r¿2f¿jps &rzd é>z¿/ézz¿r<pc¿úaj. M a M. /Пар. &32, v. 55p „2, p. /Об-fff.