Главная Учебники - Разные Лекции (разные) - часть 33
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное агентство по образованию Государственное образовательное учреждение Высшего профессионального образования «Оренбургский государственный университет»
Факультет экономики и управления Кафедра математического обеспечения информационных систем
по дисциплине «Численные методы» Прямой метод вращения векового определителя ОГУ 061800.8006.18 ООО Руководитель работы ____________________Ващук И.Н. «_____» _______________ 2006 г. Исполнитель студент гр. 04ММЭ ________________Широбоков П.Д. «_____» ________________ 2006 г. Оренбург 2006 Оглавление
Введение. 3 Постановка задачи.. 4 Описание метода. 5 Сходимость метода. 8 Описание входных и выходных данных.. 9 Заключение. 10 Список литературы.. 11 Приложение А... 12 Приложение Б.. 19 Численные методы решения проблемы собственных значений до конца 40-х годов, сводились, в основном, к решению характеристического уравнения. При реализации такого подхода, основные усилия были направлены на разработку эффективных методов быстрого вычисления коэффициентов характеристического уравнения. Такие методы имеют названия прямых. Популярным методом этого типа является метод Данилевского. Он давал довольно большую погрешность, но в тоже время имел очень большую скорость получения результата. Мы предпримем попытку анализа возможности использования этого метода в современных условиях. Попытаемся обозначить возможные границы применения этого метода, и так же найти области науки, где пользоваться методом Данилевского было бы очень удобно. Большое число задач математики и физики требует отыскания собственных значений и собственных векторов матриц, т.е. отыскания таких значений + и отыскания этих нетривиальных решений. Здесь Из курса алгебры известно, что нетривиальное решение системы (1) существует тогда и только тогда, когда где Е
- единичная матрица. Если раскрыть определитель Определитель Различают полную проблему собственных значений, когда необходимо отыскать все собственные значения матрицы А
и соответствующие собственные векторы, и частичную проблему собственных значений, когда необходимо отыскать только некоторые собственные значения, например, максимальное по модулю собственное значение . Идея метода Данилевского состоит в том, что матрица А
приводится к “нормальной форме Фробениуса”, имеющей вид: Характеристическое уравнение для матрицы Р
имеет простой вид т.е. коэффициенты при степенях Приведение матрицы А
к нормальной форме Фробениуса Р
осуществляется последовательно построкам, начиная с последней строки. 1. Приведем матрицу к виду Пусть где Следующий шаг - приведение Таким образом И так далее: 2. Рассмотрим нерегулярный случай, когда матрица, полученная в результате подобных преобразований приведена уже к виду Таким образом обычная процедура метода Данилевского не подходит из-за необходимости деления на ноль. В этой ситуации возможно два случая. 2.1 Предполагаем, что левее В результате на необходимом нам месте оказывается ненулевой элемент 2.2 Рассмотрим второй нерегулярный случай, когда в матрице Обратим внимание на то, что матрица Сомножитель Указанный подход становится неудовлетворительным при вычислении собственных значений матриц, имеющих порядок m в несколько десятков (и тем более сотен). В частности, одним из недостатков является так же то, что точность вычисления корней многочлена высокой степени данным методом чрезвычайно чувствительна к погрешности (накапливающейся со скоростью геометрической прогрессии) в коэффициентах, и на этапе вычисления последних может быть в значительной степени потеряна информация о собственных значениях матрицы. Тесты метода и ПО см. В Приложении Б. Определение. Квадратная матрица Р порядка m называется подобной матрице А , если она представлена в виде Теорема. Характеристический определитель исходной и подобной матрицы совпадают . Доказательство. Идея метода Данилевского состоит в том, что матрица А подобным преобразованиям приводится, к так называемой нормальной форме Фробениуса Теорема. Пусть Тогда Доказательство.Тривиально следует из того, что Домножая левую и правую часть этого равенства слева на S , имеем Входные параметры: Квадратная матрица порядка n*n. Рекомендуется, чтобы она была хорошо обусловлена. Выходные параметры: Получаем коэффициенты при степенях . Обозначим некоторые выводы по проделанной работе: Во время освоения данного метода мы не могли пропустить некоторые минусы метода Данилевского: - Погрешность накапливается со скоростью геометрической прогрессии. - Приходится решать достаточно сложное уравнение порядка n (если решать с помощью приближенных метод, снова получаем некоторую погрешность) - В программном варианте используются достаточно большие объемы оперативной памяти, к примеру, приходится хранить до 4 матриц порядка n*n. Но так же нельзя не остановиться на очевидных плюсах метода: - Метод удобен для нахождения собственных векторов практически любой матрицы. Рекомендуется рассматривать матрицы меньше порядка нескольких десятков. - Данный метод очень удобен в программировании (на этапе разработки ПО проблем практически не возникало). В целом метод все-таки не рекомендуется для решения задач, требующих высоких точностей. Но из-за своей простоты, и высокой скорости, подходит для больших массивов, не требующих отсутствие погрешности. 1. Основы численных методов: Учебник для вузов/ В.М. Вержбицкий. – М.: Высш. Шк., 2002. – 840 с.: ил. 2. Высшая математика для экономистов: Учебник для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – 2-е изд., перераб. и доп. – М.: ЮНИТИ, 2004. – 471 с. 3. Интернет. 4. Библия Delphi/ М.Е. Фленов – СПб.: БХВ-Петербург, 2005. – 880 с.: ил. unit MainUnit; interface uses Windows, …, Buttons; type Matrix = array of array of real; TForm1 = class(TForm) … private { Private declarations } // Процедура "перестановки" матрицы, возвращает true если все хорошо function Remove(Var rez: Matrix; i: integer): boolean; // Умножение 2-х матриц procedure Multiple(a,b:Matrix; Var rez: Matrix); // Возвращение решений function FindDet(Var a:Matrix):string; // Обнуление матриц procedure Zero(Var a:Matrix); public { Public declarations } end; var Form1: TForm1; implementation {$R *.dfm} function TForm1.FindDet(Var a: Matrix):string; Var i,j : integer; M,Mob,bac : Matrix; flag : boolean; begin SetLength(M,Length(a[1]),Length(a[1])); SetLength(Mob,Length(a[1]),Length(a[1])); SetLength(bac,Length(a[1]),Length(a[1])); flag:=true; for i:=Length(a[1])-2 downto 0 do // Построение матриц BEGIN // Обработка случая 2.1 if (a[i+1,i]=0) and (not Remove(a,i)) then begin // Если ничего не помогло flag:=false; Break; end; // Обнуление всех матриц Zero(M); Zero(Mob); Zero(bac); // Построение матриц М for j:=0 to Length(a[i])-1 do begin Mob[j,j]:=1; Mob[i,j]:=a[i+1,j]; M[j,j]:=1; M[i,j]:=-Mob[i,j]/a[i+1,i]; if i=j then M[i,j]:=1/a[i+1,i]; end; // Умножение матрицы А на М Multiple(a,M,bac); // A*M Multiple(Mob,bac,a); // M^(-1)*(A*M) END; // Обработка случая 2.2, если надо if not flag then begin M:=nil; Mob:=nil; // Находим матрицу С и выводим ее коэффициенты SetLength(bac,1,length(a)-i-1); for j:=i+1 to length(a)-1 do bac[0,j-i-1]:=a[i,j]; // Матрица C Result:='('+FloatToStrF(bac[0,0],ffFixed,10,3); for i:=1 to Length(bac)-1 do Result:=Result+','+FloatToStrF(bac[0,i],ffFixed,10,3); Result:=Result+'),'; // "Урезаем" матрицу А до состояния B, см. 2.2 пункт алгоритма SetLength(a,i+1,i+1); // Вызываем рекурсивно процедуру Result:=Result+FindDet(a); end else begin Result:='('+FloatToStrF(a[0,0],ffFixed,10,3); for i:=1 to Length(a)-1 do Result:=Result+','+FloatToStrF(a[0,i],ffFixed,10,3); Result:=Result+')'; end; bac:=nil; end; procedure TForm1.bbPlusClick(Sender: TObject); begin sgInData.ColCount:=sgInData.ColCount+1; sgInData.RowCount:=sgInData.RowCount+1; if sgInData.ColCount=11 then ShowMessage('Attention!!! Полученные результаты имеют малую точность'); end; procedure TForm1.bbMinusClick(Sender: TObject); begin if sgInData.ColCount<3 then Exit; sgInData.ColCount:=sgInData.ColCount-1; sgInData.RowCount:=sgInData.RowCount-1; end; procedure TForm1.bbOpenClick(Sender: TObject); Var k : real; f : textfile; a,i,j : integer; begin OpenDialog1.Filter:='Все файлы (*.*)|*.*| Файлы .txt (*.txt)|*.TXT'; OpenDialog1.Title:='Выбор файла для этой проги'; OpenDialog1.FilterIndex:=2; if OpenDialog1.Execute then begin AssignFile(f,OpenDialog1.FileName); Reset(f); end else Exit; ReadLn(f,a); sgInData.ColCount:=a; sgIndata.RowCount:=a; for i:=0 to a-1 do begin for j:=0 to a-1 do begin Read(f,k); sgIndata.Cells[j,i]:=FloattoStr(k); end; ReadLn(f); end; CloseFile(f); end; procedure TForm1.bbFindClick(Sender: TObject); Var a :matrix; i,j :integer; begin try SetLength(a,sgInData.ColCount,sgInData.RowCount); for i:=0 to sgInData.RowCount-1 do for j:=0 to sgInData.RowCount-1 do a[i,j]:=StrToFloat(sgInData.Cells[j,i]); except begin a:=nil; ShowMessage('STOP! Неправильный ввод, проверьте входные данные'); Exit; end; end; OutData.Clear; OutData.Lines.Add('Коэффициенты характеристического уравнения'); OutData.Lines.Add(FindDet(a)); a:=nil; end; procedure TForm1.Multiple(a, b: Matrix; var rez: Matrix); var i,k,j : word; Begin for i:=0 to Length(a[1])-1 do for k:=0 to Length(a[1])-1 do begin // Обновление занятых матриц rez[i,k]:=0; for j:=0 to Length(a[1])-1 do rez[i,k]:=rez[i,k]+a[i,j]*b[j,k]; end; end; function TForm1.Remove(var rez: Matrix; i: integer): boolean; Var j,k : integer; E,bac : Matrix; begin Result:=false; for k:=0 to i-1 do // Ищем ненулевой элемент слева if rez[i+1,k]<>0 then begin Result:=true; Break; end; if not Result then Exit; SetLength(E,Length(rez[1]),Length(rez[1])); SetLength(bac,Length(rez[1]),Length(rez[1])); for j:=0 to Length(rez[1])-1 do E[j,j]:=1; for j:=0 to Length(rez[1])-1 do begin // Меняем две строки местами в матрице E E[i,j]:=-E[i,j]-E[k,j]; E[k,j]:=-E[i,j]-E[k,j]; E[i,j]:=-E[i,j]-E[k,j]; end; Multiple(rez,E,bac); // A*M Multiple(E,bac,rez); // M^(-1)*(A*M) E:=nil; bac:=nil; end; procedure TForm1.Zero(var a: Matrix); Var i,j: integer; begin for i:=0 to Length(a)-1 do for j:=0 to Length(a[0])-1 do a[i,j]:=0; end; end. Результаты работы программы с теми же входными данными: Рис 1. Приложение Б
(продолжение) Результаты работы программы с теми же входными данными: Рис 2.
|