Прямые методы решения систем линейных уравнений. Метод Крамера. Метод Гаусса. Метод прогонки

МИНОБРНАУКИ РОССИИ

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

высшего образования «Тульский государственный университет»

Кафедра вычислительной техники

Численные методы

Отчет по лабораторной работе №1

Прямые методы решения систем линейных уравнений. Метод Крамера. Метод Гаусса. Метод прогонки

Выполнил студент группы

Проверил

Тула 2021

ЦЕЛЬ И ЗАДАЧИ РАБОТЫ

Получить навык:

- анализа различных численных методов решения системы линейных алгебраических уравнений;

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

ЗАДАНИЕ НА РАБОТУ

1. Изучить метод прогонки и разработать его алгоритм.
2. Разработать ПО для решения СЛАУ методом прогонки.

ХОД РАБОТЫ

Математическое описание метода

Метод прогонки является модификацией метода Гаусса для частного случая разреженных систем — систем с матрицей трехдиагонального типа. Каноническая форма их записи такова

; i=1,…, n;    (1)[pic 1][pic 2]

или в развёрнутом виде:

[pic 3]

При этом, как правило, все коэффициенты  ≠ 0. Метод реализуется в два этапа — прямым и обратным ходами.[pic 4]

Прямой ход. Каждое неизвестное  выражается через [pic 5][pic 6]

   =   +  для i=1, 2, …, n-1       (2)[pic 7][pic 8][pic 9][pic 10]

посредством прогоночных коэффициентов  и . Определим алгоритм их вычисления. Для этого находим :[pic 11][pic 12][pic 13]

[pic 14]

Из уравнения (2) при i = 1 находим  =   ⋅  + . Следовательно,[pic 15][pic 16][pic 17][pic 18]

[pic 19](3)

Из второго уравнения системы определяем  через , подставляя найденное значение :[pic 20][pic 21][pic 22]

[pic 23]

откуда

[pic 24]

и согласно уравнению (2) при i = 2     =   +  , следовательно:[pic 25][pic 26][pic 27][pic 28]

[pic 29]

где   =  +   .[pic 30][pic 31][pic 32]

Ориентируясь на соотношения индексов при коэффициентах уравнений (3) и (4), можно получить эти соотношения для общего случая:

[pic 33]

где  (i = 2, 3, …, n - 1 ).[pic 34]

Обратный ход. Из последнего уравнения системы с использованием данных выражения (2) при i = n – 1

[pic 35]

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

[pic 39]        (5)

или хотя бы для одного  имеет место строгое неравенство (5), деление на «0» исключается и система имеет единственное решение. Заметим, что условие (5) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем метод прогонки может быть устойчивым и при несоблюдении условия (5).[pic 40]

Схема алгоритма метода прогонки имеет вид, представленный на рисунке 1.

Описание входных – выходных данных

Осуществляется переход в матрицу.

Входные данные: размерность матрицы n,  где n – целое число. Заполнение матрицы действительными числами, являющиеся коэффициентами уравнений.

Выходные данные: вектор ( , … , ) , где  , … ,  – решение системы уравнений; где n – целое число.[pic 41][pic 42][pic 43][pic 44]

Алгоритм расчета

[pic 45]

Рисунок 1 — Общая блок-схема метода прогонки

[pic 46]

[pic 47]

Рисунок 2 – Блок-схема проверки матрицы на трёхдиагональную