Лекция 8.

Численное решение СЛАУ. Прямые методы.

Необходимые сведения из линейной алгебры.

Определение.

Нормой вектора x называется число xr , удовлетворяющее условиям: xr > 0, xr = 0 xr = 0 .

Векторное пространство с введенной нормой называют нормированным.

Одновременно оно является метрическим, поскольку можно положить

ρ(xr, yr) = xr− yr .

Определение.

Нормой квадратной матрицыA называется число, обозначаемое A и

удовлетворяющее следующим свойствам:

A > 0, A = 0 A = 0

αA = α A , где A - скаляр.

A + B ≤ A + B .

A B ≤ AB .

Пример.

A c = maxi ∑j Aij

67

Определение. Норма матрицы A согласована с нормой вектора x , если A xr ≤ Axr . Будем требовать выполнения этого свойства.

Задачи линейной алгебры.

-решение системы линейных уравнений

-вычисление определителей и обращения матриц

-вычисление собственных значений и собственных векторов матриц. Задачи линейной алгебры - самые распространенные с точки зрения при-

кладной математики.

Библиотека МИАН (РАН) (Математический Институт АН имени Стеклова): работы вычислительного характера по линейной алгебре:

С1828 по 1974 год, т.е. за 147 лет, 4000 наименований (Статья Гаусса).

С1975 по 1980 - 3000 наименований.

С1981 по 1984 - 4000 наименований.

Наиболее часто встречается первая задача., т.е. решение системы линейных уравнений (ОДУ, ДУ с ЧП).

Пусть требуется найти решение системы:

Известны формулы, дающие в явном виде решение задачи (1). Это формулы Крамера:

столбца с номером i на столбец правых частей системы. Определитель можно вычислить следующим образом:

68

= ∑(−1)[P1,...,Pn ] ap11ap2 2...apnn , где последовательности p1,..., pn - различные

Pn

перестановки натуральных чисел от 1 до n , Pn = n! - число возможных пере-

становок.

[ p1,..., pn ] - число так называемых “беспорядков”, или инверсий, в переста-

новке.

На практике эти формулы неприменимы, т.к. для подсчета каждого определителя надо вычислить n! слагаемых, что нереально при весьма умеренных

n .

Пример.

n =100 ; 100!≥1090 . Если одно слагаемое вычислять 10−6 секунд, что вполне

Фактически же в настоящее время решаются системы с n ≈104 . Существуют 2 группы методов решения системы: прямые и итерацион-

ные.

Определение.

Прямые методы - это методы, позволяющие теоретически (и без ошибок округления) получить точное решение СЛАУ за конечное число арифметических операций.

Определение.

Итерационные методы (или методы последовательных приближений) по-

зволяют вычислить последовательность векторов{xr(n)} , сходящихся при n → ∞

к решению задачи.

Примеры.

Прямые методы: метод Крамера, метод Гаусса, метод прогонки. Итерационные методы: метод простых итераций (МПИ).

69

Метод исключения Гаусса (прямой метод).

Сложность задачи Axr = fr определяется структурой матрицы A .

m = n −1, n − 2,...,2,1.

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

Треугольная матрица.

xn - 1 операция; xn−1 - 3 операции; xn−2 - 5 операций и т.д.

Матрица общего вида:

1)прямой ход → приведение матрицы к треугольному виду.

2)обратный ход → решение системы с треугольной матрицей. Реализация прямого хода:

Пустьa11 ≠ 0 . Иначе всегда можно переставить уравнения, чтобы это усло-

вие выполнялось (т.к. det A ≠ 0 всеai1 ≠ 0 ) .

Умножая первое уравнение на li(1) = − ai1 и складывая полученный резуль-

a11

тат с i - ым уравнением, исключаем из i - того уравнения xi .

70

Проделывая те же действия для i = 2,3,..., n , придем к системе уравнений

следующего вида:

нений для i = 3,4,..., n . Аналогичным образом из оставшихся уравнений исклю-

чаются x3 , x4 и так далее. Выполнив (n −1) шагов, получим систему с тре-

угольной матрицей.

Далее последует обратный ход, т.е. решение системы с треугольной мат-

Т.о. мы рассмотрели простейшую схему исключения (метод исключения Гаусса).

71

Пример.

Из первого уравнения получаем x1 =10−7 −107 x2 , подставляем во второе:

x2 = 107 − 4 ≈1 , x1 = 0 , что не удовлетворяет второму уравнению системы.

107 − 2

Причины возникновения больших погрешностей:

-деление на малые числа

-появление больших (по величине) промежуточных результатов

-потеря точности при вычитании больших близких друг другу чисел Таким образом, порядок последовательного исключения элементов (тем

более для систем высокого порядка) может сильно сказаться на результатах

Строка с этим коэффициентом ставится первой в системе.

После этого делаем 1- ый шаг вычисления (делим на максимальное чис-

ло).

Затем, перед исключением x2 из оставшихся уравнений отыскивается

После этого меняем номера у x1 и x j0 .Тогда максимальный по величине из коэффициентов первого уравнения окажется в позиции a11 , и т.д.

Наиболее надежным является метод исключения с выбором главного элемента по всей матрице на каждом шаге исключения.

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

72

Замечание.

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

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

aii(k ) > ∑aij (k ) , i = k, k +1,..., n , k =1,2,..., n −1 .

j≠i

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

Оценка влияния неустранимой погрешности решения СЛАУ. Источники:

-ошибки округления

-неточность входных данных

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

Вводя в рассмотрение нормы векторов и согласованные с ними нормы матриц, получим оценку величины погрешности:

73

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

Определение.

Значение μA называется числом обусловленности матрицы A . Именно эта величина определяет, насколько сильно погрешности входных данных могут повлиять на решение системы Axr = f .

Всегда μA >1. Действительно, 1 = E = A−1 A ≤ A−1 A = μA .

Если μA умеренной величины, μA ~ (1÷10), то ошибки входных данных ска-

зываются на решении сравнительно слабо, и система Axr = f называется хоро-

шо обусловленной.

Если μA велико, μA ≥103 , то система Axr = f называется плохо обусловлен-

ной, решение ее сильно зависит от ошибок в правых частях и коэффициентах.

Замечание.

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

Если, например, погрешность входных данных 106 , а допустимая по-

грешность решения 10−2 , то даже при μA 104 систему можно считать хорошо обусловленной.

Замечание.

Подчеркнем, что данное свойство (обусловленность), выражаемое нера-

74

шения системы Axr = fr, а является изначальной характеристикой решаемой за-

дачи.

Пример. Рассмотрим систему:

100x1 +99x2 =199,99x1 +98x2 =197

Ее решение x1 = x2 =1 .

Изменим правые части:

100x1 +99x2 =198.9999x1 +98x2 =197.01 .

Решение "возмущенной" задачи x1 ≈ 2.97, x2 ≈ −0.99 .

r

Чтобы сопоставить полученные результаты с оценкой для решения δxrx

r

Относительная погрешность δrf ≈ 1 10−4 = 0.005% . Это очень малая величи-

f 2

на.

75

r

Оценку погрешности δxrx через μA не является завышенной.

Об оценке ошибок округления арифметических операций. (Результаты исследований).

Можно показать, что машинное решение x′ = x + δx линейной системы, вычисленное методом Гаусса, точно удовлетворяет уравнениям с определенным

образом возмущенными коэффициентами:

(A + δA) xr′ = fr

Для нормы матрицы так называемых “эквивалентных возмущений” δA справедлива оценка вида:

δA ≈ n g(a) A p−t .

Здесь n - порядок системы,

p - основание машинной арифметики (особенно p = 2 ),

t - число значащих цифр при выполнении арифметических операций,

где k - номер шага на этапе прямого метода исключения ( g(a) - “коэффи-

циент роста”). Отсюда

разрядных машинах p = 2,t = 26 нельзя рассчитывать на точность, лучшую чем

Если же при этом μA =104 , то происходит полная потеря точности.

Заключение.

Таким образом, плохо обусловленные системы вызывают значительные трудности при их решении.

76

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

77