Курсовая: Численные методы
Notice: Undefined variable: ref_img in /home/area7ru/area7.ru/docs/referat.php on line 323
|
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА. Основная идея метода. Может оказаться, что система Ax=f (1) имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т.е. наибольший по модулю элемент. Тем самым, если  , то в процессе вычислений не будет происходить деление на нуль.Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений  (2)    Предположим, что  . Тогда на первом шаге будем исключать переменное  . Такой прием эквивалентен тому, что система (2) переписывается в виде (3)  и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных. Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что  . Перепишем систему (2) в виде  и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений. Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде   где  -элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок.ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице. ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок  называется матрица, полученная из единичной матрицы перестановкой к-й и l-й строк.Например, элементарными матрицами перестановок третьего порядка являются матрицы  Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения . Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной). Для любой квадратной матрицы А матрица  отличается от А перестановкой к-й и l-é ñòðîê. Для любой квадратной матрицы А матрица  отличается от А перестановкой к-го и l-го столбцов. Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка: (4)Система имеет вид (1), где  (5)Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому надо поменять местами вторую и первую строки и перейти к эквивалентной системе  (6)Систему (6) можно записать в виде  (7)т.е. она получается из системы (4) путем умножения на матрицу перестановок  Далее, к системе (6) надо применить первый шаг обычного метода исключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу  В результате от системы (7) перейдем к эквивалентной системе  (8)или в развернутом виде  (9)Из последних двух уравнений системы (9) надо теперь исключить переменное  . Поскольку максимальным элементом первого столбца укороченной системы (10) является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе  (11)которую можно записать в матричном виде как  . (12)Таким образом система (12) получена из (8) применением элемен-тарной матрицы перестановок  Далее к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную нижнюю треугольную матрицу  В результате получим систему  (13)или  (14)Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением  что эквивалентно умножению (13) на элементарную нижнюю треугольную матрицу  Таким образом, для рассмотренного примера процесс исключения Гаусса с выбором главного элемента по столбцу записывается в виде  (15)По построению матрица  (16)является верхней треугольной матрицей с единичной главной диагональю. Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матрицами  могут присутствовать элементарные матрицы перестановок  .Покажем еще, что из (16) следует разложение PA=LU, (17) где L -нижняя треугольная матрица, имеющая обратную, P - матрица перестановок. Для этого найдем матрицу  (18)По свойству 2) матрица  получается из матрицы  перестановкой второй и третьей строк, Матрица  согласно свойству 3) получается из перестановкой второго и третьего столбцов т.е.  -нижняя треугольная матрица, имеющая обратную.Из (18), учитывая равенство  , получим (19)Отсюда и из (16) видно, что  где обозначено  . Поскольку Р-матрица перестановок и L-нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к матрице РА, т.е. к системе, полученной из исходной системы перестановкой некоторых уравнений.Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1). А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде  (20)где  - элементарные матрицы перестановок такие, что и -элементарные нижние треугольные матрицы.Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе PAx=Pf, (21) где Р - некоторая матрица перестановок. Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме. ТЕОРЕМА 1. Если  то существует матрица перестано-вок Р такая, что матрица РА имеет отличные от нуля угловые ми- норы. Доказательство в п.4. СЛЕДСТВИЕ. Если то существует матрица престана-вок Р такая, что справедливо разложение РА=LU, (22) где L- нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента. 4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А. Пусть m=2, т.е.  Если  то утверждение теоремы выполняется при Р=Е, где Е - единичная матрица второго порядка. Если  , то  , т.к.  При этом у матрицы все угловые миноры отличны от нуля. Пусть утверждение теоремы верно для любых квадратных матриц порядка m-1. Покажем, что оно верно и .для матриц порядка m. Разобьем матрицу А порядка m на блоки  где    Достаточно рассмотреть два случая :  и  . В первом случае по предположению индукции существует матрица перестановок  порядка m-1 такая, что  имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок имеем  причем  . Тем самым все угловые миноры матрицы РА отличны от нуля.Рассмотрим второй случай, когда  . Т.к.  , найдется хотя бы один отличный от нуля минор порядка m-1 матрицы А, полученный вычеркиванием последнего столбца и какой-либо строки. Пусть, например, где  .Переставляя в матрице А строки с номерами l и m, получим матрицу  , у которой угловой минор порядка m-1 имеет вид и отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю. Теорема доказана. ВЫЧИСЛЕНИЕ ОПРЕДЕЛИТЕЛЯ МЕТОДОМ ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА. Одновременно с решением системы линейных алгебраических уравнений  можно вычислить определитель матрицы А. Пусть в процессе исключения найдено распожение  т.е. построены матрицы L è U . Тогда  и, таким образом, произведение диагональных елементов матрицы L (ведущих, главных елементов метода исключения) равно определителю матрицы РА. Поскольку матрицы РА и А отличаются только перестановкой строк, определитель матрицы РА может отличаться от определителей матрицы А только знаком. А именно,  Таким образом, для вычисления определителя необходимо знать, сколько перестановок было осуществлено в процессе сключения. Если матрица А выроджена, то при использовании метод Гаусса с выбором главного элемента по столбцу на некотором шаге исключения К все элементы которого столбца, находящиеся ниже главной диагонали и на ней, окажутся равными нулю.При этом дальнейшее исключение становится невозможным и программа должна выдать информацию о том, что определитель матрицы равен нулю. ОБРАЩЕНИЕ МАТРИЦ. Нахождение матрицы, обратной матрице А , еквивалентно решению матричного уравнения  (1)где Е - единичная матрица, X - искомая квадратная матрица. Уравнение (1) можно записать в виде системы  уравнений (2)где  Можно заметить, что система (2) распадается на m независимых систем уравнений с одной и той же матрицей А , но с различными правыми частями. Эти системы имеют вид ( фиксируем j ) :  (3)где  у вектора - столбца  равна единице j-та компонента и равны нулю остальные компоненты.Например, для матрицы второго порядка система (2) распадается на две независимые системы:  Äëÿ ðåøåíèÿ систем (3) используется метод Гаусса ( обычный или с выбором главного элемента). Рассмотрим применение метода Гаусса без выбора главного элемента. Поскольку все системы (3) имеют одну и ту же матрицу А , достаточно один раз совершить прямой ход метода Гаусса, т.е. получить разложение A=LU и запомнить матрицы L i U . Обратный ход осуществляется путем решения систем уравнений  с треугольными матрицами L è U. При осуществлении обратного хода можно сократить число действий, принимая во внимание специальный вид правых частей системы (4). Запишем подробнее первые j-1 уравнений системы (4):  Учитывая невырожденность матрицы L ( т.е.  отсюда получаем  При этом оставшиеся уравнения системы (4) имеют вид  Отсюда последовательно находятся неизвестные  по формулам:  Можно показать, что общее число действий умножения и деления, необходимое для обращения матрицы указанным способом, порядка  . Тем самым обращение матрицы требует не намного больше времени, чем решение системы уравнений.МЕТОД ПРОГОНКИ. Система уравнений для определения коэффициентов сплайна представляет собой частный случай систем линейных алгебраических уравнений  с трехдиагональной матрицей  , т.е. с матрицей, все элементы которой,не лежащие на главной и двух побочных диагоналях, равны нулю  при  та  В общем случае системы линейных алгебраических уравнений с трехдиагональной матрицей имеют вид  Для численного решения систем трехдиагональными матрицами применяется метод прогонки, который представляет собой вариант метода последовательного исключения неизвестных. Т.е. матрицу А можно записать  Идея метода прогонки состоит в следующем. Решение системы (1) ищется в виде  где  -неизвестные коэффициенты, которые последовательно находятся от  до  (прямая прогонка ), а затем последовательно вычисляются  (обратная прогонка) .Выведем формулы для вычисления  Из (3) можно получить Подставляя имеющиеся выражения для  в уравнение (1),приходим при  к уравнению  Последнее уравнение будет выполнено если коэффициенты  выбрать такими, чтобы выражения в квадратных скобках обращались в нуль.А именно, достаточно положить  Для отыскания всех  достаточно задать  Эти начальные значения находим из требования эквивалентности условия (3) при  т.е. условия  , первому из уравнений (2).Таким образом, получаем  (5)Нахождение коэффициентов  по формулам (4), (5) называется прямой прогонкой. После того, как прогоночные коэффициенты  найдены, решение системи (1), (2) находится по рекуррентной формуле (3), начиная с  Для начала счета по этой формуле требуется знать  , которое определяется из уравнений И равно  .Нахождение  по формулам (6)называется обратной прогонкой. Алгоритм решения системы (1), (2) определяемый формулами (4)-(6) называется методом прогонки. Метод прогонки можно пременять, если знаменатели выражений (4), (6) не обрщаются в нуль. Покажем, что для возможности применения метод прогонки достаточно потребовать, чтобы коэффициенты системы (1), (2) удовлетворяли условиям  (8)Сначала докажем по индукции, что при условиях (7), (8) модули прогоночных коэффициентов  не превосходят единицы. Согласно (5), (8) имеем  . Предположим,что  для некоторого  и докажем, что  Прежде всего для любых двух комплексных чисел  и  докажем неравенство Из неравенства треугольника имеем  Откуда Вернемся теперь к доказательству  , если . Согласно имеем оценку а, используя (7) , получаем   т.е. знаменатели выражений (4) не обращаются в нуль. Более того  Следовательно,  Далее, учитывая второе из условий (8) и только что доказанное неравенство  , имеем т.е. не обращается в нуль и знаменатель в выражении для  .К аналогичному выводу можно прийти и в том случае, когда условия (7), (8) заменяются условиями  Таким образом при выполнении условий (7), (8) (так же как и условий (9), (10)) система (1), (2) эквивалентна системе (4)-(6). Поэтому эти условия гарантируют существование и единственность решения системы (1), (2) и возможность нахождения этого решения методом прогонки.Кроме того, доказанные неравенства ,  обеспечивают устойчивость счета по рекуррентным формулам (6). Последнее означает, что погрешность,внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам.Действительно, пусть в формуле (6) при  вместо  вычислена величина  Тогда на следующем шаге вычислений, т.е. при  вместо  получим величину  и погрешность окажется равной Отсюда получаем, что  ,т.е. погрешность не возрастает.Подсчитаем число арифметических действий, выполняемых при решении задачи (1), (2) методом прогонки. По формулам (4), что реализуемые с помощью шести арифметических действий, вычисления производятся  раз, по формуле (6) выполняется 5 арифметических действий, наконец по формуле (3), требующей всего два действия, вычисления осуществляются  раз. Итак в методе прогонки всего затрачивается арифметических действий, т.е. число действий растет линейно относительно числа неизвестных  При решении же произвольной системы линейных алгебраических уравнений методом Гаусcа число действий пропорционально кубу числа неизвестных. ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ЗНАЧЕНИЙ И СОБСТВЕННЫХ ВЕКТОРОВ МАТРИЦ. Большое число задач математики и физики требует отыскания собственных значений и собственных векторов матриц, т.е. отыскания таких значений +  , для которых существуют нетривиальные решения однородной системы линейных алгебраических уравнений , (1)и отыскания этих нетривиальных решений. Здесь  -квадратная матрица порядка m ,  - неизвестный вектор - столбец.Из курса алгебры известно, что нетривиальное решение системы (1) существует тогда и только тогда, когда  , (2)где Е - единичная матрица. Если раскрыть определитель  , ïîëó÷àåòñÿ алгебраическое уравнение степени m относительно .Таким образом задача отыскания собственных значений сводится к проблеме раскрытия определителя по степеням и последующему решению алгебраического уравнения m- й степени.Определитель  называется характеристическим (или вековым ) определителем, а уравнение (2) называется характеристическим (или вековым ) уравнением.Различают полную проблему собственных значений, когда необходимо отыскать все собственные значения матрицы А и соответствующие собственные векторы, и частичную проблему собственных значений, когда необходимо отыскать только некоторые собственные значения, например, максимальное по модулю собственное значение . Метод Данилевского развертывание векового определителя. Определение. Квадратная матрица Р порядка m называется подобной матрице А , если она представлена в виде  ,где S - невыродженная квадратная матрица порядка m. ТЕОРЕМА. Характеристический определитель исходной и подобной матрицы совпадают . Доказательство.  Идея метода Данилевского состоит в том, что матрица А подобным преобразованиям приводится, к так называемой нормальной форме Фробениуса  .Характеристическое уравнение для матрицы Р имеет простой вид  т.е. коэффициенты при степенях  характеристического полинома непосредственно выражаются через элементы первой строки матрицы Р.Приведение матрицы А к нормальной форме Фробениуса Р осуществляется последовательно построкам, начиная с последеней строки. Приведем матрицу А  подобным преобразование к виду  Пусть  Можн проверить,что такой вид имеет матрица  , которая равна где   Слудующий шаг - приведение матрицы подобным преобразованием к виду  , где и вторая снизу строка имеет единицу в  -ом столбце, а все остальные элементы строки равны нулю: Если  то можно проверить, что такой вид имеет матрица : где   Таким образом  Далее процедура аналогичная, если на кождом шаге в очередной строке, на месте которого подобным преобразованием нужно получить единицу, не равную нулю. В этом случае ( будем называт его регулярным ) нормальная формула Фробениуса будет получена за ( m-1 ) шагов и будет иметь вид  Рассмотрим нерегулярный случай, когда матрица, полученная в результате подобных преобразований приведена уже к виду  и элемент  . Таким образом обычная процедура метода Данилевского не подходит из-за необходимости деления на ноль.В этой ситуации возможно два случая. В первом случае к-й строке левее элемента  есть элемент   Тогда домножая матрицу  слева и справа на элементарную матрицу перестановок  , получаем матрицу ,у которой по сравнению с матрицей переставлены l -я и (k-1 )-я строка l-й и ( k-1)- й стодбец. В результате на необходимом нам месте оказывается ненулевой элемент  , уже преобразованная часть матрицы не меняется, можно применять обычный шаг метода Данилевского к матрице  . Она подбна матрице (и, следовательно, исходной матрице А ), т.к. елементарная матрица перестановок совпадает со своей обратной, т.е.  Рассмотрим второй нерегулярный случай, когда в матрице ýлемент  и все элементы этой строки, которые тоже находятся левее его, тоже равны нулю. В этом случае характеристический определитель матрицы можно представить в виде где  і  - единичные матрицы соответствующей размерности, а квадратные матрицы  и  имееют вид: Обративм внимание на то, что матрица уже нормальную форму Фробениуса, и поэтому сомножитель  просто развертывается в виде многочлена с коэффциентами, равными элементам первой строки.Сомножитель  , åñòü характеристический определитель матрицы . Для развертывания можн опять применять метод Данилевского, приводя матрицу подобными преобразованиями к нормальной форме Фробениуса.Предположим теперь, что матрица А подобным преобразованиям уже приведена к нормальной форме Фробениуса. Решая характеристическое уравнение ,находим одним из известных методов его корни  которые являются собственными значениями матрицы Р и исходной матрицы А.Теперь стоит задача отыскать собственные векторы, соответствующие этим собственным значениям, т.е. векторы  такие, что Решим ее следующим образом: найдем собственные векторы матрицы Р , а затем по определенному соотношению я пересчитаем собственные векторы матрицы А . Это соотношение дает следующая теорема. ТЕОРЕМА. Пусть  є есть собственное значение , а  есть соответствующий собственный вектор матрицы Р , которая подобна матрице А ,т.е. Тогда  есть с...
|
|
Простая ссылка на эту работу:
Ссылка для размещения на форуме:
HTML-гиперссылка:
|
Добавлено: 2010.11.21 Просмотров: 1955 |
Notice: Undefined offset: 1 in /home/area7ru/area7.ru/docs/linkmanager/links.php on line 21
