Теорема Кронекера – Капелли
Для того чтобы система линейных уравнений являлась разрешимой, необходимо и достаточно, чтобы ранг расширенной матрицы этой системы был равен рангу её основной матрицы.
Формулы Крамера
Решение системы линейных уравнений может быть получено через расчет определителей.
,
| (3.6)
| где Δ - определитель матрицы , -определитель матрицы, полученной заменой столбца k матрицы коэффициентов на столбец свободных членов .
Доказательство представленного выражения представляет интерес как один из приемов работы с массивами.
Умножим каждое уравнение i СЛУ
на и просуммируем все уравнения
.
Обратим внимание, что правая часть представляет . В левой части уравнения выполним замену порядка суммирования
Поскольку для всех j¹k (скалярное произведение столбца j на алгебраические дополнения другого столбца k), получаем: , что и требовалось доказать .
Формула Крамера находит широкое применение для ручных расчетов СЛУ относительно небольшого (2-3) порядка.
3.5. Метод Гаусса
Наибольшее распространение для решения систем уравнений получил метод Гаусса. Основная идея его заключается в последовательном исключении переменных и постепенном переходе к эквивалентной системе уравнений с треугольной матрицей коэффициентов. Решение полученной системы не представляет проблем.
Исключение Гаусса рассмотрим на системе из трех уравнений
| (3.7)
|
Выразим из первого уравнения системы значение переменной х1 и подставим это выражение во второе и третье уравнения системы:
В результате второе и третье уравнения уже не содержат х1:
что можно представить в виде
Аналогично выразим х2 из второго уравнения и подставим это выражение в третье уравнение системы:
Окончательно система (3.7) преобразуется к виду :
Таким образом, за n-1 шагов исходная система линейных уравнений преобразуется к системе уравнений с верхней треугольной матрицей. Это прямой ход исключения Гаусса. Решение преобразованной системы уравнений с верхней треугольной матрицей, называется обратным ходом решения системы по Гауссу.
.
Общий вид формул преобразования коэффициентов
Введем обозначения : i - номер уравнения (строки); j - номер переменной (элемента в строке); к - номер шага преобразования (исключаемой переменной)
Тогда формулы преобразования расписываются так:
.
| (3.8)
| Эти формулы легко поддаются программированию для использования вычислительной техники.
Общий вид формул обратного хода
На каждом следующем шаге k (k=n-1,...,1) вычисляется значение переменной xk
.
Блок-схема метода Гаусса
1. Ввод исходных данных.
Прямой ход
2. Цикл по исключаемым переменным k =1,…,n-1.
3. Цикл по уравнениям i=2,…,n.
4. c= .
5. Цикл по текущим переменным j=i,…,n.
6. .
7. Next j; Next i ; Next k
Обратный ход
8. xn= bn/ann.
9. Цикл по восстанавливаемым переменным k =n-1,…, 1.
10. Цикл по текущим переменным j=k+1,…,n, S=0.
11. S=S+ ; Next j.
12. ; Next k
Пример. Методом Гаусса решить систему линейных уравнений
Из первого уравнения системы выразим значение переменной и подставим его во второе и третье уравнения
После приведения подобных членов последние уравнения имеют вид
Аналогично из второго уравнения выразим значение переменной и подставим его в третье уравнение
В результате система уравнений преобразуется к треугольному виду
Это прямой ход исключения Гаусса. На обратном ходе значения переменных определяются в обратном порядке (снизу вверх). Из третьего уравнения -2. Из второго после подстановки -2 получаем х2=3 и из первого х1=2.
Процедуру прямого хода можно представить в матричной форме. Исключение переменных осуществляется путем вычитания предварительно умноженной на коэффициент ki строки, соответствующей исключаемой переменной, из нижних строк
Исходная
Расширенная матрица
| Матрица после первого исключения
| Матрица после второго
исключения
|
|
|
|
Триангуляция квадратной матрицы
Алгоритм триангуляции
Основная идея метода Гаусса широко используется в различных алгоритмических модификациях. Выбор алгоритма решения СЛУ в электроэнергетике должен учитывать следующие особенности уравнений, описывающих установившиеся режимы энергосистемы:
При анализе режимов ЭЭС рассматриваются изменяющиеся во времени нагрузки узлов для сетей постоянной конфигурации, где матрица проводимостей Y остается неизменной. Изменяется только правая часть СЛУ (токи, мощности). Следовательно, требуется выбрать такой алгоритм, который в максимальной степени учитывает специфику постоянства матрицы проводимостей.
Анализ (3.8) позволяет видеть, что при повторных расчетах, связанных с изменением правой части СЛУ выполняются одни и те же преобразования матрицы коэффициентов { }. На этапе исключения переменных новые величины { } составляют примерно 2/n часть. Было бы желательно сохранить промежуточные расчеты { } для их последующего использования.
Это оказывается возможным благодаря так называемой процедуре триангуляции, согласно которой матрица коэффициентов представляется в виде произведения двух треугольных матриц A=LW, причем одна из них (L) является треугольной «снизу», а другая (W) – треугольной «сверху». Представление A=LW называется треугольным разложением или триангуляцией матрицы.
Решение системы линейных уравнений с триангулированной матрицей коэффициентов сводится к двум решениям систем уравнений с треугольными матрицами. Предположим, что требуется решить систему уравнений:
,
| (4.1)
| причем
A =LW.
Заменив в (4.1) A на LW,получаем
.
Обозначим , тогда вместо системы(4.1) можно записать две эквивалентные:
| (4.2)
| Из первого матричного уравнения решением СЛУ с треугольной матрицей Lопределяется вектор , а из второй – искомый вектор . При однократном решении СЛУ триангуляция не дает каких-либо преимуществ по сравнению с простым методом Гаусса. Однако при каждом последующем изменении вектора расчеты СЛУ производятся по (4.2) с неизменными матрицами L,W. При этом решение занимает гораздо меньше времени, чем решение системы с исходной матрицей А, поскольку исключаются повторные расчеты { } (они сохранены в матрицах L, W).
Рассмотрим триангуляцию квадратной матрицы, т.е. разложение её на треугольные сомножители.
Прежде всего, проанализируем формулу (3.8) преобразования коэффициентов в прямом ходе метода Гаусса:
По существу, данная формула означает вычитание на шаге k (исключение переменной xk) умноженной на коэффициент строки k (управляющая строка -УСТР) из текущей строки i. Коэффициенты используются при формировании матрицы L. Совокупность обычно называется управляющим столбцом (УСТБ).
Следует отметить, что любое преобразование матрицы (например, вычитание из какой-либо строки другой, умноженной на некоторый коэффициент) означает ее умножение на некоторую, совершенно определенную матрицу, или иначе, если в результате преобразования матрицы А получена матрица W, то можно записать А=LW.
В приведенном ниже примере матрица Wполучена из А вычитанием первой строки из второй, а матрица Lполучена по некоторому, известному нам правилу.
.
Таким образом, в примере показано, что действительно, существует матрица L, характеризующая линейные преобразования исходной матрицы.
Можно показать, что матрица Lформируется последовательно из управляющих столбцов в процессе гауссовского исключения переменных. Один шаг эквивалентен преобразованию с матрицей, построенной из единичной заменой k-го столбца управляющим столбцом. В частности, на первом шаге А=L1W1, на второмW1=L2W2, на n-1W n-2=Ln-1W n-1=Ln-1W. Отсюда А=LW, где результирующая матрица определяется произведением L =L1L2…Ln-1 и представляет собой совокупность управляющих столбцов.
, ,…,
Матрица Wявляется результатом процесса исключения переменных или последовательно формируется из управляющих строк
; ;
Свойство симметричности матрицы проводимостей ( ) позволяет отказаться от формирования и хранения матрицы L, поскольку управляющие столбцы легко получаются из управляющих строк
,
т.е. столбец k матрицы L равен транспонированной строке k матрицыW, деленной на ее диагональный элемент.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|