Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки Российской федерации
Воронежский государственный технический университет
Кафедра высшей математики и физико-математического моделирования
Курсовая работа
По дисциплине: «Математика»
На тему:
«Метод Гаусса и его модификации для решения систем линейных уравнений»
Разработал студент: гр. МТЭ-111 Соловьев А.А.
Руководитель: Бондарев А.В.
Защита: Оценка:
Воронеж 2012
Замечания
Содержание
Задание на курсовую работу 4
1 Метод Гаусса. 5
2 Модификации метода гаусса 9
3 Решение системы уравнений методом Гаусса с выбором главного элемента 14
Список литературы 18
Министерство образования и науки Российской федерации
Воронежский государственный технический университет
Кафедра высшей математики и физико-математического моделирования
Задание на курсовую работу
По дисциплине: «Математика»
Вариант 1
Методом Гаусса с выбором главного элемента решить систему линейных уравнений:
1 Метод Гаусса.
Метод Гаусса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.
Пусть исходная система выглядит следующим образом
Матрица называется основной матрицей системы, — столбцом свободных членов.
Тогда согласно свойству элементарных преобразований над строками основную матрицу этой системы можно привести к ступенчатому виду(эти же преобразования нужно применять к столбцу свободных членов):
При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных [3].
Тогда переменные называются главными переменными. Все остальные называются свободными.
Если хотя бы одно число , где , то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.
Пусть для любых .
Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом (, где — номер строки):
,
где
Если свободным переменным системы придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой, то по теореме об эквивалентности при элементарных преобразованиях системы эквивалентны, то есть множества их решений совпадают.
Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.
На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.
На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.
Простейший случай
В простейшем случае алгоритм выглядит так:
Прямой ход:
Обратный ход. Из последнего ненулевого уравнения выражаем базисную переменную через небазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру для всех базисных переменных, получаем фундаментальное решение.
2 Модификации метода Гаусса.
Одной из модификаций метода Гаусса является метод Гаусса с выбором главного элемента по всей матрице.
В методе последовательного исключения Гаусса вычисления возможны, если ведущие элементы системы . Добиться выполнения этого условия можно, переставляя элементы строк и столбцов матрицы. Но среди ведущих элементов могут оказаться очень маленькие по абсолютной величине. При делении на такие ведущие элементы получается большая погрешность округления (вычислительная погрешность).
Чтобы избежать сильного влияния вычислительной погрешности на решение, применяется метод Гаусса с выбором главного элемента .
Рассмотрим систему . Запишем расширенную прямоугольную матрицу коэффициентов системы
.
Среди элементов матрицы выберем наибольший по модулю, называемый главным, элемент. Например, пусть им будет элемент . Строка с номером , содержащая главный элемент, называется главной строкой.
Далее вычисляем множители для всех .
Затем матрица преобразуется так: к каждой -й, неглавной строке, прибавим почленно главную строку, умножив её на . В результате получим матрицу, у которой все элементы-го столбца, за исключением , равны 0. Отбрасывая этот столбец и главную строку, получаем новую матрицу с меньшим на единицу числом строк и столбцов.
Над матрицей повторяем те же операции, после чего получаем матрицу и т.д. Эти преобразования продолжаются до тех пор, пока не получится матрица, содержащая одну строку из двух элементов, которая тоже считается главной. Затем объединяем все главные строки, начиная с последней. После некоторой перестановки они образуют треугольную матрицу, эквивалентную исходной. На этом заканчивается прямой ход метода Гаусса с выбором главного элемента.
Далее находим , решая систему с треугольной матрицей. Это обратный ход.
Следующей модификацией является метод прогонки.
Метод прогонки является частным случаем метода Гаусса и применяется к системам с трех-пятидиагональной матрицей . Такие системы часто встречаются при численном решении краевых задач для дифференциальных уравнений второго порядка, при моделировании некоторых инженерных задач. Примером подобной системы является система, которая получается при построении кубического сплайна .
Если при решении таких систем применять метод Гаусса, то расчет можно организовать таким образом, чтобы не включать нулевые элементы матрицы. Этим самым экономится требуемая память и уменьшается объем вычислений. Указанное ускорение вычислений допускают системы линейных алгебраических уравнений с ленточными, блочными,квазитреугольными, почти треугольными и другими матрицами .
Система уравнений равносильна соотношению
Метод прогонки основывается на предположении, что искомые неизвестные связаны рекуррентным соотношением:
где
Используя это соотношение, выразим xi-1 и xi через xi+1 и подставим в уравнение (1):
,
где Fi — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать
Отсюда следует:
Из первого уравнения получим:
После нахождения прогоночных коэффициентов и , используя уравнение (2), получим решение системы. При этом,
Другим способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению
c надиагональной (наддиагональной) матрицей
.
Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы и вектора , начиная с до
и
На втором этапе, для вычисляется решение:
Метод Жордана-Гаусса — метод, который используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе или отыскания ранга матрицы. Метод является модификацией метода Гаусса.
Алгоритм заключается в следующем:
Выбирают первый слева столбец матрицы, в котором есть хоть одно отличное от нуля значение.
Если самое верхнее число в этом столбце есть ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.
Все элементы первой строки делят на верхний элемент выбранного столбца.
Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.
Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.
После повторения этой процедуры раз получают верхнюю треугольную матрицу
Вычитают из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.
Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).
Чтобы получить обратную матрицу, нужно применить все операции в том же порядке к единичной матрице.
3. Решение системы линейных уравнений методом Гаусса с выбором главного элемента.
Определим совместна ли матрица для этого вычислим определитель:
Занулим элементы в первом столбце под первым элементом:
Занулим элементы во втором столбце под вторым элементом
Занулим элементы в третьем столбце под третим элементом
Система уравнений совместна и определена. Она имеет единственное решение.
Прямой ход:
Среди элементов данной матрицы выберем наибольший по модулю, называемый главный, элемент. Это будет 5.
Поменяем строку с главным элементом на первую строку.
Рассчитаем множители:
Вычтем главную строку из не главной строки, умножив главную строку на множитель, соответсвующей строки:
Далее отбрасываем главную строку и находим новый главный элемент. Это будет .
Находим множители для каждой строки:
Вычтем главную строку из не главной строки, умножив главную строку на множитель, соответсвующей строки:
Отбрасываем главную строку и ищем новый главный элемент. Это будет .
Находим множитель для последней строки: .
Вычтем главную строку из не главной строки, умножив главную на множитель, соответсвующей строки:
.
Обратный ход:
Получим следующие корни:
Подставим найденные корни в исходную систему уравнений:
Система уравнений решена правильно
Список литературы