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

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

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

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

УТВЕРЖДАЮ

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

_____________ 

« ____ » _____________ 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. Теоретические  аспекты использованных  методов

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

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

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

         .

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

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

     Вышеописанный алгоритм может быть представлен  в терминах матричного исчисления. левая и правая часть системы  последовательно умножается слева на ряд нижних треугольных матриц с единичной диагональю L1, L2, ..., Ln-1, таких, что матрица Ln-1...L2L1A становится верхней треугольной. Предположим, что элемент а11 отличен от нуля и на первом этапе исключим элементы а21, а31, …, аn1, складывая первую строку матрицы А с соответствующим множителем со строками 2,3,…,n. Очевидно, это равносильно умножению матрицы А на матрицу L1 вида

     

 

     где . Матрица L1A примет вид:

                       

где , 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ÎRn,m1+m2+1 – массив, состоящий из элементов ленточной матрицы (после разложения содержит нижний треугольный сомножитель L), вектор правых частей bÎRn (после прямой и обратной подстановок содержит рещшение исходнйо системы).

Выходные параметры: A_LÎRn,m1- массив, содержащий нижнюю треугольную матрицу, полученную при разложении матрицы А; intÎZn – целочисленный массив, содержащий информацию о перестановке строк, выполненных при приведении матрицы А к треугольной форме.

Код возврата: retcode=0 при успешном решении и retcode = 1 в противном случае.

Описание: Алгоритм реализует разложение матрицы с частичным выбором ведущего элемента с учетом ленточности матрицы. Для общности будем предполагать, что рассматриваемая ленточная матрица несимметрична, т.е. ненулевыми являются только элемента, для которых j>i+m2 и i>j+m1. Специальный алгоритм для обработки таких матриц состоит из N-1 основных шагов. На текущем k-ом шаге алгоритма исключаются поддиагональные элементы k-столбца. На текущем шаге алгоритма, кроме m1 последних шагов, исключается m1 ненулевых поддиагональных элементов. Текущий k-ый шаг алгоритма включает в себя следующие операции:

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

          ;

  1. перестановку строк с номерами k и int[k],
  2. вычисление величин

    M[i,k]=A[i,k]/A[k,k],|M[i,k]|<=1,

    после чего из каждой строки с номером  , где 1=min(n,k+mi), вычитается k-я строка, умноженная на коэффициент M[i,k].

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

Память: В алгоритме  матрица А представлена в виде массива А размера n x (m1+m2+1). При такой форме записи не удается использовать свойства симметрии, если матрица А ими обладает. Для удобства столбцы нового массива нумеруются от -m1 до m2, причем диагональные элементы исходной матрицы А расположены в столбце с номером 0. Расположение элементов в массиве А для случая n=7, m1=2, m2=1 показано ниже.

                  

Заметим, что  в первую, вторую и последнюю строки массива А требуется ввести нулевые  элементы.

В процессе разложения матрицы массив А перестраивается  таким образом, чтобы элементы, участвующие в текущем преобразовании, образовывали столбец. Соответствующее расположение элементов в массиве А непосредственно перед исключением переменных х1 и х2 показано ниже.

    

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

Алгоритм:

  1. retcode<=0
  2. CALL BANDECOMP (n,m1,m2,macheps,A,A_L,int,retcode)

    {Алг. А1.5.1}

  1. IF retcode=0 THEN {разложение успешно}

    CALL BANSLU(n,m1,m2,A,A_L,int,b) {Алг. А1.5.2}

{RETURN для алг. A1.5)

{END для Алг. A1.5)

 

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

Назначение: Находит разложение ленточной матрицы в виде произведения нижней L и верхней U треугольных матриц.

Входные параметры: nÎZ, m1ÎZ, m2ÎZ, machepsÎR.

bÎRn , L и U в массиве АÎRn,n; intÎZn, A0ÎRn.

Входно-выходные параметры: АÎRn,m1+m2+1 – массив, состоящий из элементов ленточной матрицы (после разложения содержит нижний треугольный сомножитель L).

Выходные параметры: АÎRn,m1 – массив, содержащий нижнюю треугольную матрицу L, полученную при разложении матрицы А; intÎZn – целочисленный массив, содержащий информацию о перестановке строк, выполненных при приведении матрицы А к треугольной форме.

Код возврата: : retcode=0 при успешном решении и retcode = 1 – если матрица вырождена.

Память: Исходная ленточная матрица А порядка n записана в виде массива A[1..n,-m1..m2] размера n x (m1+m2+1). Полученная из нее матрица разлагается на произведение нижней и верхней треугольных матриц с использованием перестановки строк. Ненулевые элементы нижней треугольной матрицы хранятся в массиве A_L[1..n,1..m1], а ненулевые элементы верхней треугольной матрицы записываются в массив А. Массив Int[1..n] содержит информацию о перестановках строк при разложении матрицы А.

Алгоритм:

{подготовка к первому шагу}

1.l <=m+1

2. FOR i=1 TO m1 DO

      2.1 FOR  j=l-1 TO m2 DO

      A[i,j-1]<=A[i,j]

      2.2. l <= l-1

      2.3. FOR j=m2-l TO m2 DO

      A[i,j]<=0

{Гауссово исключение с частичным выбором ведущего элемента}

3. l<=m1

FOR k=1 TO n DO

4.1 x<=A[k,-m1]

4.2 i<=k

4.3 IF l<k THEN

l<=l+1

4.4 FOR j=k+1 TO l DO

     4.4.1 IF |A[j,-m1]|>|x| THEN

           4.4.1.1 x<=|A[j,-m1]|

           4.4.1.2 i<=j

4.5 int[k]<=i

{проверка на вырожденность}

4.6 IF x<macheps THEN

      4.6.1 retcode<=1

      4.6.2 RETURN

4.7 IF i<>k THEN

{перестановка строк i и k}

      4.7.1 FOR j=-m1 TO m2 DO

      переставить местами A[k,j] и A[i,j]

4.8 FOR i=k+1 TO l DO

      4.8.1 x<=A[i,-m1]/A[k,-m1]

      4.8.2 A_L[k,i-k]<=x

      4.8.3 FOR j=1-m1 TO m2 DO

      A[i,j-1]<=A[i,j]-x*A[k,j]

      4.8.4 A[i,m1]<=0

{RETURN для Алг. A1.5.1}

{END для Алг. A1.5.1}

 

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

Решение СЛУ  Ax=b относительно х с ранее триангулированной ленточной матрицы A=LU

Назначение: Ищется решение СЛУ Ax=b, где матрица предварительно разложена на треугольные с помощью алгоритма А1.5.1.

Входные параметры: nÎZ, m1ÎZ, m2ÎZ, АÎRn,m1+m2+1 – массив, содержащий верхнюю треугольную матрицу U разложения для исходной матрицы А; A_L ÎRn,m1 – массив, содержащий нижнюю треугольную матрицу L, полученную при разложении матрицы А; intÎZn.

Входно-выходные параметры: вектор правых частей bÎRn (после прямой и обратной подстановок содержит решение исходной системы).

Алгоритм:

1. i<=m1

{прямая подстановка}

2. FOR k=1 TO n DO

      2.1 i<=int[k]

      2.2 IF i<>k THEN

      l<=l+1

      2.4 FOR i=k+1 TO l DO

      b[i]<=b[i]-A_L[k,i-k]*b[k]

{обратная подстановка}

3. l<=-m1

4. FOR i=n DOWNTO 1 TO

      4.1

      4.2 IF l<m2 THEN

      l<=l+1

{RETURN для Алг. A1.5.2}

{END для Алг. A1.5.2}

 

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

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

program Kraut;

uses crt,dos;

const nn=40;

mm1=20;

mm2=20;

type

   matr=array[1..nn,-mm1..mm2] of real;

   matr0=array[1..nn,1..nn] of real;

   vect=array[1..nn] of real;

   vect0=array[1..nn] of integer;

var

   a,a_l:matr;

   a0: matr0;

   x,y,b:vect;

   int: vect0;

   retcode,i,j,k,N,m,m1,m2:integer;

   macheps,max,delta:real;

   hour,minute,second,sot:word;

   hour0,minute0,second0,sot0:word; 

{пpоцедуpа генеpации матpицы}

procedure GenMatr(var a0:matr0;var b:vect;m1,m2,n: integer);

var

   p: real;

   kod: integer;

function Urand (kod: integer):real;

label 10,20,99;

const itwo=2;

      ia:integer=0;

      ic:integer=0;

      mic:integer=0;

      iy:integer=0;

      m2:integer=0;

      s:real=0;

var

      m:integer;

      halfm:real;

begin

   if kod<0 then begin

   m2:=0;

   goto 99;

   end;

   if m2<>0 then goto 20;

   m:=1;

   iy:=kod;

   10:m2:=m;

   m:=itwo*m2;

   if m>m2 then goto 10;

   halfm:=m2;

   ia:=trunc (halfm*arctan(1.0)/8.0)+5;

   ic:=trunc (halfm*(0.5-sqrt(3.0)/6.0)+1);

   mic:=(m2-ic)+m2;

   s:=0.5/halfm;

   20:iy:=iy*ia;

   if iy>mic then iy:=(iy-m2)-m2;

   iy:=iy+ic;

   if iy/2>m2 then iy:=(iy-m2)-m2;

   if iy=0 then iy:=(iy+m2)+m2;

   99: urand:=iy*s;

end;

begin

  write ('Код генерации матрицы - ');

  readln (kod);

  p:=urand(-1); 

{фоpмиpование матpицы  A}

       for i:=1 to n do begin

         for j:=1 to n do begin

             if (j>i+m2) or (i>j+m1) then a0[i,j]:=0

             else a0[i,j]:=urand(kod);

             write (a0[i,j]:6:2);

         end;

         writeln;

         end;

{фоpмиpование вектоpа b}

  for i:=1 to n do begin

    b[i]:=0;

    for j:=1 to n do

      b[i]:=b[i]+a0[i,j];

  end; 

  write ('>...');

  readkey;

end; 

{Пpоцедуpа генеpации матpицы 4}

procedure Matrix4(var a0: matr0;var b:vect;m1,m2,n:integer);

var alfa: real;

begin

  clrscr;

  alfa:=5;

{Данный алгоритм  производит формирование матрицы}

  for i:=1 to n do begin

    for j:=1 to n do begin

             if (j>i+m2) or (i>j+m1) then a0[i,j]:=0

             else  if i=j then a0[i,j]:=alfa

             else a0[i,j]:=1; 

             write (a0[i,j]:6:2);

    end;

    writeln;

    end;

{Формирование  вектора b как суммы элементов  по строкам матрицы}

  for i:=1 to n do

   begin

    b[i]:=0;

    for j:=1 to n do

        b[i]:=b[i]+a0[i,j];

   end;

  write ('>...');

  readkey;

Изучение программ решения систем с ленточными матрицами 📙 Курсовая → 🆔 85957

Изучение программ решения систем с ленточными матрицами 📙 Курсовая → 🆔 85957

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