- 29-

1. Численное решение линейных алгебраических систем (слау)

В этой главе рассматривается одна из самых важных задач линейной алгебры – решение систем линейных алгебраических уравнений, в которых число уравнений равно числу неизвестных:

или в сокращенной записи:

, .

Коэффициенты при неизвестныхобразуют матрицу системы

.

Всюду на протяжении этой главы мы будем считать определитель матрицы отличным от нуля

.

В этом случае система называется невырожденной. Решение невырожденной системы всегда существует и является единственным. Обсудим методы фактического построения этого решения.

1. Прямые методы решения слау.

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

1. Формулы Крамера

Формулы Крамера представляют компоненты решения системы в виде отношения двух определителей:

, ,

где

, .

Здесь матрица получается из матрацызаменой ее-го столбца столбцом правых частей системы

---

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

, так что .

При умеренном значении эта формула дает астрономическое число:

.

Компьютеру, производительность которого составляет операций/сек, для вычисления определителя двадцатого порядка понадобится время

сек.

В частности, при операций/сек получим

сек.лет.

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

Такие результаты получены при , в то время, как в современных прикладных задачах приходится решать системы си более уравнений. Из проведенного анализа ясно, что рассчитывать решение СЛАУ по формулам Крамера с вычислением определителей «в лоб» невозможно, т. е. практическая ценность этих формул невелика.

---

2. Метод Гаусса.

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

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

Разделим все члены первого уравнения на и введем в качестве новых коэффициентов и правой части отношения

,.

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

.

Значения новых коэффициентов и правых частей системы вычисляются по формулам:

,.

---

Естественно выделить из «укороченную» систему, содержащую уравнение

Продолжая далее процесс исключения, после шага редуцируем исходную систему к виду:

или в матричной форме

,

где матрица является верхней треугольной матрицей с единицами на главной диагонали

.

Построение системы завершает прямой ход метода Гаусса.

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

Подсчитаем число арифметических операций, которое требуется выполнить при решении СЛАУ по методу Гаусса. Первый шаг прямого хода, согласно формулам и , требует делений исложений и умножений. Мы учитываем деления отдельно, поскольку для компьютера, как и для человека, это более сложная операция. Переходя последовательно отк, потом отки т.д. подсчитаем общее число арифметических операций на стадии прямого хода. Оно включает делений

,

сложений и умножений

.

Обратный ход, согласно формулам , вообще не требует деления, а необходимое число сложений и умножений подсчитывается по формуле

.

Сравнивая и с , мы видим, что обратный ход существенно проще прямого. Сумма и дает общее число сложений и умножений, необходимое для решения СЛАУ по методу Гаусса:

---

.

Оно не идет ни в какое сравнение с числом , которое требуют формулы Крамера при прямом вычислении определителей.

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

,

то роль ошибок округления в процессе вычислений будет нивелироваться.

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

---

Смотрите также файлы

• BOA462~1.doc

• 8.doc

• 7.doc

• 4.doc

• 15.doc