Сходимость и погрешность приближённых методов

Для описания сходимости вычислительного процесса и оценки погрешности приближённого решения необходимы дополнительные понятия.

Понятие нормы. Нормой вектора х, обозначается , называется величина удовлетворяющая условиям:

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.

Представим матрицу А в виде суммы А=А₁+А₂, где det А₁ ≠ 0. Тогда

(А₁+А₂) x=b,

отсюда

.

Обозначив через , , получим

,

что и требовалось. Тогда для того, чтобы обеспечить выполнение достаточного условия сходимости , в качестве А₁ достаточно взять матрицу близкую к А, т.е. А₁≈А, в качестве А₂, - «малую» матрицу .

Поясним это предложение на примере. Рассмотрим

,

Здесь . Пусть

,

Тогда . Найдём .

Имеем det А₁ = -2 ≠ 0 и

.

Тогда

и система принимает вид

.

Очевидно, для сходимости метода итераций достаточно взять .

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

В качестве примера рассмотрим следующую систему

В результате анализа коэффициентов левой части уравнений производится их перестановка

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

или, в нормальной форме,

.

Здесь матрица

,

очевидно, её норма , и, следовательно, формируемый ею итерационный процесс сходится.

Третий вариант. Является обоснованным теоретически, формализуемым и, по этой причине, пожалуй, наиболее удобным. Он заключается в следующем.

Рассмотрим систему (3.1₁)

Ax=b

и предположим, что det А₁ ≠ 0. Умножим обе части на , получим

A₁ x=b₁,

где A₁=А^ТА, b₁= A^T b. Здесь матрица A₁ является симметрической, т.е. , причём её диагональные элементы , в противном случае, по крайней мере, один из столбцов матрицы А равен нулю и, следовательно, 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