book chis_met
.pdfдругу треугольных матриц
|
|
|
A = S′S, |
s2n . |
|
S = |
0 |
s22 ·· ·· ·· |
|||
|
s11 |
s12 |
s1n |
||
|
· |
0· · |
· |
0· · ... |
snn |
|
|
|
|
... |
|
|
|
|
|
|
|
Формулы для определения sij :
s11 = √a11 , s1j
v
ui−1
uX
sii = taii − s2ki (i > 1),
k=1
sij = 0
=a1j , (j > 1),
s11
sij = |
i−1 |
(j > i), |
P |
||
|
aij − k=1 skiskj |
|
|
sii |
|
(i > j).
После того как матрица S найдена, решают систему
S′y = b,
а затем находят неизвестные x1, x2, ..., xn из системы
Sx = y
Так как обе системы имеют треугольную форму,то они легко решаются.
y1 = |
|
|
|
|
, yi = |
|
i−1 |
, (i > 1). |
||
|
|
|
|
|
P |
|||||
|
|
|
|
b1 |
|
|
bi − k=1 skiyk |
|
|
|
|
|
|
s11 |
|
|
sii |
|
|
||
xn = |
|
|
|
, xi = |
|
n |
|
, (i < n). |
||
|
|
n |
|
P |
|
|||||
|
|
y |
|
|
|
yi − k=i+1 sikxk |
||||
|
snn |
|
|
|
sii |
|
|
При практическом применении метода последовательно прямым ходом вычисляются коэффициенты sij и yi (i = 1, 2, ..., n), а затем обратным ходом находятся неизвестные xi
(i = n, n − 1, ..., 1).
Пример. Методом квадратного корня решить систему уравнений
x1 |
+3x2 −2x3 |
|
−2x5 |
= 0, 5 |
|
3x1 |
+4x2 |
−5x3 |
+x4 |
−3x5 |
= 5, 4 |
−2x1 |
−5x2 |
+3x3 −2x4 |
+2x5 |
= 5, 0 |
|
−2x1 |
x2 |
−2x3 |
+5x4 |
+3x5 |
= 7, 5 |
−3x2 |
+2x3 |
+3x4 |
+4x5 |
= 3, 3 |
11
Расчетный бланк решения.
ai1 |
ai2 |
ai3 |
ai4 |
ai5 |
bi |
1 |
3 |
-2 |
0 |
-2 |
0,5 |
3 |
4 |
-5 |
1 |
-3 |
5,4 |
-2 |
-5 |
3 |
-2 |
2 |
5,0 |
0 |
1 |
-2 |
5 |
3 |
7,5 |
-2 |
-3 |
2 |
3 |
4 |
3,3 |
|
|
|
|
|
|
si1 |
si2 |
si3 |
si4 |
si5 |
yi |
1 |
3 |
-2 |
0 |
-2 |
0,5 |
|
2,2361i -0,4472i |
-0,4472i -1,3416i -1,7471i |
|||
|
|
0,8944i 2,0125i 1,5653i -7,5803i |
|||
|
|
|
3,0414i |
2,2194 |
-2,2928 |
|
|
|
|
0,8221i |
0,1643i |
-6,0978 |
-2,2016 |
-6,8011 |
-8,8996 |
0,1998 |
xi |
1.1.5Схема Халецкого
¯
Дана система Ax¯ = b, где
A = |
. . . |
. . . . . . |
, |
¯b = |
. . . |
|
|
|
a11 |
. . . |
a1n |
|
|
a1n+1 |
|
|
an1 |
. . . |
ann |
|
|
ann+1 |
Представляем матрицу A в виде произведения двух матриц B и C, т.е. A = BC
a21 |
a22 |
. . . a2n |
= |
b21 |
b22 |
|||||||
|
a11 |
a12 |
. . . a1n |
|
|
|
b11 |
0 |
||||
an |
1 |
an |
2 |
. . . ann |
|
bn |
1 |
bn |
2 |
|||
|
|
|
|
|
|
|
|
|
||||
|
. . . . . . . . . . . . |
|
|
|
. . . . . . |
|||||||
|
|
|
|
|
|
|
|
|
|
. . . |
0 |
0 |
1 |
. . . c2n |
||
. . . |
0 |
|
1 |
c12 |
. . . c1n |
|
. . . bnn |
0 |
.0 |
. . . 1 |
|||
. . . . . . |
|
. . . . . . . . . . . |
|
|||
|
|
|
|
|
|
|
Элементы bij , cij определяются по формуле:
bi1 = ai1, |
j−1 |
||
bij |
= aij |
|
bik ckj , |
|
|
− k=1 |
|
|
|
||
|
|
|
|
(i ≥ j > 1),P |
c1j = |
a1j |
, |
b11 |
||
1 |
i−1 |
|
|
|
P |
cij = bii (aij − k=1 bik ckj ),
(1 < i < j).
Вектор решения x¯ может быть найден из последовательного решения уравнений
|
|
¯ |
Cx¯ = y¯. |
|
|
|
By¯ = b, |
|
|
Так как B и C матрицы треугольные, то |
− bik yk! |
|
||
y1 = |
b11 |
; yi = ain+1 |
/bii, (i > 1), |
|
|
a1n+1 |
|
i−1 |
|
|
|
|
X |
|
|
|
|
k=1 |
|
и |
|
|
n |
|
|
|
|
|
|
|
xn = yn; xi = yi − |
X |
|
|
|
cik xk , (i < n). |
k=i+1
12
Пример. Методом Халецкого решить систему уравнений
3x1 |
+x2 |
−x3 |
+2x4 |
= |
6 |
−5x1 |
+x2 |
+3x3 |
−x4 |
= −12 |
|
2x1 |
−5x2 |
+x3 |
−x4 |
= 1, 0 |
|
x1 |
+3x3 |
−3x4 |
= |
3 |
Расчетный вид бланка и схема решения системы.
x1 |
x2 |
x3 |
x4 |
|
x1 |
x2 |
|
|
x3 |
|
x4 |
|
a11 |
a12 |
a13 |
a14 |
a15 |
3 |
1 |
|
|
−1 |
|
2 |
6 |
a21 |
a22 |
a23 |
a24 |
a25 |
−5 |
1 |
|
|
3 |
|
−4 |
−12 |
a31 |
a32 |
a33 |
a34 |
a35 |
2 |
0 |
|
|
1 |
|
−1 |
1 |
a41 |
a42 |
a43 |
a44 |
a45 |
1 |
−5 |
|
|
3 |
|
−3 |
3 |
b11|1 |
c12 |
c13 |
c14 |
c15 |
3|1 |
1/3 |
|
|
−1/3 |
|
2/6 |
2 |
b21 |
b22|1 |
c23 |
c24 |
c25 |
−5 |
8/3 |
|1 |
|
0, 5 |
|
−0, 25 |
−0, 75 |
b31 |
b32 |
b33|1 |
c34 |
c35 |
2 |
−2/3 |
|
2 |
|1 |
|
−1, 25 |
−1, 75 |
b41 |
b42|1 |
b43 |
b44|1 |
c45 |
1 |
−16/3 |
|
6 |
2, 5 |
|1 |
3 |
|
|
|
|
|
x1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
x2 |
|
|
|
|
|
|
|
−1 |
|
|
|
|
x3 |
|
|
|
|
|
|
|
2 |
|
|
|
|
x4 |
|
|
|
|
|
|
|
3 |
Ответ: x1 = 1, x2 = −1, x3 = 2, x4 = 3.
1.1.6Метод отражений. Вариант 1
Метод отражений решения системы уравнений Ax = f состоит в выполнении n−1 шагов (n - порядок матрицы), в результате чего матрица A системы приводится к верхней
треугольной форме, и последующем решении системы с верхней треугольной матрицей. Пусть в результате выполнения k − 1 шагов матрица A привелась к виду
|
|
a11(1) |
a12(1) ... |
a1(1)k−1 |
a1(1)k |
a1(1)k+1 |
|
|
|
a22(2) ... |
a2(2)k−1 |
a2(2)k |
a2(2)k+1 |
|
|
|
... |
(k−1) |
(k−1) |
(k−1) |
|
|
|
|
ak−1k−1 |
ak−1k |
ak−1k+1 |
|
|
|
|
... |
... |
... |
Ak−1 |
= |
|
|
(k−1) |
(k−1) |
|
|
|
|
|
|
a |
a |
|
|
|
|
|
|
|
|
|
|
|
|
kk |
kk+1 |
|
|
|
|
|
|
|
|
|
|
0 |
|
... |
... |
|
|
|
|
|
(k−1) |
(k−1) |
|
|
|
|
|
ank |
ank+1 |
|
|
|
|
|
... |
... |
|
|
|
|
|
|
|
... a1(1)n |
|
|
... a2(2)n |
||
... |
(k−1) |
|
... ak−1n |
|
|
|
... |
|
... |
(k−1) |
|
a |
|
|
|
kn |
|
|
|
|
... ... |
|
|
|
||
|
|
|
... ... |
|
|
|
||
... |
ann(k−1) |
|
|
Опишем k-й шаг процесса. Цель k-го шага - обнулить все поддиагональные элементы k-го
столбца. Для этого определим вектор нормали p(k) = (0, ..., 0, p(k), p(k) |
|
, ..., pn(k))T , положив |
|
|||||||||
|
|
|
|
|
|
|
|
k k+1 |
|
|
|
|
pk |
= akk |
+ σk v |
|
|
|
|
|
(k−1) |
≥ |
|
(6) |
|
|
(alk |
)2, σk = |
|
|
||||||||
(k) |
(k−1) |
|
n |
(k−1) |
|
|
( |
1, akk(k−1) |
|
|
0, |
|
|
|
u l=k |
|
|
|
1, akk |
< 0, |
|
||||
|
|
uX |
|
|
|
− |
|
|
|
|
|
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
|
|
pl(k) = alk(k−1), l = k + 1, ..., n. |
|
|
|
|
(7) |
13
n
Определим теперь матрицу отражения Pk с элементами p(ijk) = σij −2p(ik)p(jk)/ P(p(l k))2, где
l=k
σij символ Кронеккера.
Легко проверить, что матрица Ak = PkAk−1 имеет вид
|
|
a11(1) |
a12(1) ... |
a1(1)k−1 |
a1(1)k |
a1(1)k+1 |
|
|
|
a22(2) ... |
a2(2)k−1 |
a2(2)k |
a2(2)k+1 |
|
|
|
... |
(k−1) |
(k−1) |
(k−1) |
|
|
|
|
ak−1k−1 |
ak−1k |
ak−1k+1 |
|
|
|
|
... |
... |
... |
Ak−1 |
= |
|
|
0 |
(k−1) |
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
kk+1 |
|
|
|
|
|
|
|
|
|
|
0 |
|
... |
... |
|
|
|
|
|
0 |
(k−1) |
|
|
|
|
|
ank+1 |
|
|
|
|
|
|
... |
... |
|
|
|
|
|
|
|
... a1(1)n |
|
|
... a2(2)n |
||
... |
(k−1) |
|
... ak−1n |
|
|
|
... |
|
... |
(k−1) |
|
a |
|
|
|
kn |
|
|
|
|
... ... |
|
|
|
||
|
|
|
... ... |
|
|
|
||
... |
ann(k−1) |
|
|
т.е. поддиагональные элементы ее k-ого столбца равны нулю, а первые k − 1 строк и столбцов ее совпадают, с соответствующими строками и столбцами матрицами Ak−1. Кроме того,
можно показать, что остальные элементы вычисляются по формулам
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(pl(k)alj(k−1)) |
|
|||
|
|
|
|
n |
|
|
|
|
|
|
|
||||
akk |
= |
− |
σk v |
(alk )2, |
aij |
= aij |
− |
2pi |
P n |
(k) |
)2 |
, |
(8) |
||
(k) |
|
|
uX |
(k−1) |
(k) |
(k−1) |
|
(k) l=k |
|
|
|
|
|||
|
|
|
t |
|
|
|
|
|
|
l=k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
i = k, k + 1, . . . , n, |
j = k + 1, . . . , n. |
|
|
|
|
В результате выполнения всех n − 1 шагов матрица A приведется к верхней треугольной
матрице
An−1 = Pn−1Pn−2...P2P1A,
которую мы в дальнейшем будем обозначать через R : R = An−1. Обозначив еще Q = , приходим к равенству A = QR, которое удобно использовать для получения
решения системы Ax = f .
Обратимся теперь к решению системы Ax = f . Если мы получили разложение A = QR, то для решения этой системы нам, очевидно, достаточно решить систему Rx = Q f с треугольной матрицей R и правой частью g = Q f .Решение этой системы находится по
простым явным формулам:
xn = gn/rnn, xi = |
n |
, |
i = n |
1, n 2, ..., 1. |
P |
||||
|
gi − j=i+1 rij xj |
|
− |
− |
|
rij |
|
Однако прежде чем находить решение по этим формулам, нам необходимо сначала вычислить правую часть преобразованной системы, т.е. вектор g = Pn−1 . . . P2P1f . Обозначим f (k) = Pk Pk−1P1f .Тогда f (k) = Pkf (k−1). Предположим, что вектор f (k−1) имеет вид
f (k−1) = (f1(1), f2(2), ..., fk(k−−11), fk(k−1), fk(k+1−1), ..., fn(k−1))T .
В силу определения матрицы Pk и определяющего ее вектора p(k) легко проверить, что вектор f (k) будет иметь вид
f (k) = (f1(1), f2(2), ..., fk(k−−11), fk(k), fk(k+1) , ..., fn(k))T ,
14
где элементы f |
(k) |
вычисляются по формулам |
|
|
||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
(k−1) |
|
|
|
fi |
= fi |
|
2pl |
p(k)f |
||
|
|
|
Pn |
|
, i = k, k + 1, ..., n. |
|||
|
|
|
|
|
|
l |
l |
|
|
|
(k) |
(k−1) |
− |
(k) l=k |
|
|
|
|
|
|
|
|
(p(k))2 |
|
||
|
|
|
|
|
|
P |
|
|
l
l=k
Пример. Решить систему методом отражения
6, 03x1 + 13x2 − 17x3 = 2, 0909 13x1 + 29, 03x2 − 38x3 = 4, 1509
|
Расчетный бланк |
−17x1 − 38x2 + 50, 03x3 = −5, 1191 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
k |
|
a1 |
a2 |
a3 |
a4 |
p |
z(2) |
z(3) |
z(4) |
|
|
a11 |
a12 |
a13 |
a14 |
p1 |
2r2p1/s |
2r3p1/s |
2r4p1/s |
k |
|
a21 |
a22 |
a23 |
a24 |
p2 |
2r2p2/s |
2r3p2/s |
2r4p2/s |
|
|
a31 |
a32 |
a33 |
a34 |
p3 |
2r2p3/s |
2r3p3/s |
2r4p3/s |
|
|
|
|
|
|
s = kpk2 |
r2 = (p, a2) |
r3 = (p, a3) |
r4 = (p, a4) |
|
|
6,03 |
13 |
-17 |
2,0909 |
28,2642 |
62,5533 |
-82,0807 |
8,9989 |
0 |
|
13 |
29,03 |
-38 |
4,1509 |
13 |
28,7711 |
-37,7526 |
4,1390 |
|
|
-17 |
-38 |
50,03 |
-5,1191 |
-17 |
-37,6238 |
49,3688 |
-5,4126 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1256,867 |
1390,825 |
-1825,002 |
200,084 |
|
|
-22,2342 |
-49,5533 |
65,0807 |
-6,9080 |
0 |
|
0 |
0 |
1 |
|
0 |
0,2589 |
-0,2473 |
0,0119 |
0,7156 |
|
-0,9322 |
-0,2231 |
|
|
0 |
-0,3762 |
0,6611 |
0,2934 |
-0,3762 |
|
0,4901 |
0,1173 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,6536 |
|
-0,4257 |
-0,1019 |
|
|
a(1) |
a(2) |
a(3) |
a(4) |
x |
|
|
|
|
|
-22,2342 |
-49,5533 |
65,0807 |
-6,9080 |
1,03 |
|
|
|
2 |
|
0 |
-0,4567 |
0,6849 |
0,2350 |
1,03 |
|
|
|
|
|
0 |
0 |
0,1710 |
0,1761 |
1,03 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Ответ: x1 = 1, 03, x2 = 1, 03, x3 = 1, 03.
1.1.7Метод отражений. Вариант 2
Метод отражений применяется для решения системы уравнений Ax = f с комплексно неособенной матрицей. В этом методе матрица A раскладывается на произведение двух
матриц: унитарной матрицы и правой треугольной.
При реализации данного метода необходимо воспользоваться следующими соотношениями:
ω¯ = χ(¯s − αe¯), α = |α|eargα, |α| =1p(¯s, s¯), argα = arg(¯s, e¯) − π, |
(9) |
|
χ = |
. |
p
2[|α|2 + |α||(¯s, e¯)|]
Разложение комплексной матрицы A в произведение унитарной и правой треугольной
происходит за несколько шагов. Шаг 1.
15
В качестве вектора s¯ выберем первый столбец матрицы A, т.е. s¯ = (a11, a21, . . . , an1), а за e¯ возьмем вектор e¯ = (1, 0, . . . , 0)′. Воспользуемся соотношениями (9) для нахождения α, χ, ω¯1. Построим матрицу C1 = E − 2ω¯1ω¯1 . Обозначим A1 = C1A. Матрица A1 имеет вид
|
|
0 |
a22(1) |
· |
a2(1)n |
|
|
|
a11(1) |
a12(1) |
|
a1(1)n |
|
A = |
· · · |
· (1)· · |
·· |
a ·(1)· · |
||
|
|
0 |
a |
· |
ann |
|
|
|
|
n2 |
|
|
|
|
|
|
|
|
|
|
Шаг 2.
В качестве вектора s¯ выберем s¯ = (0, a(1), . . . , a(1))′, а за e¯ возьмем вектор e¯ = (0, 1, . . . , 0)′. |
||||||||
|
|
|
21 |
|
n1 |
|
|
|
Затем находим ω¯2 и строим матрицу C2 = E − 2ω¯2ω¯2 . Обозначим A2 = C2A. Матрица A2 |
||||||||
имеет вид |
|
|
|
|
|
|
|
|
|
|
a11(2) |
a12(2) |
a31(2) |
|
· |
a1(2)n |
|
|
0 |
a22(2) |
a23(2) |
|
a2(2)n |
|||
A = |
|
0 |
|
(2) |
|
· |
(2) |
|
0 a33 |
|
· |
a3n |
|||||
|
|
|
· (2)· · |
(2)· |
a |
· · · |
|
|
|
· · · |
|
(2) |
|
||||
|
|
0 |
a |
a |
|
|
ann |
|
|
|
|
n2 |
n3 |
|
· |
|
|
|
|
|
|
|
|
|
|
Продолжая этот процесс, получаем в итоге матрицу An−1, имеющую правотреугольный
вид.
|
Рассмотрим, как находится решение системы линейных алгебраических уравнений мето- |
дом отражений. |
|
|
Обозначим через A0 = {a1(0), . . . , an(0)+1} расширенную матрицу системы Ax = f , где an(0)+1 = |
(b1 |
, b2, ..., bn)′, a(0) = (a1k , a2k , ..., a1n)′, k = 1, ..., n. |
|
k |
|
Данная матрица преобразуется к правой треугольной с помощью матриц отражения |
|
Ak+1 = Ck+1Ak или a¯i(k+1) = Ck+1a¯i(k), k = 0, ..., n − 1, i = 1, ..n + 1. |
При построении матрицы Ck+1 в качестве векторов e¯ и s¯ возьмем векторы e¯=(0, ..., 0, 1, ..., 0)′,
s¯=(0, ..., 0, a(k) |
, a(k) |
, ..., a(1) |
)′. |
k+1k+1 |
k+2k+1 |
nk+1 |
|
После n − 1 шага система Ax = f имеет вид
a11(n−1)x1 |
+a12(n−1)x2 |
+... a1(nn−1) xn |
= a1(nn−+11) , |
||
|
a22(n−1)x2 |
+... a2(nn−1) xn |
= |
a2(nn−+11) , |
|
... |
... |
... |
.... |
... |
... |
|
|
|
ann(n−1) xn |
= |
ann(n−+11) . |
Решение системы (10) находится по формулам
|
|
|
|
n |
|
|
a(n−1) |
|
akn(n−+11) |
− i=k+1 ani(n−1)xi |
|
xn = |
|
, xk = |
|
a(P1) |
. |
ann( 1) |
|
||||
nn+1 |
|
n− |
|||
|
n− |
|
|
|
|
|
|
|
|
kk |
|
(10)
(11)
Пример. Решить систему линейных алгебраических уравнений методом отражений.
2x1 + (−9 + 4i)x2 + (4 − 3i)x3 = 15 − i
−(9 + 4i)x1 + 6x2 + (−1 + 2i)x3 = −22 + 26i−(4 + 5i)x1 − (1 + 2i)x2 − 3x3 = −12 + 10i
16
Решение. Пользуясь приведенным алгоритмом, находим:
|
|
|
|
A = −9 − 4 i |
− 6 |
|
−1 + 2 i −22 + 26 i |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
2 |
|
9 + 4 i |
4 − 3 i |
15 − i |
|
|
|
|||||
|
|
|
|
|
−4 − 5 i −1 − 2 i |
|
−3 |
−12 + 10 i |
|
|
|
||||||||||
Шаг первый прямого хода. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
= (2, −9 − 4 i, −4 − 5 i), |
|
= (1, 0, 0) |
|
|
|
|||||||||
|
|
|
|
|
|
s |
e |
|
|
|
|||||||||||
ω¯1 = |
|
|
|
|
|
|
|
|
α = −11, 9164; |
χ = 0, 05491 |
|
|
|
|
|||||||
|
0, 4942 |
0, 2196 i |
ω¯1 = 0, 7641, |
|
0, 4942 + 0, 2196 i, |
|
0, 2196 + 0, 2746 i |
||||||||||||||
|
|
|
0, 7641 |
|
|
|
|
|
|
|
|
− |
|
|
− |
|
|
||||
|
−0, 2196 − |
0, 2746 i |
|
|
|
|
|
|
|
||||||||||||
− |
− |
|
|
|
|
|
|
|
|
|
|
|
|
−0, 3377 + 0, 1749 |
|
||||||
|
|
V1 = 0, 7553 + 0, 3357i |
|
0, 4151 |
|
|
|
||||||||||||||
|
|
|
|
|
−0, 1678 |
|
0, 7553 − 0, 3357i |
0, 3357 − 0, 4196i |
|
||||||||||||
A1 = − |
|
0, 3357 + 0, 4196 |
−0, 3377 − 0, 1749 i |
0, 528 |
|
|
|||||||||||||||
0 |
|
−4, 9621 + 0, 5005 i |
−4, 626 − 0, 6176 i |
−4, 8363 + 9, 5965 i |
|||||||||||||||||
|
|
|
11, 9163 |
4, 8671 − 2, 9371 i |
1, 7622 + 3, 6084 i |
10, 2378 + 35, 581 i |
|||||||||||||||
|
|
0 |
|
−7, 4783 − 4, 98837 i |
1, 0306 + 0, 1708 i |
8, 3972 + 8, 5532 i |
|
||||||||||||||
Шаг второй прямого хода. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
s¯ = (0, −4, 9621 + 0, 5005 i, −7, 4783 − 4, 9884 i), |
e¯ = (0, 1, 0) |
|
||||||||||||||||
|
|
|
argα = −π + 3, 0411; |
α = 10, 2282 − 1, 0316 i; |
χ = 0, 05644 |
|
|||||||||||||||
ω¯2 = −0, 8574 + 0, 08648 i |
|
ω¯2 = 0, −0, 8574 − 0, 08648 i, −0, 4221 + 0, 2816 i |
|||||||||||||||||||
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0, 4221 |
|
0, 2816 i |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
− |
|
− |
= 0 |
|
−0, 4851 |
|
|
0, 6751 + 0, 5558 i |
|
|||||||||||
|
|
|
|
V2 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
0 |
|
|
|
|
||
|
|
|
|
|
0 |
−0, 6751 − 0, 5558 i |
− |
0, 4851 |
|
|
|
||||||||||
A2 |
= |
0 |
|
10, 2283 − 1, 0317 i |
−3, 0349 + 0, 7571 i |
−12, 7689 − 5, 7625 i |
|||||||||||||||
|
|
−11, 9163 |
4.8671 − 2, 9371 i |
−1, 7622 + 3, 6084 i |
−10, 2378 + 35, 581 i |
|
|||||||||||||||
|
|
|
0 |
|
|
|
|
|
0 |
|
|
−2, 9662 − 2, 0714 i |
6, 1426 − 5, 017 i |
|
|||||||
Обратный ход. |
|
|
|
|
|
x¯ = |
−1, 2676 − 0, 0212 i |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
−0, 214 − 3, 1751 i |
|
|
|
|
|
−0, 5981 + 2, 1091 i
17
1.2Итерационные методы
Пусть дана система n линейных алгебраических уравнений с n неизвестными
a11x1 + a12x2 + · · · + a1nxn = b1
a21x1 + a22x2 + · · · + a2nxn = b2 (12)
· · ·· · · · · · ·· · ·· · ·· · ·· · ·· · ·· · ·· · ·
an1x1 + an2x2 + · · · + annxn = bn
Итерационные методы дают решение системы линейных алгебраических уравнений в виде предела последовательности некоторых векторов, построение которых осуществляется при помощи единообразного процесса, называемого процессом итерации. Для решения системы линейных алгебраических уравнений итерационными методами предварительно приводят систему к виду удобному для итерации
¯
x¯ = β + αx¯.
Сделать это можно несколькими способами. Например, если в матрице A |aii| >
(13)
P
|aij |
j=6i
для каждого i = 1, .., n, то удобно разрешить каждое из уравнений системы относительно диагонального неизвестного, поделив обе части i-го уравнения на aii и перенеся все члены его, кроме xi, вправо.
Можно также привести систему (12) к виду (13), если прибавить к обеим частям i-го уравнения xi, а затем перенести свободные члены влево.
Сходящийся процесс обладает важным свойством самоисправляемости, т.е. отдельная ошибка в вычислениях не отразится на окончательном результате, так как ошибочное приближение можно рассматривать как новый начальный вектор.
Обычно итерации продолжаются до тех пор, пока kx¯(k+1) − x¯(k)k ≤ ε, где ε - заданная
точность.
1.2.1Метод простой итерации
В методе простой итерации в качестве начального приближения берем произвольный вектор x¯(0) и подставляем в правую часть системы, приведенной к виду, удобному для итерации. Получаем некоторый вектор x¯(1). Продолжая этот процесс, получим последовательность век-
торов
x¯ |
(1) |
¯ |
(0) |
|
= β + αx¯ |
|
|
x¯ |
(2) |
¯ |
(1) |
|
= β + αx¯ |
|
· · ·· · ·· · ·· · ·
¯
x¯(k) = β + αx¯(k−1)
Если при k → ∞ x¯(k) → x¯, то вектор x¯(k) будет решением системы (13), т. е. системы (12).
Достаточные условия сходимости метода простой итерации устанавливаются теоремой 1. Для сходимости процесса простой итерации достаточно, чтобы какая-либо из норм матрицы α была меньше единицы
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
X |
|
|
|
|
(14) |
k |
α |
k∞ = |
max |
| |
α |
< |
1 |
, |
|
|
i |
ij | |
|
|
|
j=1
18
|
|
|
n |
|
|
|
|
|
|
|
|
X |
|
|
|
|
(15) |
α |
|
max |
α |
< |
, |
|||
k |
k1 = j |
| ij | |
1 |
|
|
|||
|
|
|
i=1 |
|
|
|
|
|
|
= v |
|
|
|
|
|||
kαk2 |
n n |
|αij |2 < 1. |
(16) |
|||||
|
|
u i=1 j=1 |
|
|
|
|
|
|
|
|
uX X |
|
|
|
|
|
t
¯
Следствие. Для системы Ax¯ = b метод простой итерации сходится, если
X
|aii| > |aij | (i = 1, 2, ..., n)
i=6j
или
X
|ajj | > |aij | (j = 1, 2, ..., n).
i=6j
Пример. Методом простой итерации решить систему уравнений с точностью ε = 10−3:
10x1 + 2x2 + x3 = 10 x1 + 10x2 + 2x3 = 12
x1 + x2 + 10x3 = 8
Решение. Так как диагональные элементы матрицы A данной системы по модулю пре-
восходят сумму модулей остальных элементов соответствующих строк, то метод простой итерации в этом случае сходится [Положий].
Разрешая систему относительно неизвестных, стоящих на диагонали, получаем:
|
|
|
|
|
x2 |
= −0, 1x1 |
− 0, 2x3 |
+ 1, 2 |
||||
|
|
|
|
|
|
|
x1 |
= 0, 2x2 |
|
0, 1x3 |
+ 1 |
|
|
|
|
|
|
x3 |
= −0, 1x1 |
− |
0, 1x2 + 0, 8 |
||||
|
|
|
|
|
|
|
−(0) |
|
− |
|
|
|
|
Принимая начальное приближение x¯ |
= 0, получаем следующие результаты вычисле- |
||||||||||
ний: |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||
|
k |
|
x1 |
x2 |
x3 |
|
kx(k+1) − x(k)k1 |
|
|
|||
|
1 |
|
1 |
1,2 |
0,8 |
|
|
|
|
|
|
|
|
2 |
|
0,68 |
0,94 |
0,58 |
|
0,32 |
|
|
|
|
|
|
3 |
|
0,754 |
1,016 |
0,638 |
|
0,076 |
|
|
|
|
|
|
4 |
|
0,733 |
0,997 |
0,623 |
|
0,021 |
|
|
|
|
|
|
5 |
|
0,7383 |
1,0021 |
0,6270 |
|
0,0053 |
|
|
|
|
|
|
6 |
|
0,73688 |
1,00077 |
0,62596 |
|
0,00142 |
|
|
|
|
|
|
7 |
|
0,73725 |
1,00112 |
0,62624 |
|
0,00037 |
|
|
|
|
Сравнивая эти результаты с точным решением |
|
|
|
||||||
x1 = |
704 |
= 0, 73717, |
x2 = |
956 |
= 1, 00105, x3 |
= |
598 |
= 0, 62618, |
|
|
|
|
|
||||||
955 |
955 |
955 |
видим, что метод простой итерации в данном случае сходится довольно быстро [8].
19
1.2.2Метод Зейделя
Метод Зейделя представляет собой модификацию метода простой итерайции. Основная его идея состоит в том, что при вычислении (k + 1)-го приближения неизвестной xi учитывается уже вычисленное ранее (k + 1)-е приближения неизвестных x1, x2, ..., xk .
Пусть система, приведенная к виду удобному для итерации, записана так:
n
X
xi = βi + αij xi, (i = 1, .., n)
j=1
Выберем произвольно начальные приближения корней x(0)1 , x(0)2 , ..., x(0)n .
Далее, предполагая, что k-е приближения x(ik) корней известны, согласно Зейделю будем строить (k + 1)-е приближение корней по следуюшим формулам:
|
x1(k+1) = β1 |
n |
|
|
+ αij xj(k) |
||
|
|
X |
|
|
|
j=1 |
|
x2(k+1) = β2 + α21x1(k+1) |
n |
||
αij xj(k) |
|||
|
|
|
X |
|
· · ·· · ·· · ·· · · |
j=2 |
|
|
|
||
|
i−1 |
|
n |
xi(k+1) = βi + αij xj(k+1) |
+ αij xj(k) |
||
|
X |
|
X |
|
j=1 |
|
j=i |
|
· · ·· · ·· · ·· · · |
|
|
x(k+1) = βn + |
n−1 |
+ αnnx(k), (k = 0, 1, 2, ...) |
|
αij x(k+1) |
|||
n |
X |
|
n |
j |
|
||
|
j=1 |
|
|
Указанная ранее теорема сходимости для метода простой итерации остается верной для итерации по методу Зейделя.
Пример. Методом Зейделя решить следующую систему с точностью ε = 10−3:
10x1 + 2x2 + x3 = 10 x1 + 10x2 + 2x3 = 12
x1 + x2 + 10x3 = 8
Разрешая систему относительно неизвестных, стоящих на диагонали, получаем:
x1 = −0, 2x2 − 0, 1x3 + 1 x2 = −0, 1x1 − 0, 2x3 + 1, 2
x3 = −0, 1x1 − 0, 1x2 + 0, 8
Достаточные условия сходимости метода Зейделя здесь выполнены.
Принимая начальное приближение x¯(0) = 0, из первого уравнения найдем x1 = 1. При x1 = 1 и x3 = 0 второе уравнение дает x2 = 1, 1. Наконец, при x1 = 1 и x2 = 1, 1 находим из третьего уравнения x3 = 0, 59. Таким образом, первое приближение будет:
x1 = 1, x2 = 1, 1, x3 = 0, 59.
20