Глава 1. Интерполирование 6 страница

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

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

Пример. Решить систему

.

Вычисления оформить в виде табл. 4.2.

Таблица 4.2

Х1	-Х1	Х3	Свободные члены
		-4	-7	-8
	-2
	-3
		-2		-4
	-4
			Х3=2	=3
			Х2=1	=2
			Х1=0	=1

Последний столбец таблицы служит для контроля вычислений. Например, рассмотрим четвертую строку таблицы. Элемент b₁₅=4 получен так же, как все остальные элементы строки, т.е. (-8)/2. После его вычисления проверяем, нет ли ошибки в вычислении элементов этой строки. Последний элемент строки должен равняться сумме всех остальных элементов строки:

1+1/2-2-7/2=-4.

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

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

В чем преимущество решения системы методом Гаусса по сравнению с решением системы по формулам Крамера? При непосредственном раскрытии определителей в формулах Крамера решение системы n уравнений с n неизвестными требует порядка n!n арифметических операций: уже при n=30 такое число операций недоступно для современных ЭВМ. Число операций умножения и деления, которые выполняются в схеме единственного деления, равно , т.е. порядка n³.

4.2. Вычисление определителей

при помощи метода Гаусса

Рассмотрим для простоты определитель третьего порядка

(4.15)

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

1

где (j=2, 3) вычисляются по формулам (4.3). Умножаем первую строку определителя последовательно на и и вычитаем ее из второй и третьей строк соответственно:

1

0 = , (4.16)

0

где (i=2, 3; j=2, 3) вычисляются по формулам (4.5).

Этим мы снизили порядок определителя на единицу. Применим к полученному определителю те же преобразования. Выносим из первой строки за знак определителя:

1

,

где вычисляется по формуле (4.7).

Умножаем первую строку полученного определителя на и вычитаем ее из второй строки определителя. Получаем

1

0 = . (4.17)

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

Пример. Вычислить при помощи метода Гаусса определитель

2 1 4

3 2 -1

-4 1 3.

Вычисления удобно оформить в виде табл. 4.3.

Таблица 4.3

Превый столбец	Второй столбец	Третий столбец
-2
		-1
-4
	1/2		7/2
	1/2	-7	-13/2
		-14	-13

Последний столбец страницы служит для контроля вычислений.

4.3. Вычисление обратной матрицы

при помощи метода Гаусса

Пусть дана неособенная матрица А:

…

А = …

… … … …

…

Требуется найти матрицу, обратную данной. Обозначим

…

Х=А^-1 …

… … … …

…

По определению обратной матрицы , где Е – единичная матица, т.е.

. (4.18)

Пусть

К-й столбец матрицы , а

к-й столбец единичной матрицы.

Тогда равенство (4.18) можно заменить следующими равенствами:

. (4.19)

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

Пример. Найти обратную матрицу для матрицы

1 2 -1

0 1 3

2 -1 -2.

Вычисление оформить в виде табл. 4.4.

Таблица 4.4

		-1
	-1	-2
	-5		-2			-6
			-2
			-2/15	5/15	1/15	19/15
			=2/15	=5/15	=1/15	19/15
			=6/15	=0	=-3/15	18/15
			=1/15	=5/15	=7/15	28/15

Ответ:

1 5 7

6 0 -3

-2 5 1.

4.4. Некоторые сведения из линейной алгебры

1. Сходимость последовательностей векторов и матриц. Пусть в n–мерном пространстве задана последовательность векторов

(к=1, 2, …).

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

.

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

Определенная таким образом сходимость называется сходимостью по составляющим, или покомпонентной сходимостью.

2. Нормы векторов и матриц. Введем понятие нормы вектора, обобщающее понятие длины вектора. Нормой вектора Х называется действительное число , удовлетворяющее следующим условиям:

1.) при и ;

2.) при любом числовом множителе с;

3.) .

(Вместо второго и третьего уравнений можно записать условие ). Вводить норму вектора можно различными способами, только бы выполнялись условия пп. 1 – 3. Укажем наиболее применимые нормы векторов:

1.) (4.20)

2.) (4.21)

3.) (евклидова норма). (4.22)

Третья норма вектора – это длина вектора. Можно проверить, что для всех трех норм выполняются условия пп. 1 – 3.

Рассмотрим понятие нормы матрицы. Нормой квадратной матрицы Ф называют число , удовлетворяющее следующим условиям:

1.) при и ;

2.) при любом числовом множителе с;

3.) ;

4.) .

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

. (4.23)

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

1. (4.24)

Эта норма матрицы согласована с первой нормой вектора (4.20).

2. (4.25)

Эта норма матрицы согласована со второй нормой вектора (4.21).

3. , (4.26)

где - наибольшее собственное значение матрицы А*А (А* матрица, комплексно сопряженная с транспонированной матрицей А^/).

Эта норма матрицы согласована с третьей нормой вектора (4.22). на практике иногда используется норма матрицы

. (4.27)

Эта норма матрицы также согласована с третьей нормой вектора (4.22).

В начале параграфа была рассмотрена сходимость последовательности векторов и матриц по компонентам. Введем понятие сходимости по норме.

Последовательность векторов Х^(к) сходится к вектору Х по норме, если при . Можно доказать, что в конечномерном пространстве сходимости по норме и по компонентам равносильны. Покажем справедливость этого утверждения для трех введенных нами норм векторов (формулы (4.20) – (4.22)). Пусть имеет место покомпонентная сходимость, т.е.

.

Покажем, что отсюда следует сходимость по норме. Действительно

при ;

при ;

при .

Покажем также, что на сходимости по норме следует сходимость по компонентам. Пусть

.

Тогда

.

Отсюда

.

Пусть

или .

Отсюда вытекает, что

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

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

Аналогично можно определить сходимость по норме последовательности матриц и показать, что сходимость по норме равносильна сходимости по компонентам.

4.5. Метод простой итерации