LEC-28 (Материалы к лекциям)

15

В.А. Столярчук. “Моделирование систем”. Конспект лекций. Лекция №28

Лекция № 28

12. Приведение матриц.

12.1 Матрицы и особенности решения матричных уравнений.

А + В = В + А

АВ≠ВА;

АВ=С;

Транспонированная матрица А^Т получается отражением матрицы А относительно её диагонали, т.е. .

Единичная матрица имеет единицы на диагонали, а остальные её элементы равны нулю.

Единичная матрица обязательно квадратная. IA = AI.

Обратная матрица А^-1 есть такая матрица, для которой выполняется равенство А^-1А=1. Не всякая матрица имеет обратную. Действительно, произведение АВ может быть равным нулю, даже если А или В не были нулевым матрицами

.

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

матрица А – невырожденная;

обратная матрица А^-1 существует;

столбцы матрицы А линейно независимы;

строки матрицы А линейно независимы;

равенство Ах = 0 означает, что х = 0.

Задача решения линейных уравнений состоит в нахождении такого

Вектора х по данной матрице А и данному вектору b, для которого выполняется равенство Ах = b.

Если матрица невырожденная (тем самым А – квадратная), то эта задача всегда имеет единственное решение для любого b.

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

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

Система уравнений называется однородной, если правая часть равна нулю, например, Ах = 0.

Особенности решения матричных уравнений.

Гауссово исключение и проблема упорядочения.

Система уравнений, которую надо решить есть:

Ах = b

Процесс исключения состоит из n-1 шагов

А^(K+1) = L^(K)A^(K)

и начинается с матрицы А⁽¹⁾ =А

Элементы матрицы А^(K+1) находятся по формуле:

a_ij^(K+1)=a_ij^(K) - Кп_, где Кп = a_iK^(K) a_Ki^(K)/ a_KK^(K) ;

Конечным результатом исключения является верхняя треугольная матрица U=A^(U) , а весь процесс эквивалентен вычислению треугольного разложения:

A = LU, где L = L_n , L_n-1, .......L₂, L₁ , а U = А⁽ⁿ⁺¹⁾

Чтобы разложение удалось вычислить, необходимо, чтобы все знаменатели a_KK^(K) в формулах были отличны от нуля. Кроме того, для обеспечения приемлемой устойчивости вычислений желательно, чтобы поправочные коэффициенты Кп были не слишком велики. В результате гауссова исключения приходим к уравнению:

LUx = b , которое преобразуется в , после чего производится обратная подстановка. Здесь: U и L - верхняя и нижняя треугольные матрицы.

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

a_ij^(K+1)=a_ij^(K) - a_iK^(K) a_Ki^(K) / a_KK^(K),

входящих в правую часть, будут равны нулю.

Методы для разреженных матриц основаны на следующих главных принципах:

а) хранятся только ненулевые элементы матрицы А;

б) формулами процесса факторизации пользуются,

если a_iK^(K) 0 и a_Kj^(K) 0.

в) число новых элементов стараются по возможности уменьшить. Новый элемент возникает, если a_ij^(K) =0 , а a_ij^(K+1) 0

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

Представим алгоритм Гаусса на каком-либо языке программирования в компактной форме. Алгоритм Гаусса строит верхнюю треугольную матрицу U и матрицу множителей L на месте матрицы А, так, что элементы матрицы А не сохраняются.

Исключение Гаусса с частичным выбором ведущего элемента

для решения системы Ах=b

Цикл по столбцам А

For K=1 to U-1 do

Поиск максимального по модулю элемента в столбце

i_max = индекс строки такой, чтоa_jmax,K= maxa_iK i K

Проверка на нуль ведущего элемента (на вырожденность)

BUFFER - машинно-зависимая константа, оценивающая величину ошибок округления

IFa_jmax,K BUFFER, то перейти на конец цикла К.

Перестановка строк с индексами К и IMAX

For j=1 to n переставить a_Kj и a_imax

Перестановка соответствующих правых частей

Переставить b_K и b_imax

Цикл по строкам

For i=K+1 to U do

Вычисление множителей и запоминание их в столбце К

m=a_iK - a_iK/a_KK

Цикл по элементам строки I

For j=K+1 to N do

a_ij=a_ij - m _* a_Kj

Вычисление правой части строки I

b_i=b_i - m _* b_K

Конец цикла по i.

Конец цикла по K.

Обратная подстановка

Цикл по строкам в обратном порядке

For i=N to 1 do

Подстановка известных компонент решения в правую часть.

Проверка на нуль ведущего элемента

IF(a_ij> BUFFER) then x_i=r / a_ij

Проверка на нуль правой части

Присвоить нуль компоненте решения и печать сообщения

Else IFr  BUFFER then x_i=0

или печать сообщения об ошибке

else печать несовместимая система, А - вырождена.

Конец цикла по i.

Матрицы L и U хранятся на месте матрицы А. Каждый множитель помещен на месте обнуляемого элемента А.

В обычной записи:

a₁₁X₁+a₁₂X₂+a₁₃X₃+...+a_1nX_n=b₁

a₂₁X₁+a₂₂X₂+a₂₃X₃+...+a_2nX_n=b₂

a₃₁X₁+a₃₂X₂+a₃₃X₃+...+a_3nX_n=b₃

......................................................

......................................................

a_n1X₁+a_n2X₂+a_n3X₃+...+a_nnX_n=b_n

......,

a₂₁X₁+a₂₂X₂+a₂₃X₃+...+a_2nX_n=b₂

a₁₁ X₁+a₁₂ X₂+a₁₃ X₃+...+a_1n X_n=b₁

Пример 1.

a) 2X₁+2X₂+4X₃=5

b) 6X₁-X₂+X₃=7

c) 4X₁-10X₂-12X₃= -4

a) 2X₁+2X₂+4X₃=5

b) -7X₂-11X₃= -8 (вычитание первой строки, умноженной на 3 из второй строки)

c) -14X₂-20X₃= -14 (вычитание первой строки, умноженной на 2 из третьей строки)

a) 2X₁+2X₂+4X₃=5

b) -7X₂-11X₃= -8

c) 2X₃=2 (вычитание второй строки, умноженной на 2

из третьей строки)

В обычной записи:

(23)X₁+(23)X₂+(43)X₃=53 (22)X₁+(22)X₂+(42)X₃=52

*

*

6X₁ -1X₂ +1X₃=7 4X₁-10X₂-12X₃= -4

-7X₂ -11X₃= -8 -14X₂-20X₃= -14

-72X₂-112X₃= -82

*

-14X₂-20X₃=-14

0+2X₃= 2

в итоге:

была стала

Пример 2.

2X₁+2X₂+4X₃=5

6X₁-X₂+0X₃=7

4X₁-10X₂-12X₃= -4

(23)X₁+(23)X₂+(43)X₃=53

*

6X₁+X₂+0X₃=7

-7X₂-12X₃= -8

(22)X₁+(22)X₂+(42)X₃=52

4X₁-10X₂-12X₃= -4

*

-14X₂-20X₃= -14

-72X₂-122X₃= -16

*

-14X₂-20X₃=-14

+4X₃= 2

В итоге:

была стала

Масштабирование и анализ машинного нуля.

Алгоритм Гаусса требует анализа ситуаций, когда некоторые получаемые числа равны 0.

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

масштаб представления чисел в исходной задаче и

масштаб представления чисел в машине.

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

Однако это было бы абсолютно неправильным, если все элементы матрицы А имели бы порядок 10^(-8). Таким образом целесообразно масштабировать систему так, чтобы все элементы были порядка 1 и тогда было бы правильным считать, что малые числа порядка 1,210^(-10) представляют собой помехи из-за ошибок округления.

Существует два естественных способа масштабирования системы Ax=b.

a) Мы можем умножить уравнения на некоторый множитель (например, на 10⁸, если элементы а_ij имеют порядок 10^(-8)) для выравнивания коэффициентов.

b) Мы можем умножить также столбцы матрицы А: это соответствует изменению единиц измерения неизвестных (например, переходу от сантиметров к метру).

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

Например:

К счастью, большинство задач могут быть масштабированы.

Решающим является выбор единиц измерения (они определяют величину изменения масштаба), которые естественны для задачи и которые не искажают соотношений между размерами объектов.

Наиболее простой способ масштабирования состоит в таком умножении каждой строки (уравнения), чтобы наибольший элемент строки был равен 1.

В предположении, что это сделано, перейдем к выбору величины BUFFER.

Если машина имеет t разрядов с основанием b, то в качестве значения BUFFER может быть всего С*b^(-t), где С - некоторое небольшое число (3  4) и должно постепенно расти с увеличением порядка матрицы.