Вычисление обратной матрицы методом Гаусса
Один из методов решения системы линейных алгебраических уравнений (2.13), записываемой в матричной форме A X=B, связан с использованием обратной матрицы А-1 [4, с.81–89]. В этом случае решение системы уравнений получается в виде X = А-1 B, где А-1 – матрица, определяемая следующим образом. Пусть А – квадратная матрица размером n´ n c ненулевым определителем det A ¹ 0. Тогда существует обратная матрица R = А-1, определяемая условием A R=E, где Е – единичная матрица, все элементы главной диагонали которой равны 1, а все элементы вне этой диагонали – 0, Е=[E1, …, En], где
где Rj – вектор-столбец.
- 15 -
Рис. 4. Схема алгоритма прямого хода метода Гаусса
- 16 -
Нет
Да
Нет
да
Да
Рис. 5. Схема алгоритма определения ведущего элемента
- 17 -
Нет
Да
Рис. 6. Схема алгоритма перестановки уравнений - 18 -
Рис. 7. Схема алгоритма расчета коэффициентов уравнения
- 19 -
Начальное значение суммы
Новое значение суммы
Определение неизвестного X[i]
Рис. 8. Схема алгоритма обратного хода метода Гаусса
- 20 -
Рассмотрим ее первый столбец R1=(r11, r21, …,rn1)T, где Т означает транспонирование. Нетрудно проверить, что произведение А·R1 равно первому столбцу Е1 = (1, 0,…, 0)Т единичной матрицы Е, т.е. вектор R1 можно рассматривать как решение системы уравнений А R1=E1. Аналогично m-й столбец матрицы R, Rm, 1£ m £ n, представляет собой решение уравнения Таким образом, обратная матрица R (точнее, ее столбцы) представляют собой набор из решений n систем линейных уравнений A Rm = Em, 1 £ m £ n. Для решения этих систем можно применять любые методы, разработанные для решения систем линейных алгебраических уравнений. Однако метод Гаусса дает возможность решать все эти n систем одновременно, а не независимо друг от друга. Действительно, все эти системы уравнений отличаются только правой частью, а все преобразования, которые производятся в процессе прямого хода метода Гаусса, полностью определяются элементами матрицы коэффициентов (матрицы А). Следовательно, в схемах алгоритмов, приведенных выше, изменению подлежат только блоки, связанные с преобразованием вектора В. В нашем случае одновременно будет преобразовываться n векторов Еm , 1 £ m £ n. Так, например, схема алгоритма рис. 7 превращается в схему рис. 9, где Е – двумерная матрица размером n´n. Начальное ее значение совпадает с единичной матрицей: Е[i, j]=0, если i ¹ j и E [i, j] = 1 для i=j, 1£ i£ n. А далее ее элементы пересчитываются по формулам, аналогичным формулам пересчета вектора (2.21). Схема алгоритма обратного хода (см. рис. 8) также претерпит изменение (рис. 10), так как решением системы является теперь не один вектор, а n векторов, т.е. матрица R.
Решение систем линейных уравнений
Эти методы позволяют получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов Х(0), Х(1),…, Х(k). Процесс получения элементов такой последовательности носит итерационный (повторяющийся) характер [3, c.97-100]. Эффективность применения таких методов зависит от удачного выбора начального вектора Х(0) и быстроты сходимости процесса. Рассмотрим два итерационных метода: 1) метод последовательных приближений; 2) метод Зейделя.
- 21 -
Рис. 9. Схема алгоритма вычисления коэффициентов - 22 -
Рис. 10. Схема алгоритма обратного хода вычисления обратной матрицы - 23 -
Указания по использованию метода
Полагая, что в системе уравнений (2.13) все диагональные элементы отличны от нуля, т.е. aii ¹ 0 (i=1, 2,…, n), выразим x1 через первое уравнение системы, x2 через второе уравнение и т.д. В результате получим новую систему, эквивалентную системе (2.13): (2.23)
Обозначим bi / aii = bi; -aij / aii= aij , где i, j=1, 2, ..., n.
Тогда система (2.23) принимает вид x1 = b1 + a12 x2 + a13 x3 +...+ a1n xn x2 = b2 + a21 x1 + a23 x3 +...+ a2n xn (2.24) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xn = bn + an1 x1 + an2 x2 +...+ an n-1 xn-1 .
Введем обозначения a11a12 . . .a1nb1 a21a22 . . .a2nb2 a = ……………… , b = … . an1an2 . . .ann bn Отметим, что в данном случае aii = 0 (i=1, 2, ..., n). Тогда система (2.24) может быть записана в матричной форме X = b +a X или x1 b1 a11a12 . . .a1nx1 x2 b2 a21a22 . . .a2n x2 (2.25) … = + . . . . . . . . . . . . … . xn bn an1 an2 . . .ann xn
- 24 -
Решим систему (2.25) методом последовательных приближений. Для этого за нулевое приближение X(0)примем столбец свободных членов. x1(0) b1 x2(0) b2 или X(0)= b. (2.26) . .. = .. . xn(0) bn
Подставляя значения нулевого приближения в правую часть системы (2.25) , можно получить первое приближение x1(1) b1 a11 a12 . . . a1n x1(0) x2(1) b1 a21 a22 . . . a2n x2(0) … = … + . . . . . . . . . . . . xn(1) bn an1 an2 . . . ann xn(0) или X(1)= b + a X(0) . Подставляя значения первого приближения в правую часть системы (2.25), можно получить второе приближение
X(2) = b+ a X(1), и т.д., и любое (k+1)-е приближение вычисляется по формуле
X(k+1) = b+ a X(k). (2.27) Если последовательность приближений X(0), X(1), ..., X(k) имеет предел
X = lim X(k) , то этот предел и является решением системы (2.13), поскольку k® ¥ по свойству предела lim X (k+1) =b + a lim X(k), k®¥ т.е. X = b +a X .
Условия сходимости итерационного процесса решения системы линейных уравнений
Сходимость зависит от величины элементов матрицы a следующим образом: если сумма модулей элементов строк или сумма модулей элементов столбцов меньше единицы, то итерационный процесс отыскания приближений к истинным значениям корней системы сходится к единственному реше-
- 25 -
нию независимо от выбора начальных (нулевых) приближений, т.е. условия сходимости можно записать так: n n S |aij | < 1 (i=1, 2, ..., n) или S |aij | < 1 (j=1, ..., n) (2.28) j=1 i=1 Сходимость итерационного процесса можно оценить и посредством норм матрицы a. А именно, процесс сходится, если выполняется одно из следующих условий: n ||a ||1 = max S |aij | < 1 , (2.29) j i=1 n или ||a ||2 = max S |aij| < 1 , i j=1 n n или||a ||3 = Ö S S | ai j |2 < 1 . i=1 j=1
Оценка погрешности решения системы линейных уравнений методом последовательных приближений
Пусть X – вектор точных значений неизвестных (корней) системы линейных уравнений (2.25) , а X(k) – вектор k-x приближений к этим точным (истинным) значениям. Тогда для оценки погрешности метода последовательных приближений, где e –точность вычислений:
|| X – X(k)|| £ e , (2.30)
можно использовать неравенство
|| X – X(k) || £ ( ||a || k+1 / (1 – ||a || ) ) || b || , (2.31)
где ||a || – одна из трех норм (2.29) матрицы коэффициентов a исходной системы уравнений; || b || – та же норма вектора свободных членов b этой системы; k – число итераций, необходимых для достижения заданной точности.
На практике при заданном значении e часто в качестве критерия окончания итерационного процесса вычисления значений (x1, x2 , ..., xn) вектора X(k) используется неравенство
- 26 - n S |xi (k+1) – xi (k) | < e . (2.32) i=1
Решение системы линейных алгебраических уравнений
Этот метод решения системы линейных уравнений является модификацией метода последовательных приближений. А именно, при вычислении (к+1)-го приближения неизвестного xiиспользуется уже найденные ранее Пусть дана система (2.24). Прежде всего необходимо задать значения начальных (нулевых) приближений корней x1(0), x2(0) , ..., xn(0). Если отсутствует какая-нибудь информация об этих значениях, то их можно принять равными свободным членам (2.26) системы или даже положить равными нулю. Выбранные таким образом нулевые приближения корней подставим в первое уравнение системы (2.24) и получим первое приближение корня x1
x1(1) = β1 + α12 x2(0) + α1 3 x3(0) + … + α1 n xn(0) . Используя во втором уравнении системы (2.24) найденное первое приближение корня х1 и нулевые приближения остальных корней, получим первое приближение корня х2
x2(1) = β2 + α2 1 x1(1) + α2 3 x2(0) + … + α2 n xn(0) .
Повторяя эту процедуру последовательно для всех уравнений системы (2.24), получим, наконец, первое приближение корня
xn(1) = βn + αn 1 x1(1) + αn 2 x2(1) + … + αn n-1 xn-1(1) .
Используя первые приближение корня системы, можно аналогичным образом найти вторые приближения, затем, используя вторые приближения, можно вычислить третьи и т.д. Так же, как и при использовании метода последовательных приближений, итерационный процесс решения системы линейных уравнений методом Зейделя сходится к единственному решению при любом выборе начальных приближений искомых корней, если выполняется одно из условий (2.29). Отметим, что при использовании метода Зейделя процесс сходится быстрее. Погрешность решения системы уравнений методом Зейделя принято оценивать по формулам (2.30) - (2.32). Схема алгоритма решения системы уравнений методом Зейделя (рис. 11) лишь незначительно отличается от схемы алгоритма решения методом - 27 -
Ввод матрицы коэффициентов A, вектора свободных членов B, вектора нулевых приближений неизвестных X0, точности eps, числа уравнений n
Цикл копирования массива X0 в массив X
6 Очистка накопителя test суммы модулей разницы k-го и (k+1)-го приближений (см. неравенство блока 17) 7 Цикл вычисления вектора-столбца приближений неизвестных системы
8 Очистка накопителя суммы
9 Цикл вычисления суммы сла--гаемых левой части i–го уравнения системы
11 Конец цикла по j
Рис. 11. Схема алгоритма решения системы линейных уравнений методом Зейделя - 28 -
12 Вычисление суммы слагаемых левой части i–го уравнения без i-го слагаемого
13 Вычисление очередного при- ближения неизвестного X[i]
14 Добавление в накопитель test очередного слагаемого
15 Запись нового приближения неизвестного в массив
16 Конец цикла по i
17 Проверка условия окончания итерационного процесса поиска приближенных значений неизвестных системы
18 Вывод массива значений вектора-столбца неизвестных системы
Рис. 11 (продолжение). Схема алгоритма решения системы линейных уравнений методом Зейделя - 29 -
последовательных приближений. Вместо переменной bpx следует ввести индексированную переменную, например X1[1], исключив из схемы блок 15. После проверки условия окончания вычислений (блок 17) в ветвь “отрицательного ответа” необходимо включить цикл копирования элементов массива X1 в соответствующие элементы массива X.
Оценка погрешности аппроксимации и выбор
Результатом этапа решения системы нормальных уравнений (2.11) является получение значений параметров аппроксимирующей функции (2.9)
для заданного набора базисных аппроксимирующих функций .
Решение ( ) системы нормальных уравнений определяет значения параметров, при которых критерий качества аппроксимации J принимает минимально возможное значение . При всех других допустимых значениях параметров величина критерия будет больше. Тем самым полученное число может быть принято за характеристику эффективности аппроксимации заданной функциональной зависимости функциями выбранного класса. При изменении класса аппроксимирующих функций, а также при изменении набора базисных функций значение может меняться. Сравнение различных классов функций по их эффективности (качеству) аппроксимации может осуществляться на основе сравнений соответствующих значений . Для количественной оценки погрешности аппроксимации может использоваться также величина ( ) максимального отклонения исходной функциональной зависимости от найденной аппроксимирующей. Для задачи 1 (подразд. 2.1.) значение
рассчитывается с помощью алгоритмов определения максимального элемента последовательности или массива. В курсовой работе исходный набор базисных аппроксимирующих функций используется для отладки разрабатываемых алгоритмов, получения первых результатов аппроксимации ( , ) и построения графика, на котором отображаются исходная и аппроксимирующая функции. Студенту необ- - 30 -
ходимо самостоятельно выбрать два дополнительных набора базисных функций и на их основе получить результаты аппроксимации, включая графики на общем изображении. По трем результатам аппроксимации следует определить лучшую аппроксимирующую функцию. Процесс поиска лучшего набора базисных функций по результатам аппроксимации представлен на схеме рис. 12. 3. Рекомендации по содержанию и порядку
Формулировка решаемой задачи
Исходными данными являются функциональная зависимость (между x и y) в виде координат точек на плоскости (см. рис. 1). Требуется посредством МНК (см. подразд. 2.1) найти аппроксимирующую функцию из заданного класса функций и оценить степень ее отклонения от исходной функциональной зависимости.
Задание аппроксимирующей функции
В курсовой работе задан исходный набор базисных аппроксимирующих функций и тем самым определено число m = 3 параметров , подлежащих определению. Аппроксимирующая функция имеет вид (2.9).
Формулировка критерия аппроксимации По заданной исходной функциональной зависимости (y от x) и выбранной аппроксимирующей функции необходимо составить критерий аппроксимации (J) согласно формуле (2.5). Критерий аппроксимации, являющийся функцией искомых параметров , можно минимизировать либо непосредственно отысканием минимума функции методами нелинейного программирования, либо используя необходимые условия минимума этой функции, т.е. составляя и решая систему нормальных уравнений (2.8).
Определение параметров аппроксимирующей функции
При определении параметров путем решения системы нормальных уравнений (2.11) используются прямые или итерационные методы решения системы линейных алгебраических уравнений. Для вычисления коэффициентов - 31 -
Рис. 12. Расчеты и выбор лучшей аппроксимирующей функции - 32 -
нормальных уравнений согласно формулам (2.12) необходимо использование алгоритмов суммирования числового ряда. Выполнение курсовой работы предполагает описание выбранного математического метода (методов) для всех этапов работы и проведение вручную всех контрольных расчетов (разд. 4) согласно разработанному алгоритму с целью их сопоставления с результатами машинных расчетов после выполнения программы на компьютере. Пояснительная записка курсовой работы должна содержать схемы всех алгоритмов, как разработанных, так и стандартных, используемых в процессе вычислений. Программная реализация курсовой работы осуществляется с использованием модульного принципа программирования. Вспомогательные алгоритмы оформляются в виде подпрограмм на языке высокого уровня, а в главной программе выполняются обращения к подпрограммам. Соответствующие этим алгоритмам подпрограммы, самостоятельно разрабатываемые или библиотечные, а также программа в целом прилагаются к пояснительной записке в соответствии с требованиями конкретного задания.
Графическое сопоставление данных Найденные параметры подлежат использованию при построении (вручную для исходного набора базисных функций и посредством ЭВМ для трех наборов, включая исходный) графика аппроксимирующей функции для сравнения его с исходными данными с целью качественной (визуальной) оценки степени близости функций, а следовательно, и качества аппроксимации по методу наименьших квадратов. Количественная оценка погрешности аппроксимации
Качество проведенной аппроксимации может быть оценено различными числовыми характеристиками ее погрешности и, в частности, значением критерия качества J и максимальным по модулю отклонением исходной зависимости от аппроксимирующей. Для выбора лучшей аппроксимирующей функции на ЭВМ работа выполняется с тремя наборами базисных функций согласно подразд. 2.3.
4. Контрольные расчеты параметров Для проверки расчетов, выполняемых на компьютере, необходимо выполнить вручную расчеты параметров аппроксимирующей функции для заданного набора базисных функций с целью получения тестовых данных. Ручные расчеты выполняются как минимум дважды (причем желательно - 33 -
разными способами) до совпадения тестовых результатов. С тестовыми (контрольными) данными сопоставляются результаты расчетов на компьютере. Существенное расхождение тестовых и компьютерных расчетов требует ана- лиза и корректировки вводимых данных, алгоритмов, программ, а возможно и тестовых расчетов. Ниже приведен контрольный расчет для двух исходных базисных функций φ1(x) = 1, φ2 (x) = x.
Пример.
1. Постановка задачи. Исходная функциональная зависимость представлена в таблице парами значений xi и yi . Найти параметры (С1 и С2) аппроксимирующей функции
2. Табличное представление исходных данных. Таблица 2
3. Критерий аппроксимации (см. подразд. 2.1). Согласно условию (2.5): J(C1, C2 ) = min . 4. Условия минимума критерия аппроксимации и формирование В соответствии с требованием использования условий локального минимума (2.9) условия минимума J =0 , =0 , = = -2( ) , - 34 -
= -2( ) ,
т.е. нормальные уравнения имеют вид -2( )=0, -2( )=0 Или C1 ·5 + C2 , C1 .
Введем обозначения a11=5 ; a12= ; b1= , a21= ; a22= ; b2= .
Тогда систему нормальных уравнений можно записать посредством матричных обозначений A C = B , где A= - матрица коэффициентов нормальных уравнений; C= - вектор-столбец неизвестных (искомых параметров);
B= - вектор-столбец свободных членов системы.
3. Вычисление коэффициентов нормальных уравнений.
а11 =5 ; а12 = 0,0+1,0+2,0+3,0+4,0 = 10,0 ; а21 = а12 = 10,0 ; а22 = 0,02 + 1,02 + 2,02 + 3,02 + 4,02 = 30,0; в1 = 0,0 + 1,0 + 8,0 + 27,0 + 64,0 = 100,0; в2 = 0,0 · 0,0 + 1,0 · 1,0 + 8,0 · 2,0 + 27,0 · 3,0 + 64,0 · 4,0 = 354,0. - 35 -
Система нормальных уравнений имеет вид
6. Решение системы нормальных уравнений. А. Метод Гаусса:
С =15,4 ; С = -10,8 Б. Метод обратной матрицы: для матрицы A = обратная матрица имеет вид A-1 = , где det A - определитель матрицы А; i j - алгебраическое дополнение. Отсюда det A = 5 · 30,0 – 10,0 · 10,0 = 50,0.
A-1 =
Решение системы уравнений A C = B методом обратной матрицы имеет вид C* = A-1 B, т.е.
C* = , 7. Запись искомой аппроксимирующей функции y(x) y = –10,8 + 15,4 x . 8. Оценка погрешности аппроксимации.
Для оценки среднеквадратичного и максимального по модулю отклонений аппроксимирующей функции от исходной представим результаты проведенных вычислений в виде табл. 3 и рис. 13.
- 36 - Таблица 3
Рис. 13. График функций y=f(x), y=
Тогда минимальное значение качества аппроксимации
Jmin = J(C ) = (10,8)2 + (–3,6)2 + (–12,0)2 + (–8,4)2 + (13,2)2 = 518,4,
а максимальное по модулю отклонение, получаемое сопоставлением найденных значений , составляет max| | = 13,2 при x = x5 = 4,0 .
Содержание пояснительной записки
Текст пояснительной записки должен включать следующие разделы. 1. Постановка задачи. 2. Представление исходных данных (табличное). 3. Описание критерия аппроксимации и способа его минимизации. 4. Описание метода вычисления коэффициентов нормальных уравнений.
- 37 -
5. Описание метода определения параметров аппроксимирующей функции (решение системы нормальных уравнений). 6. Схемы алгоритмов и их описание. 7. Контрольный расчет параметров аппроксимирующей функции (без использования компьютера). 8. Программы и результаты расчетов параметров на компьютере. 9. Графическое сопоставление исходной и аппроксимирующих функциональных зависимостей (вручную и на компьютере). 10. Описание алгоритма и программы оценки погрешности аппроксимации. 11. Анализ результатов. Выводы. Варианты курсовой работы
А. Способ выбора базисной функции. 1. Использование условного оператора. 2. Использование оператора-переключателя. 3. Использование массива указателей на функции.
Б. Способ вычисления коэффициентов нормальных 1. Вычисление непосредственно по формуле коэффициентов. 2. Умножение матриц значений базисных функций.
В. Метод решения системы линейных уравнений. 1. Метод Гаусса. 2. Метод простой итераци
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (650)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |