АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Метод Гаусса для решения систем линейных уравнений

Читайте также:
  1. A) к любой экономической системе
  2. A) прогрессивная система налогообложения.
  3. C) Систематическими
  4. CASE-технология создания информационных систем
  5. ERP и CRM система OpenERP
  6. HMI/SCADA – создание графического интерфейса в SCADА-системе Trace Mode 6 (часть 1).
  7. I Понятие об информационных системах
  8. I СИСТЕМА, ИСТОЧНИКИ, ИСТОРИЧЕСКАЯ ТРАДИЦИЯ РИМСКОГО ПРАВА
  9. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  10. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  11. I. Методические основы
  12. I. Методические основы оценки эффективности инвестиционных проектов

Пусть требуется решить систему n линейных алгебраических уравнений с n неизвестными:

 

(3.9)

 

Прямой ход метода Гаусса преобразует систему (3.9) к треугольному виду исключением соответствующих неизвестных. Пусть a 11 ≠ 0. Первый шаг заключается в исключении переменной x 1 с помощью первого уравнения из остальных уравнений. Разделим первое уравнение на a 11:

 

(3.10)

 

Затем от второго уравнения отнимем первое уравнение, умноженное на a 21. В результате, на месте второго уравнения получим уравнение, не содержащее x 1. Чтобы исключить x 1 из третьего уравнения отнимем от него первое уравнение, умноженное на a 31. Аналогично исключаем x 1 из четвертого и последующих уравнений. Для исключения x 1 из i -го уравнения (i = 2, 3, …, n) применим формулы:

 

(3.11)

 

В результате этих вычислений получим систему вида:

 

(3.12)

 

На втором шаге исключаем переменную x 2 с помощью второго уравнения из третьего и последующих уравнений. Предположим, что . Разделим второе уравнение на :

 

(3.13)

 

В системе (3.12) с помощью второй строки исключим x 2 из i -го уравнения(i = 3, 4, …, n), применяя формулы:

 

(3.14)

 

Система (3.12) преобразуется к следующему виду:

 

(3.15)

 

1. В общем случае, на шаге m, для m = 1, 2, …, n – 1, делим сначала m -ое уравнение на :

 

(3.16)

 

а затем исключаем переменную xm с помощью m -ого уравнения из i -го,
где i = m + 1, …, n:

 

(3.17)

 

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

В результате (n – 1)-го шага система (3.9) приобретает вид:

 

(3.18)

 

2. Обратный ход метода Гаусса вычисляет неизвестные xi в обратном порядке. Из последнего уравнения в (3.18) находим

 

(3.19)

 

Неизвестные xi определяем по следующим формулам:

 

(3.20)

 

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

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

Метод Гаусса с выбором главного элемента по столбцам отличается от алгоритма (3.16) — (3.20) только тем, что перед преобразованием (3.16) надо выполнить поиск максимального по модулю элемента в m -ом столбце и переставить строки системы уравнений так, чтобы максимальный элемент стал диагональным элементом матрицы коэффициентов.

 

Алгоритм метода Гаусса с выбором главного элемента по столбцам.

1. Для m = 1, 2, …, n – 1 выполним преобразования:

Найдем максимальный по абсолютной величине элемент в m -ом столбце. Пусть это будет элемент aim. Если im, то меняем местами i -ую и m -ую строки:

 

r = aij, aij = amj, amj = r, j = 1, …, n; r = bi, bi = bm, bm = r.

 

Элементы матрицы и вектора после преобразования на m -ом шаге обозначим , причем .

Делим m -ое уравнение на ведущий элемент :

 

 

а затем исключаем переменную xm с помощью m -ого уравнения из i -го,
где i = m + 1, …, n:

 

 

2. Вычисляем неизвестные xi в обратном порядке:

 

;

 

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

При реализации метода Гаусса на каком-либо языке программирования удобно использовать исходные матрицу a и вектор b для хранения промежуточных результатов преобразований. Приведенные формулы преобразований записываются как операторы присваивания, т.е. имена переменных aij и bj записываются без верхних индексов. Ниже приведены различные примеры программ метода Гаусса.

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

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

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

Общее число операций для решения системы уравнений методом Гаусса составляет приблизительно [1] 2 n 3/3 + 2 n 2, при этом большая часть, т.е. 2 n 3/3 операций приходится на прямой ход.

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

4 x 1 + 2 x 2 – 4 x 3 + 2 x 4 = 12,

2 x 1 + 9 x 2 – 4 x 3 – 4 x 4 = 14,

3 x 1 + 2 x 2 – 8 x 3 + 2 x 4 = 20,

4 x 1 + 2 x 2 + 5 x 3 + 7 x 4 = 10.

Решение. Продемонстрируем решение в программе электронных таблиц.

0. Запишем коэффициенты и правые части системы в диапазоне A 1: E 4.

1. В диапазоне A 5: E 8 сформируем расширенную матрицу системы, которая получится после исключения переменной x 1 из второго, третьего и четвертого уравнений.

В ячейку A 5 вводим формулу =A1/$A1; выделим A 5 и протянем маркер заполнения (мышью за правый нижний угол) до E 5.

Затем в ячейку A 6 вводим формулу =A2-A$5*$A2; выделим A 6 и протянем маркер заполнения до E 6.

Выделим диапазон A 6: E 6 и протянем маркером заполнения до E 8.

В ячейках A 5: E 8 появятся следующие значения:

1,0000 0,5000 -1,0000 0,5000 3,0000
0,0000 8,0000 -2,0000 -5,0000 8,0000
0,0000 0,5000 -5,0000 0,5000 11,0000
0,0000 0,0000 9,0000 5,0000 -2,0000

 

2. В диапазоне A 9: E 12 сформируем матрицу системы, которая получится после исключения x 2 из третьего и четвертого уравнений.

Присвоим строке A 9: E 9 значения строки A 5: E 5, т.е. выделим диапазон A 9: E 9 и введем формулу =A5:E5 и удерживая нажатыми клавиши Ctrl и Shift, нажимаем Enter.

В ячейку B 10 вводим формулу =B6/$B6; выделим B 10 и протянем маркер заполнения до E 10.

Затем в ячейку B 11 вводим формулу =B7-B$10*$B7; выделим B 11 и протянем мышью маркер заполнения до E 11.

Выделим диапазон B 11: E 11 и протянем маркер заполнения до E 12.

В ячейках A 9: E 12 появятся следующие значения:

 

1,0000 0,5000 -1,0000 0,5000 3,0000
0,0000 1,0000 -0,2500 -0,6250 1,0000
  0,0000 -4,8750 0,8125 10,5000
  0,0000 9,0000 5,0000 -2,0000

 

3. В диапазоне A 13: E 16 сформируем матрицу системы, которая получится после исключения x 3 из четвертого уравнения.

Перепишем значения строк A 9: E 10 в строки A 13: E 14, для этого выделим диапазон A 13: E 14 и введем формулу =A9:E10 и удерживая клавиши Ctrl и Shift нажатыми, нажимаем Enter.

В ячейку C 15 вводим формулу =C11/$C11; выделим C 15 и протянем мышью за правый нижний угол до E 15.

В ячейку C 16 вводим формулу =C12-C$15*$C12, выделим C 16 и протянем мышью за правый нижний угол до E 16. В ячейках A 13: E 16 получим значения:

 

1,0000 0,5000 -1,0000 0,5000 3,0000
0,0000 1,0000 -0,2500 -0,6250 1,0000
    1,0000 -0,1667 -2,1538
    0,0000 6,5000 17,3846

 

4. Сформируем в диапазоне A 17: E 20 окончательную матрицу системы, которая имеет треугольный вид с единицами на диагонали.

Выделим диапазон A 17: E 19 и введем формулу =A13:E15 и, удерживая нажатыми клавиши Ctrl и Shift, нажимаем Enter. В ячейку D 20 вводим формулу =D16/$D16, выделим C 15 и протянем мышью за правый нижний угол до E 20. В диапазоне A 17: E 20 получим:

1,0000 0,5000 -1,0000 0,5000 3,0000
0,0000 1,0000 -0,2500 -0,6250 1,0000
0,0000 0,0000 1,0000 -0,1667 -2,1538
      1,0000 2,6746

 

В таблице 3.1 показаны введенные формулы, которые можно увидеть, если выполнить команду меню «Сервис — параметры», выбрать вкладку «Вид» и отметить в параметрах окна флажком пункт «формулы».

5. Теперь остается выполнить обратный ход метода Гаусса. Для этого в ячейках F 17: F 20 введем формулы:

 

=E17-F20*D17-F19*C17-F18*B17
=E18-F20*D18-F19*C18
=E19-F20*D19
=E20

 

В ячейках F 17: F 20 получим ответ:

x 1 = –1,1677; x 2 = 2,2446; x 3 = –1,7081; x 2 =2,6746.

 

Таблица 3.1

  A B C D E
      -4    
      -4 -4  
      -8    
           
  =A1/$A1 =B1/$A1 =C1/$A1 =D1/$A1 =E1/$A1
  =A2-A$5*$A2 =B2-B$5*$A2 =C2-C$5*$A2 =D2-D$5*$A2 =E2-E$5*$A2
  =A3-A$5*$A3 =B3-B$5*$A3 =C3-C$5*$A3 =D3-D$5*$A3 =E3-E$5*$A3
  =A4-A$5*$A4 =B4-B$5*$A4 =C4-C$5*$A4 =D4-D$5*$A4 =E4-E$5*$A4
  =A5:E5 =A5:E5 =A5:E5 =A5:E5 =A5:E5
    =B6/$B6 =C6/$B6 =D6/$B6 =E6/$B6
    =B7-B$10*$B7 =C7-C$10*$B7 =D7-D$10*$B7 =E7-E$10*$B7
    =B8-B$10*$B8 =C8-C$10*$B8 =D8-D$10*$B8 =E8-E$10*$B8
  =A9:E10 =A9:E10 =A9:E10 =A9:E10 =A9:E10
  =A9:E10 =A9:E10 =A9:E10 =A9:E10 =A9:E10
      =C11/$C11 =D11/$C11 =E11/$C11
      =C12-C$15*$C12 =D12-D$15*$C12 =E12-E$15*$C12
  =A13:E15 =A13:E15 =A13:E15 =A13:E15 =A13:E15
  =A13:E15 =A13:E15 =A13:E15 =A13:E15 =A13:E15
  =A13:E15 =A13:E15 =A13:E15 =A13:E15 =A13:E15
        =D16/$D16 =E16/$D16

 

В таблице 3.2 приведены результаты решения системы (после снятия флажка с пункта «формулы» меню «Сервис — параметры»).

Таблица 3.2

  A B C D E F
      -4     12,0000
      -4 -4   14,0000
      -8     20,0000
            10,0000
  1,0000 0,5000 -1,0000 0,5000 3,0000  
  0,0000 8,0000 -2,0000 -5,0000 8,0000  
  0,0000 0,5000 -5,0000 0,5000 11,0000  
  0,0000 0,0000 9,0000 5,0000 -2,0000  
  1,0000 0,5000 -1,0000 0,5000 3,0000  
  0,0000 1,0000 -0,2500 -0,6250 1,0000  
    0,0000 -4,8750 0,8125 10,5000  
    0,0000 9,0000 5,0000 -2,0000  
  1,0000 0,5000 -1,0000 0,5000 3,0000  
  0,0000 1,0000 -0,2500 -0,6250 1,0000  
      1,0000 -0,1667 -2,1538  
      0,0000 6,5000 17,3846  
  1,0000 0,5000 -1,0000 0,5000 3,0000 -1,1677
  0,0000 1,0000 -0,2500 -0,6250 1,0000 2,2446
  0,0000 0,0000 1,0000 -0,1667 -2,1538 -1,7081
        1,0000 2,6746 2,6746

 

6. Для проверки правильности введенных формул умножим исходную матрицу коэффициентов, хранящихся в ячейках A 1: D 4, на столбец найденных решений F 17: F 20, и запишем полученные значения в столбец F 1: F 4.

Для этого выделим диапазон F 1: F 4, введем формулу

=МУМНОЖ(A1:D4;F17:F20)

и, удерживая нажатыми клавиши Ctrl и Shift, нажмем Enter. Значения в столбцах E 1: E 4 и F 1: F 4 должны совпадать.

Замечание. Приведенный лист с формулами можно применить для решения любой системы уравнений с четырьмя неизвестными. Для этого в диапазоне A 1: E 4 введем коэффициенты и правые части новой системы уравнений. В диапазоне F 17: F 20 автоматически отобразится решение новой системы уравнений.

Проверить правильность алгоритма можно, например, заменив числа в столбце E 1: E 4 суммами коэффициентов уравнений. Тогда вектор решений должен состоять из единиц.

Приведем программу на языке C ++ для решения системы линейных уравнений методом Гаусса с выбором главного элемента:

 

#include <except.h>

#include <iostream.h>

int gauss(long double **a, long double *b, long double *x, const int n);

int main(){

long double **a; long double *b; long double *x; int i,j,n;

cout <<" input n = "; cin >> n;

try {

a= new long double*[n]; for(i=0;i<n;i++) a[i]=new long double[n];

b= new long double[n]; x= new long double[n];

}

catch (xalloc){cout <<"\nCould not allocate\n"; exit(-1);}

cout <<"\n input matrix a \n";

for (i=0; i<n; i++)for (j=0; j<n; j++)cin >> a[i][j];

cout <<"\n input vector b\n";

for (i=0; i<n; i++)cin >> b[i];

cout << "\n matrix a: ";

for (i=0; i<n; i++){cout << "\n"; for (j=0; j<n; j++) cout <<" "<< a[i][j];}

cout << "\n vector b: ";

for (i=0; i<n; i++)cout << "\n " << b[i];

gauss(a, b, x, n);

cout << "\n vector x: ";

for (i=0; i<n; i++)cout << "\n x[" << i <<"] = " << x[i];

cout << "\n Press Key and Enter to continue";

cin >> i; // for pause

for(i=0;i<n;i++)delete[] a[i];

delete a;

delete[] b;

delete[] x;

return 0;

}//end main

int gauss(long double **a, long double *b, long double *x, const int n){

// Метод Гаусса с выбором главного элемента

int i, k, m, im; long double amm, aim, r;

for (m = 0; m <= n-2; m++) {// m

amm = a[m][m]; im = m;

for (i = m; i <= n-1; i++)

if(a[i][m] > amm){amm = a[i][m]; im = i; }

if(im!= m){r = b[im]; b[im] = b[m]; b[m] = r;

for (k = m; k <= n-1; k++)

{r = a[im][k]; a[im][k] = a[m][k]; a[m][k] = r;}

}

for (k = m; k <= n-1; k++)a[m][k] = a[m][k]/amm; // 3.16

b[m] = b[m] / amm; //

for (i = m + 1; i <= n-1; i++){// i

aim = a[i][m];

for (k = m; k <= n-1; k++)

a[i][k] = a[i][k] - a[m][k]*aim; // 3.17

b[i] = b[i] - b[m]*aim; //

}// end i

}// end m

x[n-1] = b[n-1]/a[n-1][n-1]; // 3.19

for (i = n - 2; i >= 0; i--){// i

x[i] = b[i]; //

for (k = i + 1; k < n; k++) // 3.20

x[i] = x[i] - a[i][k]*x[k]; //

}// end i

return 0;

}// end gauss

 

Приведем для сравнения вариант процедуры обычного метода Гаусса:

 

int gauss(long double **a, long double *b, long double *x, const int n){

// Метод Гаусса

int i, k, m; long double amm, aim;

for (m = 0; m <= n-2; m++) {// m

amm = a[m][m];

for (k = m; k <= n-1; k++)a[m][k] = a[m][k]/amm; // 3.16

b[m] = b[m] / amm;

for (i = m + 1; i <= n-1; i++){// i

aim = a[i][m];

for (k = m; k <= n-1; k++)

a[i][k] = a[i][k] - a[m][k]*aim; // 3.17

b[i] = b[i] - b[m]*aim;

} // end i

} // end m

x[n-1] = b[n-1]/a[n-1][n-1]; // 3.19

for (i = n - 2; i >= 0; i--){// i

x[i] = b[i];

for (k = i + 1; k < n; k++) // 3.20

x[i] = x[i] - a[i][k]*x[k];

} // end i

return 0;

} // end gauss

 

Отметим, что в процедуре gauss() массивы исходных данных a и b не сохраняются, так как результаты преобразований записываются в эти же массивы.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.028 сек.)