2015-06-24
1343
Для описания сходимости вычислительного процесса и оценки 
погрешности приближённого решения необходимы дополнительные понятия.
Понятие нормы. Нормой вектора х, обозначается 
, называется величина удовлетворяющая условиям:
1. 
;
2. 
х=0; (3.6)
3. 
;
4. 
.
В теории метрических пространств получили распространение следующие типы норм:
1. 
;
2. 
;
3. 
.
В зависимости от типа геометрической фигуры, получаемой в трёхмерном пространстве, описываемой условием 
, первая из них называется кубической, вторая,- октаэдрической и третья,- сферической.
Нормой матрицы А, обозначается 
, называется величина, удовлетворяющая помимо требований (3.6) дополнительному условию
Обычно, используются одна из следующих норм:
1. 
;
2. 
;
3. 
.
При одновременном использовании норм необходимо их согласование. А именно, норма вектора первого типа используется с нормой матрицы первого типа и т.д.
Понятие расстояния. Расстоянием между векторами x, y, обозначается символом 
, называется величина
.
Из свойства 4 (3.6) следует важное для дальнейшего, так называемое, неравенство треугольника
Действительно,
Сжимающие отображения. Пусть F,- некоторое отображение в линейном пространстве векторов. Оно называется сжимающим,- если существует такое число 
, что для любых векторов x, y выполняется соотношение
.
Применительно к нормальной форме системы уравнений (3.3) в качестве F рассмотрим правую часть системы уравнений. А именно,
.
Тогда
.
Таким образом, для того, чтобы отображение, определяемое системой (3.3) было сжимающим достаточно, чтобы одна из норм матрицы В была меньше 1.
Понятие сходимости. Пусть 
, где к = 1, 2, …,- некоторая бесконечная последовательность векторов. Говорят, что она сходится к вектору х по норме, если
Последовательность 
сходится к вектору 
покомпонентно, если
для 
.
Нетрудно показать, что два эти понятия в некотором роде эквивалентны. А именно, если последовательность 
сходится по норме, то она сходится покомпонентно и наоборот.
При анализе сходимости последовательностей центральное место принадлежит признаку Коши:
Последовательность сходится тогда и только тогда, когда для   такой номер  , что для  и   выполняется  (или  для ). |
Сходимость итерационного процесса. Оценка погрешности. Пусть ,- итерационная последовательность, т.е.
, (3.7)
где 
,- сжимающее отображение с коэффициентом сжатия 
.
Рассмотрим 
. По индукции имеем
. (3.8)
Далее, по свойству треугольников и с учетом (3.8), справедливым оказывается соотношение
(3.9)
Потребовав теперь, чтобы
,
очевидно, можно найти номер 
, начиная с которого 
для 
, m > 0.
Таким образом, для сжимающего отображения признак Коши выполнен и, следовательно, итерационный процесс (3.7) сходится.
Оценим теперь погрешность к -го приближения, а именно, величину 
, где х - точное решение. С этой целью рассмотрим соотношение (см. (3.9))
Переходя в нём к пределу при 
, получим, таким образом,
(3.10)
и доказанным становится утверждение:
| Если одна из норм матрицы B системы уравнений (3.3) меньше единицы, то итерационный процесс (3.4) является сходящимся при любом начальном приближении. Погрешность к -го приближения описывается соотношением (3.10). |
3.5 Приведение системы Ax=b к нормальному виду
Из предыдущего следует, что успех приближённого решения системы линейных алгебраических уравнений (3.1) во многом определяется возможностью её приведения к нормальному виду (3.3), для которого выполняется достаточные условия сходимости. Приведём некоторые соображения и рекомендации на этот счёт.
Первый вариант. Рассмотрим систему
Ах=b.
Представим матрицу А в виде суммы А=А1+А2, где det А1 ≠ 0. Тогда
(А1+А2) x=b,
отсюда
.
Обозначив через 
, 
, получим
,
что и требовалось. Тогда для того, чтобы обеспечить выполнение достаточного условия сходимости 
, в качестве А1 достаточно взять матрицу близкую к А, т.е. А1≈А, в качестве А2, - «малую» матрицу 
.
Поясним это предложение на примере. Рассмотрим
,
Здесь 
. Пусть
,
Тогда 
. Найдём .
Имеем det А1 = -2 ≠ 0 и
.
Тогда
и система принимает вид
.
Очевидно, для сходимости метода итераций достаточно взять 
.
Второй вариант. Состоит в следующем. Путём эквивалентных преобразований стараются добиться того, чтобы диагональные элементы в матрице А доминировали в левой части соответствующих уравнений, т.е. были по модулю существенно больше остальных. После этого каждое из уравнений делят на 
и, первое уравнение разрешают относительно 
второе,- относительно 
и т.д.
В качестве примера рассмотрим следующую систему
В результате анализа коэффициентов левой части уравнений производится их перестановка
и для обеспечения доминирования во втором уравнении коэффициента 
, который пока равен -7,9, ко второму уравнению прибавляется третье. В результате этого имеем
или, в нормальной форме,
.
Здесь матрица
,
очевидно, её норма 
, и, следовательно, формируемый ею итерационный процесс сходится.
Третий вариант. Является обоснованным теоретически, формализуемым и, по этой причине, пожалуй, наиболее удобным. Он заключается в следующем.
Рассмотрим систему (3.11)
Ax=b
и предположим, что det А1 ≠ 0. Умножим обе части на 
, получим
A1 x=b1,
где A1=АТА, b1= AT b. Здесь матрица A1 является симметрической, т.е. 
, причём её диагональные элементы 
, в противном случае, по крайней мере, один из столбцов матрицы А равен нулю и, следовательно, det А = 0. Далее деля уравнение на диагональные элементы 
и, разрешая их относительно , и т.д. получим нормальную систему
,
где 
.
Показано, что для нормальной системы, полученной таким образом, метод Зейделя сходится.
Варианты индивидуальных заданий
1. При помощи ручного просчета найти решение системы линейных уравнений Аx=b методом Жордана – Гаусса, заданную своей расширенной матрицей согласно варианта задания. Вычисления провести с выбором определяющего элемента.
2. Написать программу решения системы методом Зейделя Аx=b, заданной своей расширенной матрицей. Максимальное количество уравнений в системе равно восьми. Исходные данные программы - расширенная матрица системы и значение допустимой погрешности. Выходные данные - вектор-столбец Х решения системы, проверка решения А*x и количество итераций, выполненное для получении решения.
Варианты систем для задания 1
| № 1 -6 -2 -4 68 -4 2 5 -1 -3 -1 -5 43 | № 2 -5 3 2 -24 3 3 5 -29 -4 -1 5 -43 | № 3 -1 1 1 5 1 2 -5 -6 -2 -5 2 -25 | № 4 -2 4 -3 -2 -4 -1 2 5 -5 1 1 4 | № 5 -1 -2 -2 7 1 -3 -4 -3 3 -3 -2 -25 |
| № 6 -6 -1 5 6 -6 -2 -6 32 -6 -3 5 14 | № 7 -4 -4 -4 40 3 4 4 -37 2 -1 -6 26 | № 8 1 -3 -5 2 2 1 4 -17 4 -6 1 -19 | № 9 -4 -2 -5 16 1 -6 5 7 -4 3 1 -28 | № 10 -4 -3 4 -21 3 1 5 12 5 5 2 30 |
| № 11 -3 1 -1 -6 -4 -2 3 15 -2 1 -5 -18 | № 12 5 -6 5 20 -1 -4 -1 14 1 2 3 -28 | № 13 2 5 -1 -41 -2 5 1 -29 2 -4 -3 14 | № 14 1 -6 4 65 2 2 5 28 -1 -3 2 25 | № 15 5 5 -4 -42 -2 4 -1 -9 -2 4 -5 -21 |
| № 16 1 5 -3 -5 -5 5 -4 30 -4 -5 4 15 | № 17 4 1 -5 11 3 4 2 1 1 5 5 -10 | № 18 -5 2 -2 25 -5 -2 -3 30 -6 5 -6 14 | № 19 -1 -4 -1 22 -5 -4 -2 46 -6 -1 -1 40 | № 20 5 -6 -2 15 -6 2 -6 30 -5 -4 -4 57 |
| № 21 -6 2 -5 37 4 -6 -4 16 4 4 2 -42 | № 22 -3 5 1 17 1 1 -3 5 1 -4 5 -12 | № 23 4 -5 -2 -3 -4 5 -1 3 -2 -5 1 39 | № 24 -5 1 -3 -7 3 -1 -5 -35 1 4 1 -13 | № 25 -1 -4 -6 -17 -4 2 1 -10 5 5 -4 63 |
