Разработка программных средств для решения СЛАУ методом прогонки

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 17.06.2017
Размер файла 449,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СТЕРЛИТАМАКСКИЙ ФИЛИАЛ

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

ВЫСШЕГО ОБРАЗОВАНИЯ

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

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

Кафедра математического моделирования

Курсовая работа

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

Стерлитамак 2017

ВВЕДЕНИЕ

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

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

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

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

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

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

система линейный алгебраический прогонка

ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа:

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

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

1.2 Метод прогонки

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

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

В общем случае системы линейных алгебраических уравнений с трехдиагональной матрицей имеют вид

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

Т.е. матрицу А можно записать

Идея метода прогонки состоит в следующем. Решение системы (1) ищется в виде

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

Выведем формулы для вычисления Из (3) можно получить

Подставляя имеющиеся выражения для в уравнение (1), приходим при к уравнению

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

А именно, достаточно положить

Для отыскания всех достаточно задать

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

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

(5)

Нахождение коэффициентов по формулам (4), (5) называется прямой прогонкой. После того, как прогоночные коэффициенты найдены, решение системи (1), (2) находится по рекуррентной формуле (3), начиная с Для начала счета по этой формуле требуется знать , которое определяется из уравнений

И равно

.

Нахождение по формулам

(6)

называется обратной прогонкой.

Алгоритм решения системы (1), (2) определяемый формулами (4)-(6) называется методом прогонки.

Метод прогонки можно применять, если знаменатели выражений (4), (6) не обращаются в нуль.

Покажем, что для возможности применения метод прогонки достаточно потребовать, чтобы коэффициенты системы (1), (2) удовлетворяли условиям

Сначала докажем по индукции, что при условиях (7), (8) модули прогоночных коэффициентов не превосходят единицы. Согласно (5), (8) имеем . Предположим, что для некоторого j и докажем, что

Прежде всего для любых двух комплексных чисел и докажем неравенство

Из неравенства треугольника имеем

Откуда

Вернемся теперь к доказательству , если . Согласно имеем оценку

а, используя (7) , получаем

т.е. знаменатели выражений (4) не обращаются в нуль.

Более того

Следовательно,

Далее, учитывая второе из условий (8) и только что доказанное неравенство , имеем

т.е. не обращается в нуль и знаменатель в выражении для .

К аналогичному выводу можно прийти и в том случае, когда условия (7), (8) заменяются условиями

Таким образом при выполнении условий (7), (8) (так же как и условий (9), (10)) система (1), (2) эквивалентна системе (4)-(6). Поэтому эти условия гарантируют существование и единственность решения системы (1), (2) и возможность нахождения этого решения методом прогонки.

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

Действительно, пусть в формуле (6) при вместо вычислена величина

Тогда на следующем шаге вычислений, т.е. при вместо

получим величину и погрешность окажется равной

Отсюда получаем, что ,т.е. погрешность не возрастает.

Подсчитаем число арифметических действий, выполняемых при решении задачи (1), (2) методом прогонки.

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

арифметических действий, т.е. число действий растет линейно относительно числа неизвестных

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

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

2.1 Формулировка задачи

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

)

2.2 Решение системы методом Гаусса

Дана система:

Преобразуем в матрицу:

Чтобы было легче работать, умножим каждый член матрицы на 100:

Преобразуем матрицу, умножив вторую строку на 3 и вычтем из третью строку:

Получим:

Далее, умножим первую строку на 5 и вычтем 21 умноженную на третью строку

Найдем сумму третьей строки умноженной на 92 и второй строки умноженной на 185

В результате преобразований данная система приводится к треугольному виду:

из последнего уравнения находим z:

подставляя это значение во второе уравнение, получаем:

из первого уравнения, подставив полученные значения, получим:

Выполним проверку подставим полученные значения x,y,z в первую строку данной матрицы:

0,63*0,376+0,05*0,777+0,15*0,427=0,34

0,05*0,376+0,34*0,777+0,1*0,427=0,32

0,15*0,376+0,1*0,777+0,71*0,427=0,42

Проверка выполнена.

2.3 Решение системы методом прогонки

Приведем матрицу к виду:

Матрица:

- умножим вторую строку на 15 и вычтем из нее первую строку:

- третью строку умножим на 5 и вычтем из нее третью строку:

Мы преобразовали матрицу к виду:

Вычислим значения прогоночных коэффициентов и :

т.к =0

Обратный ход

Вычислим значение :

Подставив в формулу значение , вычислим значение :

Подставив в формулу значение , вычислим значение :

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

3.1 Блок-схема

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

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

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

edtB1: TEdit;

lbl2: TLabel;

edtE1: TEdit;

lbl3: TLabel;

edtD1: TEdit;

edtE2: TEdit;

lbl4: TLabel;

edtB2: TEdit;

lbl5: TLabel;

edtD2: TEdit;

edtC2: TEdit;

lbl6: TLabel;

lbl7: TLabel;

edtD3: TEdit;

lbl8: TLabel;

edtB3: TEdit;

lbl9: TLabel;

edtC3: TEdit;

btn1: TButton;

lbl1: TLabel;

lbx: TLabel;

lby: TLabel;

lbz: TLabel;

procedure btn1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

// нажатие на "вычислить"

procedure TForm1.

btn1Click(Sender: TObject);

const

n=3; // размерность массивов и матриц

var

C, D, E : array of Real; //матрица уравнений

B : array of Real; // чему равны уравнения (первая часть)

Y : array of Real; // результат

I,k : Integer; // для циклов, перебора

ALF, BET : array of Real; // Alpha и Beta для предв. вычислений

znam : Real;

begin

{установим длины массивов}

SetLength(C,n);

SetLength(D,n);

SetLength(E,n);

SetLength(B,n);

SetLength(Y,n);

SetLength(ALF,n);

SetLength(BET,n);

{заполним массивы}

//главная диагональ (d):

d[0]:=strtofloat(edtD1.text);

d[1]:=strtofloat(edtD2.text);

d[2]:=strtofloat(edtD3.text);

//диагональ c (та что пониже d)

c[0]:=0;

c[1]:=strtofloat(edtC2.text);

c[2]:=strtofloat(edtC3.text);

//диагональ e (та что повыше d)

e[0]:=strtofloat(edtE1.text);

e[1]:=strtofloat(edtE2.text);

e[2]:=0;

//заполняем чему равны наши выражения

b[0]:=strtofloat(edtB1.text);

b[1]:=strtofloat(edtB2.text);

b[2]:=strtofloat(edtB3.text);

//проверим, можно ли считать этим способом:

k:=0;

for i:=0 to n-1 do

if Abs(d[i])>Abs(c[i])+abs(e[i]) then k:=k+1;

if k=0 then begin

ShowMessage('Данный способ не применим, т.к. условие диагонального преобладания матрицы не выполняется :( ');

Exit;

end;

{вычисление вспомогательных величин}

ALF[0]:= -(E[0]/D[0]);

BET[0]:= B[0]/D[0];

{прямой ход}

for I:= 1 to n - 1 do

begin

znam := d[i] + c[i]*ALF[i-1];

ALF[i]:= -(e[i]/znam);

BET[i]:= (-c[i]*BET[i-1]+b[i])/znam;

end;

{обратный ход, нахождение корней}

Y[n-1]:=(b[n-1]-c[n-1]*BET[n-2])/(d[n-1]+c[n-1]*ALF[n-2]);

for I:= n - 2 downto 0 do

Y[i]:=Y[i+1]*ALF[i]+BET[i];

//вывод результата

lbx.Caption:='X = ' + floattostr(Y[0]);

lby.Caption:='Y = ' + floattostr(Y[1]);

lbz.Caption:='Z = ' + floattostr(Y[2]);

end;

end.

3.3 Тестовый пример

В качестве тестового примера возьмем :

При ручном подсчете корни равны: x=-3 y=-7 z=-15

Рисунок 1. Результат работы программы

3.4 Решение задачи с помощью ЭВМ

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

Рисунок 2. Результат работы программы (метод прогонки)

ЗАКЛЮЧЕНИЕ

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

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

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

В ходе выполнения курсовой работы мы проделали ручной расчет заданного уравнения, выполнили расчет на языке программирования Delphi. Также мы выполнили тестовый пример для проверки метода прогонки.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Карманов В.Г. Математическое программирование. - М.: ФИЗМАТЛИТ 2008. -264 с.

2. Волков Е.А. Численные методы. - М.: Лань 2008. -256 с.

3. Пирумов У.Г. Численные методы. - М.: Изд-во Юрайт, 2012. -421 с.

4. Бахвалов Н.С., Лапин А.В., Чижонков Е.В. Численные методы в задачах и упражнениях. - М.: Бином Лаборатория знаний, 2016. -240 с.

5. Калиткин Н. Численные методы. -М.:БХВ СПБ,2011. -592 с.

Размещено на Allbest.ur

...

Подобные документы

  • Преобразование матрицы системы линейных алгебраических уравнений (СЛАУ) с помощью алгоритма Гаусса. Решение задачи методом простой итерации. Создание блок-схемы и текста программы для решения СЛАУ, реализованной на языке программирования Turbo Pascal.

    курсовая работа [1,2 M], добавлен 15.06.2013

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

    курсовая работа [1,6 M], добавлен 20.01.2010

  • Изучение систем линейных алгебраических уравнений (СЛАУ) с использованием табличного процессора MS Excel 2007. Пример решения системы линейных алгебраических уравнений методом Крамера. Прикладное программное обеспечение, применяемое для решения СЛАУ.

    курсовая работа [184,5 K], добавлен 20.11.2013

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

    курсовая работа [431,8 K], добавлен 15.06.2013

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

    курсовая работа [581,0 K], добавлен 15.06.2013

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

    курсовая работа [657,1 K], добавлен 09.01.2014

  • Решение нелинейных краевых задач. Входные данные и содержание алгоритма Бройдена. Содержание алгоритма Бройдена. Метод исключения Гаусса для решения СЛАУ. Вывод формулы пересчета Бройдена. Разработка программы, исследование результата и примеры ее работы.

    курсовая работа [912,3 K], добавлен 01.04.2010

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

    курсовая работа [25,0 K], добавлен 20.11.2008

  • Разработка программного продукта для решения систем линейных алгебраических уравнений методом Гаусса с помощью ЭВМ. Математическое описание объекта моделирования, начальные и граничные условия. Алгоритм реализации задачи. Использование модуля CRT.

    курсовая работа [269,6 K], добавлен 07.01.2016

  • Системы линейных алгебраических уравнений. Код программы для решения систем линейных алгебраических уравнений. Математические и алгоритмические основы решения задачи методом Гаусса. Программная реализация решения. Алгоритмы запоминания коэффициентов.

    лабораторная работа [23,5 K], добавлен 23.09.2014

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

    курсовая работа [610,7 K], добавлен 25.06.2012

  • Программный продукт для решения систем линейных уравнений методом Гаусса. Алгоритм для проведения вычислений. Цель разработки и область ее применения. Схема информационных потоков. Метод Гаусса: исключение неизвестных. Проектирование удобного интерфейса.

    курсовая работа [340,0 K], добавлен 02.07.2010

  • Отделение корней методом простых интеграций. Дифференцирование и аппроксимация зависимостей методом наименьших квадратов. Решение нелинейного уравнения вида f(x)=0 методом Ньютона. Решение системы линейных уравнений методом Зейделя и методом итераций.

    курсовая работа [990,8 K], добавлен 23.10.2011

  • Применение итерационных методов численного решения системы линейных алгебраических уравнений при вычислении на ЭВМ. Математические и алгоритмические основы решения задачи, метод Гаусса. Функциональные модели и блок-схемы, программная реализация решения.

    курсовая работа [527,5 K], добавлен 25.01.2010

  • Системы линейных алгебраических уравнений. Решение систем уравнений графическим способом. Разработка программного кода модуля, реализующего приближенное решение систем линейных уравнений графическим способом. Отладка программного модуля "Метод Гаусса".

    курсовая работа [858,5 K], добавлен 01.12.2013

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

    курсовая работа [939,4 K], добавлен 16.01.2014

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

    курсовая работа [428,9 K], добавлен 25.01.2010

  • Решение систем алгебраических линейных уравнений методом Гаусса. Вычисление обратной матрицы и определителя. Декомпозиция задачи. Схема взаимодействия интерфейсных форм. Описание процедур и функций. Тестирование разработанного программного продукта.

    курсовая работа [1,1 M], добавлен 05.06.2012

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

    курсовая работа [1,0 M], добавлен 27.09.2014

  • Изучение основных этапов проектирования программных систем, создание прикладной программы, которая выполняет решение систем линейных алгебраических уравнений методом Гаусса. Вычисление определителя и обращение матриц. Листинг разработанной программы.

    курсовая работа [563,3 K], добавлен 12.07.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.