МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«БАРАНОВИЧСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» 
 
 
 
 
 
 
 

Факультет   Кафедра    
 
 

Дата регистрации работы в деканате    Дата регистрации работы на кафедре    Отметка о допуске к защите

_{Оценка за защиту} 

КУРСОВАЯ РАБОТА (КУРСОВОЙ ПРОЕКТ) 
 

_{по дисциплине}   

Тема: «  » 
 

Исполнитель: 

студент (факультет, курс, группа) 
 

фамилия, имя, отчество 
 
 
 

Руководитель: 

ученое  звание,  ученая  степень,  должность, 
 

фамилия, имя, отчество 
 
 
 
 
 
 
 
 
 

Барановичи 2011 год

Р Е Ф Е Р А Т 

Курсовая работа : 27с., 2 рис., 6 источников. 
 

КАЧЕСТВО, УПРАВЛЕНИЕ КАЧЕСТВОМ, СТАНДАРТЫ ИСО 9000,

ЗАТРАТЫ НА КАЧЕСТВО, КОНТРОЛЬ КАЧЕСТВА.

Объектом и предметом исследования является система линейных уравнений и её решение методом Гаусса.

 Цель работы: составить алгоритм решения СЛАУ методом Гаусса и реализовать его методами среды программирования Delphi.

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

В процессе работы проведены следующие исследования и разработки: исследование методов решения СЛАУ, разработка алгоритмов решения СЛАУ методом Гаусса. 
 

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

 Технико – экономическая и социальная значимость – алгоритм и его программная реализация позволяет снизить временные затраты на проведение сложных вычислений.

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

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

     Содержание

Введение                                                                                                                       4

1. Постановка задачи                                                                                                7
1. Условие задачи                                                                                                     7
2. Алгоритм решения системы линейных уравнений методом Гаусса             7
2. Анализ существующих методов решения задачи                                              9
1. Метод Гаусса (схема единственного деления)                                                   10
2. Метод Гаусса с выбором главного элемента                                                    13
3. Метод оптимального исключения                                                                     14
4. Сравнение прямых и итерационных методов                                                   16
3. Описание алгоритма                                                                                            18
4. Блок-схемы алгоритма                                                                                        19
5. Листинг программы                                                                                             22
6. Выполнение программы                                                                                     26

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

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

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

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

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

     Решение систем линейных алгебраических уравнений (СЛАУ) является одной из основных задач линейной алгебры. Эта задача имеет важное прикладное значение при решении научных и технических проблем. Кроме того, является вспомогательной при реализации многих алгоритмов вычислительной математики, математической физики, обработки результатов экспериментальных исследований.

     Применяемые на практике численные методы решения  СЛАУ делятся на две группы - прямые и итерационные.

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

     Итерационные  (или приближенные) методы являются бесконечными и находят решение системы как предел при k®¥ последовательных приближений x^(k), где k - номер итерации. Обычно задается точность e, и вычисления проводятся до тех пор, пока не будет выполнена оценка ºx^(k) – x^(k-1) º< e. Число итераций n(e), которое необходимо провести для получения заданной точности, для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных методов можно сравнивать по необходимому числу итераций n(e). Эти методы особенно предпочтительны для систем с матрицами специального вида - симметричными, трехдиагональными, ленточными и большими разреженными матрицами.

     Выбор среды программирования.

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

1. Постановка  задачи.
1. Условие задачи

Решить систему линейных уравнений  методом Гаусса

  20.9   1.2  2.1   0.9                       21.7

  1.2     21.2  1.5     2.5                       27.46

  2.1      1.5  19.8    1.3                       28.76

9.      2.5    1.3   32.12                     49.72    

2. Алгоритм  решения системы  линейных уравнений методом Гаусса
1. В одном цикле реализуются операции:

;      ;                                                 (1.1)

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

2. Вычисляется первый элемент вспомогательного вектора y:

                                                                                         (1.2)

3. Открывается цикл для , внутри которого производятся следующие вычисления:
• открывается цикл для , внутри которого вычисляется , причем для вычисления суммы создается вложенный цикл для и вводится вспомогательная переменная для временного хранения просуммированных данных (после каждого повторения цикла для эта переменная должна обнуляться).
• открывается цикл для , внутри которого вычисляется                                                              (1.3)
• , причем для вычисления суммы создается вложенный цикл для и вводится вспомогательная переменная для временного хранения просуммированных данных (эта переменная может быть той же, что и в предыдущем подпункте, но она должна быть предварительно обнулена и далее обнуляться после каждого повторения цикла для ).
4. В цикле для произвести вычисления остальных элементов вспомогательного вектора y по формуле:

                                                                     (1.4)

 Вычисление  суммы производится также, как  и в предыдущих пунктах (во  вложенном цикле для  )

5. Вычисляется .
6. Получим вектор искомых решений в цикле по формуле                                                                (1.5)

В этом случае для вычисления суммы необходимо открыть вложенный цикл для  .

  2. Анализ существующих методов решения задачи 

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

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

                                                       (2.1) 

  где x₁, x₂,..., x_n - неизвестные величины, b₁, b₂,..., b_n - элементы правой части. Если определитель системы отличен от нуля, то она имеет единственное решение. Для удобства дальнейших преобразований обозначим элементы правой части а_i(n+1) и запишем расширенную матрицу размерами n´(n+1), которая содержит всю информацию о системе:  

  A =                                                  (2.2) 

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

  Приведем  формальное описание схем некоторых прямых методов.

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

                                                   (2.3) 

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

                   ( 2.4) 

  и матрицу  размерами (n - k) (n - k+1), элементы которой вычисляются по формулам  

                (2.5)  

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

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

           (2.6) 

  Прямой  ход состоит из n - 1 шагов исключения.

  1-й  шаг. Целью этого шага является исключение неизвестного x₁ из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a₁₁ ¹ 0. Будем называть его главным элементом 1-го шага.

  Найдем  величины 

  q_i1 = a_i1/a₁₁   (i = 2, 3, …, n)                                                                         (2.7)  

  называемые  множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q₂₁, q₃₁, …, q_n1. Это позволит обратить в нуль коэффициенты при x₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему 

  a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

  a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

  a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n = b₃⁽¹⁾ ,                                                           (2.8)

  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

  a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n = b_n⁽¹⁾ . 

  в которой a_ij⁽¹⁾ и b_ij⁽¹⁾ вычисляются по формулам 

  a_ij⁽¹⁾ = a_ij − q_i1a_1j    ,    b_i⁽¹⁾ = b_i − q_i1b₁                                                            (2.9) 

  2-й  шаг. Целью этого шага является исключение неизвестного x₂ из уравнений с номерами i = 3, 4, …, n. Пусть a₂₂⁽¹⁾ ≠ 0, где a₂₂⁽¹⁾ – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага 

  q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾   (i = 3, 4, …, n)                                                                 (2.10) 

  и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q₃₂, q₄₂, …, q_m2. В результате получим систему 

        a₁₁x₁ + a₁₂x₂ +  a₁₃x₃ + … +  a_1nx_n =  b₁ ,

              a₂₂⁽¹⁾x₂ +  a₂₃⁽¹⁾x₃ + … +  a_2n⁽¹⁾ =  b₂⁽¹⁾ ,                   (2.11)

                    a₃₃⁽²⁾x₃ + … +  a_3n⁽²⁾x_n =  b₃⁽²⁾ ,                      

  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .                           

                    a_n3⁽²⁾x₃ + … +  a_nn⁽²⁾x_n =  b_n⁽²⁾ . 

  Здесь коэффициенты a_ij⁽²⁾ и b_ij⁽²⁾ вычисляются по формулам 

  a_ij⁽²⁾ = a_ij⁽¹⁾ – q_i2a_2j⁽¹⁾   ,    b_i⁽²⁾ = b_i⁽¹⁾ – q_i2b₂⁽¹⁾.                                                (2.12) 

  Аналогично  проводятся остальные шаги. Опишем очередной k-й шаг.

  k-й шаг. В предположении, что главный (ведущий) элемент k-го шага a_kk^(k–1) отличен от нуля, вычислим множители k-го шага 

  q_ik = a_ik^(k–1) / a_kk^(k–1)   (i = k + 1, …, n)                                                           (2.13) 

  и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на q_k+1,k, q_k+2,k, …, q_nk.

  После (n - 1)-го шага исключения получим систему уравнений 

        a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

              a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,                           (2.14)

                    a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

        .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                                a_nn^(n–1)x_n = b_n^(n–1) . 

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

  Обратный  ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_n–1. Осуществляя обратную подстановку, далее последовательно находим x_n–1, x_n–2, …, x₁. Вычисления неизвестных здесь проводятся по формулам 

  x_n = b_n^(n–1) / a_nn^(n–1),                                                                                        (2.15)

  x_k = (b_n^(k–1) – a_k,k+1^(k–1)x_k+1 – … – a_kn^(k–1)x_n) / a_kk^(k–1), (k = n – 1, …, 1). 

  Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы a_kk^(k–1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

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

  В методе Гаусса с выбором главного элемента по столбцу гарантируется, что |q_ik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk^(k-1). После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления. 

3. Метод оптимального исключения. В целях экономии оперативной памяти (примерно в 4 раза) операции прямого и обратного хода метода Гаусса выполняются попеременно. На первом шаге после приведения первого уравнения исключается неизвестное x₁ из второго уравнения, а затем с помощью приведенного второго уравнения - неизвестное x₂ из первого. После (k-1) таких шагов матрица системы имеет вид