Решение системы линейных уравнений - Программирование, компьютеры и кибернетика курсовая работа

Характеристика методов решений систем линейных алгебраических уравнений, основные виды численных методов и применение программного продукта Delphi 5.0 как наиболее эффективного. Сущность методов Гаусса, Гаусса-Жордана и Якоби, особенности метода Зейделя.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Министерство образования и науки Республики Беларусь
Белорусский государственный университет
Факультет информационных технологий и управления
Кафедра Вычислительных Методов и Программирования
Итерационные (или приближенные) методы являются бесконечными и находят решение системы как предел при k последовательных приближений x ( k ) , где k - номер итерации. Обычно задается точность и вычисления проводятся до тех пор, пока не будет выполнена оценка x ( k ) - x ( k -1) < . Число итераций n (), которое необходимо провести для получения заданной точности, для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных методов можно сравнивать по необходимому числу итераций n (). Эти методы особенно предпочтительны для систем с матрицами специального вида - симметричными, трехдиагональными, ленточными и большими разреженными матрицами.
После проведенного обзора программных средств мы выбрали среду программирования наиболее подходящую нам как очень удобное средство для разработки данного программного продукта. DELPHI 5.0 является наиболее выгодной нам средой программирования.
1. Анализ суще ствующих методов решения задачи
Прямые методы решения СЛАУ. К прямым (или точным) методам решения СЛАУ относятся алгоритмы, которые в предположении, что вычисления ведутся без округлений, позволяют получить точное решение системы за конечное число арифметических действий. Чаще всего решение задач такими методами осуществляется поэтапно: на первом этапе систему преобразуют к тому или иному простому виду, на втором - решают упрощенную систему и получают значения неизвестных.
Запишем систему линейных алгебраических уравнений в развернутом виде:
где x 1 , x 2 ,..., x n - неизвестные величины, b 1 , b 2 ,..., b n - элементы правой части. Если определитель системы отличен от нуля, то она имеет единственное решение. Для удобства дальнейших преобразований обозначим элементы правой части а i ( n +1 ) и запишем расширенную матрицу размерами n ( n +1) , которая содержит всю информацию о системе:
С этой матрицей можно обращаться так же, как и с системой - переставлять строки, прибавлять кратное одной строки к другой, исключая неизвестные и приводя матрицу к треугольному или диагональному виду.
Приведем формальное описание схем некоторых прямых методов.
Метод Гаусса (схема единственного деления). Алгоритм метода состоит из двух этапов. Первый этап называется прямым ходом метода и заключается в последовательном исключении неизвестных из уравнений, т.е. в приведении матрицы А к верхнему треугольному виду (ниже главной диагонали все нули). Для этого на первом шаге разделим первое уравнение системы на а 11 (предположим, что коэффициент а 11 0, в противном случае осуществляем перестановку уравнений системы). Обозначим коэффициенты полученного приведе н ного уравнения , домножим его на коэффициент а 21 и вычтем из второго уравнения системы, исключая тем самым х 1 из второго уравнения (обнуляя коэффициент а 12 матрицы). Поступим аналогично с остальными уравнениями и получим новую систему, матрица которой в первом столбце, кроме первого элемента, содержит только нули, т.е.
Первое уравнение в дальнейших преобразования не участвует. Описанный выше процесс исключения неизвестных применим к матрице размерами ( n -1) n . После k аналогичных шагов получим k приведенных уравнений с коэффициентами
и матрицу размерами ( n - k ) ( n - k +1), элементы которой вычисляются по формулам
Элементы , на которые осуществляется деление, называются ведущими элементами метода Гаусса и не должны равняться нулю. Прямой ход метода Гаусса заканчивается после n шагов определением .
Обратный ход метода Гаусса заключается в последовательном определении компонент решения, начиная с х n и заканчивая х 1 , по следующим формулам:
Метод Гаусса с выбором главного элемента . Метод заключается в том, что при прямом ходе в алгоритме метода Гаусса на каждом шаге исключения производится выбор наибольшего по модулю элемента в качестве ведущего . Этого достигают перестановкой строк или столбцов матрицы коэффициентов. Наиболее распространённой в вычислительной практике является стратегия выбора главного элемента столбца - нахождение максимального по модулю элемента k - го столбца матрицы и использование его в качестве ведущего элемента на k -м шаге исключения. В этом случае для невырожденных систем гарантируется, что ведущие элементы не равны нулю, и уменьшается погрешность при делении и последующем вычитании при преобразованиях. Рекомендуется также масштабировать предварительно каждое уравнение исходной системы, разделив на его наибольший по абсолютной величине коэффициент. Это делает рост элементов промежуточных матриц ограниченным.
Метод оптимального исключения. В целях экономии оперативной памяти (примерно в 4 раза) операции прямого и обратного хода метода Гаусса выполняются попеременно. На первом шаге после приведения первого уравнения исключается неизвестное x 1 из второго уравнения, а затем с помощью приведенного второго уравнения - неизвестное x 2 из первого. После ( k -1) таких шагов матрица системы имеет вид
На k - м шаге, используя первые k уравнений, исключаем неизвестные x 1 ,..,x k из ( k +1) -го уравнения. Затем посредством этого уравнения исключается неизвестное x k+1 из первых k уравнений и т.д. В результате прямого хода матрица системы приводится к диагональному виду с единицами на главной диагонали. При этом отпадает необходимость обратного хода, поскольку столбец правой части приведенной матрицы и является вектором решения.
Метод Гаусса-Жордана. Эта модификация метода Гаусса незначительно отличается от метода оптимального исключения. Операции исключения переменных для каждого приводимого уравнения осуществляют не только ниже, но и выше главной диагонали. Операции с первым уравнением системы полностью аналогичны стандартной схеме. Второе уравнение системы после приведения и домножения на соответствующие коэффициенты вычитаем не только из третьего и последующих уравнений, но и из первого. В результате k таких шагов получаем матрицу
Как и в методе оптимального исключения, матрица системы приводится к диагональному виду и вектором решения является столбец .
LU - разложение . Матрицу A можно представить в виде произведения нижней треугольной матрицы (включая диагональ) L (lower) и верхней треугольной матрицы U ( upper ) , т.е. A = LU . Это равенство равносильно n 2 числовым равенствам
Разложение матрицы A на множители обычно получают посредством алгоритма, который называется компактной схемой метода Гаусса. Элементы l i m и U m i могут быть вычислены по формулам
Тогда решение системы Ax=b сводится к последовательному решению двух систем - Ly=b и Ux=y.
Рассмотренный метод можно применять к решению серии систем с одной и той же матрицей.
Для решения итерационным методом система линейных алгебраических уравнений Ax = b должна быть приведена к виду x = Gx + f , где G - некоторая матрица, f - преобразованный вектор свободных членов. Затем выбирается начальное приближение - произвольный вектор x (0) - и строится рекуррентная последовательность векторов x (1) , x (2) ,..., x ( k ) ,... по формуле
Для сходимости этой последовательности при любом начальном приближении необходимо и достаточно , чтобы все собственные значения матрицы G были по абсолютной величине меньше единицы. На практике это трудно проверить, и обычно пользуются достаточными условиями сходимости - итерации сходятся, если какая-нибудь норма матрицы меньше единицы, т.е.
Чем меньше норма матрицы G , тем быстрее сходится итерационный процесс.
Преобразование системы можно осуществить, просто решая каждое i -е уравнение относительно x i :
Метод Якоби использует следующий алгоритм построения приближений:
Если A - матрица с доминирующей диагональю, т.е. , то метод Якоби сходится при любом начальном приближении x (0 ) .
Метод Якоби относится к одношаговым итерационным методам , когда для нахождения x ( k +1 ) требуется помнить только одну предыдущую итерацию x ( k ) . Для исследования сходимости удобнее записывать итерационные методы не в координатной, а в матричной форме, придерживаясь стандартной формы записи итерационных методов.
Канонической формой одношагового итерационного метода решения СЛАУ называется его запись в виде
где B k+1 - матрица, задающая тот или иной итерационный метод, k+1 - итерационный параметр. Числовые параметры k вводят для ускорения сходимости. Способ выбора итерационных параметров определяется при исследовании сходимости метода, когда выясняется при каких значениях параметров метод сходится и когда сходимость будет наиболее быстрой (соответствующие параметры называются оптимальными).
Итерационный метод называют явным , если B k+1 - единичная матрица. Неявные итерационные методы имеет смысл применять лишь в том случае, когда решение системы уравнений с матрицей B k требует меньше машинной памяти или времени или алгоритмически проще, чем решение исходной системы.
Методом простой итерации называют явный метод с постоянм параметром
где r ( k ) = Ax ( k ) - b - вектор невязки . Метод сходится для симметричных положительно определенных матриц при .
Для окончания итерационного процесса используют три способа. При первом определяют величину стабилизации и прекращают вычисления, если она меньше , т.е.
Недостатком этого способа является то, что при медленно сходящихся итерациях величина стабилизации может быть малой, хотя приближенное решение сильно отличается от точного.
При втором способе вычисляют нормы невязки до начала итераций и на каждой итерации. Итерации прекращают при выполнении неравенства
При третьем способе предварительно оценивается число итераций, необходимое для получения заданной точности . Если для погрешности итерационного метода выполняются оценки
где q (0,1), то метод сходится со скоростью геометрической прогрессии со знаменателем q . Можно определить, потребовав, чтобы q n < , число итераций n , достаточное для того, чтобы начальная погрешность уменьшилась в заданное число раз:
Целая часть числа n 0 ( ) является минимальным числом итераций, нео б ходимым для получения заданной точности .
Величина ln(1/ q ) является скоростью сходимости итерационного метода .
Для решения методом Зейделя система линейных алгебраических уравнений Ax = b должна быть приведена к виду x = Gx + f , где G - некоторая матрица, f - преобразованный вектор свободных членов. Затем выбирается начальное приближение - произвольный вектор x (0) - и строится рекуррентная последовательность векторов x (1) , x (2) ,..., x ( k ) ,... по формуле
Для сходимости этой последовательности при любом начальном приближении необходимо и достаточно , чтобы все собственные значения матрицы G были по абсолютной величине меньше единицы. На практике это трудно проверить, и обычно пользуются достаточными условиями сходимости - итерации сходятся, если какая-нибудь норма матрицы меньше единицы, т.е.
Чем меньше норма матрицы G , тем быстрее сходится итерационный процесс.
Преобразование системы можно осуществить, просто решая каждое i -е уравнение относительно x i :
Метод Зейделя использует следующий алгоритм построения приближений:
Если A - матрица с доминирующей диагональю, т.е. , то метод Зейделя сходится при любом начальном приближении x (0 ) .
Метод Зейделя сходится примерно так же, как геометрическая прогрессия со знаменателем || G | | . Если норма матрицы G близка к 1, то скорость сходимости очень медленная. Для ускорения сходимости используется метод релаксации . Суть его в том, что полученное по методу Зейделя очередное значение пересчитывается по формуле:
Здесь 0<2 - параметр релаксации. Если <1 - нижняя релаксация , если >1 - верхняя релаксация . Параметр подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.
Метод Зейделя является одношаговым итерационным методам , когда для нахождения x ( k +1 ) требуется помнить только одну предыдущую итерацию x ( k ) .
Погрешность итерации вычисляется по формуле:
Если меньше заданной точности , то итерационный процесс прекращают.
Элементы главной диагонали называются главными. Заметим, что если в ходе расчётов по данному алгоритму на главной диагонали окажется нулевой элемент, то произойдет сбой программы. Для того, чтобы избежать этого, следует перестановку строк таким образом, чтобы на главной диагонали находились максимальные элементы строк. Т. е., если в k-й строке максимальным является i-й элемент, необходимо поменять местами k-ю и i-ю строки, и поменять местами соответствующие элементы вектора b. Такой выбор главного элемента необходим для сходимости итерационного процесса.
Приведём блок-схему реализации данного метода:
Сущность метода Гаусса при решении систем линейных уравнений. Элементарные преобразования этого метода. Краткое описание среды визуальной разработки Delphi. Описание основных применяемых процедур и алгоритм роботы программы по решению уравнений. курсовая работа [1,1 M], добавлен 29.08.2010
Метод Гаусса-Зейделя как модификация метода Якоби, его сущность и применение. Разработка программы решения системы линейных алгебраических уравнений на языке VB, проверка правильности работы программы в MS Excel и математических пакетах MathCad и MatLab. курсовая работа [325,5 K], добавлен 27.10.2013
Использование MS Excel для математических расчетов. Описание численных методов решения системы линейных алгебраических уравнений. Решение систем линейных алгебраических уравнений с методами Крамера и Зейделя и с помощью табличного процессора MS Excel. курсовая работа [1,6 M], добавлен 14.02.2021
Системы линейных алгебраических уравнений. Решение систем уравнений графическим способом. Разработка программного кода модуля, реализующего приближенное решение систем линейных уравнений графическим способом. Отладка программного модуля "Метод Гаусса". курсовая работа [858,5 K], добавлен 01.12.2013
Применение итерационных методов численного решения системы линейных алгебраических уравнений при вычислении на ЭВМ. Математические и алгоритмические основы решения задачи, метод Гаусса. Функциональные модели и блок-схемы, программная реализация решения. курсовая работа [527,5 K], добавлен 25.01.2010
Разработка программного продукта для решения систем линейных алгебраических уравнений методом Гаусса с помощью ЭВМ. Математическое описание объекта моделирования, начальные и граничные условия. Алгоритм реализации задачи. Использование модуля CRT. курсовая работа [269,6 K], добавлен 07.01.2016
Рассмотрение двух способов решения систем линейных алгебраических уравнений: точечные и приближенные. Использование при программировании метода Гаусса с выбором главного элемента в матрице и принципа Зейделя. Применение простой итерации решения уравнения. курсовая работа [879,8 K], добавлен 05.06.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Решение системы линейных уравнений курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа: Проблемы разработки и реализации финансовой политики муниципального образования РФ
Рефераты По Дисциплине Педагогика
Курсовая работа по теме Влияние токсических веществ на загрязнение почвы
Монтаж электрооборудования
Реферат: Маас-Рейнская операция
Курсовая работа: Особенности отбора предметного содержания при изучении химии в средней школе
Реферат: Курс 4 Специальность Фик группа
Реферат: по дисциплине “основы предпринимательства” на тему: “
Реферат: Программы системы 1С: Предприятие. Администрирование в программах 1С: Предприятие
Дипломная работа по теме Внутренний контроль на предприятии. Внедрение системы внутреннего контроля бухгалтерского учета экон...
Дипломная работа по теме Описание работы электрической схемы охранного устройства с автодозвоном по телефонной линии
Дипломная работа: Обоснование необходимости реконструкции ОАО "ФанДОК"
Сочинение По Тексту Гроссмана Солдаты Лежали
Доклад: Жмайло, Марк
Безопасность Строительства Курсовая
Эссе Осенний Лес
Ответ на вопрос по теме Охрана природы (Шпаргалка)
Реферат: Государство и рыночная экономика. Скачать бесплатно и без регистрации
Курсовая работа по теме Промывочные жидкости в разведочном бурении
Почему Я Не Отличник Сочинение
Жизнь и творчество И.А. Бунина - Литература презентация
Эритроцитурия - Медицина презентация
Национальный музей Прадо - Культура и искусство статья