Новые многофункциональные материалы и нанотехнологии

70 эквивалентно исключению из уравнений одного из неизвестных. Из расширенной матрицы исключается главная строка и q-й столбец, содержащий нули. При этом получается матрица размером (n
−

1)
× n , т.е. содержащая (n
−

1) строк и n столбцов.
С новой расширенной матрицей проводится аналогичная операция.
Новый главный элемент выбирается среди всех столбцов, кроме самого правого, который состоит из преобразованных свободных членов. Новая главная строка перемещается на второе место вслед за первой главной.
После (n
−

1)-го шага останется расширенная матрица, состоящая из одной строки и двух столбцов. Эта строка вместе с ранее перемещенными главными строками образуют матрицу, которая после необходимой перенумерации неизвестных приобретет вид, аналогичный тому, который получается в обычном методе Гаусса. Матрица преобразованных коэффициентов при неизвестных приобретает треугольный вид. Значения корней вычисляются обратным ходом, идентичным методу Гаусса, описанным в предыдущем параграфе.
Пример 2. Для иллюстрации метода главных элементов решим систему из трех линейных уравнений
0,34x
1
+ 0,71x
2
+ 0,63x
3
= 2,08,
0,71x
1
− 0,65x
2
− 0,18x
3
= 0,17,
(4.25)
1,17x
1
− 2,35x
2
+ 0,75x
3
= 1,28.
Соответствующая расширенная матрица имеет вид:










−
−
−
28
,
1 75
,
0 35
,
2 17
,
1 17
,
0 18
,
0 65
,
0 71
,
0 08
,
2 63
,
0 71
,
0 34
,
0

(4.26)
Видно, что максимальным по модулю, т.е. главным, является коэффициент a
32
. Следовательно, главная строка данной системы – третья.
Теперь главную строку (3-ю строку матрицы (4.26)) умножим на отношение a
12
/a
32
=
−0,3021 и вычтем ее из 1-й строки матрицы (4.26).
Затем главную строку умножим на отношение a
22
/a
32
= 0,2766 и вычтем ее из 2-й строки матрицы (4.26). Вычисления показывают, что вторые элементы в преобразованных строках занулятся. Отбрасывая этот столбец, получаем новую матрицу размером 3
×2:

71






−
−
1840
,
0 3875
,
0 3864
,
0 4667
,
2 8566
,
0 6935
,
0

(4.27)
В этой матрице требуется выбрать новый ведущий элемент. Это максимальное по модулю число в двух столбцах слева, т.е.
)
1
(
12
a
=
0,8566. Следовательно, новой (второй) главной строкой является верхняя в матрице (4.27).
Умножим новую главную строку на
)
1
(
22
a
/
)
1
(
12
a
=
−0,3875/0,8566 =
=
−0,4524 и вычтем ее из второй строки матрицы (4.27). Получаются два ненулевых значения 0,7001 и 0,9319, которые образуют последнюю строку преобразованной матрицы. Соответствующая преобразованная система уравнений примет вид:
1,17x
1
− 2,35x
2
+ 0,75x
3
= 1,28,
0,6935x
1
+ 0,8566x
3
= 2,4667,

(4.28)
0,7001x
1
= 0,9319.
Теперь не составляет труда последовательно вычислить корни данной системы обратным ходом, описанным в предыдущем параграфе:
x
1
= 1,331;
x
2
= 0,693;
x
3
= 1,802.
Результаты целесообразно округлить до 0,001 (хотя исходные данные были записаны с точностью до 0,01) и затем провести проверку подстановкой полученных корней в исходную систему уравнений.
Расчет методом главных элементов является несколько более трудоемким по сравнению с обычным методом Гаусса, рассмотренным в §4.3, так как требует на каждом шаге прямого хода совершать поиск главного элемента
Это не является серьезным недостатком метода, так как его реализация проводится на современных компьютерах.
Вышеприведенный пример 2 не демонстрирует преимуществ метода главных элементов из-за малого размера решаемой системы. Однако при большом количестве уравнений метод главных элементов позволяет добиться требуемой точности искомых корней без проведения операции уточнения и, следовательно, является более эффективным относительно обычного метода Гаусса.

72
На точность решения системы линейных уравнений существенно влияют, помимо выше рассмотренных факторов, погрешности исходных данных: коэффициентов матрицы А и свободных членов b.
Для наглядности рассмотрим геометрические представление системы линейных двух уравнений с двумя неизвестными
a
11
x
1
+ a
12
x
2
= b
1
,

a
21
x
1
+ a
22
x
2
= b
2


(4.29)
Каждое уравнение последней системы можно изобразить прямой линией в системе координат x
1
,

x
2
(см. рис. 4.1).
а
б
Рис. 4.1. Геометрическая схема решения системы двух линейных уравнений с двумя неизвестными.
Корни системы (4.29) на рис. 4.1 представлены координатами точки пересечения прямых линий.
Изменение коэффициентов при неизвестных и свободных членов системы (4.29) изобразится сдвигом или поворотом линий. Из рис. 4.1.а видно, что малые изменения величин a
ij
и b
i
(i, j = 1, 2) приведут к небольшому сдвигу точки пересечения. Напротив, в случае, изображенном на рис. 4.1.б точка пересечения может переместиться очень сильно даже при малом возмущении чисел a
ij
и b
i
(i, j = 1, 2).
Чувствительность решения системы линейных уравнений (4.1) к изменению коэффициентов при неизвестных и свободных членов характеризуется с помощью числа обусловленности cond(A).
Для определения этой величины обусловленности сначала требуется ввести понятие нормы вектора и матрицы. В линейной алгебре
x
2
x
1
x
2
x
1

73 используются различные варианты определения норм. В настоящем учебном пособии нормой n-мерного вектора полагается сумма абсолютных значений элементов этого вектора. Например, норма вектора свободных членов системы (4.1) запишется в виде:
|| b || =
∑
=
n
i
i
b
1

(4.30)
За норму матрицы примем максимальное значение из норм векторов, образованных столбцами этой матрицы.
Норма матрицы коэффициентов при неизвестных (4.2) выразится так:
|| А || =
n
j
,...
1
max
=
|| a
j
||,
(4.31) где a
j
– вектор, состоящий из элементов j-го столбца матрицы А.
Числом обусловленности матрицы А называется величина
cond
(A) =
|| А || ⋅ || А
−1
||
(4.32)
В теории систем линейных уравнений доказывается, что всегда
cond
(A)
≥ 1.
Обозначим
δδδδb вектор погрешностей свободных членов, δδδδx – вектор погрешностей корней. В теории получено следующее соотношение:
x
x
δ
≤ cond(A)
b
b
δ

(4.33)
Если число обусловленности cond(A) много больше единицы, то матрица A называется плохо обусловленной. При этом сравнительно малые относительные погрешности свободных членов могут привести к большим погрешностям корней.
Обозначив
δδδδA матрицу погрешностей коэффициентов при неизвестных исходной системы линейных уравнений (4.1), можно записать соотношение, которое выражает влияние погрешностей исходных данных на точность корней системы (4.1):

74
x
x
δ
≤
A
A
A
cond
A
cond
δ
−
)
(
1
)
(








δ
+
δ
b
b
A
A

(4.34)
Заметим, что для вычисления числа обусловленности необходимо иметь явный вид обратной матрицы А
−1
. Существуют специальные способы приближенной оценки числа cond(A), которые не требуют использования А
−1
. Эти приемы описаны в подробных курсах численных методов, например в [5].
Для решения плохо обусловленных систем линейных уравнений применяются особые методы, изложенные в специальных курсах и учебных пособиях.

§ 4.5. Итерационные методы
Как было указано в начале данной главы, итерационные методы представляют собой методы последовательных приближений. Каждый итерационный метод использует определенное рекуррентное соотношение. По заданному нулевому приближению сначала вычисляется первое, затем по первому второе и т.д. Процесс итераций должен быть построен таким образом, чтобы с ростом числа шагов получаемые приближенные значения корней в принципе сходились к точному решению.
Следует иметь в виду, что исходные данные – коэффициенты при неизвестных и свободные члены в практических задачах часто обладают неустранимой погрешностью
Кроме того, в процессе расчетов на компьютере неизбежны погрешности округления из-за конечной разрядности регистров процессора. В этой связи важным достоинством итерационных методов является то, что можно заранее задать точность искомого решения. Главный же их недостаток – то, что для каждого рекуррентного процесса необходимо исследование условий его сходимости.
Вновь рассмотрим систему линейных уравнений
(4.1).
Предположим, что все диагональные коэффициенты матрицы А не равны нулю a
ii

≠ 0 (i= 1, 2, ..., n). Разрешим первое уравнение относительно неизвестного x
1
, второе уравнение – относительно x
2
и т.д.

75
В результате получим систему линейных уравнений, эквивалентную данной (4.1).


x
1
= d
1
+ c
12
x
2
+ c
13
x
3
+ ... + c
1n
x
n
,


x
2
= d
2
+ c
21
x
1
+ c
23
x
3
+ ... + c
2n
x
n
,
...................................………………
(4.35)


x
n
= d
n
+ c
n
1
x
1
+ c
n
2
x
2
+ ... + c
nn
−1
x
n
−1

В последней системе введены новые обозначения:
c
ij
=
−
ii
ij
a
a
( при i
≠ j ), c
ij
=
0 ( при i = j ), где i, j = 1, 2, ..., n; (4.36)
d
i
=
ii
i
a
b
, где i = 1, 2, ..., n.
(4.37)
Определим матрицу коэффициентов C
C =












nn
n
n
n
n
c
c
c
c
c
c
c
c
c
...
...
...
2 1
2 22 21 1
12 11

(4.38) и вектор-столбец D
D =












n
d
d
d
2 1


(4.39)
Перепишем систему (4.35) в матричной форме
x = D + C x.

(4.40)
Решить систему (4.40) можно методом простой итерации
(методом Якоби). Для этого примем вектор D за начальное

76 приближение вектора x
(0)
искомых корней. Тогда, подставляя в правую часть уравнений (4.40) вектор x
(0)
, получим в левой части вектор- столбец первого приближения корней:
x
(1)
= D + C x
(0)

Последовательно повторяя эту операцию, вычисляем (k+1)-е приближения с помощью следующего рекуррентного матричного соотношения:
x
(k+1)
= D + C x
(
k)

(4.41)
Распишем формулы последовательных приближений в развернутом виде:
)
0
(
i
x
= d
i
,
)
1
(
+
k
i
x
= d
i
+
∑
=
n
j
k
j
ij
x
c
1
)
(
,
(4.42) где i = 1, 2, ..., n ; k = 0, 1, 2, ... .
Метод простой итерации основан на том, что последовательность векторов-столбцов x
(
k)
(k = 0, 1, 2, ...) сходится к точному решению исходной системы (4.1) при определенных условиях, которые будут сформулированы ниже.
Достаточное условие сходимости итерационного процесса (4.41) может быть выражено в виде:
|| C || < 1.

(4.43)
В курсе линейной алгебры доказывается, что при условии (4.43) итерационный процесс (4.41) сходится к единственному решению исходной системы (4.1) при любом начальном приближении x
(0)
Следовательно, в принципе, не обязательно за исходное приближение
x
(0)
брать столбец свободных членов (4.39).
Однако практика показывает, что из-за погрешностей исходных данных и округления при выполнении операций процессором сходимость процесса к точному решению может быть нарушена.
Для использования на практике метода простой итерации, прежде всего, необходимо иметь все диагональные коэффициенты матрицы А не равными нулю a
ii

≠ 0 (i = 1, 2, ..., n). Для невырожденной матрицы А

77 это может быть выполнено перестановкой уравнений исходной системы
(4.1).
Из определения нормы матрицы следует, что условие (4.43) у матрицы C выполнится, если ее элементы малы по абсолютной величине. Это достигается, если диагональные элементы a
ii

достаточно велики по модулю относительно остальных элементов a
ij

(i
≠ j) матрицы
А
, что следует из определения (4.36). Можно доказать, что условие сходимости (4.43) будет выполнено, если справедливы n неравенств:
| a
ii
| >
∑
≠
=
n
i
j
j
ij
a
1
, i = 1, 2, ..., n .
(4.44)
Иначе говоря, метод простой итерации даст единственное решение системы линейных уравнений (4.1), если в каждом уравнении модуль диагонального коэффициента превышает сумму модулей остальных коэффициентов в соответствующей строке исходной системы, т.е. сумму модулей остальных коэффициентов при неизвестных в этом уравнении.
Выполнить требование (4.44) можно, применяя линейные преобразования уравнений исходной системы (4.1).
Пример 3. Дана следующая система из 4-х линейных уравнений:
2x
1
+ 3x
2

− 4

x
3
+

x
4
= 3,

(а)
x
1
− 2x
2

− 5

x
3
+

x
4
= 2,

(б)
5x
1
− 3x
2
+

x
3
− 4

x
4
= 1,

(в)
10x
1
+ 2x
2

−

x
3
+
2

x
4
=
− 4.
(г)
Если взять уравнения (б) и (г) в качестве 3-го и 1-го уравнений новой системы, для них будет выполняться условие (4.44). Разность уравнений
(а) и (б) дает 2-е уравнение. Наконец линейная комбинация уравнений
2((а) – (б) + (в)) – (г) даст 4-е уравнение преобразованной системы. В результате получается система
10x
1
+ 2x
2

−

x
3
+
2

x
4
=
− 4,
x
1
+ 5x
2
+

x
3
+ 0 = 1,
x
1
− 2x
2

− 5

x
3
+

x
4
= 2,
3x
1
+ 0x
2
+ 0

x
3
− 9

x
4
= 10.

78
Для всех уравнений последней системы выполнены условия (4.44).
Можно эту систему преобразовывать к виду (4.35) и решать методом простой итерации (4.41).
В качестве иллюстрации скорости сходимости итерационного процесса (4.41) еще один пример.
Пример 4. Пусть система состоит из трех следующих линейных уравнений.
4 x
1
+ 0,24 x
2

− 0,08

x
3
= 8,
0,09 x
1
+ 3 x
2
− 0,15

x
3
= 9,
(4.45)
0,04 x
1
− 0,08

x
2

+ 4

x
3
= 20.
Видно, что для данной системы условие (4.44) выполнено и, следовательно, можно для решения применить метод простой итерации.
Сначала преобразуем систему (4.45) к стандартному виду (4.35):
x
1
= 2
− 0,06 x
2
+ 0,02

x
3
,
x
2
= 3
− 0,03 x
1
+ 0,05

x
3
,

(4.46)
x
3
= 5
− 0,01 x
1
+ 0,02

x
2

В качестве начального приближения возьмем вектор свободных членов системы уравнений (4.46):
)
0
(
1
x
= 2;
)
0
(
2
x
= 3;
)
0
(
3
x
= 5.
Подставляя эти числа в правые части уравнений (4.46), получим в левых частях первое приближение решения. Результаты нескольких итераций сведены в следующую таблицу 4.1.
Значения, приведенные в таблице 4.1, показывают, что решение системы линейных уравнений (4.45) с точностью до пяти знаков после запятой достигается уже после 4-й итерации. Последующие итерации не изменяют значения указанных десятичных разрядов. Если требуется вычислить корни с точностью до 0,001, то достаточно провести лишь 3 итерации. Полученное решение будет достаточно точным в рамках заданной погрешности.

79
Таблица 4.1
Номер итерации
x
1
x
2
x
3 0
2 3
5 1
1,92 3,19 5,04 2
1,9094 3,1944 5,0446 3
1,909228 3,194948 5,044794 4
1,909199 3,194963 5,044807 5
1,909198 3,194964 5,044807
Пример 4 демонстрирует, что после преобразования исходной системы к виду (4.35) остается проводить операции умножения и сложения, вычисляя правые части этой системы. Хранить в оперативной памяти компьютера приходится только неизменяемую матрицу C.
Если изначально задана требуемая абсолютная погрешность
ε вычисления корней, то на каждом шаге итераций проверяются условия
)
1
(
)
(
−
−
k
i
k
i
x
x
<
ε, i = 1, …, n.
(4.47) где k
− номер итерации, i − номер уравнения. Если хотя бы одно из условий (4.47) не выполняется, то проводится следующая итерация. В результате все корни решаемой системы уравнений будут вычислены с абсолютной погрешностью
≤ ε.
При решении прикладных задач более часто используется другой итерационный метод, называемый методом Зейделя.
Метод Зейделя базируется на вышеописанной схеме и использует рекуррентное соотношение (4.41). Особенностью этого метода является то, что при вычислении k-го приближения корня x
i
системы линейных уравнений (4.1) учитываются уже вычисленные ранее k-е приближения корней x
1
, x
2
, … , x
i
−
1
Пусть исходная система (4.1) преобразована в приведенную систему
(4.35). Выбирается вектор начального приближения искомых корней.
Итерации проводятся по схеме (4.41) с одной оговоркой. Если уже вычислено k-е приближение корней x
(
k)
, то следующее (k+1)-е приближение x
(
k+1)
строится по следующим формулам:

80
)
1
(
1
+
k
x
= d
1
+
∑
=
n
j
k
j
j
x
c
1
)
(
1
,
)
1
(
2
+
k
x
= d
2
+ c
21
)
1
(
1
+
k
x
+
∑
=
n
j
k
j
j
x
c
2
)
(
2
,
…………………………………………………… (4.48)
)
1
(
+
k
i
x
= d
i
+
∑
−
=
+
1 1
)
1
(
i
j
k
j
ij
x
c
+
∑
=
n
i
j
k
j
ij
x
c
)
(
,
……………………………………………………
)
1
(
+
k
n
x
= d
n
+
∑
−
=
+
1 1
)
1
(
n
j
k
j
ij
x
c
+ c
nn
)
(k
n
x

Как и в предыдущем методе, после нескольких итераций по данной схеме корни

Скачать 0.96 Mb.

Поделитесь с Вашими друзьями: