Итак, метод Гаусса применим к любой системе линейных уравнений, он идеально подходит для решения систем, содержащих больше трех линейных уравнений. Метод Гаусса решения СЛАУ с числовыми коэффициентами в силу простоты и однотипности выполняемых операций пригоден для счета на электронно-вычислительных машинах.
Достоинства метода:
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 .
Одним из простейших способов решения системы линейных уравнений является прием, основанный на вычислении определителей (правило Крамера ). Его преимущество состоит в том, что он позволяет сразу провести запись решения, особенно он удобен в тех случаях, когда коэффициенты системы являются не числами, а какими-то параметрами. Его недостаток – громоздкость вычислений в случае большого числа уравнений, к тому же правило Крамера непосредственно не применимо к системам, у которых число уравнений не совпадает с числом неизвестных. В таких случаях обычно применяют метод Гаусса .
Системы линейных уравнений, имеющие одно и то же множество решений, называются эквивалентными . Очевидно, что множество решений линейной системы не изменится, если какие-либо уравнения поменять местами, или умножить одно из уравнений на какое-либо ненулевое число, или если одно уравнение прибавить к другому.
Метод Гаусса (метод последовательного исключения неизвестных ) заключается в том, что с помощью элементарных преобразований система приводится к эквивалентной системе ступенчатого вида. Сначала с помощью 1-го уравнения исключается x 1 из всех последующих уравнений системы. Затем с помощью2-го уравнения исключается x 2 из 3-го и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса , продолжается до тех пор, пока в левой части последнего уравнения останется только одно неизвестное x n . После этого производится обратный ход метода Гаусса – решая последнее уравнение, находим x n ; после этого, используя это значение, из предпоследнего уравнения вычисляем x n –1 и т.д. Последним находим x 1 из первого уравнения.
Преобразования Гаусса удобно проводить, осуществляя преобразования не с самими уравнениями, а с матрицами их коэффициентов. Рассмотрим матрицу:
называемую расширенной матрицей системы, ибо в нее, кроме основной матрицы системы, включен столбец свободных членов. Метод Гаусса основан на приведении основной матрицы системы к треугольному виду (или трапециевидному виду в случае неквадратных систем) при помощи элементарных преобразованиях строк (!) расширенной матрицы системы.
Пример 5.1. Решить систему методом Гаусса:
Решение . Выпишем расширенную матрицу системы и, используя первую строку, после этого будем обнулять остальные элементы:
получим нули во 2-й, 3-й и 4-й строках первого столбца:
Теперь нужно чтобы все элементы во втором столбце ниже 2-й строки были равны нулю. Для этого можно умножить вторую строку на –4/7 и прибавить к 3-й строке. Однако чтобы не иметь дело с дробями, создадим единицу во 2-й строке второго столбца и только
Теперь, чтобы получить треугольную матрицу, нужно обнулить элемент четвертой строки 3-го столбца, для этого можно умножить третью строку на 8/54 и прибавить ее к четвертой. Однако чтобы не иметь дело с дробями поменяем местами 3-ю и 4-ю строки и 3-й и 4-й столбец и только после этого произведем обнуление указанного элемента. Заметим, что при перестановке столбцов меняются местами, соответствующие переменные и об этом нужно помнить; другие элементарные преобразования со столбцами (сложение и умножение на число) производить нельзя!
Последняя упрощенная матрица соответствует системе уравнений, эквивалентной исходной:
Отсюда, используя обратный ход метода Гаусса, найдем из четвертого уравнения x 3 = –1; из третьего x 4 = –2, из второго x 2 = 2 и из первого уравнения x 1 = 1. В матричном виде ответ записывается в виде
Мы рассмотрели случай, когда система является определенной, т.е. когда имеется только одно решение. Посмотрим, что получится, если система несовместна или неопределенна.
Пример 5.2. Исследовать систему методом Гаусса:
Решение . Выписываем и преобразуем расширенную матрицу системы
Записываем упрощенную систему уравнений:
Здесь, в последнем уравнении получилось, что 0=4, т.е. противоречие. Следовательно, система не имеет решения, т.е. она несовместна . à
Пример 5.3. Исследовать и решить систему методом Гаусса:
Решение . Выписываем и преобразуем расширенную матрицу системы:
В результате преобразований, в последней строке получились одни нули. Это означает, что число уравнений уменьшилось на единицу:
Таким образом, после упрощений осталось два уравнения, а неизвестных четыре, т.е. два неизвестных "лишних". Пусть "лишними", или, как говорят, свободными переменными , будут x 3 и x 4 . Тогда
Полагая x 3 = 2a и x 4 = b , получим x 2 = 1–a и x 1 = 2b –a ; или в матричном виде
Записанное подобным образом решение называется общим , поскольку, придавая параметрам a и b различные значения, можно описать все возможные решения системы. à
Метод Гаусса – метод последовательного исключения неизвестных – заключается в том, что с помощью элементарных преобразований исходная система приводится к равносильной ей системе ступенчатого или треугольного вида, из которой последовательно, начиная с последних (по номеру), неизвестных находятся все остальные неизвестные. Дана система (1)
Начинаем осуществлять прямой ход . Считаем, что коэффициент а 11 ≠ 0; если же это не так, меняем местами уравнения.
Первый
шаг состоит в том, чтобы исключить
неизвестное х
1
из всех уравнений, кроме первого. Для
этого ко второму уравнению прибавим
первое уравнение, умноженное на число
,
к третьему уравнению прибавим первое
уравнение, умноженное на число
,
и так далее до последнего уравнения.
После первого шага получим систему:
Полученная система равносильна исходной системе.
Вторым
шагом исключают неизвестное из всех
уравнений, кроме первого и второго. Для
этого повторяем все действия первого
шага для второго и последующих уравнений,
а именно: считаем, что коэффициент
≠ 0
и так далее. Если в результате преобразований
получается нулевое уравнение, то его
удаляют, если же получается несовместное
уравнение, то решение системы закончено
– она несовместна. Процесс исключения
неизвестных продолжаем до тех пор, пока
это возможно. Обозначим количество
уравнений, оставшихся после прямого
хода, через r
.
Это число равно рангу основной матрицы
системы и может быть меньше или равно
n
.
Рассмотрим оба случая.
1) Если r = n
где с 11 ≠ 0, с 22 ≠ 0, …, с nn ≠ 0.
Обратным
ходом
,
начиная с последнего уравнения,
последовательно найдем значения x
n
,
(где x
n
= 
),
x
n
– 1 ,
..., x
1 .
В этом случае система линейных уравнений
имеет единственное решение, то есть
является определенной.
2) Если r < n , то система после прямого хода принимает вид:
где с 11 ≠ 0, с 22 ≠ 0, …, с rr ≠ 0. Неизвестные x 1 , x 2 , …, x r , с которых начинаются уравнения, называются главными неизвестными , а остальные x r + 1 , x r + 2 , …, x n – свободными . В этом случае обратным ходом, начиная с последнего уравнения, выражают главные неизвестные через свободные неизвестные. Получают следующие равенства:
x 1 = k 1, r + 1 x r + 1 + … + k 1, n x n + t 1 ,
x 2 = k 2, r + 1 x r + 1 + … + k 2, n x n + t 2 ,
……………………………………..
x r = k r , r + 1 x r + 1 + … + k r , n x n + t r .
Определение 6.10. Общим решением системы называется выражение главных неизвестных через свободные.
Если свободным неизвестным придать какие-нибудь числовые значения, то из общего решения получим значения главных неизвестных. Таким образом, получают частное решение системы. Из способа его получения следует, что система имеет более одного решения, то есть является неопределенной.
Пример 6.3. Решить методом Гаусса систему линейных уравнений:
Решение
.
Преобразования
с системой линейных удобнее производить
не с самими уравнениями, а с матрицей
их коэффициентов. Расширенная матрица
этой системы имеет вид: (А
|B
) = 
.
Осуществляем
прямой ход. Первым шагом исключаем
неизвестное х
1
из всех уравнений, кроме первого. Так
как а
11 = 1 ≠ 0,
то переставлять уравнения местами не
нужно. Прибавим ко второму уравнению
системы первое уравнение, умноженное
на (–1), к третьему уравнению – первое,
умноженное на (–3). Получим после
преобразований следующую матрицу:
,
в которой элемент а
22 = 1.
Перестановка местами уравнений (первое
уравнение трогать не следует) не поможет,
поэтому переходим к следующему
неизвестному х
3
и исключаем его из всех уравнений, кроме
первого и второго. Для этого к третьему
уравнению прибавим второе, умноженное
на (–2) и вычеркнем получившееся нулевое
уравнение. После прямого хода получаем
следующую систему:
.
Прямой ход завершен. В этом случае n
= 4,
r
= 2,
r
< n
,
и, следовательно, система неопределенная.
Главные неизвестные – это те неизвестные,
с которых начинаются уравнения, в нашем
случае это х
1
и х
3 .
Неизвестные х
2
и х
4
– свободные.
Обратным
ходом надо выразить главные неизвестные
через свободные. Для этого в столбцах,
содержащих ведущие элементы строк,
следует получить нули. Здесь это элемент
а
13 .
Прибавим к первому уравнению, умноженному
на 2, второе и выпишем получившуюся
матрицу коэффициентов:
,
а затем и сами уравнения:
Из
этих уравнений получаем общее решение:
Найдем
какое-нибудь частное решение; пусть
х
2 = 3,
х
4 = 1,
тогда из общего решения получим значения
х
1 = 
,
и х
1 = –2.
Таким образом, частное решение – вектор
а
= (
,
3, –2, 1).
Ответ
:
общее решение {(
,
х
2 ,
,
х
4)},
где х
2 ,
х
4 R;
частное
решение, если х
2 = 3,
х
4 = 1,
то (
,
3, –2, 1).
Рассмотрим один из самых распространенных методов решения систем линейных алгебраических уравнений - метод Гаусса. Этот метод (который называют также методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.
Вычисления с помощью метода Гаусса состоят из двух основных этапов, называемых прямым ходом и обратным ходом (обратной подстановкой). Прямой ход метода Гаусса заключается в последовательном исключении неизвестных из системы (5.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.
В действительности причина состоит в использовании на шаге малого ведущего элемента Следствием этого стало появление большого
множителя и существенное возрастание коэффициента в последнем уравнении системы.
Таким образом, изложенный выше вариант метода Гаусса (схема единственного деления) оказался некорректным и, следовательно, непригодным для вычислений на ЭВМ. Этот метод может привести к аварийному останову (если при некотором и вычисления по нему могут оказаться неустойчивыми.
Описание метода. На шаге прямого хода коэффициенты уравнений системы с номерами преобразуются по формулам
Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей
В методе Гаусса с выбором главного элемента по столбцу гарантируется, что для всех к Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент а. при неизвестной в уравнениях с номерами Затем соответствующее выбранному коэффициенту уравнение с номером меняют местами с уравнением системы для того, чтобы главный элемент занял место коэффициента
После этой перестановки исключение неизвестного производят, как в схеме единственного деления.
Пример 5.9. Решим систему уравнений (5.39) методом Гаусса с выбором главного элемента по столбцу на -разрядной десятичной ЭВМ.
Прямой ход. 1-й шаг. Максимальный в первом столбце элемент матрицы находится в первой строке, поэтому перестановка уравнений не нужна. Здесь 1-й шаг проводится точно так же, как и в примере 5.8.
2-й шаг. Среди элементов матрицы системы (5.40) максимальный принадлежит третьему уравнению. Меняя местами второе и третье уравнения, получим систему
После вычисления последнее уравнение системы преобразуется к виду
Обратный ход. Из последнего уравнения находим Далее, имеем В данном случае ответ получился точным.
Заметим, что дополнительная работа по выбору главных элементов в схеме частичного выбора требует порядка действий, что практически не влияет на общую трудоемкость метода.
Вычислительная устойчивость схемы частичного выбора. Детальное исследование метода Гаусса показывает, что действительной причиной неустойчивости схемы единственного деления является возможность неограниченного роста элементов промежуточных матриц в процессе прямого хода. Так как на шаге схемы частичного выбора 1, то для вычисленных по формулам (5.42) элементов справедлива оценка Следовательно, максимальное по модулю значение элементов матрицы возрастает на одном шаге не более чем в 2 раза и в самом неблагоприятном случае шаг прямого хода даст коэффициент роста
Гарантия ограниченности роста элементов матрицы делает схему частичного выбора вычислительно устойчивой. Более того, для нее оказывается справедливой следующая оценка погрешности:
Здесь вычисленное на ЭВМ решение системы; его относительная погрешность; число обусловленности матрицы ем - машинное эпсилон; наконец, причем некоторая медленно растущая функция, зависящая от порядка системы (типа степенной функции с небольшим показателем), коэффициент роста.
Наличие в оценке (5.43) множителя указывает на то, что при большом схема частичного выбора может оказаться плохо обусловленной и возможна существенная потеря точности. Однако практика матричных вычислений показывает, что существенный рост элементов матрицы происходит крайне редко. В подавляющем большинстве случаев действительное значение коэффициента роста не превышает 8-10. Если система хорошо обусловлена, то погрешность вычисленного решения оказывается, как правило, малой.
Иногда для проверки качества приближенного решения х
вычисляют невязку и о степени близости приближенного решения к точному пытаются судить по тому, насколько мала невязка. Этот метод ненадежен по отношению к схеме частичного выбора, так как известно, что она гарантированно дает малые невдэки. Более точно это утверждение можно сформулировать так: справедлива оценка
где то же, что и в оценке (5.43). Заметим, что в неравенство (5.44) не входит число обусловленности.
В этой схеме допускается нарушение естественного порядка исключения неизвестных.
На 1-м шаге метода среди элементов определяют максимальный по модулю элемент Первое уравнение системы и уравнение с номером меняют местами. Далее стандартным образом производят исключение неизвестного х, из всех уравнений, кроме первого. (что значительно меньше соответствующего значения для схемы частичного выбора). Подчеркнем, что до сих пор еще не найдено матрицы, для которой полный выбор дал бы значение Таким образом, для хорошо обусловленных систем этот вариант метода Гаусса является хорошо обусловленным.
Однако гарантия хорошей обусловленности достигается здесь ценой значительных затрат на выбор главных элементов. Для этого дополнительно к арифметических действий требуется произвести примерно операций сравнения, что может ощутимо замедлить процесс решения задачи на ЭВМ. Поэтому в большинстве случаев на практике предпочтение отдается все же схеме частичного выбора. Как уже отмечено, ситуации, когда при использовании этого варианта метода Гаусса происходит существенный рост элементов, встречаются чрезвычайно редко. Более того, эти ситуации могут быть легко выявлены с помощью заложенных в современных программах эффективных методов слежения за ростом элементов матриц.
Известно, что для некоторых классов матриц при использовании схемы единственного деления главные элементы гарантированно располагаются на главной диагонали и потому применять частичный выбор нет необходимости. Так, например, обстоит дело для систем с положительно определенными матрицами, а также с матрицами, обладающими следующим свойством диагонального преобладания:
Матрицы, удовлетворяющие условию (5.45), таковы, что в каждой из строк модуль элемента расположенного на главной диагонали, больше суммы модулей всех остальных элементов строки.
Перед началом решения целесообразно масштабировать систему так, чтобы ее коэффициенты были величинами порядка единицы.
Существуют два естественных способа масштабирования системы Первый заключается в умножении каждого из уравнений на некоторый масштабирующий множитель Второй состоит в умножении на масштабирующий множитель каждого столбца матрицы, что соответствует замене переменных (фактически - это замена единиц измерения). В реальных ситуациях чаще всего масштабирование может быть выполнено без существенных трудностей. Однако подчеркнем, что в общем случае удовлетворительного способа масштабирования пока не найдено.
На практике масштабирование обычно производят с помощью деления каждого уравнения на его наибольший по модулю коэффициент. Это вполне удовлетворительный способ для большинства реально встречающихся задач.
(СЛАУ), состоящая из уравнений с неизвестными:
Предполагается, что существует единственное решение системы, то есть .
В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности.
Процесс решения системы линейных уравнений
по методу Гаусса состоит из 2х этапов:
1. Предполагаем, что . Тогда первое уравнение системы делим на коэффициент , в результате получаем уравнение . Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент . В результате система преобразуются к виду: 2. В предположении, что , делим второе уравнение на коэффициент и исключаем неизвестное из всех последующих уравнений и т.д. 3. Получаем систему уравнений с треугольной матрицей:Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные (матрица и правая часть уравнения - ) заданы точно и вычисление ведется без округлений. Для получения решения требуется умножений и делений, то есть порядка операций.
Условия, при которых метод выдает точное решение, на практике не выполнимы - неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой рассмотрим возмущенную систему:
Пусть введена некоторая норма . - называется числом обусловленности матрицы .
Возможны 3 случая:
Число обусловленности матрицы всегда . Если оно велико () , то говорят, что матрица плохо обусловлена. В этом случае малые возмущения правых частей системы , вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления, существенно влияют на решение системы. Грубо говоря, если погрешность правых частей , то погрешность решения будет .
Проиллюстрируем полученные результаты на следующем числовом примере: Дана система
Она имеет решение .
Теперь рассмотрим возмущенную систему:
Решением такой системы будет вектор .
При совсем малом возмущении правой части получили несоизмеримо большое возмущение решения. Объяснить такую "ненадежность" решения можно тем, что матрица почти вырожденная: прямые, соответствующие двум уравнениям, почти совпадают, что видно на графике:
Такой результат можно было предвидеть в силу плохой обусловленностью матрицы :
Вычисление является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы.
Составляем контрольный столбец , состоящий из контрольных элементов системы:
При преобразовании уравнений над контрольными элементами производятся те же операции, что и над свободными членами уравнеий. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности.
2) Относительная погрешность известного решения позволяет без существенных дополнительных затрат получить суждение о погрешности решения.
Задается некоторый ветор с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения . Вычисляется вектор , и на ряду с исходной системой уравнения решается система .
Пусть и - реально получаемые решения этих систем. Суждение о погрешности искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины и , отличаются не в очень большое число раз.
3) Изменение масштабов - прием, применяющийся для получения представления о реальной величине погрешности, возникающей за счет округлений при вычислениях.
Наряду с исходной системой тем же методом решается система
, где и - числаЕсли бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: . Поэтому при и , не являющихся степенями двойки, сравнение векторов и дает представление о величине вычислительной погрешности
Рассмотренные ниже модификации метода Гаусса позволяют уменьшить погрешность результата.
Основное увеличение ошибки в методе происходит во время прямого хода, когда ведущая -я строка умножается на коэффициенты .Если коэффициенты 1%20" alt=" >1 ">, то ошибки, полученные на предыдущих шагах накапливаются. Чтобы этого избежать, применяется модификация метода Гаусса с выбором главного элемента. На каждом шаге к обычной схеме добавляется выбор максимального элемента по столбцу следующим образом:
Пусть по ходу исключения неизвестных получена система уравнений:
, .Найдем такое , что и поменяем местами -е и -е уровнения.
Такое преобразование во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях.
Если есть подозрение, что полученное решение сильно искажено, то можно улучшить результат следующим образом. Величина называется невязкой. Погрешность удовлетворяет системе уравнений
.Решая эту систему, получаем приближение к и полагаем
.Если точность данного приближения неудовлетворительна, то повторяем эту операцию.
Процесс можно продолжать до тех пор, пока все компоненты не станут достаточно малыми. При этом нельзя останавливать вычисления только потому, что все компоненты вектора невязки стали достаточно малыми: это может быть результатом плохой обусловленности матрицы коэффициентов.
Рассмотрим для примера матрицу Вандермонда размером 7х7 и 2 различные правые части:
Данные системы были решены двумя способами. Тип данных - float. B итоге получили следующие результаты:
| Обычный метод | |||
|---|---|---|---|
| 1 | 2 | ||
| 1 | 2 | 1 | 2 |
| 0.999991 | 1 | 0.999996 | 1 |
| 1.00019 | 1 | 7.4774e-005 | 2,33e-008 |
| 0.998404 | 1 | 0.999375 | 1 |
| 1.00667 | 1 | 0.00263727 | 1,12e-006 |
| 0.985328 | 1 | 0.994149 | 1 |
| 1.01588 | 1 | 0.00637817 | 3,27e-006 |
| 0.993538 | 1 | 0.99739 | 1 |
| 0,045479 | 2,9826e-006 | 0,01818 | 8,8362e-006 |
| 0,006497 | 4,2608e-007 | 0,0045451 | 2,209e-006 |
| 0,040152 | 4,344e-005 | 0,083938 | 2,8654e-006 |
| С выбором ведущего элемента по строке | |||
|---|---|---|---|
| 1 | 2 | ||
| 1 | 2 | 1 | 2 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | -3.57628e-005 | 1,836e-007 |
| 1.00001 | 1 | 1.00031 | 1 |
| 0.999942 | 1 | -0.00133276 | 7,16e-006 |
| 1.00005 | 1 | 1.00302 | 0,99998 |
| 1.00009 | 1 | -0.0033505 | 1,8e-005 |
| 0.99991 | 1 | 1.00139 | 0,99999 |
| 0,000298 | 4,3835e-007 | 0,009439 | 5,0683e-005 |
| 4,2571e-005 | 6,2622e-008 | 0,0023542 | 1,2671e-005 |
| 0,010622 | 9,8016e-007 | 0,29402 | 1,4768e-006 |
