Метод Гаусса: описание алгоритма решения системы линейных уравнений, примеры, решения. Решение систем линейных алгебраических уравнений, в которых число уравнений равно числу неизвестных и основная матрица системы невырожденная, методом Гаусса

В данном случае помимо соблюдения требования a kk 0 при реализации формул (6) накладываются дополнительные требования, чтобы ведущий (главный) элемент в текущем столбце в процессе преобразований исходной матрицы имел максимальное по модулю значение. Это также достигается перестановкой строк матрицы.

Пример . В качестве иллюстрации преимущества модифицированного метода Гаусса, рассмотрим систему третьего порядка:

Прямой ход метода Гаусса

Исключаем х 1 из второго и третьего уравнений. Для этого первое уравнение умножаем на 0,3 и складываем со вторым, а затем умножаем первое уравнение на (–0,5) и складываем с третьим. В результате получаем

(б )

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

Умножая второе уравнение на 25, и складывая с третьим, получим

(в )

Обратный ход метода Гаусса

Выполняем вычисления, начиная с последнего уравнения в полученной системе:

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

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

(г )

Прямой ход метода для системы (г ) повторим по аналогичной технологии с исходной системой (а ).

(д )

После исключения х 2 третье уравнение примет вид (остальные – без изменения)

15005 х 3 = 15004. (е )

Выполняя обратный ход, получим

Очевидно, что полученные решения и [–0,35; –1,4; 0,99993] различны. Причиной этого является малая величина ведущего элемента во втором уравнении преобразования в (д ). Чтобы это исключить, переставим в (д ) вторую и третью строки


(ж )

Для данной системы после исключения х 2 из третьего уравнения, оно примет следующий вид

6,002 х 3 = 6,002. (з )

В данном случае, выполняя обратный ход

мы получим решение системы (г ) , которое в точности совпадает с решением исходной системы.

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

Рассмотрим блок-схему модифицированного метода Гаусса (рис. 2.1).

Рис. 2.1. Блок-схема модифицированного метода Гаусса

Проведем анализ предложенной схемы на примере системы n =3 (=0,001)

(8)

;. (*)

Блок 1. Ввод исходных данных:n – порядок системы,A – матрица коэффициентов при неизвестных,b – вектор свободных членов.

Блок 2.I-й цикл прямого хода (дляk , изменяющегося от 1 до предпоследнего значения, т.е. доn –1) обеспечивает исключение из главной диагонали матрицыА элементаa kk =0 благодаря поиску максимального элементаa kk в текущем столбце, осуществляемому в блоках 36 с помощью циклаII.

Затем реализуются расчеты по формулам (6) прямого хода Гаусса в блоках циклов IVиV.

Проведем поблочный анализ в среде рассмотренных циклов IVна примере (8).

Блок 3p =k = 1

Вход в цикл II

Блок 4m =k +1 = 2 доn = 3

Блок 5a 11 = 2 <a 21 = 4 из (*)

Блок 6p = 2

Блок 4m = 2+1 = 3

Блок 5a 21 = 4 <a 31 = 6 из (*)

Блок 6p = 3

Выход из цикла IIи вход в циклIII, блоки 710 выполняют перестановку строк матрицыА поэлементно

Блок 7j = 1 (j от 1 до 3)

Блок 8 r = a 11 = 2 из (*)

Блок 9 a 11 = a 31 = 6

Блок 10 a 31 = r

Блок 7 j = 2

Блок 8 r = a 12 = 1

Блок 9 a 12 = a 32 = 5

Блок 10 a 32 = r = 1

Блок 7j = 3 и по аналогииr =a 13 ;a 13 =a 33 ;a 33 =r = −1.

Выход из цикла IIIи вход вБлок 11 и далее 1213 выполняют аналогичную перестановку значений свободных членов

r =b 1 = 1;b 1 = b 3 = 14;b 3 =r= 1.

Вход в цикл IVс измененной системой

;; (**)

для пересчета b 2 вектора

m =k +1 = 1+1 = 2 доn = 3

c = a mk / a kk = a 21 / a 11 = 4/6 из (**)

b 2 =b 2 –c b 1 = 6 – 4/614 = −20/6 из (**)

Вход во вложенный цикл Vдля пересчета второй строки

i = 1 (i от 1 до 3); a 21 = a 21 – с  a 11 = 4 – 4/6  6 = 0;

i = 2; a 22 = a 22 – с  a 12 = 6 – 4/6  5 = 16/6;

i = 3; a 23 = a 23 – с  a 13 = 2 – 4/6  8 = −20/6.

Выход из цикла Vи вход в циклIV

m = 3;c =a 31 /a 11 = 2/6.

Вход в Блок 16

b 3 =b 3 –c b 1 = 1 – 2/614 = −22/6.

Выход из цикла IVи вход в циклVи вход вБлок 17

i = 1 (i от 1 до 3); a 31 = a 31 – с  a 11 = 2 – 2/6  6 = 0;

i = 2; a 32 = a 32 – с  a 12 = 1 – 2/6  5 = −4/6;

i = 3; a 33 = a 33 – с  a 13 = −1 – 2/6  8 = −22/6.

Выход из цикла Vс преобразованной системой

;
; (***)

и вход по линии А в циклI

k = 2;p =k = 2;m =k +1 = 3; вход вБлок 5

| a 22 | < |a 32 | = | 16/6 | > | 4/6 | из (***).

Выход из цикла IIи вход в циклIII

j = 2 (j от 2 до 3);

r = a kj = a 22 = 16/6; a 22 = a 22 ; a 22 = r = 16/6; из (***)

r =a 23 = −20/6;a 23 =a 23 ;a 23 =r = −20/6; из (***)

В данном случае на диагонали оказался максимальный элемент, поэтому перестановка 2-ой и 3-ей строк не выполняется.

Выход из цикла IIIи вход в циклIвБлок 11

r =b 2 ;b 2 = b 2 ;b 2 =r= −20/6.

Свободный член b 2 остается на своем месте.

Вход в цикл IV

m =k +1 = 2+1 = 3;

c = a mk / a kk = a 32 / a 22 = (–4/6) / (16/6); из (***)

b 3 =b 3 –c b 2 = −22/6 – (–1/4)(–20/6) = −27/6 из (***)

Выход из цикла IVи вход в циклV

i = 2 (i от 2 до 3); a 32 = a 32 – с  a 22 = −4/6 – (–1/4)  16/6 = 0;

i = 3;a 33 =a 33 –с a 23 = −22/6 – (–1/4)(–20/6) = −27/6.

Выход из цикла Vи выход из циклаI.

Обратный ход метода Гаусса

В Блоках 1924 реализуются формулы (7).

В Блоке 19 из последнего уравнения находится значениеx n (n = 3)

x 3 =b n / a nn =b 3 / a 33 = (–27/6) / (–27/6) = 1.

Вход в цикл VI(Блок 20), в котором значение переменной циклаk изменяется отn –1 до 1 с шагом (–1)

Блок 21s= 0

Вход в цикл VII(Блок 22)

i = k +1 = 2+1 = 3; n = 3; s = s + a ki  x i = 0 + a 23 x 3 = −20/6 1 = −20/6.

Выход из цикла VIIнаБлок 24 в циклVI:

k = 2; x 2 = (b k – s)/ a nn = (b 2 – s)/ a 22 = (–20/6 +20/6)/ a 22 = 0.

k =k –1 = 2–1 = 1;

i = k + 1 = 2; s = 0 + a 12 x 2 = 5  0 = 0;

i = k + 1 = 3; s = 0 + a 13 x 3 = 8  1 = 8;

x 1 = (b 1 –s)/ a 11 = (14 – 8) / 6 = 1.

Выход из последнего цикла VII.

В Блоке 25 (цикл опущен) выполняется вывод на экран полученного решения СЛАУ – векторат.е.x i ,i =1, ...,n . В нашем случае (1; 0; 1).

2. Модификации метода Гаусса

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

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

Исключить возникновение подобных случаев позволяет метод Гаусса с выбором главного элемента.

Идея этого метода состоит в следующем. На некотором k-м шаге прямого хода из уравнений исключается не следующая по номеру переменная x k , а такая переменная, коэффициент при которой является наибольшим по абсолютной величине. Этим гарантируется отсутствие деления на нуль и сохранение устойчивости метода.

Если на k-м шаге в качестве главного элемента выбирается ¹ , то в матрице A¢ должны быть переставлены местами строки c номерами k и p и столбцы с номерами k и q.

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

Существуют две более простые модификации метода Гаусса:

С выбором главного элемента по столбцу;

С выбором главного элемента по строке.

В первом случае в качестве главного элемента выбирается наибольший по абсолютной величине элемент k-й строки (среди элементов , i = ). Во втором - наибольший по абсолютной величине элемент k-го столбца (среди элементов , i = ). Наибольшее распространение получила первый подход, поскольку здесь не изменяется нумерация переменных.

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

LU-разложение. В современном математическом обеспечении ЭВМ метод Гаусса реализуется с использованием LU-разложения, под которым понимают представление матрицы коэффициентов A в виде произведения A = LU двух матриц L и U, где L – нижняя треугольная матрица, U - верхняя треугольная матрица

Если LU-разложение получено, то решение исходной системы уравнений (2) сводится к последовательному решению двух следующих систем уравнений с треугольными матрицами коэффициентов

линейный алгебраический уравнение численный

где Y = - вектор вспомогательных переменных.

Такой подход позволяет многократно решать системы линейных уравнений с разными правыми частями B. При этом наиболее трудоемкая часть (LU-разложение матрицы A) выполняется только один раз. Эта процедура соответствует прямому ходу метода Гаусса и имеет оценку трудоемкости O(n 3). Дальнейшее решение систем уравнений (6) и (7) может выполняться многократно (для различных B), причем решение каждой из них соответствует обратному ходу метода Гаусса и имеет оценку вычислительной сложности O(n 2).

Для получения LU-разложения можно воспользоваться следующим алгоритмом.

1. Для исходной системы (1) выполнить прямой ход метода Гаусса и получить систему уравнений треугольного вида (5).

2. Определить элементы матрицы U по правилу

u ij = C ij (i = ; j = )

3. Вычислить элементы матрицы L по правилам

Расчетные формулы для решения системы (6) имеют следующий вид:

y 1 = b 1 / l 11 ;

Расчетные формулы для решения системы (7)

(i = n - 1, n - 2, …, 1).

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

35437 x4=0.58554 5 x1=1.3179137 x2=-1.59467 x3=0.35371 x4=0.58462 6 x1=1.3181515 x2=-1.59506 x3=0.35455 x4=0.58557 5. Сравнительный анализ различных методов численного дифференцирования и интегрирования 5.1 Методы численного дифференцирования 5.1.1 Описание метода Предположим, что в окрестности точки xiфункция F (x) дифференцируема достаточное число раз. ...

На языке Turbo Pascal 7.0 для решении систем линейных алгебраических уравнений, используя метод простой итерации. 1.2 Математическая формулировка задачи Пусть А – невырожденная матрица и нужно решить систему где диагональные элементы матрицы А ненулевые. 1.3 Обзор существующих численных методов решения задачи Метод Гаусса В методе Гаусса матрица СЛАУ с помощью равносильных...

Числа). Далее по формулам (2) последовательно находятся xn-1 , xn-2 ,…, x1 при i=n-1, n-2,...,1 соответственно. Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки, сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов δi, λiпо формулам (3) при i=1,2,…,n (прямая прогонка) и затем неизвестных xi по...

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

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

Метод Гаусса (метод последовательного исключения неизвестных ) заключается в том, что с помощью элементарных преобразований система приводится к эквивалентной системе ступенчатого вида. Сначала с помощью 1-го уравнения исключается x 1 из всех последующих уравнений системы. Затем с помощью2-го уравнения исключается x 2 из 3-го и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса , продолжается до тех пор, пока в левой части последнего уравнения останется только одно неизвестное x n . После этого производится обратный ход метода Гаусса – решая последнее уравнение, находим x n ; после этого, используя это значение, из предпоследнего уравнения вычисляем x n –1 и т.д. Последним находим x 1 из первого уравнения.

Преобразования Гаусса удобно проводить, осуществляя преобразования не с самими уравнениями, а с матрицами их коэффициентов. Рассмотрим матрицу:

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

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

Решение . Выпишем расширенную матрицу системы и, используя первую строку, после этого будем обнулять остальные элементы:

получим нули во 2-й, 3-й и 4-й строках первого столбца:

Теперь нужно чтобы все элементы во втором столбце ниже 2-й строки были равны нулю. Для этого можно умножить вторую строку на –4/7 и прибавить к 3-й строке. Однако чтобы не иметь дело с дробями, создадим единицу во 2-й строке второго столбца и только

Теперь, чтобы получить треугольную матрицу, нужно обнулить элемент четвертой строки 3-го столбца, для этого можно умножить третью строку на 8/54 и прибавить ее к четвертой. Однако чтобы не иметь дело с дробями поменяем местами 3-ю и 4-ю строки и 3-й и 4-й столбец и только после этого произведем обнуление указанного элемента. Заметим, что при перестановке столбцов меняются местами, соответствующие переменные и об этом нужно помнить; другие элементарные преобразования со столбцами (сложение и умножение на число) производить нельзя!

Последняя упрощенная матрица соответствует системе уравнений, эквивалентной исходной:

Отсюда, используя обратный ход метода Гаусса, найдем из четвертого уравнения x 3 = –1; из третьего x 4 = –2, из второго x 2 = 2 и из первого уравнения x 1 = 1. В матричном виде ответ записывается в виде

Мы рассмотрели случай, когда система является определенной, т.е. когда имеется только одно решение. Посмотрим, что получится, если система несовместна или неопределенна.

Пример 5.2. Исследовать систему методом Гаусса:

Решение . Выписываем и преобразуем расширенную матрицу системы

Записываем упрощенную систему уравнений:

Здесь, в последнем уравнении получилось, что 0=4, т.е. противоречие. Следовательно, система не имеет решения, т.е. она несовместна . à

Пример 5.3. Исследовать и решить систему методом Гаусса:

Решение . Выписываем и преобразуем расширенную матрицу системы:

В результате преобразований, в последней строке получились одни нули. Это означает, что число уравнений уменьшилось на единицу:

Таким образом, после упрощений осталось два уравнения, а неизвестных четыре, т.е. два неизвестных "лишних". Пусть "лишними", или, как говорят, свободными переменными , будут x 3 и x 4 . Тогда

Полагая x 3 = 2a и x 4 = b , получим x 2 = 1–a и x 1 = 2b –a ; или в матричном виде

Записанное подобным образом решение называется общим , поскольку, придавая параметрам a и b различные значения, можно описать все возможные решения системы. à

Систему уравнений (1.1) представим в виде

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

Метод Гаусса можно интерпретировать как метод, в котором первоначально матрица приводится к верхней треугольной форме (прямой ход), а далее - к единичной (обратный ход). Очевидно, что если матрица единичная, то x t = b r

Пусть матрица системы (1.3) - верхняя треугольная, поэтому a tj = 0 при i > j, т. е. все элементы ниже главной диагонали равны нулю. Тогда из последнего уравнения сразу определяем х п. Подставляя х п в предпоследнее уравнение, находим х а _ х и т. д. Общие формулы имеют вид

При k > I коэффициенты а ы = 0.

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

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

Умножим k-ю строку на число с тк = т > k и вычтем

из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-ro столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется ПРЯМЫМ ХОДОМ МЕТОДА ГАУССА. Вычисление неизвестных по формулам (1.4) называют ОБРАТНЫМ ХОДОМ метода.

Обратный ход можно совершить иначе, если обратить в нуль и все коэффициенты, лежащие выше главной диагонали. Например, элементы п -го столбца обращаются в нуль, если ej^| умножить на (-a^V ax t = б| 2л) , где Ь^ п) - коэффициенты правой части i-го уравнения после указанных преобразований.

На некотором шаге прямого хода может оказаться, что коэффициент aj*" * 0, но мал по сравнению с остальными элементами матрицы системы и, в частности, мал по сравнению с элементами первого столбца. Деление коэффициентов системы на малую величину может привести к значительным ошибкам округления.

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

Для реализации метода требуется примерно п 3 /3 операций типа умножения и п 3 /3 операций типа сложения . Полезно помнить, что оценка числа операций определяется в основном операциями, затрачиваемыми при выполнении прямого хода метода Гаусса. Обратный ход метода Гаусса требует примерно п 2 операций. Следовательно, если требуется решить несколько систем линейных алгебраических уравнений вида Ах = b с одной и той же матрицей и различными правыми частями, то общее число операций при решении S систем будет оцениваться величиной (2/3)п 3 + Sn 2 . В этом случае целесообразно реализовать алгоритм метода Гаусса в виде двух подпрограмм: первая подпрограмма должна реализовывать прямой ход алгоритма и получать на выходе верхнюю треугольную матрицу, а вторая подпрограмма должна, используя полученную матрицу, вычислять решение системы для произвольной правой части.

(СЛАУ), состоящая из уравнений с неизвестными:

Предполагается, что существует единственное решение системы, то есть .

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

Описание метода

Процесс решения системы линейных уравнений

по методу Гаусса состоит из 2х этапов:

• Обратный ход Непосредственное определение неизвестных

Анализ метода

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

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

Пусть введена некоторая норма . - называется числом обусловленности матрицы .

Возможны 3 случая:

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

Проиллюстрируем полученные результаты на следующем числовом примере: Дана система

Она имеет решение .

Теперь рассмотрим возмущенную систему:

Решением такой системы будет вектор .

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

Такой результат можно было предвидеть в силу плохой обусловленностью матрицы :

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

Способы оценки ошибок

Составляем контрольный столбец , состоящий из контрольных элементов системы:

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

2) Относительная погрешность известного решения позволяет без существенных дополнительных затрат получить суждение о погрешности решения.

Задается некоторый ветор с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения . Вычисляется вектор , и на ряду с исходной системой уравнения решается система .

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

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

Наряду с исходной системой тем же методом решается система

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

Улучшение метода исключения Гаусса

Рассмотренные ниже модификации метода Гаусса позволяют уменьшить погрешность результата.

Выбор главного элемента

Основное увеличение ошибки в методе происходит во время прямого хода, когда ведущая -я строка умножается на коэффициенты .Если коэффициенты 1%20" alt=" >1 ">, то ошибки, полученные на предыдущих шагах накапливаются. Чтобы этого избежать, применяется модификация метода Гаусса с выбором главного элемента. На каждом шаге к обычной схеме добавляется выбор максимального элемента по столбцу следующим образом:

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

Найдем такое , что и поменяем местами -е и -е уровнения.

Такое преобразование во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях.

Итеративное улучшение результата

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

Решая эту систему, получаем приближение к и полагаем

Если точность данного приближения неудовлетворительна, то повторяем эту операцию.

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

Числовой пример

Рассмотрим для примера матрицу Вандермонда размером 7х7 и 2 различные правые части:

Данные системы были решены двумя способами. Тип данных - float. B итоге получили следующие результаты: