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

На правах рукописи

КИНЦЕЛЬ Дмитрий Александрович

РАЗРАБОТКА МЕТОДОВ И КОМПЛЕКСА ПРОГРАММ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ ДЛЯ РЕШЕНИЯ ПЛОХО ОБУСЛОВЛЕННЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Саратов 2004

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

Научный руководитель:

кандидат технических наук, профессор Каримов Равиль Нургалиевич

Официальные оппоненты: - доктор физико-математических наук,

профессор Губатенко Валерий Петрович

Защита состоится «03» марта 2004 года в 14.00 часов на заседании диссертационного совета Д 212.242.08 при Саратовском государственном техническом университете по адресу: 410054, г. Саратов, ул. Политехническая 77, Саратовский государственный технический университет, корп. 1, ауд. 319.

С диссертацией можно ознакомиться в научно-технической библиотеке Саратовского государственного технического университета.

кандидат технических наук,

доцент Иващенко Владимир Андреевич

Ведущая организация:

Саратовский государственный университет (г. Саратов)

Автореферат разослан февраля 2004 г.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Чтобы избежать ошибок, связанных с машинным округлением, необходимо использовать арифметические системы, которые свободны от ошибок округления. Примером таких систем являются одномодульные системы вычетов. Общая идея состоит в том, что рациональные числа переводятся во множество целых. Все действия производятся во множестве целых чисел, а результаты приводятся по модулю т. Конечные результаты с помощью обратного отображения переводятся из множества целых чисел во множество рациональных. Вычисления, основанные на таких системах, называются «безошибочными», или их эквивалентом — «точными вычислениями» (exact computation). В связи с этим актуальной является задача исследования числовых систем, которые позволяют точно находить решения плохо обусловленных задач на ЭВМ.

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

Для достижения поставленной цели в работе сформулированы следующие задачи:

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

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

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

Научную новизну диссертационной работы составляют результаты теоретических и экспериментальных исследований:

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

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

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

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

Практическую значимость имеют:

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

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

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

-материалы работы использованы в учебном процессе для подготовки студентов специальности 220200 «Автоматизированные системы обработки информации и управления» в Саратовском государственном техническом университете.

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

- комбинированный метод для решения плохо обусловленных систем линейных алгебраических уравнений, сочетающий безошибочные вычисления и обычную конечно-разрядную арифметику ЭВМ;

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

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

Апробация работы. Основные теоретические положения и практические результаты работы обсуждались и докладывались на: II Всероссийской научно-практической конференции «Современные технологии в обучении и производстве», (Камышин, 2003), XVI Международной научной конференции «Математические методы в технике и технологиях "ММТТ-ДОН"», (Ростов-на-Дону, 2003), III Всероссийской научно-технической

конференции «Проблемы информатики в образовании, управлении, экономике и технике» (ВК-73-93), (Пенза, 2003).

Публикации. По теме диссертации опубликовано 6 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы из 141 наименования; содержит 2 рисунка, 6 таблиц, 3 приложения, комплекс программ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Вторая глава посвящена обзору применяемых в настоящее время методов решения плохо обусловленных задач, анализу их достоинств и недостатков. Любые численные методы, применяемые для нахождения решения на ЭВМ, использующей для расчета обычную конечно-разрядную арифметику, подвержены проблеме ошибок машинного округления. Приведена сравнительная оценка методов: Гаусса (исключения), его модификаций: итеративного метода Гаусса и метода Холецкого, UD-разложения, сингулярного разложения, полиномов Чебышева. Изложены характерные особенности данных методов, алгоритмы реализаций методов на ЭВМ, результаты решения задач с их помощью, указываются погрешности нахождения оценок.

В третьей главе изложена теоретическая часть одного из видов целочисленной арифметики — одномодульной системы вычетов и результаты диссертационной работы. Если выполняются операции с целыми числами, а результат приводится по модулю т, то такая арифметическая система называется одномодульной арифметикой вычетов (single-modulus residue

arithmetic). Целое число т>\ при этом называется модулем арифметической системы.

В одномодульной арифметике вычетов каждое целое be. I, где I -множество положительных чисел, отображается на целое в конечном множестве

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

Если тя=7, то 58 eR2, поскольку

¡58|?=2.

(3)

При этом число 2 называется наименьшим неотрицательным вычетом числа 58 по модулю 7. Считается, что число 58 является приведенным к 2 по модулю 7 или числа 58 и 2 сравнимы по модулю 7.

Пусть (^-множество рациональных чисел, которые допускают отображение в 1'т

§ = {а/Ь:(Ь,т) = 1}, (4)

где выражение (Ь, т) = 1 обозначает, что наибольший делитель чисел Ъ и т равняется 1. Рекомендуется выбирать число т простым, что гарантирует существование обратного элемента к целому числу Ъ в конечном коммутативном кольце

Каждое число к е 1т является образом бесконечного множества элементов из которое обозначается . Следовательно, для по определению

Q* ={a/beQ: \а/Ъ\т=к}.

Отсюда получаем, что

Q=UQ*.

(5)

(6)

Например, множество Q2 состоит из элементов вида а/Ь, при (Ь, т) =1, для которых \а!Ь\т=2. Очевидно, что м н о е пе-

ресекаются. Отображение НвГ-О-:►!»( не является взаимно однозначным, так как каждое целое является образом бесконечного подмножества

рациональных чисел. Существует способ выбора одного элемента из

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

Конечное подмножество множества ф, задаваемое следующим образом:

Рд, = {в/6е0:(в,6) = 1> 0<И<ЛГ, 0<|6|^ЛГ}, (7)

где N > О - целое число, называется множеством дробей Фарея порядка N. Если N- максимальное целое число, для которого выполнено неравенство +1 < т, и если содержит некоторую дробь Фарея х = а/Ь порядка N, то эта дробь является единственной. Отсюда следует, что число элементов во множестве Е^ меньше т. Не каждый из классов <Зо>Р1>---»От-1 может содержать элемент но если некоторый класс все же содержит дробь Фарея порядка N, то в этом классе такая дробь единственная. Обозначим

1т={\а1Ъ\т: а/ЬеГ^} (8)

образ множества дробей Фарея порядка N при отображении |-|т:<}— Отображение является взаимно однозначным, следователь-

но, существует обратное отображение. Для иллюстрации рассмотрим пример такого соответствия. Пусть т = 23, тогда N = 3. В табл.1 в нижней строке записаны все дроби Фарея третьего порядка, в верхней - их образы при отображении

Таблица 1

Дроби Фарея третьего порядка для т = 23

I 0 1 2 3 7 8 9 10 11 12 13 14 15 16 20 21 22

р 0 1 2 3 -2/3 1/3 ... -3/2 -1/2 1/2 3/2 -1/3 2/3 ... -3 -2 -1

Многоточие в табл. 1 на месте чисел 4, 5, 6, 9, 14, 17,18, 19 означает, что 123 с12з, эти числа не входят 123т . е. не являются образами каких-либо дробей Фарея третьего порядка.

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

Расширенный алгоритм Евклида.

1. Выбираем начальную матрицу

где а и с - положительные числа, а Ь и й - произвольные целые числа.

2. Для пока определяем как частное и как неотрицательный остаток при делении Тогда

3. Аналогично определяем

4. Завершаем вычисления при аи+1 = 0. В результате получаем

Вычисления по этому алгоритму удобно оформлять в табличной форме. Ниже приведены примеры прямого и обратного отображений. Осуществим отображение —Пусть от =23, N=3 и 5/12. Тогда вычисления с начальной матрицей

Г23 О" 12 5_

приводят к результатам, представленным в табл. 2.

Таблица 2

Таким образом, получаем

(12)

Теперь переведем целое 145е1бл в дробь, принадлежащую Г|7. Начальная матрица имеет вид

631 о 145 1

Результаты вычислений приведены ниже в табл. 3.

Алгоритм порождает конечное множество дробей, в данном примере их шесть

Из этих дробей выделена дробь -8/13, так как именно она является единственной дробью Фарея порядка 17.

При выборе большого целого т множество ^ дробей Фарея порядка N будет достаточно представительным. Если для некоторой задачи все ее данные и ответы содержатся в , то можно перевести все операнды из Руу в 1Я, выполнить все операции на множестве 1т , а затем перевести целые результаты в . Если некоторые из ответов задачи не принадлежат Е^, тогда полученные результаты будут неверными, но они будут сравнимы по модулю т с правильными ответами. Такая ситуация называется псевдопереполнением. Если результат промежуточных вычислений не принадлежит V// , а конечный — принадлежит , то результат всех вычислений оказывается верным. Проблема псевдопереполнения возникает тогда, когда в конечном множестве дробей, порожденных алгоритмом Евклида, отсутствует дробь Фарея Nго порядка.

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

Таблица 3

Пример обратного отображения

631 о 145 1

4 51 -4 2 43 9

1 8 -13

5 3 74

2 2 -161 1 1 235

2 0 -631

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

у = а0 + ахх+а2х2 +...+ архр.

Из-за очень плохой обусловленности СНУ на практике их удается решать для параболических регрессий невысокого порядка, обычно не выше четвертого. Для примера возьмем уравнение параболической регрессии шестого порядка

>- = 170.04-4.0428•* + 2.4663-х2 -0.4325-д:3 + 0.03064 х4 -

и вычислим значения у для х =0, 1, ..., 49. После этого попытаемся для этих 50 пар значений найти уравнение многочлена 6-го порядка, используя обычную конечно-разрядную арифметику ЭВМ. Для всех вычислений использовался тип числа «Extended», имеющий 19-20 десятичных значащих разрядов. Решение СНУ методом Гаусса имеет вид

а0= 170.0399, а, =-4.0428, аг = 2.4663, а3= -0.4325,

а4 = 0.03064, а5 = -0.000952, а6 = 0.0000108.

Таким образом, получено точное решение. Теперь повторим процесс решения уравнения для других 50 значений у при х = 50, 51, ..., 99. В этом случае имеем

а0= 169.8090, л, =-4.0232, аг = 2.4656,- а3=-0.4325,

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

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

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

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

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

чисел Уц), 1 = 1...«, где п- количество точек, по которым идет вычисление, переходим ко второй паре (Х21>У2/)- Здесь

У2, =Уи-<*РхР. х21~х11- По новым парам (л^^-Уг/) строим матрицу СНУ порядкар-1, и находим значение коэффициента а^. Переходим к

следующим парам значений

Итеративную процедуру можно завершить, когда матрица СНУ будет третьего порядка, так как в этом случае погрешности округления практически отсутствуют.

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

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

а0= 4251/25 = 170.04, л, = -10107/2500 =-4.0428,

а2 = 24663/10000 =2.4663, д3= -173/400 =0.4325,

а4 = 383/12500 =0.03064, а, = -24313/17853 = -1.3618439,

Найденные значения коэффициентов с помощью модульной

арифметики соответственно равны -24313/17853 и -27940/37457, эти решения не являются верными в математическом смысле, но они сравнимы с верными по модулю т. Оценки коэффициентов для данного примера, полученные с помощью различных методов, приведены в табл. 4,5, 6.

Таблица 4

Оценки параболы для случая, когда х изменяется от 0 до 49 '

Методы а0 а\ а2 аЗ <34 <35 аб

Истинные значения 170.04 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Прямое обращение 170.0400 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Гаусса 170.0400 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Итерат. Гаусса 170.0400 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Холецкий 170.0400 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Сингуляр. 170.0400 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Чебышева 170.0400 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Модульная 4251/25 -10107/2500 24663/10000 -173/400 383/12500 -24313/17853 -27940/37457

Комбинир. 4251/25 -10107/2500 24663/10000 -173/400 383/12500 -119/125000 27/2500000

Таблица 5

Оценки параболы для случая, когда х изменяется от 50 до 99

Методы аО а\ а 2 аЗ аЛ а5 аб

Истинные значения 170.04 -4.0428 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Прямое обращение -544.081 30.3086 1.9664 -0.42887 0.03062 -0.000952 0 0000108

Гаусса 169.8089 -4.0232 2.4656 -0,4325 0.03064 -0.000952 0.0000108

Итерат. Гаусса 169.8090 ' -4.0233 2.4656 -0.4325 0.03064 -0 000952 0.0000108

Холецкий 143.0915 -1.7572 2.3864 -0.4310 0.03062 -0.000952 0.0000108

Сингуляр. -163.645 24.2752 1.4761 -0.4142 0.03045 -0.000951 0.0000108

Чебышева 170.1024 -4.0481 2.4665 -0.4325 0.03064 -0.000952 0.0000108

Модульная 4251/25 -10107/2500 24663/10000 -173/400 383/12500 -24313/17853 -27940/37457

Комбинир. 4251/25 -10107/2500 24663/10000 -173/400 383/12500 -119/125000 27/2500000

Таблица 6

Оценки параболы для случая, когда х изменяется от 100 до 149

Методы аО а\ а2 аЪ аА а5 аб ■

Истинные значения 170.04 -0.4028 2.4663 -0.4325 0.03064 -0.000952 0.0000108

Прямое обращение ■4645374 56612.13 -140.055 -0.90758 0.03017 -0.000937 0.0000108

Гаусса 3.7973 4.1408 2 2991 -0 4307 0.03062 -0.000952 0.0000108

Итерат. Гаусса 3.3504 4.1591 2.2987 -0.4307 0.03062 -0.000952 0.0000108

Холецкий 1П003 -5445.74 113.37 -1.63348 0.03793 -0.000976 0.0000108

Сингуляр. 85.639 -0.1675 2.3928 -0.4318 0.03064 -0.000952 0.0000108

Чебышева 218.255 -6.4183 2.5149 -0.4330 0.03064 -0.000952 0.0000108

Модульная 4251/25 -10107/2500 24663/10000 -173/400 383/12500 -24313/17853 -27940/37457

Комбинир 4251/25 -10107/2500 24663/10000 -173/400 383/12500 -119/125000 27/2500000

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

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

Основные положения комбинированного метода.

1. Комбинированный метод рекомендуется для следующих методов: рекурсивных; имеющих большое количество промежуточных вычислений;

для методов, в исходных данных которых отношение минимального и максимального чисел составляет несколько порядков.

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

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

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

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

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

2. Используется итеративный метод Гаусса для нахождения значения коэффициента ар.

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

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

очень малой.

4. Заменяется значение

5. Используется второй шаг итеративного метода: от начальных пар чисел переходим ко второй паре Здесь

6. По новым парам (хг^-Уг/) строится матрица СНУ порядкар - 1. Находится значение коэффициента Определяется ее порядок и также подбирается из множества наиболее подходящая дробь. Итерацию можно закончить прир = 3, когда ошибки округления практически отсутствуют.

Комбинированный метод в ситуации псевдопереполнения определил верные в математическом смысле значения коэффициентов а5 И Значения, найденные классическим методом Гаусса с использованием одно-модульной арифметики вычетов, в математическом смысле являются неверным решением, но данное решение является верным в одномодульной системе вычетов по модулю т, так как в этой системе по модулю 38967 числа -24313/17853 и -119/125000 равны; также равны в этой системе числа -27940/37457 и 27/2500000.

На рис. 1, 2 приведены графики полиномов, построенных по оценкам, полученным различными методами для случая, когда х изменяется от 100 до 149. Графики полиномов сильно отличаются по диапазону изменения у для лучшего и худшего методов, поэтому приведены два рисунка: на рис. 1 приведены методы, дающие наилучшие результаты; на рис. 2 - наихудшие.

О 5 10 х 15 20 25 30

Рис. 1. Графики оценок в диапазоне 0-30

Обозначения кривых на рисунках: уа - кривая,соответствующая истинным значениям, полностью совпадает с решением, полученным комбинированным методом;

1Уъ - классический и итеративный методы Гаусса; ус - сингулярное разложение; Уа - полиномы Чебышева;

уе - метод Холецкого;

Уу - прямое обращение матрицы,

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

-1-10*

-2-10'

-3-10'

-4-10'

Л

\ "—^ Уа

- -

-—■ 1 1 \ 1 | 1

5 10 I 15 20 25

Рис. 2. Графики оценок в диапазоне 0-30

30

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

Следует выделить два метода, дающих лучшие оценки среди классических методов. Это метод разложения по ортогональным полиномам Че-бышева и метод сингулярного разложения. Немного худшие оценки дают классический и итеративный методы Гаусса. Абсолютно точное решение,

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

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

В заключении сформулированы основные результаты диссертационной работы:

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

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

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

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

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

Основные положения диссертационного исследования отражены в следующих публикациях:

1. Большаков А. А., Каримов Р. Н., Кинцель Д. А. Использование одномодульной системы вычетов для решения плохо обусловленных задач на ЭВМ //Математические методы в технике и технологиях-ММТТ-16: Сб. трудов XVI Междунар. научн. конф.: В 10 т. Т.1. Секция 1/ Под общей ред. B.C. Балакирева. Санкт-Петербург: Изд-во Санкт-Петербургского гос. технолог, ин-та, 2003. - С. 41-43.

2. Каримов Р. Н., Кинцель Д. А. Методы оценивания коэффициентов парабол высоких порядков //Автоматизация и управление в машино- и приборостроении: Межвуз. науч. сб. - Саратов: Сарат. гос. техн. ун-т, 2003. С. 112-115.

3. Кинцель Д. А. Оценивание зависимостей с использованием параболической функции одной переменной //Электротехнические комплексы и силовая электроника. Анализ, синтез, управление: Межвуз. науч. сб. -Саратов: Сарат. гос. техн. ун-т, 2003. С. 48-54.

4. Каримов Р. Н., Кинцель Д. А. Решение плохо обусловленных задач с помощью безошибочных вычислений //Современные технологии в обучении и производстве. Материалы II Всероссийской научно-практической конференции. Камышин, 2003 . Т.2. С. 292-294.

5. Большаков А. А., Кинцель Д. А. Использование модульной арифметики для решения плохо обусловленных задач //Проблемы информатики в образовании, управлении, экономике и технике (ВК-73-93): Сборник статей III Всероссийской научно-технической конференции. - Пенза, 2003. С. 11-15.

6. Большаков А. А., Каримов Р. Н., Кинцель Д. А. Идентификация параболической регрессии с помощью одномодульной арифметики вычетов //Электротехнические комплексы и силовая электроника. Анализ, синтез, управление: Межвуз. науч. сб. - Саратов: Сарат. гос. техн. ун-т, 2001. С. 39-44.

P- 284 t

КИНЦЕЛЬ Дмитрий Александрович

РАЗРАБОТКА МЕТОДОВ И КОМПЛЕКСА ПРОГРАММ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ ДЛЯ РЕШЕНИЯ ПЛОХО ОБУСЛОВЛЕННЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Автореферат

Ответственный за выпуск доц. Н.П. Митяшин Корректор Л.А. Скворцова

Лицензия ИД № 06268 от 14.11.01

Подписано в печать 28.01.04

Бум. тип. Усл.-печл. 1,0

Тираж 100 экз. Заказ 57

Саратовский государственный технический университет 410054 г. Саратов, ул. Политехническая, 77 Копипринтер СГТУ, 410054 г. Саратов, ул. Политехническая, 77

Формат 60x84 1/16 Уч.-изд.л, 1,0 Бесплатно

ВВЕДЕНИЕ.

1. АНАЛИЗ ОШИБОК.

1.1. ОТНОСИТЕЛЬНЫЕ И АБСОЛЮТНЫЕ ОШИБКИ.

1.2. ОШИБКИ СОДЕРЖАЩИЕСЯ В ИСХОДНОЙ ИНФОРМАЦИИ.

1.3. ОШИБКИ ОГРАНИЧЕНИЯ.

1.4. ОШИБКИ ОКРУГЛЕНИЯ.

1.5. УСТОЙЧИВОСТЬ И ОБУСЛОВЛЕННОСТЬ СИСТЕМ НОРМАЛЬНЫХ УРАВНЕНИЙ ЧИСЛО ОБУСЛОВЛЕННОСТИ.

2. МЕТОДЫ ВЫЧИСЛЕНИЙ.

2.1. ИСПОЛЬЗОВАНИЕ ФОРМУЛ КРАМЕРА.

2.2. ПРЯМОЕ ОБРАЩЕНИЕ МАТРИЦЫ.

2.3. МЕТОД ПОСЛЕДОВАТЕЛЬНОГО ИСКЛЮЧЕНИЯ (ГАУССА).

2.4. МЕТОД РАЗЛОЖЕНИЯХОЛЕЦКОГО.

2.5. МЕТОД РАЗЛОЖЕНИЯ ПО СИНГУЛЯРНЫМ ЧИСЛАМ.

2.6. ОЦЕНИВАНИЕ КОЭФФИЦИЕНТОВ С ПОМОЩЬЮ ПОЛИНОМОВ ЧЕБЫШЕВА.

3. РЕШЕНИЕ ЗАДАЧИ НАХОЖДЕНИЯ ПАРАМЕТРОВ ПАРАБОЛИЧЕСКОЙ РЕГРЕССИИ.

3.1. ПОСТАНОВКА И РЕШЕНИЕ ЗАДА ЧИ.

3.2. ОДНОМОДУЛЬНАЯ СИСТЕМА ВЫЧЕТОВ.

3.3. РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА.

3.4. КОМБИНИРОВАННЫЙ МЕТОД РЕШЕНИЯ ЗАДА ЧИ И СРАВНЕНИЕ МЕТОДОВ.

Актуальность исследования. В настоящее время любой инженерный расчет немыслим без использования ЭВМ. С развитием технических возможностей компьютеров соответственно расширяется и область их применения, охватывающая все большую сферу инженерных задач. Существует достаточное количество пакетов прикладных программ, которые широко применяются специалистами, ориентированных на решения как самых общих, так и специализированных инженерных задач [38, 40, 137]. Однако вычисления в машинной арифметике отличаются от арифметики «карандаша и бумаги». В ручных вычислениях промежуточные результаты непосредственно доступны для обозрения, и точность вычислений можно изменить в соответствии с требованием момента [53]. В машинной арифметике каждое число имеет фиксированное количество разрядов, которого в ряде случаев недостаточно для получения приемлемой точности [6]. Также ручные вычисления обычно не бывают длинными, тогда как машинный процесс вычислений может состоять из миллионов шагов [89]. Ничтожно малые ошибки, которыми в коротком вычислении можно было бы пренебречь, накапливаясь в протяженном процессе, могут приводить к разрушительным последствиям. Кроме этого, методы, вполне удовлетворительные для задач малой размерности, могут быть неэффективными для задач больших размерностей этого же типа [39].

Одной из задач, наиболее часто встречающихся в научных вычислениях, - решение системы линейных уравнений [121]. К линейным уравнениям приводят многие приложения [42, 140]. Также линейные уравнения могут возникать и опосредованно, как шаг в решении более сложной проблемы [15, 141]. Системы нелинейных уравнений, решают, используя последовательность линейных приближений, что порождает последовательность линейных систем [34, 88, 136]. При решении краевых задач для дифференциальных уравнений часто ограничиваются поиском решения только в конечном множестве точек, что во многих случаях ведет к системам линейных уравнений [87].

Для целого класса задач, которые относятся к плохо обусловленным, точное решение не может быть получено на компьютере традиционными способами, которые обычно используются в стандартном математическом обеспечении [8]. В этом случае некорректность решения обусловливается архитектурой ЭВМ, формой представления информации, и не зависит, например, от производительности или объема памяти. Любая цифровая ЭВМ является конечной машиной, так как она способна представлять конечное множество чисел. Поэтому в общем случае множество вещественных чисел R, которое является бесконечным, не представимо в компьютере. Точность представления таких чисел на ЭВМ зависит от размера разрядной сетки, используемой для вычислений. По этой причине при решении практически любой реальной задачи на ЭВМ возникают ошибки округления. При решении плохо обусловленных задач такие ошибки могут приводить к катастрофическому искажению результата решения [70].

Чтобы избежать ошибок связанных с машинным округлением в работе предлагается использовать системы, которые свободны от ошибок округления [31]. Примером таких систем являются одномодульные системы вычетов. Общая идея состоит в том, что рациональные числа с помощью метода, основанного на расширенном алгоритме Евклида, переводятся во множество целых чисел \т (прямое отображение). Все действия производятся во множестве целых чисел, а результаты приводятся по модулю т. Конечные результаты с помощью обратного отображения переводятся из множества целых чисел во множество рациональных. Вычисления, основанные на таких системах, называются «безошибочными», или их эквивалентом - «точные вычисления» (exact computation) [31]. Основной проблемой использования схожих систем является проблема взаимно однозначного перевода чисел из одной системы в другую. По причине того, что поле рациональных чисел бесконечно, а количество целых чисел, представимых в компьютере является конечным, возникает проблема однозначного обратного отображения полученного решения в поле рациональных чисел. Для определенного ряда задач, имеющих целочисленное решение, проблемы обратного отображения, не возникает. Но для задач, решение которых надо искать в поле рациональных чисел такая проблема существует.

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

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

Для достижения поставленной цели в работе сформулированы следующие задачи:

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

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

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

Научную новизну диссертационной работы составляют результаты теоретических и экспериментальных исследований:

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

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

Практическую значимость имеют:

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

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

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

- материалы работы использованы в учебном процессе для подготовки специальности 220200 «Автоматизированные системы обработки информации и управления» в Саратовском государственном техническом университете.

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

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

Апробация работы. Основные теоретические положения и практические результаты работы обсуждались и докладывались на: II. Всероссийской научно-практической конференции «Современные технологии в обучении и производстве», 2003 г., г. Камышин, XVI международной научной конференции «Математические методы в технике и технологиях "ММТТ-ДОН"», 2003 г., г. Ростов-на-Дону, III Всероссийской научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (ВК-73-93), 2003 г., г. Пенза.

Публикации. По теме диссертации опубликовано 6 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы из 141 наименования; содержит 2 рисунка, 6 таблиц, 3 приложения, комплекс программ.

4. ЗАКЛЮЧЕНИЕ

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

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

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

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

1. Абрамовиц М., Стиган И. Справочник по специальным функциям. - М.: Наука, 1979.

2. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Основы моделирования и первичная обработка данных. М: Финансы и статистика, 1983.472 с.

3. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Исследование зависимостей. М.: Финансы и статистика, 1985.487 с.

4. Андерсон Т. Статистический анализ временных рядов, М.: Мир, 1975, 760с.

5. Арене X., Лёйтер Ю. Многомерный дисперсионный анализ. Пер. с нем. М.: Финансы и статистика, 1985. 230 с.

6. Афифи А., Эйзенс С. Статистический анализ. Подход с использованием ЭВМ / Пер. с англ. М.:Мир,1982.488с.

7. Ахмед Н., Pao К.Р. Ортогональные преобразования при обработке цифровых сигналов: Пер.с англ. М.:Связь,1980. - 248 с.

8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

9. Балакирев B.C., Володин В.М., Цирлин A.M. Оптимальное управление процессами химической технологии. М.: Химия, 1978. - 383 с.

10. Беллман Р. Ведение в теорию матриц, М.: Наука, 1969, 386 с.

11. Березин И.С., Жидков Н.П. Методы вычислений, в 2-х томах, т.1, т.2., М.: Физматиздат, 1962,464 е., 640 с.

12. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. 448 с.

13. Бокс Дж., Дженкинс Г. Анализ временных рядов. Прогноз и управление. Вып.1,2: Пер.с англ. М.: Мир, 1974. 406с., 197 с.

14. Болдин М.В., Симонова Г.И., Тюрин Ю.Н. Знаковый статистический анализ линейных моделей. М.: Наука, 1997. 288 с.

15. Болч Б., Хуань К.Дж. Многомерные статистические методы для экономики: Пер.с англ. М.: Статистика, 1979. - 317 с.

16. Большаков A.A., Каримов Р.Н. Методы сжатия информации. Саратов, Са-рат. политехи, ин-т, 1991 88с.

17. Боровиков В.П., Боровиков И.П. Статистический анализ и обработка данных в среде Windows. М.: Информационно-издательский дом «Филинь», 1997. 608 с.

18. Васильева Л.Г., Жилейкин Я.М., Осипик Ю.И. Преобразования Фурье и вейвлет-преобразования. Их свойства и применение // Вычислительные методы и программирование, 2001, т. 3, с. 172- 175.

19. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения): — М.: Высш.шк., 2000. 266 с.

20. Виленкин С.Я. Статистическая обработка результатов исследования случайных функций. М.: Энергия, 1979. 320 с.

21. Воеводин В.В., Тыртышников Е.Е. Вычислительные процессы с теплице-выми матрицами, М: Наука, 1987, 320 с.

22. Волгин В. В. Модели случайных процессов для вероятностных задач синтеза АСУ. Генеральная совокупность реализаций. Эргодичность. Единственная реализация. М.: Изд-во МЭИ, 1998. 64 с.

23. Волгин В.В., Каримов Р.Н. Оценка корреляционных функций в промышленных системах управления. М.: Энергия, 1979. 80 с.

24. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы программы суперЭВМ /Под ред. Я. Ковалика. М.: Радио и связь, 1988

25. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

26. Гильберт Д. Основания геометрии. М.: Гостехиздат, 1948.

27. Голуб Дж., Ван Лоан Ч. Матричные вычисления. М.: Мир, 1993.

28. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения: Пер. с англ. М.: Мир, 1988. - 208 с.

29. Данциг Дж. Б. Линейное программирование, его применения и обобщения. -М.: Прогресс, 1966.

30. Демиденко Е.З. Линейная и нелинейная регрессии. М.:Финансы и статистика, 1981.-302 с.

31. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. Пер с англ. М.: Мир, 1988.

32. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке: В 2-х томах, т.1 Методы обработки данных, т.2 - Методы планирования эксперимента. - М.: Мир, 1980,1981. - 610с, - 529с.

33. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. Пер с англ. М.: Мир, 1984.

34. Дрейпер Н., Смит Г. Прикладной регрессионный анализ: В 2-х кн. Кн.1, Кн.2 / Пер. с англ. М.: Финансы и статистика. 1986. 366с., 1987,351 с.

35. Енюков И.С. Методы, алгоритмы, программы многомерного статистического анализа: Пакет ППСА. М.: Финансы и статистика, 1986. 232 с.

36. Еремин А.Ю., Капории И.Е., Реализация явных чебышевских методов при решении задач большой размерности, в кн.: Многопроцессорные вычислительные структуры. Таганрог: ТРТИ, 1985, вып. 7 (XVI), с. 43-46.

37. Загоруйко Н.Г. и др. Пакет прикладных программ ОТЭКС (для анализа данных). М.: Финансы и статистика, 1986. 160 с.41.3акс JI. Статистическое оценивание/ Пер. с нем. М.: Статистика, 1976. 598с.

38. Залманзон JI.A. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989. 496 с.

39. Иберла К. Факторный анализ. М.: Статистика, 1980. 398 с.

40. Иванов В.К., Васин В.В., Тасана В.П. Теория линейных некорректных задач и ее приложения. М.: Наука, 1978,206с.

41. Ицкович Э.Л. Контроль производства с помощью вычислительных машин, М: Энергия, 1975, 416 с.

42. Каримов Р.Н. Обработка экспериментальной информации. Учеб. пособие. Ч. 1. Разведочный анализ. Анализ качественных данных. Ч. 2. Регрессионный анализ. СГТУ, Саратов, 2002. 112с., 116с.

43. Каримов Р.Н., Долотовский Л.В. Регрессионная модель сложной преобразовательной системы для многокритериального проектирования// Вопросы преобразовательной техники и частотного электропривода: Меж-вуз.научн.сб. Сарат.госуд.техн.ун т, 1994. С.ЗЗ - 38.

44. Каримов Р. Н., Кинцель Д. А. Решение плохо обусловленных задач с помощью безошибочных вычислений // Прогрессивные технологии в обучении и производстве. Матер. II всероссийской конференции, г. Камышин, Волгоград, 2003, Т.2,292 294

45. Каримов Р. Н., Кинцель Д. А. Методы оценивания коэффициентов парабол высоких порядков //Автоматизация и управление в машино- и приборостроении. Межвуз. науч. сб. Саратов, СГТУ, 2003. с. 112-115.

46. Каримов Р.Н., Усов Д. П. Знаковый метод оценки статических характеристик объектов в системах управления// Вопросы преобразовательной техники и частотного электропривода: Межвуз.научн.сб. Сарат.госуд.техн.ун -т, 2000. С.33-38.

47. Каримов Р.Н., Червякова О.В. Восстановление пропусков в многомерных данных методом сингулярного разложения. //Вопросы преобразовательной техники и частотного электропривода и управления: Межвуз.научн.сб. Сарат.госуд.техн.ун т, 1999. С. 19 - 26.

48. Кашьяп Р. JL, Pao А. Р. Построение динамических стохастических моделей по экспериментальным данным: Пер. с англ. М:., Наука. 1983. 384 с.

49. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение: Пер. с англ. Изд. второе, стереотип. - М.: Мир, 2001. - 575 е., ил.

50. Кедем Б. Спектральный анализ и различение сигналов по пересечениям нуля // ТИИЭР. 1986. Т. 74, № 11. С. 6-25.

51. Кендалл М.Дж., Стьюарт А. Статистические выводы и связи/ Пер. с англ. М.: Наука, 1973. 899 с.

52. Кендалл М.Дж., Стьюарт А. Многомерный статистический анализ временные ряды/Пер. с англ. М.: Наука, 1976. 736 с.

53. Кинцель Д. А. Оценивание зависимостей с использованием параболической функции одной переменной. // Электротехнические комплексы и силовая электроника. Анализ синтез управление: Межвуз. науч. сб. Саратов: СГТУ, 2003. с. 48-54.

54. Кнут Д. Е. Искусство программирования. Том 2. Получисленные алгоритмы. М.: Мир, 1977.

55. Корн Г., Корн Т., Справочник по математике для научных работников и инженеров; пер с англ., М.: Наука, 1979,720 с.

56. Корнейчук Н.П., Экстремальные задачи теории приближения, М.: Наука, 1976,320 с.

57. Крамер Г., Лидбеттер М. Стационарные случайные процессы. М.: Мир, 1969.398 с.

58. Куликов Е. И., Трифонов А. П. Оценка параметров сигналов на фоне помех. М.: Сов. радио, 1978. 296 с.о

59. Ликеш И., Ляга И. Основные таблицы математической статистики/ Пер.с чешек. М.: Финансы и статистика, 1985. 356 с.

60. Лимер Э. Статистический анализ не экспериментальных данных. Выбор формы связи: Пер. с англ. М.: Финансы и статистика, 1983. - 381 с.

61. Линник Ю.В. Метод наименьших квадратов и основы теории обработки наблюдений. Л. Физматгиз, 1962,352с.

62. Литвак Б.Г. Экспертная информация: Методы получения и анализа. М.: Радио и связь, 1982. - 184 с.

63. Литтл Р. Дж.А., Рубин Д.А. Статистический анализ данных с пропусками/Пер. с англ. М.: Финансы и статистика, 1990. 366 с.

64. Лоусон Ч., Хенсен Р. Численное решение задач метода наименьших квадратов: Пер.с англ. М.: Наука, 1986. - 232 с.

65. Льюнг Л. Идентификация систем. Теория для пользователя: Пер. с англ. М.: Наука, 1991.432 с.

66. Мак-Кракен Д., Дорн У. Численные методы и программирование на фортране. Пер. с англ. М.: Мир, 1977. - 584 с.

67. Маленво Э. Статистические методы эконометрии. М.: Статистика, 1975, вып. 1,-421 е., 1976, вып. 2, - 325 с.

68. Маркус М., Минк X. Обзор по теории матриц и матричных неравенств. Пер. с англ. М.: Мир, 1982.

69. Марпл-мл.С.Л. Цифровой спектральный анализ и его приложения: Пер. с англ. М.: Мир, 1990. - 584 с.

70. Математика и САПР: в 2-х кн., кн 1. Основные методы. Теория полюсов., /Пер. с франц./, Шенен П.,Коснар М., Гардан И. и др. М: Мир, 1988, 204с.

71. Математика и САПР: в 2-х кн., кн 2. Вычислительные методы. Геометрические методы., /Пер. с франц./, Жерман-Лакур П., Жорж П., Пистр Ф. и др. М: Мир, 1989,264с.

72. Математическая энциклопедия. М.: Советская энциклопедия, 1979. Т.2. 1104с.

73. Митропольский А.К. Техника статистических вычислений. М.: Наука, 1971.-576 с.

74. Морозов В.А., Регулярные методы решения некорректно поставленных задач. М: Наука, 1987,240 с.

75. Мостеллер Ф., Тьюки Дж. Анализ данных и регрессия: В 2-х вып. Вып. 1/ Пер. с англ. М.: Финансы и статистика, 1982. 317 с.

76. Мудров В.И., Кушко В.Л. Метод наименьших модулей. М.: Знание, 1971.-64 с.

77. Налимов В.В. Теория эксперимента. М.: Наука, 1971. 208с.

78. Немчинов B.C. Полиномы Чебышева и математическая статистика. М.: Наука, 1946.

79. Обнаружение изменения свойств сигналов и динамических систем: Пер. с англ./ М. Бассвиль, А. Вилски, А. Банвенист и др.; Под ред. М. Бассвиль и А. Банвениста. М.: Мир, 1989. 278 с.

80. Оппенгейм A.B., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. /Под. ред. С.Я. Щаца. М.: Связь, 1979. - 416 е., ил.

81. Орлов А.И. Задачи оптимизации и нечеткие переменные. М.: Знание, 1980.64 с.

82. Ортега Дж., Введение в параллельные и векторные методы решения линейных систем: Пер. с англ., М: Мир, 1991,367с.

83. Ортега Дж., Пул У. Введение в численные методы дифференциальных уравнений. Пер с англ. М.: Наука, 1986.

84. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. Пер с англ. М.: Мир, 1975.

85. Остем К., Виттенмарк Б. Системы управления с ЭВМ: Пер с англ. М.: Мир, 1987. 480 с.

86. Отнес Р., Эоксон JI. Прикладной анализ временных рядов. Основные методы/ Пер. с англ. М.: Мир, 1982.428 с.

87. Пакеты прикладных программ: Опыт использования. М.: Наука, 1989 (Алгоритмы и алгоритмические языки).

88. Поллард Дж. Справочник по вычислительным методам статистики/Пер. с англ. М.: Финансы и статистика, 1982. 344 с.

89. Прикладная статистика: Классификация и снижение размерности / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин. М.: Финансы и статистика, 1989. 607 с.

90. Пытьев Ю. П. Математические методы интерпретации эксперимента: Учеб. Посо-бие для вузов. М.: Высш. шк., 1989. 351 с.

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

92. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов: Пер. с англ. М.:, Мир. 1978. 774 с.

93. Робастность в статистике. Подход на основе функций влияния/Пер. с англ. М.: Мир, 1989. 512 с.

94. Самарский A.A., Гулин A.B., Численные методы. Учебное пособие для ВУЗов, М.: Наука, 1989,432 с.

95. Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ./Под ред. С. Гуна, X. Уайтхауса, Т.Кайлата. М.: Радио и связь, 1989.-472 е.: ил

96. ЮО.Себер Дж. Линейный регрессионный анализ / Пер.с англ.- М.: Мир, 1980. 456 с.

97. Семенов H.A. Программы регрессионного анализа и прогнозирования временных рядов. Пакеты ПАРИС и МАВР. М.: Финансы и статистика. 1990.—111 с.

98. Сергеенко.А.Б. Цифровая обработка сигналов: Учебное пособие. СПб.: Питер, 2002. 608 с.

99. Сирл С., Госман У. Матричная алгебра в экономике: Пер. с англ. М.: Статистика, 1974. - 374 с.

100. Ю4.Смоляк. С.А., Титаренко Б.П. Устойчивые методы оценивания: (Статистическая обработка неоднородных совокупностей). М.: Статистика, 1980. 208 с.

101. Ю5.Современные методы идентификации систем. Пер. с англ./ Под ред. П. Эйкхоффа. М.: Мир, 1983.400с.

102. Юб.Справочник по прикладной статистике: В 2-х т. Т.1, Т.2/Пер.с англ. под ред. Э.Ллойда, У.Ледермана, Ю.Н.Тюрина. М. Финансы и статистика, 1989,1990, 510с.,-526с.

103. Статистические методы для ЭВМ. Пер.с англ. М.: Наука, 1986. - 464 с.

104. Стахов А.П. Введение в алгоритмическую теорию измерения. М.:, Сов. Радио, 1977.-288 с.

105. Суетин П.К. Классические ортогональные многочлены. М.: Наука, 1976.

106. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач., М: Наука, 1979, 286 с.

107. Ш.Тихонов А.Н., Гончарский A.B., Степанов В.В. Регулязирующие алгоритмы и априорная информация, М: Мир, 1983, 200с.

108. Тихонов А.Н., Уфимцев M.B. Статистическая обработка результатов эксперимента. М.: Изд-во МГУ, 1988. 174 с.

109. ИЗ.Ту Дж., Гонсалес Р. Принципы распознавания образов: Пер.с англ. М.: Мир, 1978.411с.

110. Тутубалин В. Н. Теория вероятностей. М.: МГУ, 1972. 230 с.

111. Тьюки Дж. Анализ результатов наблюдений. Разведочный анализ/Пер. с англ. М.: Мир, 1981. 693с.

112. Пб.Тюрин Ю.Н., Макаров A.A. Статистический анализ данных на компьютере. М.: ИНФРА М, 1998. - 528 с.

113. Уилкс С. Математическая статистика: Пер. с англ. М.: Наука, 1967. -632 с.

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

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

116. Форсайт Дж., Моулер К. Численное решение систем линейных алгебраических уравнений. Пер с англ. М.: Мир, 1969.

117. Хадлет Р., Джонсон Р. Линейная классификация и некоторые дальнейшие результаты по наилучшим представлениям низкой размерности. // Классификация и кластер. М.: Мир, 1980. 389 с.

118. Хальд А. Математическая статистика с техническими приложениями. -М.:ИЛ, 1956.

119. Хемминг Р.В. Численные методы для научных работников и инженеров. М.:, Наука, 1972,-400 с.

120. Хеннан Э. Многомерные временные ряды. Пер. с англ. М.: Мир, 1974. 575 с.

121. Химмельблау Д. Анализ процессов статистическими методами/Пер. с англ. М.: Мир, 1973.- 957с.

122. Хорн Р., Джонсон Ч. Матричный анализ/Пер.с англ. М.: Мир, 1989. 655с.

123. Хьюбер П. Робастность в статистике/Пер. с англ. М.: Мир, 1984.304 с.

124. Цветков Э.И. Методические погрешности статистических измерений, Ленинград, Энергоатомиздат, 1984,144с.

125. Цветков Э.И. Процессорные измерительные средства, Ленинград, Энергоатомиздат, 1989, 224с.

126. Чуев Ю.В., Михайлов Ю.Б., Кузьмин В.И. Прогнозирование количественных характеристик процессов. М.: Сов. Радио, 1975. 400 с.

127. Шилов Г.Е. Математический анализ (конечномерные линейные пространства), М.: Наука, 1969, 432с.

128. Шишкин Е.В. Линейные пространства и отображения М.: изд-во МГУ, 1987,311с.

129. Эстербо О., Златев 3. Прямые методы для разреженных матриц: Пер. с англ., М.: Мир, 1987,120с.

130. Ярославский Л.П. Введение в цифровую обработку изображений. М.: Сов. Радио, 1979.312 с.

131. Jenkins М.А., Traub J.F. 1970, A three-stage algorithm for real polynomials using quadratic iteration, SIAM Journal on Numerical Anlysis 7, pp 545-556.

132. Luenberger D. G. 1984, Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Massachusetts.

133. Mathcad 6.0 PLUS. Финансовые, инженерные и научные расчеты в среде Windows 95. Издание 2-е, стереотипное М.: Информационно-издательский дом «Филинъ», 1997. - 712 с.

134. Rissanen J. A. Universal Prior for the Integers and Estimation bu Minimum Description Length. Ann. Stat., vol. 11, pp. 417-431, 1983.

135. Schnabel R.B., Koontz J.E., Weiss B.E. 1982, A modular system of algorithms for unconstrained minimization, Report CU-CS-240-82, Computer Science Department, University of Colorado, Boulder, Colorado

136. Simonoff, J.S. (1988), Regression Diagnostics to Detect Nonrandom Miss-ingness in Linear Regression, Technometrics, v.30, n.2, p.205 214.

137. Wattson L.T. 1986, Numerical linear algebra aspects of globally convergent homotopy methods, SIAM Review pp. 529-545.