close

Вход

Забыли?

вход по аккаунту

?

4 Задачи линейной алгебры

код для вставкиСкачать
4. ЗАДАЧИ ЛИНЕЙНОЙ АЛГЕБРЫ
4.1. Общая характеристика методов решения
Основной задачей линейной алгебры является решение систем линейных алгебраических уравнений (СЛАУ). Кроме этого здесь решаются задачи обращения матриц, вычисления определителей, нахождения собственных значений и собственных векторов матриц. Эти задачи важны не только сами по себе. К ним сводятся многие другие проблемы численного анализа: интерполяция функций, решение дифференциальных уравнений и их систем и многие другие.
Методы решения СЛАУ можно разбить на две основные группы. К первой относятся так называемые точные или прямые методы - это алгоритмы, позволяющие получить решение за конечное, заранее известное число арифметических действий. Сюда входят: метод, основанный на правиле Крамера, метод исключений Гаусса и метод прогонки. Вторую группу составляют приближенные (или итерационные) методы, основанные на многократном повторении одной и той же группы действий, каждая из которых дает все более точный результат. Из этой группы методов ниже будут рассмотрены метод простых итераций и метод Зейделя.
4.2. Решение систем линейных алгебраических уравнений методом Гаусса
Общий вид системы линейных алгебраических уравнений:
a11 x1+a12 x2+...+a1n xn=a1,n+1a21 x1+a22 x2+...+a2n xn=a2,n+1(4.1). . . . . . . . . ...... . . . .. . . . an1 x1+an2 x2+...+ann xn=an,n+1
где aij - заданные элементы расширенной матрицы СЛАУ ( i=1,...,n, j=1,...,n+1 );
xi - неизвестные (искомые) величины;
n - порядок системы.
Системе (4.1) соответствует расширенная матрица размера n на n+1:
a11a12...a1na1,n+1a21a22...a2na2,n+1.....an1an2...annan,n+1в которой первые n столбцов состоят из коэффициентов при неизвестных, а последний столбец образован из свободных членов системы (4.1).
Решить СЛАУ - значит найти такую комбинацию значений xi , при которой каждое уравнение (4.1) превращается в тождество.
По правилу Крамера каждое значение xi решения системы (4.1) вычисляется по формуле xi= D i /D, где D - определитель матрицы коэффициентов при неизвестных, D i - определитель матрицы, полученной из матрицы коэффициентов при неизвестных заменой i-го столбца на столбец свободных членов. Этой формулой можно с успехом пользоваться для систем 2-го, 3-го порядков, но для более высоких порядков вычисление определителей становится довольно сложной проблемой, и поэтому метод, основанный на правиле Крамера, практически не используется.
Значительно более простым и эффективным по быстродействию является метод Гаусса. Алгоритм этого метода состоит из двух этапов, называемых, соответственно, прямым и обратным ходом. Целью прямого хода является последовательное исключение неизвестных из уравнений системы; и только в обратном ходе производится непосредственное определение значений неизвестных.
Вначале рассмотрим выполнение алгоритма метода Гаусса на примере системы 3-го порядка
a11 x1+a12 x2+a13 x3=a14a21 x1+a22 x2+a23 x3=a24(4.1' )a31 x1+a32 x2+a33 x3=a34. Из первого уравнения (4.1') выразим x1 :
x1 = (a14 - a12 x2 - a13 x3) / a11 ,(4.2)
а само это уравнение запишем в виде :
x1 + x2 + x3 = ,
(4.3)где = a1j / a11 , j = 2,3,4.
(4.4)Подставим (4.2) с учетом (4.4) во второе и третье уравнения (4.1') и получим систему :
x1
+ x2
+ x3
=x2
+x3
=
(4.5) x2
+ x3
=
,где = aij - ai1 . , i=2,3; j = 2,3,4 ,
т.е. на данном этапе прямого хода из второго и третьего уравнений системы исключено неизвестное x1.
Из второго уравнения преобразованной системы (4.5) выразим x2 :
x2 = ( - x3) / ,
(4.6)
а само это уравнение запишем в виде :
x2 + x3 = ,
(4.7)где = / , j = 3,4.
(4.8)Подставим (4.6) с учетом (4.8) в третье уравнение (4.5) и получим систему :
x1
+ x2
+ x3
=
x2
+ x3
=
(4.9) x3
=
,где = - . , j = 3,4 ,
т.е. на данном этапе прямого хода из третьего уравнения системы исключено x2.
Из третьего уравнения (4.9) выразим x3 : x3 = / ,
или x3 = .
Теперь система приобретает вид:
x1
+ x2
+ x3
=
x2
+ x3
=
(4.10)
x3
=
. На этом заканчивается прямой ход метода Гаусса. Матрица коэффициентов полученной системы имеет вид:
1
0
1
(4.11)
0
0
1
.Это треугольная матрица. На ее главной диагонали расположены единицы, а элементы под главной диагональю равны нулю.
Обратный ход метода очевиден. Третье уравнение системы (4.10) уже явно определяет значение x3 .
(4.12)Подставляя это значение во второе уравнение (4.10), получаем:
.
(4.13)Подставляя найденные значения x2,x3 в первое уравнение (4.10), получаем значение x1:
.
(4.14)Соотношения (4.12), (4.13), (4.14) и являются решением системы ( 4.1' ).
Блок-схема решения СЛАУ методом Гаусса
Блок-схема фрагмента "Выбор главного элемента"
Блок-схема фрагмента "Обратный ход"
Рис.4.1. Схемы алгоритма метода Гаусса
Теперь обобщим рассмотренный алгоритм на произвольную систему n-го порядка. На каждом k-ом шаге (k=1,2,3,...,n) прямого хода выполняются операции:
,
j = 1,2,...,n+1,
(4.15),
i = k+1,...,n; j = 1,2,...,n+1.
(4.16) На последнем шаге, т.е. при k=n, выполняются только операции (4.15), так как для выполнения (4.16) уже исчерпаны все значения i.
При выполнении операций (4.15) производится деление на диагональные элементы akk. Поэтому может возникнуть критическая ситуация, если этот элемент оказывается равным нулю. Избежать этой ситуации можно путем перестановки уравнений преобразуемой системы, начиная с k-го и по n-е таким образом, чтобы на месте akk оказался ненулевой элемент. Более того, доказано, что для достижения максимальной точности решения системы надо перестановку уравнений осуществлять таким образом, чтобы на месте akk оказывался максимальный по модулю элемент из тех, что находятся в k-м столбце матрицы системы начиная с диагонального и ниже. Эта процедура называется выбором главного элемента. Если же в результате этой процедуры на главной диагонали окажется все-таки нулевой элемент, то это означает, что главный определитель D матрицы системы равен нулю. По правилу Крамера это значит, что система вырожденная, т.е. либо не имеет решений, либо имеет их бесконечно много.
На рис.4.1 представлена укрупненная схема алгоритма, реализующего метод Гаусса. В ней достаточно подробно отражен прямой ход метода и схемы фрагментов "выбор главного элемента" и "обратный ход". 4.3. Вычисление определителей При выполнении прямого хода метода Гаусса при решении СЛАУ вычисление по формулам (4.15), (4.16) производится для j=1, ..., n+1, т.е. преобразованию подлежат как коэффициенты при неизвестных x1,..., xn, так и свободные члены системы.
Аналогичный алгоритм, но для j=1,...,n, может быть применен для вычисления определителя любой квадратной матрицы порядка n. Подставляя (4.15) в (4.16), получим:
,
(4.17)где k = 1, ... , n-1 - номер шага преобразования матрицы; i = k+1,...,n ; j = 1,2,...,n.
Так как i изменяется от k+1, то это означает, что первая строка матрицы не изменяется.
Преобразование исходной матрицы по формуле (4.17) приводит к треугольной матрице, у которой элементы, расположенные ниже главной диагонали, равны нулю:
. . .0
. . .
0
0
. . .. . .. . .. . .. . .. . .. . .
0
0
0. . .
0
0
0. . .
0 Преобразование (4.17) является линейным и поэтому не приводит к изменению определителя матрицы; но так как преобразованная матрица - треугольная, то ее определитель равен произведению элементов главной диагонали. В отличие от решения СЛАУ здесь не требуется выполнение обратного хода.
Для получения максимальной точности результата надо стремиться, как и при решении СЛАУ, к тому, чтобы на каждом k-ом шаге преобразования на месте элемента аkk находился максимальный по модулю элемент из тех, что стоят в k-ом столбце ниже k-ой строки. Это достигается процедурой выбора главного элемента, поэтому при вычислении определителя надо учитывать, что перестановка любых двух строк матрицы приводит к изменению знака определителя на противоположный.
4.4. Обращение матриц Матрица X является обратной по отношению к заданной квадратной матрице A, если их произведение дает единичную матрицу E :
A . X = E .(4.18)В единичной матрице элементы главной диагонали равны 1, а все остальные элементы равны 0.
Как известно, произведение двух квадратных матриц A и X порядка n дает квадратную матрицу C того же порядка, элементы которой вычисляются по формуле:
(4.19)Алгоритм обращения матриц, т.е. вычисления элементов матрицы X, удовлетворяющих матричному уравнению (4.18), рассмотрим на примере матриц третьего порядка:
;; Уравнение (4.18) с учетом формулы (4.19) для этих матриц имеет вид:
a11 x11+a12 x21+a13 x31a11 x12+a12 x22+a13 x32a11 x13+a12 x23+a13 x331 0 0a21 x11+a22 x21+a23 x31a21 x12+a22 x22+a23 x32a21 x13+a22 x23+a23 x33=0 1 0a31 x11+a32 x21+a33 x31a31 x12+a32 x22+a33 x32a31 x13+a32 x23+a33 x330 0 1
Фактически здесь записаны три СЛАУ третьего порядка: a11 x11 + a12 x21 + a13 x31=11)a21 x11 + a22 x21 + a23 x31=0a31 x11 + a32 x21 + a33 x31=0
a11 x12 + a12 x22 + a13 x32=02)a21 x12 + a22 x22 + a23 x32=1a31 x12 + a32 x22 + a33 x32=0
a11 x13 + a12 x23 + a13 x33=03)a21 x13 + a22 x23 + a23 x33=0a31 x13 + a32 x23 + a33 x33=1 Их особенностью является то, что все три системы имеют одну и ту же матрицу коэффициентов при неизвестных, а именно матрицу А.
Итак, чтобы найти матрицу X, обратную к заданной матрице А порядка n, надо решить n систем линейных уравнений, матрицей коэффициентов которых является исходная матрица А, а вектор-столбцами свободных членов являются столбцы единичной матрицы E. При использовании метода Гаусса решения этих n систем прямой ход можно осуществить одновременно для всех систем. Расширенная матрица при этом будет иметь порядок n х 2n; ее левая половина есть матрица А, правая - матрица E.
4.5. Итерационные методы решения СЛАУ
Для применения этого метода приведем систему (4.1) к виду:
x1 = (a1,n+1- a 11 x 1- a 12 x 2-...- a 1n x n) / a 11+ x 1x2 = (a2,n+1- a 21 x 1- a 22 x 2-...- a 2n x n) / a 22+ x 2(4.20). . . . . . . . . . . . . . . . . . . . . . . .xn = (an,n+1- a n1 x 1- a n2 x 2-...- a nn x n) / a nn+ x nЗададимся некоторым начальным приближением , , ... , и подставим его значения в правые части (4.20), и получим новое приближение , , ... , , которое подставим снова в систему (4.20) и т.д.
Таким образом организуется итерационный процесс, называемый методом простых итераций для систем алгебраических уравнений и являющийся обобщением метода простых итераций для алгебраических уравнений, рассмотренного в разделе 3:
(4.21). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ,где =(ai,n+1- a i1 x 1- a i2 x 2-...- a in x n) / a ii+ x i , i=1,2,...,n ;
m - номер итерации.
Процесс (4.21) можно представить в несколько ином виде:
(4.22). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ,где=(ai,n+1- a i1 x 1- a i2 x 2-...- a in x n) / a ii , i=1,2,...,n ;
Значения или короче характеризуют разницу между m-м и (m+1)-м приближениями и образуют совокупность так называемых невязок (m+1)-го приближения.
Процесс (4.21) или (4.22) является бесконечным вычислительным процессом, каждая новая итерация которого дает все лучшее приближение к точному решению системы. В качестве критерия окончания обычно берется выполнение условия: "Все невязки по абсолютной величине меньше наперед заданного числа ", характеризующего точность решения системы, т.е.
< , i =1,2,...,n
(4.23) Процесс (4.22) можно видоизменить, если использовать приближения к решениям, найденные в ходе текущей итерации, при проведении этой же итерации:
=
=
=
(4.24). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . = Этот процесс называется методом Зейделя. Он приводит, как правило, к ускорению сходимости по сравнению с процессом (4.22). Еще одним важным преимуществом метода Зейделя является меньший расход памяти ЭВМ, т.к. при его использовании необходим один массив для хранения вектора-столбца приближений, а в методе простых итераций - два: по массиву на предыдущее и текущее приближения.
Для сходимости итерационных методов, т.е. для выполнения условия (4.23) при некотором конечном m, необходимо, чтобы значения диагональных элементов матрицы СЛАУ были преобладающими по абсолютной величине по сравнению с другими элементами. Обеспечить это требование можно путем перестановки строк и (или) столбцов матрицы системы.
8
4. Задачи линейной алгебры
8
21
Документ
Категория
Рефераты
Просмотров
209
Размер файла
1 767 Кб
Теги
линейной, алгебра, задачи
1/--страниц
Пожаловаться на содержимое документа