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

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

Размещено на

Размещено на

Федеральное агентство по образованию

ФГОУ СПО «Уфимский авиационный техникум»

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

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

методом прогонки

по дисциплине «Численные методы»

Студент Д.Р. Мусакалимов

Руководитель работы Э.Р. Ахматсафина

Содержание

Введение

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

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

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

2. Постановка и решение задачи

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

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

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

3. Программная реализация

3.1 Блок-схема

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

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

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

Заключение

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

Введение

линейное уравнение гаусс алгоритм

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

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

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

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 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) имеем . Предположим, что для некоторого и докажем, что

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

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

Откуда

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

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



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

Более того

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

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

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

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

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

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

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

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

вместо