ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 203
Скачиваний: 2
МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Физический факультет
Кафедра физики твердого тела
ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ ДЛЯ ФИЗИКОВ
ЧАСТЬ 3
Численные методы линейной алгебры,
методы решения нелинейных уравнений
Для студентов 2 курса специальности 010400 - Физика и
3 курса специальности 200200 - Микроэлектроника и п/п приборы
Составители:
проф. С.И.Курганский
доц. О.И.Дубровский
доц. Л.И.Куркина
Воронеж – 1998
2
5. ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ
К численным методам линейной алгебры относятся численные методы
решения систем линейных алгебраических уравнений, обращения матриц,
вычисления определителей, нахождения собственных значений и собственных
векторов матриц. Для решения всех этих задач применяются различные
модификации одних и тех же методов. Поэтому здесь мы рассматриваем
главным образом лишь первую из перечисленных выше задач.
Методы решения систем линейных алгебраических уравнений разбивают
на две группы. К первой группе принадлежат так называемые точные или
прямые методы – алгоритмы, позволяющие получить точное в математическом
смысле решение системы за конечное число арифметических действий. Сюда
относится известное правило Крамера нахождения решения с помощью
определителей, метод прогонки, рассмотренный выше, а также методы Гаусса и
квадратного корня, которые будут рассмотрены ниже. Сразу же отметим, что
правило Крамера в практических расчетах невыгодно, так как требует слишком
большого количества операций.
Вторую группу методов составляют методы последовательных
приближений, в которых абсолютно точное решение системы за конечное число
действий в принципе получить невозможно. Однако его можно найти с любой
наперед заданной точностью. Эти методы характеризуются тем, что с самого
начала задаются какими-то приближенными значениями неизвестных. Из этих
приближенных значений тем или иным способом получают новые
“улучшенные” приближенные значения. С ними поступают точно так же и т.д.
К таким методам принадлежат рассматриваемые ниже метод простой итерации
и метод Зейделя.
5.1. Метод Гаусса
Рассмотрим задачу решения системы линейных алгебраических
уравнений
Ax b
=
.
Здесь
A
- заданная квадратная матрица размера
n n
´
A
=
æ
è
ç
ç
ç
ç
ö
ø
÷
÷
÷
÷
a
a
a
a
a
a
a
a
a
n
n
n
n
nn
11
12
1
21
22
2
1
2
K
K
K
.
.
.
.
,
b
и
x
соответственно заданный вектор свободных членов и вектор неизвестных
3
b
=
æ
è
ç
ç
ç
ç
ö
ø
÷
÷
÷
÷
b
b
b
n
1
2
K
,
x
=
æ
è
ç
ç
ç
ç
ö
ø
÷
÷
÷
÷
x
x
x
n
1
2
K
.
В явном виде система может быть записана также как
a x
b
ij j
i
j
n
=
=
å
1
(
)
i
n
=
1 2
, ,
,
K
,
или
a x
a x
a x
b
a x
a x
a x
b
a x
a x
a x
b
n n
n n
n
n
nn n
n
11 1
12 2
1
1
21 1
22 2
2
2
1 1
2 2
+
+ +
=
+
+ +
=
+
+ +
=
ì
í
ï
ï
î
ï
ï
K
K
K
. . . . . . . . . . . . . . . . . .
.
Метод Гаусса основан на приведении матрицы системы к треугольному
виду. Это достигается последовательным исключением неизвестных из
уравнений системы. Метод Гаусса включает в себя два этапа: прямой и
обратный ход.
1) Прямой ход. Предположим, что коэффициент
a
11
, называемый
ведущим элементом первой строки, не равен нулю. Разделим первое уравнение
на этот коэффициент. В результате оно примет вид
x
a x
b
j j
j
n
1
1
1
1
1
2
+
=
=
å
,
где
a
a
a
j
j
1
1
1
11
=
/
,
b
b
a
1
1
1
11
=
/
. Затем с помощью полученного уравнения во
всех остальных уравнениях системы исключим слагаемые, содержащие
x
1
. Для
этого умножим это уравнение на
a
21
и вычтем из второго уравнения, умножим
на
a
31
и вычтем из третьего уравнения и т.д. В результате уравнения системы,
начиная со второго, примут вид
a x
a x
a x
b
a x
a x
a x
b
n n
n
n
nn n
n
22
1
2
23
1
3
2
1
2
1
2
1
2
3
1
3
1
1
+
+ +
=
+
+ +
=
ì
í
ï
î
ï
K
K
. . . . . . . . . . . . . . . . . .
,
где
a
a
a a
ij
ij
i
j
1
1 1
1
=
-
,
b
b
a b
i
i
i
1
1 1
1
=
-
(
)
i j
n
,
, ,
,
=
2 3 K
. Подобным образом
преобразуем эти уравнения, т.е. разделим второе уравнение на
a
22
1
и с
помощью полученного уравнения во всех остальных уравнениях, начиная с
третьего, исключим слагаемые, содержащие
x
2
. Этот процесс будем
продолжать до тех пор, пока в левой части последнего,
n
-го, уравнения не
останется лишь один член с неизвестным
x
n
. В результате исходная система
будет приведена к эквивалентной форме с верхней треугольной матрицей:
4
x
a x
a x
a x
b
x
a x
a x
b
x
a
x
b
x
b
n n
n n
n
n
n
n
n
n
n
n
n
n
1
12
1
2
13
1
3
1
1
1
1
2
23
2
3
2
2
2
2
1
1
1
1
1
+
+
+ +
=
+
+ +
=
+
=
=
ì
í
ï
ï
ï
î
ï
ï
ï
-
-
-
-
-
K
K
. . . . . . . . . . . . . . . . . . . . .
,
.
2) Обратный ход . Он состоит в последовательном вычислении искомых
неизвестных. Сначала из последнего уравнения определяем
x
b
n
n
n
=
. Используя
это значение, из предыдущего уравнения находим
x
n
-
1
. И т.д. Последним
найдем
x
1
из первого уравнения. Таким образом, для отыскания неизвестных
имеем рекуррентную формулу
x
b
a x
i
i
i
ij
i
j
j i
n
=
-
= +
å
1
(
)
i n n
=
,
,
,
-1 1
K
.
Вычисление определителей
. В прямом ходе процедуры Гаусса матрица
системы
A
приводится к треугольному виду с помощью операций двух типов:
1) Деление всех элементов строки на ведущий элемент этой строки. При этом,
как известно из линейной алгебры, определитель матрицы также делится на
этот ведущий элемент.
2) Добавление к элементам строки элементов другой строки, умноженных на
константу. Определитель матрицы при такой операции не изменяется.
Таким образом, если обозначить через
A
t
полученную в результате этих
преобразований треугольную матрицу, то
det
det
A
A
t
=
-
a a a
a
nn
n
11 22
1
33
2
1
K
.
С другой стороны, определитель треугольной матрицы, на главной диагонали
которой находятся только единицы, равен единице. Следовательно,
определитель исходной матрицы равен произведению ведущих элементов
строк:
det
A
=
-
a a a
a
nn
n
11 22
1
33
2
1
K
.
Таким образом, при решении системы линейных алгебраических уравнений
методом Гаусса “попутно” можно вычислить определитель матрицы этой
системы. Если же требуется только найти определитель заданной матрицы, то
вычисления проводятся по схеме, соответствующей прямому ходу метода
Гаусса. Отличие лишь в том, что отсутствуют действия над столбцом
свободных членов.
Рассмотренный выше простейший вариант метода Гаусса называется
схемой единственного деления. Он обладает рядом недостатков. Если ведущий
элемент какой-либо строки, например
a
11
, окажется равным нулю, то эта схема
5
формально непригодна. Возможен также более неприятный случай, когда
ведущий элемент не нулевой, но очень мал по модулю по сравнению с другими
элементами строки. Тогда при делении на это малое число получаются очень
большие числа. Это приводит к значительному росту погрешности округлений.
Как следствие, точность результата становится очень плохой, даже
катастрофически плохой.
Изложим теперь схему метода Гаусса, свободную от этих недостатков.
Она называется схемой с выбором главного элемента и в алгоритмическом
плане незначительно отличается от предыдущей.
Пусть, как и прежде, дана система линейных алгебраических уравнений
Ax b
=
.
Сначала добиваемся выполнения условий
a
a
ij
11
³
(
)
i j
n
,
, ,
,
=
1 2 K
.
Для этого отыскиваем максимальный по модулю элемент матрицы
A
и при
необходимости переставляем два уравнения и два столбца исходной системы.
Затем производим соответствующую перенумерацию коэффициентов и
неизвестных. Найденный максимальный по модулю коэффициент
a
11
называется первым главным элементом. После этого выполняем как обычно
первый шаг процедуры Гаусса, т.е. во всех уравнениях системы, начиная со
второго, исключаем слагаемые, содержащие
x
1
. В полученной “урезанной”
системе находим второй главный элемент, т.е. добиваемся
a
a
ij
22
1
1
³
(
)
i j
n
,
, ,
,
=
2 3 K
,
и повторяем процедуру.
В этом случае также можно вычислить определитель исходной матрицы
A
. Из линейной алгебры известно, что при перестановке двух строк или
столбцов матрицы определитель меняет знак. Поэтому в полученную формулу
для определителя необходимо добавить множитель
( )
-
1
n
, где
n
- полное число
перестановок строк и столбцов на всех этапах приведения матрицы к
треугольному виду. В результате формула для определителя приобретает вид
( )
det
A
= -
-
1
11 22
1
33
2
1
n
a a a
a
nn
n
K
.
Может случиться, что система вырождена, т.е. ее определитель det
A
=
0.
Это приведет к тому, что на некотором шаге главный элемент окажется равным
нулю (т.е. равны нулю и все элементы ниже него). Поэтому на каждом шаге
нужно контролировать обращение в нуль главного элемента. Решение
вырожденных систем рассматривалось в курсе линейной алгебры и здесь мы
рассматривать этот вопрос не будем.
5.2. Метод квадратного корня