Прямые методы

Одним из способов решения системы линей­ных уравнений является правило Крамера, согласно которому каждое неиз­вестное представляется в виде отношения определителей.

, где

При большом числе уравнений потребуется выполнить огромное число арифметических операций.(число операций =)

- количество арифметических операций.

Поэтому правило Крамера используется для решения систем, состоящих из нескольких уравнений.

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

Обратный ход метода Гаусса состоит в последовательном вычисле­нии искомых неизвестных: решая последнее уравнение, находим един­ственное в этом уравнении неизвестное .Далее, используя это значение, из предыдущего уравнения вычисляем и т. д. Последним найдем из первого уравнения.

Рассмотрим применение метода Гауссадля системы:

(1)

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

(2)

,

где () , ().

Теперь из третьего уравнения системы (2) нужно исключить . Для этого умножим второе уравнение на и прибавим результат к третьему. Получим систему

(3)

где , .

Матрица системы (3) имеет треугольный вид. На этом заканчивается прямой ход метода Гаусса.

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

Обратный ход начинается с решения третьего уравнения системы (3):

.

Используя это значение, можно найти из второго уравнения, а затем из первого:

, .

Аналогично строится вычислительный алгоритм для линейной системы с произвольным числом уравнений.

Блок-схема решения методом Гаусса системы линейных уравнений вида:

рис.1.

Левая часть блок-схемы соответствует прямому ходу. Поясним смысл индексов: -номер уравнения, из кото­рого исключается неизвестное ; - номер столбца; - номер неизвестного, которое исключается из остав­шихся уравнений (а также номер того уравнения, с помощью которого исклю­чается ). Операция пере­становки уравнений (т. е. перестановки соответствую­щих коэффициентов) слу­жит для предотвращения де­ления на нулевой элемент. Правая часть блок-схемы описывает процесс обратного хода. Здесь - номер не­известного, которое опреде­ляется из -гo уравнения; - номера уже найденных неизвестных.

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

Блок-схема алгоритма выбора главного элемента. Она дополняет блок-схему метода Гаусса. Здесь введены новые индексы:- номер наибольшего по абсолютной величине элемента матрицы в столбце с номером (т.е. среди элементов );- текущий номер элемента, с которым происходит сравнение. Заметим, что диагональные элементы матрицы на­зываются ведущими элементами; ведущий элемент - это коэффициент при -м неизвестном в -м уравнении на -м шаге исключения.

Благодаря выбору наибольшего по модулю ведущего элемента уменьшаются множители, используемые для преобразования уравнений, что способствует снижению погрешностей вычислений. Поэтому метод Гаусса с выбором главного элемента обеспечивает приемлемую точность решения для сравнительно небольшого числа () уравнений. И только для плохо обусловленных систем решения, полученные по этому методу, ненадежны.

Метод Гаусса целесообразно использовать для реше­ния систем с плотно заполненной матрицей. Все элемен­ты матрицы и правые части системы уравнений находят­ся в оперативной памяти машины. Объем вычислений определяется порядком системы :число арифметических операций примерно равно .

4. Определитель и обратная матрица. Ранее уже отмечалось, что непосредственное нахождение определите­ля требует большого объема вычислений. Вместе с тем легко вычисляется определитель треугольной матрицы: он равен произведению ее диагональных элементов.

Для приведения матрицы к треугольному виду может быть использован метод исключения т. е. прямой ход метода Гаусса. В процессе исключения элементов вели­чина определителя не меняется. Знак определителя ме­няется на противоположный при перестановке его столб­цов или строк. Следовательно, значение определителя по­сле приведения матрицы к треугольному виду вычис­ляется по формуле

.

Здесь диагональные элементы берутся из преобразо­ванной (а не исходной) матрицы. Знак зависит от того, четной или нечетной была суммарная перестановка строк (или столбцов) матрицы при ее приведении к треуголь­ному виду (для получения ненулевого или максималь­ного по модулю ведущего элемента на каждом этапе ис­ключения). Благодаря методу исключения можно вычис­лять определители 100-го и большего порядков, и объем вычислений значительно меньший, чем в проведенных ранее оценках.

5.Метод прогонки. Он является модификацией мето­да Гаусса для частного случая разреженных систем – системы уравнении с трехдиагональной матрицей. Такие системы получаются при моделировании некоторых ин­женерных задач, а также при численном решении крае­вых задач для дифференциальных уравнении. Запишем систему уравнений в виде

(1)

……………………………………………………………..

На главной диагонали матрицы этой системы стоят эле­менты , над ней - элементы, , под ней — элементы . При этом обычно все коэффициенты не равны нулю.

Метод прогонки, состоит из двух этапов - прямой прогонки (аналога прямого хода метода Гаусса) и обрат­ной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в том, что каждое неизвестное выражается через с помощью прогоночных коэф­фициентов ,:

(2)

Из первого уравнения системы (1) найдем

.

С другой стороны, по формуле (2)

.

При­равнивая коэффициенты в обоих выражениях для , по­лучаем:

(3).

Из второго уравнения системы (1) выразим через ,заменяя по формуле (2): .

Отсюда найдем или

, , ,

Аналогично можно вычислить прогоночные коэффициен­ты для любого номера :

, , , (4).

Обратная прогонка состоит в последовательном вы­числении неизвестных . Сначала нужно найти . Для этого воспользуемся выражением (2) при и последним уравнением системы (1). Запишем их , .

Отсюда, исключая , находим .

Далее, используя формулы (2) и выражения для прогоночных коэффициентов (3), (4), последова­тельно вычисляем все неиз­вестные .

Блок-схема решения системы линейных уравнений вида (1).

При анализе алгоритма метода прогонки надо учитывать возможность деления на нуль в формулах (4). Можно показать, что при выполнении условия преоб­ладания диагональных эле­ментов, т. е. если , причем хотя бы для одного значения имеет место строгое неравенство, деления на нуль не возника­ет, и система (1) имеет единственное решение.

Приведенное условие пре­обладания диагональных элементов обеспечивает также устойчивость метода прогон­ки относительно погрешно­стей округлений. Последнее обстоятельство позволяет использовать метод прогон­ки для решения больших систем уравнений. Заметим, что данное условие устойчи­вости прогонки является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (1) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных

элементов.