Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Прямые методы_Лин.ур-ий

.pdf
Скачиваний:
9
Добавлен:
04.06.2015
Размер:
393.11 Кб
Скачать

Лекция 3. Численные методы решения систем линейных алгебраических уравнений. Прямые методы (метод Гаусса).

Рассмотрим численные методы решения систем линейных алгебраических уравнений

Ax f ,

(1.1)

где A матрица размера

m m ,

x (x ,....,x

m

)T искомый вектор,

 

 

1

 

f ( f1 ,...., fm ) заданный вектор. Предполагается, что определитель матри-

цы A отличен от нуля, так что решение x существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы A . Из курса алгебры известно, что систему (1) можно решить, по крайней мере, двумя способами: либо по формулам Крамера, либо методом последовательного исключения неизвестных (методом Гаусса). При больших m первый способ, основанный на вычислении определителей, требует порядка m! арифметических действий, в то время как метод Гаусса –

только 0(m3 ) действий.

Методы численного решения системы (1) делятся на две группы: прямые методы и итерационные методы. В прямых (или точных) методах решение системы (1) находится за конечное число арифметических операций.

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

Итерационные методы (их называют также методами последовательных приближений) состоят в том, что решение x системы (1) находится как

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

Запишем систему (1) в развернутом виде

a11x1 a12x2

 

 

a1m xm

f 1

 

a21x a22x2

 

 

a2m xm

 

f 2

(1.2)

 

 

 

 

 

 

am1x am2x2

 

 

amm xm

 

fm.

 

1

Метод Гаусса решения системы (2) состоит в последовательном

исключении

неизвестных

x1,....,xm из

этой системы. Предположим, что

a11 0. Поделив первой уравнение на a11,

получим

 

 

x1 c12x2

.... c1mxm y1,

 

 

 

 

(1.3)

 

где c

 

a1 j

, j 2,....,m, y

f

1

.

 

 

 

 

 

 

 

 

 

 

1 j

 

a11

 

 

1

a11

 

 

 

 

 

 

 

 

 

 

 

Рассмотрим

теперь

оставшиеся

уравнения

системы

(1.3)

ai1x1 ai2x2 .... aimxm fi ,i 2,3,....,m.

 

(1.4)

 

Умножим (1.3) на ai1 и вычтем полученное уравнение из i го уравнения

системы (1.4), i=2,….,m. В результате получим следующую систему уравнений:

x1 c12x2

 

c1jx j

 

 

c1m xm

y1,

a(1) x

2

 

 

a(1) x

j

 

 

a(1)

 

 

f (1)

,

22

 

 

 

2 j

 

 

2m

 

 

2

(1.5)

 

 

 

 

 

 

a(1)

x

2

 

 

a(1) x

j

 

 

a(1)

x

m

 

f (1) .

m2

 

 

 

 

mj

 

 

mm

 

 

m

 

Здесь обозначено

a(1)

a

c

a

,

f (1)

f

i

y a

i1

,i, j 2,3,....,m.

(1.6)

ij

ij

1 j

i1

 

i

 

1

 

 

Матрица системы (1.5) имеет вид

 

1

с12

с1m

 

 

0

(1)

(1)

 

 

a22

a2m

 

 

 

.

 

 

0

(1)

(1)

 

 

am2

amm

Матрицы такой структуры принято обозначать так:

 

1

 

 

 

0

 

 

 

 

 

,

 

 

 

 

 

 

 

0

 

2

где крестиками

обозначены

 

ненулевые

элементы.

В

системе

(5)

неизвестное

 

 

 

xi

содержится только

в первом

уравнении,

поэтому в

дальнейшем достаточно иметь дело с укороченной системой уравнений

 

a(1) x

2

 

 

 

a(1) x

j

 

 

a(1)

 

 

f

(1) ,

 

 

22

 

 

 

2 j

 

 

2m

 

 

 

2

 

(1.7)

 

 

 

 

 

 

 

 

a(1) x

2

 

 

a(1) x

j

 

 

a(1) x

m

 

f (1) .

 

 

m2

 

 

 

mj

 

 

mm

 

 

m

 

 

Тем самым осуществлен первый шаг метода Гаусса.

Если

a(1)

0,

то из

 

 

 

 

 

 

 

 

 

 

 

 

 

 

22

 

 

системы (1.7)

 

 

совершенно аналогично можно исключить неизвестное

x2 и

прийти к системе, эквивалентной (1.2) и имеющей матрицы следующей структуры:

 

1

 

 

 

 

0

1

 

 

 

 

 

 

 

 

0

0

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

 

 

При этом первое уравнение системы (1.5) остается без изменений.

Исключая таким образом, неизвестные x3 , x4 ,....,xm ,

придем окончательно к

системе уравнений вида

 

 

 

 

 

 

x1 c12x2

 

 

c1m xm

y1,

 

 

x2

 

 

c2m xm

y2 ,

 

 

 

 

 

 

 

 

 

 

(1.8)

 

 

 

xm 1

 

cm 1,m xm

 

ym 1,

 

 

 

 

 

 

xm

 

 

ym,

 

эквивалентной системе (1.2).

 

 

 

 

 

Матрица этой системы

 

 

 

 

 

 

1

с12 с1m 1

с1,m

 

 

 

 

 

 

1 c2,m 1

 

 

 

 

 

 

0

c2,m

 

 

 

С

 

 

 

 

 

(1.9)

 

 

 

 

 

 

 

 

 

 

 

0

0

1

cm 1.m

 

 

 

 

0

0

 

0

1

 

 

 

 

 

 

 

 

 

3

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

Получение системы (1.8) называется прямым ходом метода Гаусса. Обратный ход заключается в нахождении неизвестных x1,....,xm из системы

(1.8). Поскольку матрица системы имеет треугольный вид, можно последовательно найти все неизвестные все неизвестные, начиная с xm .

Действительно, xm ym , xm 1

ym 1 cm 1,m xm

и т.д. Общие формулы

обратного хода имеют вид

 

 

 

m

 

 

xi yi cij x j ,i m 1,....1,,xm ym .

(1.10)

j i 1

 

 

Расчетные формулы. При реализации на компьютере прямого хода метода

Гаусса нет

необходимости

действовать

с переменными x1, x2 ,.....,xm .

Достаточно

указать алгоритм, согласно которому исходная матрица A

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

Пусть осуществлены первые

k 1

-

шагов,

т.е. уже

исключены

переменные x1, x2 ,.....,xk 1. Тогда имеем систему

 

 

 

 

x1 c12x2

 

 

 

 

c1k xk

 

 

c1m xm

 

y1,

x2

 

 

 

 

сxk

 

 

c2m xm

 

y2 ,

 

 

 

 

 

 

 

 

 

xk 1

 

ck 1,k xk

 

 

 

ck 1,m xm

 

yk 1(1.11)

 

 

a(k 1) x

k

 

 

a(k 1) x

m

 

f (k 1)

 

 

kk

 

 

 

 

km

 

k

 

 

 

 

 

 

 

 

 

 

 

 

 

a(k 1) x

k

 

 

a(k 1) x

m

 

f (k 1}

 

 

mk

 

 

 

 

mm

 

m

Рассмотрим k е уравнение этой системы

 

 

 

 

 

a(k 1) x

k

a(k 1)

f (k 1)

 

 

 

 

 

 

kk

 

km

k

 

и предположим, что a(k 1)

0.

Поделив обе части этого уравнения на a (k 1)

,

 

 

 

 

 

kk

 

 

 

kk

 

получим

 

 

 

 

 

 

 

 

xk

ck,k 1xk 1

 

 

ck,mxm ym ,

 

(1.12)

 

 

a(k 1)

 

 

 

 

 

 

 

 

где ckj

 

kj

, j k 1, k 2,....,m,

 

 

 

a(k 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

kk

 

 

 

 

 

 

 

 

4

f (k 1)

yk k .

a (kkk 1)

Далее умножим уравнение (12) на aik(k 1) и вычтем полученное соотношение из i го уравнения системы (11), где i k 1,k 2,....,m. В результате последняя группа уравнений системы (11) примет вид

 

 

 

xk

 

ck ,k 1 xk 1

 

 

 

ck ,m xm

yk ,

 

 

 

 

 

 

 

 

a (k )

 

x

k 1

 

 

 

a (k )

x

m

f

(k )

 

 

 

 

 

 

 

 

k 1k 1

 

 

 

 

 

 

 

 

 

 

 

k 1,m

 

 

 

k 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a (k )

x

k 1

 

 

 

a (k ) x

m

f

(k}

 

 

 

 

 

 

 

 

m,k 1

 

 

 

 

 

 

 

 

 

 

 

mm

 

m

 

 

Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений

преобразуются по следующему правилу:

 

 

 

 

 

a

(0) a

kj

, k, j 1,2,....,m,

 

 

 

 

 

 

 

 

 

 

 

 

 

kj

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a(k 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c

 

 

kj

 

, j k 1, k 2,....,m; k 1,2,....,m;

 

 

 

(1.13)

kj

a(k 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

kk

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a(k) a

(k 1) a(k 1)c

kj

,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(1.14)

 

ij

 

 

ij

 

ik

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i, j k 1, k 2,.....,m, k 1,2,....,m 1.

 

 

 

 

 

 

 

 

Вычисление правых частей системы (1.8) осуществляется по формулам

 

 

 

 

 

 

f (0)

 

f

 

, y

 

 

fk(k 1)

, k 1,2,.....,m,

 

 

 

(1.15)

 

 

 

 

 

 

 

k

k

 

 

 

 

 

 

 

 

 

 

k

 

 

 

 

 

 

 

a(k 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

kk

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f (k)

f (k 1)

a(k 1) y

k

,i k 1, k 2,.....,m.

(1.16)

 

 

 

 

 

 

i

 

 

 

 

i

 

 

 

 

ik

 

 

 

 

 

 

 

 

 

 

 

Коэффициенты cij

и правые части yi ,i 1,2,.....,m;

j i 1,i 2,....,m, хранятся

в памяти компьютера и используются при осуществлении обратного хода по формулам (10).

Основным ограничением метода является предположение о том, что все элементы a(kkk 1) , на которые проводится деление, отличны от нуля. Число a(kkk 1) называется ведущим элементом на k м шаге исключения. Даже если

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

a(k 1)

,

а другое число (т.е. на k м шаге исключается не

x

k

,

а другая

kk

 

 

 

 

 

5

переменная x j , j k ). Наиболее последовательно такая стратегия выбора

ведущих элементов осуществляется в методе Гаусса с выбором главного

элемента.

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

1. Вычисление коэффициентов ckj, k 1,2,....,m; j k 1, k 2,....,m; по формулам (13) требует

 

m

 

 

 

 

 

m(m 1)

 

 

 

(m k)

1 2 .... (m 1)

 

делений.

 

 

 

 

 

k 1

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Вычисление всех коэффициентов aij(k ) по формулам (1.14) требует

 

m 1

 

2

 

 

 

 

(m 1)m(2m 1)

 

 

 

(m k)

 

12 22 (m 1)2

умножений.

 

 

 

 

 

 

k 1

 

 

 

 

 

 

 

 

6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таким образом, вычисление ненулевых элементов cij треугольной

 

матрицы C требует

 

 

 

 

 

 

 

 

 

m(m 1)

 

(m 1)m(2m 1)

 

(m2 1)m

 

операций умножения и деления.

 

2

6

3

 

 

 

 

 

 

 

 

 

 

 

При больших числах m это число действий равно приблизительно m3

.

 

 

 

 

 

 

 

 

 

 

3

 

3. Вычисление правых частей yk по формулам (15) требует m делений, а нахождение fi(k) по формулам (16)

m

 

 

 

 

 

 

 

 

 

(m k)

m(m 1)

умножений. Следовательно, вычисление правых ча-

 

 

 

k 1

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

стей преобразованной системы (8) требует

 

m

m(m 1)

 

m(m 1)

действий умножения и деления.

 

 

 

 

2

 

 

 

 

2

 

 

 

 

 

 

В итоге для осуществления прямого хода метода Гаусса необходи-

мо выполнить

 

 

 

 

 

 

 

 

 

(m2 1)m

 

m(m 1)

 

m(m 1)(2m 1)

действий, из которых ос-

3

 

 

 

2

 

6

 

 

 

 

 

 

 

новное число действий ( порядка m33) приходится на вычисление Элементов матрицы C.

4.Для осуществления обратного хода метода Гаусса по формулам (1.10) требуется

6

(a11(0)

m(m 1)(2m 1)

 

m(m 1)

 

m(m2 3m 1)

действий умножения и деле-

6

2

3

 

 

 

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

деления в методе Гаусса близко к m3 3 . Это означает, что вычисление

одного неизвестного тратится в среднем m2 3 . По затратам времени и

необходимой машинной памяти метод Гаусса пригоден для решения систем уравнений (1.2) общего вида с числом неизвестных m порядка 100.

Связь метода Гаусса с методом разложения на множители.

Было показано, что метод Гаусса преобразует исходную систему уравнений

Ax f

(2.1)

в эквивалентную систему

 

Cx y,

(2.2)

где C верхняя треугольная матрица с единицами на главной диагонали. Выясним теперь, как связаны между собой векторы правых частей f , y .

Для этого обратимся к формулам (1.16), из которых последовательно получаем

f

a

 

y ,

f

2

a

y

a(1) y

2

,....

 

 

 

 

1

 

11

1

 

 

21

1

22

 

 

 

 

 

и вообще

f j bj1y1

bj2 y2

.... bjjyj, j 1,2,....,m,

 

(2.3)

где b

ji

числовые коэффициенты, причем b

jj

a( j 1)

. Соотношения

 

 

 

 

 

 

 

 

 

 

 

 

 

jj

 

(2.3) можно записать в матричном виде

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f By,

 

 

 

(2.4)

где B нижняя треугольная матрица с элементами a(jji 1) , j 1,2,....,m,

a11) на главной диагонали. Напомним, что основное допущение при формулировке метода Гаусса состояло в том, что все a(jji 1) 0. По-

этому на диагонали матрицы B стоят ненулевые элементы, и, следовательно, матрица B имеет обратную.

Подставляя в уравнение (2.2) выражение для y в виде y B 1f ,

приходим к уравнению

Cx B 1f ,

или, что то же самое, к уравнению

7

BCx f .

(2.5)

Сопоставляя (2.5) с уравнением (2.1), приходим к выводу, что в результате применения метода Гаусса получено разложение исходной матрицы A в произведение A BC, где B нижняя треугольная матрица с ненулевыми элементами на главной диагонали и C верхняя треугольная матрица с единичной главной диагональю.

Теперь мы имеем право трактовать метод Гаусса следующим образом. Пусть заданы матрица A и вектор f . Сначала проводится разложение A в произведение двух треугольных матриц, A BC. За-

тем последовательно решаются две системы уравнений

By f ,

(2.6)

Cx y

(2.7)

с треугольными матрицами, откуда и находится искомый вектор x. Разложение A BC соответствует прямому ходу метода Гаусса, а решение системы (2.6) (2.7) - обратному ходу. Заметим, что в методе

Гаусса разложение A BC и решение системы (2.6) проводится одновременно.

Далее нижние треугольные матрицы будем обозначать буквой L ( от английского lower – нижний), а верхние треугольные – буквой U (от английского upper – верхний).

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

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

Ранее было показано, что обычный метод Гаусса можно записать в

виде

8

LmLm 1 L1Ax LmLm 1 L1f ,

где Lk , k 1,2,....,m элементарные нижние треугольные матрицы.

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

Определение 2. Элементарной матрицей перестановок Pkl называ-

ется матрица, полученная из единичной матрицы перестановкой k й и l й строк.

Например, элементарными матрицами перестановок третьего порядка являются матрицы

 

0

1

0

 

0 0

1

 

1

0

0

P 1

0

0 , P

0

1

0 , P

0

0

1 .

12

 

 

 

13

 

 

 

23

 

 

 

 

0

0

1

 

1

0

0

 

0

1

0

 

 

 

 

 

 

 

 

 

 

 

 

Отметим следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения.

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

2. Для любой квадратной матрицы A матрица PklA отличается от

A перестановкой k й и l й строк.

3. Для любой квадратной матрицы A матрица APkl отличается от

A перестановкой k го и l го столбцов.

Пример.

Рассмотрим применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента. Рассмотрим следующий пример системы третьего порядка:

x1 x2

x3

f1,

2x1

 

x3

 

f2 , (2.4)

5x2

 

3x3

 

f3.

1

1

1

 

Система имеет вид (2.1), где A 2

0

1 .

(2.5)

 

 

 

 

0

5

3

 

 

 

 

 

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

9

2x1

 

x3

 

f2

,

x1 x2

 

x3

 

f1

, (2.6)

5x2

 

3x3

f3.

Систему (2.6) можно записать в виде

 

P12Ax P12f ,

 

(2.7)

т.е. она получается из системы (2.4) путем умножения на матрицу перестановок

 

0

1

0

P

1

0

0 .

12

 

 

 

 

0

0

1

 

 

 

 

Далее, к системе (2.6) надо применить первый шаг обычного метода исключения Гаусса. Этот шаг, как мы видели, эквивалентен умножению системы (2.7) на элементарную нижнюю треугольную матрицу

 

 

1

 

 

 

 

 

 

 

 

0

0

 

2

 

 

 

 

 

 

 

 

1

 

L

 

 

1

0 .

 

 

1

 

 

2

 

 

 

 

 

 

 

0

 

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

В результате от (2.7) перейдем к системе

 

L1P12Ax L1P12f

 

 

 

 

 

 

(2.8)

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

 

 

 

 

 

 

 

 

x

 

 

 

1

x

 

 

 

f2

,

 

 

1

 

2

3

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

 

 

1

x

 

 

f

 

f2

,

(2.9)

 

 

 

 

 

 

 

2

 

2

 

3

 

1

2

 

 

 

5x2

3x3

 

f3.

 

 

Из последних двух уравнений системы (2.9) надо теперь исключить переменное x2 . Поскольку максимальным элементом первого столбца укоро-

ченной системы

x2

 

1

x3

 

f2

 

 

2

2 ,

(2.10)

5x2

 

3x3

 

f3

 

Является элемент второй строки, делаем в (2.10) перестановку строк и тем самым от системы (2.9) переходим к эквивалентной системе

10