Лабораторная работа № 3

Тема: Численные методы решения систем линейных алгебраических уравнений (СЛАУ).

Теоретическое введение.

Системы линейных алгебраических уравнений.

Множество прикладных и чисто математических задач приво­дят к необходимости решения систем линейных алгебраических уравнений. Без преувеличения можно утверждать, что это одна из важнейших задач вычислительной математики. Значимость задачи породила целый ряд методов ее решения. Среди этих методов есть универсальные и специализированные (т.е. применимые лишь к системам, имеющим некоторые специ­альные свойства). Методы отличаются друг от друга эффективно­стью, требованиями к объемам машинной памяти (при реализа­ции на ЭВМ), закономерностями накопления ошибок в ходе рас­четов. Не существует одного метода, который можно было бы во всех случаях предпочесть всем остальным, и поэтому знакомство с несколькими методами является обязательным для квалифици­рованного вычислителя.

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

Итак, перед нами система п линейных алгебраических уравне­ний с п неизвестными:

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n=b₂ (3.1)

Ax=b.

Как обычно, полужирные прописные буквы обозначают мат­рицу, полужирные строчные — векторы-столбцы.

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

• метод определителей (метод Крамера), хорошо известный из курса алгебры;

• матричное решение: х = А^-1b (если известна обратная матри­ца);

• различные варианты метода исключения неизвестных (мето­да Гаусса).

Чаще всего точные методы реализуются на ЭВМ, и в процессе вычислений ошибки округления и погрешности арифметических действий неизбежны. В силу этого название “точный” не вполне соответствует существу дела (но является традиционным).

Практическое применение первых двух методов может оказаться неэффективным или вообще невозможным. Если попробовать ре­шать “в лоб” систему 15 линейных уравнений с 15 неизвестными с помощью формул Крамера, то придется вычислить 16 опреде­лителей порядка 15, что приведет к выполнению примерно 2•16•15! •14 умножений и сложений. Для выполнения этих вычис­лений на ЭВМ с быстродействием 10⁶ арифметических операций в секунду потребуется почти 10 недель непрерывной работы. С прак­тической точки зрения при достаточно больших размерах систе­мы матричное решение также является малопривлекательным, по­скольку задача нахождения обратной матрицы сама по себе не проще задачи решения системы.

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