Абсолютная и относительная погрешности вектора.

Абсолютная погрешность вектора x^*

Относительная погрешность вектора x^* .

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

Пусть  — точное решение линейной системы , а

 — решение системы с возмущенной матрицей :

, ,

вычитая из второго уравнения первое, имеем , откуда  и, следовательно, .

Величину  принято называть числом обусловленности матрицы.

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

Пусть  — решение системы с возмущенной правой частью: :

, , , ,  и  т.е.

Заметим, что если , то . Такое определение числа обусловленности позволяет дать следующую геометрическую интерпретацию обусловленности матрицы. Матрица  отображает n-мерную единичную сферу (множество векторов единичной длины ) в множество векторов различной длины . Это множество — r-мерный эллипсоид в Rⁿ,r — ранг матрицы А, для невырожденных систем r = n. На рисунке изображен случай n =2.

Здесь  и  — наибольшее и наименьшее сингулярные числа матрицы — соответственно большая и малая полуоси эллипса и плохая обусловленность отвечает сильно вытянутым эллипсам.

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

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

Решение линейной системы методом Гаусса

Методы решения систем линейных алгебраических уравнений можно разделить на точные и приближенные. Примером точных методов может служить метод Крамера, который на самом деле никогда не применяется из-за огромного количества вычислений и связанных с ними ошибок округления. Точные методы решения линейных систем применяют для решения линейных систем относительно небольшой размерности (до ). Метод Гаусса — точный метод решения невырожденной системы линейных алгебраических уравнений. Метод Гаусса, его еще называют методом гауссовых исключений, состоит в том, что систему  линейных алгебраических уравнений относительно  неизвестных

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

решение которой находят по формулам

Общее число арифметических операций прямого хода метода Гаусса , считая размерность системы n.

Пример.

Легко убедиться, что точным решением системы является вектор . Если решить эту задачу методом Гаусса, выполняя вычисления с тремя значащими цифрами, то в результате округлений получится совершенно непригодное решение .

Решение системы линейных алгебраических уравнений

методом простых итераций

Точные методы решения линейных систем применяют для решения линейных систем относительно небольшой размерности (до ). Для решения систем большей размерности ( ) используют итерационные методы. Для решения систем еще больших размерностей(> 10⁶ )  применяют специальные методы, которые здесь не рассматриваются Метод прогонки – алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами. Общее число арифметических операций прямого хода 8n.

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

Метод состоит в следующем.

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

Преобразовать систему  к виду  можно, например, выделив диагональные элементы: .

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

Тогда

1) решение  системы  существует и единственно;

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

1) Из курса линейной алгебры известно, что система линейных алгебраических уравнений имеет единственное решение при любой правой части тогда и только тогда, когда соответствующая однородная система имеет только нулевое решение. Пусть  - решение однородной системы . . Т.к. по условию , это неравенство возможно только при . Следовательно, =0 и тем самым первое утверждение теоремы доказано.

2) Вычитая из равенства  равенство , получим

.

Вычисляя норму левой и правой частей этого равенства и используя неравенство  получим :

.

Справедливость неравенства (*) установлена. Учитывая, что  не зависит от k, а  при  получаем, что  при .

В качестве условия окончания итерационного процесса можно взять условие , где  — заданная погрешность. Тогда полагаем .

Решение системы методом Зейделя. В итерационном методе Зейделя (метод Зейделя называют методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений) . При вычислении каждой последующей компоненты решения используются уточненные значения предыдущих компонент. 

Метод Зейделя легко записать в компактной матричной форме: ,

, .

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