Схема Гаусса с выбором главного элемента
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Курганский государственный университет
Кафедра математического анализа
Метод ГАУССА и его модификации
Методические указания для лабораторных занятий и самостоятельной работы студентов по вычислительной математике специальностей Математика 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 =aij–ai1b1j.
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=(ai2– mi1a12)/ a и заносим в раздел IV.
7) При j=3,4,5,6 вычисляем коэффициенты a по формуле
a = a3j – m31a1j – m32 a и записываем в раздел V.
8) Находим число m43=(a43 – m41а13 – m42a )/ a и записываем его в раздел VI.
9) При j=4,5,6 находим коэффициенты a по формуле a = a4j – m41a1j – m42a – 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!