book chis_met

другу треугольных матриц

Формулы для определения sij :

После того как матрица S найдена, решают систему

S′y = b,

а затем находят неизвестные x1, x2, ..., xn из системы

Sx = y

Так как обе системы имеют треугольную форму,то они легко решаются.

При практическом применении метода последовательно прямым ходом вычисляются коэффициенты sij и yi (i = 1, 2, ..., n), а затем обратным ходом находятся неизвестные xi

(i = n, n − 1, ..., 1).

Пример. Методом квадратного корня решить систему уравнений

11

Расчетный бланк решения.

1.1.5Схема Халецкого

¯

Дана система Ax¯ = b, где

Представляем матрицу A в виде произведения двух матриц B и C, т.е. A = BC

Элементы bij , cij определяются по формуле:

Вектор решения x¯ может быть найден из последовательного решения уравнений

k=i+1

12

Пример. Методом Халецкого решить систему уравнений

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

Ответ: x1 = 1, x2 = −1, x3 = 2, x4 = 3.

1.1.6Метод отражений. Вариант 1

Метод отражений решения системы уравнений Ax = f состоит в выполнении n−1 шагов (n - порядок матрицы), в результате чего матрица A системы приводится к верхней

треугольной форме, и последующем решении системы с верхней треугольной матрицей. Пусть в результате выполнения k − 1 шагов матрица A привелась к виду

Опишем k-й шаг процесса. Цель k-го шага - обнулить все поддиагональные элементы k-го

13

n

Определим теперь матрицу отражения Pk с элементами p(ijk) = σij −2p(ik)p(jk)/ P(p(l k))2, где

l=k

σij символ Кронеккера.

Легко проверить, что матрица Ak = PkAk−1 имеет вид

т.е. поддиагональные элементы ее k-ого столбца равны нулю, а первые k − 1 строк и столбцов ее совпадают, с соответствующими строками и столбцами матрицами Ak−1. Кроме того,

можно показать, что остальные элементы вычисляются по формулам

В результате выполнения всех 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 .Решение этой системы находится по

простым явным формулам:

Однако прежде чем находить решение по этим формулам, нам необходимо сначала вычислить правую часть преобразованной системы, т.е. вектор 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

l

l=k

Пример. Решить систему методом отражения

6, 03x1 + 13x2 − 17x3 = 2, 0909 13x1 + 29, 03x2 − 38x3 = 4, 1509

Ответ: x1 = 1, 03, x2 = 1, 03, x3 = 1, 03.

1.1.7Метод отражений. Вариант 2

Метод отражений применяется для решения системы уравнений Ax = f с комплексно неособенной матрицей. В этом методе матрица A раскладывается на произведение двух

матриц: унитарной матрицы и правой треугольной.

При реализации данного метода необходимо воспользоваться следующими соотношениями:

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 имеет вид

Шаг 2.

Продолжая этот процесс, получаем в итоге матрицу An−1, имеющую правотреугольный

вид.

При построении матрицы Ck+1 в качестве векторов e¯ и s¯ возьмем векторы e¯=(0, ..., 0, 1, ..., 0)′,

После n − 1 шага система Ax = f имеет вид

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

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

Решение. Пользуясь приведенным алгоритмом, находим:

−0, 5981 + 2, 1091 i

17

1.2Итерационные методы

Пусть дана система n линейных алгебраических уравнений с n неизвестными

a11x1 + a12x2 + · · · + a1nxn = b1

a21x1 + a22x2 + · · · + a2nxn = b2 (12)

· · ·· · · · · · ·· · ·· · ·· · ·· · ·· · ·· · ·· · ·

an1x1 + an2x2 + · · · + annxn = bn

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

для каждого i = 1, .., n, то удобно разрешить каждое из уравнений системы относительно диагонального неизвестного, поделив обе части i-го уравнения на aii и перенеся все члены его, кроме xi, вправо.

Можно также привести систему (12) к виду (13), если прибавить к обеим частям i-го уравнения xi, а затем перенести свободные члены влево.

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

Обычно итерации продолжаются до тех пор, пока kx¯(k+1) − x¯(k)k ≤ ε, где ε - заданная

точность.

1.2.1Метод простой итерации

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

торов

· · ·· · ·· · ·· · ·

¯

x¯(k) = β + αx¯(k−1)

Если при k → ∞ x¯(k) → x¯, то вектор x¯(k) будет решением системы (13), т. е. системы (12).

Достаточные условия сходимости метода простой итерации устанавливаются теоремой 1. Для сходимости процесса простой итерации достаточно, чтобы какая-либо из норм матрицы α была меньше единицы

j=1

18

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 данной системы по модулю пре-

восходят сумму модулей остальных элементов соответствующих строк, то метод простой итерации в этом случае сходится [Положий].

Разрешая систему относительно неизвестных, стоящих на диагонали, получаем:

видим, что метод простой итерации в данном случае сходится довольно быстро [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)-е приближение корней по следуюшим формулам:

Указанная ранее теорема сходимости для метода простой итерации остается верной для итерации по методу Зейделя.

Пример. Методом Зейделя решить следующую систему с точностью ε = 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