Помощь по Теле2, тарифы, вопросы

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

Метод Гаусса

Метод Гаусса – наиболее универсальный метод решения СЛАУ (за исключением ну уж очень больших систем). В отличие от рассмотренного ранее , он подходит не только для систем, имеющих единственное решение, но и для систем, у которых решений бесконечное множество. Здесь возможны три варианта.

1. Система имеет единственное решение (определитель главной матрицы системы не равен нулю);
2. Система имеет бесконечное множество решений;
3. Решений нет, система несовместна.

Итак, у нас есть система (пусть у нее будет одно решение), и мы собираемся решать ее методом Гаусса. Как это работает?

Метод Гаусса состоит из двух этапов – прямого и обратного.

Прямой ход метода Гаусса

Сначала запишем расширенную матрицу системы. Для этого в главную матрицу добавляем столбец свободных членов.

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

Что можно делать:

1. Можно переставлять строки матрицы местами;
2. Если в матрице есть одинаковые (или пропорциональные) строки, можно удалить их все, кроме одной;
3. Можно умножать или делить строку на любое число (кроме нуля);
4. Нулевые строки удаляются;
5. Можно прибавлять к строке строку, умноженную на число, отличное от нуля.

Обратный ход метода Гаусса

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

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

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

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

Сначала запишем расширенную матрицу:

Теперь займемся преобразованиями. Помним, что нам нужно добиться треугольного вида матрицы. Умножим 1-ую строку на (3). Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой и получим:

Затем умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Умножим 1-ую строку на (6). Умножим 2-ую строку на (13). Добавим 2-ую строку к 1-ой:

Вуаля - система приведена к соответствующему виду. Осталось найти неизвестные:

Система в данном примере имеет единственное решение. Решение систем с бесконечным множеством решений мы рассмотрим в отдельной статье. Возможно, сначала Вы не будете знать, с чего начать преобразования матрицы, но после соответствующей практики набъете руку и будете щелкать СЛАУ методом Гаусса как орешки. А если Вы вдруг столкнетесь со СЛАУ, которая окажется слишком крепким орешком, обращайтесь к нашим авторам! вы можете, оставив заявку в Заочнике. Вместе мы решим любую задачу!

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

Достоинства метода:

a) менее трудоёмкий по сравнению с другими методами;

b) позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение;

c) позволяет найти максимальное число линейно независимых уравнений - ранг матрицы системы.

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

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:

a) нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: , после чего приводится к виду единичной матрицы методом Гаусса-Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица:);

b) определения ранга матрицы (согласно следствию из теоремы Кронекера-Капелли ранг матрицы равен числу её главных переменных);

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

Существуют и другие методы решения и исследования систем линейных уравнений, которые лишены отмеченных недостатков. Эти методы основаны на теории матриц и определителей.

Комбинаторика.

Сколькими способами трое мальчиков - Алмас, Болат, Сабыр - могут стоять в одном ряду? - Это не трудно, напишем все возможные случаи (комбинации): АБС, АСБ, БАС, БСА, САБ, СБА. Всего шесть комбинаций.

Допустим к ним присоединился еще один мальчик Даурен. Каковы будут способы расположения в этом случае? В возможных шести случаях Даурен может стоять первым, вторым, третьим и последним:

ДАБС, ДАСБ, ДБАС, ДБСА, ДСАБ, ДСБА;
АДБС, АДСБ, БДАС, БДСА, СДАБ, СДБА;
АБДС, АСДБ, БАДС, БСДА, САДБ, СБДА;
АБСД, АСБД, БАСД, БСАД, САБД, СБАД.

Всего 24 разных способов. А если еще увеличить количество детей? Каждый раз писать и выводить общее количество трудно. Нам нужно определить число способов, а не виды способов. Нет ли других методов для определение этого число? - Есть. И в теории вероятностей нас больше интересует количество способов расположения, чем виды расположения. Раздел математики, называемый комбинаторикой, дает возможность сразу определить количество таких способов. Ознакомимся с основными понятиями комбинаторики, необходимыми для решения задач теории вероятностей. Это - перестановка, размещение и сочетания. Остановимся на каждом в отдельности.

1. Перестановка. Рассмотрим число случаев в предыдущей задаче. Мы переставили местами буквы А, Б, С и посчитали число всевозможных комбинаций, оно равнялось 6. А когда число мальчиков увеличилось на единицу, переставь местами буквы А, Б, С, Д, мы нашли число всевозможных комбинаций, оно равнялось 24.

ОПРЕДЕЛЕНИЕ. Перестановкой из n различных элементов называются комбинации, которые состоят из n элементов и отличаются друг от друга только порядком их расположения.

Число перестановок из n различных элементов обозначают P n и подсчитывают по формуле:

здесь n! (читается "эн факториал") означает произведение всех натуральных чисел от 1 до n:

Понятно, что один факториал равен единице, 1! = 1, вместе с этим, в математике принято считать что и ноль факториал равен единице. И так 0! = 1.

Вернемся к примеру. Здесь n=3. Следовательно, можно найти искомое число перестановок по формуле (1): P 3 =3!=1 2 3=6. Аналогично, число перестановок из четырех букв равно: P 4 =4!=1 2 3 4=24

Пример 7. Найдем значение выражения с факториалами 8!/6! 2!

Сначала преобразуем 8!=1 2 3 4 5 6 7 8=6! 7 8

Это преобразование подставим в выражение и упростим. 8!/6! 2=6! 7 8/6! 2=7 8/2=28

2. Размещения. Рассмотрим пример. Сколько двузначных чисел (цифры не повторяются) можно записать с помощью цифр 7, 8, 9. Это можно сделать в двух этапах: первый этап - определение количество подбора разрядов десятков числа, он равен 3 (любая из данных 3 цифр может занять разряд десятков); второй этап - определение количество подбора разрядов единиц числа, он равен 2 (любая цифра из оставшихся двух может занять разряд единиц). По правилу умножения из трех чисел можно составить всего 3 2=6 различных двузначных чисел. Действительно, можно в этом убедиться непосредственно записывая эти числа 78, 79, 87, 89, 97, 98, При решении задачи мы расположили по два элемента из трех, причем эти комбинации отличаются либо составом (78, 98), либо порядком их расположения (78, 87).

ОПРЕДЕЛЕНИЕ. Размещением из n элементов по m элементов (m n) называются комбинации, состоящие из m элементов, взятых из данных n различных элементов, отличающихся друг от друга либо самими элементами, либо порядком их расположения.

Число размещений из n элементов по m элементов обозначают и читают так: "А из эн по эм". Чтобы найти используют формулу:

(15)

Рассмотрим еще один пример. В 5 классе изучают 10 предметов. Сколькими способами можно составить расписание, если в этот день должно быть 4 различных урока?

Чтобы найти число способов расположения 10-ти предметов по четыре предмета, воспользуемся формулой (15) нахождения числа размещений из 10 элементов по 4 элемента:

Итак, 10 предметов по 4 предмета можно расположить 5040 различными способами.

3. Сочетания. Пример. Нужно составить произведения двух различных чисел из данных трех чисел 7, 8, 9.

Учитывая переместительное свойство умножения, имеем: 7 8=56, 7 9=63, 8 9=72. При решении задачи мы отобрали по два элемента из трех, причем эти комбинации отличаются только составом (78, 98), а их расположения не влияют на произведение.

ОПРЕДЕЛЕНИЕ. Сочетанием из n элементов по m элементов (m n) называются комбинации, состоящие из m элементов, взятых из данных n различных элементов, отличающиеся друг от друга только составом.

Число сочетаний из n элементов по m элементов обозначают и читают так: "це из эн по эм". Чтобы найти используют формулу:

(16)

В нашем примере n=3, а m=2. Тогда

Рассмотрим еще пример. В классе 25 учеников, из них 12 мальчиков. а) Нужно составить дежурство по два человека, причем пары должны состоят либо из мальчиков, либо из девочек. б) Сколько можно создать групп для дежурства, из двух мальчиков и одной девочки?

Решение. а) При решении этой задачи воспользуемся правилом сложения и формулой сочетания. Сначала посчитаем сколько пар можно создать из мальчиков (m 1) и из девочек (m 2), после найдем их сумму (m=m 1 +m 2).

Чтобы определить сколько пар можно создать из 12 мальчиков воспользуемся формулой для подсчета числа сочетаний из 12 элементов по 2 элемента

Из девочек можно создать 78 различных пар. Тогда по два мальчика и по две девочки всего можно создать m=66+78=144 различных пар.

б) При решении этой задачи воспользуемся правилом умножения и формулой сочетания. В группе два мальчика и одна девочка. Сначала посчитаем сколькими способами можно выбрать из 12 мальчиков по два мальчика (m 1) и из 13 девочек одну девочку (m 2), затем перемножим полученные результаты (m=m 1 m 2).
Из 12 мальчиков 2 мальчика можно выбрать 66 различными способами. А из 13 девочек 1 девочку можно выбрать следующим образом:

Тогда группу из двух мальчиков и из одной девочки можно создать m=66 13=856 различными способами.

Определение матрицы. Определители второго и третьего порядков, их основные свойства. Миноры и алгебраические дополнения, разложение определителя по строке (столбцу). Методы вычисления определителей. Понятие об определителе n-го порядка.

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

Обозначения: А – матрица, - элемент матрицы, номер строки, в которой стоит данный элемент, номер соответствующего столбца; m – число строк матрицы, n – число ее столбцов.

Определение 1.2 . Числа m и n называются размерностями матрицы.

Определение 1.3. Матрица называется квадратной , если m = n. Число n в этом случае называют порядком квадратной матрицы.

Каждой квадратной матрице можно поставить в соответствие число, определяемое единственным образом с использованием всех элементов матрицы. Это число называется определителем.

Определение 1.4. Определителем второго порядка называется число, полученное с помощью элементов квадратной матрицы 2-го порядка следующим образом:

.

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

1. 2.

Определение 1.5 . Определителем третьего порядка называется число, определяемое с помощью элементов квадратной матрицы 3-го порядка следующим образом:

А` , называемая транспонированной по отношению к матрице А , элементы которой связаны с элементамиА соотношением a` ij = a ji .

При решении системы уравнений

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

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

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

Недостаток модификации. Предположим х i найден с погрешностью D. Тогда при поиске какого-либо х s надо, согласно формуле обратного хода, умножать . При этом погрешность D также умножится на . Если значение велико, то погрешность возрастет.

Вывод: надо обеспечить, чтобы ведущий элемент был не просто большим, а самым большим по модулю в своей строке. Тогда при нормировке ведущей строки все прочие коэффициенты, согласно формуле (5), будут по модулю меньше 1, и ошибки будут уменьшаться .

Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные х i исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы .

Внимание. При такой замене меняется нумерация неизвестных x i . Чтобы обеспечить такую замену, надо при программировании ввести массив p 1 ,…p n с настоящими номерами неизвестных. В начале прямого хода все p i = i – обычная нумерация. После нахождения ведущего элемента меняем местами p k и p r . При обратном ходе по формуле (7) вычисляются перенумерованные x i . После вычисления всех неизвестных надо положить y]:=x[i] , и массив y[i] будет окончательным решением задачи.

Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, p k и p r , а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.

Применение метода Гаусса для решения различных задач линейной алгебры

1. Обращение матриц. Пусть необходимо вычислить обратную матрицу к квадратной матрице А. Обозначим Х = А –1 . Как известно АХ = I, где I – единичная матрица, в которой по диагонали расположены 1, а остальные элементы – 0. Иными словами, i-й столбец матрицы I равен

(1 стоит на i-м месте). Пусть х (i) – i-й столбец матрицы Х. Тогда, в силу правила умножения матриц (строка умножается на столбец) имеем А х (i) = e (i) . Значит, для обращения матрицы надо решить n систем линейных уравнений с одинаковыми матрицами и разными правыми частями:

Ах = е (1) ; Ах = е (2) ; …; Ах = е ( n ) . (2.1)

Решив эти системы, получим, что найденные решения х (1) , х (2) , …, х (n) являются столбцами матрицы А –1 .

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

1) переставляли строки или столбцы в зависимости от модификации метода;

2) делили ведущую строку на ненулевой ведущий элемент;

3) к строкам матрицы прибавляли ведущую строку, умноженную на некоторое число.

Как известно, при таких преобразованиях определитель матрицы претерпевает соответствующие изменения:

1) изменяет знак;

2) делится на тот же элемент;

3) не меняется.

После прямого хода матрица А будет приведена к верхнему треугольному виду с единицами на главной диагонали. Определитель такой матрицы равен, очевидно, 1. С учетом тех изменений, которые претерпевал определитель матрицы А в процессе преобразований, имеем следующую формулу:

det A = (–1) s × a 11 × a 22 ×…× a n n ,

где a j j – ведущие элементы, s – число перестановок строк и/или столбцов при поиске ведущих элементов.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Вручную реализовать метод Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) для данной системы уравнений

и выполнить следующие задания

1) Решить эту систему уравнений

2) Вычислить определитель матрицы данной системы (методом Гаусса – см. п 2 ).

3) Обратить матрицу этой системы (методом Гаусса – см. п 1 ).

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

2. Составить программу решения линейной системы методом Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) и выполнить обращение матриц с использованием этой программы.

Систему уравнений (1.1) представим в виде

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

Метод Гаусса можно интерпретировать как метод, в котором первоначально матрица приводится к верхней треугольной форме (прямой ход), а далее - к единичной (обратный ход). Очевидно, что если матрица единичная, то x t = b r

Пусть матрица системы (1.3) - верхняя треугольная, поэтому a tj = 0 при i > j, т. е. все элементы ниже главной диагонали равны нулю. Тогда из последнего уравнения сразу определяем х п. Подставляя х п в предпоследнее уравнение, находим х а _ х и т. д. Общие формулы имеют вид

При k > I коэффициенты а ы = 0.

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

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

Умножим k-ю строку на число с тк = т > k и вычтем

из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-ro столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется ПРЯМЫМ ХОДОМ МЕТОДА ГАУССА. Вычисление неизвестных по формулам (1.4) называют ОБРАТНЫМ ХОДОМ метода.

Обратный ход можно совершить иначе, если обратить в нуль и все коэффициенты, лежащие выше главной диагонали. Например, элементы п -го столбца обращаются в нуль, если ej^| умножить на (-a^V ax t = б| 2л) , где Ь^ п) - коэффициенты правой части i-го уравнения после указанных преобразований.

На некотором шаге прямого хода может оказаться, что коэффициент aj*" * 0, но мал по сравнению с остальными элементами матрицы системы и, в частности, мал по сравнению с элементами первого столбца. Деление коэффициентов системы на малую величину может привести к значительным ошибкам округления.

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

Для реализации метода требуется примерно п 3 /3 операций типа умножения и п 3 /3 операций типа сложения . Полезно помнить, что оценка числа операций определяется в основном операциями, затрачиваемыми при выполнении прямого хода метода Гаусса. Обратный ход метода Гаусса требует примерно п 2 операций. Следовательно, если требуется решить несколько систем линейных алгебраических уравнений вида Ах = b с одной и той же матрицей и различными правыми частями, то общее число операций при решении S систем будет оцениваться величиной (2/3)п 3 + Sn 2 . В этом случае целесообразно реализовать алгоритм метода Гаусса в виде двух подпрограмм: первая подпрограмма должна реализовывать прямой ход алгоритма и получать на выходе верхнюю треугольную матрицу, а вторая подпрограмма должна, используя полученную матрицу, вычислять решение системы для произвольной правой части.

Рассмотрим один из самых распространенных методов решения систем линейных алгебраических уравнений - метод Гаусса. Этот метод (который называют также методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

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

1. Схема единственного деления.

Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

Прямой ход состоит из шагов исключения.

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

Найдем величины

называемые множителями 1-ю шага. Вычтем последовательно из второго, третьего, уравнений системы (5.1) первое уравнение, умноженное соответственно на Это позволит обратить в

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

в которой вычисляются по формулам

2-й шаг. Целью этого шага является исключение неизвестного из уравнений с номерами Пусть где - коэффициент, называемый главным (или ведущим) элементом шага. Вычислим множители 2-го шага

и вычтем последовательно из третьего, четвертого, уравнений системы (5.30) второе уравнение, умноженное соответственно на . В результате получим систему

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

Аналогично проводятся остальные шаги. Опишем очередной шаг.

k-й шаг. В предположении, что главный (ведущий) элемент шага отличен от нуля, вычислим множители шага

и вычтем последовательно из уравнений полученной на предыдущем шаге системы уравнение, умноженное соответственно на

После шага исключения получим систему уравнений

матрица которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы (5.33) находим Подставляя найденное значение в предпоследнее уравнение, получим Осуществляя обратную подстановку, далее последовательно находим Вычисления неизвестных здесь проводятся по формулам

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

Вычисления 1-го шага исключения по формулам (5.29), (5.31) требуют выполнения деления, умножений и вычитаний, т. е. общее число арифметических операций составляет Аналогично, на шаге требуется операций, а на шаге - операций.

Подсчитаем теперь приближенно общее число арифметических операций прямого хода, считая размерность системы достаточно большой:

Как нетрудно видеть, для реализации обратного хода по формулам (5.34) нужно всего операций, что при больших пренебрежимо мало по сравнению с числом операций прямого хода.

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

Пример 5.7. Методом Гаусса решим систему

Прямой ход. 1-й шаг. Вычислим множители Вычитая из второго, третьего и четвертого уравнений системы (5.35) первое уравнение, умноженное на соответственно получим

2-й шаг. Вычислим множители Вычитая из третьего и четвертого уравнений системы (5.36) второе уравнение, умноженное на соответственно, приходим к системе

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

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

Результаты вычислений можно свести в следующую таблицу.

Таблица 5.2 (см. скан)

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

Пример 5.8. Используя метод Гаусса, решим систему уравнений

на -разрядной десятичной ЭВМ.

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

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

2-й шаг. После вычисления множителя последнее уравнение системы должно быть преобразовано к виду где Однако на используемой ЭВМ будет получено уравнение

Действительно, коэффициент определяется точно, так как при его вычислении не возникает чисел, мантиссы которых имеют более 6 разрядов. В то же время при вычислении умножение коэффициента 3.0001 на дает 7-разрядное число 105003.5, после округления которого до 6 разрядов получится 105004. Вычисление 62) завершается выполнением операции вычитания: . После округления последнего числа до 6 разрядов мантиссы приходим к уравнению (5.41).

Обратный ход. Из уравнения (5.41) находим и 1.00001. Сравнение с истинным значением показывает, что эта величина получена с очень высокой для используемой ЭВМ точностью. Дальнейшие вычисления дают

После округления имеем .

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

В чем же причина появления такой значительной погрешности? Говорить о накоплении ошибок округления не приходится, так как всего было выполнено 28 арифметических операций и лишь в 4 случаях потребовалось округление. Предположение о плохой обусловленности системы не подтверждается; вычисление дает значение и 100.

В действительности причина состоит в использовании на шаге малого ведущего элемента Следствием этого стало появление большого

множителя и существенное возрастание коэффициента в последнем уравнении системы.

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

2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора).

Описание метода. На шаге прямого хода коэффициенты уравнений системы с номерами преобразуются по формулам

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

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

После этой перестановки исключение неизвестного производят, как в схеме единственного деления.

Пример 5.9. Решим систему уравнений (5.39) методом Гаусса с выбором главного элемента по столбцу на -разрядной десятичной ЭВМ.

Прямой ход. 1-й шаг. Максимальный в первом столбце элемент матрицы находится в первой строке, поэтому перестановка уравнений не нужна. Здесь 1-й шаг проводится точно так же, как и в примере 5.8.

2-й шаг. Среди элементов матрицы системы (5.40) максимальный принадлежит третьему уравнению. Меняя местами второе и третье уравнения, получим систему

После вычисления последнее уравнение системы преобразуется к виду

Обратный ход. Из последнего уравнения находим Далее, имеем В данном случае ответ получился точным.

Заметим, что дополнительная работа по выбору главных элементов в схеме частичного выбора требует порядка действий, что практически не влияет на общую трудоемкость метода.

Вычислительная устойчивость схемы частичного выбора. Детальное исследование метода Гаусса показывает, что действительной причиной неустойчивости схемы единственного деления является возможность неограниченного роста элементов промежуточных матриц в процессе прямого хода. Так как на шаге схемы частичного выбора 1, то для вычисленных по формулам (5.42) элементов справедлива оценка Следовательно, максимальное по модулю значение элементов матрицы возрастает на одном шаге не более чем в 2 раза и в самом неблагоприятном случае шаг прямого хода даст коэффициент роста

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

Здесь вычисленное на ЭВМ решение системы; его относительная погрешность; число обусловленности матрицы ем - машинное эпсилон; наконец, причем некоторая медленно растущая функция, зависящая от порядка системы (типа степенной функции с небольшим показателем), коэффициент роста.

Наличие в оценке (5.43) множителя указывает на то, что при большом схема частичного выбора может оказаться плохо обусловленной и возможна существенная потеря точности. Однако практика матричных вычислений показывает, что существенный рост элементов матрицы происходит крайне редко. В подавляющем большинстве случаев действительное значение коэффициента роста не превышает 8-10. Если система хорошо обусловлена, то погрешность вычисленного решения оказывается, как правило, малой.

Иногда для проверки качества приближенного решения х

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

где то же, что и в оценке (5.43). Заметим, что в неравенство (5.44) не входит число обусловленности.

3. Метод Гаусса с выборок главного элемента по всей матрице (схема полного выбора).

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

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

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

4. Случаи, когда выбор главных элементов не нужен.

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

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

5. Масштабирование.

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

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

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