Основные трудности решения систем линейных уравнений. Классификация методов решения

Требуется найти решение системы линейных уравнений

где А = (ai;.) — квадратная матрица коэффициентов при неизвестных; х = (Xj) — вектор-столбец неизвестных; Ь = (бр — вектор-столбец правых частей системы. С точки зрения классической теории линейных алгебраических систем их решение не вызывает затруднений. По правилу Крамера система п линейных уравнений с п неизвестными имеет единственное решение, если определитель системы отличен от нуля (detA * 0) и значение каждого из неизвестных вычисляется как отношение двух определителей порядка п, т. е.

Здесь detA^— определитель матрицы, получаемой заменой j-го столбца матрицы А столбцом правых частей. При непосредственном вычислении определителей как алгебраической суммы п! произведений элементов для отыскания решения системы линейных уравнений по правилу Крамера требуется приблизительно п • л! арифметических операций типа умножения*. Будет показано, что использование метода исключения Гаусса позволяет уменьшить время, необходимое для решения задачи (1.1), до величины менее одной секунды.

Другое важное обстоятельство, связанное с решением систем линейных алгебраических уравнений, состоит в следующем. С точки зрения теории линейных систем различаются два случая: определитель матрицы системы не равен нулю (detA * 0), т. е. система уравнений является невырожденной, либо определитель матрицы системы равен нулю (det А = 0), в этом случае система называется вырожденной. Во втором случае система ли-

*Под операциями типа умножения подразумеваются операции умножения, деления и возведения в степень.

КРАМЕР ГАБРИЕЛЬ (Cramer Gabriel; 1704—1752) — швейцарский математик. Крамер установил правило решения систем линейных уравнений с буквенными коэффициентами (правило Крамера), а также заложил основы теории определителей.

бо не имеет решения, либо имеет неединственное решение. С точки зрения практических вычислений существуют «почти невырожденные системы» — системы, определитель которых близок к нулю, но отличен от нуля (det А ~ 0). Небольшие изменения коэффициентов матрицы системы или правых частей системы в «почти невырожденных системах» могут привести к большим погрешностям решения.

Все эти случаи хорошо иллюстрируются на примере решения системы двух линейных уравнений:

На рис. 1.1 каждому уравнению соответствует прямая на плоскости хгОх2, а точка пересечения этих прямых есть решение системы (1.1).

Если det А = 0, то наклоны прямых равны и они либо параллельны, либо совпадают. При det А ~ 0 небольшие погрешности в коэффициентах и правых частях могут привести к большим погрешностям в решении, т. е. к неточному определению положения точки пересечения.

Рис. 1.1

Системы такого типа, в которых есть малые погрешности в коэффициентах системы или в правых частях (эти погрешности могут быть, в частности, результатом округлений при вычислениях или записи чисел в память компьютера), называются ПЛОХО ОБУСЛОВЛЕННЫМИ.

Плохо обусловленная система геометрически соответствует почти параллельным прямым. В теоретических исследованиях обусловленность характеризуется числом обусловленности X = ||А || • НА"1!), при любой норме > 1. Чем больше это число, тем хуже обусловленность системы; так, при х *= Ю3—104 система уже плохо обусловлена. На практике, однако, ограничиваются проверкой условия det А~ 0.

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

Будут рассмотрены наиболее употребительные прямые и итерационные методы. ПРЯМЫЕ МЕТОДЫ дают решение задачи за конечное (точно определяемое для каждого метода) число операций. Здесь намеренно не употребляется термин «точные методы», так как из-за ошибок округления при вычислениях с конечным числом знаков решение всегда получается с погрешностями. Причины этого и способы уменьшения влияния ошибок округления будут обсуждены ниже. Из прямых методов будут рассмотрены метод Гаусса, метод Гаусса с выбором главного элемента для системы линейных алгебраических уравнений общего вида и метод прогонки для систем линейных уравнений с трехдиагональной матрицей.

ГАУСС КАРЛ ФРИДРИХ (Gaufi Carl Friedrich; 1777— 1855) — великий немецкий математик, которому также принадлежат работы по астрономии, физике, геодезии. Г. доказал основную теорему алгебры о существовании хотя бы одного корня у всякого алгебраического уравнения. Ему принадлежат важные работы по теории чисел, дифференциальной геометрии, теории вероятностей, теории бесконечных рядов. Вычисляя погрешности при измерениях, Г. предложил метод наименьших квадратов. Г. разработал теорию геодезических линий, построил первую квадратичную форму, доказал «славную» теорему (theoreme ergerium) об одинаковости меры кривизны (К) соответствующих точек поверхностей, совмещаемых путем изгибания. Отличительными чертами творчества Г. являются глубокая органическая связь в его исследованиях между теоретической и прикладной математикой и широта проблематики.

ИТЕРАЦИОННЫЕ МЕТОДЫ дают решение как предел бесконечной последовательности приближенных решений, в которых каждое последующее более точное приближение находится по уже найденному предыдущему решению (или предыдущим решениям). Из итерационных методов решения систем линейных алгебраических уравнений рассмотрены метод простой итерации и метод Зейделя.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >