Методы решения СЛАУ с трехдиагональной матрицей

Методы обращения матриц

Задача нахождения обратной матрицы вплотную примыкает к задаче решения систем линейных алгебраических уравнений вида . Пусть - обратная матрица к матрице . Умножим обе части последнего матричного уравнения слева на матрицу . В результате получим . Откуда или . Таким образом, зная обратную матрицу , можно определить решение системы уравнений.

a) Метод Гаусса.

Используем метод Гаусса для нахождения обратной матрицы. Пусть обратная матрица к матрице

имеет вид .

Из определения обратной матрицы следует, что , т. е.

= .

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

,

где вектор -ой системы имеет вид: , , если . Решив все систем методом Гаусса, получим матрицу .

b) Метод Жордана.

Пусть после -го шага преобразования по методу Жордана матрица имеет вид

.

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

.

Применяя описанный процесс к матрице , получим матрицы , причем, ,

,

…………………..

,

.

Но в соответствии с методом Жордана . Отсюда находим

.

Из определения обратной матрицы имеем

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

Тогда . При этом все вычисления происходят внутри одного массива.

с) Метод отражений.

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

Рассмотрим алгоритм обращения верхней треугольной матрицы. Пусть

, .

Тогда и по правилу умножения матриц получаем

, ;

, , ;

, , ,

;

………………………………………………………………………………………………………

, , ,

.

ЛЕКЦИЯ № 14

4.9. Обусловленность систем линейных алгебраических уравнений

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

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

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

Будем считать, что решение и правая часть системы (4.1) принадлежат линейному пространству , состоящему из - мерных векторов. Введем в пространстве норму. Нормой вектора называется действительное число, удовлетворяющее условиям:

для любого , ;

для любого числа и любого ;

для любых .

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

. (4.32)

Из определения следует, что для всех , ,

для любых матриц , ; , где - единичная матрица.

Вместе с основной системой (4.1) рассмотрим возмущенную систему

, (4.33)

которая отличается от (4.1) правой частью. Будем предполагать, что матрица не возмущается. Обозначим , .

Говорят, что система (4.1) устойчива по правой части, если при любых и справедлива оценка

, (4.34)

где - постоянная, не зависящая от правых частей и . Оценка (4) выражает факт непрерывной зависимости решения от правой части, т. е. показывает, что при . Вопрос исследования устойчивости является важным потому, что никогда нельзя задать правую часть точно. На самом деле вместо вектора задается какой-то близкий ему вектор . Погрешность может возникнуть, например, в результате округления.

Покажем, что если , то система (4.1) устойчива по правой части. Так как из (4.1) и (4.33) следует, что , то в силу существования обратной матрицы и

, (4.35)

т.е. выполняется неравенство (4.34) с константой .

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

В оценку (4.35) входят абсолютные погрешности решения и правой части . При решении системы (4.1) более естественными характеристиками являются относительные погрешности

, .

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

, (4.36)

которое следует из (4.1). Перемножив (4.35) и (4.36), получим оценку

, (4.37)

где .

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

Предположим, что в системе (4.1) возмущены как правая часть, так и коэффициенты матрицы . Рассмотрим вместе с системой (4.1) возмущенную систему

(4.38)

и обозначим , , .

Лемма 4.1. Пусть - квадратная матрица, удовлетворяющая условию и - единичная матрица. Тогда существует матрица , причем

. (4.39)

Доказательство: Для любого вектора имеем

,

где . Однородное уравнение имеет только нулевое

решение, так как из равенства и неравенства следует,

что и . Поэтому в неравенстве можно обозначить

, и переписать его в виде . Отсюда получаем

,

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

Теорема 4.4. Пусть матрица имеет обратную и пусть выполнено условие

. (4.40)

Тогда матрица имеет обратную и справедлива следующая оценка относительной погрешности:

. (4.41)

Доказательство: Докажем, что существует матрица, обратная матрице . Имеем

,

где . По условию (10) имеем

, (4.42)

поэтому согласно лемме 4.1 существует матрица , следовательно, и .

Получим оценку (4.41). Для этого сначала представим вектор в виде

.

Согласно (4.1) имеем , поэтому

. (4.43)

Получим оценки норм матриц и . Обозначим . Имеем

,

, .

По лемме 4.1 получим

,

так как . Далее,

и

.

Переходя к равенству (4.43), получим

.

Преобразуем . Получаем

.

Тогда окончательно имеем неравенство

,

которое совпадает с неравенством (4.41).

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

ЛЕКЦИЯ № 15

Методы решения СЛАУ с трехдиагональной матрицей

Не нашли, что искали? Воспользуйтесь поиском по сайту: