Далее, согласно правому граничному условию

.

Отсюда можно найти остальные неизвестные в процессе обратной прогонки с помощью рекуррентной формулы .

Число операций, которое требуется для решения системы общего вида методом Гаусса, растет при увеличении пропорционально. Метод прогонки сводится к двум циклам: сначала по формулам рассчитываются прогоночные коэффициенты, затем с их помощью по рекуррентным формулам находятся компоненты решения системы. Это означает, что с увеличением размеров системы число арифметических операций будет расти пропорционально, а не. Таким образом, метод прогонки в пределах сферы своего возможного применения является существенно более экономичным. К этому следует добавить особую простоту его программной реализации на компьютере.

Во многих прикладных задачах, которые приводят к СЛАУ с трехдиагональной матрицей, ее коэффициенты удовлетворяют неравенствам:

,

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

Согласно теореме предыдущего раздела решение таких систем всегда существует и является единственным. Для них также справедливо утверждение, которое имеет важное значение для фактического расчета решения с помощью метода прогонки.

Лемма

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

.

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

---

.

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

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

---

2. Обусловленность слау.

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

1. Норма матрицы.

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

и евклидова норма

,

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

1. ,тогда и только тогда, когда;

2. ;

3. (неравенство треугольника).

Для скалярного произведения справедливо неравенство Коши-Буняковского .

Рассмотрим квадратную матрицу размером. Она определяет в пространстве линейное преобразование

или

.

---

Введем величину

,

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

,

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

.

Отсюда следует, что в конечномерном пространстве норма матрицы ограничена, причем на единичной сфере всегда найдется такой вектор , что

.

Наконец, из определения нормы следует, что

.

Это простое неравенство лежит в основе всех дальнейших оценок.

2. Корректность решения слау.

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

1. Решение задачи существует.

2. Решение задачи единственное.

3. Решение задачи непрерывно зависит от входных данных.

Обсудим с точки зрения этого определения задачу решения СЛАУ с неравным нулю определителем

,

считая матрицу фиксированной и рассматривая в качестве входных данных вектор правых частей системы.

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

---

.

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

тоже можно записать через обратную матрицу :

,

где

.

Отсюда получаем

.

Неравенство доказывает непрерывную зависимость возмущения решения от возмущения правой части:

при.

Это означает, что решение СЛАУ с неравным нулю определителем - корректная математическая задача: для нее выполняются все три требования корректности Адамара.

3. Число обусловленности матрицы.

Исходное уравнение позволяет написать неравенство:

.

Перемножая его с неравенством того же знака , получим:

.

Пусть , тогда, согласно ,и неравенство можно переписать в виде:

,

где

.

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

---

Смотрите также файлы

• BOA462~1.doc

• 8.doc

• 7.doc

• 4.doc

• 15.doc