Если мы умножим какое-либо уравнение системы (1") на постоянное число и прибавим его к другому уравнению системы, то получим новую систему, эквивалентную прежней. Новая система уравнений будет иметь свою матрицу , соответствующим образом преобразованную из матрицы (). Преобразование заключается в том, что некоторая строка матрицы видоизменяется прибавлением к ней другой строки, умноженной на соответствующее число.
Подобным образом, если умножить какое-либо из уравнений системы на число , оставив остальные уравнения прежними, то получим новую систему, очевидно, эквивалентную исходной. Новая система будет иметь свою матрицу , соответствующим образом преобразованную из матрицы (). На этот раз преобразование заключается в том, что строка, соответствующая указанному уравнению, умножается на .
Появляется также необходимость переставлять местами два уравнения системы (1"), получив, таким образом, формально новую, но эквивалентную исходной систему. В этом случае преобразование сводится к перестановке местами двух строк матрицы .
Указанные три преобразования называют элементарными преобразованиями матрицы.
Технически, вместо того чтобы писать новую систему уравнений, ограничиваются тем, что пишут только соответствующую ей матрицу . Всегда можно, применяя подходящим образом элементарные операции над системой уравнений или, что все равно, над матрицей , добиться либо решения заданной системы (1"), либо прийти к явно противоречивой системе. Так как последняя эквивалентна системе (1"), то это докажет противоречивость системы (1").
Ниже приводятся примеры применения этого метода.
Операция обозначает, что получается из посредством одной или нескольких элементарных преобразований.
Пример 7. Решить систему
Конечно, согласно теореме 1, мы могли бы просчитать все пять определителей четвертого порядка и найти . Здесь было бы много повторяющихся вычислений.
Составим матрицу :
,
где, как мы видим, последний столбец состоит из правых частей нашей системы. Умножая первую строку на (-1) и прибавляя ее к третьей и четвертой строкам, получим матрицу
.
В матрице элементы третьей строки, являющиеся коэффициентами при неизвестных, кроме одного, равны нулю. Переместим эту строку на место второй строки. Тогда элемент, не равный нулю, окажется на главной диагонали:
.
Вторую строку можно еще умножить на (-1), чтобы запись была проще:
.
Дальнейшие преобразования матриц очевидны:
Отсюда , , , . Чтобы не допустить ошибки, рекомендуется осуществить проверку, подставив полученные значения в исходные уравнения системы.
Метод Гаусса – это просто! Почему? Известный немецкий математик Иоганн Карл Фридрих Гаусс еще при жизни получил признание величайшего математика всех времен, гения и даже прозвище «короля математики». А всё гениальное – просто! Кстати, портрет Гаусса красовался на купюре в 10 дойчмарок (до введения евро), и до сих пор Гаусс загадочно улыбается немцам с обычных почтовых марок.
Метод Гаусса прост тем, что для его освоения ДОСТАТОЧНО ЗНАНИЙ ПЯТИКЛАССНИКА. Про миноры и алгебраические дополнения можно на время забыть! Необходимо уметь складывать и умножать! Не случайно метод последовательного исключения неизвестных преподаватели часто рассматривают на школьных математических факультативах.
Парадокс, но у студентов метод Гаусса вызывает наибольшие сложности. Ничего удивительного – всё дело в методике, и мы постараемся в доступной форме рассказать об алгоритме метода.
Сначала немного систематизируем знания о системах линейных уравнений. Система линейных уравнений может:
1) Иметь единственное решение.
2) Иметь бесконечно много решений.
3) Не иметь решений (быть несовместной ).
Метод Гаусса – наиболее мощный и универсальный инструмент для нахождения решения любой системы линейных уравнений. Как мы помним, правило Крамера и матричный метод непригодны в тех случаях, когда система имеет бесконечно много решений или несовместна. А метод последовательного исключения неизвестных в любом случае приведет нас к ответу! На данном уроке мы вновь рассмотрим метод Гаусса для случая №1 (единственное решение системы), под ситуации пунктов №№ 2-3 отведена статья Несовместные системы и системы с общим решением. Заметим, что сам алгоритм метода во всех трёх случаях работает одинаково.
Вернемся к простейшей системе
И решим ее методом Гаусса.
На первом этапе запишем так называемую расширенную матрицу системы :
По какому принципу записаны коэффициенты, думаем, всем видно.
Примечание: Расширенная матрица системы получается из исходной с помощью «операции наращивания строк / столбцов». В данном случае матрицу нарастили за счёт столбца свободных членов исходной системы уравнений.
Примечание: Кроме перечисленных ранее 6-и алгебраических операций с матрицами и «операции наращивания» существует ещё «операция отбрасывания строк/столбцов». С помощью «операции отбрасывания строк/столбцов» составляют, например, подматрицы, определители которых являются минорами элементов матрицы.
Вертикальная черта внутри матрицы не несёт никакого математического смысла – это просто линия отчёркивания для удобства оформления.
Определение: Матрица системы – это матрица, составленная только из коэффициентов при неизвестных переменных системы линейных уравнений.
Определение: Расширенная матрица системы – это матрица системы, которую нарастили справа на столбец свободных членов.
В данном примере . – это матрица системы, а - это расширенная матрица системы. Любую из них можно для краткости называть просто матрицей.
После того, как записана расширенная матрица системы, с ней необходимо выполнить некоторые новые алгебраические действия, которые с лёгкой руки Гаусса называются также элементарными преобразованиями матрицы . Преобразования называют элементарными , потому что показано (будем считать это определением), что
Определение: После каждого элементарного преобразования расширенной матрицы получается совершенно другая матрица, но решения для этой новой системы линейных уравнений остаются теми же, что и для исходной матрицы .
Существуют следующие элементарные преобразования:
1) Строки матрицы можно переставлять местами. Например, в рассматриваемой матрице можно безболезненно переставить первую и вторую строки:
2) Если в матрице есть (или появились) пропорциональные (как частный случай – одинаковые) строки, то следует удалить из матрицы все эти строки кроме одной.
Рассмотрим, например матрицу 
. В данной матрице последние три строки пропорциональны, поэтому достаточно оставить только одну из них:
.
3) Если в матрице в ходе преобразований появилась нулевая строка, то ее также следует удалить . Рисовать не будем, понятно, нулевая строка – это строка, в которой одни нули .
4) Строку матрицы можно умножить (разделить)
на любое число, отличное от нуля
. Рассмотрим, например, матрицу . Здесь целесообразно первую строку разделить на –3, а вторую строку – умножить на 2: 
. Данное действие очень полезно, поскольку упрощает дальнейшие преобразования матрицы.
5) Это преобразование вызывает наибольшие затруднения, но на самом деле ничего сложного тоже нет. К строке матрицы можно прибавить другую строку, умноженную на число , отличное от нуля.
Рассмотрим нашу матрицу из практического примера: . Сначала распишем преобразование очень подробно.
Умножаем первую строку на (-2): 
, далее ко второй строке прибавляем первую строку, оставляя первую без изменений
: 
. Теперь первую строку можно разделить «обратно» на (–2): .
Как видите, строка, которую ПРИБАВЛЯЛИ – не изменилась . Всегда меняется строка, К КОТОРОЙ ПРИБАВЛЯЮТ .
На практике так подробно, конечно, не расписывают, а пишут короче:
Еще раз: ко второй строке прибавили первую строку, умноженную на (–2) . Умножают строку обычно устно или на черновике, при этом мысленный ход расчётов примерно такой:
«Переписываю матрицу и переписываю первую строку: 
»
«Сначала первый столбец. Внизу мне нужно получить ноль. Поэтому единицу вверху умножаю на –2: , и ко второй строке прибавляю первую: 2 + (–2) = 0.
Записываю результат во вторую строку: 
»
«Теперь второй столбец. Вверху –1 умножаю на –2: (-1∙(-2) = 2 ). Ко второй строке прибавляю первую: 1 + 2 = 3. Записываю результат во вторую строку:
»
«И третий столбец. Вверху –5 умножаю на –2: (-5∙(-2) = 10 ). Ко второй строке прибавляю первую: (–7 + 10 = 3 ). Записываю результат во вторую строку:
»
Пожалуйста, тщательно осмыслите этот пример и разберитесь в последовательном алгоритме вычислений, если вы это поняли, то метод Гаусса практически «в кармане». Но, конечно, над этим преобразованием мы еще поработаем.
Повторим: «Элементарные преобразования не изменяют решение системы»
ВНИМАНИЕ!: рассмотренные манипуляции нельзя использовать , если Вам предложено задание, где матрицы даны «сами по себе». Например, при «классических» действиях с матрицами что-то переставлять внутри матриц ни в коем случае нельзя!
Вернемся к нашей системе . Она уже почти решена.
Что просит Гаусс? Он говорит: «Запишите расширенную матрицу системы и с помощью элементарных преобразований приведите ее к ступенчатому виду ».
В данном случае для этого
(1) Ко второй строке прибавьте первую строку, умноженную на –2. Кстати, почему первую строку умножаем именно на –2? Для того чтобы внизу получить ноль, а значит, избавиться от одной переменной во второй строке.
(2) Разделите вторую строку на 3. Почему? Чтобы вторая строка давала сразу значение второй переменной.
Цель элементарных преобразований – привести матрицу к ступенчатому виду:
В оформлении задания прямо так и отчеркивают простым карандашом «лестницу», а также обводят кружочками числа, которые располагаются на «ступеньках». Сам термин «ступенчатый вид» не вполне теоретический, в научной и учебной литературе он часто называется трапециевидный вид или треугольный вид .
В результате элементарных преобразований получена система уравнений, эквивалентная исходной системе линейных уравнений, которая приняла вид:
Теперь систему нужно «раскрутить» в обратном направлении – снизу вверх, этот процесс называется обратным ходом метода Гаусса .
В нижнем уравнении у нас уже готовый результат: . Рассмотрим первое уравнение системы и подставим в него уже известное значение «игрек»:
Ответ:
Рассмотрим наиболее распространенную ситуацию, когда методом Гаусса требуется решить систему трёх линейных уравнений с тремя неизвестными.
Пример 1
Решить методом Гаусса систему уравнений:
Запишем расширенную матрицу системы:
Сейчас мы сразу нарисуем результат, к которому мы придём в ходе решения:
.
Повторимся, что наша цель – с помощью элементарных преобразований привести матрицу к ступенчатому виду. С чего начать действия?
Сначала смотрим на левое верхнее число:
.
Почти всегда здесь должна находиться единица . Вообще говоря, устроит и (–1), а иногда и другие числа, но как-то так традиционно сложилось, что туда обычно помещают единицу. Как организовать единицу? Смотрим на первый столбец – готовая единица у нас есть! Преобразование первое: меняем местами первую и третью строки:
Теперь первая строка у нас останется неизменной до конца решения . Уже легче.
Единица в левом верхнем углу организована. Теперь нужно получить нули вот на этих местах:
Нули получаем как раз с помощью «трудного» преобразования. Сначала разбираемся со второй строкой (2, –1, 3, 13). Что нужно сделать, чтобы на первой позиции получить ноль? Нужно ко второй строке прибавить первую строку, умноженную на –2 . Мысленно или на черновике умножаем первую строку на –2: (–2, –4, 2, –18).
И последовательно проводим (опять же мысленно или на черновике) сложение, т. е. ко второй строке прибавляем первую строку, уже умноженную на –2 :
Результат записываем во вторую строку:
Аналогично разбираемся с третьей строкой (3, 2, –5, –1). Чтобы получить на первой позиции ноль, нужно к третьей строке прибавить первую строку, умноженную на –3 .
Мысленно или на черновике умножаем первую строку на –3: (–3, –6, 3, –27). И к третьей строке прибавляем первую строку, умноженную на –3 :
Результат записываем в третью строку:
На практике эти действия обычно выполняются устно и записываются в один шаг:
Не нужно считать всё сразу и одновременно . Порядок вычислений и «вписывания» результатов последователен и обычно такой: сначала переписываем первую строку, и пыхтим себе потихонечку – ПОСЛЕДОВАТЕЛЬНО иВНИМАТЕЛЬНО :
.
А мысленный ход самих расчётов мы уже рассмотрели выше.
В данном примере это сделать легко, вторую строку делим на –5 (поскольку там все числа делятся на 5 без остатка). Заодно делим третью строку на –2, ведь чем меньше числа, тем проще решение:
На заключительном этапе элементарных преобразований нужно получить еще один ноль здесь:
Для этого к третьей строке прибавляем вторую строку, умноженную на –2 :
Попробуйте разобрать это действие самостоятельно – мысленно умножьте вторую строку на (–2) и проведите сложение. Последнее выполненное действие – причёска результата, для этого делим третью строку на 3.
В результате элементарных преобразований получена система, эквивалентная исходной системе линейных уравнений:
Теперь в действие вступает «обратный ход» метода Гаусса. Уравнения «раскручиваются» снизу вверх.
В третьем уравнении у нас уже готовый результат:
Смотрим на второе уравнение: . Значение «зет» уже известно, таким образом:
Пример 3
Запишем расширенную матрицу системы и с помощью элементарных преобразований приведем ее к ступенчатому виду:
Смотрим на левую верхнюю «ступеньку». Там у нас должна быть единица. Проблема состоит в том, что в первом столбце единиц нет вообще, поэтому перестановкой строк ничего не решить. В таких случаях единицу нужно организовать с помощью элементарного преобразования. Обычно это можно сделать несколькими способами.
Поступим так:
(1) К первой строке прибавляем вторую строку, умноженную на (–1) . То есть, мысленно умножили вторую строку на (–1) и выполнили сложение первой и второй строки, при этом вторая строка у нас не изменилась.
Теперь слева вверху (–1), что нас вполне устроит. Кто хочет получить (+1), может выполнить дополнительное телодвижение: умножить первую строку на (–1), сменив у неё знак. Дальше алгоритм работает уже по накатанной колее:
.
(2) Ко второй строке прибавили первую строку, умноженную на 5. К третьей строке прибавили первую строку, умноженную на 3.
(3) Первую строку умножили на (–1). В принципе, это для красоты. У третьей строки также сменили знак и переставили её на второе место, таким образом, на второй «ступеньке у нас появилась нужная единица.
(4) К третьей строке прибавили вторую строку, умноженную на 2.
(5) Третью строку разделили на 3.
Заряжаем обратный ход, в оформлении примеров часто не переписывают саму систему, а уравнения «берут прямо из приведенной матрицы». Обратный ход, напоминаю, работает, снизу вверх. Да тут подарок получился:
Ответ:
.
Пример 4
Решить систему линейных уравнений методом Гаусса
Это пример для самостоятельного решения, он несколько сложнее. Ничего страшного, если кто-нибудь запутается. Полное решение и образец оформления в конце урока. Ваш ход решения может отличаться от нашего хода решения.
Раздел 3. Численные методы решения уравнений
Виды математических моделей (уравнений) в теории электрических цепей
1. - системы линейных алгебраических уравнений –
линейные цепи постоянного и синусоидального переменного (комплексный метод) тока.
2 . - системы нелинейных алгебраических или
трансцендентных уравнений – нелинейные цепи постоянного или синусоидального тока.
3. 
. –
системы нелинейных дифференциальных
уравнений первого порядка в обыкновенных производных – переходные процессы в нелинейных цепях.
Здесь F и ψ – вектор-функции, т.е. эквивалентно записи:
f 1 (X,b 1) = 0
f 2 (X,b 2) = 0
…………
f n (X,b n) = 0
а 
-
записи:
ψ 1 (dX/dt,X,b 1 ,t) = 0
ψ 2 (dX/dt,X,b 2 ,t) = 0
…………………..
ψ n (dX/dt,X,b n ,t) = 0
Рассмотрим наиболее эффективные методы решения этих уравнений.
Численные методы решения систем линейных алгебраических уравнений (ЛАУ)
Метод Гаусса (исключения неизвестных)
Методы решения ЛАУ имеют важное значение, так как они применяются (итерационно) для решения более сложных уравнений.
Пусть система ЛАУ задана в виде:
,
где - квадратная матрица n – го порядка с ненулевыми диагональными элементами ; - вектор неизвестных; - вектор правых частей.
Алгоритм метода Гаусса состоит из прямого и обратного хода. Во время прямого хода осуществляется последовательное исключение неизвестных. Система приобретает вид:
Пересчет коэффициентов производится по формуле:
, где i, j = k+1, …n
при исключение k
-го неизвестного.
При этом столбец правых частей удобно рассматривать как n + 1 столбец матрицы коэффициентов , т.е. j = k+1, …n+1.
Обратный ход заключается в определении неизвестных, начиная с последнего уравнения где осталась одна неизвестная x n . Полученное значение x n подставляется в предыдущее уравнение и определяется x n -1 и т.д.
Для произвольного x k получается следующая формула:
где k = n, n -1,…1.
Трудоемкость метода Гаусса оценивается количеством выполняемых арифметических операций:
.
Кубическая зависимость от размерности задачи существенно ограничивает сложность анализируемых цепей. Однако если часть коэффициентов a ik в матрице равна нулю, т.е. она является разреженной , то появляется возможность сокращения трудоемкости.
Основная идея метода разреженных матриц состоит в учете при вычислениях и хранении только ненулевых элементов матрицы . Степень разреженности матрицы характеризуется коэффициентом заполнения:
где n ннэ –число ненулевых элементов.
Существуют матрицы коэффициентов специального вида: ленточные, когда ненулевые элементы располагаются вдоль главной диагонали; и блочно-диагональные, когда вдоль главной диагонали располагаются ненулевые блоки. Еще встречаются блочно-диагональные с окаймлением.
Пример ленточной матрицы Пример блочно-диагональной матрицы
 |
Пример блочно-диагональной матрицы с окаймлением
Для них разработаны специальные эффективные методы решения. Для диагональной – метод прогонки . Блочная распадается на отдельные группы уравнений по блокам, которые решаются методом Гаусса. Для блочно-диагональных с окаймлением существуют диакоптические методы решения.
Диакоптика – подход к исследованию сложных систем, заключающейся в расчленение системы на части и её анализе по частям при учете всех связей между выделенными частями.
Рассмотрим систему m линейных уравнений с n неизвестными
Элементарными преобразованиями системы (4.12) называют:
Очевидно, что элементарные преобразования переводят линейную систему в эквивалентную.
Ступенчатой системой называется система линейных уравнений вида
| (4.13) |
где . Коэффициенты a ii называются главными , или ведущими , элементами системы. Например, система
Имеет ступенчатый вид.
Если в системе (4.13) k = n , то ее называют треугольной . Очевидно, что в этом случае она является определенной.
Если k < n , то k неизвестных х 1 , х 2 , ..., х к , называют главными элементами . Они могут быть выражены через остальные n – k неизвестные, называемые свободными . В этом случае система (4.13) будет называться неопределенной .
Вернемся к произвольной системе (4.12) и для определенности будем считать, что . Если это не так, то тождественными линейными преобразованиями системы (4.12) можно всегда добиться выполнения данного условия. Исключим х 1 из всех уравнений, кроме первого. Для этого обе части первого уравнения умножим на a 21 /a 11 и вычтем из соответствующих частей второго уравнения. Затем обе части первого уравнения умножим на a 31 /a 11 и вычтем из соответствующих частей третьего. И так поступим с каждым следующим уравнением. Далее таким же образом исключаем х 2 из третьего, четвертого и так далее уравнений. В результате таких преобразований мы получим совместную ступенчатую систему или придем к несовместимой системе, в которой одно из уравнений имеет отличный от нуля свободный член, а все остальные коэффициенты левой части равны нулю. В последнем случае система (4.12) также будет несовместимой.
Пример 6 . Решить систему
Решение . Вычисления удобно записывать по так называемой схеме единственного деления, в которой оперируют с коэффициентами системы .
| X 1 | X 2 | X 3 | B | |
| 1 | 2 | 1 | 9 | 13 |
| 1 | 1 | 2 | 8 | 12 |
| 2 | 1 | 1 | 7 | 11 |
| 1 | 2 | 1 | 9 | 13 |
| 0 | -1 | 1 | -1 | -1 |
| 0 | -3 | -1 | 11 | 15 |
| 1 | 2 | 1 | 9 | 13 |
| 0 | -1 | 1 | -1 | -1 |
| 0 | 0 | -4 | -8 | -12 |
В результате получаем треугольную систему.
Рассмотрим точные методы решения системы ; здесь - матрица размерности
Метод решения задачи относят к классу точных, если в предположении отсутствия округлений он дает точное решение задачи после конечного числа арифметических и логических операций. Если число ненулевых элементов матрицы системы имеет порядок , то для большинства используемых в настоящее время точных методов решения таких систем требуемое число операций имеет порядок . Поэтому для применимости точных методов необходимо, чтобы такой порядок числа операций был приемлем для данной ЭВМ; другие ограничения накладываются объемом и структурой памяти ЭВМ.
Оговорка об «используемых в настоящее время методах» имеет следующий смысл. Существуют методы решения таких систем с меньшим порядком числа операций, однако они не используются активно из-за сильной чувствительности результата к вычислительной погрешности.
Наиболее известным из точных методов решения систем линейных уравнений является метод исключения Гаусса. Рассмотрим одну из его возможных реализаций. В предположении, что , первое уравнение системы
делим на коэффициент , в результате получаем уравнение
Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствующий коэффициент . В результате эти Уравнения преобразуются к виду
Первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Далее в предположении, что , делим второе уравнение на коэффициент и исключаем неизвестное из всех уравнений, начиная со второго, и т. д. В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с треугольной матрицей
Совокупность проведенных вычислений, в ходе которых исходная задача преобразовалась к виду (2), называется прямым ходом метода Гаусса.
Из уравнения системы (2) определяем , из и т. д. до . Совокупность таких вычислений называют обратным ходом метода Гаусса.
Нетрудно проверить, что реализация прямого хода метода Гаусса требует арифметических операций, а обратного - арифметических операций.
Исключение происходит в результате следующих операций: 1) деления уравнения на , 2) вычитания получающегося после такого деления уравнения, умноженного на , из уравнений с номерами к . Первая операция равносильна умножению системы уравнений слева на диагональную матрицу
вторая операция равносильна умножению слева на матрицу
Таким образом, система (2), получаемая в результате этих преобразований, запишется в виде
Произведение левых (правых) треугольных матриц является левой (правой) треугольной матрицей, поэтому матрица С левая треугольная. Из формулы для элементов обратной матрицы
следует, что матрица, обратная к левой (правой) треугольной, является левой (правой) треугольной. Следовательно, матрица левая треугольная.
Введем обозначение . Согласно построению все и матрица D правая треугольная. Отсюда получаем представление матрицы А в виде произведения левой и правой треугольных матриц:
Равенство вместе с условием , образует систему уравнений относительно элементов треугольных матриц В и : . Поскольку при и при , эта система может быть записана в виде
(3)
или, что то же самое,
Воспользовавшись условием, что все получаем систему рекуррентных соотношений для определения элементов и :
Вычисления проводятся последовательно для совокупностей . Здесь и далее в случае, когда верхний предел суммирования меньше нижнего, считается, что вся сумма равна нулю.
Таким образом, вместо последовательных преобразований системы (1) к виду (2) можно непосредственно произвести вычисление матриц В и с помощью формул (4). Эти вычисления можно осуществить, если только все элементы окажутся отличными от нуля. Пусть - матрицы главных миноров порядка матриц А, В, D. Согласно (3) . Поскольку , то . Следовательно,
Итак, для осуществления вычислений по формулам (4) необходимо и достаточно выполнение условий
В ряде случаев заранее известно, что условие (5) выполнено. Например, многие задачи математической физики сводятся к решению систем с положительно определенной матрицей А. Однако в общем случае этого заранее сказать нельзя. Возможен и такой случай: все , но среди величин есть очень малые и при делении на них будут получаться большие числа с большими абсолютными погрешностями. В результате этого решение сильно исказится.
Обозначим . Поскольку и , то справедливы равенства . Таким образом, после разложения матрицы исходной системы на произведение левой и правой треугольных матриц решение исходной системы сводится к последовательному решению двух систем с треугольными матрицами; это потребует арифметических операций.
Последовательность операций по разложению матрицы А на произведение треугольных матриц и по определению вектора d часто удобно объединить. Уравнения
системы можно записать в виде
Следовательно, значения могут вычисляться одновременно с остальными значениями по формулам (4).
При решении практических задач часто возникает необходимость решения систем уравнений с матрицей, содержащей большое количество нулевых элементов.
Обычно эти матрицы имеют так называемую ленточную структуру. Более точно, матрицу А называют -диагональной или имеющей ленточную структуру, если при . Число называют шириной ленты. Оказывается, что при решении системы уравнений с ленточной матрицей методом Гаусса число арифметических операций и требуемый объем памяти ЭВМ могут быть существенно сокращены.
Задача 1. Исследовать характеристики метода Гаусса и метода решения системы с помощью разложения ленточной матрицы А на произведение левой и правой треугольных матриц. Показать, что для нахождения решения требуется арифметических операций (при ). Найти главный член числа операций при условии .
Задача 2. Оценить объем загружаемой памяти ЭВМ в методе Гаусса для ленточных матриц.
При вычислениях без помощи ЭВМ велика вероятность случайных погрешностей. Для устранения таких погрешностей иногда вводят контрольный системы , состоящий из контрольных элементов уравнений системы
При преобразовании уравнений над контрольными элементами производятся те же операции, что и над свободными членами уравнений. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности.
К примеру, в случае приведения системы уравнений к виду с помощью формул (4) контрольный элемент каждого из уравнений системы вычисляется по тем же формулам (4). После вычисления всех элементов при фиксированном контроль осуществляется проверкой равенства
Обратный ход метода Гаусса также сопровождается вычислением контрольных элементов строк системы.
Чтобы избежать катастрофического влияния вычислительной погрешности, применяют метод Гаусса с выбором главного элемента.
Его отличие от описанной выше схемы метода Гаусса состоит в следующем. Пусть по ходу исключения неизвестных получена система уравнений
Найдем такое, что и переобозначим и ; далее произведем исключение неизвестной из всех уравнений, начиная с . Такое переобозначение приводит к изменению порядка исключения неизвестных и во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях.
Часто требуется решить несколько систем уравнений , с одной и той же матрицей А. Удобно поступить следующим образом: введя обозначения
произведем вычисления по формулам (4), причем элементы вычислим при . В результате будут получены р систем уравнений с треугольной матрицей, соответствующих исходной задаче
Решаем эти системы каждую в отдельности. Оказывается, что общее число арифметических действий при решении р систем уравнений таким способом .
Описанный выше прием иногда используется для того, чтобы без существенных дополнительных затрат получить суждение о погрешности решения, являющейся следствием погрешностей округления при вычислениях. Задаются вектором z с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения; часто из-за отсутствия достаточной информации берут . Вычисляется вектор , и наряду с исходной системой уравнений решается система .
Пусть и z - реально получаемые решения этих систем. Суждение о погрешности искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины и , отличаются не в очень большое число раз.
Другой прием для получения суждения о реальной величине погрешности, возникающей за счет округлений при вычислениях, состоит в изменении масштабов, меняющем картину накопления вычислительной погрешности.
Наряду с исходной системой тем же методом решается система
При и , не являющихся целыми степенями двойки, сравнение векторов и дает представление о величине вычислительной погрешности. Например, можно взять .
Изучение многих задач приводит к необходимости решения систем линейных уравнений с симметричной положительно определенной матрицей. Такие системы возникают, например, при решении дифференциальных уравнений методом конечных элементов или же конечно-разностными методами. В этих случаях матрица системы имеет также и ленточную структуру.
Для решения таких систем, а также систем уравнений более общего вида с эрмитовой не обязательно положительно определенной матрицей применяется метод квадратного корня (метод Холецкого). Матрица А представляется в виде
где S - правая треугольная матрица, - сопряженная с ней, т. е.
причем все - диагональная матрица с элементами , равными или -1. Матричное равенство (6) образует систему уравнений
Аналогичные уравнения при отброшены, так как уравнения, соответствующие парам и , эквивалентны. Отсюда получаем рекуррентные формулы для определения элементов и :
Матрица S является правой треугольной, и, таким образом, после получения представления (6) решение исходной системы также сводится к Последовательному решению двух систем с треугольными матрицами. Заметим, что в случае все и .
Задача 3. Оценить число арифметических операций и загрузку памяти ЭВМ (при условии объем памяти, требуемый для запоминания матрицы А, уменьшается) при решении системы с вещественной положительно определеннной матрицей А методом квадратного корня.
Многие пакеты прикладных программ для решения краевых задач математической физики методом конечных элементов организованы по следующей схеме. После формирования матрицы системы А путем перестановки строк и столбцов (одновременно переставляются и строки и и столбцы) система преобразуется к виду с наименьшей шириной ленты. Далее применяется метод квадратного корня. При этом с целью уменьшения объема вычислений при решении системы с другими правыми частями матрица S запоминается.
