Поиск решений системы линейных уравнений методом Гаусса (стр. 2 из 3)

· Преобразование первого рода: две строки матрицы меняются местами, и при этом знаки всех элементов одной из строк изменяются на противоположные.

· Преобразование второго рода: к одной строке матрицы прибавляется другая строка, умноженная на произвольное число.

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

Метод Гаусса в математическом варианте состоит в следующем:

1. ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее. Если нашли ненулевой элемент в k-й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k-ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля;

2. используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент a_k1/a₁₁.

3. переходим ко второму столбцу (или j-му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.

Программистский вариант метода Гаусса имеет три отличия от математического:

1. индексы строк и столбцов матрицы начинаются с нуля, а не с единицы;

2. недостаточно найти просто ненулевой элемент в столбце. В программировании все действия с вещественными числами производятся приближенно, поэтому можно считать, что точного равенства вещественных чисел вообще не бывает. Некоторые компиляторы даже выдают предупреждения на каждую операцию проверки равенства вещественных чисел. Поэтому вместо проверки на равенство нулю числа a_ijследует сравнивать его абсолютную величину _ij с очень маленьким числом ε (например, ε = 0.00000001). Если _ij=< ε, то следует считать элемент a_ijнулевым;

3. при обнулении элементов j-го столбца, начиная со строки i + 1, мы к k-й строке, где k > i, прибавляем i-ю строку, умноженную на коэффициент r = -a_kj/a_ij:

Такая схема работает нормально только тогда, когда коэффициент r по абсолютной величине не превосходит единицы. В противном случае, ошибки округления умножаются на большой коэффициент и, таким образом, экспоненциально растут. Математики называют это явление неустойчивостью вычислительной схемы. Если вычислительная схема неустойчива, то полученные с ее помощью результаты не имеют никакого отношения к исходной задаче. В нашем случае схема устойчива, когда коэффициент r = -a_kj/a_ijне превосходит по модулю единицы. Для этого должно выполняться неравенство Отсюда следует, что при поиске разрешающего элемента в j-м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине. Если он по модулю не превосходит ε, то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.

Основная идея метода Гаусса- привести матрицу систему к диагональному виду, то есть все элементы главной диагонали –нули. Для приведения матрицы к такому виду, мы выбираем самую верхнюю строку матрицы, и вычитаем её из всех остальных строк, умножив её для каждой строки на некий коэффициент, так, что самый левый столбец ниже главной диагонали заполнен нулями. Вычитаемая с коэффициентом строка называется текущей строкой. Выбирая текущую строку вначале верхнюю, а потом всё ниже и ниже, мы добьёмся, что все элементы ниже главной диагонали будет равны нулю. Эту часть метода- обработка строк по текущей строке и предстоит распараллеливать.

Суть метода заключается в последовательном исключении неизвестных. Рассмотрим систему линейных уравнений:

Разделим обе части 1–го уравнения на a₁₁ 0, затем: 1) умножим на а₂₁ и вычтем из второго уравнения 2) умножим на а₃₁ и вычтем из третьего уравнения и т.д. Получим:, где d_1j = a_1j/a₁₁, j = 2, 3, …, n+1.d_ij= a_ij – a_i1d_1ji = 2, 3, … , n; j = 2, 3, … , n+1. Далее повторяем эти же действия для второго уравнения системы, потом – для третьего и т.д.

Пример. Решить систему линейных уравнений методом Гаусса.

Составим расширенную матрицу системы.

А* =

Таким образом, исходная система может быть представлена в виде:

,

откуда получаем:x₃ = 2;x₂ = 5;x₁= 1.

Пример. Решить систему методом Гаусса.

Составим расширенную матрицу системы.

Таким образом, исходная система может быть представлена в виде:

,

откуда получаем: z = 3; y = 2;x =1.

Работа с файлами.

Стандартная библиотека С++ содержит набор функций для работы с файлами. Эти функции описаны в стандарте ANSI. Отметим, что файловый ввод-вывод не является частью языка С+, и ANSI-функции - не единственное средство ввода-вывода. Так, в операционной системе Unix более популярен другой набор функций ввода-вывода, который можно использовать не только для работы с файлами, но и для обмена по сети. В C++ часто используются библиотеки классов для ввода-вывода. Тем не менее, функции ANSI-библиотеки поддерживаются всеми С++-компиляторами, и потому программы, применяющие их, легко переносятся с одной платформы на другую. Прототипы функций ввода-вывода и используемые для этого типы данных описаны в стандартном заголовочном файле "stdio.h.

Открытие файла: функция fopen.

Для доступа к файлу применяется тип данных FILE. Это структурный тип, имя которого задано с помощью оператора typedef в стандартном заголовочном файле "stdio.h". Программисту не нужно знать, как устроена структура типа файл: ее устройство может быть системно зависимым, поэтому в целях переносимости программ обращаться явно к полям структуры FILE запрещено. Тип данных "указатель на структуру FILE используется в программах как черный ящик: функция открытия файла возвращает этот указатель в случае успеха, и в дальнейшем все файловые функции применяют его для доступа к файлу.

Здесь path - путь к файлу (например, имя файла или абсолютный путь к файлу), mode - режим открытия файла. Строка mode может содержать несколько букв. Буква "r" (от слова read) означает, что файл открывается для чтения (файл должен существовать). Буква "w" (от слова write) означает запись в файл, при этом старое содержимое файла теряется, а в случае отсутствия файла он создается. Буква "a" (от слова append) означает запись в конец существующего файла или создание нового файла, если файл не существует.

В некоторых операционных системах имеются различия в работе с текстовыми и бинарными файлами (к таким системам относятся MS DOS и MS Windows; в системе Unix различий между текстовыми и бинарными файлами нет). В таких системах при открытии бинарного файла к строке mode следует добавлять букву "b" (от слова binary), а при открытии текстового файла -- букву "t" (от слова text). Кроме того, при открытии можно разрешить выполнять как операции чтения, так и записи; для этого используется символ + (плюс). Порядок букв в строке mode следующий: сначала идет одна из букв "r", "w", "a", затем в произвольном порядке могут идти символы "b", "t", "+". Буквы "b" и "t" можно использовать, даже если в операционной системе нет различий между бинарными и текстовыми файлами, в этом случае они просто игнорируются.

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

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

Алгоритм решения системы линейных уравнений с помощью метода Гаусса. Алгоритм реализован на языке С++.

Пусть у нас есть система N линейных уравнений

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... a_1Nx_N = b₁

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... a_2Nx_N = b₂

a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + ... a_3Nx_N = b₃

...

a_N1x₁ + a_N2x₂ + a_N3x₃ + ... a_NNx_N = b_N

где x_i - неизвестные, a_ij - коэффициенты при неизвестных, b_i - свободные члены в уравнениях, i,j пробегают значения от 1 до N.

Цель задачи - зная a_ij и b_i найти x_i.

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

a11x1 +	a12x2 +	a13x3 +	...	a1NxN = b1
a22x2 +	a23x3 +	...	a2NxN = b2
a33x3 +	...	a3NxN = b3
...
...	aNNxN = bN

Особенность этой системы - в строках с номером i все коэффициенты a_ij при j<i равны нулю.