Схема Гаусса с выбором главного элемента

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Курганский государственный университет

Кафедра математического анализа

 

 

 

 

Метод ГАУССА и его модификации

 

    Методические указания для лабораторных занятий и самостоятельной работы студентов по вычислительной математике специальностей Математика 050201, Информатика 050202, Физика 050203    

 

Курган 2006

Кафедра математического анализа

 

Дисциплина «Математика» (специальности 050201,050202, 050203)

 

Составил: канд. пед. наук, доцент Михащенко Т.Н.

 

 

Составлены на основании ГОС ВПО для специальностей Математика «050201.65», Информатика «050202.65», Физика «050203.65». Методические указания могут быть использованы для проведения лабораторных занятий и организации самостоятельной работы студентов специальности 050202 – Информатика с дополнительной специальностью математика, 050201 – Математика с дополнительной специальностью информатика                                                                         

 

Введение

 

Как утверждается в книге известного американского математика Валяха, 75% всех расчётных математических задач приходится на решение систем линейных алгебраических уравнений. Это не удивительно, так как математические модели тех или иных явлений или процессов либо сразу строятся как линейные, либо сводятся к таковым. Поэтому трудно переоценить роль, которую играет выбор эффективного способа решения системы линейных уравнений. Современная вычислительная математика располагает большим арсеналом методов, а математическое обеспечение ЭВМ­ – многими пакетами прикладных программ, позволяющих решать различные возникающие на практике линейные системы.

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

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

На выбор студенту предлагается несколько модификаций проведения и оформления вычислений: полная и компактная схемы Гаусса, модификация Краута-Дулитла, схема Гаусса с выбором главного элемента и схема Халецкого. 

 

1. Компактная схема Гаусса

 

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

Рассмотрим порядок составления схемы для системы четырёх уравнений с четырьмя неизвестными. Все результаты вычислений будем записывать в одну таблицу (табл. 1).

Порядок заполнения таблицы, прямой ход:

1) Записываем коэффициенты данной системы в четырёх строках и пяти столбцах раздела I (табл. 1).

2) Суммируем все коэффициенты по строке и записываем сумму в столбце å (столбец контроля), например a16= .

 

3) Делим все числа, стоящие в первой строке, на a11 и результаты b1j=a1j /a11 записываем в пятой строке раздела I.

4) Вычисляем  и делаем проверку. Если вычисления ведутся постоянным знаком после запятой, то числа b16 и  не должны отличаться более чем на единицу последнего разряда. В противном случае следует проверить действия пункта 3.

 

5) Вычисляем коэффициенты a  (i =2,3,4; j=2,3,4,5,6):a =aijai1b1j.

6)   Результаты записываем в первые три строки раздела II.

7) Делаем проверку. Сумма элементов каждой строки  (i=2,3,4) не должна отличаться от a  более чем на единицу последнего разряда (если все вычисления ведутся с постоянным числом знаков после запятой).

 

8) Делим все элементы первой строки раздела II на a  и результаты записываем в четвёртой строке раздела II. Делаем проверку как в пункте 4.

9) Вычисляем a ,  a =a a b , (i=3,4; j=3,4,5,6). Делаем проверку, как в пункте 6.

10) Делим элементы первой строки раздела III на a  и находим числа b =a /a . Все результаты записываем в третьей строке раздела III. Делаем проверку.

 

11) Вычисляем a =a  - a b . Результаты записываем в разделе IV.

Таблица 1

Компактная схема Гаусса

 

            i ai1 ai2 ai3 ai4 ai5 S= ai6

I

1 a11 a12 a13 a14 a15 Sa1j = a16
2 a21 a22 a23 a24 a25 Sa2j = a26
3 a31 a32 a33 a34 a35 Sa3j = a36
4 a41 a42 a43 a44 a45 Sa4j = a46
  1 b12 b13 b14 b15 a16 / a11= b15

II

2   a a a a a
3   a a a a a
4   a a a a a
    1 b b b a /a =b

III

3     a a a a
4     a a a a
      1 b b a /a =b
IV 4       a a a

V

        1 x4  
      1   x3  
    1     x2  
  1       x1  

Обратный ход:

12) В разделе V записываем единицы, как это указано в табл. 1, вычисляем x4=a /a .

13) Для вычисления значений x3,x2,x1 используются лишь строки разделов I, II, III, содержащие единицы (отмеченные строки). Так для вычисления x3 умножаем x4 на b  и получившееся произведение вычитаем из b . При этом единицы, расставленные в разделе V, помогают находить для xi (i=3,2,1) соответствующие коэффициенты    в    отмеченных    строках.  Таким  образом,

x3= b - b x4.

14) Вычисляем x2, и затем x1, для чего используем элементы отмеченной строки раздела II:       x2= b - b x4- b  x3,  

x1= b - b x4 - b x3 - b x2.

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

 

Решим с помощью компактной схемы Гаусса систему уравнений, все вычисления занесем в таблицу (табл.2):

 

Следуя порядку действий, указанному в параграфе 1, получаем значения неизвестных: x4=0,068976; х3=-1,815417; x2=0,964032; х1=4,870672.

 

Проверка показывает, с какой точностью получен результат, погрешность вычислений не превосходит соответственно 0,0000029;  0,0000028; 0,000001; 0,000016 в первом, втором, третьем и четвертом уравнениях.

 

 

Таблица 2

  i x1 x2 x3 x4 Свободные члены S S1

I

1 2 -3,5 2,7 -8,2 0,9 -6,1 -6,1
2 1 2,8 3,6 2,4 1,2 11 11
3 1 2,5 -3,8 -2,6 14 11,1 11,1
4 5 -6 4,8 2,1 10 15,9 15,9
  1 -1,75 1,35 -4,1 0,45 -3,05 -3,05

II

2   4,55 2,25 6,5 0,75 14,05 14,05
3   4,25 -5,15 1,5 13,55 14,15 14,15
4   2,75 -1,95 22,6 7,75 31,15 31,15
    1 0,494505 1,428571 0,164835 3,087912 3,087912

III

3     -7,251648 -4,571429 12,849451 1,026374 1,026374
4     -3,30989 18,671429 7,296703 22,658242 22,658242
      1 0,630399 -1,771935 -0,141537 -0,141537

IV

4       20,757978 1,431793 22,189771 22,189771
        1 0,068976 1,068976 1,068976

V

        1 0,068976   0,0000029
      1   -1,815417   0,0000028
    1     0,964032   0,000001
  1       4,870672   0,000016

 

       

 

2. Модификация Краута – Дулитла

 

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

Порядок заполнения таблицы, прямой ход:

1) Записываем коэффициенты системы aijдля i=1,2,3,4; j=1,2,3,4,5 в разделе I (табл.3).

2) Суммируем коэффициенты по каждой строке и результаты заносим в столбец å в качестве ai6 (i=1,2,3,4).

3) При i=2,3,4 находим числа mi1= ai1 / a11 и записываем их в разделе II.

4) При j=2,3,4,5,6 вычисляем коэффициенты a  по формуле a = a2j ­– m21а1j и записываем их вразделе III.

5) Контроль: сумма  не должна отличаться от a  более чем на единицу последнего разряда.

6) При i=3,4 находим числа тi2по формуле тi2=(ai2mi1a12)/ a  и заносим в раздел IV.

7)  При j=3,4,5,6 вычисляем коэффициенты a  по формуле

 a = a3j m31a1jm32 a  и записываем в раздел V.

8) Находим число m43=(a43m41а13m42a )/ a  и записываем его в раздел VI.

9) При j=4,5,6 находим коэффициенты a  по формуле                                         a = a4j m41a1jm42a  – m43a   и записываем в раздел VII.

10) Контроль: сравниваем сумму a ­ + a  с числом a .

Обратный ход осуществляется аналогично компактной схеме Гаусса. Находим неизвестные x4, x3, x2, x1 по формулам: a x4=a a x3+a x4= a ,  a x2+ a x3+ a x4= a ,     a11x1+a12x2+a13x3+a14x4= a15.Вычисления по этим формулам ведутся без промежуточных за­писей. Результаты записываются в разделе VIII таблицы.

Таблица 3

Схема Краута – Дулитла

  ai1 ai2 ai3 ai4 ai5 å= ai6
I a11 a21 a31 a41 a12 a22 a32 a42 a13 a23 a33 a43 a14 a24 a34 a44 a15 a25 a35 a45 a16 = åa1j a26 = åa2j a36 = åa3j a46 = åa4j
II m21 m31 m41          
III   a a a a a
IV   m32 m42        
V     a a a a
VI     m43      
VII       a a a
VIII   1     1     1     1   x4 x3 x2 x1  

 

 

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

 

Решим предыдущую систему с помощью схемы Краута – Дулитла систему уравнений, результаты вычислений занесем в таблицу (табл.4).

 

Таблица 4

 

ai1

ai2

ai3

ai4

ai5

S

S1

I

2

-3,5

2,7

-8,2

0,9

-6,1

 

1

2,8

3,6

2,4

1,2

11

 

1

2,5

-3,8

-2,6

14

11,1

 

5

-6

4,8

2,1

10

15,9

 

II

0,5

 

 

 

 

 

 

0,5

 

 

 

 

 

 

2,5

 

 

 

 

 

 

III

 

4,55

2,25

6,5

0,75

14,05

14,05

IV

 

0,934066

 

 

 

 

 

 

0,604396

 

 

 

 

 

V

 

 

-7,2516483

-4,5714285

12,84945

1,0263

1,0263

VI

 

 

0,4564327

 

 

 

 

VII

 

 

 

20,757978

1,431793

22,189

22,189

VIII

 

 

 

1

0,068976

 

 

 

 

1

 

-1,815417

 

 

 

1

 

 

0,964032

 

 

1

 

 

 

4,870726

 

 

 

Схема Гаусса с выбором главного элемента

Рассмотрим линейную систему уравнений:  

Запишем расширенную матрицу коэффициентов системы:

M= .

Среди элементов матрицы aij (i, j=1,...,n) выберем наибольший по модулю, называемый главным элементом. Пусть им будет, например, элемент apq. Строка с номером p, содержащая главный элемент, называется главной строкой. Далее вычисляем множители mi=aiq/apq для всех i p. Затем преобразуем матрицу следующим образом: из каждой i-й неглавной строки вычитаем почленно главную строку, умноженную на mi. В результате получим матрицу, у которой все элементы q-го столбца, за исключением, аpq равны нулю. Отбрасывая этот столбец и главную строку, получим новую матрицу Mt с меньшим на единицу числом строк и столбцов.

Над матрицей M1, повторяем те же операции, после чего получим матрицу M2,и т. д. Такие преобразования продолжаем до тех пор, пока не получим матрицу, содержащую одну строку из двух элементов, которую считаем тоже главной. Затем объединяем все главные строки, начиная с последней. После некоторой перестановки они образуют треугольную матрицу, эквивалентную исходной. На этом заканчивается этап вычислений, называемый прямым ходом. Решив систему с полученной треугольной матрицей коэффициентов, найдем последовательно значения неизвестных xi (i=1,2, ...,n). Этот этап вычислений называется обратным ходом.

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

Результаты всех вычислений удобно записывать в таблицу.

Прямой ход:

1) Записываем в первом разделе таблицы коэффициенты системы

aij (i=1,2,3,4; j=1,2,3,4,5).

2) В столбце å= ai6 записываем суммы коэффициентов по каждой строке.

3) Находим главный элемент, подчёркиваем его.

4) Находим числа mi по формуле mi= aiq/apq, где apq – главный элемент и результаты записываем в столбце mi раздела I.

5) Из каждой i–ой строки вычитаем главную строку, умноженную на соответствующий элемент mi.

6) Контроль: находим суммы  и сравниваем с ai6.

 

Решим с помощью данного метода ту же самую систему уравнений:    .

Результаты всех вычислений будем записывать в таблицу (табл. 5):

Прямой ход:

1) Записываем в первом разделе таблицы коэффициенты системы

aij (i=1,2,3,4; j=1,2,3,4,5).

2) В столбце å= ai6 записываем суммы коэффициентов по каждой строке.

3) Находим главный элемент. В данной системе им будет коэффициент   a14= -8,2 (p=1, q=4), выделяем этот элемент.

4) Находим числа mi (i=2,3,4). Для этого делим элементы столбца ai4 на a14 и результаты записываем в столбце mi разделаI:

m2= = =-0,292683 ; m3= = =0,3170732; m4= = =-0,256098.

5) Вычисляем коэффициенты новой матрицы. Из каждой i–ой (i=2,3,4) строки вычитаем главную строку, умноженную на соответствующий элемент mi.

Так, при i=2 будем иметь:

1 – (-0,292683)*2=1,5853659;

2,8 –­ (-0,292683)*(-3,5)= 1,7756098;

3,6 – (-0,292683)*2,7=4,3902439;

2,4 – (-0,292683)*(-8,2)=0;

1,2 ­– (-0,292683)*0,9=1,4634146;

11 – (-0,292683)*(-6,1)= 9,2146341.

При i=3,4 продолжаем вычисления аналогичным образом. Результаты записываем в разделе II. При этом не выписываем главную строку.

6) Контроль: находим суммы  и сравниваем с , например, 9,2146341=  и т.д.

7) Выбираем главный элемент, выделяем его. В нашем случае это будет = -6,8963415.

8) Делим элементы столбца ai2 на . Получаем числа:

= -0,257471;

-0,523431.

9) Вычисляем коэффициенты . Для этого из каждой i–ой (i=2,3) строки вычитаем главную строку, умноженную на соответствующий элемент . Так, при i=2 будем иметь:

1,5853659–(-0,257471)*5,5121951=

=3,0045977;

1,7756098 – (-0,257471)*(-6,8963415)=0;

4,3902439 – (-0,257471)*5,4914634=

=5,8041379;

1,4634146 – (-0,257471)*10,2304878=

=4,0974713;

9,2146341 – (-0,257471)* 14,3378049=

=12,9062069.

При  i=3 вычисления ведутся аналогично. Результаты записываем в разделе III, оставляя свободными уже столбцы ai2 и ai4.

10) Контроль: сумма (i=2,3) должна равняться ; это условие выполняется.

11) Выбираем главный элемент, выделяем его. В нашем случае это будет =5,8041379.

12) Находим -0,30697. Записываем в столбец mi раздела III.

13) Вычисляем коэффициенты . Для этого из третьей строки вычитаем главную строку, умноженную на соответствующий элемент . Получаем:

3,2511052 – (-0,30697)*3,2511052=

=4,1734273;

-1,7816976 – (-0,30697)*5,8041379=0;

19,0695844 – (-0,30697)*4,0974713=

=20,3273862;

Таблица 5

 

i

mi

ai1

ai2

ai3

ai4

ai5

S= ai6

S1

I

1

 

2

-3,5

2,7

-8,2

0,9

-6,1

 

2

-0,29268

1

2,8

3,6

2,4

1,2

11

 

3

0,31707

1

2,5

-3,8

-2,6

14

11,1

 

4

-0,25609

5

-6

4,8

2,1

10

15,9

 

II

2

-0,25741

1,585365

1,775609

4,3902439

0

1,46341

9,214634

9,21463

3

-0,52343

0,365853

3,609756

-4,656097

0

13,7146

13,03414

13,0341

4

 

5,512195

-6,89634

5,491463

0

10,2304

14,33780

14,3378

III

2

 

3,004597

0

5,804137

 

4,09747

12,90620

12,9062

3

-0,30697

3,251105

0

-1,781697

 

19,0695

20,53899

20,5389

IV

3

 

4,17342

0

 

20,3273

24,50081

24,5008

V

1

 

4,87066

x1

 

 

2

 

0,964032

x2

 

 

3

 

-1,815417

x3

 

 

4

 

0,06897

x4

 

 

20,5389920 – (-0,30697)* 2,9062069=

=24,5008135.

14) Контроль: .

15) Выписываем главные строки каждого раздела. Получим систему, эквивалентную данной системе:

Обратный ход:

16) Результаты вычислений при реализации обратного хода записываем в разделе V: x1=20,3273862/4,1734273= 4,8706698,

x3=(4,0974713 – 3,0045977*4,8706698)/ 5,8041379= -1,8154172,

x2=(10,2304878 – 5,5121951*4,8706698 – 5,4914634*(-1,8154172))/

/ (-6,8963415)= 0,9640325,

x4=(0,9 – 2*4,8706698+3,5*0,9640325 – 2,7*(-1,8154172))/( -8,2)=0,0689755.

Схема Халецкого

    Рассмотрим систему линейных уравнений, записанную в матрич­ном виде:  Ax=b,  где A=(aij) – квадратная матрица (i, j=1,2,...,n)  и x=  

b=  – векторы-столбцы. Представим матрицу A в виде произведения A=BC,    где B= ,     C= .  

Тогда элементы bij и cij будут определяться по формулам:

 

и              

 

   Отсюда искомый вектор x может быть вычислен из цепи уравнений By=b,Cx=y.          Так как матрицы B и C треугольные, то данные системы легко решаются, а именно:

 

и 

 

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

Рассмотрим порядок составления схемы для системы четырёх уравнений с четырьмя неизвестными. Все результаты вычислений будем записывать в одну таблицу (табл. 6).

Порядок заполнения таблицы:

1) В первый раздел табл. 4 вписываем матрицу коэффициентов системы, её свободные члены и контрольные суммы.

2) Элементы столбца x1 из раздела I переносим в столбец x1 из раздела II, так как bi1­=ai1 (i=1,2,3,4).

3) Вычисляем элементы первой строки раздела II. Для этого делим все элементы первой строки раздела I на элемент a11= b11.

4) Заполняем столбец x2 раздела II, начиная со второй строки. Пользуясь вышеприведенными формулами, определяем bj2.

5) Заполняем вторую строку раздела II, определяя c2j для j=3,4,5,6.

6) Заполняем столбец x3, вычисляя его элементы b33 и b43.

7) Аналогично продолжаем процесс до тех пор, пока не будет заполнен раздел II. Таким образом, заполнение раздела II происходит способом “ёлочки”: столбец – строка, столбец – строка и т.д.

8) Определяем yi и xi (i=1,2,3,4) по соответствующим формулам и записываем в разделе III.

9) Текущий контроль осуществляем с помощью столбца å, над которым производим те же действия, что и над столбцом свободных членов.

 

Таблица 6

Схема Халецкого

 

x1

x2

x3

x4

 

S

I

a11

a12

a13

a14

a15

a16

a21

a22

a23

a24

a25

a26

a31

a32

a33

a34

a35

a36

a41

a42

a43

a44

a45

a46

II

b11

1

c12

c13

c14

c15

c16

b21

b22

1

c24

c24

c25

c26

b31

b32

b33

1

c34

c35

c36

b41

b42

b43

b44

1

c45

c46

III

1

 

 

 

y1

x1

 

1

 

 

y2

x2

 

 

1

 

y3

x3

 

 

 

1

y4

x4

                     

Решим, используя схему Халецкого систему уравнений

Результаты всех вычислений будем записывать в таблице (табл.7):

1) В первый раздел табл. 4 вписываем матрицу коэффициентов системы, её свободные члены и контрольные суммы.

2) Элементы столбца x1 из раздела I переносим в столбец x1 из раздела II, так как bi1­=ai1 (i=1,2,3,4).

3) Вычисляем элементы первой строки раздела II. Для этого делим все элементы первой строки раздела I на элемент a11= b11, в нашем случае

 на 2. Имеем:

c12=  c13=  c14=  c15=  c16=

4) Заполняем столбец x2 раздела II, начиная со второй строки. Пользуясь формулами, определяем bj2:

5) Заполняем вторую строку раздела II, определяя c2j для j=3,4,5,6

6) Заполняем столбец x3, вычисляя его элементы b33 и b43. Аналогично продолжаем процесс до тех пор, пока не будет заполнен раздел II.

7) Определяем yi и xi (i=1,2,3,4) и записываем их в разделе III:

 

        

 

Таблица 7

 

x1

x2

x3

x4

 

S

S

I

2

-3,5

2,7

-8,2

0,9

-6,1

 

1

2,8

3,6

2,4

1,2

11

 

1

2,5

-3,8

-2,6

14

11,1

 

5

-6

4,8

2,1

10

15,9

 

II

2     1

-1,75

1,35

-4,1

0,45

-3,05

-3,05

1

4,55 1

0,494505

1,428571

0,164835

3,087912

3,087912

1

4,25

-7,25165 1

0,630398

-1,77193

-0,14154

-0,14154

5

2,75

-3,30989011

20,757978 1

0,068976

1,068976

1,068976

III

1

 

 

 

0,45

4,870671

 

 

1

 

 

0,164835

0,964032

 

 

 

1

 

-1,77193

-1,81541

 

 

 

 

1

0,068976

0,068976

 

 

 


Дата добавления: 2018-04-04; просмотров: 1649; Мы поможем в написании вашей работы!

Поделиться с друзьями:




Мы поможем в написании ваших работ!