ВОСТОЧНО-СИБИРСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ  УНИВЕРСИТЕТ 
 

Кафедра ЭСПП и СХ

Электротехнический  факультет

УТВЕРЖДАЮ

 Зав.  кафедрой 

_____________ 

« ____ » _____________ 2007 год. 
 
 
 

ЗАДАНИЕ

по курсовому  проектированию 
 

Студенту  второго курса _____ группы электротехнического факультета  (ФИО) ________________________ 

Срок  выполнения проекта  _____________________2007 г. 

Защита  проекта назначена на ___________________2007 г. 

Время выдачи задания _________________________2007 г. 
 

1. Тема проекта: Изучение программ решения систем с ленточными матрицами. 

2. Задание и содержание  расчетно-пояснительной  записки:

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

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

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

      Выполнить следующие задания:

1. Показать, что процедура Б с частичным  выбором ведущего элемента требует  два раза больше памяти, чем  процедура А.

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

3. Провести подсчет числа операций, выполненных процедурами. Оценить временную сложность.

4. Представить требования на размер оперативной памяти для размещения переменных через размеры параметров задачи. Оценить объемную сложность.

5. Качественно сравнить трудность программирования метода исключения Гаусса для полных матриц с трудностью его программирования в условиях процедура А; сравнить полученные результаты с трудностью составления процедуры Б.

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

7. Повторить задание 6 для использования требований на размеры памяти вместо скорости.

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

3. Литература, пособия:

      1. Давыдов В.В., Сактоев В.Е., Хулукшинов  Р.Г. Программирование матричных  вычислений; Методические указания  к курсовому проектированию /ВСГТУ, Улан-Удэ, 1991. – 68 с.

      2. Давыдов В.В., Борисов Г.О. Программирование  матричных вычислений в электротехнических  задачах. Сборник алгоритмов решения  систем линейных уравнений: Методические  указания к практическим занятиям, курсовому проектированию и СРС /ВСГТУ, Улан-Удэ, 1996, 51с.

      3. А.А.Амосов, Ю.А.Дубинский, Н.В. Копченова.  Вычислительные методы для инженеров;  М., Высш. шк., 1994. – 544 с. 
 
 
 
 

Руководитель  проекта:     Кривошеин М.Ю. 

Задание принял к исполнению     _____________________

                                               (дата и подпись студента) 
 
 

 

Восточно-Сибирский  Государственный  Технологический

УНивЕРСИТЕТ 
 

Кафедра ЭСПП и СХ 
 
 

ДОПУЩЕН К ЗАЩИТЕ

Руководитель  проекта

Кривошеин М. Ю.

« _____ » ___________ 2007 год 
 
 

КУРСОВАЯ РАБОТА 

по курсу: Компьютерные технологии в электроэнергетике 

на тему: «Изучение программ решения систем

с ленточными матрицами» 
 
 
 
 

Студент второго  курса,

ст.гр._________  __________________________(Ф.И.О.) 
 
 
 
 
 
 

Улан-Удэ

2007

 

 
 
 
 
 
 
 
 

РАСЧЕТНО – ПОЯСНИТЕЛЬНАЯ 

ЗАПИСКА 
СОДЕРЖАНИЕ 

Введение

1. Теоретические аспекты  использованных методов

1. Прямые  методы решения систем линейных уравнений 

     1.2. Используемые алгоритмы  в виде псевдопрограмм

     1.2.1. Алгоритм А1.5 (BANSOLVE). Драйвер решения СЛУ с ленточной матрицей

     1.2.2. Алгоритм А1.5.1 (BANDECOMP). Триангуляция ленточной матрицы

     1.2.3 Алгоритм А1.5.2 (BANSLU).

2. Программная реализация

     2.1. Тексты программ

     2.2. Расчет размера оперативной памяти для размещения переменных

     2.3. Инструкция для пользователей

     2.4. Результаты тестирования программ с заданными входными данными

3. Вычислительные эксперименты

     3.1. Условия эксперимента

     3.2. Отчет о результатах.  Характеристические  профили.

     3.2.1 Скорость выполнения  программы

     3.2.2. Точность вычисления  программы 

Заключение

Список  использованной литературы

 

  Введение

 

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

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

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

 

1. Теоретические  аспекты использованных  методов

2. Прямые  методы решения систем линейных уравнений

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

     Пусть А – квадратная матрица порядка  n, - вектор, состоящий из n компонент:

         .

     Задача  состоит в решении системы  уравнений  . Рассмотрим метод исключения Гаусса.

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

     Вышеописанный алгоритм может быть представлен  в терминах матричного исчисления. левая и правая часть системы  последовательно умножается слева на ряд нижних треугольных матриц с единичной диагональю L₁, L₂, ..., L_n-1, таких, что матрица L_n-1...L₂L₁A становится верхней треугольной. Предположим, что элемент а₁₁ отличен от нуля и на первом этапе исключим элементы а₂₁, а₃₁, …, а_n1, складывая первую строку матрицы А с соответствующим множителем со строками 2,3,…,n. Очевидно, это равносильно умножению матрицы А на матрицу L₁ вида

     

 

     где . Матрица L₁A примет вид:

                       

где , i=2,n, j=i,n. Верхний индекс в скобках показывает число модификаций элементов.

      Процедура исключения элементов повторяется  многократно, т.е. на k-м этапе исключается часть k-го столбца, расположенная под диагональю. После n-1-го этапа получаем верхнюю треугольную матрицу

                  

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

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

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

1.2.1. Алгоритм А1.5 (BANSOLVE). Драйвер решения СЛУ с ленточной матрицей

Назначение: Решить Аx=b относительно х с ленточной матрицей А.

Входные параметры: machepsÎR, nÎZ, m1ÎZ – число диагоналей с ненулевыми элементами, расположенных под диагональю в матрице А; m2ÎZ – число диагоналей с ненулевыми элементами, расположенных над диагональю в матрице А.

Входно-выходные параметры: AÎR^n,m1+m2+1 – массив, состоящий из элементов ленточной матрицы (после разложения содержит нижний треугольный сомножитель L), вектор правых частей bÎRⁿ (после прямой и обратной подстановок содержит рещшение исходнйо системы).