Вычисление определителя и обратной матрицы

Г) Метод Зейделя

В) Итерационный метод

Запишем систему уравнений (3.9) в виде

Ах = b,(3.21)

где А – матрица коэффициентов; b– вектор правых ча­стей системы.

Преобразуем (3.21) к виду, удобному для итераций:

х = Вх + с. (3.22)

Тогда метод простой итерации определяется формулой:

x^k+1 = Bx^k + c, k = 0, 1, ... , (3.23)

где начальное приближение x⁰ задано.

В качестве критерия сходимости метода итераций обычно применяют условие

||x^k+1 - x^k|| £ ε.

Сформулируем теоремы об условиях сходимости мето­да простых итераций.

Теорема 3.1 (достаточное условие сходимости).Если ||В|| < 1, то система (3.21) имеет единственное решение, а итерационный метод (3.23) сходится к решению со ско­ростью геометрической прогрессии.

Теорема 3.2. (необходимое и достаточное условие схо­димости).Пусть система (3.22) имеет единственное реше­ние. Итерационный процесс (3.23) сходится к решению системы (3.22) тогда и только тогда, когда все собствен­ные значения матрицы В по модулю меньше единицы.

Теоремы 3.1 и 3.2 не дают способов преобразования произвольной системы линейных уравнений к виду (3.22) так, чтобы метод итераций (3.23) при этом сходился к решению. Эти теоремы имеют важное теоретическое значение. На практике для проверки условия сходимости метода итераций более полезна теорема 3.1, а теорему 3.2 удается использовать тогда, когда собствен­ные значения матрицы В известны. Задача определения собственных значений матрицы в общем случае сложнее, чем задача решения системы линейных уравнений.

Для преобразования системы уравнений к виду, удоб­ному для итераций, можно умножить систему (3.21) на матрицу D = А^-1- ε, где ε – произвольная матрица. Тог­да система примет вид (3.22)

х= Вх + с, В = εА, с = Db (3.24)

и матрица В будет удовлетворять теореме 3.1, если выб­рать элементы матрицы ε достаточно малыми по модулю. Однако этот прием не выгоден, так как для вычисления обратной матрицы А^-1необходимо выполнить не меньше операций, чем при решении самой системы.

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

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

Пусть требуется решить систему уравнений (3.1):

(3.25)

Выразим из первого уравнения переменную х₁ из вто­рого – х₂и т. д.:

Пусть k-e приближение к решению обозначено как х^k = . Подставим его в правую часть полу­ченной системы и выразим следующее приближение x^k+1= .В отличие от метода итераций, метод

Зейделя использует при вычислении уже най­денные компоненты вектора х^k+1.

Расчетные формулы метода Зейделя можно записать в виде

(3.26)

Теорема 3.3(достаточные условия сходимости).Пусть при всех i для коэффициентов системы уравнений (3.25) выполняются условия

. (3.27)

Тогда метод Зейделя сходится и выполняется неравен­ство

||x^k+1 - x^k||₁ £ q||x^k – x*||₁ (3.28)

где х* – точное решение системы (3.25).

Если матрица А удовлетворяет условию (3.27), гово­рят, что А – матрица с диагональным преобладанием.

Теорема 3.4(достаточные условия сходимости).Пусть матрица А системы (3.1) – вещественная, симмет­ричная и положительно определенная. Тогда метод Зей­деля сходится.

3.3.Погрешность решения и обусловленность системы уравнений

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

Ах = b₁,b₁ = b + η.

Пусть х¹ решение неточно заданной системы Ах = b₁, х – решение точной системы Ах = b.Обозначим погрешность решения через r = х¹ - х.Тогда можно запи­ть Ах¹= b₁в виде А (х + r) = b + η,и Аr= η.

Определение 3.5. Мерой обусловленности системы называется число

. (3.29)

Мера обусловленности системы равна верхней грани отношения относительной погрешности решения к относительной погрешности правой части. Из формулы (3.29) следует неравенство

(3.30)

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

Учитывая, что r = А^-1η,можно получить формулу вы­числения меры обусловленности системы:

(3.31)

Определение 3.6. Мерой обусловленности матрицы А называется число

. (3.32)

Для вычисления меры обусловленности матрицы мож­но с помощью (3.31) получить формулу

. (3.33)

Учитывая (3.30), можно записать

(3.34)

Неравенство (3.34) связывает относительные погреш­ности правой части и решения системы через свойства матрицы системы.

Определение 3.7. Системы уравнений и матрицы назы­ваются плохо обусловленными,если их меры обусловлен­ности принимают большие значения, и хорошо обуслов­ленными,если меры обусловленности принимают малые значения.

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

Вычисление определителя матрицы является класси­ческим примером задач, для решения которых важно найти эффективные алгоритмы.

При непосредственном раскрытии определителя квад­ратной матрицы

n-го порядка нужно найти сумму n! слага­емых, каждое из которых равно произведению n элементов матрицы, взятых по одному с каждого столбца и каждой строки, т. е. нужно выполнить порядка n!n операций. Число операций для вычисления определителя 100-го по­рядка приблизительно равно 100! × 100 = 100^157,9 × 100. Та­кое число операций не способен выполнить за приемле­мое время ни один из существующих суперкомпьютеров. Тем не менее современные компьютерные программы вы­числения определителей справляются с матрицами и бо­лее высокого порядка, используя экономичные алгорит­мы. Одним из таких алгоритмов является метод Гаусса.

Если матрица приведена к диагональному или треу­гольному виду, то ее определитель равен произведению диагональных элементов.

Для преобразования матрицы к треугольному виду можно применить метод Гаусса, который потребует порядка 2n³/3 операций.

Для n = 100 имеем 2n³/3 = 0,67 ×10⁶. На такой объем арифметических операций современный пер­сональный компьютер тратит не более 1 с.

Если внимательно проанализировать метод Гаусса, то можно увидеть, что он фактически позволяет одновре­менно с приведением матрицы коэффициентов к треу­гольному виду, вычислить определитель этой матрицы. Действительно, определитель матрицы коэффициентов системы уравнений (3.18) равен произведению диагональ­ных элементов, т. е. единице. С другой стороны, если к любой строке матрицы прибавить другую строку, умно­женную на число, определитель не изменится. А если строку матрицы разделить на число, отличное от нуля, то определитель матрицы разделится на то же число. Отсю­да следует, что в результате преобразований к виду (3.18), определитель матрицы коэффициентов системы уравне­ний (3.9) изменился на множитель, который равен про­изведению ведущих элементов, т. е. мы получаем форму­лу для вычисления определителя

.

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