Метод Крамера

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

, ,

где матрица получается из матрицызаменой столбцаiна столбец свободных членовF.

Формула Крамера дает решение уравнения в явном виде, но с вычислительной точки зрения она невыгодна. Расчет по ней требует слишком большого числа операций и оказывается очень чувствительным к ошибкам округления. Поэтому на практике при вычислениях на компьютерах используют другие методы. Автор использует формулу Крамера для решения систем уравнений с двумя неизвестными, что возможно выполнить «в уме».

Метод Гаусса

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

Метод Гаусса выполняется в два этапа:

• Прямой ход. Система уравнений приводится к треугольному виду.

• Обратный ход. Заключается в последовательном определении неизвестных из полученной треугольной системы.

Итак, решение системы уравнений (3.1) по схеме единственного деления заключается в следующем:

Предположим, что коэффициент . Разделим коэффициенты первого уравнения системы (3.1) на. Первое уравнение примет вид:

, (3.3)

где

для и.

Используя уравнение (3.3), можно исключить из системы (3.1) неизвестную (везде, кроме первого уравнения). Для этого вычтем из второго уравнения системы уравнение (3.3), умноженное на. Далее, из третьего уравнения вычтем уравнение (3.3), умноженное наи т.д. В результате получим следующую систему

, (3.4)

где коэффициенты идлявычисляются по формулам

и .

Предполагаем, что коэффициент и аналогичным способом исключаем из системы (3.4) неизвестную(кроме первого и второго уравнения). Далее избавляемся от неизвестногои т.д. В результате получаем следующую систему уравнений

, (3.5)

Итак, в результате выполнения первого этапа метода Гаусса - прямого хода - от системы уравнений (3.1) переходим к эквивалентной ей системе уравнений (3.5) с треугольной матрицей. Как известно, решение системы уравнений с треугольной матрицей является достаточно простой операцией и выполняется по следующим формулам:

,

и т.д.

Общая формула имеет вид:

, (3.6)

где .

Примечание. При имееми.

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

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

Пример. Решить систему уравнений схемой единственного деления. При вычислениях все числа округлять до пяти цифр. Пример показывает, как ошибки округления могут привести к получению неверного решения.

.

Исключили неизвестную и получили систему

.

Исключаем неизвестную :

Прямой ход закончился. Выполняем второй этап и получаем следующее решение:

,

в то время как точное решение имеет вид:

.

На примере видно, что небольшая погрешность для , равная 0.0008, стремительно увеличивается длядо 0.4286 и достигает максимума для(1.9021).

Итак, приближенное решение почти в три раза больше точного решения. Данное возмущение связано со вторым уравнением. Главный элемент второго уравнения равен 0.0007. В соответствии с формулой (3.6) погрешность решенияувеличилась враз.

Если бы вычисления проводились без ошибок округления, то решение было бы точным. Но к сожалению, все расчеты с вещественными числами выполняются только приближенно. В зависимости от типа вещественного числа (Real,Single,Extendedи т.д.) точными являются 10-20 знаков.

Вычислительную погрешность можно существенно уменьшить. Причина резкого роста погрешности заключена в малости ведущего элемента. Чтобы повысить точность метода, необходимо выбрать другой ведущий элемент. Существует несколько вариантов выбора главного элемента - по строкам, по столбцам и по матрице. Пусть необходимо исключить неизвестную , т.е. работаем сi-тымуравнением. Выберем максимальный по модулю коэффициент вi-томстолбце, из числа стоящих на главной диагонали и ниже. Пусть это будет коэффициент изj-тогоуравнения. Поменяем местами уравнения № i и j. Продолжим исключение неизвестных. Описанный алгоритм и есть метод Гаусса с выбором главного элемента по столбцам. Если максимальный по модулю элемент будем искать вi-тойстроке, то получим метод Гаусса с выбором главного элемента по строкам. При выборе главного элемента в матрице поиск осуществляется в матрице коэффициентов - в строках отiдоnи столбцах отiотn.

В вышеописанном примере для исключения неизвестного применим выбор главного элемента по столбцам. Ведущий элемент будет равен -16.895. В результате получим приближенное решение

.

Следовательно, несмотря на ошибки округления, погрешность решения не превысила 0.0003

Пример. Ниже будет приведен фрагмент программы, реализующий прямой ход метода Гаусса без выбора главного элемента. Предполагается, что все необходимые переменные были определены ранее.

{Перебираем номера неизвестных k от первого до}

{предпоследнего. Будем исключать неизвестную x[k]}

For k:=1 to N-1 do

begin

{Если главный элемент равен нулю, даем}

{сообщение и завершаем работу программы}

If Abs(A[k,k])<0.001 then

begin

Writeln(’Главный элемент равен нулю.’);

Writeln(’Данную схему применять нельзя.’);

Halt(1);

end;

{Перебираем уравнения от k+1 до последнего}

For i:=k+1 to N do

begin

{Перебираем коэффициенты уравнения}

For j:=k+1 to N do

{и вычисляем их новые значения}

A[i,j]:=A[i,j]-A[i,k]*A[k,j]/A[k,k];

{Вычисляем значение коэфф. правой части}

F[i]:=F[i]-A[i,k]*F[k]/A[k,k];

end;

end;

Для получения решения системы уравнений применяется формула (3.6). Алгоритм вкратце выглядит следующим образом. Осуществляют перебор номеров iотndo1. Вычисляют выражение, стоящее в скобках, обращая внимание на правильность суммирования, и значение дроби.

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

Пример. В программе метода Гаусса с выбором главного элемента по строкам и матрице для восстановления решения может использоваться нижеприведенный код.

{В массиве Por хранится информация о }

{местоположении элементов решения}

Var Por:Array[1..N] of Integer;

...

{После ввода коэфф. системы, задаем массив Por}

For i:=1 to N do Por[i]:=i;

...

{Пусть на I-том шаге исключения главный}

{элемент находится в j-том столбце.}

{Необходимо поменять местами коэффициенты }

{i и j столбца. Изменяем соответственно данные}

{в массиве Por. Для этого используем}

{переменную Vsp типа Integer}

Vsp:=Por[i]; Por[i]:=Por[j]; por[j]:=Vsp;

...

{Решили систему уравнений, далее требуется}

{восстановить решение. Полученное решение было}

{записано в массив X.}

{Восстановленное решение запишем в массив Xnew}

For i:=1 to N do

Xnew[i]:=X[Por[i]];