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

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

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

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

Факультет  ________________инженерный__________________________________

____

Кафедра   __________информационные системы и технологии__________________

Дата регистрации работы в деканате    _________

Дата регистрации работы на кафедре   _________

Отметка о допуске к защите                    _________

Оценка за защиту                                                   _________

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

по дисциплине _     Основы алгоритмизации и программирования ___________

Тема:«Сравнение эффективности различных методов решения систем линейных алгебраических уравнений. Метод Гаусса и метод простой итерации»

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

студент 1 курса группы ИСТ-11_

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

Белясова Мария Дмитриевна__

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

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

преподаватель________________

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

Климко Елена Викторовна______

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

                                                              Барановичи 2011

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

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

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

РЕЦЕНЗИЯ

на курсовую работу

(регистрационный №_____)

Студента

_________Белясовой Марии Дмитриевны

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

Факультет __________инженерного_______________________________________

___________

Курс ___1______

Дисциплина

____________ Основы алгоритмизации и программирования

Рецензент

________ Климко Елена Викторовна

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

Дата получения к/р для рецензирования _____________________________________

Дата возвращения к/р после рецензирования _________________________________

Оценка______________ Подпись преподавателя-рецензента ____________________

Текст рецензии:

____________________________________________________________

___________

_________________________________________________

_________________________________________________

_________________________________________________

_________________________________________________

_________________________________________________

_________________________________________________

_________________________________________________

Р Е Ф Е Р А Т

     Курсовая работа: 34с., 1 рис., 4 источника

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

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

                            [pic]

     Цель работы: На языке программирования Delphi создать программу для нахождения корней системы линейных алгебраических уравнений указанными методами.

    При выполнении работы использованы методы:  метод Гаусса и метод простой итерации.

              ________________________

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ………………………………………………………………………6

1. Теоретическая часть ……………………………………………………….….8

     1.1 Постановка задачи ………………………………………………………8

     1.2 Теоретические сведения…………………………………………………..9

          1.2.1 Метод Гаусса …..............................................……..………………..9

          1.2.2 Метод простой итерации.......………………......…..……………...14

1.3 Блок-схемы алгоритмов программ (подпрограмм)…….……………..15

          1.3.1 Метод Гаусса …...............................................………………….…15

          1.3.2 Метод простой итерации…...............…………...………...............20

2. Практическая часть …………………………………………………….……26   2.1. Текст программы………………………………..…………………........26

2.2. Результаты (графическое представление результатов).………………32

ЗАКЛЮЧЕНИЕ ………………………………………………………………..33

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

5

Введение

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

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

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

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

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

5

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

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

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

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

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

5

1. Теоретическая часть

1.1 Постановка задачи

Решить систему линейных алгебраических уравнений:

              [pic]

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

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

5

Теоретические сведения

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

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

История

Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I в. до н.э. и II в. н. э.

Описание метода

Пусть исходная система выглядит следующим образом

[pic]

Матрица A называется основной матрицей системы, b — столбцом свободных членов.

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

[pic]

5

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

Тогда переменные  [pic]называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число [pic] , где i > r, то рассматриваемая система несовместна.

Пусть [pic]  для любых i > r.

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом  X ([pic], где i-номер строки)

[pic]

где

[pic]

Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.

Следствия:

1: Если в совместной системе все переменные главные, то такая система является определённой.

2: Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной.

5

Условие совместности

Упомянутое выше условие [pic] для всех  [pic] может быть сформулировано в качестве необходимого и достаточного условия совместности:

Напомню, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Алгоритм

Описание

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

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

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

5

переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.Метод Гаусса требует порядка O(n3) действий.

Этот метод опирается на:              Теорема (о приведении матриц к ступенчатому виду).

Любую матрицу путём элементарных преобразований только над строками можно привести к ступенчатому виду.

Простейший случай

В простейшем случае алгоритм выглядит так:

[pic]

Прямой ход:

[pic]

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

Применение и модификации

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:

нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: [pic], после чего [pic] приводится