Эксперименты лаба8,9(2курс)

D = 0 – матрица называется вырожденной, система может не иметь решений, или иметь их бесконечное множество.

Для иллюстрации рассмотрим систему двух уравнений

Если изобразить каждое уравнение графически, то возможны три случая:

1) прямые пересекаются, т.е.

a1 6= b1 , a2 b2

2) прямые параллельны, т.е.

a1 = b1 6= c1 , a2 b2 c2

3) прямые совпадают, т.е.

Определитель нашей системы имеет вид

a1 b1

D = .

a2 b2

В практических вычислениях из-за округлений редко удается получить точное равенство определителя нулю. При D ≈ 0 прямые могут оказаться почти параллельными, и координаты точки пересечения могут быть весьма чувствительными к малым изменениям коэффициентов системы. То есть малые погрешности вычислений или исходных данных могут привести к существенным погрешностям в решении. В этом случае система уравнений называется плохо обусловленной.

1.2.Методы решения линейных систем

Методы решения линейных систем делятся на два класса:

1)точные (прямые) методы, которые представляют из себя конечные алгоритмы для вычисления корней системы; примеры: правило Крамера, метод Гаусса, метод главных элементов, метод квадратных корней и др.

2)итерационные методы, позволяющие получать корни системы с

2

заданной точностью путем сходящихся бесконечных процессов, примеры: метод итераций, метод Гаусса – Зейделя, метод релаксации и т.д.

Точные методы используют конечные формулы для вычисления неизвестных.

Плюсы:

–решение получается после заранее известного числа операций,

–универсальность и простота метода.

Минусы:

–в памяти машины должна находиться вся матрица, поэтому при больших матрицах это требует большого объема памяти.

–накопление ошибок округления, поскольку на любом этапе используются все предыдущие результаты. Поэтому даже точные методы на самом деле являются приближенными, при этом затруднительно оценить погрешность.

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

Плюсы:

–нет необходимости хранить в памяти машины всю матрицу,

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

Минусы:

–эффективность существенно зависит от удачного выбора начального приближения и быстроты сходимости метода.

1.3.Точные (прямые) методы

1.Формулы Крамера.

Для системы n линейных уравнений с n неизвестными

с невырожденной матрицей A

= det A 6= 0

единственное решение находится умножением (7) слева на матрицу A−1,

т.е.

A−1Ax = A−1b x = A−1b.

3

В курсе линейной алгебры показывается, что для неизвестных справедливы формулы (Крамера)

a11x + a12y = b1, a21x + a22y = b2

неизвестные записываются следующим образом:

где

Таким образом, решение системы из n уравнений с n неизвестными сводится к вычислению n + 1 определителя порядка n. Т.к. вычисление определителей большого порядка требует выполнения большого объема арифметических операций, то применение данного метода ограничено.

2. Метод Гаусса.

Алгоритм последовательного исключения неизвестных носит название метода Гаусса. В основе метода лежит приведение матрицы системы к треугольному виду. Этого можно достичь, последовательно исключая неизвестные из уравнений:

–с помощью первого уравнения исключаем x1 из второго и всех последующих уравнений системы;

–с помощью второго уравнения исключаем x2 из третьего и всех последующих уравнений системы;

...

–продолжаем до тех пор, пока в левой части последнего (n-го) уравнения не останется одно слагаемое с xn. В результате матрица будет приведена к треугольному виду. Данный процесс носит название прямого хода метода Гаусса.

Далее, решая последнее уравнение, находим xn и подставляем его в предыдущее уравнение. Затем решаем его, находим xn−1 и т.д. В этом состоит обратный ход метода Гаусса.

4

Для того, чтобы исключить x1 из второго уравнения, прибавим к нему

первое, умноженное на −a21 . Далее, умножим первое уравнение на −a31

a11 a11

и сложим с третьим. В результате у нас получится система уравнений

a11x1 + a12x2 + a13x3 =b1, a022x2 + a023x3 =b02, a032x2 + a033x3 =b03,

Далее исключаем из третьего уравнения x2. Для этого надо умножить

второе уравнение на −a032 и сложить с третьим. В результате

a022

a11x1 + a12x2 + a13x3 =b1, a022x2 + a023x3 =b02,

a0033x3 =b003,

где

Далее начинается обратный ход метода.

В процессе исключения неизвестных необходимо выполнять операцию деления на коэффициенты a11, a022 (ведущие элементы). Они должны быть отличны от нуля. Если это не так, то необходимо соответствующим образом переставить уравнения системы, что должно быть предусмотрено в вычислительном алгоритме.

Модификацией метода Гаусса является схема с выбором ведущего элемента. В ней требование неравенства нулю диагональных элементов

5

aii заменяется более жестким: из всех оставшихся в i-ом столбце элементов нужно выбрать наибольший по модулю и переставить уравнения так, чтобы этот элемент оказался на месте элемента aii. Благодаря этому уменьшаются множители, используемые для преобразования уравнений, что уменьшает погрешности вычислений. Модифицированный метод Гаусса обеспечивает приемлемую точность для систем с n . 1000.

3. Метод прогонки.

Метод прогонки представляет собой модификацию метода Гаусса для систем уравнений с трехдиагональной матрицей. Запишем такую систему уравнений:

b1x1+c1x2 = d1, a2x1+b2x2 + c2x3 = d2,

a3x2 + b3x3 + c3x4 = d3,

...................................................

an−1xn−2 + bn−1xn−1 + cn−1xn = dn−1, anxn−1 + bnxn = dn.

Прямая прогонка состоит в нахождении прогоночных коэффициентов Ai и Bi, с помощью которых неизвестное xi выражается через xi+1:

6

или

Последние соотношения можно обобщить для произвольного номера i:

На этом заканчивается прямая прогонка. При обратной прогонке последовательно вычисляются неизвестные xi. Для этого сначала запишем

xn−1 = An−1xn + Bn−1

и последнее уравнение системы

anxn−1 + bnxn = dn.

Из двух последних уравнений находим xn:

xn = dn − anBn−1 . bn + anAn−1

Далее по прогоночным формулам находим все остальные неизвестные.

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

1.Метод простой итерации. Исходная система уравнений

Ax = b.

Отсюда

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

x(1) = Bx(0) + τb.

7

В результате

Формула (16) выражает метод простой итерации. От выбора параметра

τ1 зависит его сходимость и скорость сходимости.

2.Метод Гаусса – Зейделя.

Метод Гаусса – Зейделя является итерационным. Рассмотрим его на примере системы

a11x1 + a12x2 + a13x3 =b1, a21x1 + a22x2 + a23x3 =b2, a31x1 + a32x2 + a33x3 =b3.

Выразим неизвестные из уравнений

Далее зададим некоторое нулевой приближение для неизвестных (x(0)1 , x(0)2 , x(0)3 ). Подставляя в формулу для x1 находим x(1)1 (первое при-

ближение для x1). При вычислении x(1)2 вместо x(0)1 будем использовать x(1)1 . В результате найдем x(1)2 . Далее находим x(1)3 . И далее повторяем вычисления. В общем случае k-ое приближение будет выражаться через k − 1 приближение следующим образом

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

8

1.5.Задачи на собственные значения

Рассмотрим квадратную матрицу n-го порядка:

Вектор

x = {x1, x2, ..., xn}

называется собственным вектором матрицы A, соответствующим собственному значению λ, если он удовлетворяет системе уравнений:

Характеристической матрицей С данной матрицы A называется матрица

где E – единичная матрица. В результате мы получаем, что систему (21) можно записать в виде

Полученная система является однородной системой n линейных уравнений с n неизвестными. Ненулевые решения наша система имеет только в случае

det C = 0.

Определитель det C является многочленом n-й степени относительно λ:

det C = c0λn + c1λn−1 + ... + cn−1λ + cn.

Этот многочлен называется характеристическим многочленом и его корни являются собственными значениями матрицы A.

1.6.Задания для самостоятельной работы

Решить системы линейных уравнений а) методом Гаусса;

9

б) методом простой итерации; в) методом Гаусса – Зейделя.

9, 31x1 + 1, 21x2 + 2, 32x3 + 1, 22x4 + 3, 01x5 = 17, 07 2, 01x1 + 11, 02x2 + 3, 21x3 + 1, 25x4 + 2, 26x5 = 19, 75

1.3, 26x1 + 2, 02x2 + 10, 98x3 + 2, 22x4 + 3, 02x5 = 21, 50

1, 98x1 + 2, 11x2 + 3, 22x3 + 12, 44x4 + 1, 75x5 = 21, 50

4, 02x1 + 1, 01x2 + 1, 02x3 + 2, 55x4 + 9, 90x5 = 18, 50

23, 75x1 + 5, 27x2 + 1, 23x3 + 1, 22x4 + 3, 33x5 = 34, 80 1, 28x1 + 31, 41x2 + 5, 02x3 + 3, 75x4 + 1, 24x5 = 42, 70

2.2, 73x1 + 3, 34x2 + 15, 23x3 + 1, 23x4 + 2, 47x5 = 25, 00

5, 24x1 + 1, 78x2 + 2, 03x3 + 21, 62x4 + 3, 28x5 = 33, 95

3, 45x1 + 2, 22x2 + 1, 23x3 + 4, 54x4 + 22, 16x5 = 36, 60

9, 99x1 + 1, 05x2 + 2, 07x3 + 3, 28x4 + 2, 60x5 = 28, 98 2, 61x1 + 10, 03x2 + 1, 28x3 + 1, 32x4 + 4, 57x5 = 22, 42

3.5, 35x1 + 3, 37x2 + 15, 17x3 + 2, 08x4 + 1, 47x5 = 32, 79

1, 53x1 + 5, 02x2 + 2, 54x3 + 17, 05x4 + 3, 21x5 = 30, 88

3, 77x1 + 1, 25x2 + 2, 74x3 + 4, 01x4 + 15, 16x5 = 30, 70

12, 07x1 + 2, 03x2 + 4, 04x3 + 1, 31x4 + 2, 25x5 = 33, 77 3, 33x1 + 15, 16x2 + 3, 07x3 + 1, 24x4 + 2, 32x5 = 28, 45

4.1, 27x1 + 2, 32x2 + 12, 35x3 + 4, 08x4 + 3, 06x5 = 24, 35

5, 01x1 + 1, 32x2 + 2, 27x3 + 17, 24x4 + 4, 23x5 = 35, 08

4, 14x1 + 2, 03x2 + 1, 23x3 + 3, 21x4 + 22, 04x5 = 36, 79

17, 15x1 + 3, 21x2 + 3, 24x3 + 3, 51x4 + 1, 78x5 = 32, 10 1, 32x1 + 18, 23x2 + 4, 71x3 + 2, 22x4 + 3, 48x5 = 48, 19

5.3, 51x1 + 2, 08x2 + 15, 21x3 + 1, 27x4 + 1, 32x5 = 25, 47

2, 77x1 + 4, 54x2 + 5, 05x3 + 23, 95x4 + 3, 75x5 = 44, 60

3, 29x1 + 1, 71x2 + 2, 33x3 + 4, 75x4 + 17, 89x5 = 31, 68

10