Математика

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

Саратовский государственный технический университет

МАТЕМАТИКА

Методические указания и задания

к самостоятельной работе студентов

по разделу «Методы решения систем линейных

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

для всех специальностей всех форм обучения

Одобрено

Редакционно-издательским советом

Саратовского государственного

технического университета

Энгельс 2007

Основные понятия

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

а11х1 + а12х2 + … + а1nXn = a1(n+1)

а21х1 + а22х2 + … + а2nXn = a2(n+1) (1)

. . .

аn1х1 + аn2х2 + … + аnnXn = an(n+1)

или в матричной форме

АХ=В

где

а11 а12 … а1n

А=(аij)= а21 а22 … а2n

…

аn1 аn2 … аnn - матрица коэффициентов системы

a 1(n+1) х1

В = a 2(n+1) , Х = х2

. . . …

a n(n+1) хn

-  соответственно столбец свободных членов и столбец неизвестных.

Если матрица А неособенная, т. е. detА≠0, то система (1) имеет единственное решение.

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

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

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

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

Метод Гаусса

Пусть в системе (1) коэффициент а11≠0.

Назовем а11 ведущим элементом первой строки.

Разделив первое уравнение системы (1) на а11 получим новое уравнение:

(2)

Для исключения из каждого уравнения системы (1) начиная со второго, будем умножать уравнение (2) последовательно на а21, а31 и т. д. и вычитать из второго, третьего и т. д. уравнений системы соответственно.

Получим:

(3)

…

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

(4)

…

Таким образом, коэффициенты системы (4) находятся с помощью формул:

, (5)

____ _____

где k+1≤ j ≤n+1, k+1≤ i ≤n, k=1,n (, i, j = 1,(n+1))

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

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

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

Замечание.

1)  Если в ходе расчета оказалось, что элемент , то исключение по формулам (5) нельзя проводить. Но все элементы к-го столбца не могут быть нулями; это означало бы, что detА=0. Перестановкой строк можно переместить ненулевой элемент на главную диагональ и продолжить расчет.

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

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

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

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

Этот метод надежен, прост и наиболее выгоден для линейных систем общего вида с плотно заполненной матрицей.

Проиллюстрируем применение метода Гаусса на следующем примере.

Пример1. Решить методом Гаусса систему линейных алгебраических уравнений:

х1+0,17х2+0,25х3+0,54х4=0,3

0,47х1+х2+0,67х3-0,32х4=0,5 (6)

-0,11х1+0,35х2+х3-0,74х4=0,7

0,55х1+0,43х2+0,36х3+х4=0,9

Решение:

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

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

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

2.  Суммируем все коэффициенты по строке и записываем сумму с обратным знаком в последний столбец, т. е.

, i=1,4.

Тогда сумма всех элементов каждой из четырех начальных строк будет равна нулю.

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

Делим все числа, стоящие в первой строке, на и записываем в первую строку шага II.

4.  По формулам (5) вычисляем коэффициенты , i=2,4, J=2,6. Результаты записываем в соответствующие строки шага II. С элементами последнего столбца поступаем так же, как с элементами предыдущих столбцов.

5.  Для проверки правильности вычислений находим сумму элементов каждой строки. Величина суммы должна отличаться от нуля в пределах ошибок округления. Большое отклонение от нуля свидетельствует о наличии грубой ошибки в вычислениях.

6.  Среди элементов выбираем главный элемент и поступаем как в п.3. Пусть - главный элемент. Делим на него вторую строку шага II и результат записываем в первую строку шага III.

7.  По формулам (5) вычисляем коэффициенты , i=3,4, J=3,6. Результаты записываем во вторую и третью строки шага III.

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

9.  Пусть - главный элемент. Делим на него вторую строку шага III и результат записываем в первую строку шага IV.

10.  По формулам (5) вычисляем Результаты записываем во вторую строку шага IV.

11.  Проверяем правильность вычислений (п.5).

Обратный ход

1.  В шаге V записываем единицы.

2.  Вычисляем

3.  Для вычислений используются лишь первые строки шагов II, III, IV, т. е. строки, содержащие единицы:

; ;

(7)

находят по формулам (7), заменяя на , i=3,2,1).

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

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

Шаг
I	1 0,47 -0,11 0,55	0,17 1 0,35 0,43	-0,25 0,67 1 0,36	-0,54 -0,32 -0,74 1	0,3 0,5 0,7 0,9	-1,76 -2,32 -1,2 -3,24
II	1	0,17 0,9201 0,3687 0,3365	-0,25 0,7875 0,9725 0,4975	-0,54 -0,5738 -0,6806 0,7030	0,3 0,3590 0,7330 0,7350	-1,76 -1,4928 -1,3936 -2,2720
III		1	0,8559 0,6569 0,2095	-0,6236 -0,4507 0,9128	0,3902 0,5891 0,6037	-1,6224 -0,7954 -1,7261
IV			1	-0,6861 1,0565	0,8968 0,4158	-1,2108 -1,4724
V	1	1	1	1	0,3936 1,1668 -0,3630 0,4409	-1,3937 -2,1670 -0,6368 -1,4409

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

=0,44, = -0,36, =1,17, =0,39.

(Главные элементы заключены в рамки.)

Метод простой итерации

Пусть задана линейная система уравнений.

Приведем ее к виду:

Х=СХ+F (8)

где С – некоторая матрица, а F – вектор – столбец.

Исходя из произвольного вектора Х(0)

Х0 =

,

Строим итерационный процесс.

Х(к+1) = СХ(к) + F, к = 0,1,2,…

или в развернутом виде:

;

…

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

Х(1), Х(2), Х(3), …Х(к).

Известно, что если элементы матрицы С удовлетворяют одному из условий:

i=1,n

j=1,n (9)

то итерационный процесс сходится к точному решению системы Х при любом начальном векторе Х(0), т. е.

Х=limХ(к)

к→∞

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

Приведение систем (1) к виду (8) можно осуществить различными способами. Важно только, чтобы выполнялось одно из условий (9).

На практике поступают следующим образом: из заданной системы (1) выделяют уравнения с коэффициентами, модули которых больше сумм модулей остальных коэффициентов уравнения.

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

Оценка погрешности приближенного решения Х(к) дается одной из следующих формул:

j= (10)

Если выполняется первое из условий (9), или

Если выполняется второе из условий (9).

Процесс итерации заканчивается, когда указанные оценки свидетельствуют о достижении заданной точности.

Замечания:

1)  Если итерационный процесс сходится достаточно быстро, т. е. если для решения систем требуется менее к итераций, то получаем выигрыш во времени по сравнению с методом Гаусса, так как число арифметических действий, необходимых для одной итерации, пропорционально n2, а в методе Гаусса – n3.

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

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

4)  В качестве нулевого приближения Х(0) можно принимать столбец свободных членов.

Пример 2.

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

2х1 + 3х2 – 4х3 + х4 – 3 = 0 (а)

х1 - 2х2 – 5х3 + х4 – 2 = 0 (б)

5х1 - 3х2 + х3 -4х4 – 1 = 0 (в)

10х1 + 2х2 – х3 + 2х4 +4 = 0 (г)

Решение.

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

10х1 + 2х2 – х3 + 2х4 +4 = 0 (а’)

5х1 - 3х2 + х3 -4х4 – 1 = 0 (б’)

х1 - 2х2 – 5х3 + х4 – 2 = 0 (в’)

2х1 + 3х2 – 4х3 + х4 – 3 = 0 (г’)

Для получения второго уравнения преобразованной системы вычтем из (г’) - (в’), получим:

10х1 + 2х2 – х3 + 2х4 +4 = 0 (а’’)

х1 + 5х2 + х3 – 1 = 0 (б’’)

х1 - 2х2 – 5х3 + х4 – 2 = 0 (в’’)

5х1 - 3х2 + х3 -4х4 – 1 = 0 (г’’)

Преобразуем и последнее уравнение системы с помощью линейной комбинации: 2(а’’) - (б’’) + 2(в’’)- (г’’).

10х1 + 2х2 – х3 + 2х4 +4 = 0

х1 + 5х2 + х3 – 1 = 0

х1 - 2х2 – 5х3 + х4 – 2 = 0

3х1 + 0х2 + 0х3 - 9х4 – 10 = 0

В итоге получим преобразованную систему:

х1=0х1-0,2х2+0,1х3-0,2х4-0,4

х2=-0,2х1+0х2-0,2х3+0х4+0,2

х3=0,2х1-0,4х2+0х3+0,2х4-0,4

х4=0,333х1+0х2+0х3+0х4-1,111

к которой можно применить метод простой итерации.

Пример 3.

Методом простой итерации решить систему уравнений (е=10-3).

20,9х1 + 1,2х2 + 2,1х3 + 0,9х4 = 21,7

1,2х1 + 21,2х2 + 1,5х3 + 2,5х4 = 27,46

2,1х1 + 1,5х2 + 19,8х3 + 1,3х4 = 28,76

0,9х1 + 2,5х2 + 1,3х3 + 32,1х4 = 49,72

Решение:

Приведем систему к виду (8)

х1=*(21,7-1,2х2-2,1х3-0,9х4)

х2=*(27,46-1,2х1-1,5х3-2,4х4)

х3=*(28,76-2,1х1-1,5х2-1,3х4)

х4=*(49,72-0,9х1-2,5х2-1,39х3)

Коэффициенты полученной системы удовлетворяют первому условию (9). Действительно,

; ;

;

Следовательно, сходимость по методу итераций гарантирована.

В качестве начального вектора Х(о) возьмем элементы столбца свободных членов:

 

1,04

Х(0) = 1,30

1,45

1,55

Последовательно вычисляем

при к=1

при к=2

= 0,8106, = 1,0118, = 1,2117, = 1,4077

при к=3

= 0,7978, = 0,9977, = 1,1975, = 1,3983

при к=4

= 0,8004, = 1,0005, = 1,2005, = 1,4003

при к=5

= 0,7999, = 0,9999, = 1,1999, = 1,3999

Находим модули разности значений при к=4 и к=5:

=0,0005; = 0,0006;

=0,0006; = 0,0004.

В соответствии с оценкой (10) погрешность этих значений

max = *0,0006 = 0,0002

Она меньше заданного числа ε, потому в качестве решения возьмем

х1≈0,7999; х2≈0,9999; х3≈1,1999; х4≈1,3999.

Для сравнения приведем точные значения неизвестных:

х1=0,8; х2=1,0; х3=1,2; х4=1,4.

ЗАДАНИЯ

1. Методом Гаусса решить систему уравнения (ε=10-4);

3,81х1+0,25х2+1,28х3+(0,75+а)х4 = 4,21;

3,25х1+1,32х2+(4,58+а)х3+0,49х4 = 6,47+β;

5,31х1+(6,28+а)х2+0,98х3+1,04х4 = 2,38;

(9,39+а))х1+2,45х2+3,35х3+2,28х4 = 10,48+ β;

где а=0,5к; к=0,1,2,3,4; β=0,5n; n=0,1,2,3,4..20.

2. Методом простой итерации решить систему уравнений (ε=10-4);

(24,21+а)х1+2,42х2+3,85х3 = 30,24;

2,31х1+31,49х2+1,52х3 = 40,95- β;

3,49х1+4,85х2+(28,72+а)х3 = 42,81;

где а=0,2к; к=0,1,2,3,4; β=0,2n; n=0,1,2,3,4..20.

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

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

(11)

с положительно-определенной симметрической матрицей A.

Идея метода градиентного (наискорейшего)спуска состоит в отыскании вектора, доставляющего минимум функционалу

Такой вектор отличается от функции ошибки лишь постоянным, заранее неизвестным слагаемым Здесь - точное решение системы (11), совпадающее с вектором, реализующим минимум - вектор ошибки.

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

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

Тогда ;

Далее определяется

где , и процесс продолжается по формулам

,

при этом функция ошибки

.

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

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

Метод градиентного спуска может быть применен и к системам с несимметрической матрицей. Для этого надо систему уравнений (11) умножить на транспонированную матрицу A`. Получим систему с симметрической матрицей .

В качестве невязки берем где .

Расчетные формулы имеют вид

при = = .

Пример 4.

Методом градиентного спуска решить систему уравнений

Решение.

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

i
1	2	3	4	5
1	0 0 0	-0.7 2.5 0.1	-3.98 10.12 -0.3	0.24059
2	-0.16841 0.60148 0.02406	0.25755 0.06523 0.17218	0.61961 -0.00116 0.19995	0.51684
3	-0.03530 0.63519 0.11305	-0.06269 0.06582 0.06884	-0.20219 0.29966 0.04283	0.36781
4	-0.05836 0.65940 0.13836	0.01168 -0.04439 0.05308	0.07976 -0.18451 0.05453	0.40980
5	-0.05357 0.64121 0.16012	-0.02101 0.03122 0.03073	-0.07447 0.13447 0.02033	0.36954
6	-0.061134 0.65274 0.17147	0.00651 -0.01847 0.02322	0.03754 -0.07837 0.02404	0.39288
7	-0.05867 0.64517 0.18099	-0.00888 0.01366 0.01336	-0.03183 0.05857 0.00888	0.36953
8	-0.06195 0.65022 0.18593	0.00288 -0.01008 0.01008	0.01640 -0.03393 0.01044	0.41016
9	-0.06077 0.64694 0.19006	-0.00384 0.00593 0.00580	-0.01379 0.02541 0.00385	0.36975
10	-0.06219 0.64913 0.19220	0.00125 -0.00346 0.00437	0.00712 -0.01447 0.00453	0.40997
11	-0,06167 0,64772 0,19399	-0,00167 0,00257 0,00251	-0,00598 0,01103 0,00167	0,36905
12	-0,06229 0,64867 0,19492	0,00054 -0,00150 0,00190	0,00309 -0,00638 0,00197	0,41061
13	-0,06207 0,64805 0,19570	-0,00072 0,00112 0,00109	-0,00259 0,00478 0,00073	0,39262
14	-0,06234 0,64846 0,19610	0,00024 -0,00065 0,00082	0,00134 -0,00277 0,00085	0,40881
15	-0,06224 0,64820 0,19644	-0,00031 0,00048 0,00047	-0,00112 0,00207 0,00031	0,36825
16	-0,06235 0,64837 0,19661	0,00010 -0,00028 0,00036	0,00058 -0,00120 0,00037	0,41351
17	-0,06231 0,64826 0,19676	-0,00014 0,00021 0,00020	-0,00049 0,00090 0,00014	0,36309

На следующем шаге получаем приближенное значение системы:

Х1=-0,06236; х2=0,64834; х3=0,19684.

ЗАДАНИЯ

1.  Методом градиентного спуска решить систему линейных уравнений:

(3,1+а)х1 + 1,5х2 + х3 = 10,83 – β;

1,5х1 + (2,5-а)х2 + 0,5х3 = 9,2;

х1 + 0,5х2 +(4,2+а) х3 = 17,10 – β;

где а=0,25к, к=0,1,2,3,4; β=0,35n, n=1,2,3…20;

Вычисления вести до тех пор, пока

2.  Методом градиентного спуска решить систему линейных уравнений

3,81х1 + 0,25х2 +1,28 х3 +(0,75+а)х4= 4,21;

2,25х1 + 1,32х2 +(4,58+а) х3 +0,49х4= 6,47+β;

5,31х1 + (6,28+а)х2 +0,98 х3 +1,04х4= 2,38;

(9,39+а)х1 + 2,45х2 +3,35 х3 +2,28х4= 10,48+β;

где а=0,5к, к=0,1,2,3,4; β=0,5n, n=1,2,3…20; ε= 10-4.

ЛИТЕРАТУРА

1)  , Вычислительные методы линейной алгебры. – М. – Л: физматгиз, 1963 – 734 с.

2)  . Численные методы. – М.: Наука. 1977. – 300 с.

3)  . Численные методы. – М.:Наука. 1982. – 254 с.

4)  . Элементы методов вычислений. –Мн.: Изд-во Белорус. ун-та, 1982. – 164 с.

5)  . Численные методы. – М: Наука 1978 – 512 с.

6)  . Численные методы. – М:Наука 1975. – Т1 – 631 с.

7)  , . Вычислительная математика в примерах и задачах. –М:Наука 1972 – 367 с.

МАТЕМАТИКА

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

Составил:

Пономарев