МИНИСТЕРСТВООБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное агентство по образованию
Государственное образовательное учреждение
Высшегопрофессионального образования
«Оренбургскийгосударственный университет»
Факультетэкономики и управления
Кафедра математическогообеспечения информационных систем
КУРСОВАЯРАБОТА
по дисциплине«Численные методы»
Прямой методвращения векового определителя
ОГУ061800.8006.18 ООО
Руководитель работы
____________________Ващук И.Н.
«_____» _______________ 2006 г.
Исполнитель студент гр. 04ММЭ
________________Широбоков П.Д.
«_____» ________________ 2006 г.
Оренбург 2006
Оглавление
Введение. 3
Постановка задачи… 4
Описание метода. 5
Сходимость метода. 8
Описание входных ивыходных данных… 9
Заключение. 10
Список литературы… 11
Приложение А… 12
Приложение Б… 19
Введение
Численные методы решенияпроблемы собственных значений до конца 40-х годов, сводились, в основном, крешению характеристического уравнения. При реализации такого подхода, основныеусилия были направлены на разработку эффективных методов быстрого вычислениякоэффициентов характеристического уравнения. Такие методы имеют названияпрямых. Популярным методом этого типа является метод Данилевского. Он давалдовольно большую погрешность, но в тоже время имел очень большую скоростьполучения результата.
Мы предпримем попыткуанализа возможности использования этого метода в современных условиях.Попытаемся обозначить возможные границы применения этого метода, и так же найтиобласти науки, где пользоваться методом Данилевского было бы очень удобно.
Постановказадачи
Большое число задачматематики и физики требует отыскания собственных значений и собственныхвекторов матриц, т.е. отыскания таких значений +/>,для которых существуют нетривиальные решения однородной системы линейных алгебраических уравнений
/> , (1)
и отыскания этихнетривиальных решений.
Здесь /> -квадратная матрицапорядка m, /> — неизвестный вектор — столбец.
Из курса алгебрыизвестно, что нетривиальное решение системы (1) существует тогда и толькотогда, когда
/>, (2)
где Е — единичнаяматрица. Если раскрыть определитель /> ,получим алгебраическое уравнение степени m относительно />.Таким образом задачаотыскания собственных значений сводится к проблеме раскрытия определителя /> по степеням /> и последующему решениюалгебраического уравнения m — й степени.
Определитель /> называется характеристическим (или вековым ) определителем, а уравнение (2) называется характеристическим (или вековым ) уравнением.
Различают полнуюпроблему собственных значений, когда необходимо отыскать все собственныезначения матрицыА и соответствующие собственные векторы, и частичнуюпроблему собственных значений, когда необходимо отыскать только некоторыесобственные значения, например, максимальное по модулю собственное значение .
Описаниеметода
Идея метода Данилевскогосостоит в том, что матрица А приводится к “нормальной форме Фробениуса”,имеющей вид: /> .
Характеристическоеуравнение для матрицы Р имеет простой вид
/>
т.е. коэффициенты пристепенях /> характеристическогополинома непосредственно выражаются через элементы первой строки матрицы Р.
Приведение матрицы А кнормальной форме Фробениуса Р осуществляется последовательно построкам,начиная с последней строки.
1. Приведем матрицу />
к виду />
Пусть /> Можно проверить, что такойвид имеет матрица />, которая равна />
где
/>/>
Следующий шаг — приведение /> подобным преобразованием к/>. />
Таким образом />
И так далее: />
2. Рассмотримнерегулярный случай, когда матрица, полученная в результате подобных преобразованийприведена уже к виду
/> и элемент /> .
Таким образом обычная процедура метода Данилевского не подходит из-за необходимости деления на ноль. Вэтой ситуации возможно два случая.
2.1 Предполагаем, чтолевее /> есть элемент /> /> Тогда домножая матрицу /> слева и справа наэлементарную матрицу перестановок />,получаем матрицу />.
В результате нанеобходимом нам месте оказывается ненулевой элемент />,уже преобразованная часть матрицы не меняется, можно применять обычный шагметода Данилевского к матрице />.
2.2 Рассмотрим второйнерегулярный случай, когда в матрице /> элемент/> и все элементы левее, тоженулевые. В этом случае характеристический определитель матрицы /> можно представить в виде
/> где /> и/> - единичные матрицысоответствующей размерности, а квадратные матрицы /> и/> имееют вид:/>
Обратим внимание на то,что матрица /> уже имеет нормальнуюформу Фробениуса, и поэтому сомножитель /> просторазвертывается в виде многочлена с коэффициентами, равными элементам первойстроки.
Сомножитель /> нужно преобразовывать. Для развертывания можно применять метод Данилевского, приводя матрицу /> подобными преобразованиямик нормальной форме Фробениуса.
Указанный подходстановится неудовлетворительным при вычислении собственных значений матриц,имеющих порядок m в несколько десятков (и тем более сотен). В частности, однимиз недостатков является так же то, что точность вычисления корней многочленавысокой степени данным методом чрезвычайно чувствительна к погрешности(накапливающейся со скоростью геометрической прогрессии) в коэффициентах, и наэтапе вычисления последних может быть в значительной степени потерянаинформация о собственных значениях матрицы.
Тесты метода и ПО см. ВПриложении Б.
Сходимостьметода
Определение. Квадратнаяматрица Р порядка m называется подобной матрице А, если она представленав виде />, где S — невыродженнаяквадратная матрица порядка 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(Vara: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 (notRemove(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 thenM[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 dobac[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 thenShowMessage('Attention!!! Полученные результаты имеют малую точность');
end;
procedure TForm1.bbMinusClick(Sender:TObject);
begin
if sgInData.ColCount
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-1do 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 dorez[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 doE[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 doa[i,j]:=0;
end;
end.
ПриложениеБ
/>
Результаты работы программы с теми жевходными данными:
Рис 1.
/>
ПриложениеБ
(продолжение)
/>/> /> />
/>
/> />
/>
/> />
/>
Результаты работы программы с теми жевходными данными:
Рис 2.
/>