Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ

Факультет информационных технологий

Кафедра моделирования информационных систем и сетей

Выпускная квалификационная работа

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

Студента 2-го курса магистратуры очной формы обучения

Направление 230100.68 - Информатика и вычислительная техника (магистр)

Щербаков Роман Сергеевич

Руководитель: д.т.н., профессор

Гданский Н.И.

Рецензент

к.т.н., доцент

Карпов А.В.

Москва 2015

Оглавление

Введение

1. Обзор существующих результатов по теме работы. Постановка задачи исследования

1.1 Алгоритм. Основные свойства и качественные показатели

1.2 Основные понятия численных методов линейной алгебры

1.3 Линейные уравнения и системы линейных уравнений. Основные понятия

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

1.5 Прямые методы решения систем линейных уравнений с исключением неизвестных. Метод Гаусса

1.6 Решение систем линейных уравнений с использованием LU-разложения матрицы системы

1.7 Цифровые и аналоговые алгоритмы фильтрации и сглаживания данных

1.8 Моменты наступления событий как случайные потоки событий в системах массового обслуживания

1.9 Нормальное распределение, его свойства и моделирование

1.10 Построение линейных моделей с использованием данных обратной связи

1.11 Анализ выполненного обзора. Постановка задачи исследования

2. Влияния погрешности исходных данных на точность расчета коэффициентов линейной модели. Влияние сглаживания на их точность

2.1 Оценка влияния погрешности исходных данных на точность расчета коэффициентов линейной модели

2.2 Линейное симметричное сглаживание исходных данных расчетной модели. Формулы для неравномерной сетки

2.3 Основные допущения при построении имитационной модели

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

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

3.1 Постановка задачи аппроксимационного сглаживания

3.2 Вывод основных соотношений квадратичной аппроксимации

3.3 Варианты алгоритмов квадратичного аппроксимационного сглаживания данных

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

Заключение

Библиографический список

Введение

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

Объект исследования Методы построения линейных моделей в задачах управления.

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

Методы исследования. При выводе теоретических положений и разработке алгоритмов применены методы математического моделирования, математического анализа, численных методов и теории алгоритмов. При разработке программного обеспечения и выполнении расчетов использовался программный комплекс, MS Visual Studio 2012.

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

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

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

1)максимально возможной точностью решения,

2) минимальной вычислительной сложностью получаемого решения.

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

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

2. Выбор рациональных методов решения СЛАУ с учетом погрешностей данных обратной связи.

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

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

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

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

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

Во второй главе исследована зависимость погрешностейх векторовх коэффициентов линейных моделей от погрешностей и коэффициентов матрицы и свободного вектора. Доказано, что с точностью до малых второго порядка данная зависимость х (,).линейна. Предложено формульное задание для симметричной относительно центральной точки t_j линейно-взвешенной фильтрации по общему нечетному числу m=2s+1 сигналов для случая неравномерной сетки по времени, учитывающее два возможных случая отклонение текущих точек относительно центральной точки. Оценена вычислительная сложность фильтров. Разработан алгоритм имитационного моделирования зашумленных данных и их симметричного линейного сглаживания. По выполненному алгоритму разработана расчетная программа на языке С++ и выполнены расчеты для 11 видов функций. Дан анализ полученных результатов.

В третьей главе на основе анализа результатов имитационного моделирования дана постановка задачи аппроксимационного сглаживания, дан вывод основных соотношений квадратичной аппроксимации, требующих минимальных вычислительных затрат. Разработано 4 варианта алгоритмов квадратичного аппроксимационного сглаживания данных, отличающиеся числом последующих точек, используемых при сглаживании (глубинами h =0,1,2,3), а также величиной доли учета аппроксимированных значений функции . Разработано семейство аппроксимационных квадратичных методов с глубинами h =0,1,2,3 и заданной долей аппроксимированного значения . Дана оценка их вычислительной сложности при фильтрации одного значения функции. Разработан алгоритм имитационного моделирования зашумленных данных при помощи квадратичного аппроксимационного сглаживания. По нему написана программа на языке С++. С применением данной программы выполнено сравнительное исследование предложенных методов. Оно показало, что алгоритм глубины 0 дает устойчивые результаты по уменьшению матожидания высокочастотных шумов. На тестовых кривых данное уменьшение составило 10-30 раз. Это дает основание рекомендовать его к практическому использованию вместо линейных фильтров, имеющих более низкие показатели.

Аннотация

Выпускная квалификационная работа содержит 96 страниц, 4 рисунка и 3 таблицы, 38 использованных литературных источников.

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

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

Во второй главе исследована зависимость погрешностей коэффициентов линейных моделей от погрешностей входных данных. Предложено формульное задание для симметричной относительно центральной точки линейно-взвешенной фильтрации для случая неравномерной сетки по времени. Разработан алгоритм имитационного моделирования зашумленных данных и их симметричного линейного сглаживания. По нему разработана расчетная программа на языке С++ и выполнены расчеты для 11 видов функций. Дан анализ полученных результатов.

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

Annotation

Graduate work contains 99 pages, 4 figures and 3 tables, 38 references, and 4 applications.

The work is devoted to the study of errors of calculation of linear models in problems of digital control and the development of methods to reduce them by filtering the input data.

The first chapter describes the methods for solving systems of linear algebraic equations, methods of filtering data in digital systems, simulation of random processes, formulated objectives of the work

The second chapter of the dependence of the errors of the coefficients of linear models of error in the input data. Proposed definable task for symmetrical about a central point linearly weighted filtering the case of non-uniform grid over time. An algorithm for simulation of noisy data and a balanced line smoothing. According to it, the design program developed in C + + and performed calculations for 11 kinds of functions. The analysis of the results.

In the third chapter, the statement of the problem of the approximation of smoothing, developed four versions of the quadratic approximation algorithms for data smoothing. An algorithm for simulation of noisy data by using these methods, it is written by the program in C + + and performed numerical experiments, which showed that the algorithm of the depth of 0 yields consistent results on the reduction of mathematical expectation of high frequency noise.

1. Обзор существующих результатов по теме работы. Постановка задачи исследования

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

1.1 Алгоритм. Основные свойства и качественные показатели

Понятие алгоритма первично [4,9,19,36,38]. Словесно алгоритм можно определить как последовательность точно сформулированных и однозначно определенных действий по решению поставленной задачи. Данные основные свойства алгоритмов обеспечивают практическую возможность их выполнения (и, соответственно, решения задач) при помощи вычислительных машин.

Основные свойства алгоритма.

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

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

3. Массовость применения. Алгоритм предназначен для решения целого класса однотипных задач. Например, для сложения двух целых чисел вариантов таких пар - бесконечное множество.

4. Результативность. Алгоритм выдаёт уникальный и предполагаемый результат для заданных входных данных.

Основные способы записи алгоритмов.

1. Словесное описание - используется естественный язык.

2. Графическое. С помощью специальных изображений, которые называют блок--схемами.

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

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

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

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

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

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

1.2 Основные понятия численных методов линейной алгебры

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

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

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

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

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

Линейное (векторное) пространство L строится с использованием числового множества Р, которое образует поле - алгебраическую систему, в которой на элементах множества определены бинарные (двухместные) отношения и бинарные операции (сложение + и умножение ), подчиненные 9 основным аксиомам АР1- АР9. Множество Р называют также числовым полем, а его элементы - числами или скалярами.

Линейное (векторное) пространство L(Р) над полем P -- это множество элементов (называемых векторами) L, на котором введены операции сложения векторов (+) и умножения () вектора на скаляр (число), удовлетворяющие аксиомам теории поля АР1- АР8.

При этом элементы множества L(Р) называют векторами, а элементы поля P -- скалярами.

Важным понятием векторных пространств является линейная зависимость. Конечное множество векторов {v₁,v₂,...,v_n}L называется линейно независимым, если единственная линейная комбинация данных векторов ₁v₁+₂v₂+...+_nv_n равная нулю, является тривиальной, т.е. имеет нулевые коэффициенты: ₁=₂=...=_n=0. Если существует нулевая линейная комбинация векторов {v₁,v₂,...,v_n} с ненулевыми коэффициентами, то данной множество называют линейно зависимым.

Линейное пространство называют n-мерным, если в нем существует линейно независимая комбинация из n векторов, а любая комбинация из большего числа векторов является линейно зависимой. Число n называют размерностью пространства. В любом n-мерном векторном пространстве L можно найти ортонормированный (состоящий из взаимно ортогональных векторов единичной длины) базис из n векторов {е₁,е₂,...,е_n}, в котором однозначно будут разлагаться (представлены в виде линейной комбинации вида x =x₁е₁+x₂е₂+...+ x_nе_n) любые векторы из L. Коэффициенты данного разложения однозначно задают вектор в базисе {е₁,е₂,...,е_n} : х=(x₁, . . . , х_n).

Евклидово пространство Еⁿ - n-мерное векторное пространство над полем вещественных чисел R с положительно определённым скалярным произведением векторов (x,y), которое для любых векторов х=(x₁, . . . , х_n)Еⁿ и y=(y₁, . . . , y_п)Еⁿ обозначается как (x,y) и рассчитывается по формуле:

(x,y) = x₁y₁ + . . . + х_nу_п.

Наряду со скалярами и векторами основными элементами линейной алгебры являются матрицы -- математические объекты, имеющие вид прямоугольных таблиц элементов поля R, которые представляют собой совокупность строк и столбцов, на пересечении которых находятся её элементы. Количество строк и столбцов матрицы задают размер матрицы. Наибольший интерес представляют квадратные матрицы, у которых число строк равно числу столбцов. Это число называют порядком матрицы. Матрицы обозначают большими латинскими буквами (А,В,...), а их элементы - соответствующими малыми с указанием в нижних индексах номера строки и столбца элемента (а₁₂, b_ij). Матрицы используют в математике для компактной записи систем линейных алгебраических или дифференциальных уравнений в векторной форме. При этом строки матрицы соответствуют левым частям уравнений системы, а столбцы -- ее неизвестным. Также при наличии свободных коэффициентов в уравнениях для них вводят отдельный вектор. В результате, решение систем линейных уравнений сводится к операциям над их матрицами и векторами свободных коэффициентов.

У квадратных матриц особо выделяют совокупность элементов, у которых номера строк и столбцов совпадают (а₁₁, а₂₂,...,а_nn), которую называют главной диагональю матрицы А. Транспонированием называют такое преобразование матрицы А, при котором столбцы и строки меняются местами, т.е. все недиагональные элементы симметрично отражаются относительно главной диагонали. Транспонированную матрицу обозначают А^т.

Пример 1. Матрица А порядка 3 и транспонированная матрица А^т:

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

Треугольной нижней называют квадратную матрицу, у которой выше главной диагонали стоят нули (А₁), треугольной верхней называют квадратную матрицу, у которой ниже главной диагонали стоят нули(А₂). Диагональной называют квадратную матрицу, у которой все недиагональные элементы равны нулю (D). Важным частным случаем диагональной матрицы является единичная, в которой на диагонали стоят только единицы (Е). Для Е и любой матрицы того же порядка А справедливо:

AE = EA = A.(1.1)

Пример 2. Треугольные нижняя (А₁) и верхняя (А₂), диагональная (D) и единичная (Е) квадратные матрицы порядка 3:

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

Симметричными называют матрицы, у которых во всех парах элементов, расположенных симметрично относительно главной диагонали, элементы равны между собой: a_{i j} = a_{j i} (1 i,j n; i j). В примере 3 приведена симметричная матрица А₁ порядка 3.

Пример 3. Симметричная матрица А₁ порядка 3, прямая матрица А₂ и обратная к ней А₂^-1:

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

Матрицей, обратной к А, называют матрицу A^-1, которая при умножении на А дает в итоге единичную матрицу Е:

A^-1 A = A A^-1 = Е.(1.2)

В примере 3 дана матрица А порядка 3 и ее обратная матрица A^-1.

1.3 Линейные уравнения и системы линейных уравнений. Основные понятия

Линейные уравнения являются наиболее употребительными в математическом моделировании при построении зависимостей между параметрами моделей [1,2,7,8,16,17,33-35]. Это обусловлено тем, что линейная зависимость параметров наиболее наглядна, имеет самое простое математическое выражение, для которого достаточно полно разработана теория и практические методы решения. Поэтому зачастую на практике при решении нелинейных зависимостей используют линеаризацию их в области искомых значений неизвестных для упрощения методов исследования.

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

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

Каноническим называют такой вид линейных уравнений, при котором все слагаемые, содержащие неизвестные (х₁, х₂,... х_n), находятся в левой части и выполнено приведение коэффициентов при неизвестных (а₁, а₂,... а_n), а приведенный свободный коэффициент (b) стоит в правой части уравнения:

а₁х₁+ а₂х₂+...+ а_nх_n = b.

Линейными уравнениями с одним неизвестным в каноническом виде называют зависимости типа

а х = b,(1.3)

где х- неизвестное, a, b - постоянные коэффициенты.

Теоретическим достаточным условием существования и единственности решения линейного уравнения (1.3) с одним неизвестным является условие

a 0. (1.4)

При его выполнении решение (1.4) всегда существует, единственно и равно:

х = b / а.(1.5)

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

a ,(1.6)

где > 0 - заранее задаваемое положительное число, задающее граничную величину предельной абсолютной погрешности линейного коэффициента a, при которой он уже не считается равным или близким к нулю. Если условие (1.6) выполнено, то решение совпадает с (1.5).

Системой m линейных уравнений с n неизвестными (или линейной системой) в линейной алгебре называют систему m линейных уравнений канонического вида с n неизвестными вида:

(1.7)

В (1.7) x₁, x₂, …, x_n -- неизвестные, a₁₁, a₁₂, …, a_mn -- постоянные линейные коэффициенты системы (задающие матрицу системы), b₁, b₂, … b_m -- свободные члены (задающие вектор свободных коэффициентов). Индексы коэффициентов (a_ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент.

Систему (1.7) называются однородной, если все её свободные члены равны нулю (b₁ = b₂ = … = b_m = 0), иначе -- неоднородной.

Система (1.7) называется квадратной, если число m ее уравнений равно числу n неизвестных. Число n = m называют порядком системы.

Решение системы (1.7) -- совокупность n чисел c₁, c₂, …, c_n, таких что подстановка каждого c_i вместо x_i в систему (1.7) обращает все её уравнения в тождества. Найти решение системы означает выяснить, существуют ли у системы решения, и если они существуют, найти их.

Система (1.7) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения. Совместная система вида (1.7) может иметь одно или более решений.

Решения c₁⁽¹⁾, c₂⁽¹⁾, …, c_n⁽¹⁾ и c₁⁽²⁾, c₂⁽²⁾, …, c_n⁽²⁾ совместной системы вида (1.7) называются различными, если нарушается хотя бы одно из равенств:

c₁⁽¹⁾ = c₁⁽²⁾, c₂⁽¹⁾ = c₂⁽²⁾, …, c_n⁽¹⁾ = c_n⁽²⁾.

Совместная система вида (1.7) называется определённой, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется неопределённой. Если уравнений больше, чем неизвестных, она называется переопределённой.

В технических приложениях, как правило, рассматриваются системы с квадратными матрицами (m = n). Поэтому в дальнейшем будем рассматривать только этот случай.

Множество коэффициентов (a_ij) квадратной системы образуют ее матрицу А, а множество коэффициентов (b_i) - вектор В свободных коэффициентов системы. Обозначив вектор (x₁, x₂, …, x_n) неизвестных черезХ, в векторном виде систему представляют в виде:

AХ =В. (1.8)

Рассмотрим систему линейных уравнений с квадратной матрицей (1.8). Теоретически необходимым и достаточным условием существования единственного решения данной системы является условие:

det(A)0.(1.9)

Если det(A)=0, то матрица А называется вырожденной, а система линейных уравнений либо не имеет решения, либо имеет их бесчисленное множество. При выполнении практических расчетов на ЭВМ из-за округления результатов вычислений точное равенство определителя, как правило, не выполняется. Поэтому вместо условия (1.9) необходимо использовать условие вида:

det(A) ,

в котором > 0 - малое число, учитывающее возможные погрешности вычислений.

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

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

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

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

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

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

Среди прямых методов решения, в которых решение системы выражено в формульном виде наиболее известными являются методы:

1) с помощью обратной матрицы,

2) метод Крамера.

1. Метод с использованием обратной матрицы [1,2,16,17,33,34]. Векторное решение системы линейных уравнений вида (1.8) можно получить умножая обе части системы слева на обратную матрицу A^-1. Оно имеет вид:

Х = A^-1В (1.10)

где A^-1 матрица, обратная к А.Таким образом, решение системы сводится к решению задачи обращения квадратной матрицы системы А.

Оценка трудоемкости и сложности алгоритма. Определим вначале число необходимых операций при решении системы линейных уравнений с использованием обращения матрицы. В теории известно, что при использовании сокращенного алгоритма, реализующего метод Гаусса--Жордана, на получение обратной матрицы A^-1 порядка n затрачивается (n-1)²(n+1) умножений и сложений, а также 2(n-1)(n+1) делений. Для получения решения Х обратная матрица должна быть умножена на свободный вектор системыВ. Данное умножение требует выполнения n² умножений и n(n-1) сложение. В итоге получим, что суммарные количества умножений m(n), сложений s(n) и делений d(n) в алгоритме с использованием обратной матрицы будут следующими:

m(n) = (n-1)²(n+1) + n² = n³ - n² + 1;

s(n) = (n-1)²(n+1) + n(n-1) = n³ - 2n + 1;

d(n)= 2(n-1)(n+1).

Из найденных чисел m(n), s(n) и d(n) следует, наиболее быстро растут числа операций сложения и умножения (n³), сложность алгоритма - кубическая O(n³).

Метод (правило) Крамера [5,27,30,63,112] представляет каждое неизвестное х_i системы уравнений (1.6) в виде отношения определителей:

х_i = _i /, (1.11)

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

- главный определитель системы (определитель матрицы А).

Оценка сложности алгоритма. Из теории известно, что оптимальные методы расчета определителей имеют максимальную (при ненулевом определителе) сложность О(n³). Поскольку метод Крамера предусматривает расчет (n+1) определителя порядка n, то его сложность будет в лучшем случае при оптимальном расчете определителей иметь полиномиальную сложность четвертой степени: n О(n³)=О(n⁴). Метод не оптимален, поскольку он имеет сложность, превышающую сложность метода с использованием обратной матрицы. Высокая сложность метода обусловлена тем, что в нем при расчете определителей повторно рассчитываются их одинаковые фрагменты. Поэтому метод Крамера имеет больше теоретическое, чем практическое значение.

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

1.5 Прямые методы решения систем линейных уравнений с исключением неизвестных. Метод Гаусса

Рассмотрим квадратную систему линейных уравнений порядка n:

(1.12)

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

1. Сложение или вычитание уравнений.

2. Умножение или деление всех членов уравнения на постоянное ненулевое число.

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

Основная идея метода исключения состоит в том, что за счет эквивалентных преобразований уравнений системы (1.12) в ней:

1) из уравнений системы с номерами 2,...,n устраняется неизвестное х₁

2) из уравнений системы с номерами 3,...,n - неизвестное х₂,

3) из уравнений системы с номерами 4,...,n - неизвестное х₃ и т.д.

При этом в матрице системы под главной диагональю обнуляются 1) элементы столбца 1; 2) элементы столбца 2; 3) элементы столбца 3 и т.д., т.е. матрица последовательно приводится к верхнему треугольному виду.

Метод Гаусса.

Метод исключения Гаусса [1,7,8,16,17,33,35] содержит два основных этапа эквивалентных преобразований уравнений системы:

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

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

В качестве операций, определяющих скорость выполнения алгоритма приняты: 1) сравнение, 2) сложение и вычитание,3) умножение, 4) деление. Числа операций данных операций для задачи размерности n обозначим как c(n), s(n), m(n), d(n). В дальнейшем при расчете чисел операций и оценке сложности будем рассматривать случай, когда система имеет единственное решение, т.е. определитель матрицы А не равен нулю. При этом достигается максимальная сложность алгоритма.

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

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

1) существует ли единственное решение системы,

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

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

Для минимизации вычислительной погрешности в каждой строке матрицы i (1in-1) выбирается элемент с максимальным модулем. Его называют главным элементом строки и путем перестановки порядка неизвестных помещают данный элемент на главную диагональ матрицы. Для контроля текущего положения неизвестных в уравнениях системы введем целочисленный вектор порядка неизвестных Р. Каждый его элемент p_i задает текущий номер столбца матрицы A, который соответствует неизвеcтному x_i исходной системы уравнений.

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

Если оно выполняется, то это означает, что путем эквивалентных преобразований в матрице системы выделена практически нулевая строка и из свойств определителя следует: det(A)=0. При этом система не имеет единственного решения.

Прямой ход можно представить в виде последовательного выполнения начальных присваиваний и шагов с номерами i (1in), на которых обрабатываются элементы строки i, лежащие на главной диагонали и правее ее, а также все аналогичные элементы нижележащих строк i +1,..., n.

Начальные присваивания. Всем элементам p_i вектора порядка неизвестных Р. присваиваем значения, равные i (1in): p_i:= i.

Шаг i (1in) включает выполнение следующих действий.

1. Поиск главного элемента m_i строки i. Для него также фиксируется номер столбца j_mi. Если модуль m_i мал (m_i< ), то определитель матрицы близок к нулю и полагаем, что решение системы не существует, выход из алгоритма с отрицательным ответом.

Если же модуль значения главного элемента m_i равен или превышает , то продолжаем выполнение алгоритма.

Общее число сравнений для строки i равно (n - i +1).

2. При (j_mi i) в матрице А меняем местами столбцы с номерами j_mi и i, а в вектореР меняем местами значения соответствующих элементов: p_i p_jmi .

3. Преобразование нижележащих строк матрицы и элементов вектораВ с номерами k = i +1,..., n для обнуления элементов столбца i, лежащих под главной диагональю. Для этого вначале рассчитывается отношение (-a_ki/a_ii), затем на него умножаются все элементы i-строки от i до n, после чего складываются все элементы строк i и k в столбцах с номерами от (i+1) до n. Также на отношение (-a_ki/a_ii) умножается элемент b_i свободного столбца и складывается с элементов b_k, после чего получается новое значение элемента b_k: b_k :=b_k + (-a_ki/a_ii) b_i .

Для каждой строки k и соответствующего элемента свободного вектора затрачиваем операции: сложений и умножений - по (n-i)+1; делений 1. Поскольку ниже строки i лежит (n-i) строк, то общее число затрачиваемых операций при обработке строки i и всех нижележащих cтрок равно:

- сравнений: c_i(n) = (n-i+1);

- сложений и умножений: s_i(n) = d_i(n) = (n-i)((n-i)+1)= (n-i)²+(n-i) ;

- делений: m_i(n) =1*(n-i) = (n-i).

Исходная система уравнений (1.10) после выполнения эквивалентных преобразований при прямом ходе в случае ненулевого определителя матрицы примет вид:

(1.13)

Трудоемкость прямого хода. Суммируя числа операций по всем строкам с номерами i (1in), получаем, что при выполнении прямого хода метода Гаусса затрачивается следующее количество операций рассмотренного вида (c_пр(n), s_пр(n), m_пр(n), d_пр(n)):

- сравнений: c_пр(n) = n +(n-1)+ …+1 = n(n+1)/2;

- сложений и умножений: s_пр(n) = m_пр(n) = [(n-1)²+(n-2)²+…+1²+0²]+[(n-1)+(n-2)+…+1+0] = (n-1)n(2n-1)/6 + n(n+1)/2 = n (n²-1)/3;

- делений: d_пр(n) = (n-1)+(n-2)+ …+0 = n(n-1)/2.

Выполненные оценки показывают, что сложность прямого хода - кубическая О(n³).

Обратный ход. Задача - путем эквивалентных преобразований системы уравнений выполнить обнуление всех элементов матрицы А, лежащих выше главной диагонали. Строки матрицы i и компоненты свободного вектора обрабатываются в обратном порядке - от i=n до i=1.

По аналогии с прямым ходом вначале рассмотрим обработку произвольной строки с номером i и всех строк, лежащих выше нее (от k=i-1 до k=1), а также соответствующих компонент свободного вектора. При обработке каждой строки k вначале определяется отношение (-a_ki/a_ii). Затем на него умножается элемент b_i свободного столбца и складывается с элементов b_k, после чего получается новое значение элемента b_k: b_k :=b_k + (-a_ki/a_ii) b_i .

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

(1.14)

Разделив все элементы свободного вектора B на соответствующие диагональные элементы матрицы А: х_i := b_i /a_ii ; (1 ? i ? n), получим решение системы, в котором неизвестные переставлены согласно векторуР. При этом дополнительно будет выполнено n делений.

Искомые решения {х_i} исходной системы (1.12), получаем, переставляя полученные после обратного хода значения { х_i } с учетом компонент вектора порядка неизвестных Р:

х_i :=х _pi ; (1 ? i ? n).

Трудоемкость обратного хода. Суммируя числа операций по всем строкам с номерами i (1in), с учетом дополнительных n операций деления получаем, что при выполнении обратного хода затрачивается следующее количество операций:

- сравнения: c_обр(n) =0;

- сложения и умножения: s_обр(n) = d_обр(n)) = (n-1) + (n-2) +…+ 0 = n(n-1)/2;

- деления: d_обр = s_обр(n) + n = n(n-1)/2 + n = n(n+1)/2.

Сложность обратного хода - квадратическая О(n²).

Трудоемкость и сложность алгоритма метода Гаусса. Суммируя числа операций для прямого и обратного ходов, получим числа операций для всего алгоритма:

- сравнения: c(n) = с_пр(n) + с_обр(n) = n(n+1)/2;

- сложений и умножений: m(n) = s(n) = s_пр(n) + s_обр(n) = n (n²-1)/3 + n(n-1)/2 = n(n-1)(2n+5)/6;

- делений: d(n) = d _пр(n) + d_обр(n) = n(n-1)/2 + n(n+1)/2 = n².

Наиболее быстро растут числа сложений и умножений - как n³/3. Сложность алгоритма - кубическая О(n³).

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

Метод Гаусса-Жордана решения систем линейных уравнений

Данный метод является модификацией метода исключения [7,8,16,35]. Он также имеет прямой и обратный ходы.

Задачей прямого хода является выяснение существования решения системы и при положительном ответе - приведение ее матрицы к верхнему треугольному виду с единичной диагональю. Для этого на прямом ходе для всех значений i (i = 1,…,n) производится обработка элементов а_ij (j = i,…,n) ведущей строки i и соответствующего элемента b_i вектораB, а также обнуление элементов ведущего столбца i под главной диагональю. Вначале проверяют для диагонального элемента условие а_ii = 0.

Если равенство выполняется, заменяют всю строку i расширенной матрицы на нижележащую k (k > i), у которой элемент столбца i не равен нулю: а_ki 0. В том случае, если такой строки нет, то в рассматриваемой подматрице системы путем эквивалентных преобразований получен нулевой столбец, следовательно, ее определитель равен нулю и у нее и у всей исходной системы не существует единственного решения. Для уменьшения погрешности расчетов желательно при обмене выбирать такую нижележащую строку k (k > i), у которой элемент а_ki столбца i имеет максимальный модуль.

Если диагональный элемент а_ii 0, то все элементы строки i расширенной матрицы делятся на него. После такого преобразования элемент на главной диагонали а_ii будет равен 1. Обнуление элементов столбца i под главной диагональю производится аналогично методу Гаусса - к каждой нижележащей строке k (k > i),прибавляется строка i расширенной матрицы, все элементы которой умножены на коэффициент (-а_ki).

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